🤖 machine learning

Fast and Featureless Node Representation Learning with Partial Pairwise Supervision

本文介绍了对比 FUSE，这是一个快速且统一的框架，通过优化带有轻量级模块度近似的谱对比目标，实现在仅有部分成对监督且无节点特征的图上可扩展的节点表示学习。

原作者： Sujan Chakraborty, Saptarshi Bej

发布于 2026-05-20

📖 1 分钟阅读☕ 轻松阅读

原作者： Sujan Chakraborty, Saptarshi Bej

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在举办一场规模宏大、混乱不堪的派对，成千上万的人正在相互寒暄。你想根据他们认识谁、喜欢谁将他们分组，但这里有个难题：你没有名字，没有个人简介，也没有照片。 你只知道两件事：

谁站在谁附近（图结构）。
来自主办方的几条具体备注，说明“这两个人是最好朋友”（正样本对）和“这两个人互相讨厌”（负样本对）。

这就是论文《对比式 FUSE》试图解决的问题。这是一种新方法，旨在让计算机理解这些社交网络，而无需任何关于个人的数据，只需他们的连接关系以及关于谁应与谁在一起或分离的几条规则。

以下是论文如何利用简单的类比来分解这个问题：

1. 问题：无特征的派对

大多数分析网络（如社交媒体或科学论文）的计算机程序通常依赖“特征”——例如一个人的年龄、职业或他们使用的词汇。但在许多现实世界的情境中（例如预测基因如何相互作用或分析匿名购买数据），这些信息要么不存在，要么不可靠。

作者们表示：“让我们忽略缺失的数据。让我们只关注谁与谁相连的地图，以及我们拥有的关于谁喜欢谁的少量线索。”

2. 解决方案：“对比式 FUSE"

作者们创建了一个名为对比式 FUSE的框架。你可以把它想象成一个聪明、快速的组织者，它使用两个主要工具来整理派对宾客：

工具 A：“社群磁铁”（模块化）
想象一个巨大的隐形磁铁，将那些已经站在紧密圆圈里的人拉得更近。在论文中，这基于模块化。它审视连接的网络并指出：“这些人都在同一个角落聚会；让我们确保他们的数字‘座位’彼此靠近。”这保留了网络中自然形成的群体（社群）。
工具 B：“规则手册”（对比监督）
现在，想象主办方递给你一份具体的指令清单：“把爱丽丝和鲍勃安排在紧挨着的位置”，以及“确保查理和戴夫位于房间的两侧”。
论文称此为成对监督。它创建了一个“符号拉普拉斯矩阵”（一个复杂的数学术语，指代规则手册），将朋友拉近，将敌人推远。

魔法所在： 与其他试图从头猜测整体画面的方法不同，该方法同时结合了“社群磁铁”和“规则手册”。它在遵守具体规则的同时学习群体划分。

3. 速度黑客：“轻量级近似”

通常，计算如何在庞大的网络中移动每个人，就像试图一次性计算体育场里每个人的风阻一样。这既缓慢又计算成本高昂。

作者们发现了一个巧妙的捷径。他们意识到，不需要对每一次计算都进行繁重、精确的数学运算。相反，他们使用了一种轻量级近似。

类比： 与其称量海滩上的每一粒沙子以知道总重量，不如取一小勺有代表性的沙子并乘以倍数。这并非完全精确，但准确率高达 99%，且耗时仅为原来的极小部分。
结果： 这使得系统能够在合理的时间内训练包含数百万条连接的图（例如 OGBN-Products 数据集），而旧方法则会崩溃或耗时无穷。

4. 工作原理（过程）

论文描述了一个简单的迭代循环：

开始： 给每个人分配一个随机座位。
拉与推：
- “社群磁铁”将邻居拉近。
- “规则手册”将朋友拉近，将敌人推远。
调整： 将每个人向同时满足两条规则的方向稍微移动。
归一化： 确保每个人的“大小”保持一致（以免一个大声的人主导整个房间）。
重复： 重复此过程数千次，直到座位安排完美。

5. 结果：快速且准确

作者在真实世界数据上测试了该方法，包括：

引文网络： （哪些科学论文相互引用）。
购物数据： （哪些产品被一起购买）。
大规模数据集： （如包含 160 万篇论文的 OGBN-ArXiv）。

发现：

性能： 在整理这些群体方面，其表现与最先进的现有方法一样好，甚至更好。
速度： 它显著更快。在某些大型数据集上，它比其他流行方法快13 到 14 倍。
无需特征： 它在未使用任何“个人资料数据”（如文本或用户人口统计数据）的情况下实现了这一目标，完全依赖提供的结构和少量规则。

总结

对比式 FUSE 是一种全新的、超快速的方法，用于在不知道人们（或节点）是谁的情况下，整理混乱的网络，前提是你知道谁与谁相连，并拥有几条关于谁应与谁为友或为敌的具体指令。它将网络的自然分组与这些具体规则相结合，并利用巧妙的数学捷径，使其速度足以应对世界上最大的网络。

技术摘要：对比 FUSE

问题陈述

本文解决了在显式节点特征不可用、不可靠或无法迁移（无特征或特征稀疏图）的图中学习有意义节点表示的挑战。与仅依赖图结构的传统无监督图嵌入方法，或依赖数据增强的自监督对比学习方法不同，本研究聚焦于一种监督信息仅以部分成对约束形式存在的场景。这些约束指示两个节点是应相似（必须链接）还是应不相似（不能链接），这种场景常见于计算生物学（如合成致死性预测）、推荐系统（隐式反馈）以及节点属性无法访问的隐私敏感网络等领域。

目标是开发一个快速、可扩展的框架，通过联合优化以下两点来学习判别性节点嵌入：

结构一致性：保留图的全局社区结构。
成对一致性：遵循提供的有符号成对约束（吸引相似对，排斥不相似对）。

方法论：对比 FUSE

作者提出了对比 FUSE，这是一个统一的框架，通过谱形式将基于模块度的结构学习与对比监督相结合。

1. 目标函数

核心目标函数 $J(S)$ 结合了结构项和对比项：
$J(S) = \text{Tr}(S^\top \tilde{B}S) - \lambda \text{Tr}(S^\top L_c S)$

结构项（模块度）：第一项最大化模块度，鼓励同一社区内的节点拥有相似的嵌入。作者使用修正的模块度矩阵 $\tilde{B} = A - \frac{d\mathbf{1}^\top}{2m}$ ，其中 $A$ 是邻接矩阵， $d$ 是度向量， $m$ 是总边数。
对比项：第二项利用从成对监督矩阵 $Y$ （其中 $Y_{ij} \in \{+1, -1, 0\}$ ）构建的有符号归一化对比拉普拉斯（ $L_c$ ）。该项作为正则化项，在嵌入空间中拉近正样本对并推远负样本对，并通过每个节点的对比度进行归一化，以防止高度受约束的节点占据主导地位。

2. 通过梯度近似实现高效优化

一项关键创新在于对模块度梯度的处理。模块度目标的精确梯度涉及度 - 度校正项（ $d(d^\top S)$ ），这对于大型稠密图而言计算昂贵且数值不稳定。

近似：作者提出了一种轻量级近似，用无权重全局和 $\mathbf{1}^\top S$ 替换加权度聚合 $d^\top S$ 。
理论依据：论文证明（定理 2），在关于嵌入分布和图度结构的温和假设下，所提出的近似梯度的上升方向与精确梯度保持紧密对齐（有界余弦相似度）。这使得在保留模块度寻结构行为的同时，能够显著节省计算成本。

3. 优化算法

该框架采用投影梯度上升：

计算结构梯度（ $G_{mod} = \tilde{B}S$ ）和对比梯度（ $G_{con} = -L_c S$ ）。
组合梯度： $G = G_{mod} + \lambda G_{con}$ 。
更新嵌入： $\tilde{S} = S + \eta G$ 。
投影：通过行归一化（ $S_i \leftarrow \tilde{S}_i / \|\tilde{S}_i\|_2$ ）强制单位范数约束，以防止平凡的缩放解。
下游分类：学习到的嵌入被用作基于 GNN 的分类器（GCN、GAT 或 GraphSAGE）的输入特征，随后通过 MLP 预测成对关系。

主要贡献

新颖的对比公式：提出了一种在成对监督下进行节点表示学习的方法，直接将标记的节点对约束整合到嵌入目标中，而无需节点特征。
有符号归一化对比拉普拉斯：提出了一种特定的拉普拉斯算子，通过以归一化方式同时吸引相似对和排斥不相似对，增强了基于模块度的学习。
可扩展优化方案：开发了一种计算高效的模块度梯度近似方法，在保持与精确目标理论一致性的同时显著降低了开销，从而支持在百万级边图上进行训练。

实验结果

该方法在多样化的基准数据集上进行了评估，包括引文网络（Cora、CiteSeer、PubMed）、共购图（Amazon Photo、WikiCS）以及大规模 OGB 数据集（ArXiv、Products）。

性能：与最先进基线（包括无监督方法 DeepWalk、Node2Vec，自监督对比方法 DGI、GRACE、SGCL，以及谱方法 COLES）相比，对比 FUSE 在下游节点分类性能（准确率和宏平均 F1）方面取得了具有竞争力或更优的结果。
可扩展性与效率：该框架展示了显著的运行时优势。在中等规模数据集上，它比 GRACE 和 SGCL 等对比基线快得多。在大规模 OGBN-ArXiv 数据集上，其速度比基于随机游走的方法（DeepWalk、Node2Vec）快约13–14 倍，同时保持了具有竞争力的性能。由于内存限制，其他几个基线无法在 ArXiv 上运行。
消融实验：移除对比项（设置 $\lambda=0$ ）导致性能持续下降，证实了在无特征设置中学习判别性表示时成对监督的必要性。

意义与主张

本文主张，对比 FUSE有效地弥合了结构社区检测与成对监督学习之间的差距。其主要意义在于提供了一种快速且可扩展的替代方案，以应对现有对比学习方法通常依赖昂贵的深度编码器、广泛的数据增强或消息传递架构的问题。

通过将受模块度启发的结构学习与对比监督相结合，该框架使得在节点特征缺失但成对关系已知的场景下能够高效地学习节点嵌入。作者强调，这种方法对于需要高效重新计算嵌入的演化图或特定上下文图，以及生物信息学和隐私敏感网络等必须仅依赖结构学习的领域尤为有价值。该方法在预测准确性和计算效率之间取得了有利的平衡，使其适用于大规模现实世界应用。