本文我们将主要介绍各种典型的图神经网络的网络架构和训练方法。文章《A Comprehensive Survey on Graph Neural Networks》[1]提供了一个全面的图神经网络(GNNs) 概述，并且将最新的图神经网络分为四类，即递归图神经网络(RecGNNs)、卷积图神经网络(ConvGNNs)、图自动编码器(GAEs)和时空图神经网络(STGNNs)。在图神经网的实际应用中，卷积图神经网络的使用最为广泛，因此，本文将重点介绍ConvGNNs一类网络模型，如上图GNN Roadmap所示。

1. 欧式空间卷积

         在讲卷积图神经网络（非欧空间做卷积）之前，我们先来回顾下卷积神经网络（欧式空间做卷积）的过程。有一张如下图所示的6*6的image，我们在做卷积的时候，通常会使用一个固定大小的卷积核，比如3*3，然后根据设置的步长滑动整张6*6的image，在每一次滑动之处与原图相应位置做内积。如下图为卷积核滑动两次之后的结果。

但是对于非欧空间的图结构，我们无法找到一个固定大小的卷积核去滑动整个图区域，如下图所示。

这时我们就要针对图的特殊结构，借助欧式空间的卷积方法和图结构特征，提出两种卷积图神经网络的卷积方案：

方案一：

本篇我们将主要介绍基于空间的卷积图神经网络方法和对应的典型的网络架构。

2. Spatial-based Convolution

在讲基于空间的卷积图神经网络方法之前，我们先引入两个术语：

lAggregate：

用当前层的某节点邻居状态特征更新下一层该节点的状态特征（下左图）。比如下图，我们想要将（下标代表节点的索引，上标代表当前在第几层卷积操作）通过图卷积的方式转变成，我们可以通过某种加权求和的方式将 Layer i的以及的邻居节点的feature整合起来，从而得到的feature，其它节点一样的道理，最后得到Layer i+1的hidden state。

lReadout：

把所有节点的状态特征集合起来代表整个图的状态特征（下右图）。即采用某种sum或者average的方式将所有nodes的feature抽象成一个hidden state，并以此代表整张图的feature。

2.1

图神经网络

(Neural Network for Graphs，NN4G)[2]

NN4G在图神经网络领域算是比较早（2009）的提出的卷积图神经网络模型，其通过直接将节点的邻域信息相加来进行图卷积，表达式如下：

其中表示图中某个节点的索引，K代表当前所在的卷积层数。表示节点的所有邻居。是激活函数，比如Relu，和是待学习的模型参数，即下图中的，下图中Hidden Layer 1中的的获得是将以及其邻居的信息进行相加，并通过加权的方式整合input layer在该节点的信息，转成矩阵形式就是： 

其中矩阵就是图网络的邻接矩阵。

而readout层则通过对每一层的所有节点信息的取平均，即下图中所有紫色节点  ，从而获得每一层图的representation，并对每一层的信息通过求和平均的方式进行整个图的representation更新，即：

对于NN4G，其具体的计算过程可以用下面这幅图概括。NN4G也是卷积图神经网络的代表性结构，后续的卷积图神经网络都是或多或少的在NN4G的基础上做一些简单的修改（Aggregate）而获得。所以理解NN4G的运算流程对于理解基于空间的卷积图神经网络至关重要。

2.2

扩散卷积神经网络

(Diffusion Convolutional Neural Network,  DCNN)[3]

DCNN在Aggregate阶段给出了不一样的方法，DCNN将图卷积视为扩散过程，它假设信息以一定的转移概率从一个节点转移到邻近的节点，使信息分布在几轮后达到均衡。如下图所示，第一层的的结果是与距离为1的节点的featue的求和平均，同理第二层的则是与距离为2的节点的featue的求和平均，这样我们对每一层的卷积操作可以用以下公式表示：

其中K表示层数，代表转移矩阵，是节点度矩阵，A是邻接矩阵，就代表了卷积所能观测到的节点邻居范围，时表示对距离为1的邻居节点的卷积，时表示对距离为2的邻居节点的卷积。当我们计算出了每一层的节点的feature的时候，我们需要对每一层的节点feature进行concatenation成一个矩阵，然后通过一些线性变换对每个节点在不同层的feature做特征变换，如下图所示，最终得到整张图或者每个节点的特征矩阵。

2.3

混合模型

(Mixture Model Networks, MoNET)[4]

通过上述模型，我们可以发现，当计算某个节点在某一层的hidden state的时候，对于该节点的所有邻居上述算法都是一视同仁。但是实际情况可能是任何两个节点之间的关系是有区别的。比如在一副社交关系图谱中，某个个体和其所连接的所有个体亲密关系通常不会相同。这就需要一种新的aggregate方式来解决。

MoNET同样是定义了一种新的Aggregate的方式，在Aggregate阶段不是简单的对邻居节点feature的平均求和，而是通过加权的方式，权重的计算则是通过衡量节点之间的度的距离方式，即：

当然这里只是提出了一种权重的计算方式，实际实现中可以选择不同的权重实现方式。其中表示节x 的度，图中的w则是特征变换（比如NN），经过NN对节点feature进行编码，最后对某一节点的邻居节点特征加权求和。

2.4

图采样聚合模型

(Graph Sample and aggregate, GraphSAGE)[5]

GraphSAGE主要是通过对邻居节点采样的方法对节点信息进行更新，即图中的Step 1，然后再对这些采样的节点信息进行某种方式的聚合，主要有Mean\Pooling\LSTM三种aggregate的方法，即图中的Step 2，Step 3则是利用聚合信息进行当前节点label或者邻居节点的预测，预测的方式有两种，一种是无监督学习方式。无监督学习基于图的损失函数希望临近的顶点具有相似的向量表示（公式的前半部分），同时让分离的顶点的表示尽可能区分（公式的后半部分），损失函数如下：

其中是的临近节点，是负采样样本的分布，即对远离节点的节点的采样，是负采样的个数，是待学习的节点特征。第二种是有监督学习方式，监督学习形式根据任务的不同直接设置目标函数即可，如最常用的节点分类任务使用交叉熵损失函数等。

2.5

图注意神经网络

(Graph Attention Networks, GAT)[6]

注意力机制已经在传统神经网络CNN和RNN中有了成功的实践，并且使用attention后模型的性能在特定任务上都有不少的提升。GAT是将attention机制实现在卷积图神经网络之中。这里的attention就是一种用来计算节点与邻居之间权重的方式，最后通过加权求和的方式更新节点的feature，节点间权重的计算公式如下： 

其中是模型更新之后的权重表达式，是节点v相对于节点u的attention值，w是模型学习的参数。

下图就是GAT模型的图卷积层的更新过程，其中 e(energy)就是attention的权重。

3. 总结

本篇博文主要介绍了Spatial-based Convolution（基于空间的卷积图神经网络），以NN4G为基础，分别介绍了DCNN，MONET，GrapgSAGE，GAT等卷积图神经网络结构以及其实现的方式。对于想要在图神经网络进行实践的同学，可以先学习一些开源的图神经网络框架。目前完成度较好的图神经网络框架主要是基于PyTorch和MXNet的DGL (Deep Graph Library)和PyG (PyTorch Geometric)。