图神经网络 Graph Neural Network (GNN)

传统的神经网络比较适合用于欧式空间的数据，而图神经网络 GNN 可以把神经网络用在图结构 (Graph) 中。图神经网络的种类很多，包括图卷积网络 GCN、图注意力网络 GAT、图自编码器 GAE 等。本文介绍最早被提出的图神经网络 (Graph Neural Network) GNN。

1.相关概念

之前的文章介绍过图卷积网络 GCN 和图注意力网络 GAT，其中 GCN 是 2016 年被提出的，GAT 是 2018 年提出的。本文介绍最早期的图神经网络 Graph Neural Network，简称 GNN。GNN 2009 年已经出现了，发表在论文《The graph neural network model》中。

1.1 graph_focused 和 node_focused

图领域的应用通常分为两类：graph_focused 和 node_focused。graph_focused 更关注于整个图结构，对整个图结构进行预测；node_focused 会关注节点的信息，可以进行节点的预测。

node_focused 可以理解为一个函数 τ，将图 G 和节点 n 转化为欧式空间中的一个 m 维向量：

node_focused

graph_focused 不关注于具体的节点 n，只需要得到图 G 的向量 (包含整个图 G 的信息)，因此函数 τ 可以改为：

graph_focused

下图展示了graph_focused 和 node_focused 的应用。图 (a) 为化学分子结构，需要预测分子结构对人体是否有害，则使用 graph_focused 的方法判断整个分子结构是否有害，而不用判断具体某个原子的有害性。图 (b) 是一个城堡图片，判断图中每一个节点是否属于城堡内部 (即黑点)，此时需要得到每一个节点的特征，并预测节点的类别，属于 node_focused。图 (c) 是网页连接结构，可以通过 node_focused 判断每一个网页的类型。

graph_focused 和 node_focused 的应用

1.2 positional graph 和 nonpositional graph

GNN 可以用于 positional graph 和 nonpositional graph。nonpositional graph 是指节点的邻居节点是没有顺序关系的，即可以随意排列，这种 graph 比较常见。 而 positional graph 是指对于一个节点 n，需要为其所有邻居指定一个独一无二的整数位置，位置用 injective function 计算，如下公式所示：

positional 计算 (injective function)

可以理解为 nonpositional graph 不区分节点的邻居，对于所有邻居采用相同的方法计算。而 positional graph 会考虑邻居的具体位置 (即 position)。

1.3 数学符号

下面是 GNN 中用到的一些符号含义：

符号含义

2.GNN 模型

2.1 传播和输出模型

在图结构中，一个节点可以表示一个对象或概念，而边可以表示节点之间的关系。GNN 用一个状态向量 xn 表示节点 n 的状态，节点 n 的状态需要用四个部分的向量进行计算：节点 n 的特征向量、邻居节点的特征向量、邻居节点的状态向量、边 (与 n 相连) 的特征向量。如下图所示：

节点 1 的状态向量 x1 计算方法

GNN 计算的公式主要包括传播和输出两个部分。传播部分主要是用 transition function f 将邻居节点和边的信息结合在一起，得到当前节点的状态向量。输出部分用 output function o 将节点的特征和状态向量转为输出向量。transition function 和 output function 如下面的公式：

传播公式和输出公式

对于 positional graph，在使用 transition function 时，需要把邻居节点的位置信息也包含进来。例如可以将邻居节点的特征 l_ne[n]、状态 x_ne[n] 和边的特征 l_co[n] 按照 position 的顺序排列，然后还需要进行 pad，把不存在的邻居节点的位置置为空值。

对于 nonpositional graph，可以将 transition function 改成下面的形式，即对于所有邻居采用相同的方式处理，最后再相加。

nonpositional 传播公式

2.2 迭代计算

GNN 通过迭代计算节点的状态 x，如下所示：

状态向量迭代计算公式

GNN 整体结构如下图所示：

GNN 整体结构

2.3 GNN 优化

GNN 中利用了巴拿赫不动点定理(Banach’s Fixed Point Theorem)，假设 transition function 是压缩映射函数 (contraction map)，从而保证节点的状态向量 x 最终收敛到一个不动点。

为了确保 transition function f 是一个压缩映射，GNN 在 f 对 x 的偏导数矩阵中加上了惩罚项。最后再通过梯度下降学习模型的参数

3.参考文献

The graph neural network model