查看原文
其他

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

王睿嘉 PaperWeekly 2022-11-01

 


©作者 | 宋睿智

来源 | 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 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算


📬 投稿通道:

• 投稿邮箱:hr@paperweekly.site 

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

• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿


△长按添加PaperWeekly小编




🔍


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

进入知乎首页搜索「PaperWeekly」

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

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存