GPT-GNN: Generative Pre-Training of Graph Neural Networks
文中指出训练GNN需要大量和任务对应的标注数据，这在很多时候是难以获取的。一种有效的方式是，在无标签数据上通过自监督的方式预训练一个GNN，然后在下游任务上只需要少量的标注数据进行fine-tuning。
本文提出了GPT-GNN通过生成式预训练的方式来初始化GNN。GPT-GNN引入了一个自监督的属性图生成任务，来pre-training一个GNN，使其能够捕捉图上的结构信息和节点属性信息。
图生成任务被分成了两部分：①属性生成。②边生成。
pre-training的GNN要能够捕捉input graph的结构信息和节点属性信息，使其能够在相似领域的下游任务上通过少量label的fine-tuning就能达到很好的泛化效果。本文采用的方式是重构输入的属性图来对图分布建模。
第一步，如上左图所示，通过自监督学习任务（节点属性生成和边生成）来预训练GNN。第二步，如上右图所示，pre-training好的模型以及参数用于对下游任务的初始化，只需要在少部分标注数据上做fine-tuning。
The GNN Pre-Training Problem
输入G=(V,E,X)，其中V表示顶点集，E表示边集，X表示顶点属性矩阵。
目标：pre-training一个GNN模型，使其能够：1)捕捉图中的结构特征和属性特征。2)能够对图的下游任务有帮助。
也就是对图G=(V,E,X)不使用label学习一个可以泛化的GNN模型fθ。
The Generative Pre-Training Framework
GPT-GNN通过重构/生成输入图的结构信息和节点属性信息来pre-training GNN。given 输入图G=(V,E,X)和GNN模型fθ，图和GNN的likelihood定义为p(G,θ)，通过最大化likelihood来预训练GNN，也就是
如何对p(G,θ)建模？
通过自回归的方法分解目标概率分布。
首先说明什么是自回归
如上式所示，c为常数项，є为随机误差，概括来说就是X的当期值等于一个或数个前期值的线性组合加常数项加随机误差。
对于graph来说，自回归方法概括为：nodes in the graph come in an order, and the edges are generated by connecting each new arriving node to existing nodes.
对于一个给定的order，通过自回归的方式分解log likelihood，每次生成一个节点。
在step i，given 所有在前面步骤生成的节点，包括节点属性X<i和节点之间的边E<i来生成新的节点i，包括节点属性Xi和与现有节点的连接边Ei.
Factorizing Attributed Graph Generation
如何对pθ(Xi,Ei|X<i,E<i)建模？
一种简单的方式是假设Xi和Ei是独立的，也就是
然而，这种分解方式完全忽略了节点属性和节点之间联系（边）之间的依赖关系。然而这种依赖关系是属性图和基于聚合邻居节点信息的GNN的核心属性。
因此，文中提出了一种分解方式，当生成一个新的节点属性时，给出结构信息，反之亦然。
从而整个生成过程可以分为两部分：
1)given 观测边，生成节点属性。
2)given 观测边和1)中生成的节点属性，生成剩下的边。
通过这种方式，模型能够捕捉每个节点属性和结构之间的依赖关系。
定义变量o来表示Ei中观测边的index vector，即Ei,o表示已经观测到的边。¬o表示masked边（要生成边）的index。
通过引入o，可以把前面的分布重写为所有可能观测边的期望likelihood.
这里的理解非常重要，第一个等式中，把Ei拆成了Ei,¬o和Ei,o，也就是说指定了哪些边是观测边，哪些边是masked边。需要注意的是，当o确定下来以后，¬o也是确定的。因此等式外面加上了对o的累加，这里可以理解为类似于全概率公式去对所有可能的o求和。
此外，这里需要注意Ei，E<i，Ei,o，Ei,¬o四个符号分别表示的是什么。现在位于step i，E<i是指在step i之前已经生成的边，Ei是指在step i将会生成的边（与节点i相连，有好多条），之后再将Ei中的边生成过程拆分成已经生成和将要生成两部分，即Ei,o和Ei,¬o。
下一个等式中，把第二个p看作概率分布，写作对于o期望的形式。最后把Xi和Ei,¬o看作独立的过程，拆成两个概率分布。
这种分解的优势在于，没有忽略Xi和Ei,o的联系。第一项表示given观测边，聚合目标节点i的邻居信息来生成其属性Xi.第二项表示given观测边和刚生成的属性Xi，预测Ei,¬o中的边是否存在。
如上图所示，给出了一个例子。对于一个academic graph，我们要去生成一个paper node，它的属性为title，并且其和author，publish venue，reference相连。上图中的实线部分为已经观测到的边，首先生成节点的属性，即title。然后基于author1，author2，author3和刚生成的节点属性title，预测剩下的边，即虚线部分。
Efcient Attribute and Edge Generation
出于效率的考虑，希望：
1)对于输入图只跑一次GNN就能计算节点属性生成和边生成过程的loss。
2)希望节点属性生成和边生成能同时进行。
然而，边生成需要用到节点属性信息，如果两个生成过程同时进行，会导致信息泄漏。
为了避免这个问题，将节点分为两种类型：
•属性生成节点。mask住这些节点的属性，用一个共用的dummy token Xinit来代替，Xinit和Xi的维度是相同的，并且在pre-training的过程中学习到。
•边生成节点。保持它们原有的属性。
需要注意的是，同一个节点在不同阶段扮演不同的角色，可能是属性生成节点也可能是边生成节点。只是在某一阶段，一个节点有一个确定的角色。
在graph上训练GNN来生成各节点的embedding，用hAttr和hEdge来分别表示属性生成节点和边生成节点的embedding。由于属性生成节点的属性被mask住了，因此hAttr中包含的信息通常会少于hEdge。因此，在GNN的message passing过程中，只使用hEdge作为向其他节点发送的信息。也就是说，对于每个节点，其聚合邻居hEdge的信息和自身的信息来生成新的embedding。之后，对于节点的embedding，使用不同的decoder来生成节点属性和边。（注意，节点的embedding和节点属性不是一回事。通俗理解，在GNN中节点的属性是input，节点的embedding是hidden layer。）
对于属性生成，用DecAttr来表示decoder，输入hAttr来生成节点属性。decoder的选择依赖于节点属性的类型，如果是text类型的节点属性，可以使用LSTM等；如果节点属性是vector，可以使用MLP。定义一个距离函数来度量生成属性和真实属性之间的差异，对于text类型属性，可以使用perplexity，对于vector属性，可以使用L2距离。由此，可以计算属性生成过程中的loss
最小化生成属性和真实属性之间的差异，等价于对generate attributes做MLE，也就是最大化下式
从而捕捉了图中的节点属性信息。
对于边生成过程，假设每条边的生成过程和其他边是独立的，由此对likelihood进行分解
得到hEdge后，如果节点i和节点j相连，则使用
进行建模，DecEdge是一个pairwise score function。
loss定义为
Si-指的是没有和节点i相连的节点。
最小化loss等价于对generate edges做MLE，从而捕捉了图中的结构信息。
上图给出了属性图生成过程的一个具体例子。
a)对于input graph确定permutation order π。
b)随机挑选一部分与节点i相连的边作为observed edges Ei,o，剩下的边作为masked edges Ei,¬o，并且删除masked edges。
c)把节点分为属性生成节点和边生成节点。
d)计算节点3,4,5的embedding，包括它们的属性生成节点和边生成节点。
(d)-(e)通过对于每个节点并行进行节点属性预测和masked边预测来训练一个GNN模型。
完整的算法流程如下所示。
对于上图的算法流程进行详细的说明。
输入一个属性图，每次采样一个子图G~作为训练的实例进行训练。首先决定permutation order π。同时，我们希望能够并行化训练，只做一次前向传播，就能得到整个图的embedding，由此可以同时计算所有节点的loss。因此，根据permutation order π来移除边，也就是使每个节点只能从跟低order的节点处获得信息。
之后，需要决定哪些边被mask。对于每个节点，获得其所有的出边，随机挑选一部分边被mask住，这一过程对应上述line4。
之后，对节点进行划分，得到整个图中节点的embedding，用于之后loss的计算，对应line5。
lone 7-9进行loss的计算。
line 8中，通过整合采样图中未连接的节点和Q中以前计算的节点embedding来选择负样本，这种方式能够减轻对于采样图优化和对于整个图优化的差距。
在line11-12中，优化模型并更新Q。
GPT-GNN for Heterogeneous & Large Graphs
对于异构图，即包含不同类型的点和边的图，唯一的不同在于不同类型的点和边采用不同的decoder。
对于大规模的图，可以采样子图来进行训练，即上述算法流程中Sampler的作用。为了计算Ledge这一loss，需要遍历输入图的所有节点。然而，我们只能在采样的子图上计算这个loss。为了缓解这一差异，提出了adaptive queue，其中存储了之前采样的子图的节点embedding作为负样本。每次采样一个新的子图时，逐步更新这个队列，增加新的节点embedding，移除旧的节点embedding。通过引入adaptive queue，不同采样子图中的节点也能为全局的结构提供信息。
