论文分享 | NIPS2022 | 图对比学习的新范式和增广方法

引言

本次推送将带来两篇关于图对比学习（GCL）的文章，第一篇主要关注于图对比学习能work的原因以及是否存在更为高效的学习范式，第二篇主要关注于在图对比学习中的增广方法。

文章概览

1、Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination论文地址：https://arxiv.org/abs/2206.01535目前大多数关于GNN的工作都集中在（半）监督学习上，导致了一些缺点，包括对标签的严重依赖、概括性差和鲁棒性弱。为了解决这些问题，自监督学习，通过前置任务来提取信息知识，而不依赖人工标签，已经成为图数据的一种有前途的、趋势性的学习范式。然而，目前的自监督学习方法，特别是图对比学习（GCL）方法，在设计中需要大量的计算，阻碍了它们扩展到大型图。本文试图提出一种新的方法来解决这一问题。2、Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum论文地址：https://arxiv.org/abs/2210.02330图对比学习（GCL）是通过扩充图来学习节点表示的一种学习方法，近年来受到了广泛的关注。尽管各种图形增强策略层出不穷，但一些基本问题仍然不清楚：GCL学习到的表示中基本上编码了什么信息？在不同的扩充之后，是否有一些通用的图形扩充规则？如果是，它们是什么？它们能带来什么见解？本文试图通过建立GCL和图谱之间的联系来回答这些问题。

论文细节

1

1、面向的主要问题

图对比学习能获得成功的原因是什么？是否存在更省时间，占用更少内存的图对比学习范式？

2、相关背景知识介绍

2.1 什么是对比学习？为什么要使用对比学习？

pic1-2-2.1

图源：SimCLR

• 代理任务+目标函数
• 更好地利用没有label的数据

2.2 DGI(Deep Graph Infomax)

图表示学习领域里对比学习的开山之作，通过基于互信息（变量间相互依赖性）的量度进行对比学习。

2.2.1  设置

为节点特征集合， 为邻接矩阵。

2.2.2  目标

训练一个编码器 （GCN），使得 为节点的表示向量。

2.2.3  方法

1. 通过邻接矩阵不变，重组目标子图特征得到负样本实例。

2. 通过编码器获得正例子图和负例子图的节点表示。

3. 通过 Readout 函数得到正样例图级别的summary vector：

   在本文中，使用的Readout函数是所有节点特征的简单平均值。

4. 定义一个 discriminator ，用来计算 patch-summary 对的得分。若patch被summary包含，则得分高。

5. 通过对比学习对编码器进行训练。

3、DGI方法的缺陷

求证：DGI能起作用的真正原因并非是通过patch-level representations和graph summary进行对比学习，而是将positive nodes和negative nodes区分开。

命题一：Sigmoid 函数不适用于权重被 Xavier 初始化的 GNN 生成的 summary vector，且 summary vector  中的元素非常接近于相同的值。

证明一：使用Xavier初始化的GNN，在通过 sigmoid 和 ReLU 激活后生成得到summary vector是一个近似于常数的向量。

证明过程：使用Xavier初始化的GNN每个节点服从初始分布进行适当的展开后，通过激活函数，可得：

证明二：即使是经过训练后的GNN，生成的summary vector仍然是一个近似于常数的向量

实验：

表一：不同数据集上summary vector的值

命题二：即使生成的summary vector是个常数向量，依然不影响模型最后的结果。

证明过程：实验：将summary vector替换为不同值的常数向量进行计算，发现除了全置为0之外并不影响模型最后的结果。

表二：不同常量值对模型结果的影响

那么问题来了，既然summary vector并不会影响模型最后的结果，那模型为什么起了作用呢？

回顾：我们重新回顾DGI中的损失函数，并使用我们已知的信息（summary vector是个常数向量）进行简化。假定判别器是一个线性层，即 。则可以简化成：

结论：DGI 真正做的工作是区分正确特征的一组节点和错误特征的节点。即，使用一个固定的向量去区分合理／不合理的节点嵌入矩阵。

4、DGI方法的改进

既然我们已经知道了DGI工作的原理（将一组正确的节点和错误的节点区分开来），那我们是否可以对其进行简化？既然DGI的原理是“区分正确和错误的节点”，我们不妨直接对节点进行区分，而不像DGI使用一个向量对它进行判别。这样一来，这个问题就可以简化为一个二分类问题，即：我们希望正样例的节点尽可能的趋近于1，而负样例的节点尽可能趋近于0。

Loss 也可以写成一个二分类问题：

这样一来，模型的改进方法就呼之欲出了，我们只需要让一系列正例节点和负例节点都经过一样的编码路径，然后区分开这两组节点，就达到了DGI相同的效果。

图三：GGD (Graph Group Discrimination)结构图

4.1 Augmentation（图的增广）

使用边缘剔除和特征剔除进行图的增广，如删去一些边，给特征补0。

4.2 Corruption（图的破坏）

通过DGI和MVGRL相同的技术，随机改变Gˆ的拓扑结构 Xˆ中节点的顺序。

4.3 The Siamese GNN （GNN投影网络）

GNN投影网络由两个部分组成，即一个GNN编码器和一个投影网络。GNN编码器可以由各种GNN来替代，例如GCN和GAT。本文采用GCN作为编码器。投影网络是一个多层感知机。在数据聚合阶段，所有的正负例数据样本都用相同的聚合技术进行聚合，例如和、均值和线性聚合。

4.4 Group Discrimination （群体区分）

采用二元交叉熵（BCE）损失来区分两组节点样本。

5、模型推断

1. 固定 GNN encoder、MLP predict 的参数，获得初步的节点表示
2. MVGRL 多视图的方法引入多跳子图的全局信息 , 其中是邻接矩阵
3. 得到局部表示和全局表示的聚合  

6、实验

6.1 实验数据集

五个小数据集：Cora, CiteSeer, PubMed, Amazon Computers, Amazon Photos 三个大数据集：ogbn-arxiv, ogbnproducts，ogbn-papers100M

6.2 节点分类任务

小数据集分类任务：X, A, Y 意味着特征，邻接矩阵和标签

大数据集分类任务：上图为ogbn-arxiv，中图为ogbn-products，下图为ogbn-papers100M

6.3 节点分类效率

上图：每个epoch的训练时长，下图：训练所需内存（MB）

7、模型拓展

通过对特征矩阵X进行随机来破坏图G的拓扑结构，通过区分正样本（即用真实边生成的节点）和负样本，我们推测该模型可以通过学习如何识别生成的节点是否具有正确的拓扑结构，并输出有效的节点嵌入。

定理1 给定一个图 ，一个被破坏的图和一个编码网络 ，我们认为正样例  的分布为 、 负为。优化组别损失相当于等于最大化和之间的Jensen-Shannon熵。

简单来说，我们可以看到损失的最大化与的最大化是一样的，其中代表Jenson-Shannon熵。因此，通过对损失L的优化，和趋于分离。因此，群体辨别在直觉上是在学习避免犯错误（使编码器偏向于避免错误的样本）。因为通过分离两个分布，可以逐渐趋向于节点嵌入的最佳分布。节点嵌入的最佳分布。由于最佳分布与是不相干的，如果生成的嵌入能避免类似于分布外样本，即负样本，它就能在理想情况下更接近于与最优分布。因此，训练好的模型可以提高生成的节点嵌入的质量。

8、未来的工作

1、二元组鉴别（即对以不同拓扑结构生成的节点进行分类）是否可以推广到鉴别多个组？

2、是否有其他的负样本生成技术来创造一个更困难的负样本进行区别？

2

1、面向的主要问题

• 在理论层面：

1. 图对比学习（GCL）学习到的表示中基本上编码了什么信息？
2. 在不同的增广之后，是否有一些通用的图增广规则？如果是，它们是什么？它们能带来什么见解？

在实践层面：

1. 应该在增广图中保留或者丢弃哪些信息？
2. 不同的图增强策略之间是否有一些一般规则？
3. 如何使用这些一般规则来验证和改进当前的GCL方法？

2、问题引入：再论图对比学习

传统的图对比学习框架往往由三部分组成：图增强，编码表示和对比学习误差优化，如下图所示：

目前，我们有很多图增强策略，如启发式策略（随机删去边和节点，特征掩码）和基于学习的策略（解耦，GAN等），但仍然没有基本的图增强注册。那么，在某些情况下，图结构在增广之后可能会出现较大的变化。这个时候，一个值得思考的问题便出现了：正样本和负样本之间是否还存在一般性的界限?一般来说，图结构的改变本质上是图谱上不同频率的强度发生变化，那我们似乎可以尝试着，从谱域的视角对图的增广进行探索。

3、一些预备知识

3.1 图的拉普拉斯矩阵和低频/高频分量

我们把图的度矩阵设为对角矩阵，邻接矩阵设为，那么图的拉普拉斯矩阵可以定义为 ，把邻接矩阵归一化之后有，则拉普拉斯矩阵可以写为 。因为  是对称矩阵，那么可以通过特征值分解为 ,便可以把特征值在一半以下的特征值作为低频分量的幅值，在一半以上的特征值作为高频向量的幅值。

3.2 InfoNCE损失

pic-2-3.2

其中，意味着在增广下的节点表示，指模型训练温度

4、理论证明

4.1 从谱域角度看，什么样的信息应该被保留？

实验一：保留高频/低频信息，随后逐步加入低频/高频信息，探究不同强度的低频/高频增广对模型训练的效果。测试不同的特征空间对图增广的影响，而排除特征值的影响。如保留20%的高频信息，则图拉普拉斯矩阵为：

保留20%的低频信息则为

实验结果：

（图中准确率越高，证明增强之后的图和原图更相似，对比学习的效果越好） （1）当保留最低部分的频率时，取得了最佳性能 （2）当高频部分中更多的频率被涉及时，性能一般会上升 （3）当图谱中高频的信息逐渐被增广且加入时，原图和增广图部分的频谱差异逐渐增加结论：两个对比图增广的图谱间高频部分的差异应该大于低频部分的差异 （ GAME rule --Graph AugMEntation rule）

4.2 结论的正确性分析

实验二：我们将实验一中图的增广方法换为9种当前主流的图增广，分别是MVGRL中提出的PPR matrix, heat diffusion matrix, pair-wise distance matrix、GCA中 Degree, Eigenvector, PageRank 级别的随机删除以及 GraphCL 的 random node dropping, edge perturbation, subgraph sampling。在每一种增广后，我们利用特征值扰动公式来计算这些增广后图特征值的改变。并采用Cora数据集进行模型正确性的度量。

从增广后的图谱中可以看出，第一行中，MVGRL 提出的三种增强方法更好地符合 GAME rule 的要求，即它们和原图谱间的低频部分差异小，高频部分差异大。而在实际测试中，也验证了这一假说。

InfoNCE的数学形式推导：本文中对InfoNCE的数学形式进行了推导,得到了在不考虑激活函数的情况下InfoNCE的上界，即和分别表示原图谱和增强图谱的第i个频率， 为网络参数时，有

当我们想要最大化 InfoNCE Loss时, 会在和相似的项上增大，而和的相似也表明了原图和增强图在第i个频率分量上表现出了不变性。由此，我们得到第二条结论：满足GAME准则的情况下，这两个增广的共性低频部分将会被模型着重捕捉，而低频信息对模型更加有益。

5、模型改进

既然我们已经得到了这些结论，那怎么通过这些结论对模型进行改进呢？在现有的图增强方法中，正负例都由同一个图谱生成，很难形成符合GAME准则的正负对。那我们不妨先从图谱本身的频率出发，先进行一个保留低频，改变高频的变换，再进行其他GCL方法的增广，如图所示：

我们定义图的增广主要为边的增加和，两者推导过程相似，在文章的附录中证明了我们的优化目标是最大化这样一个式子

1. Matching Term（匹配项）: 为了最大化这一项，我们希望  和  尽可能匹配，其中 , 和   分别是特征向量矩阵和原图中关于特征值的函数。在尽可能匹配的情况下，  相当于指导了边的增加。同时根据GAME准则，我们增加的边的在高频部分的振幅应该高于低频部分的振幅，进一步严格，我们要求振幅和频率的函数是一个单调增函数。我们又发现，拉普拉斯矩阵的频谱  恰好也是关于频率的单增函数，那么我们只需要训练一个从  到  的函数变换，即可获得满足条件的边增加。

2. Entropy Regularization（熵正则）：增加边改变的不确定度，使得模型不只是关注于图谱中特定的一些边，而让更多的边参与到优化过程中；

3. Lagrange Constraint Conditions （拉格朗日约束条件）：限制解的范围，防止出现无意义的解

5.1 解方程

1. 首先求  对  的偏导，有
   一番证明后，我们得到了  能取到极值的条件:
2. 因为4b是个超越方程，没有解析解，所以我们转向4a，在迭代过程中，我们认为会趋向于稳定，所以可以用上一轮的加入下一轮的迭代中，即写成
   便解得：
3. 因为，,未知，所以我们将其建模成一个matrix scaling 问题，并利用 Sinkhorn's Iteration 进行求解，得到每次迭代的差别上界
4. 同理，可以建模出边的删减和新的图增广矩阵：

6、实验

6.1 基线模型和数据集

本文选择了BCE loss（DGI, MVGRL）、InfoNCE loss（GRACE, GCA, GraphCL）以及 CCA loss（CCA-SSG），并从三者中选出了一个模型与这种图增强方法融合，验证其有效性。

6.2 结果

pic-2-6.2

6.3 可视化

本文进一步可视化了图增强后的图谱，发现符合对GAME rule中最优对比的假说。

6.4 超参数

除此之外，本文还探究了不同的根据拉普拉斯矩阵L生成C矩阵的方法，及熵部分中的敏感度

7、模型的不足

这项工作主要集中在同质图而不是异质图，后者的高频信息更为有用。

供稿丨钟诚

编辑丨柴劲阳

责编丨刘晴雯

供稿人：钟诚丨研究生二年级丨研究方向：智慧医疗丨邮箱：[e-mail]