原文链接：https://dl.acm.org/doi/10.1145/3394486.3403168

会议：KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining （CCF A类）

代码：https://github.com/THUDM/GCC

年度：2020/08/20

学习已成为解决实际问题的强大技术

节点分类、相似度搜索、图分类等各种下游图学习任务受益于其最近的发展

然而，现有的图表示学习技术专注于领域特定的问题，并为每个图数据集训练一个专用模型，这通常不可转移到域外数据

Hypothesis

假设：具有代表性的图形结构模式具有通用性和跨网络转移性

在过去的20年里，网络科学研究的重点是发现和抽象不同网络的一般结构特征

• 例如，Barabasi和Albert指出万维网、社交网络、生物网络等多种网络都具有无标度特征，即其度分布遵循幂律[1]
• Leskovec等人。[28]发现许多实图符合致密收缩定律。其他常见的网络模式包括小世界[57]motif分布[31]、社区组织[34]和核心-外围结构[6]在概念层面验证了我们的假设

然而，在过去的几年里，随着深度学习的近期进展[4、30]，图形学习的范式已经从结构化模式转变为图形学习

具体来说

• 图表示学习将图表的顶点、边缘或子图转换为低维嵌入，以保留图表的重要结构信息
• 然后，从输入图中学到的嵌入可以输入到同一图中下游任务的标准机器学习模型中。

然而，到目前为止，大多数图表的学习工作都集中在单个图表或一组固定图表的学习上，非常有限的工作可以转移到域外的数据和任务上

本质上，这些表示学习模型旨在学习特定的网络结构模式，用于每个数据集

例如

• [39]在Facebook学习社交图片DeepWalk嵌入模型不能应用于其他图片

鉴于(1)图表中学习的局限性和(2)常见结构模式中发现的现有技术

自然问题出现了：我们能从网络中学习可转移的代表性图嵌入吗？

在自然语言处理[10]、计算机视觉[17]等领域也提出和追求了类似的问题

到目前为止，最强大的解决方案是在自我监督的设置下，从大型数据集预训练中表示学习模型

预训练的理念是利用预训练模型作为良好的初始化，以便在看不见的数据集中微调（不同）任务

在过去的几年里，网络/图中顶点相似性的量化已经得到了广泛的研究

顶点相似性的目标是回答[26]之类的问题

如“这两个顶点有多相似?”或“其他哪个顶点与这些顶点最相似?”相似的定义在不同的情况下可能是不同的

我们简要回顾了以下三种类型的顶点相似性

Neighborhood similarity

邻域相似性的基本假设，即邻近性，是紧密连接的顶点应该被认为是相似的

• 早期的邻域相似性度量包括Jaccard相似性(计算共同邻域)、RWR相似性[36]和SimRank[21]等
• 最近开发的网络嵌入算法，如LINE [47]， DeepWalk [39]， node2vec[14]，也遵循邻域相似性假设

Structural similarity

与邻域相似度通过连通性来衡量相似度不同，结构相似度甚至不假设顶点是连通的

结构相似的基本假设是具有相似局部结构的顶点应该被认为是相似的

关于结构相似性建模的研究有两种方向

• 第一行定义了基于领域知识的代表性模式。例如顶点度、结构多样性[51]、结构孔[7]、k-core[2]、motif[5,32]等。因此，这种类型的模型，如Struc2vec[43]和RolX[18]，通常都包含明确的功能
• 第二项研究利用谱图理论来模拟结构相似性。最近的一个例子是GraphWave[12]

在这项工作中，我们专注于结构相似性

与上述两种类型不同的是，我们采用对比学习和图神经网络从数据中学习结构相似性

Attribute similarity

现实世界的图形数据往往具有丰富的属性，如引文网络中的文本、社会网络中的人口统计信息、分子图中的化学特征等

最近的图神经网络模型，如GCN [25]， GAT [53]， GraphSAGE[16,62]和MPNN[13]，利用附加属性作为边信息或监督信号来学习进一步用于度量顶点相似性的表示

对比学习是一种从数据中获取相似性的自然选择

• 在自然语言处理中，Word2vec[30]模型利用拟合词和负采样来学习词嵌入
• 在计算机视觉中，大量的工作[15,17,49,58]通过最小化同一图像的两个视图之间的距离来学习自我监督图像表示

在这项工作中，我们采用了Oord等人[35]的InfoNCE损失和Wu等人[58]的实例识别任务

Skip-gram based model

早期对预训练图表示的尝试是受Word2vec[30]启发的基于跳跃图的网络嵌入模型

如LINE [47]， DeepWalk [39]， node2vec[14]和metapath2vec[11]

它们大多数遵循邻域相似性假设

上述方法学习到的表示与用于训练模型的图捆绑在一起，不能处理样本外问题

我们的图对比编码(GCC)在两个方面不同于这些方法

• 首先，GCC关注结构相似性，结构相似性与邻域相似性正交
• 其次，GCC可以跨图形转移，甚至转移到训练前从未见过的图形

Pre-training graph neural networks

最近有几项研究将语言训练前的[10]引入了训练前的图神经网络(GNN)

• 例如，Hu等。[19]在标记图上预训练GNN，特别是分子图，其中每个顶点(原子)有一个原子类型(如C、N、O)，每个边(化学键)有一个键类型(如单键和双键)。训练前的任务是恢复隐藏分子图中的原子类型和化学键类型
• 另一项相关的工作是Hu等人[20]的，它定义了几个图学习任务来预训练GCN[25]

我们的GCC框架在两个方面与上述方法有所不同

• 首先，GCC适用于一般的未标记图，特别是社会和信息网络
• 其次，GCC不涉及显式的特征化和预定义的图学习任务

在本节中，我们形式化了图神经网络(GNN)的预训练问题

为了解决这个问题，我们提出了图形对比编码(GCC)框架

图2展示了GCC的训练前和微调阶段的概述

从概念上讲，给定一组来自不同领域的图，我们的目标是预先训练一个GNN模型，以一种自我监督的方式捕获这些图的结构模式

该模型应该能够受益于不同数据集上的下游任务

潜在的假设是，在不同的图中存在共同的和可转移的结构模式

如motifs,，这在网络科学文献[28,32]中很明显

一个示例场景是，我们在带有自我监督的Facebook、IMDB和DBLP图上预训练GNN模型，并将其应用于US-Airport网络进行节点分类，如图2所示

形式上，GNN预训练问题是学习一个函数$f$，它将一个顶点映射到一个低维特征向量，使$f$具有以下两个性质:

• 首先是结构相似性，它将具有相似局部网络拓扑的顶点在向量空间中相互靠近;
• 二是可转移性，可兼容预训练时不可见的顶点和图

因此，嵌入函数$f$可用于各种图学习任务，如社会角色预测、节点分类、图分类等

值得注意的是，这项工作的重点是在没有节点属性和节点标签的结构表示学习，这使得它不同于图神经网络研究中常见的问题设置

此外，我们的目标是预训练一个结构表示模型并将其应用于不可见的图，这与传统的网络嵌入[14,39 - 41,47]和最近的尝试不同（将带属性的图作为输入并将其应用于特定域[19]的预训练图神经网络）

给定一组图，我们的目标是预先训练一个通用图神经网络编码器，以捕获这些图背后的结构模式

为了实现这一点，我们需要为图结构数据设计适当的自我监督任务和学习目标

受最近CV[17,58]和NLP[9,30]成功的对比学习的启发，我们建议使用子图实例区分作为我们的训练前任务和InfoNCE[35]作为我们的学习目标

训练前任务将每个子图实例视为自己的一个不同类，并学习区分这些实例

• 其承诺是，它可以输出捕获这些子图实例之间相似性的表示[17,58]。
• 从字典查找的角度来看，给定一个 编码查询$q$ 和一个包含$K+1$个编码键 { k 0 ， ⋅ ⋅ ⋅ ， k K } \{k_0，···，k_K\} { k0​，⋅⋅⋅，kK​}的字典，对比学习查找$q$在字典中匹配的单个键(用$k_{+}$表示)

在这项工作中，我们采用InfoNCE，这样:

其中

• $\tau$为 temperature hyper-parameter
• $f_q$和$f_k$是两个图神经网络，将查询实例$x^q$和每个密钥实例$x^k$ 编码为$d$维表示，用$q=f_q(x^q)$和$k=f_k(x^k)$表示

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

• Q1：如何在图中定义子图实例?
• Q2：如何在图中或图中定义（不）相似实例对，例如，对于查询$x^q$，哪个键$x^k$是匹配的?
• Q3：什么是合适的图形编码器$f_q$和$f_k$ ?

值得注意的是，在我们的问题设置中，并没有假设$x^q$和$x^k$来自同一个图

接下来，我们通过相应的回答上述问题，提出GCC训练前框架的设计策略

Q1: Design (subgraph) instances in graphs.

对比学习框架的成功很大程度上依赖于数据实例的定义

CV和NLP任务可以直接将实例定义为图像或句子

但是，这种思想不能直接扩展到图数据，因为图中的实例没有明确的定义

此外，我们训练前的重点是纯粹的结构化表示，没有额外的输入特性/属性，这使得自然选择单个顶点作为实例是不可行的

因为它不适用于区分两个顶点

为了解决这个问题，我们建议使用子图作为对比实例，将每个单个顶点扩展到其局部结构

具体来说，对于某个顶点$v$，我们定义一个实例为它的$r-ego$网络:

Definition 3.1. A r-ego network

设$G=(V,E)$是一个图

• 其中$V$表示顶点的集合
• $E\subseteq V\times V$表示边的集合

对于一个顶点$v$，其 $r-neighbors$定义为 S v = { u : d ( u , v ) ≤ r } S_v = \{u:d(u, v)≤r\} Sv​={ u:d(u,v)≤r}

• 其中$d(u,v)$是图$G$中$u$到$v$之间的最短路径距离
• 顶点$v$的$r-ego$网络，用$G_v$表示，是由$S_v$诱导的子图

图3的左面板显示了 2-ego 网络的两个例子

注意：$r-ego$网络是$S_v$诱导的子图

GCC将每个$r-ego$网络视为自己的一个不同类别，并鼓励模型区分相似实例和不同实例

Q2: Define (dis)similar instances

接下来，我们将介绍如何定义(不)相似实例

• 一对是相似实例
• 一对是不相似实例

在计算机视觉[17]中，同一幅图像的两个随机数据增强(例如，随机裁剪、随机调整大小、随机颜色抖动、随机翻转等)被视为一个类似的实例对

在GCC中，我们将同一个$r-ego$网络的两个随机数据增强作为一个相似的实例对，并将数据增强定义为图采样[27]

图采样是一种从原始图中获得代表性子图样本的技术

假设我们想要扩充顶点$v$的$r-ego$网络($G_v$)， GCC的图采样遵循三个步骤:

• 重启随机漫步(RWR)[50]
• 子图归纳
• 匿名化[22,29]

(1) Random walk with restart.

我们从ego顶点$v$开始在$G$上进行随机游走，游走以与边权值成比例的概率迭代到它的邻域

此外，在每一步中，步数返回起始顶点$v$的概率为正

每一次游走，会有一定的概率会到起点

(2) Subgraph induction

带重启的随机遍历收集了$v$周围的一个顶点子集，用${\tilde{S}}_v$表示

由${\tilde{S}}_v$诱导的子图${\tilde{G}}_v$ 被认为是$r-ego$网络$G_v$的增强版

这一步也被称为诱导子图随机游走抽样(ISRW)

(3) Anonymization

我们匿名化采样图${\tilde{G}}_v$，以任意顺序将其顶点重新标记为 { 1 , 2 ， ⋅ ⋅ ⋅ ， ∣ S ~ v ∣ } \{1,2，···，|\tilde S_v |\} { 1,2，⋅⋅⋅，∣S~v​∣}

我们重复上述过程两次，以创建两个数据扩展

它们形成一个类似的实例对$(x^q,$