图神经网络（Graph Neural Network）在社交网络、推荐系统、知识图谱上的效果初见端倪，成为近2年大热的一个研究热点。然而，什么是图神经网络？图和神经网络为什么要关联？怎么关联？

本文将以浅显直觉的方式，介绍GNN的灵感来源，构造方法，训练方式等，根据《Representation Learning on Networks》中GNN部分，做了具体的解读和诠释，并增补了一些代码中才有的实现细节，帮助初学者理解。

代码实现：（https://github.com/leichaocn/graph_representation_learning）

目录
卷积神经网络的启示
核心想法
传播机制
传播机制举例
训练的方式
一般的设计步骤
Node2Vec与GNN的对比
总结
参考文献

卷积神经网络的启示

回顾对图像的简单卷积：

3im1.png

图1.卷积网络的基本操作（source）

如图1所示：一幅图（image）所抽取的特征图（features map）里每个元素，可以理解为图（image）上的对应点的像素及周边点的像素的加权和（还需要再激活一下）。

同样可以设想：一个图（graph）所抽取的特征图（也就是特征向量）里的每个元素，也可以理解为图（graph）上对应节点的向量与周边节点的向量的加权和。
澄清几个概念：

特征向量：一条数据（image、word、node等）的数字化表示，是机器学习任务的必备输入。
embedding：更好的特征向量，蕴含潜在语义信息，是来自network训练后的结果，如果能找到优秀的embedding，将有效提升后面机器学习任务的性能表现。例如从word2vec网络中抽出的word embedding向量，“北京”“巴黎”这两个词就比较相似，因为都是首都；从CNN网络中抽出的image embedding，暹罗猫、无耳猫两个图片的向量就比较相似，因为都有猫。
features map ：由cnn生成的特征向量，也就是image embedding。image 经过一层CNN前向传播后的输出，是一个二维的矩阵，只要进行拉直（flatten），就转变为了一维的特征向量。类似于全连接神经网络网络里每一层里都能获取的一维的特征向量。

这种迁移联想值得好好体会。

体会明白后，那具体怎么做呢？

核心想法

正如上面讨论的，归纳为一句话：用周围点的向量传播出自己的Embedding。

一个非常简单的例子就能搞明白。

3im2.png

图2.一个图（graph）的例子（source）

对于图2来说，要计算节点A的Embedding，我们有以下的两条想法：

节点A的Embedding，是它的邻接节点B、C、D的Embedding传播的结果
而节点B、C、D的Embedding，又是由它们各自的邻接节点的Embedding传播的结果。

但是你可能会说，这样不断追溯，何时能结束？所以为了避免无穷无尽，我们就做两层，可以构造图3的传播关系。

3im3.png

图3.由两层传播生成节点A的Embedding（source）

第0层即输入层，为每个节点的初始向量（根据所处领域里特征数据进行构建），不妨称为初始Embedding。

第一层

节点B的Embedding来自它的邻接点A、C的Embedding的传播。

节点C的Embedding来自它的邻接点A、B、C、D的Embedding的传播。

节点D的Embedding来自它的邻接点A的Embedding的传播。
第二层

节点A的Embedding来自它的邻接点B、C、D的Embedding的传播。

好了，大概可能有点感觉了，可是传播到底是什么？图中的小方块里到底在什么什么？

（注意：图中所有的方块代表的操作均相同，大小、颜色的差异没有任何含义）

传播机制

小方块里做的就两件事：

收集（Aggregation）

简言之，就是对上一层的所有邻接节点的Embedding，如何进行汇总，获得一个Embedding，供本层进行更新。
更新（Update）

即对本层已“收集完毕”的邻接点数据，是否添加自身节点的上一层Embedding，如果是如何添加，如何激活，等等方式，最终输出本层的Embedding。

表达成数学公式，即下面这个式子：

3im4.png

先解释其中的符号含义： $h$ 表示节点的Embedding，下标 $v$ 或 $u$ 表示节点的索引，上标 $k$ 表示第几层的意思， $\sigma$ 表示激活函数， $W_k$ 和 $B_k$ 表示矩阵， $N(v)$ 表示节点 $v$ 的邻接点集合， $AGG(\cdot)$ 表示收集操作。

这个公式的右边就做了两件事：

收集：即 $AGG(\cdot)$ 部分
更新：除了 $AGG(\cdot)$ 外的其他部分。

这个公式太抽象，我们举例说明三种常见的图神经网络，看看是如何设计的。

传播机制举例

基础版本

3im5.png

1）收集

即直接对上一层所有节点的Embedding求平均。

2）更新

即为用收集完毕的Embedding与本节点上一层的Embedding进行了加权和，然后再激活。显然，由于上一层Embedding与本层Embedding维度相同，所以 $W_k$ 和 $B_k$ 为方阵。

图卷积网络（Graph Convolutional Networks）

3im6.png

1）收集

由 $u\in N(v)\cup v$ 可知，收集的输入Embeddings不仅仅包括节点 $v$ 的邻接点们的Embedding，还包括节点 $v$ 自身的Embedding，而分母变成了 $\sqrt{\mid N(u) \mid \mid N(v) \mid}$ ，是一种更复杂的加权和，不仅考虑了节点 $v$ 的邻接点的个数，还考虑了每个邻接点 $u$ 自身的邻接接个数。（基础版本中的平均是最简单的加权和）

2）更新

显然比基础版本简单多了，不再考虑节点 $v$ 自己的上一层Embedding，直接让收集好的Embedding乘上矩阵 $W_k$ 后再激活完事。

之所以叫图卷积网络，是因为和卷积网络的套路类似，对自己和周边节点（像素）进行加权求和。

GraphSAGE

3im7.png

这不就是咱们上面提到的那个概念公式？是的，GraphSAGE由于其变体较多，所以需要用这个最抽象的公式来概括它。

1）收集

可以有如下的收集方式：

直接平均

这是最简单的收集方式

3im8.png

池化

3im9.png

LSTM

3im10.png

2）更新

收集好的Embedding经过矩阵 $A_k$ 变换，节点 $v$ 自己上一层的Embedding经过矩阵 $B_k$ 变换，我们即可得到两个Embedding，把它俩给按列拼接起来。

这里要注意：它俩不是相加；矩阵 $A_k$ 和矩阵 $B_k$ 都不是方阵，均自带降维功能。 $AGG(\cdot)$ 输出是 $d$ 维， $h^{k-1}_v$ 是 $d$ 维，但是经过军阵变换后，它俩都成了 $d/2$ 维，经过拼接，又恢复成 $d$ 维。

训练的方式

无监督的训练

跑不同的Aggregation和Update方法，结合自定义的损失函数，都可以训练出这些权重。这里的自定义损失函数，需要根据你对节点Embedding的最终期望，让它附加上一个什么样的效果来设计。

例如word2vec利用序列中的上下文信息，用一个词预测周围词，构造分类损失来训练。图的无监督训练也可以用一个节点预测周围节点，构造分类损失来训练。当然，还有其他的无监督套路，这个视频不错（18min~21min）：https://www.bilibili.com/video/av53422483/

在无监督任务中，获取经过神经网络优化的Embedding，就是我们的目的。

有监督的训练

如果我们想要实现节点分类，那么我们就需要有带标签的训练数据，设计损失函数，即可进行训练。

例如，我们有一批带label的图结构的数据，已经标记好了哪些是水军，哪些是普通用户。我们就可以构造如下的交叉熵损失函数。

3im11.png

图4.有监督训练中损失函数的构造（source）

转换矩阵

注意其中的 $z_v$ 即节点 $v$ 的Embedding， $y_v$ 是节点 $v$ 的label，那 $\theta$ 是什么鬼？

如刚才我们讨论的，图神经网络的传播结果，是所有节点经过“传播”优化的Embedding，这些Embedding的维度均为 $d$ 维（在初始化时定义好的），而我们分类任务可能是 $c$ 类，所以，需要再前向传播的最后一层，加入矩阵，把 $d$ 维的输出映射成 $c$ 维的输出，这样才能让交叉熵损失函数对应起来。

由于我们列举的是二分类任务，图4中也用的是二分类的交叉熵损失，因此只需要1维输出足矣，所以在这里的 $c$ 为1， $\theta$ 为一个向量（可视为把 $d$ 维压缩为1维的特殊矩阵）。