本文从一个更直观的角度对当前经典流行的GNN网络，包括GCN、GraphSAGE、GAT、GAE以及graph pooling策略DiffPool等等做一个简单的小结。 

三、图神经网络的几个经典模型与发展

上述式子还可以使用矩阵形式表示如下， 

图6

当然，其实GCN的缺点也是很显然易见的，第一，GCN需要将整个图放到内存和显存，这将非常耗内存和显存，处理不了大图；第二，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现(比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的)。

2. Graph Sample and Aggregate(GraphSAGE)[8]

为了解决GCN的两个缺点问题，GraphSAGE被提了出来。在介绍GraphSAGE之前，先介绍一下Inductive learning和Transductive learning。注意到图数据和其他类型数据的不同，图数据中的每一个节点可以通过边的关系利用其他节点的信息。这就导致一个问题，GCN输入了整个图，训练节点收集邻居节点信息的时候，用到了测试和验证集的样本，我们把这个称为Transductive learning。然而，我们所处理的大多数的机器学习问题都是Inductive learning，因为我们刻意的将样本集分为训练/验证/测试，并且训练的时候只用训练样本。这样对图来说有个好处，可以处理图中新来的节点，可以利用已知节点的信息为未知节点生成embedding，GraphSAGE就是这么干的。

GraphSAGE是一个Inductive Learning框架，具体实现中，训练时它仅仅保留训练样本到训练样本的边，然后包含Sample和Aggregate两大步骤，Sample是指如何对邻居的个数进行采样，Aggregate是指拿到邻居节点的embedding之后如何汇聚这些embedding以更新自己的embedding信息。下图展示了GraphSAGE学习的一个过程，

图7

K 第一步，对邻居采样

第二步，采样后的邻居embedding传到节点上来，并使用一个聚合函数聚合这些邻居信息以更新节点的embedding

第三步，根据更新后的embedding预测节点的标签

接下来，我们详细的说明一个训练好的GrpahSAGE是如何给一个新的节点生成embedding的（即一个前向传播的过程），如下算法图：

首先，(line1)算法首先初始化输入的图中所有节点的特征向量，(line3)对于每个节点 v ，拿到它采样后的邻居节点 N(v) 后，(line4)利用聚合函数聚合邻居节点的信息，(line5)并结合自身embedding通过一个非线性变换更新自身的embedding表示。

注意到算法里面的 K ，它是指聚合器的数量，也是指权重矩阵的数量，还是网络的层数，这是因为每一层网络中聚合器和权重矩阵是共享的。网络的层数可以理解为需要最大访问的邻居的跳数(hops)，比如在图7中，红色节点的更新拿到了它一、二跳邻居的信息，那么网络层数就是2。为了更新红色节点，首先在第一层(k=1)，我们会将蓝色节点的信息聚合到红色解节点上，将绿色节点的信息聚合到蓝色节点上。在第二层(k=2)红色节点的embedding被再次更新，不过这次用到的是更新后的蓝色节点embedding，这样就保证了红色节点更新后的embedding包括蓝色和绿色节点的信息，也就是两跳信息。

为了看的更清晰，我们将更新某个节点的过程展开来看，如图8分别为更新节点A和更新节点B的过程，可以看到更新不同的节点过程每一层网络中聚合器和权重矩阵都是共享的。

图8

那么GraphSAGE Sample是怎么做的呢？GraphSAGE是采用定长抽样的方法，具体来说，定义需要的邻居个数 S ，然后采用有放回的重采样/负采样方法达到S  。保证每个节点（采样后的）邻居个数一致，这样是为了把多个节点以及它们的邻居拼接成Tensor送到GPU中进行批训练。

那么GraphSAGE 有哪些聚合器呢？主要有三个，

这里说明的一点是Mean Aggregator和GCN的做法基本是一致的（GCN实际上是求和）。

到此为止，整个模型的架构就讲完了，那么GraphSAGE是如何学习聚合器的参数以及权重矩阵W呢？如果是有监督的情况下，可以使用每个节点的预测lable和真实lable的交叉熵作为损失函数。如果是在无监督的情况下，可以假设相邻的节点的embedding表示尽可能相近，因此可以设计出如下的损失函数，

那么GrpahSAGE的实际实验效果如何呢？作者在Citation、Reddit、PPI数据集上分别给出了无监督和完全有监督的结果，相比于传统方法提升还是很明显。

至此，GraphSAGE介绍完毕。我们来总结一下，GraphSAGE的一些优点，

（1）利用采样机制，很好的解决了GCN必须要知道全部图的信息问题，克服了GCN训练时内存和显存的限制，即使对于未知的新节点，也能得到其表示

（2）聚合器和权重矩阵的参数对于所有的节点是共享的

（3）模型的参数的数量与图的节点个数无关，这使得GraphSAGE能够处理更大的图

（4）既能处理有监督任务也能处理无监督任务

（就喜欢这样解决了问题，方法又简洁，效果还好的idea！！！）

当然，GraphSAGE也有一些缺点，每个节点那么多邻居，GraphSAGE的采样没有考虑到不同邻居节点的重要性不同，而且聚合计算的时候邻居节点的重要性和当前节点也是不同的。

3. Graph Attention Networks(GAT)[9]

为了解决GNN聚合邻居节点的时候没有考虑到不同的邻居节点重要性不同的问题，GAT借鉴了Transformer的idea，引入masked self-attention机制，在计算图中的每个节点的表示的时候，会根据邻居节点特征的不同来为其分配不同的权值。

具体的，对于输入的图，一个graph attention layer如图9所示，

图9

其中a采用了单层的前馈神经网络实现，计算过程如下（注意权重矩阵W对于所有的节点是共享的）：

计算完attention之后，就可以得到某个节点聚合其邻居节点信息的新的表示，计算过程如下： 

为了提高模型的拟合能力，还引入了多头的self-attention机制，即同时使用多个W^k计算self-attention，然后将计算的结果合并（连接或者求和）：

此外，由于GAT结构的特性，GAT无需使用预先构建好的图，因此GAT既适用于Transductive Learning，又适用于Inductive Learning。

那么GAT的具体效果如何呢？作者分别在三个Transductive Learning和一个Inductive Learning任务上进行实验，实验结果如下：

无论是在Transductive Learning还是在Inductive Learning的任务上，GAT的效果都要优于传统方法的结果。

至此，GAT的介绍完毕，我们来总结一下，GAT的一些优点，

（1）训练GCN无需了解整个图结构，只需知道每个节点的邻居节点即可

（2）计算速度快，可以在不同的节点上进行并行计算

（3）既可以用于Transductive Learning，又可以用于Inductive Learning，可以对未见过的图结构进行处理

（仍然是简单的idea，解决了问题，效果还好！！！）

到此，我们就介绍完了GNN中最经典的几个模型GCN、GraphSAGE、GAT，接下来我们将针对具体的任务类别来介绍一些流行的GNN模型与方法。

四、无监督的节点表示学习（Unsupervised Node Representation）

由于标注数据的成本非常高，如果能够利用无监督的方法很好的学习到节点的表示，将会有巨大的价值和意义，例如找到相同兴趣的社区、发现大规模的图中有趣的结构等等。

图10

这其中比较经典的模型有GraphSAGE、Graph Auto-Encoder（GAE）等，GraphSAGE就是一种很好的无监督表示学习的方法，前面已经介绍了，这里就不赘述，接下来将详细讲解后面两个。

1. Graph Auto-Encoder(GAE)[10]

在介绍Graph Auto-Encoder之前，需要先了解自编码器(Auto-Encoder)、变分自编码器(Variational Auto-Encoder)，具体可以参考[11]，这里就不赘述。

理解了自编码器之后，再来理解变分图的自编码器就容易多了。如图11输入图的邻接矩阵A和节点的特征矩阵X，通过编码器（图卷积网络）学习节点低维向量表示的均值μ和方差σ，然后用解码器（链路预测）生成图。

图11

编码器（Encoder）采用简单的两层GCN网络，解码器（Encoder）计算两点之间存在边的概率来重构图，损失函数包括生成图和原始图之间的距离度量，以及节点表示向量分布和正态分布的KL-散度两部分。具体公式如图12所示：

图12

另外为了做比较，作者还提出了图自编码器(Graph Auto-Encoder)，相比于变分图的自编码器，图自编码器就简单多了，Encoder是两层GCN，Loss只包含Reconstruction Loss。

那么两种图自编码器的效果如何呢？作者分别在Cora、Citeseer、Pubmed数据集上做Link prediction任务，实验结果如下表，图自编码器（GAE）和变分图自编码器（VGAE）效果普遍优于传统方法，而且变分图自编码器的效果更好；当然，Pumed上GAE得到了最佳结果。可能是因为Pumed网络较大，在VGAE比GAE模型复杂，所以更难调参。

五、Graph Pooling

Graph pooling是GNN中很流行的一种操作，目的是为了获取一整个图的表示，主要用于处理图级别的分类任务，例如在有监督的图分类、文档分类等等。

图13

Graph pooling的方法有很多，如简单的max pooling和mean pooling，然而这两种pooling不高效而且忽视了节点的顺序信息；这里介绍一种方法：Differentiable Pooling (DiffPool)。

1.DiffPool[12]

在图级别的任务当中，当前的很多方法是将所有的节点嵌入进行全局池化，忽略了图中可能存在的任何层级结构，这对于图的分类任务来说尤其成问题，因为其目标是预测整个图的标签。针对这个问题，斯坦福大学团队提出了一个用于图分类的可微池化操作模块——DiffPool，可以生成图的层级表示，并且可以以端到端的方式被各种图神经网络整合。

DiffPool的核心思想是通过一个可微池化操作模块去分层的聚合图节点，具体的，这个可微池化操作模块基于GNN上一层生成的节点嵌入X以及分配矩阵 S ，以端到端的方式分配给下一层的簇，然后将这些簇输入到GNN下一层，进而实现用分层的方式堆叠多个GNN层的想法。（图14）

图14

那么这个节点嵌入和分配矩阵是怎么算的？计算完之后又是怎么分配给下一层的？这里就涉及到两部分内容，一个是分配矩阵的学习，一个是池化分配矩阵。

总的来看，每层的DiffPool其实就是更新每一个簇节点的嵌入和簇节点的特征矩阵，如下公式： 

至此，DiffPool的基本思想就讲完了。那么效果如何呢？作者在多种图分类的基准数据集上进行实验，如蛋白质数据集（ENZYMES，PROTEINS，D&D），社交网络数据集（REDDIT-MULTI-12K），科研合作数据集（COLLAB），实验结果如下： 

其中，GraphSAGE是采用全局平均池化；DiffPool-DET是一种DiffPool变体，使用确定性图聚类算法生成分配矩阵；DiffPool-NOLP是DiffPool的变体，取消了链接预测目标部分。总的来说，DiffPool方法在GNN的所有池化方法中获得最高的平均性能。

为了更好的证明DiffPool对于图分类十分有效，论文还使用了其他GNN体系结构（Structure2Vec(s2v)），并且构造两个变体，进行对比实验，如下表：

可以看到DiffPool的显著改善了S2V在ENZYMES和D&D数据集上的性能。

而且DiffPool可以自动的学习到恰当的簇的数量。

至此，我们来总结一下DiffPool的优点，

（1）可以学习层次化的pooling策略

（2）可以学习到图的层次化表示

（3）可以以端到端的方式被各种图神经网络整合

重点总结

 

1.GCN的缺点也是很显然易见的，第一，GCN需要将整个图放到内存和显存，这将非常耗内存和显存，处理不了大图；第二，GCN在训练时需要知道整个图的结构信息(包括待预测的节点)

2.GraphSAGE的优点：

（1）利用采样机制，很好的解决了GCN必须要知道全部图的信息问题，克服了GCN训练时内存和显存的限制，即使对于未知的新节点，也能得到其表示

（2）聚合器和权重矩阵的参数对于所有的节点是共享的

（3）模型的参数的数量与图的节点个数无关，这使得GraphSAGE能够处理更大的图

（4）既能处理有监督任务也能处理无监督任务

3.GAT的优点：

（1）训练GCN无需了解整个图结构，只需知道每个节点的邻居节点即可

（2）计算速度快，可以在不同的节点上进行并行计算

（3）既可以用于Transductive Learning，又可以用于Inductive Learning，可以对未见过的图结构进行处理