基于部分成对监督的快速无特征节点表示学习

《Neural Networks》：Fast and Featureless Node Representation Learning with Partial Pairwise Supervision

　　摘要：我们提出了Contrastive FUSE，这是一种快速且统一的框架，用于在仅有部分节点对标签而无节点特征的图中进行可扩展的节点表示学习。与现有方法不同，我们直接优化一个谱对比目标函数，该函数将基于社区的结构信号与带符号的节点对约束相结合。为支持大规模训练，我们用一种轻量级的近似方法替代了计算成本较高的模块度梯度，这种方法在保持模块度结构搜索特性的同时显著降低了计算成本。由此形成了一种高效的优化方案，具有自然的梯度分解和自适应的学习率调整机制，即便在百万边规模的图上也能实现快速迭代更新。在基准引文网络、大型共同购买图以及OGB数据集上的大量实验表明，Contrastive FUSE能够在不依赖节点特征的情况下实现具有竞争力甚至更优的对比分类性能，同时相比现有基准方法具有显著的运行速度提升。这些结果凸显了将受模块度启发的结构学习与对比监督相结合，在实现高效且可扩展的节点表示学习方面的有效性。

引言：学习有意义的节点表示是图学习中的核心问题，其应用范围涵盖社交网络、生物相互作用网络、推荐系统以及科学知识图谱等领域。其目标是将节点嵌入到低维向量空间中，从而保留图的结构性特征以及与任务相关的关系。长期以来，人们一直在探索基于随机游走、谱分解和自编码架构的无监督图嵌入方法，例如DeepWalk（Perozzi等人，2014年）、Node2Vec（Grover和Leskovec，2016年）以及变分图自编码器（VGAE）（Kipf和Welling，2016年）。最近，诸如DGI（Veli?kovi?等人，2018年）、GRACE（Zhu等人，2020年）和SGCL（Shu等人，2021年）之类的自监督方法则采用了基于增强的对比学习目标，这类目标旨在最大化相同节点在不同扰动下的表示一致性，同时将其与其他节点区分开来。在本研究中，我们考虑了一种不同的对比学习概念。我们不依赖于基于增强的一致性，而是研究在无特征或特征稀疏的图中，在部分观察到的节点对监督下的节点分类问题。具体而言，我们假设监督以节点对约束的形式存在，这些约束指示两个节点应被视为相似还是不同，而明确的节点属性则不可用、不可靠，或在不同图实例之间无法迁移（Chen等人，2025年；Etzion和Moshe，2025年）。我们的目标是直接从图结构和节点对约束出发，以快速且可扩展的方式学习出具有区分能力的节点嵌入。这种场景在多个领域中普遍存在。在计算生物学中，许多问题都是通过节点对关系来定义的。例如，合成致死性预测模型将基因视为蛋白质-蛋白质相互作用网络中的节点，通过致死性和非致死性基因对来提供监督。同样，蛋白质-蛋白质相互作用和药物-靶标相互作用预测往往主要依赖于结构连接性，因为节点属性往往不完整、存在噪声、依赖于上下文，或者对于新出现的实体来说根本不可用（Xiao和Deng，2020年；Yuan等人，2021年）。在推荐系统中，点击或购买等隐性反馈通常通过节点对偏好信号来表示，而明确的用户或物品特征往往较为稀疏或不可靠（Cao等人，2024年；Sidana等人，2022年）。在医疗保健或社交网络等注重隐私的场景中，由于法律或制度限制，节点属性可能无法获取，这就需要仅依靠结构信息进行学习（Etzion和Moshe，2025年）。在所有这些场景中，监督通常以节点对的形式存在，而嵌入则往往需要针对不断变化或具有特定上下文的图高效地重新计算。为解决这一问题，我们提出了Contrastive FUSE，这是一种基于图结构和节点对约束来学习节点嵌入的快速且可扩展的框架。其核心思想是在传统的模块度最大化目标函数中，加入由带标签的节点对构建的带符号、标准化的对比拉普拉斯矩阵。这一设计能够促使相似节点对的嵌入值相互靠近，同时明确区分不同的节点对，进而保留图的全局结构组织。为实现可扩展的优化，我们还引入了一种模块度梯度的高效近似方法，该方法在保持其结构搜索特性的同时大幅降低了计算开销。由此产生的优化流程采用逐行投影的迭代梯度上升法，无需使用深度编码器、图增强技术或复杂的消息传递架构。我们在包括引文网络、共同购买图以及大规模OGB数据集在内的多种基准数据集上对Contrastive FUSE进行了评估。在各种不同的应用场景下，所提出的方法均能在显著降低运行时间的同时，实现与现有对比基准方法相当甚至更优的节点分类性能。我们的主要贡献如下：1. 我们提出了一种新的对比学习公式，用于在节点对监督下进行节点表示学习，该公式直接将带标签的节点对约束整合到无特征或特征稀疏图的嵌入目标函数中。2. 我们提出了一种带符号、标准化的对比拉普拉斯矩阵，它通过在嵌入空间中同时吸引相似节点对并排斥不同节点对，从而增强基于模块度的结构学习效果。3. 我们基于模块度梯度的近似方法开发了一种计算效率高的优化方案，该方案能够在保持模块度最大化方法的结构正则化特性的同时，实现快速且可扩展的训练。

相关研究：谱聚类长期以来一直是图划分和社区检测领域的基础框架。传统方法通过对方程拉普拉斯算子的不同变体进行特征值分解，从而构建低维节点嵌入，其目标是最小化基于割的标准，如归一化割（Mercado等人，2019年）。与谱割密切相关的是模块度最大化方法（Newman，2006年），该方法旨在寻找那些内部边密度高于随机情况下预期值的图划分。

问题描述：设G=(V,E)为一个无向图，其中|V|=n个节点，邻接矩阵为A∈Rn×n。设d∈Rn为度向量，其中di=∑jAij，m=1/2∑i,jAij为图中的总边数。除了图的结构信息外，我们还有一组由矩阵Y∈{?1,0,+1}n×n编码的节点对监督信号，其中Yij={+1，若(i,j)为正对（如同类别）；?1，若(i,j)为负对；0，若该对未被标记}。

学习目标：我们的目标是学习一个节点嵌入矩阵S=[S1??Sn?]∈Rn×k，其中Si∈Rk，该矩阵需同时满足以下特性：1. 结构一致性：内部连接性更强的节点应具有相似的嵌入值。2. 节点对一致性：正对(i,j)∈P+应被嵌入得较近，而负对(i,j)∈P?则应被嵌入得较远。

结构一致性建模：我们采用了Newman（2006年）定义的模块度概念的稍作修改版本，以适配连续值数据。

数据集：我们在涵盖引文网络、共同购买图以及大规模学术图在内的多种基准图数据集上对所提出的Contrastive FUSE框架进行了评估。具体而言，我们使用了Cora（McCallum等人，2000年）、CiteSeer（Giles等人，1998年）、PubMed（Namata等人，2012年）、WikiCS（Mernyei和Cangea，2022年）、Amazon Photo（McAuley等人，2015年），以及大规模的OGBN-ArXiv（Hu等人，2021年）和OGBN-Products（Hu等人，2021年）数据集，相关细节见表1。

下游分类性能：表2展示了在Cora、CiteSeer、PubMed、WikiCS和Amazon Photo这五个数据集上，Contrastive FUSE的平均下游分类性能。在所有分类器中，Contrastive FUSE始终能取得最佳或接近最佳的性能。需要说明的是，在表格和图表中，我们的算法Contrastive FUSE统一被记为ContFUSE。像COLES和MVGRL这样的基准方法在ArXiV这样规模更大的数据集上无法运行，还会出现内存错误。在逻辑回归模型中，Contrastive FUSE提升了性能。

理论结果：定理1 Contrastive FUSE目标函数的利普希茨光滑性。设J(S)=Tr(S?B?S)?λTr(S?LcS)，其中B?∈Rn×n是图的对称模块度矩阵，Lc∈Rn×n是对称的带符号对比拉普拉斯矩阵。那么梯度?J(S)关于弗罗贝尼乌斯范数是利普希茨连续的。特别地，对于所有的S,S′∈Rn×k，有∥?J(S)??J(S′)∥F≤L∥S?S′∥F，其中L=2∥B?λLc∥2，‖·‖2表示谱范数。因此，J是一个L阶光滑函数。证明：首先注意到B?和Lc都是对称矩阵。定义M:=B??λLc。那么目标函数可以...

时间复杂度分析：我们分析了Contrastive FUSE在每次优化迭代以及整个训练过程中的计算复杂度。设n=|V|为节点数，|E|为边数，P为带标签的对比节点对数量，k为嵌入维度。结构（模块度）梯度可通过Gmod=B?S计算得出，其中B?=A?d1?2m。由于A是稀疏矩阵，只有|E|个非零元素，因此矩阵-向量乘法AS所需的计算时间为O(|E|k)。度修正项则涉及一个秩为一的运算...

可重复性：通过https://github.com/SujanChakraborty/Contrastive_FUSE上的代码，可以完全复现实验结果。该代码提供了相应的Python环境及笔记本文件，所需的Python依赖项可在requirements.txt文件中找到。README.md文件中还提供了逐步运行代码的详细指南。

未标注的浮点数

算法1 CRediT作者贡献声明：Sujan Chakraborty：撰写——初稿、可视化、验证、软件实现、方法设计、形式化分析。Saptarshi Bej：撰写——审阅与编辑、指导监督、资源提供、概念构思。

利益冲突声明：作者声明不存在任何可能影响本文所述工作的已知财务利益或个人关系。

Sujan Chakraborty | Saptarshi Bej