https://arxiv.org/pdf/2006.04131

https://github.com/CRIPAC-DIG/GRACE

Deep Graph Contrastive Representation Learning，2020，arxiv preprint

总结：20年的一篇早期图对比学习的文章，作者主要针对19年发表的DGI模型的两个弊端进行改进，提出了一种比较简单的GCL框架GRACE（现在大部分GCL方法都沿用了这一种框架）。由于现在大部分GCL方法都是采用这种node-level对比框架，数据增强策略也更丰富，因此这篇文章和现有其他GCL方法相比并没有什么亮眼的创新之处。

1. 简介

1.1 摘要

Graph representation learning nowadays becomes fundamental in analyzing graph-structured data. Inspired by recent success of contrastive methods, in this paper, we propose a novel framework for unsupervised graph representation learning by leveraging a contrastive objective at the node level. Specifically, we generate two graph views by corruption and learn node representations by maximizing the agreement of node representations in these two views. To provide diverse node contexts for the contrastive objective, we propose a hybrid scheme for generating graph views on both structure and attribute levels. Besides, we provide theoretical justification behind our motivation from two perspectives, mutual information and the classical triplet loss. We perform empirical experiments on both transductive and inductive learning tasks using a variety of real-world datasets. Experimental experiments demonstrate that despite its simplicity, our proposed method consistently outperforms existing state-of-the-art methods by large margins. Moreover, our unsupervised method even surpasses its supervised counterparts on transductive tasks, demonstrating its great potential in real-world applications.

现如今图表示学习对于分析图结构数据越来越重要。受进来对比方法的成功应用，本文作者通过利用节点级别的对比目标，提出了一种新的框架用于无监督图表示学习。具体来说，作者通过干扰生成两个图视角，然后最大化同一节点在不同视角下节点表示的一致性。为了给对比目标提供不同类型节点上下文信息，作者提出了一种在结构和属性层级生成图视图的混合方案。另外，作者提供了互信息和三元损失两个方面理论上的证明。作者同时在转导和非转导两种设定下，利用真实数据集进行了大量实验。实验结果表明，虽然作者的模型比较简单，但是和其他SOTA方法相比，性能得到了大幅度替身。在transductive任务中，作者的方法甚至不输于同类有监督方法，更证明了其在实际应用中的潜能。

1.2 本文工作

背景： （1）传统的无监督图表示学习方法，比如DeepWalk、node2vec等，它们都是对NLP中skip-gram模型的延伸。这些基于游走的方法过度依赖于网络结构中的邻近信息，通过对比迫使同一条游走路径中的节点具有相似的节点嵌入。（2）对于近年来得到广泛关注的GNNs，虽然在图学习邻域取得了很大的成功，但是大部分GNNs都是有监督的，依赖于大量有标签数据，这在实际应用中有时是不可行的。一些无监督GNNs，比如GraphSAGE，也和DeepWalk等类似，通过矩阵重构来学习节点嵌入，依然过度依赖于图邻接矩阵。（3）对于图对比学习，受CV中基于InfoMax方法的成功，DGI模型将CV中DIM模型延伸到图表示学习中，通过最大化节点间互信息，来学习节点嵌入。

动机： 作者认为DGI模型中的local-global MI maximization框架存在弊端：

• 虽然已经证明了在一定条件下其目标函数等价于最大化输入节点特征和高层级节点嵌入之间的互信息。但是DGI中是把节点和全局图进行对比，为了实现InfoMax目标，需要一个单射函数生成全局图嵌入，而单射属性非常受限，无法实现。在DGI中使用mean-pooling作为readout函数，不能保证图嵌入能从节点中提取有用信息。
• DGI中使用feature shuffling生成新的图视图，在特征矩阵稀疏的时候，不能保证为节点生成不同的上下文信息，导致难以学习对比目标。

作者希望提出一种新的图对比学习框架，解决DGI模型中存在的这些弊端。

本文工作： 作者提出了一种新的图对比学习框架GRACE，解决了DGI模型中存在的两个弊端。

2. 方法

2.1 对比框架

这篇论文属于早期图对比学习研究，和目前各种GCL方法相比，框架没有什么亮眼之处，属于最通用、最基础的GCL框架。文章主要对DGI模型进行改进，后续很多方法都是基于这种框架改进得到。

如上图1所示，GRACE执行步骤大致如下：

1. 生成两个图视角，用$\widetilde G_1$，$\widetilde G_2$表示。

2. 利用GNNs，分别计算两个视角下的图嵌入$U=f\left(\tilde{\boldsymbol{X}}_{1}, \widetilde{A}_{1}\right)$，$V=f\left(\tilde{\boldsymbol{X}}_{2}, \widetilde{A}_{2}\right)$。

3. 计算对比目标。具体来说，以$\widetilde G_1$作为锚点，每个正样本对$(u_i,v_i)$的目标定义为：

   $\ell\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right)=\log \frac{e^{\theta\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right) / \tau}}{\underbrace{e^{\theta\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right) / \tau}}_{\text {the positive pair }}+\underbrace{\sum_{k=1}^{N} \mathbb{1}_{[k \neq i]} e^{\theta\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{k}\right) / \tau}}_{\text {inter-view negative pairs }}+\underbrace{\sum_{k=1}^{N} \mathbb{1}_{[k \neq i]} e^{\theta\left(\boldsymbol{u}_{i}, \boldsymbol{u}_{k}\right) / \tau}}_{\text {intra-view negative pairs }}}$

   其中$\theta(\boldsymbol{u}, \boldsymbol{v})=s(g(\boldsymbol{u}), g(\boldsymbol{v}))$为判别器，$s$为余弦相似度，$g$为非线性映射器（2层MLP）。同理，可以计算以$\widetilde G_2$为锚点时的对比损失。这样整个模型的目标定义为：

   $\mathcal{J}=\frac{1}{2 N} \sum_{i=1}^{N}\left[\ell\left(u_{i}, v_{i}\right)+\ell\left(v_{i}, u_{i}\right)\right]$

GRACE伪代码如下图所示：

2.2 视角生成

在对比学习中，数据增强策略是非常重要的一个组件，不同的增强策略会为节点提供不同的上下文信息。本文作者主要使用 Removing edges (RE) 和 Masking node features (MF) 两种增强策略。

• RE

  即随机去掉原始图的部分边。具体来说，首先随机采样一个mask矩阵$\widetilde{R} \in\{0,1\}^{N \times N}$，服从伯努利分布，即如果$A_{ij}=1$，$\widetilde{\boldsymbol{R}}_{i j} \sim \mathcal{B}\left(1-p_{r}\right)$，否则$\widetilde R_{ij}=0$。其中$p_r$表示删除该边的概率。这样干扰后的邻接矩阵可以表示为：

  $\widetilde{\boldsymbol{A}}=\boldsymbol{A} \circ \widetilde{\boldsymbol{R}}$

• MF

  即用0随机mask特征向量的部分维度。具体来说，按照$1-p_m$的伯努利分布$\widetilde{m}_{i} \sim \mathcal{B}\left(1-p_{m}\right), \forall i$随机采样一个mask向量$\widetilde{m} \in\{0,1\}^{F}$。干扰后的节点特征$\widetilde X$表示为：

  $\widetilde{\boldsymbol{X}}=\left[x_{1} \circ \tilde{m} ; x_{2} \circ \tilde{m} ; \cdots ; x_{N} \circ \tilde{m}\right]^{\top}$

在GRACE中，作者同时使用这两种增强策略来生成新视图。生成的新视图$\mathcal{\widetilde G_1}$，$\mathcal{\widetilde G_1}$通过超参数$p_{r，1},p_{m,1}$和$p_{r，2},p_{m,2}$控制。作者通过实验发现，GRACE对这一超参的选择并不敏感，只要不过度破坏原始图信息即可，比如$p_r\leq0.8$，$p_m\leq0.8$。

2.3 理论分析

2.3.1 互信息

互信息Mutual Information（MI）是一种量化方式，计算的是一个随机变量包含另一个随机变量的信息量。

这一部分作者证明了对比目标$J$是模型输入X和两个视角下节点嵌入之间互信息的下界，即$J\leq I(X,U,V)$。

具体推导过程这里不做描述，感兴趣可以看原文。

2.3.2 三元损失

所谓三元损失，即通过三元组定义的一种损失函数：$L=\sum_{i}^{N}\left[\left\|f\left(x_{i}^{a}\right)-f\left(x_{i}^{p}\right)\right\|_{2}^{2}-\left\|f\left(x_{i}^{a}\right)-f\left(x_{i}^{n}\right)\right\|_{2}^{2}+\alpha\right]_{+}$。其目标如下图所示，即拉近锚点和正例样本间的距离，拉远锚点和负例样本间的距离：

这一部分作者证明了最小化对比目标和最大化三元损失一致：

$-\ell\left(u_{i}, v_{i}\right) \propto 4 N \tau+\sum_{j=1}^{N} \mathbb{1}_{[j \neq i]}\left[\left(\left\|u_{i}-v_{i}\right\|^{2}-\left\|u_{i}-v_{j}\right\|^{2}\right)+\left(\left\|u_{i}-v_{i}\right\|^{2}-\left\|u_{i}-u_{j}\right\|^{2}\right)\right]$

3. 实验

作者进行了三种类型实验：transductive 节点分类、大规模图上的inductive节点分类、多个图上的inductive节点分类。

3.1 实验设置

所有实验都采用DGI中的评估模式，首先按照无监督方式训练模型，然后将得到的嵌入用来训练一个逻辑回归分类器。

• Transductive learning

  使用两层GCN作为encoder：

  $\begin{aligned} \mathrm{GC}_{i}(\boldsymbol{X}, \boldsymbol{A}) &=\sigma\left(\hat{\boldsymbol{D}}^{-\frac{1}{2}} \hat{\boldsymbol{A}} \hat{\boldsymbol{D}}^{-\frac{1}{2}} \boldsymbol{X} \boldsymbol{W}_{i}\right) \\ f(\boldsymbol{X}, \boldsymbol{A}) &=\mathrm{GC}_{2}\left(\mathrm{GC}_{1}(\boldsymbol{X}, \boldsymbol{A}), \boldsymbol{A}\right) \end{aligned}$

• Inductive learning on large graph

  对于大规模数据集，作者也基本参照DGI，使用带有残差连接的三层GraphSAGE-GCN：

  $\begin{aligned} \widehat{\mathrm{MP}}_{i}(\boldsymbol{X}, \boldsymbol{A}) &=\sigma\left(\left[\hat{\boldsymbol{D}}^{-1} \hat{\boldsymbol{A}} \boldsymbol{X} ; \boldsymbol{X}\right] \boldsymbol{W}_{i}\right) \\ f(\boldsymbol{X}, \boldsymbol{A}) &=\widehat{\mathrm{MP}}_{3}\left(\widehat{\mathrm{MP}}_{2}\left(\widehat{\mathrm{MP}}_{1}(\boldsymbol{X}, \boldsymbol{A}), \boldsymbol{A}\right), \boldsymbol{A}\right) \end{aligned}$

  由于在大规模图上，GPU内存有限无法直接计算所有节点，所以这里采用GraphSAGE中subsampling方式进行计算。即首先采样一个minibatch节点，然后分别以每个节点为中心，1/2/3跳分别采样30/25/20个邻居节点。

• Inductive learning on multiple graphs

  还是和DGI中类似，堆叠三个mean-pooling层：

  $\begin{aligned} H_{1} &=\widehat{\mathrm{MP}}_{1}(\boldsymbol{X}, \boldsymbol{A}) \\ \boldsymbol{H}_{2} &=\widehat{\mathrm{MP}}_{2}\left(\boldsymbol{X} \boldsymbol{W}_{\text {skip }}+\boldsymbol{H}_{1}, \boldsymbol{A}\right) \\ f(\boldsymbol{X}, \boldsymbol{A})=\boldsymbol{H}_{3} &=\widehat{\mathrm{MP}}_{3}\left(\boldsymbol{X} \boldsymbol{W}_{\text {skip }}^{\prime}+\boldsymbol{H}_{1}+\boldsymbol{H}_{2}, \boldsymbol{A}\right) \end{aligned}$

  虽然在PPI数据集中包含多个图，但是出于计算效率考虑，作者只选取同一张图其他节点作为当前锚点的负样本。

3.2 实验结果

3.2.1 基础实验

从上表1可以看出，在所有实验设定下，和无监督方法相比，作者提出的GRACE模型都取得了最优表现。和有监督方法相比，在transductive设定下，GRACE也取得了最优表现。

3.2.2 敏感性实验

作者主要分析了模型对增强策略中$p_{m, 1}, p_{r, 1}, p_{m, 2}, p_{r, 2}$这些超参的敏感性，为了方便起见，作者设定$p_{1}=p_{r, 1}=p_{m, 1}$，$p_{2}=p_{r, 2}=p_{m, 2}$，结果如下图2所示：

可以看到只要不过度破坏原始数据结构和属性信息，模型对这些超参并不敏感。

3.2.3 消融实验

作者针对模型中两种增强策略RE和MF进行消融实验，结果如下表5所示：