NeurIPS 2023 Spotlight | 图对比学习的可证训练问题

论文作者：

作者单位：

论文链接：

https://arxiv.org/pdf/2309.13944.pdf

https://github.com/voidharuhi/pot-gcl

背景介绍

图对比学习大多遵循 InfoMax 准则，即最大化两个增广图之间的互信息，其损失函数 InfoNCE 形式为：

我们可视化了不同 GCL 模型的节点训练情况的分布。下图为三种 GCL 方法的节点平均 InfoNCE loss 值的柱状图，横轴为 InfoNCE loss 的数值，纵轴为节点个数。可以看到，有很大部分的节点训练结果较远地偏离了平均情况，尤其是 InfoNCE 较大的节点，也就是训练相对较差的节点，因此我们是不愿看到这种情况的。

节点的“结构特性”：节点紧致性

为了形式化定义节点的“结构特性”，我们提出了节点紧致性（node compactness）来衡量节点对于 GCL 训练的适应情况。这是一种来自于节点对 GCL 准则，也就是 InfoMax 的遵守程度的直接定义，具体形式为：

图对比学习的可证训练（POT）

基于“节点紧致性”的定义，我们提出了图对比学习的“可证训练”。这里“可证”指的是，我们在训练中最大化“节点紧致性”这样一个最差情况的理论下界，也就是对节点训练中的稳定性的最差可能情况进行了可证明的优化保证。实现上，可以将节点的紧致性加入交叉熵损失函数中，令目标为“1”。我们提出的可证训练目标为：

我们的可证训练可以作为一种插件，加入各种 GCL 方法中，与 InfoNCE 结合后，总体的对比学习损失函数为：

可证训练的整体框架如下。首先 GCL 的增广策略会对应某个增广的集合。左边是正常的 GCL 过程，可以看作首先从这个增广的集合中随机采样出一些增广图，之后进行对比学习得到 InfoNCE 损失；右侧是我们的“可证训练”，我们得到每个节点的紧致性之后利用二元交叉熵优化该值，保证了每个节点都能够根据其本身的“结构特性”去适应 GCL 训练并遵守 GCL 的准则。

但是，我们仅仅给出了节点紧致性的形式，其中的 min 并不能显式地直接使用，因为增广的范围是非常多的，为 NP-hard 问题。因此，我们想要把节点紧致性的形式简化，即由我们容易知道的一些量构成（输入的图，GNN 的参数，以及增广策略的参数）。因此，一个很好的策略是通过上下界传播的方式求解。因为上下界传播做的事就是针对有界的输入，通过整个神经网络，推得输出的上下界。

我们的问题中，“输入的上下界”就是增广策略所定义的，是已知的；而节点紧致性的 min 正对应了“输出的上下界”（z 由 GNN 得到，W 可以看作一个 linear 层，因此节点紧致性是 GNN+线性层的输出下界）。应用上下界传播有两个挑战：输入的离散性（图结构），以及网络的非线性部分。这两个挑战都可能导致上下界传播的失败。但是，它们是可以通过一些近似算法解决的。

5.1 离散->连续

首先是将离散的输入上下界变换为连续输入的上下界。定义 3 是增广范围的形式化描述，其中我们限制了仅限删边、无向图、以及全局和每个节点局部的删边个数。很多增广策略都可以转化为这种形式的定义，例如 GRACE 的随机删减边，Q 就是边的个数乘以删边概率，而 q_i 就是节点 i 的度乘以删边概率。

我们可以利用消息传递矩阵，也就是度归一化的邻接矩阵，来达到我们连续化的目的。因为消息传递矩阵的值可以取 0-1 之间的值，是连续的，而邻接矩阵的值只能取 0 或 1。因此，我们将基于邻接矩阵的定义 3 转化为了定义 4，定义 5 规定了消息传递矩阵每个元素的上下界（我们限制删边是因为这是常见的做法，也可以不局限于删边，那么定义 4 会相应的改变）。

5.2 非线性激活->线性界

为了解决网络的非线性，也就是激活函数的问题，我们采用了定义 5 描述的线性上下界。因此，激活函数输出的上下界可以由激活函数输入的上下界的线性函数表示。α 和 β 是线性上下界的参数，由 p 的上下界计算得到。

之后，定理 1 给出了消息传递的上下界计算方式（也就是由上一层的 embedding 得到这一层激活函数前的上下界的方式）。

5.3 图对比学习可证训练的实现

有了上述的一些定义和定理，定理 2 给出了节点紧致性的计算的实现形式。通过上下界传播，我们成功化简了 min，得到了可以通过一系列矩阵运算得到的形式，便于实现。

整体的算法流程如下。首先是通过 GNN 得到 embedding，进而得到 InfoNCE loss；之后我们根据定理 2 可以计算出节点紧致性，进而得到 POT loss；把这两个 loss 加在一起，进行反向传播，就是 POT+GCL 的训练过程。

实验结果表明，我们的 POT 作为一种插件式增强，可以提升现有 GCL 的性能，并且能够与半监督方法相比或略微超过（之前的 GCL 很难做到）。

我们还进行了一些可视化的实验来表明我们可证训练以及节点紧致性设计的合理性。首先是 POT 能够改进我们设计的节点紧致性，因为 POT 中显式地优化了这个指标。这也是比较意料之中的。

另一方面，POT 对于 InfoNCE 本身的优化也有帮助。可以看到，使用 POT 之后，节点的 InfoNCE 整体向左偏移（优化的更好了），并且其分布也更加向中心集中，也就是说原来很多难以训练的节点由于 POT 的训练而被关注到、优化好了。

POT 能够反映不同增广策略的特点。由于 GRACE 是所有边以相同概率删掉，而 GCA 的删除策略与度相关，因此节点在不同 GCL 增广策略下对增广的敏感程度是不同的。POT 的分布反映了这种差异性。

POT 如我们所想，确实反映了节点的本质的“结构特性”，也就是在 GCL 增广下的脆弱程度。我们对同一区间内紧致性的节点的 InfoNCE 的方差取了平均（方差能够反映这种“脆弱”性）。可以看到，节点紧致性越大，InfoNCE 的方差越小，也就是节点越“脆弱”。这个实验结果恰好验证了节点紧致性具有我们所期望的性质。

首先，我们探究了图对比学习的训练情况，发现了其训练不平衡的问题。其次，我们定义“节点紧致性”去描述节点在图对比训练中的本质的“结构特性”。我们基于该指标提出了“可证训练”。这种训练模式对节点的最差训练情况提供了优化上的保证。大量实验验证了我们训练框架的有效性。最后，本方法的思路是将一个优化目标转化为一个优化下界的问题，将普通的训练转化为对训练情况进行保证。这种思路是对训练加以理论保证的一种实现方式。

🔍

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

进入知乎首页搜索「PaperWeekly」

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