https://arxiv.org/pdf/2006.09963

https://github.com/THUDM/GCC

GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training，2020，KDD

总结：简单来说，作者提出了一种subgraph-subgraph level图对比学习框架GCC，对GNNs进行预训练后将模型迁移到其他数据集。框架本身就是非常常规的对比学习框架，目标函数也是常规的对比损失，没什么特别之处。值得关注的一点是作者如何生成定义、增强子图的。作者的实验比较丰富，但是实验结果并没有什么亮眼之处。个人感觉，这篇能发顶会主要原因：一是论文写的比较早，应该是第一篇用对比学习来搞图预训练任务的，开创意义比较大；二是作者比较会写论文，文章立意比较高。

1. 简介

1.1 摘要

Graph representation learning has emerged as a powerful technique for addressing real-world problems. Various downstream graph learning tasks have benefited from its recent developments, such as node classification, similarity search, and graph classification. However, prior arts on graph representation learning focus on domain specific problems and train a dedicated model for each graph dataset, which is usually non-transferable to out-of-domain data. Inspired by the recent advances in pre-training from natural language processing and computer vision, we design Graph Contrastive Coding (GCC)1—a self-supervised graph neural network pre-training framework—to capture the universal network topological properties across multiple networks. We design GCC’s pre-training task as subgraph instance discrimination in and across networks and leverage contrastive learning to empower graph neural networks to learn the intrinsic and transferable structural representations. We conduct extensive experiments on three graph learning tasks and ten graph datasets. The results show that GCC pre-trained on a collection of diverse datasets can achieve competitive or better performance to its task-specific and trained-from-scratch counter-parts. This suggests that the pre-training and fine-tuning paradigm presents great potential for graph representation learning.

图表示学习逐渐成为解决现实问题的一种强大技术，许多下游任务都从它的发展中收益，比如节点分类、相似检索、图分类。但是，现有的图表示学习方法大多关注领域相关的特定问题，为每个数据集单独训练一个模型，这个模型都不能迁移到其他领域任务中。受NLP和CV中预训练最新进展的启发，我们设计了Graph Contrastive Coding（GCC）——一种自监督图神经网络预训练架构，可以跨网络捕捉通用的拓扑信息。我们将网络内和跨网络子图判别作为GCC的预训练任务，并通过对比学习使图神经网络可以学习内在的、可迁移的结构表示。我们在10个数据集、3个图学习任务上进行了大量实验，结果表明在不同数据集上对GCC进行预训练可以让模型取得很好的表现。这表示预训练和微调模式在图表示学习领域具有很大潜力。

1.2 本文工作

背景： 过去20年里，网络科学的研究主要集中于在不同网络间发现、提取通用的结构属性。但是在最近几年，由于深度学习取得了很大进展，图学习模式逐渐从发现structural pattern转向图表示学习。而大多数图表示学习方法都是针对于单一任务的，不能迁移到out-of-domain数据和任务。因为本质上图表示学习模型旨在学习一个专用于某个数据集的network-specific structural patterns。

动机： 鉴于（1）现有很多图表示学习方法存在局限性（2）对于common structural pattern discovery在过去已经进行了很多研究，证明了其可行性，作者在想“能不能从网络中学习一个通用的、可迁移的图嵌入？”

本文工作： 在CV和NLP领域也存在类似前文提到的问题，目前为止，最好的一种方法就是在大型数据集上以自监督方式对模型进行预训练，然后在unseen数据集上进行微调。受其启发，本文作者提出了Graph Contrastive Coding（GCC），利用对比学习思想实现跨网络学习结构表示。作者通过大量实验证明了GCC的性能和可迁移性。

2 方法

上图2展示了GCC的整体架构，首先在三个数据集上进行预训练，然后迁移到其他数据集上进行微调。下面首先看一下作者是GNN预训练问题是如何定义的。

2.1 问题定义

对于预训练问题，从概念上来说，给定来自不同domain的图集合，我们希望以自监督方式预训练一个GNN模型，可以在这些不同图之间捕捉结构模式。预训练好的模型可以用于其他不同数据集上的下有任务。

注：这里有一个潜在假设就是，不同图之间确确实实是存在着这样一个通用的、可迁移的结构模式（比如motifs）。

说的正式一点，GNN预训练问题就是学习一个函数$f$，将节点映射成一个低维特征向量，这个$f$具有以下两个性质：

• structural similarity： 对于两个具有相似局部拓扑结构的节点，映射出来的特征向量要相似（就是这几年很火的图表示学习的目标）
• transferability： 能够适用于unseen数据集（即要求模型学习到的时通用的结构模式，这就是传统common structural pattern discovery方法的目标）

总结来说，其实就是把图表示学习问题和传统的结构模式发现问题结合到一起。

因为GCC是个预训练框架，因此下面分预训练和微调两部分介绍该框架。

2.2 预训练

受对比学习在CV和NLP领域成功应用的启发，作者将“subgraph instance discrimination”作为预训练任务（即subgraph-subgraph level 对比），InfoNCE作为学习目标。

• 预训练任务： 简单点说就是进行subgraph-subgraph level 对比。让每个子图自成一类，自己就是该类别的一个实例。模型需要做的就是输出可以捕获不同子图实例间相似性的表示向量。

• 学习目标： 这里作者说的比较复杂，其实就是常规的对比学习损失函数。作者采用InfoNCE作为损失函数：

  $\mathcal{L}=-\log \frac{\exp \left(\boldsymbol{q}^{\top} \boldsymbol{k}_{+} / \tau\right)}{\sum_{i=0}^{K} \exp \left(\boldsymbol{q}^{\top} k_{i} / \tau\right)}$

  其中$q$就是锚点，$k_+$就是正样本，$\{k_0,...,k_1\}$表示所有正负样本集合。

这篇文章作者扯得比较复杂，其实GCC可以看作一种subgraph-subgraph level的对比学习方法。既然是subgraph-subgraph层对比，那首先就要设计一个子图采样方法，得到输入样本集合。然后要考虑的就是增强策略，即如何为子图生成正负样本。最后当然还需要选取一种GNNs作为图编码器，学习图嵌入。

因此为了构建GCC的每个组件，我们需要解决三个问题：

1. 如何定义subgraph？

   本文作者采用r-ego network方式生成子图，其定义如下：

   $G=(V,E)$表示一张图，$V$表示节点集合，$E\subseteq V\times V$表示边集合。对于顶点$v$，它的r-neighbors定义为$S_v=\{u:d(u,v)\leq r\}$，其中$d(u,v)$表示u和v之间的最短距离。（这个应该就是等价于r-hop邻居构成的子图）

   下图3最左边，小圆圈里面圈出来的就是两个子图。

2. 如何生成正负样本（即增强策略）？

   在CV中，将同一张图片经两次随机增强（旋转或剪切）后得到的两个增强样本看作similar instance pair（即正样本对）。同样地，在GCC中作者也将同一个子图经过两次 随机增强（本文采用图采样） 后得到的两个增强样本看作正样本对。GCC的图采样包含三个步骤：

   1. RWR，从节点$v$看是执行带有restart的随机游走
   2. 子图诱导，对于节点$v$，第一步RWR得到的子图表示为$\widetilde S_v$，从$\widetilde S$诱导得到的子图表示为$\widetilde G_v$。
   3. Anonymization，每个子图$\widetilde G_v$自成一类，按顺序分配标签$\{1,2,...,|\widetilde S_v|\}$。（这一步介绍有点多余，对比学习天生的设置就是这样，加上这一句可以更好理解前面的对比损失）

   重复执行前面3个步骤，对于每个节点我们都能得到两个增强子图。下图3中间四张图表示的就是增强后得到的子图。

3. 对于$q$和$k$，哪种graph encoder最合适？

   如下图3所示，给定子图$x^q$和$x^k$，GCC使用两个编码器$f_q$和$f_k$分别对输入子图进行编码。从理论上来说我们可以采用任何一种GNNs作为编码器，GCC模型对此并不敏感。在实际应用中，作者采用GIN作为图编码器。

   另外需要注意的是，如前文所属，作者关注的是模型在预训练过程中学习通用的、可迁移的结构表示。但是现有的大部分GNN模型都需要节点特征/属性作为输入。为了弥补这一差异，作者利用采样子图的图结构来初始化顶点特征。具体来说，作者定义了“generalized positional embedding”：

   $A$和$D$分别表示子图的邻接矩阵和度矩阵，对正则化的图拉普拉斯矩阵进行特征分解：$I-D^{-1 / 2} A D^{-1 / 2}=U \Lambda U^{\top}$，$U$最上面的特征向量即为generalized positional embedding。

上图3展示了GCC预训练的大致流程。对于训练方式，作者基本是参照何凯明CV里面对比学习模型，在实验中采用了end-to-end和MOCO两种训练方式。

2.3 微调

• 下游任务

  图学习下游任务大致可以分为两类：node-level和graph-level，目标分别为预测节点或图的标签。对于graph-level任务，直接使用GCC对输入图进行编码，得到图表示即可。对于node-level任务，可以使用GCC对节点的r-ego网络进行编码。

• 微调策略

  GCC提供了两种微调策略：

  • Freezing： 微调时冻结GCC中图编码器参数，重新训练一个分类器
  • Full fine-tuning： 对整个模型参数进行微调，包括编码器和分类器

3. 实验

3.1 基础实验

节点分类： 为了评估GCC，作者将节点的r-ego子图输入到GCC中，然后将得到的节点表示喂给输出层，预测节点标签。实验结果如下表2所示：

图分类： 将原始图输入GCC，得到graph-level表示后，喂给分类器预测图标签。实验结果如下表3所示：

Top-k Similarity Search： 采用KDD、ICDM等学术会议的的co-author数据集进行实验。top-k相似度查询的问题定义为：给定两个图$G_1$和$G_2$，从$G_1$中找到和$G_2$中节点$u$最相似的节点$v$。因为similarity search是无监督问题，因此不需要对GCC进行微调。具体来说，作者利用RWR，分别以$u$和$v$为中心节点进行子图采样，然后利用GCC对接点进行编码，最后计算$u$和$v$之间的相似度。实验结果如下表4所示：

3.2 消融实验

预训练的有效性： 如前文表2、表3所示，为了验证GCC的有效性来自于GIN的强大编码能力还是预训练，作者设计了GCC(rand)模型。具体来说，GCC(rand)将其GIN编码器随机初始化一个参数后进行fully fine-tune。可以看到在大部分情况下，GCC(MoCo)的想能要优于GCC(rand)，这证明了预训练是有效的，可以为GIN提供一个号的初始化参数。

对比损失机制： 在CV邻域，MOCO模型比E2E模型性能要好很多，并且负样本越多（即K值越大）性能越好。但是本文发现，在图领域，K值的大小对于模型性能影响并不大，例如$MoCo(K=16384)$和$MoCo(K=1024)$相比性能增加不超过1.0。另外，和E2E相比，MoCo方式训练模型速度更快，如下图6所示：

动量更新中动量值： 所谓动量更新即$\theta_k\leftarrow m\theta_k+(1-m)\theta_q$。从下表5可以看出，在US-Airport数据集中动量值取$m=0.999$模型最好，这和CV中MOCO模型是一致的。但是在COLLAB数据集中，似乎m越大模型性能越好。

预训练数据集： 从下图5可以看出，用于预训练的数据集越多，在unseen数据集上的表现越好。