【Graph Neural Network 图神经网络】1.Recurrent Graph Neural Network 循环图神经网络

图神经网络概述

神经网络的成功推动了模式识别和数据挖掘的研究，产生了若干种端到端的深度学习方法：卷积神经网络CNN、循环神经网络RNN、自动编码器。其中卷积神经网络CNN能够利用图像数据的平移不变、局部连通和可组合，提取与整个数据集共享的局部有意义的特征，以进行各种图像分析任务。
但是在应用场景中依然有大量的数据以图Graph的形式表示，例如电子商务中的用户与产品的交互、化学中的分子结构、引文网络中的论文关系等。因为图结构可能是不规则的，图中的节点可能具有不同数量的邻居，图中实例彼此关联不独立，所以现有方法难以满足图数据的需求。
如下图所示，左边是图像的二维卷积，其中每个像素都被视为一个节点，邻居是有序且有固定大小的；右边是图卷积，简单卷积方案是求红色节点及其邻居节点特征的加权平均值。所以可以说，在卷积操作中，图像是图的一种特殊情况。

图/网络嵌入vs图神经网络

图/网络嵌入（Embedding）和图神经网络（GNN）是不同的概念，也密切相关。
Embedding主要是通过一些基于因子分解（Factorerization）、随机游走（Random Walk）或者深度学习的方法，将图节点转换成适合于现有机器学习模型的低维向量表示；GNN是一种深度学习模型，旨在设计一种学习机制，以端到端的方式解决图相关的节点分类、链路预测等问题。
所以，GNN是一个为多种任务而设计的神经网络模型，而Embedding则涵盖了针对同一任务的多种方法。两者是一种相交的关系：GNN是进行Embedding的多种方法之一，Embedding是GNN可以完成的多种任务之一。

循环图神经网络

循环图神经网络(RecGNNs)是图神经网络的先驱。它们运用了类似RNN的思想，在图中的节点上递归地应用相同的参数来提取高级节点表示。由于受到计算能力的限制，早期的研究主要集中在有向无环图。

GNN*

Scarselli等人提出了一种图神经网络模型(GNN*，因为与GNN同名避免混淆命名为GNN*)，该模型既适用于图应用又适用于节点应用，将这两个现有应用模型统一为一个通用框架。 GNN*是循环神经网络和随机游走模型的扩展，并保持了它们的特性：扩展了循环神经网络，因为它可以处理多类别的图，包括循环图，有向图和无向图，并且无需任何预处理即可处理以节点为中心的应用。 该方法通过引入学习算法并扩大可建模的过程类别来扩展随机游走理论。

模型

在图中，节点表示对象或概念，边表示关系。而每个对象/概念都有它的功能与相关定义。因此，我们可以基于领域中包含的信息将状态$x_n$附加到每个节点$n$，成为了节点$n$的一种概念的表示，也可被用于生成输出$o_n$（即概念的输出）。
$f_w$是一个参数函数，称为局部转移函数，它表示节点$n$对周围邻居的依赖性，而$g_w$是描述输出生成方式的局部输出函数，具体定义如下：
$$x_n=f_w(l_n,l_{co[n]},x_{ne[n]},l_{ne[n]})$$$$o_n=g_w(x_n,l_n)$$
其中$l_n$是节点$n$的标签，$l_{co[n]}$是它所有边的标签，$x_{ne[n]}$是它邻居的状态，$l_{ne[n]}$是它邻居的标签。

状态计算

基于信息扩散机制，GNN*通过递归交换邻域信息来更新节点状态，直到达到稳定的均衡状态，机制类似循环神经网络RNN。依据前文的模型定义，通过迭代计算状态和输出的定义如下：
$$x_n(t+1)=f_w(l_n,l_{co[n]},x_{ne[n]}(t),l_{ne[n]})$$$$o_n(t)=g_w(x_n(t),l_n)$$
其中所描述的计算可解释为由计算$f_w$和$g_w$的单元组成的网络，称为编码网络（encoding network）。为了构建编码网络，可用函数$f_w$的计算单元替换图的每个节点。每个单元存储节点$n$的当前状态$x_n(t)$，并在激活时用节点标签和附近存储的信息来计算新状态$x_n(t+1)$，单元的反复激活产生了上式所描述的行为。节点的输出由另一个实现$g_w$的单元产生。

学习算法

若$F_w$收缩，依据Banach不动点定理，有定点解：$$x=F_w(x,l)$$$$o=G_w(x,l)$$
模型的学习算法基于梯度迭代策略，由以下几步组成：

1. 状态$x_n(t)$由上文的等式迭代更新，直到它们接近方程式的定点解：$x(T)=x$
2. 计算梯度$\frac{{\partial }_{e_w}(T)}{{\partial }_w}$
3. 根据梯度更新参数$w$

在步骤1中需要注意：通过设置$f_w$为收缩映射可确保收敛到定点；步骤3在传统的梯度下降框架中进行，时间反向传播包括在按时间展开的分层网络上执行传统的反向传播，以计算时间T上损失函数相对于所有$f_w$和$g_w$实例的梯度，然后求和获得总梯度。

整体来说学习过程与经典RNN类似，所以在此不多展开。

Gated Graph Neural Networks(GG-NN)

相比于GNN*，GG-NN引入了GRU(Gate Recurrent Unit)，并以此为基础构建了空间域的消息传递模型。

GRU

GRU是循环神经网络LSTM的变体，将LSTM中的遗忘门（Forget gate）/输入门（Input gate）/输出门（Output gate）替换为重置门（Reset gate）/更新门（Update gate），相比于经典RNN它可以处理长时记忆，相比于LSTM它参数少训练速度快。GRU的单元结构和状态更新公式如下：

重置门是用来决定要忘记多少过去的信息的门；更新门类似于LSTM的遗忘和输入门，控制当前时刻的隐藏层输出$h_t$需要保留多少之前的隐藏层信息，若$z_t$接近1相当于我们把之前的隐藏层信息拷贝到当前时刻，可以学习长距离依赖。
一般来说那些具有短距离依赖的单元Reset gate比较活跃（如果$r_t$为1，而$z_t$为0 那么相当于变成了一个标准的RNN，能处理短距离依赖），具有长距离依赖的单元Update gate比较活跃。

节点注释

GG-NN相比于GNN另一个变化是节点表示的更新次数固定为$T$，所以GG-NN并不能保证图的最终状态会到达固定点。由于更新次数$T$变成了固定值，因此GG-NN可以直接使用BPTT算法来进行梯度的计算。
在GNN中，初始化节点表示没有意义，因为收缩映射约束确保了固定点与初始化无关。 GG-NN不再是这种情况，它使我们可以将节点标签合并为额外输入。 为了将这些用作输入的节点标签与之前介绍的节点标签区分开，我们称它们为节点注释（node annotation），并使用向量$x$来表示这些注释。
为了说明如何使用节点注释，考虑一个示例任务，即训练一个图神经网络来预测给定图上的节点$s$是否可以到达节点$t$。对于这个任务，有两个与问题相关的特殊节点，$s$和$t$。为了将这些节点标记为特殊节点，给它们一个初始的节点注释。节点$s$被注释为$x_s=[1,0{]}^T$，节点$t$被注释为$x_t=[0,1{]}^T$，其他节点被注释为$x_v=[0,0{]}^T$。然后，我们使用节点注释$x_v$对节点状态向量$h_v^{(1)}$进行初始化，当$h_v^{(1)}$的维度大于$x_v$时，使用0将剩下的维度补齐。
在可达性示例中，传播模型很容易学习将节点注释传播到所有可到达节点。例如通过将与前向边缘关联的传播矩阵设置为$\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]$，这将导致节点表示的第一维沿着边向前传播，最终导致从$s$到达的所有节点的表示的第一维被设置为1。然后，输出分类器可以查看节点的表示向量前两维中是否有非零项判断是否可由$s$到达。
以上示例如下图所示，(a)为图结构，(b)为展开的一步传播，（c)为循环矩阵，相当于把邻接矩阵中的1替换为对应的传播矩阵。

传播模型

传播过程可表示为：

其中，$A$表示图中节点与其他节点的连接关系（ $A$可以视作将连接矩阵的每一个“1”元素替换为$D\ast D$的传播矩阵得到）。在大多数情况下，是比较稀疏的矩阵，而且，在同一类型的边上，参数是共享的。$A_v$是$A$的一个子矩阵，对应于$A$中与节点$v$有关的列。式（1）是一个初始化步骤，用于将节点标注复制到节点状态向量中，其余部分使用0补齐。式（2）则用于不同节点之间的信息传播，这些信息传播要受到图中边的限制(包括是否有边、边的方向以及边的类型)。$a_v^{(t)}$包含了每个方向上的激活。其他的公式都是GRU单元的更新参数：$z$与$r$分别表示更新门与重置门，$\sigma ()$为sigmoid函数，$⨀$表示逐元素相乘。

输出模型

根据任务的不同，GG-NN可以有多种不同形式的输出。
当GG-NN用于节点选择（node selection）任务时，对于每个节点$v$都需要有一个输出：
若对于图级（graph-level）输出，可以定义一个图的表示向量：

其中，$\sigma ()$相当于一个soft attention机制，用于决定哪个节点与当前的任务有关。 $i$与$j$都是神经网络，其输入是$h_v^{(T)}$与$x_v$的连接，输出是实值向量。$tanh$函数也可以被替换为恒等变换。

参考文献

1. Scarselli, F., Gori, M., Ah Chung Tsoi, Hagenbuchner, M., Monfardini, G., 2009. The Graph Neural Network Model. IEEE Trans. Neural Netw. 20, 61–80.
2. Li, Y., Tarlow, D., Brockschmidt, M., Zemel, R., 2017. Gated Graph Sequence Neural Networks. arXiv:1511.05493.
3. 《Gated Graph Sequence Neural Networks》阅读笔记