图神经网络是是一种基于图结构的广义神经网络。其实传统的神经网络也是可以处理图数据，只需要进行前期合理的embedding即可，那么为什么还需要GNN呢？GNN其实属于一种embedding算法，它通过在整张图上传递、转换、聚合节点的特征信息，从而生成单节点的embedding。本文简要介绍GNN，力求通俗易懂，需要更详细的研究GNN的话，推荐一篇2019年的综述A Comprehensive Survey on Graph Neural Networks。

基本概念

图

图是由节点（node，或顶点vertex）和边（edge）构成的一种数据结构，节点可以看作是对象，边可以看作是对象之间的关系。进一步的，每个节点可以有自己的信息，边也可以加上权重和方向以表示关系的不同。所以，最基本的图可以表示为\(V,E\)，其中\(V\)是vertex的集合，\(E\)是edge的集合。简单起见，先不考虑V自身的信息和E的权重和方向。

图的表示一般有两种方式：一种是表示为节点对:\((a, b)\)，表示\(a, b\)之间有一条边（暂时不考虑方向）。容易发现，这种表示在边很多的时候会重复存储很多节点信息，可能带来空间的浪费。另一种方式是表示为邻接矩阵（adjacency matrix），即矩阵的横轴和纵轴分别代表边的两端，如果位置\((a, b)\的值\(\Lambda_{a, b} = 1\，即\(a, b\)之间有一条边。使用邻接矩阵的好处是在边很多的时候可以节省空间，可以方便的加上边的权重信息（对应位置的值为2，3等等），也可以利用矩阵的结构，方便的进行并行运算（对机器学习来说非常重要）。但也会存在一个问题，即图很稀疏的时候（边很少），会存在大量的0值，浪费空间，所幸常用的库都做了sparse matrix的各种实现，既节省空间，又保持了矩阵的形式。

一个节点的邻居可以表示为\(N(a)\)，是与该节点之间存在边的所有节点的集合。一个节点的度（degree）是这个节点邻居的个数，即\(card(N(a))\).

神经网络

神经网络可以看成是多层的加权求和运算，在各个层之间加入激活函数（一般是非线性函数，以提高模型的表示能力），可以写成：

$$ X_1 = activiation(W_0X_0) \\
X_2 = activiation(W_1X_1) \\
…\\
X_n = activiation(W_{n-1}X_{n-1}) \\
Y = output_transformation(W_nX_n) $$

可以使用训练数据集来训练神经网络，也就是获得一组能反应训练集的特征的权重\(W_{0~n)\)，这样可以用于预测。为优化权重使用梯度下降算法。此外还有很多tricks，比如dropout。

GNN

GNN可以看作是对每一个节点分别使用同一个神经网络来获得这个节点的输出值。在神经网络的每一层里，用该节点自身的邻居的状态来更新该节点的状态，最终状态则是每个节点的输出值。如果用于图的分类问题，可以对全部节点的输出值进行聚合，得到最终的结果。

对每一层的运算过程我们可以抽象成两步：聚集（aggregate）和合并（combine）。对于一个有\(n\)个节点的图，我们将图的邻接矩阵记为\(\Lambda\in \mathbb N^{n \times n}\)，\(t\)层的各个节点的状态记为\(H \in \mathbb N^{n \times d_t}\)，每个节点的状态可能有多个维度，则这两步可以写成：

$$ aggregation: Z_t = \Lambda H_{t-1} combine: H_t = \mathcal C_t(Z_t) $$

其中\(\mathcal C_t\)是一个合并方程，对\(Z_t\)的每一行用一个权重矩阵\(W_t \in \mathbb N^{d_{t-1} \times d_t}\)相乘，将状态矩阵转化到新的维度\(H_t \in \mathbb N^{n \times d_t}\)。将所有的步骤合并起来，并在最后加入一个readout function，整个网络可以写成：

$$ f(\Lambda, H_0) = g(H_T(\Lambda, H_{T-1}(\Lambda, H_{T-2}(\Lambda, … H_1(\Lambda, H_0))))) $$

输入一个邻接矩阵和初始状态，输出一个预测值，当然也可以去掉readout一步，获得每个节点的状态\(H_T\)作为输出。