图神经网络从入门到入门

近年来，深度学习领域关于图神经网络（Graph Neural Networks，GNN）的研究热情日益高涨，图神经网络已经成为各大深度学习顶会的研究热点。GNN 处理非结构化数据时的出色能力使其在网络数据分析、推荐系统、物理建模、自然语言处理和图上的组合优化问题方面都取得了新的突破。

图神经网络有很多比较好的综述[1][2][3]可以参考，更多的论文可以参考清华大学整理的 GNN paper list[4] 。

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

笔者注：行文如有错误或者表述不当之处，还望批评指正！

一、为什么需要图神经网络？

随着机器学习、深度学习的发展，语音、图像、自然语言处理逐渐取得了很大的突破，然而语音、图像、文本都是很简单的序列或者网格数据，是很结构化的数据，深度学习很善于处理该种类型的数据（图 1）。

图 1

然而现实世界中并不是所有的事物都可以表示成一个序列或者一个网格，例如社交网络、知识图谱、复杂的文件系统等（图 2），也就是说很多事物都是非结构化的。

图 2

相比于简单的文本和图像，这种网络类型的非结构化的数据非常复杂，处理它的难点包括：

1. 图的大小是任意的，图的拓扑结构复杂，没有像图像一样的空间局部性
2. 图没有固定的节点顺序，或者说没有一个参考节点
3. 图经常是动态图，而且包含多模态的特征

那么对于这类数据我们该如何建模呢？能否将深度学习进行扩展使得能够建模该类数据呢？这些问题促使了图神经网络的出现与发展。

二. 图神经网络是什么样子的？

相比较于神经网络最基本的网络结构全连接层（MLP），特征矩阵乘以权重矩阵，图神经网络多了一个邻接矩阵。计算形式很简单，三个矩阵相乘再加上一个非线性变换（图 3）。

图 3

因此一个比较常见的图神经网络的应用模式如下图（图 4），输入是一个图，经过多层图卷积等各种操作以及激活函数，最终得到各个节点的表示，以便于进行节点分类、链接预测、图与子图的生成等等任务。

图 4

上面是一个对图神经网络比较简单直观的感受与理解，实际其背后的原理逻辑还是比较复杂的，这个后面再慢慢细说，接下来将以几个经典的 GNN models 为线来介绍图神经网络的发展历程。

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

1 . Graph Convolution Networks(GCN)[5]

GCN 可谓是图神经网络的 “开山之作”，它首次将图像处理中的卷积操作简单的用到图结构数据处理中来，并且给出了具体的推导，这里面涉及到复杂的谱图理论，具体推到可以参考[6][7]。推导过程还是比较复杂的，然而最后的结果却非常简单 (图 5)。

图 5

我们来看一下这个式子，天呐，这不就是聚合邻居节点的特征然后做一个线性变换吗？没错，确实是这样，同时为了使得 GCN 能够捕捉到 K-hop 的邻居节点的信息，作者还堆叠多层 GCN layers，如堆叠 K 层有：

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

其中
是归一化之后的邻接矩阵，
相当于给
层的所有节点的 embedding 做了一次线性变换，左乘以邻接矩阵表示对每个节点来说，该节点的特征表示为邻居节点特征相加之后的结果。（注意将
换成矩阵
就是图 3 所说的三矩阵相乘）

那么 GCN 的效果如何呢？作者将 GCN 放到节点分类任务上，分别在 Citeseer、Cora、Pubmed、NELL 等数据集上进行实验，相比于传统方法提升还是很显著的，这很有可能是得益于 GCN 善于编码图的结构信息，能够学习到更好的节点表示。

图 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

第一步，对邻居采样

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

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

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

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

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

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

图 8

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

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

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

到此为止，整个模型的架构就讲完了，那么 GraphSAGE 是如何学习聚合器的参数以及权重矩阵
呢？如果是有监督的情况下，可以使用每个节点的预测 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

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

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

为了提高模型的拟合能力，还引入了多头的 self-attention 机制，即同时使用多个
计算 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 输入图的邻接矩阵
和节点的特征矩阵
，通过编码器（图卷积网络）学习节点低维向量表示的均值
和方差
，然后用解码器（链路预测）生成图。

图 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 上一层生成的节点嵌入
以及分配矩阵
，以端到端的方式分配给下一层的簇，然后将这些簇输入到 GNN 下一层，进而实现用分层的方式堆叠多个 GNN 层的想法。（图 14）

图 14

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

• 分配矩阵的学习

这里使用两个分开的 GNN 来生成分配矩阵
和每一个簇节点新的嵌入
，这两个 GNN 都是用簇节点特征矩阵
和粗化邻接矩阵
作为输入，

• 池化分配矩阵

计算得到分配矩阵
和每一个簇节点新的嵌入
之后，DiffPool 层根据分配矩阵，对于图中的每个节点 / 簇生成一个新的粗化的邻接矩阵
与新的嵌入矩阵
,

总的来看，每层的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）可以以端到端的方式被各种图神经网络整合

然而，注意到，DiffPool也有其局限性，分配矩阵需要很大的空间去存储，空间复杂度为
，
为池化层的层数，所以无法处理很大的图。

参考

1. ^Graph Neural Networks: A Review of Methods and Applications. arxiv 2018 https://arxiv.org/pdf/1812.08434.pdf
2. ^A Comprehensive Survey on Graph Neural Networks. arxiv 2019. https://arxiv.org/pdf/1901.00596.pdf
3. ^Deep Learning on Graphs: A Survey. arxiv 2018. https://arxiv.org/pdf/1812.04202.pdf
4. ^GNN papers https://github.com/thunlp/GNNPapers/blob/master/README.md
5. ^Semi-Supervised Classification with Graph Convolutional Networks(ICLR2017) https://arxiv.org/pdf/1609.02907
6. ^如何理解 Graph Convolutional Network（GCN）？ https://www.zhihu.com/question/54504471
7. ^GNN 系列：图神经网络的 “开山之作”CGN 模型 https://mp.weixin.qq.com/s/jBQOgP-I4FQT1EU8y72ICA
8. ^Inductive Representation Learning on Large Graphs(2017NIPS) https://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
9. ^Graph Attention Networks(ICLR2018) https://arxiv.org/pdf/1710.10903
10. ^Variational Graph Auto-Encoders（NIPS2016） https://arxiv.org/pdf/1611.07308
11. ^VGAE（Variational graph auto-encoders）论文详解 https://zhuanlan.zhihu.com/p/78340397
12. ^Hierarchical Graph Representation Learning withDifferentiable Pooling(NIPS2018) https://arxiv.org/pdf/1806.08804
    https://zhuanlan.zhihu.com/p/136521625