GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training

摘要

目前图表示学习在许多任务上取得了很好的效果但是都是关注于具体领域的并不具有迁移性。本文借鉴预训练思想，设计了一个自监督图神经网络框架来在多个网络中捕获一般化的网络拓扑结构属性。我们设计的预训练任务是在多个网络之间判别子图实体，使用对比学习强化图神经网络来学习固有的，可迁移的结构化表示。

引言

假设：具有代表性的图结构模式是一般化的且在网络之间可迁移。
过去二十多年的工作主要关注点在发掘不同网络中潜在的一般化的结构属性。最近几年图学习的重点从结构模式挖掘转向图表示学习。将结点，边，子图等转化为低维嵌入可以保留一些重要的结构信息。但是，大多数表示学习主要是在单一图上或者一组固定数目的图中学习，表达受限且很难迁移。本质上，这些表示学习模型旨在学习每个数据集专用的网络特定结构模式。举个例子，在社交网络上使用DeepWalk学到的表示无法用于其他图中。因此，可否学习一个一般化的，可迁移的图嵌入是个待解决的问题。

本文借助对比学习的思想在多个图上学习结构化表示。基本的思想是先从输入图中采样实例，把每个实例作为单独的类别，编码并判别这些实例。在GCC中，我们将子图判别作为预训练任务，根据结点的局部结构区分他们。对于每个结点从他的多跳ego-network中采样子图。GCC的目的是区分从特定结点采样的子图和从其他结点采样的子图。由于GCC并不要求结点和子图来自于同一张图，因此图编码器被迫要从不同的输入图中捕获一般化的模式。

相关工作

结点相似性是用来衡量结点之间相似程度的指标，常见的方法有三类：
1）Neighborhood similarity
假设直接相邻的结点应该相似。早期的邻居相似性度量方法包括Jaccard similarity，RWR similarity和SimRank等。大多数图嵌入方法如DeepWalk，LINE，node2vec都是基于邻居相似度假设的。

2）Structural similarity
不同于邻居相似度通过度量连接关系来计算，structural similarity不需要假设结点得连接，而是认为结点具有相似的局部结构则结构相似度应更相似。建模结构相似度的工作主要分为两类，一个是基于领域知识如结点的度，结构多样性 k-core,motif等。基于该想法的工作主要包括struct2vec，RoIX等。其二是使用谱图理论来建模结构相似性。

3）Attribute similarity
现实世界的图数据包含许多属性信息如引用网络中的文本，分子图中的化学特征。常见的图神经网络如GCN，GAT，GraphSAEG等使用属性信息作为额外信息学习表示可以进一步用于衡量结点相似性。

模型

在给定一组来自多个领域的图，我们希望通过预训练GNN模型捕获跨网络的结构模式。比如，在Fackbook，IMDB，DBLP数据图上预训练一个GNN模型，然后应用于US－Airport网络中做结点分类。GNN预训练目标是学习一个函数可以把结点映射到低维的特征向量中。这个函数应该包含两个属性，一是保留结构相似性，网络局部拓扑相似的结点在向量空间中应该靠近；二是可迁移性，对于预训练中未见过的结点或图也适用。不同于常见的图神经网络学习，本文的重点在于不考虑结点属性和结点标签条件下学习结构化的表示。通过预训练一个结构化表示模型，然后应用到未见过的图上。

在给定一组图后，我们需要预训练一个一般化的图神经网络编码器捕获这些图中的结构化模式。本文通过把子图判别作为预训练任务，使用InfoNCE作为目标函数来学习。预训练任务把子图实例作为单独的类别，学习子图之间的差异性，这样输出的表示可以捕获子图之间的相似性。从查表的角度分析即给定一个查询向量ｑ和一个包含Ｋ＋１个编码的关键字的字典，对比学习是要找到一个与ｑ匹配的键值k+.因此可以将InfoNCE改写为

目前有三个问题尚待解决
1)如何在图中定义子图?
2)如何在图之间定义相似度距离?
3)适合的图编码器fq,fk是什么?

Design(subgraph) instances in graphs
对比学习成功的关键在于数据实体的定义.在CV和NLP领域中,实体一般是图像和句子,但在图数据中并没有直接定义好的实体.由于我们的预训练任务只关注于结构化表示,因此我们通过使用子图来作为对比实体.本文中子图定义为r-ego network即对于每个结点，选择所有到它距离不大于r的节点作为子图。

Define (dis)similar instances
在GCC中，我们将对同一个r-ego 网络的随机增强视作相似的实例并把这种增强方式称为图采样。假设要增强结点v的r-ego network，图采样主要包含三个步骤
1）带重启的随机游走
从中心结点v开始按照一定权重在邻居结点中随机游走。并且，在每一步游走时，都有一定的概率返回到初始结点。
2）子图归纳
随机游走得到了一组结点v的邻居结点记为S。用S中生成的子图G’视作是一个r-ego network的增强。
3）匿名化
对采样的子图中的结点按照任意顺序重新标注。这样做是隐藏结点索引，避免通过索引作为判别条件。

Define graph encoders
任何一种图神经网络都可以作为GCC的编码器，但是传统图神经网络要求结点特征或者属性信息作为输入，而本文只关注结构表示。为解决这个问题，本文采用采样子图的图结构来作为初始结点的特征。即每个子图的位置编码定义为归一化的图拉普拉斯的最大的特征向量。

如图为GCC预训练的一个例子，我们把字典的大小设置为3。首先随机从二阶的ego-network中生成两个子图xq和xk0，同时另外两个子图xk1和xk2则是从噪声分布中生成的。然后使用两个编码器fq和fk得到低维嵌入q和{k1, k2, k3}，最后通过对比loss，使xq和xk0接近，与其他更远。

实验