论文链接：https://arxiv.org/pdf/2006.15437.pdf
代码链接：https://github.com/acbull/GPT-GNN
论文来源：KDD 2020
参考文档：https://blog.****.net/c9yv2cf9i06k2a9e/article/details/108231322

1、简介

本文研究如何利用图生成作为自监督任务来预训练 GNN。我们将图的生成概率分解成两个模块：1）节点特征生成；2）图结构生成。通过对这两个模块建模，GPT-GNN 可以捕捉图任务里特征与结构之间的关联，从而不需要很多的标注数据就可达到很高的泛化性能。

2、背景

机器学习的成功很大程度上取决于数据。但是，高质量的标记数据通常很昂贵且难以获得，尤其是对于希望训练参数较多的模型。而相对应的，我们却可以很容易地获取大量的无标记数据，其数量可以是标记数据的数千倍。

例如，在社交网络上进行异常检测时，恶意帐户的标注需要依赖于专家知识，数量较小，而整个网络的规模却可以达到十亿规模。

为了解决标注数据较少，尽可能利用其无标注数据，一个常规的做法是自监督的预训练（self-supervised pre-training）。其目标是设计合理的自监督任务，从而使模型能从无标注数据里学得数据的信息，作为初始化迁移到下游任务中。由于目标任务中很多的知识已经在预训练中学到，因此通过预训练，我们只需要非常少量的标注数据，就能得到较好的泛化性能。

在 NLP 领域，BERT 及其变种的取得了巨大的成功，证明了语言模型作为一个自监督任务，可以帮助训练非常深的 Transformer 模型，以捕捉语言的底层知识，如语法、句法、词义等。

同样，在 CV 领域，最近的工作如 SimCLR 也显示出通过对比学习（Contrastive Learning）对 ResNet 进行预训练也可以显著提升泛化性能。这些成功表明，无标注数据本身包含丰富的语义知识，因此如果通过预训练可以使模型能捕捉无标注数据的分布，就能作为初始化帮助一系列下游任务。

受到这些工作的启发，我们思考能否将预训练的想法运用到图数据分析中。本工作就致力于预训练图神经网络，以期 GNN 能够学习到图数据的结构和特征信息，从而能帮助标注数据较少的下游任务。

3、GPT-GNN模型

要在图数据上做预训练，第一个问题是：如何设计合适的无监督学习任务？

本工作提出用生成模型来对图分布进行建模，即逐步预测出一个图中一个新节点会有哪些特征、会和图中哪些节点相连。

GPT-GNN通过最大化图的似然函数来预训练 GNN，也就是说

$θ^∗=\mathop{\max}\limits_θp(G;θ)$θ∗=θmax​p(G;θ)

图的生成过程是迭代生成过程，假定对图中的点进行排列 $π$π，在 $π$π 的排列顺序下定义图的似然函数

$p(G;θ)=\mathbb{E}_π[p_θ(X^π,E^π)]$p(G;θ)=Eπ​[pθ​(Xπ,Eπ)]

其中 $X^π$Xπ定义了节点向量 $X^π∈R^{∣V∣×d}$Xπ∈R∣V∣×d，$E_i^{\pi}$Eiπ​表示所有与节点 $i^π$iπ相连的边。对数似然函数定义为

$\log p_θ(X,E)=∑_{i=1}^{∣V∣}\log p_θ(X_i,E_i∣X_{<i},E_{<i})$logpθ​(X,E)=i=1∑∣V∣​logpθ​(Xi​,Ei​∣X<i​,E<i​)

下一个问题是如何计算 $p_θ(X_i,E_i∣X_{<i},E_{<i})$pθ​(Xi​,Ei​∣X<i​,E<i​)， 假定我们提前可以观察到部分的边，GPT-GNN算法可以将节点特征的生成和边的生成分成两部分

• 给定观测到的与当前生成节点相连的边，生成节点特征
• 给定观测到的与当前生成节点相连的边，上一步生成的节点特征，生成其他的边

假设 $E_{i,o}$Ei,o​表示与$i$i 相连的可以观察到的边
$p_{\theta}(X_i,E_i|X_{<i},E_{<i})=\mathbb{E}_o[p_{\theta}(X_i,E_{i,\urcorner o}|E_{i,o},X_{<i},E_{<i})] \\=\mathbb{E}_o[p_{\theta}(X_i|E_{i,o},X_{<i},E_{<i})\cdot p_{\theta}(E_{i,\urcorner o}|E_{i,o},X_{\leq i},E_{<i})]$pθ​(Xi​,Ei​∣X<i​,E<i​)=Eo​[pθ​(Xi​,Ei,┐o​∣Ei,o​,X<i​,E<i​)]=Eo​[pθ​(Xi​∣Ei,o​,X<i​,E<i​)⋅pθ​(Ei,┐o​∣Ei,o​,X≤i​,E<i​)]为了对两步生成过程进行建模，将当前阶段的节点的节点拆分成两个点，分别用来进行属性生成和边生成。对于属性生成节点，使用共享的表示dummy的初始化向量 $X_{init}$Xinit​表示。对于边生成节点，我们将该点上的属性作为输入传进去。

假定 $h^{Attr}$hAttr 和 $h^{Edge}$hEdge分别表示属性生成节点和边生成节点的输出向量，在GNN进行消息传递时，只是用 $h^{Edge}$hEdge进行消息传递。定义节点属性的解码器为 $Dec^{Attr}(⋅)$DecAttr(⋅)，属性损失函数定义为$\mathcal{L}_i^{Attr}=Distance(Dec^{Attr}(h_i^{Attr}),X_i)$LiAttr​=Distance(DecAttr(hiAttr​),Xi​)对于边生成模型，假定边与边之间时相互独立的，即$p_θ(E_{i,\urcorner o}∣E_{i,o},X_{≤i},E_{<i})=∏_{j^+∈E_{i,\urcorner o}}p_θ(j^+∣E_{i,o},X_{≤i},E_{<i})$pθ​(Ei,┐o​∣Ei,o​,X≤i​,E<i​)=j+∈Ei,┐o​∏​pθ​(j+∣Ei,o​,X≤i​,E<i​)损失函数定义为
$\mathcal{L}_i^{edge}=−∑_{j+∈E_{i,\urcorner o}}\log\frac{\exp(Dec^{Edge}(h_i^{Edge},h_{j^+}^{Edge}))}{∑_{j∈S_i^−∪\{j^+\}}\exp(Dec^{Edge}(h_i^{Edge},h_j^{Edge}))}$Liedge​=−j+∈Ei,┐o​∑​log∑j∈Si−​∪{j+}​exp(DecEdge(hiEdge​,hjEdge​))exp(DecEdge(hiEdge​,hj+Edge​))​

其中 $S_i^−$Si−​表示不与 $i$i相邻的节点。算法的整体流程如下所示

4、应用

1. 异质网络：异构图意味着包含不同类型的节点和边。对于异构图，唯一的区别是每种类型的节点和边都可以具有自己的解码器，该解码器由异构GNN指定。

2. 大型网络：对图进行子图采样以进行训练。 特别的，建议分别使用LADIES算法和其异构版本HGSampling 从同构图和异构图采样密集子图。 从理论上讲，这两种方法都保证了采样节点之间的高度互连，并最大程度地保留了结构信息。估计边生成等式中的对比损失，需要遍历输入图的所有节点。但是，我们只能访问子图中的采样节点以估计此损失，从而使自监督仅关注本地信号。 为了缓解此问题，提出了“自适应队列”，它在先前采样的子图中将节点表示形式存储为负采样。每次处理新的子图时，我们都会通过添加新的节点表示并删除旧的节点表示来逐步更新此队列。由于不会严格更新模型参数，因此队列中存储的负样本是一致且准确的。自适应队列使我们能够使用更大的负样本池 $S_i^−$Si−​。此外，跨不同样本子图的节点可以引入用于对比学习的全局结构指导。

5、实验

作者除了常规的性能实验、消融实验以外，提出了三种迁移实验的设置

• 时间迁移性：使用来自不同时间跨度的数据进行预训练和微调。
• 领域迁移性：使用来自不同领域的数据进行预训练和评估
• 时间+领域迁移性

我们在两个大规模异构网络和一个同构网络上进行了实验。

第一个异构图是 Microsoft Academic Graph（OAG），其中包含超过 2 亿个节点和 23 亿条边。另一个是 Amazon Recommendation 数据集。

总体而言，我们提出的 GPT-GNN 在不同的实验设定下显著提高下游任务的性能，平均能达到 9.1％ 的性能提升，且优于其他图预训练的方法。

我们还评估了在不同百分比的标记数据下，GPT-GNN 是否依然能取得提升。我们可以看到，使用 GPT 预训练时，仅使用 20％ 标签数据的模型性能就会比使用 100％ 数据进行直接监督学习的模型性能更高。这显示了预训练的有效性，尤其是在标签稀缺时。

6、总结

个人感觉实验部分存在一些问题，作者做的实验除了迁移鲁棒性以外只有两个常规实验，缺乏pretrain方法之间的比较，算法的有效性应该是前提条件，而算法效果比同类更好才是创新点。