GCC: Graph Contrastive Coding for Graph Neural NetworkPre-Training

Abstract

图表示学习已经成为解决现实问题的强大技术。各种下游图学习任务受益于其最近的发展，如节点分类、相似度搜索和图分类。然而，现有的图表示学习技术专注于领域特定的问题，并为每个图数据集训练一个专用模型，这通常不可转移到域外数据。受自然语言处理和计算机视觉在预训练方面的最新进展的启发，我们设计了图对比编码(GCC)1 -一个自我监督的图神经网络预训练框架，以捕获跨多个网络的通用网络拓扑属性。我们将GCC的预训练任务设计为网络中的子图实例判别，并利用对比学习使图神经网络能够学习内在的和可转移的结构表征。我们在三个图学习任务和十个图数据集上进行了广泛的实验。结果表明，GCC在不同的数据集上的预训练可以达到与任务特定的和训练有素的同行具有更大的竞争力或更好的性能。这表明预训练和微调范式为图表示学习提供了巨大的潜力。

INTRODUCTION

本文我们提出了Graph Contrastive Coding（GCC）框架来学习跨图形的结构表示。相反，我们利用对比学习的思想设计了图预训练任务作为实例识别。它的基本思想是从输入图中抽取instance，将它们视为自己的一个不同类，并学习对这些实例进行编码和区分。GCC需要回答三个问题，以便它能够学习 the transferable structural patterns：(1) what are the instances? (2) what are the discrimination rules? (3) how to encode the instances?

本文的预训练任务：子图实例判别（subgraph instance discrimination）。对于每个顶点，将其 r-ego networks 作为采样子图实例，GCC 的目的是区分从特定顶点采样的子图和从其他顶点采样的子图。

主要贡献：

• 我们将 跨多个图的 GNN 预训练 问题公式化，并确定其存在主要挑战（难点）。
• 我们将预训练任务设计为Graph representation learning ，以从多个输入图中捕获通用和可转移的结构特征。
• 我们提出GCC框架来学习 structural graph representations，该框架是利用 contrastive learning 来指导训练。
• 我们进行了大量实验，以证明对于跨领域的任务，GCC可以提供与 特定任务领域的模型 近似或更高的性能。
   

RELATED WORK

主要包括三部分：vertex similarity, contrastive learning ,  graph pre-training

Vertex Similarity

 包括 Neighborhood similarity,Structural similarity，Attribute similarity

Graph Pre-Training

---

• Skip-gram based model

一些受word2vec启发而产生的图embedding方法，例如LINE、DeepWalk、node2vec、          metapath2vec，大多基于节点的相似特征，并且不能使用到样本以外的问题。而本文提出的GCC模型是基于结构相似性的，并且能在训练之外的图上进行迁移。

• Pre-training graph neural networks

在这篇文章之前，也有一些针对图的预训练文章，这些文章要么使用了图上节点或者边的属性，要么定义了训练任务。本文的模型：1）不使用图标签；2）没有需要学习的特征任务。

GRAPH CONTRASTIVE CODING (GCC)

Figure 2 展示了GCC的 pre-training 和 fine-tuning 阶段的概述。

The GNN Pre-Training Problem 

 给定一组来自不同领域的图，我们的目标是预训练GNN模型，以self-supervised的方式捕获这些图中的结构特征。该模型应该能够使不同数据集上的下游任务受益。基本假设是，不同的graph之间存在着 common and transferable structural patterns,例如主题，这在网络科学文献中是显而易见的。一个易于理解的场景，我们在Facebook、IMDB和DBLP图上预先训练一个GNN模型，并进行self-supervised学习，然后将其应用于 US-Airport network图的节点分类任务，如图2所示。

形式上，GNN预训练问题是学习将顶点映射到低维特征向量的函数f，且f具有以下两个特性：

• 首先，structural similarity，具有相似拓扑结构的节点在向量空间中映射相近。
• 其次，transferability，它兼容预训练期间不可见的顶点和图形。

GCC Pre-Training

给定一组图，我们的目标是预先训练一个通用图神经网络编码器，以捕获这些图背后的结构模式。为了实现这一点，我们需要为图结构数据设计适当的自我监督任务和学习目标。

我们建议用子图实例判别作为预训练任务，用InfoNCE[35]作为学习目标。预训练任务将每个子图实例视为自己的一个不同类，并学习区分这些实例。其承诺是，它可以输出捕获这些子图实例之间相似性的表示。

从字典查找的角度来看，给定一个 query q 和一个包含 K+1 个 keys {k,⋯,k} 的字典，对比学习查找 q 在字典中匹配的键  k+ 。本文采用了 InfoNCE ：

 其中，τ 为温度超参数。fq 和 f 是两个 GNN encoder ，将 query x 和 keys x 编码为 d 维表示，用 q=fq(xq)和 k=fk(xk)表示。

要在GCC中实例化每个组件，我们需要回答以下三个问题:

• Q1: How to define subgraph instances in graphs?
• Q2: How to define (dis) similar instance pairs in and across graphs, i.e., for a query Xq, which key Xk is the matched one?
• Q3: What are the proper graph encoders fq and fk ?

Q1: Design (subgraph) instances in graphs.

图中的实例没有明确的定义。此外，我们预训练的重点是纯粹的结构化表示，没有额外的输入特性/属性。这使得自然选择单个顶点作为实例是不可行的，因为它不适用于区分两个顶点。

为了解决这个问题，我们建议使用子图作为对比实例，将每个单个顶点扩展到其局部结构。具体来说，对于某个顶点v，我们定义一个实例为它的r-ego 网络:

Definition 3.1. A r-ego network. 对于一个顶点v，其r-邻居定义为Sv = {u: d(u,v)≤r}，其中d(u,v)是图g中u到v之间的最短路径距离，顶点v的r-ego网络，记为Gv，是由Sv诱导的子图。

 图3的左边显示了2-ego网络的两个例子。GCC将每个r-ego网络视为自己的一个不同类别，并鼓励模型区分相似实例和不同实例。

Q2: Define (dis)similar instances.

在GCC中，我们将同一个r-ego网络的两个随机数据增广作为一个相似的实例对，并将数据增广定义为图采样[27]。图抽样是一种从原始图中获得代表性子图样本的技术。假设我们想要扩充顶点v的r-ego网络(Gv)， GCC的图采样遵循三个步骤:重启随机漫步(RWR)[50]、子图归纳和匿名化

• Random walk with restart. 我们从自我顶点v开始在G上进行随机游走，游走以与边权值成比例的概率迭代地移动到它的邻域。此外，在每一步中，步数返回起始顶点v的概率为正。
• Subgraph induction. 带重启的随机漫步收集了v周围的一个顶点子集，用eSv表示。由eSv诱导的子图eGv被认为是自我网络Gv的扩充版。这一步也被称为诱导子图随机游走抽样(ISRW)。
• Anonymization. 我们将采样的图eGv匿名化，方法是将其顶点重新标记为{1,2，···，|eSv |}，任意顺序

我们重复上述过程两次，以创建两个数据扩展，它们形成一个类似的实例对(xq, xk+)。如果两个子图从不同的r-ego网络扩增而来，我们将它们视为具有k不等于k+的不同实例对(xq, xk)。值得注意的是，上述所有图操作—重启随机漫步、子图归纳和匿名化—都可以在DGL包中使用.

Q3: Define graph encoders.

给定两个采样子图xq和xk, GCC分别通过两个图神经网络编码器fq和fk对其进行编码。从技术上讲，这里可以使用任何图形神经网络[4]作为编码器，并且GCC模型对不同的选择不敏感。在实际应用中，我们采用了最新的图神经网络模型——图同构网络(GIN)[59]作为我们的图编码器。回想一下，我们在训练前关注的是结构表示，而大多数GNN模型需要顶点特征/属性作为输入。为了弥补这一差距，我们建议利用每个采样子图的图结构来初始化顶点特征。具体地，我们定义广义位置嵌入如下:

Definition 3.2. Generalized positional embedding

 

以上事实表明，在序列模型中的位置嵌入可以看作是路径图的拉普拉斯特征向量。这激发了我们将位置嵌入从路径图推广到任意图。使用标准化图拉普拉斯图而非非标准化图的原因是路径图是一个正则图（即常度），而现实世界的图通常是不规则的，有倾斜的度分布。除了广义位置嵌入外，我们还添加了顶点度[59]的独热编码和自我顶点的二进制指标作为顶点特征。在由图编码器编码后，最终的 dd 维输出向量然后用它们的 L2-Norm 进行归一化。

A running example 

我们在图3中展示了一个GCC预训练的运行示例。为了简单起见，我们将字典大小设置为3。GCC首先从图3左侧的一个2-ego网络中随机增加两个子图xq和xk0。同时，另两个子图xk1和xk2是由噪声分布生成的——在本例中，它们是由图3左侧面板上的另一个2-ego网络随机扩展而来的。然后两个图形编码器fq和fk将查询和三个键映射到低维向量q和{k0, k1, k2}。最后，公式1中的对比损失促使模型识别(xq, xk0)为相似的实例对，并将它们与不同的实例(即{xk1, xk2})区分开来。

GCC Fine-Tuning

图学习中的下游任务通常可分为图级和节点级两类，其目标分别是预测图级或节点的标签。对于图级任务，输入图本身可以由 GCC 进行编码，以实现表示。对于节点级的任务，节点表示可以通过编码其 r-ego 网络(或从其 r-ego 网络增强的子图)来定义。

Freezing vs. full fine-tuning

　　GCC为下游任务提供了两种微调策略——freezing mode 和 fine-tuning mode。

• 在 freezing mode 下，冻结预先训练的图编码器 fqfq 的参数，并将其作为静态特征提取器，然后在提取的特征之上训练针对特定下游任务的分类器。
• 在 fine-tuning mode 下，将用预先训练好的参数初始化的图编码器 fqfq 与分类器一起对下游任务进行端到端训练。

GCC as a local algorithm

　　GCC作为一种图算法，属于局部算法类别，由于GCC通过基于随机游走（大规模）网络的图采样方法来探索局部结构，因此GCC只涉及对输入（大规模）网络的局部探索。这种特性使GCC能够扩展到大规模的图形学习任务，并对分布式计算设置非常友好。