NeurIPS 2022 | 基于精确差异学习的图自监督学习

©作者 | 宋睿智

来源 | MIND Laboratory

论文标题：

Graph Self-supervised Learning with Accurate Discrepancy Learning

收录会议：

NeurIPS 2022

论文链接：

https://arxiv.org/abs/2202.02989

节点表示学习对结构公平性有所要求，即在度小和度大节点上都有良好的性能表现。最近研究表明，图卷积网络 (GCN) 常对度小节点的预测性能较差，在广泛存在的度呈长尾分布的图上表现出结构不公平。图对比学习 (GCL) 继承了 GCN 和对比学习的优势，甚至在许多任务上超越了半监督 GCN。那么 GCL 针对节点度的表现又如何呢？是否可能为缓解结构不公平提供新的思路？

本文介绍

图神经网络的自监督学习 (GNNs) 旨在以无监督的方式学习图的精确表示，以获得用于各种下游任务的可转移表示。预测学习和对比学习是图自监督学习的两种最流行的方法。然而，它们有自己的缺点。虽然预测学习方法可以学习相邻节点和边之间的上下文关系，但是它们不能学习全局图级相似性。对比学习虽然可以学习全局图级相似性，但是其最大化两个不同的受干扰的图之间的相似性的目标时，可能导致表示不能区分具有不同属性的两个相似的图。

为了改进这些缺点，在本文中，作者提出了一个框架，旨在学习原始图和受干扰的图之间的精确差异，称为基于差异的自我监督学习 (D-SLA)，即创建具有不同相似度的给定图的多个扰动，并训练模型来预测每个图是原始图还是被干扰的图。

本文贡献：

1. 提出了一种新的图自监督学习框架，其目标与对比学习完全相反，其目的是学习使用区分器（discriminator）区分图和受干扰的图，因为即使是轻微的扰动也可能导致图的完全不同的属性；

2. 为被干扰的图进行图编辑距离而无需任何额外工作，以在表示空间中保持图之间的精确差异量；

3. 在化学、生物和社会领域的各种基准上进行预培训和微调验证了 D-SLA，在这些基准上，D-SLA 显著优于基准。

模型介绍

传统的图对比学习中，与驻留在连续域中的图像相比，图本质上是离散的数据结构，因此即使有轻微的扰动，它们的属性也可能会完全不同。例如，图（d）和（e）中的两个分子表明，尽管它们具有高度相关的结构，但他们的分子作用完全不同。

为了解决这个问题，作者提出了一种新的自监督学习方法，旨在学习图之间的差异，称为基于差异的自监督学习（DSLA）。具体来说，首先像对比学习方案一样干扰给定的图形，但不是像对比学习那样最大化干扰图形之间的相似性，而是旨在了解它们之间的差异。

为了实现这个目标，首先设计了一个区分器，它可以学习区分真实图形和受干扰的图（如下图（c-1））。这使得模型能够了解可能在很大程度上影响图形全局属性的小差异。然而，仅仅知道两个图是不同的是不够的，还要知道它们之间的确切差异量。

下图是 D-SLA 的整体框架，主要分为了三个部分。

A.基于图区分的差异学习（Discrepancy Learning with Graph Discrimination）

个具有代表性的 GCL 模型 DGI[2] 和 GraphCL[3]，分析其结构公平性。具体地，我们将GCN、DGI 和 GraphCL 分别在 Cora、Citeseer、Photo 和 Computer 数据集上训练，并根据度将节点分组，计算这些组的平均准确率，如图所示。

为进一步反映结构公平性，我们用线性回归拟合这些散点，斜率越小，该模型对度偏差越公平。Photo 和 Computer 数据集上的实验结果，参见论文。从图中可以看出，DGI 和 GraphCL 尾节点的平均准确率高于 GCN，且回归线的斜率也较小。这一有趣的现象说明，无监督的 GCL 方法比半监督的 GCN 更具有结构公平性。

GCL结构公平性的理论分析

图定义为 ，其中 是 个节点组成的节点集 ， 是边集， 是节点特征矩阵， 代表节点 的特征。边集可以用邻接矩阵 表示，如果 ，则 。给定无标签的训练集，每个节点属于 个社区 之一。假设增广集 包含所有可能的拓扑增广策略，节点 的自我中心网络 可能产生的所有正例集为 。

GCL 的目标是学到合理的 GCN 编码器 使得正例对间相近，而负例对间相远。这里，我们聚焦于拓扑增广和单层 GCN：

其中 是转移矩阵 的第 行， 是加自环的邻接矩阵， 是度矩阵。我们使用社区指示器 

其中  是社区中心， 代表 范数。社区指示器 的误差形式化为：

基于以上定义，记正例对表示间距离不大于 的节点集为 。

假设非线性变换具有 -Lipschitz 连续性，即 ，拓扑增广均匀采样 条边 ，且存在半径 使任意增广都有 。可证：

该定理建立了表示的社区内集中程度与 中正例对对齐程度间的关系。具体地，社区内集中需要较小的 。对比学习优化框架正是缩小正例对间的距离，因而 GCL 满足要求。

接下来，我们证明 GCL 还具有社区间分散的特性。对于增广集 ，将两节点间的增广距离定义为其变换前表示的最小距离，

其中 是增广后的邻接矩阵 的第 行， 为增广后的度。基于增广距离，我们引入 -augmentation 的定义用于衡量变换前表示的集中程度。

越大的 和越小的 说明变换前表示越集中。假设表示被归一化 ，且 。我们同时约束社区间距离和社区指示器误差：

为更准确地分配社区，不等式右边应接近 ，因而需要 较小。我们进一步通过对比框架中的正例对对齐损失约束 ：

所有定理证明参见原文。综上，社区间距离和社区指示器的误差由两个因素主导：1）正例对的对齐，较好的对齐可使  较小，从而 较小；2）增广表示的集中程度，更集中则 更大。

小的 和大的 会直接减小社区指示器的误差，并为社区间分散提供小的 。需要强调的是，第一个因素是 GCL 的对比目标，反映 GCL 结构公平的原因。而第二个因素取决于图增广策略的设计。在此驱动下，我们提出可以进一步集中增广表示的图增广方式。

GRADE

图增广

我们通过同时扰动原始特征和拓扑生成两个增广 和 ，并将两增广所得节点表示记为 和 。

为获得更集中的增广表示，需要增加社区内边，减少社区间边。由于尾节点和头节点的结构属性不同，我们分别设计了不同的拓扑增广策略，如图所示。为扩展尾节点邻域以包含更多相同社区的节点，我们将锚尾节点 与采样所得相似节点 的自我中心网络插值。为防止增广过程注入许多不同社区节点，进一步依据 和 间的相似性调整插值比率。对于头节点，我们则利用相似性采样来提纯其邻域，尽量移除社区间边。

形式化地，我们基于节点表示间的余弦相似度构建相似度矩阵 ，对 有 ，否则 。对于任意尾节点 ，自多峰分布 中采样出节点 ，其中 是 中对应于节点 的行向量。

然后，将 和 的邻居分布插值，为尾节点 创建新的相似度感知邻域。这里，节点 的邻居分布定义为 ，如果 ，否则 。为减少不同社区节点带来的噪音，相似度 用作插值比率 ，

然后，从邻居分布 中进行不替换采样。对任意头节点 ，定义用于提纯的相似性分布。具体地，如果 ，则节点 的相似性分布为 ，否则 。基于相似性分布 ，不替换地采样出 个邻居，其中 是边丢弃率。通过这种相似性采样，不同社区间的边往往会被移除，从而保留有效的邻域信息。

至于特征增广，我们随机产生掩码向量 来隐去节点特征中的部分维度。掩码 中的每个元素都是从贝努利分布 中采样所得，其中超参数 是特征丢弃率。因此，增广后的特征 为：

在实现时，设置阈值 区分尾节点和头节点。增广 和 应用相同的超参数 和 。

优化目标

对节点 ，不同图增广得到的节点表示 和 构成正例对，而其他节点的表示被视为负例。因此，每个正例对 的目标函数定义为：

其中 是温度系数， 是 ， 是多层感知器（MLP），用于增强表达能力[4]。因此，总体目标函数是最大化所有正例对的平均值：

实验

我们将 GRADE 与最具代表性的 GCL 模型 DGI、GraphCL、GRACE、MVGRL 和 CCA-SSG 进行比较，并同时评估半监督 GCN 以供参考。对于 GCL 模型，每个模型以无监督方式进行训练后，所得节点表示喂入逻辑回归分类器，并采用常见的两种划分方式进行评估：1）半监督划分，每类 20 个标记节点用于训练，1000 个节点用于测试；2）监督划分，1000 个节点用于测试，其余节点用于训练。GCN 同样遵循上述划分进行训练。

节点分类

10 次独立实验的平均值和标准差如上表所示。在大多数情况下，GRADE 优于所有基线方法。GRADE 在 Cora 和 Citeser 数据集上的提升更显著，因为这两个数据集的平均节点度约为 3，存在大量尾节点。为验证 GRADE 在提高尾节点分类性能的同时保留了头节点的性能，我们根据阈值 将 Cora 的测试节点分为尾节点和头节点，并在小提琴图中绘制其平均准确率。正如预期，无论尾节点还是头节点，GRADE 都有较明显的性能提升。

公平性分析

为定量分析结构公平性，定义组平均为所有以度分组的平均准确度的平均值，而偏差定义为方差。

基于这些指标，评估结果如下表所示。可以看出，GRADE 降低了所有数据集的偏差，并保持最高的组平均。

可视化

为证明 GRADE 使社区更集中，我们可视化了 Cora 数据集上 GRADE 和基线的节点表示。以蓝色社区为例，图对比学习基线虽比 GCN 有更清晰的社区边界，但蓝色节点仍很分散。在 GRADE 中，它们聚集在一起，说明增广策略发挥了重要作用。

更多实验，请参考原文。

参考文献

[1] Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong Rawlsgcn: Towards rawlsian difference principle on graph convolutional network. In WWW, 2022. 

[2] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019. 

[3] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurIPS, 2020. 

[4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In ICML, 2020.

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·