https://arxiv.org/pdf/2012.07437

Distance-wise Graph Contrastive Learning，2020，arxiv preprint

总结：在半监督图学习任务中，作者通过实验发现，CL对模型性能的提升主要集中在那些远离有标签数据的节点上。基于这个发现，作者认为现有的这些GCL方法，GL和Graph Learning的结合方式是不协调的，提出了一种新的半监督图对比学习方法DwGCL。具体来说，作者根据节点的PageRank值进行distance-wise augmentation，根据TIG（作者自己定义的一个东西）值选取Contrastive Pair，最后利用KL散度定义了模型的损失函数。总的来说，个人认为这篇文章切入角度很有趣，其动机让人耳目一新，和其他论文有很大区别。不过比较可惜的是，从实验结果来看，DwGCL带来的性能提升并不多，平均大概有1%，但是DwGCL模型和其他GCL方法相比更复杂，感觉得不偿失。

1. 简介

1.1 摘要

Contrastive learning (CL) has proven highly effective in graph-based semi-supervised learning (SSL), since it can efficiently supplement the limited task information from the annotated nodes in graph. However, existing graph CL (GCL) studies ignore the uneven distribution of task information across graph caused by the graph topology and the selection of annotated nodes. They apply CL to the whole graph evenly, which results in an incongruous combination of CL and graph learning. To address this issue, we propose to apply CL in the graph learning adaptively by taking the received task information of each node into consideration. Firstly, we introduce Group PageRank to measure the node information gain from graph and find that CL mainly works for nodes that are topologically far away from the labeled nodes. We then propose our Distance-wise Graph Contrastive Learning (DwGCL) method from two views: (1) From the global view of the task information distribution across the graph, we enhance the CL effect on nodes that are topologically far away from labeled nodes; (2) From the personal view of each node’s received information, we measure the relative distance between nodes and then we adapt the sampling strategy of GCL accordingly. Extensive experiments on five benchmark graph datasets show that DwGCL can bring a clear improvement over previous GCL methods. Our analysis on eight graph neural network with various types of architecture and three different annotation settings further demonstrates the generalizability of DwGCL.

在图学习领域，对比学习已经被证明是一种高效的半监督学习方法，可以在有效地从图标记节点中补充有限的任务信息。但是，现有的GCL方法忽略了图拓补结构和标记节点导致图中信息分布不均匀的问题，只是单纯的将CL方法应用到整张图上，而这种结合方式是不协调的。为了解决这个问题，我们提出通过考虑每个节点接收到的人物信息，将CL自适应地应用到图学习中。首先，我们引入Group PageRank计算每个节点从图中能获取多少信息，发现CL主要适用于那些在拓扑结构上远离有标签节点的节点。然后我们提出了Distance-wise Graph Contrastive Learning（DwGCL）。DwGCL从两个角度出发：（1）global view，即考虑任务信息在整张图上的分布，我们在那些远离有标签节点的节点上增强CL效应；（2）person view，即考虑每个节点接收到的信息，我们测量节点之间的相对距离，然后相应地使用GCL的采样策略。5个标准图数据集上的大量实验表明，和现有GCL方法相比，DwGCL能带来显著的性能提升。通过对8中不同GNN和3中不同标注设置下实验结果的分析，我们进一步证明了DwGCL的通用性。

1.2 本文工作

背景： GNNs能有效利用图拓扑结构中的关系信息解决各类图问题。虽然在半监督任务中GNN依旧可以从有限标签中学习不错的知识，但是忽略了大量无标签节点中蕴藏的信息，这限制了其在半监督任务中的性能。最近很多方法引入对比学习来解决半监督图学习任务，比如DGI、GRACE、GraphCL等等。

动机： 当学习GNNs时，任务信息会从有标签节点传播到无标签节点。但是由于有标签节点分布不均匀，因此建模能力随着距离有标签节点越来越远而变差。如下图1所示：

现有的GCL方法都忽略了图信息在图中分布不均匀的问题，单纯地将对比学习用到整个图上，这种结合方式是不协调的。

本文工作： 为了解决这个问题，作者提出了DwGCL方法，通过考虑任务信息分布来更灵活地将CL应用到图学习中。

2. 方法

2.1 动机

先在这部分介绍下Group PageRank以及GCL相关知识，为后面DwGCL的介绍做准备。

2.1.1 Group PageRank

PageRank是一种常用来计算节点重要性的算法，公式如下：

$\pi_{p r}=(1-\alpha) \boldsymbol{A}^{\prime} \pi_{p r}+\alpha \boldsymbol{I}$

其中$A^{\prime}=A D^{-1}$，$D$表示度矩阵，$I\in\mathbb R^n$表示转移概率，通常用$1/n$填充，$\alpha\in(0,1]$表示随机游走restart概率。

本文作者希望计算的是一群节点（属于同一个类别的所有有标签节点）的影响力，所以作者改造了一个Group PageRank算法：

$\boldsymbol{\pi}_{g p r}(c)=(1-\alpha) \boldsymbol{A}^{\prime} \boldsymbol{\pi}_{g p r}+\alpha \boldsymbol{I}_{\boldsymbol{c}}$

其中$c\in[0,k)$表示类别index，$I_c\in\mathbb R^n$表示转移概率：

$\boldsymbol{I}_{c}^{i}\left\{\begin{array}{ll} \frac{1}{\left|\boldsymbol{L}_{c}\right|}, & \text { if the } i \text {-th node is a labeled node of class } c \\ 0, & \text { otherwise } \end{array}\right.$

其中$L_c$表示类别$c$下有标签节点数量。作者首先单独计算每个类别的Group PageRank向量，然后合起来作为最终Group PageRank矩阵$Z \in \mathbb{R}^{n * k}$。$Z_{i,j}$表示类别i向节点j提供的监督信息。在实际应用中，Group PageRank矩阵$Z$可以并行计算：

$Z=\alpha\left(E-(1-\alpha) A^{\prime}\right)^{-1} \boldsymbol{I}^{*}$

其中$E$为单位矩阵，$I^*\in\mathbb R^{n*k}$表示所有$I_c$的组合。

2.1.2 TIG值

通过Group PageRank矩阵$Z$，我们可以知道每种类型有标签节点对无标签节点的影响力。此外，作者还想了解这些信息对下游任务能起到多大作用。

作者定义Topology Information Gain（TIG）表示节点从有标签节点那里获取到的有用信息。理想状态下，每个无标签节点获取到的信息应该集中于某一个类别，这样就能轻松预测其标签。所以对于节点$i$，其TIG值计算方法如下：

$\begin{array}{c} Z_{i, c}^{*}=\frac{1}{2} Z_{i, c}\left(1+\frac{X_{i} \mathcal{P}_{c}^{T}}{\left\|\boldsymbol{X}_{i}\right\|\left\|\mathcal{P}_{c}\right\|}\right), \mathcal{P}_{c}=\frac{1}{\left|L_{c}\right|} \sum_{i \in \boldsymbol{L}_{c}} \boldsymbol{X}_{i} \end{array}$

$\begin{array}{c} T_{i}=\max \left(\boldsymbol{Z}_{i}^{*}\right)-\lambda \frac{\left(\sum_{c=0}^{k-1} \boldsymbol{Z}_{i, c}^{*}\right)-\max \left(\boldsymbol{Z}_{i}^{*}\right)}{k-1} \end{array}$

其中$max(·)$表示最大值函数，$\lambda$表示对来自其他类别信息的惩罚因子，$\mathcal P_c$表示这个节点类别的原型表示。作者假设每个未标记节点对来自不同类别的信息都有自己的特殊偏好，所以使用节点嵌入$X_i$和类别原型$\mathcal P_c$之间的余弦相似度来调整前面计算的PageRank值$Z_i$。

得到TIG值后，现在就可以探究CL在图上的工作机制了。作者在CORA数据集上，使用GCN作为编码器进行了一组实验。

作者将测试集节点按照TIG值大小，从小到大排列，然后分成4组。然后在这4组数据对CL进行消融实验，结果如下图2所示：

可以看到，随着TIG值不断增大，节点能接收到更多有用信息，GNN的性能越来越好，但是CL给模型带来的提升却越来越小。这说明：“CL主要提升的是在拓扑结构上远离有标签数据的那部分无标签节点上的性能”。

2.2 Distance-wise图对比学习

基于2.1节的实验以及分析，作者提出了一种图对比学习方法，以distance-wise方式将CL整合到图学习中。

具体来说，在图学习中最终要的两个组件就是：数据增强和负样本采样。作者针对这两个部分分别提出了distance-wise增强和distance-wise负采样。除了这两点外，作者还提出为不同的子图分配不同的对比损失权重。这样那些接受到少量有效监督信息的节点可以从CL中得到更多补充信息。

2.2.1 Distance-wise增强

传统GCL数据增强策略大体可以分成：随机和启发式两类，但是这两类方法都没有考虑不同节点能获取到的有效监督信息量是不同的。作者提出的增强策略考虑下面两方面因素：

• TIG值：TIG值越低的节点，被选中实施数据增强的概率越大。
• 考虑节点增强的扩散，作者通过降低增强节点周围子图的概率来动态调整选择概率。

具体增强策略伪代码如下：

这部分伪代码有点复杂，我没有细看，只是大概了解了其思想。

2.2.2 Distance-wise正/负采样

现有的对比学习，对于某个锚点，要么将其余所有样本作为负样本，要么将不同类别的所有样本作为负样本。本文作者基于节点间的距离，为锚点选取合适的z正/负样本。对于链各个节点之间的距离，作者从3个方面考虑：

1. 全局拓扑距离。节点的PageRank值包含了全局拓扑信息和标记信息，作者计算两个节点PageRank值之间的KL散度作为全局拓扑距离：

   $\boldsymbol{D}_{i, j}^{g}=\operatorname{KL}\left(\boldsymbol{p}_{i}, \boldsymbol{p}_{j}\right), \text { with } \quad p_{i}=\operatorname{NORM}\left(Z_{i}^{*}\right)$

2. 局部拓扑距离。作者将两个节点之间的mini jump hop数作为局部拓扑距离。

3. 节点嵌入距离，即两个节点嵌入间的余弦距离。

因此两个节点间的最终距离定义为：

$\boldsymbol{D}_{i, j}=\mathrm{S}\left(\boldsymbol{D}_{i, j}^{g}\right)+\lambda_{1} \mathrm{~S}\left(\boldsymbol{D}_{i, j}^{l}\right)+\lambda_{2} \mathrm{~S}\left(\boldsymbol{D}_{i, j}^{e}\right)$

其中$S(·)$表示缩放函数，将范围缩放到$[0,1]$之间。得到所有节点之间的距离后，开始进行正/负采样工作。

具体来说，对于锚点节点$i$，其对应的正样本集合就是距离$i$最近的若干节点，负样本集合就是距离$i$不远不近的那些节点：

$\boldsymbol{P}_{i}=\boldsymbol{R}_{i}\left[0: \operatorname{post}_{e n d}\right], \boldsymbol{N}_{i}=\boldsymbol{R}_{i}\left[\operatorname{negt}_{b e g}: \text { negt }_{\text {end }}\right]$

2.3 DwGCL目标函数

2.3.1 有监督损失

$\mathcal F(·)$表示GNN编码器，对于有标签节点其交叉熵损失定义为：

$\begin{aligned} t &=\mathcal{F}(\boldsymbol{X}, \boldsymbol{A}, \theta) \\ \mathcal{L}_{C E} &=-\frac{1}{|\boldsymbol{L}|} \sum_{i \in \boldsymbol{L}} \sum_{c=0}^{k-1} \boldsymbol{y}_{i} \log p\left(\boldsymbol{t}_{i}^{c}, \tau\right) \end{aligned}$

其中$t_i$表示节点$i$的嵌入向量，$\theta$表示GNN参数。

2.3.2 无监督损失

除了有监督损失，DwGCL还包含3中无监督损失：self-consistency损失、正样本对的对比损失和负样本对的对比损失。

self-consistency损失定义如下：

$\mathcal{L}_{s}^{i}=\mathrm{KL}\left(\mathcal{F}\left(\boldsymbol{X}_{\boldsymbol{p}}, \boldsymbol{A}_{\boldsymbol{p}}, \boldsymbol{\theta}\right)_{i}, \mathcal{F}(\boldsymbol{X}, \boldsymbol{A}, \widetilde{\boldsymbol{\theta}})_{i}\right)$

即增强前后节点嵌入间的KL散度。需要注意的是$\widetilde \theta$完全复制自$\theta$，但是不进行反向传播。同样地，定义下面两个对比损失：

$\begin{aligned} \mathcal{L}_{p}^{i} &=\frac{1}{\left|\boldsymbol{P}_{i}\right|} \sum_{j \in \boldsymbol{P}_{i}} \mathrm{KL}\left(\mathcal{F}\left(\boldsymbol{X}_{\boldsymbol{p}}, \boldsymbol{A}_{\boldsymbol{p}}, \boldsymbol{\theta}\right)_{i}, \mathcal{F}(\boldsymbol{X} \boldsymbol{A}, \widetilde{\boldsymbol{\theta}})_{j}\right) \\ \mathcal{L}_{n}^{i} &=\frac{1}{\left|\boldsymbol{N}_{i}\right|} \sum_{j \in \boldsymbol{N}_{i}} \mathrm{KL}\left(\mathcal{F}\left(\boldsymbol{X}_{\boldsymbol{p}}, \boldsymbol{A}_{\boldsymbol{p}}, \boldsymbol{\theta}\right)_{i}, \mathcal{F}(\boldsymbol{X} \boldsymbol{A}, \widetilde{\boldsymbol{\theta}})_{j}\right) \end{aligned}$

这样完整的无监督损失可以表示成：

$\mathcal{L}_{U}^{i}=\mathcal{L}_{s}^{i}+\mu_{1} \mathcal{L}_{p}^{i}-\mu_{2} \mathcal{L}_{n}^{i}$

和现有GCL方法不同，作者在使用无监督损失的时候，根据接收到的监督信息，给不同子图分配不同的权重。具体来说基于TIG值，给每个节点分配一个不同的CL权重$wj_i$。权重计算方式如下：

$\boldsymbol{w}_{i}=w_{\min }+\frac{1}{2}\left(w_{\max }-w_{\min }\right)\left(1+\cos \left(\frac{\operatorname{Rank}\left(\boldsymbol{T}_{i}\right)}{n} \pi\right)\right)$

这样整个模型的最终损失定义为：

$\mathcal{L}=\mathcal{L}_{C E}+\frac{1}{n} \sum_{i=0}^{n-1} \boldsymbol{w}_{i} \mathcal{L}_{U}^{i}$

3. 实验

3.1 实验结果

3.1.1 对比实验

3.1.2 DwGCL的泛化能力

使用不同类型GNNs作为图编码器，实验结果如下图3所示：

3.1.3 消融实验

对DwGCL的不同组件进行消融，结果如下表3所示：

3.2 案例分析

3.2.1 DwGCL可以增强图中那些under-represented节点的CL效果

从上图4实验结果可以看到，在TIG值比较小的时候，和普通GCL相比，DwGCL可以显著提高模型性能。

3.2.2 DwGCL可以有效缓解过平滑问题

感觉比较扯，效果也不明显。

3.2.3 样本大小和样本难度之间的权衡

Contrastive Pair的采样在对比学习中十分重要。从上图5可以看到，负样本和锚点间距离太远或者太近都不好，这是符合常理的。因为太远了，两者太容易被区分，太近了两者太相似起不到对比的作用，都会影响对比学习的效果。另外，起初负样本数量越大，模型性能越好，但是大到一定数量反而会降低模型性能。