Question

1. 许多实际应用都建立在图结构数据graph-structured data 之上，因此我们经常希望执行以 graph 为输入的机器学习任务。解决该问题的标准方法包括：设计关于输入图的自定义的特征工程feature engineering、graph kernel、以及根据图上的随机游走来定义 graph feature 的方法。与论文《Gated Graph Sequence Neural Networks》的目标更密切相关的是在图上学习特征的方法，包括图神经网络 Graph Neural Networks、谱网络 spectral networks、以及最近的用于学习化学分子 graph representation 来执行分类的 graph fingerprint 的工作。

   论文 《Gated Graph Sequence Neural Networks》的主要贡献是输出序列的图神经网络的扩展。之前的用于图结构输入的 feature learning 的工作主要聚焦于在产生单一输出的模型上，例如 graph-level 分类，但是 graph input 的许多问题都需要输出序列。例如，图上的 path、具有所需属性的 graph nodes 的枚举。作者觉得现有的 graph feature learning 工作不适合这个问题。论文的 motivating application 来自于程序验证 program verification ，该应用需要输出逻辑公式，作者将其表述为序列输出sequential output问题。

   论文的第二个贡献是：强调图神经网络（以及作者在这里开发的进一步扩展）是一类广泛有用的神经网络模型，适用于当前该领域面临的很多问题。

   图上的 feature learning 有两种 setting：

   • 学习输入图input graph的 representation。
   • 在产生一系列输出的过程中学习内部状态internal state的 representation。

   在这里，第一种 setting 是通过之前关于图神经网络的工作来实现的。作者对该框架进行了一些小的修改，包括将其更改为使用围绕 RNN 的现代实践。

   第二种 setting 很重要，因为我们需要图结构问题的、不仅仅是单个分类的输出。在这些情况下，挑战在于如何学习图上的特征，从而编码已经产生的部分输出序列（例如，如果是输出 path，那么就是到目前为止的 path）、以及仍然需要产生的部分输出序列（例如，剩余的 path）。论文将展示 GNN 框架如何适配这些 setting，从而产生一种新的、graph-based 的神经网络模型，作者称之为 Gated Graph Sequence Neural Networks: GGS-NN 。

   论文在 bAbI 任务、和阐明模型能力的 graph algorithm learning 任务的实验中说明这个通用模型的各个方面。然后作者提出一个 application 来验证计算机程序。当试图证明诸如内存安全（即，程序中不存在空指针解引用）等属性时，一个核心问题是找到程序中使用的数据结构的数学描述。遵循 《Learning to decipher the heap for program verification》 ，作者将其表述为一个机器学习问题，其中论文将学习从一组输入图（代表内存状态）映射到已实例化的数据结构的逻辑描述 logical description 。《Learning to decipher the heap for program verification》 依赖于大量的手工设计的特征，而论文表明该系统可以用 GGs-NN 来替代，而不会降低准确性。

2. 相关工作：

   • 最密切相关的工作是 GNN，我们在文中详细讨论。另一个密切相关的模型是 《Neural network for graphs: A contextual constructive approach》，它与 GNN 的主要区别在于输出模型。GNN 已在多个领域得到应用，但它似乎并未在 ICLR 社区中广泛使用。我们在这里的部分目标是将 GNN 宣传为一种有用的、且有趣的神经网络变体。

   • 我们从 GNN 到 GG-NN 的适配，与 《Parameter learning with truncated message-passing》 到 《Empirical risk minimization of graphical model parameters given approximate inference, decoding, and model structure》 在结构化预测 setting 中的工作之间可以进行类比。信念传播 belief propagation （必须运行到接近收敛才能获得良好的梯度）被替代为截断的信念传播更新truncated belief propagation updates ，然后对模型进行训练使得 truncated iteration 在固定数量的迭代之后产生良好的结果。类似地，RNN 扩展到 Tree LSTM ，类似于我们在 GG-NN 中使用 GRU 更新而不是标准的 GNN 递归，目的是改善信息在图结构中的长期传播 long-term propagation 。

   • 本文所表达的将特定问题的神经网络组装assembling成学习组件 learned components 的思想具有悠久的历史，至少可以追溯到 1988 年的《Representing part-whole hierarchies in connectionist networks》 关于根据一个 family tree 结构来组装神经网络的工作，以便预测人与人之间的关系。类似的思想出现在 《Neural methods for non-standard data》 和 《From machine learning to machine reasoning》 中。

   • graph kernel 可用于具有图结构输入的各种 kernel-based learning 任务，但是我们没有发现关于学习 kernel 并且输出序列的工作。《Deepwalk: Online learning of social representations 》 通过在图上进行随机游走将图转换为序列，然后使用 sequence-based 方法来学习 node embedding 。《Supervised neural networks for the classification of structures》 将图映射到 graph vector，然后使用一个 output neural network 进行分类。

     有几种模型利用图结构上 node representation 的类似的propagation 。

     • 《Spectral networks and locally connected networks on graphs》 将卷积推广到图结构。他们的工作与 GNN 之间的差异类似于卷积网络和循环网络之间的差异。
     • 《Convolutional networks on graphs for learning molecular fingerprints》 也考虑了对图的类卷积convolutional like 操作，构建了一个成功的 graph feature 的可学习learnable、可微differentiable的变体。
     • 《Deep architectures and deep learning in chemoinformatics: the prediction of aqueous solubility for drug-like molecules》 将任意无向图转换为许多具有不同方向的不同 DAG ，然后将 node representation 向内传播到每个 root ，并训练许多模型的一个 ensemble 。

     在上述所有内容中，重点是 one-step 问题。

   • GNN 和我们的扩展具有许多与指针网络 pointer network （《Pointer networks》）相同的理想特性。当使用节点选择的输出层node selection output layer时，可以选择输入中的节点作为输出。有两个主要区别：

     • 首先，在 GNN 中，图结构是显式的，这使得模型不太通用，但可能提供更强的泛化能力。
     • 其次，指针网络要求每个节点都具有属性（如，空间中的位置），而 GNN 可以表达仅由它们在图中的位置所定义的节点，这使得 GNN 更加通用。

   • GGS-NN 在两个方面与 soft alignment and attentional models 相关：

     • 首先，${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\tanh (\sum _{v\in \mathcal{V}}\sigma \left(g_1({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{x}}}_v)\right)\odot \tanh \left(g_2({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{x}}}_v)\right))$$ \mathbf{\vec h}_\mathcal G = \tanh\left(\sum_{v\in \mathcal V}\sigma\left(g_1\left(\mathbf{\vec h}_v^{(T)},\mathbf{\vec x}_v\right)\right)\odot \tanh\left( g_2\left(\mathbf{\vec h}_v^{(T)},\mathbf{\vec x}_v\right)\right)\right) $ 中的 graph representation 使用上下文将注意力集中在哪些节点对当前决策很重要。
     • 其次，在程序验证示例program verification example 中的节点注解 node annotation 会跟踪到目前为止已经解释了哪些节点，这提供了一种明确的机制来确保输入中的每个节点都已在producing an output 的序列中使用。

6.1 模型

6.1.1 GNN 回顾

1. GNN 是根据图结构$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G=(\mathcal V, \mathcal E) $ 定义的通用神经网络架构，$\mathcal{V}$$ \mathcal V $ 为节点集合，$\mathcal{E}$$ \mathcal E $ 为边集合，其中边$e=(v,v^{\prime })\in \mathcal{V}\times \mathcal{V}$$ e=(v,v^\prime)\in \mathcal V\times \mathcal V $ 为节点 pair 对。我们聚焦于有向图，因此$(v,v^{\prime })$$ (v,v^\prime) $ 代表一条有向边$v\to v^{\prime }$$ v\rightarrow v^\prime $ ，但是我们注意到 GNN 框架可以很容易地适配无向图。

   节点$v$$ v $ 的 node embedding 记做${\overrightarrow{\mathbf{h}}}_v\in {\mathbb{R}}^D$$ \mathbf{\vec h}_v\in \mathbb R^D $ 。图可能包含 node label ，其中节点$v$$ v $ 的 node label 为${\overrightarrow{l}}_v\in {\mathbb{R}}^{n_v}$$ \vec l _v \in \mathbb R^{n_v} $ ，$n_v$$ n_v $ 为节点标签的维度。图也可能包含 edge label，其中边$e$$ e $ 的 edge label 为${\overrightarrow{l}}_e\in {\mathbb{R}}^{n_E}$$ \vec l_e\in \mathbb R^{n_E} $ ，$n_E$$ n_E $ 为边标签的维度。

   在原始 GNN 论文中状态向量记作${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ ，为了和 RNN 保持一致，这里记作${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 。

   定义节点集合$\mathcal{S}$$ \mathcal S $ 的 node embedding 集合为${\overrightarrow{\mathbf{h}}}_{\mathcal{S}}=\{{\overrightarrow{\mathbf{h}}}_v\mid v\in \mathcal{S}\}$$ \mathbf{\vec h}_\mathcal S = \left\{\mathbf{\vec h}_v\mid v\in \mathcal S\right\} $ 。定义边集合$\mathcal{S}$$ \mathcal S $ 的 edge label 集合为${\overrightarrow{l}}_{\mathcal{S}}=\{{\overrightarrow{l}}_e\mid e\in \mathcal{S}\}$$ \vec l_\mathcal S = \left\{\vec l_e\mid e\in \mathcal S\right\} $ 。

   定义$\text{IN}(v)=\{v^{\prime }\mid (v^{\prime },v)\in \mathcal{E}\}$$ \text{IN}(v) = \left\{v^\prime\mid (v^\prime,v)\in \mathcal E\right\} $ 为节点$v$$ v $ 的前驱节点predecessor node 集合。定义$\text{OUT}(v)=\{v^{\prime }\mid (v,v^{\prime })\in \mathcal{E}\}$$ \text{OUT}(v) = \left\{v^\prime \mid (v,v^\prime)\in \mathcal E\right\} $ 为节点$v$$ v $ 的后继节点successor node 集合。节点$v$$ v $ 的邻居集合定义为$\text{NBR}(v)=\text{IN}(v)\cup \text{OUT}(v)$$ \text{NBR}(v) = \text{IN}(v)\cup \text{OUT}(v) $ 。节点$v$$ v $ 的所有边（包括 incoming edge 和 outgoing edge）定义为$\text{Co}(v)=\{(v^{\prime },v^{\prime \prime })\in \mathcal{E}\mid v=v^{\prime }\text{or}v=v^{\prime \prime }\}$$ \text{Co}(v) = \left\{(v^\prime,v^{\prime\prime})\in \mathcal E\mid v=v^\prime \text{ or } v = v^{\prime\prime}\right\} $ 。

   在原始 GNN 论文中，邻居节点仅仅考虑前驱节点集合，即指向节点$v$$ v $ 的节点集合。因此，原始 GNN 论文仅考虑入边。

2. GNN 通过两个步骤来得到输出：

   • 首先通过转移函数transition function 得到每个节点的representation${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ ，即 propagation step，其中转移函数也被称作传播模型propagation model 。
   • 然后通过输出函数 output function 得到每个节点的输出${\overrightarrow{\mathbf{o}}}_v$$ \mathbf{\vec o}_v $ ，其中输出函数也被称作输出模型 output model 。

   该系统是端到端可微的，因此可以利用基于梯度的优化算法来学习参数。

3. 传播模型：我们通过一个迭代过程来传播节点的状态。

   节点的初始状态${\mathbf{h}}_v^{(1)}$$ \mathbf h_v^{(1)} $ 可以为任意值，然后每个节点的状态可以根据以下方程来更新直到收敛，其中$t$$ t $ 表示时间步：

   $${\overrightarrow{\mathbf{h}}}_v^{(t)}=f_w({\overrightarrow{l}}_v,{\overrightarrow{l}}_{\text{CO}(v)},{\overrightarrow{l}}_{\text{NBR}(v)},{\overrightarrow{\mathbf{h}}}_{\text{NBR}(v)}^{(t-1)})$$

   其中$f_w(\cdot )$$ f_w(\cdot) $ 为转移函数，它有若干个变种，包括：non-positional form 和posistional form、线性和非线性。 原始 GNN 论文建议按照 non-positional form 进行分解：

   $$f_w({\overrightarrow{l}}_v,{\overrightarrow{l}}_{\text{CO}(v)},{\overrightarrow{l}}_{\text{NER}(v)},{\overrightarrow{\mathbf{h}}}_{\text{NBR}(v)}^{(t-1)})=\sum _{v^{\prime }\in \text{IN}(v)}{h}_w({\overrightarrow{l}}_v,{\overrightarrow{l}}_{v^{\prime },v},{\overrightarrow{l}}_{v^{\prime }},{\overrightarrow{\mathbf{h}}}_{v^{\prime }}^{(t-1)})+\sum _{v^{\prime }\in \text{OUT}(v)}{h}_w({\overrightarrow{l}}_v,{\overrightarrow{l}}_{v,v^{\prime }},{\overrightarrow{l}}_{v^{\prime }},{\overrightarrow{\mathbf{h}}}_{v^{\prime }}^{(t-1)})$$

   其中$h_w(\cdot )$$ h_w(\cdot) $ 可以为线性函数，或者为一个神经网络。当$h_w(\cdot )$$ h_w(\cdot) $ 为线性函数时，$h_w(\cdot )$$ h_w(\cdot) $ 为：

   $$h_w({\overrightarrow{l}}_v,{\overrightarrow{l}}_{v^{\prime },v},{\overrightarrow{l}}_{v^{\prime }},{\overrightarrow{\mathbf{h}}}_{v^{\prime }}^{(t)})={\mathbf{A}}^{(v^{\prime },v)}{\overrightarrow{\mathbf{h}}}_{v^{\prime }}^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(v^{\prime },v)}$$

   其中${\overrightarrow{\mathbf{b}}}^{(v^{\prime },v)}\in {\mathbb{R}}^D$$ \mathbf{\vec b}^{(v^\prime,v)}\in \mathbb R^D $ 和矩阵${\mathbf{A}}^{(v^{\prime },v)}\in {\mathbb{R}}^{D\times D}$$ \mathbf A^{(v^\prime,v)}\in \mathbb R^{D\times D} $ 分别由两个前馈神经网络的输出来定义，这两个前馈神经网络的参数对应于 GNN 的参数。

4. 输出模型：模型输出为${\overrightarrow{\mathbf{o}}}_v=g_w({\overrightarrow{\mathbf{h}}}_v,{\overrightarrow{l}}_v)$$ \mathbf{\vec o}_v = g_w\left(\mathbf{\vec h}_v, \vec l_v\right) $ 。其中$g_w$$ g_w $ 可以为线性的，也可以使用神经网络；${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 为传播模型最后一次迭代的结果${\overrightarrow{\mathbf{h}}}_v^{(T)}$$ \mathbf{\vec h}_v^{(T)} $ ，其中$T$$ T $ 为最大迭代次数。

5. 为处理 graph-level 任务，GNN 建议创建一个虚拟的超级节点super node，该超级节点通过特殊类型的边连接到所有其它节点，因此可以使用 node-level 相同的方式来处理 graph-level 任务。

6. GNN 模型是通过 Almeida-Pineda 算法来训练的，该算法首先执行传播过程并收敛，然后基于收敛的状态来计算梯度。其优点是我们不需要存储传播过程的中间状态（只需要存储传播过程的最终状态）来计算梯度，缺点是必须限制参数从而使得传播过程是收缩映射contraction map。

   转移函数是收缩映射是模型收敛的必要条件，这可能会限制模型的表达能力。当$f_w(\cdot )$$ f_w(\cdot) $ 为神经网络模型时，可以通过对网络参数的雅可比行列式的$L_1$$ L_1 $ 范数施加约束来实现收缩映射的条件：

   $${\mathcal{L}}_w=\sum _{i=1}^p\sum _{j=1}^{q_i}{\Vert {\overrightarrow{\mathbf{t}}}_{i,j}-{\phi }_w(G_i,v_{i,j})\Vert }_2^2+\beta L\left({\Vert \frac{\partial F_w}{\partial \overrightarrow{\mathbf{x}}}\Vert }_1\right)$$

   其中$p$$ p $ 表示图的个数，$q_i$$ q_i $ 表示第$i$$ i $ 个图的节点数量，${\overrightarrow{\mathbf{t}}}_{i,j}$$ \mathbf{\vec t}_{i,j} $ 为第$i$$ i $ 个图、第$j$$ j $ 个节点的监督信息，${\varphi }_w(G_i,v_{i,j})$$ \phi_w(G_i,v_{i,j}) $ 为第$i$$ i $ 个图、第$j$$ j $ 个节点的预测，$L(\cdot )$$ L(\cdot) $ 为罚项：

   $$\begin{array}{c}L(y)=\{\begin{array}{ll}|y-\mu |& ,\text{if}y>\mu \\ 0& ,\text{else}\end{array}\end{array}$$

   超参数$\mu \in (0,1)$$ \mu \in (0,1) $ 定义了针对转移函数的约束。

7. 事实上一个收缩映射很难在图上进行长距离的信息传播。

   考虑一个包含$N$$ N $ 节点的环形图，图中的节点首位相连。假设每个节点的隐状态的维度为1 ，即隐状态为标量。假设$h_w(\cdot )$$ h_w(\cdot) $ 为线性函数。为简化讨论，我们忽略了所有的节点标签信息向量、边标签信息向量，并且只考虑入边而未考虑出边。

   在每个时间步$t$$ t $ ，节点$v$$ v $ 的隐单元为：$h_v^{(t)}=m_v\times h_{v-1}^{(t-1)}+b_v$$ h_v^{(t)} = m_v\times h_{v-1}^{(t-1)} + b_v $ ，其中$m_v,b_v$$ m_v,b_v $ 为传播模型的参数。考虑到环形结构，我们认为：$v\le 0$$ v\le 0 $ 时有$h_v=h_{N+v}$$ h_v = h_{N+v} $ 。

   令${\overrightarrow{\mathbf{h}}}^{(t)}={[h_1^{(t)},\cdots ,h_N^{(t)}]}^{\mathrm{\top }},\overrightarrow{\mathbf{b}}={[b_1,\cdots ,b_N]}^{\mathrm{\top }}$$ \mathbf{\vec h}^{(t)} = \left[h_1^{(t)},\cdots,h_N^{(t)}\right]^\top, \mathbf{\vec b} = \left[b_1,\cdots,b_N\right]^\top $ ，令：

   $$\begin{array}{c}\mathbf{M}=\left[\begin{array}{cccccc}0& 0& 0& \cdots & 0& m_1\\ m_2& 0& 0& \cdots & 0& 0\\ 0& m_3& 0& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & m_N& 0\end{array}\right]\end{array}$$

   则有：${\overrightarrow{\mathbf{h}}}^{(t)}=\mathbf{M}{\overrightarrow{\mathbf{h}}}^{(t-1)}+\overrightarrow{\mathbf{b}}$$ \mathbf{\vec h}^{(t)} = \mathbf M\mathbf{\vec h}^{(t-1) } + \mathbf{\vec b} $ 。

   记$T\left({\overrightarrow{\mathbf{h}}}^{(t-1)}\right)=\mathbf{M}{\overrightarrow{\mathbf{h}}}^{(t-1)}+\overrightarrow{\mathbf{b}}$$ T\left(\mathbf{\vec h}^{(t-1)}\right) = \mathbf M\mathbf{\vec h}^{(t-1) } + \mathbf{\vec b} $ ，则$T(\cdot )$$ T(\cdot) $ 必须为收缩映射，则存在$\rho \le 1$$ \rho\le 1 $ 使得对于任意的$\overrightarrow{\mathbf{h}},{\overrightarrow{\mathbf{h}}}^{\prime }$$ \mathbf{\vec h},\mathbf{\vec h}^\prime $ ，满足:

   $$\Vert T\left(\overrightarrow{\mathbf{h}}\right)-T\left({\overrightarrow{\mathbf{h}}}^{\prime }\right)\Vert <\rho \Vert \overrightarrow{\mathbf{h}}-{\overrightarrow{\mathbf{h}}}^{\prime }\Vert$$

   即：

   $$\Vert \mathbf{M}(\overrightarrow{\mathbf{h}}-{\overrightarrow{\mathbf{h}}}^{\prime })\Vert <\rho \Vert \overrightarrow{\mathbf{h}}-{\overrightarrow{\mathbf{h}}}^{\prime }\Vert$$

   如果选择${\overrightarrow{\mathbf{h}}}^{\prime }=\overrightarrow{\mathbf{0}}$$ \mathbf{\vec h}^\prime = \mathbf{\vec 0} $ ，选择$\overrightarrow{\mathbf{h}}=(\underset{v-2}{\underbrace{0,0,\cdots ,0}},1,0,\cdots ,0{)}^{\mathrm{\top }}$$ \mathbf{\vec h} = (\underbrace{0,0,\cdots,0}_{v-2},1,0,\cdots,0)^\top $ （即除了位置$v-1$$ v-1 $ 为1、其它位置为零） ，则有$|m_v|<\rho$$ |m_v|\lt \rho $ 。

   扩展$h_v^{(t)}=m_v\times h_{v-1}^{(t-1)}+b_v$$ h_v^{(t)} = m_v\times h_{v-1}^{(t-1)} + b_v $ ，则有：

   $$\begin{array}{c}{h}_v^{(t)}=m_v\times h_{v-1}^{(t-1)}+b_v\\ =m_v(m_{v-1}{h}_{v-2}^{(t-2)}+b_{v-1})+b_v\\ =m_v{m}_{v-1}(m_{v-2}{h}_{v-2}^{(t-3)}+b_{v-2})+m_v{b}_{v-1}+b_v\\ =m_v{m}_{v-1}{m}_{v-2}{h}_{v-3}^{(t-3)}+m_v{m}_{v-1}{b}_{v-2}+m_v{b}_{v-1}+b_v\end{array}$$

   考虑到$|m_v|<\rho$$ |m_v|\lt \rho $ ，这意味着从节点$j\to j+1\to j+2\cdots \to v$$ j\rightarrow j+1 \rightarrow j+2\cdots \rightarrow v $ 传播的信息以指数型速度${\rho }^{\delta }$$ \rho^\delta $ 衰减，其中$\delta$$ \delta $ 为节点$j$$ j $ 到节点$v$$ v $ 的距离（这里$j$$ j $ 是$v$$ v $ 的上游节点）。因此 GNN 无法在图上进行长距离的信息传播。

8. 事实上，当$h_w(\cdot )$$ h_w(\cdot) $ 为非线性函数时，收缩映射也很难在图上进行长距离的信息传播。令

   $$h_v^{(t)}=\sigma (m_v\times h_{v-1}^{(t-1)}+b_v)$$

   其中$\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数。则有$T\left({\overrightarrow{\mathbf{h}}}^{(t-1)}\right)=\sigma (\mathbf{M}{\overrightarrow{\mathbf{h}}}^{(t-1)}+\overrightarrow{\mathbf{b}})$$ T\left(\mathbf{\vec h}^{(t-1)}\right) = \sigma\left(\mathbf M\mathbf{\vec h}^{(t-1) } + \mathbf{\vec b}\right) $ ，$T(\cdot )$$ T(\cdot) $ 为一个收缩映射。则存在$\rho \le 1$$ \rho\le 1 $ 使得对于任意的$\overrightarrow{\mathbf{h}},{\overrightarrow{\mathbf{h}}}^{\prime }$$ \mathbf{\vec h},\mathbf{\vec h}^\prime $ ，满足:

   $$\Vert T\left(\overrightarrow{\mathbf{h}}\right)-T\left({\overrightarrow{\mathbf{h}}}^{\prime }\right)\Vert <\rho \Vert \overrightarrow{\mathbf{h}}-{\overrightarrow{\mathbf{h}}}^{\prime }\Vert$$

   这意味着函数$T\left(\overrightarrow{\mathbf{h}}\right)$$ T\left(\mathbf{\vec h}\right) $ 的雅可比矩阵的每一项都必须满足：

   $$\left|\frac{\partial T_i}{\partial h_j}\right|<\rho ,\mathrm{\forall }i,\mathrm{\forall }j$$

   • 证明：考虑两个向量$\overrightarrow{\mathbf{h}},{\overrightarrow{\mathbf{h}}}^{\prime }$$ \mathbf{\vec h},\mathbf{\vec h}^{\prime} $ ，其中 ：

     $$\begin{array}{c}\overrightarrow{\mathbf{h}}=(h_1,\cdots ,h_{j-1},h_j,h_{j+1},\cdots ,h_N)\\ {\overrightarrow{\mathbf{h}}}^{\prime }=(h_1,\cdots ,h_{j-1},h_j+\mathrm{\Delta },h_{j+1},\cdots ,h_N)\end{array}$$

     则有$\Vert T_i\left(\overrightarrow{\mathbf{h}}\right)-T_i\left({\overrightarrow{\mathbf{h}}}^{\prime }\right)\Vert \le \Vert T\left(\overrightarrow{\mathbf{h}}\right)-T\left({\overrightarrow{\mathbf{h}}}^{\prime }\right)\Vert <\rho |\mathrm{\Delta }|$$ \left\|T_i\left(\mathbf{\vec h}\right) - T_i\left(\mathbf{\vec h}^\prime\right)\right\|\le \left\|T\left(\mathbf{\vec h}\right) - T\left(\mathbf{\vec h}^\prime\right)\right\| \lt \rho |\Delta| $ ，则有：

     $$\Vert \frac{T_i(h_1,\cdots ,h_{j-1},h_j,h_{j+1},\cdots ,h_N)-T_i(h_1,\cdots ,h_{j-1},h_j+\mathrm{\Delta },h_{j+1},\cdots ,h_N)}{\mathrm{\Delta }}\Vert <\rho$$

     其中$T_i\left(\overrightarrow{\mathbf{h}}\right)$$ T_i\left(\mathbf{\vec h}\right) $ 为$T\left(\overrightarrow{\mathbf{h}}\right)$$ T\left(\mathbf{\vec h}\right) $ 的第$i$$ i $ 个分量。

     当$\mathrm{\Delta }\to 0$$ \Delta\rightarrow 0 $ 时， 左侧等于$\left|\frac{\partial T_i}{\partial h_j}\right|$$ \left|\frac{\partial T_i}{\partial h_j}\right| $ ，因此得到结论$\left|\frac{\partial T_i}{\partial h_j}\right|<\rho ,\mathrm{\forall }i,\mathrm{\forall }j$$ \left|\frac{\partial T_i}{\partial h_j}\right|\lt \rho, \forall i, \forall j $ 。

   • 当$j=i-1$$ j= i-1 $ 时，有$\left|\frac{\partial T_i}{\partial h_{i-1}}\right|<\rho$$ \left|\frac{\partial T_i}{\partial h_{i-1}}\right| \lt \rho $ 。考虑到图为环状结构，因此对于$j\ne i-1$$ j\ne i-1 $ 的节点有$\frac{\partial T_i}{\partial h_j}=0$$ \frac{\partial T_i}{\partial h_j} = 0 $ 。

     考虑到时刻$t$$ t $ 的更新，则有：

     $$\left|\frac{\partial h_i^{(t)}}{\partial h_{i-1}^{(t-1)}}\right|<\rho$$

     现在考虑$h_1^{(1)}$$ h_1^{(1)} $ 如何影响$h_t^{(t)}$$ h_t^{(t)} $ 。考虑链式法则以及图的环状结构，则有：

     $$\begin{array}{c}\left|\frac{\partial h_t^{(t)}}{\partial h_1^{(1)}}\right|=|\frac{\partial h_t^{(t)}}{\partial h_{t-1}^{(t-1)}}\times \frac{\partial h_{t-1}^{(t-1)}}{\partial h_{t-2}^{(t-2)}}\times \cdots \times \frac{\partial h_2^{(2)}}{\partial h_1^{(1)}}|\\ =\left|\frac{\partial h_t^{(t)}}{\partial h_{t-1}^{(t-1)}}\right|\times \left|\frac{\partial h_{t-1}^{(t-1)}}{\partial h_{t-2}^{(t-2)}}\right|\times \cdots \times \left|\frac{\partial h_2^{(2)}}{\partial h_1^{(1)}}\right|<\rho \times \rho \times \cdots \times \rho ={\rho }^{t-1}\end{array}$$

     当$\rho <1$$ \rho \lt 1 $ 时，偏导数$\frac{\partial h_t^{(t)}}{\partial h_1^{(1)}}$$ \frac{\partial h_t^{(t)}}{\partial h_{1}^{(1)}} $ 随着$t$$ t $ 的增加指数级降低到0 。这意味着一个节点对另一个节点的影响将呈指数级衰减，因此 GNN 无法在图上进行长距离的信息传播。

     当$h_w(\cdot )$$ h_w(\cdot) $ 为线性函数时，前向传播的信息以指数型速度衰减；当$h_w(\cdot )$$ h_w(\cdot) $ 为非线性函数时，反向传播的信息以指数型速度衰减。

6.1.2 GG-NN 模型

1. 门控图神经网络 Gated Graph Neural Networks:GG-NN 对 GNN 进行修改，采用了门控循环单元GRU ，并对固定的$T$$ T $ 个时间步进行循环展开，并使用 back propagation through time: BPTT 算法来计算梯度。这比Almeida-Pineda 算法需要更多的内存，但是它消除了约束参数以确保收敛的必要性。我们还扩展了底层的 representation 和 output model 。

a. node annotation

1. 在 GNN 中节点状态的初始化值没有意义，因为不动点理论可以确保不动点独立于初始化值。但是在 GG-NN 模型中不再如此，节点的初始化状态可以作为额外的输入。为了区分节点的初始化状态和其它类型的节点标签信息，我们称初始化状态为节点的注解node annotation，以向量$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 来表示。

   节点的初始化状态可以视为节点的标签信息的一种。

   节点的注解向量就是后来广泛使用的 node feature vector 。

2. 注解向量的示例：对于给定的图，我们希望预测是否存在从节点$s$$ s $ 到节点$t$$ t $ 的路径。该任务存在任务相关的两个节点$s,t$$ s,t $ ，因此我们定义注解向量为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_v=\{\begin{array}{ll}(1,0{)}^{\mathrm{\top }},& v=s\\ (0,1{)}^{\mathrm{\top }},& v=t\\ (0,0{)}^{\mathrm{\top }},& \text{other}\end{array}\end{array}$$

   注解向量使得节点$s$$ s $ 被标记为任务的第一个输入参数，节点$t$$ t $ 被标记为任务的第二个输入参数。我们通过${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 来初始化状态向量${\overrightarrow{\mathbf{h}}}_v^{(1)}$$ \mathbf{\vec h}_v^{(1)} $ ：

   $${\overrightarrow{\mathbf{h}}}_v^{(1)}=[x_{v,0},x_{v,1},0,\cdots ,0{]}^{\mathrm{\top }}$$

   即：${\overrightarrow{\mathbf{h}}}_v^{(1)}$$ \mathbf{\vec h}_v^{(1)} $ 的前面两维为${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 、后面的维度填充为零。

   传播模型很容易学得将节点$s$$ s $ 的注解传播到任何$s$$ s $ 可达的节点。如，通过设置传播矩阵为：所有存在后向边的位置都为1 。这将使得${\overrightarrow{\mathbf{h}}}_s^{(1)}$$ \mathbf{\vec h}_s^{(1)} $ 的第一维沿着后向边进行复制，使得从节点$s$$ s $ 可达的所有节点的${\overrightarrow{\mathbf{h}}}_v^{(T)}$$ \mathbf{\vec h}_v^{(T)} $ 的第一维均为1 。

   最终查看是否存在某个节点的状态向量前两维为[1,1] ，即可判断从$s$$ s $ 是否可达节点$t$$ t $ 。

b.传播模型

1. 初始化状态向量：${\overrightarrow{\mathbf{h}}}_v^{(1)}={[{\overrightarrow{\mathbf{x}}}_v^{\mathrm{\top }},\overrightarrow{\mathbf{0}}]}^{\mathrm{\top }}\in {\mathbb{R}}^D$$ \mathbf{\vec h}_v^{(1)} = \left[\mathbf{\vec x}_v^\top,\mathbf{\vec 0}\right]^\top \in \mathbb R^D $ ，其中$D$$ D $ 为状态向量的维度。这一步将节点的注解信息拷贝到状态向量的前几个维度。

2. 信息传递：${\overrightarrow{\mathbf{a}}}_v^{(t)}={\mathbf{A}}_{v:}^{\mathrm{\top }}{[{\overrightarrow{\mathbf{h}}}_1^{(t-1)\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{h}}}_{|\mathcal{V}|}^{(t-1)\mathrm{\top }}]}^{\mathrm{\top }}+{\overrightarrow{\mathbf{b}}}_v$$ \mathbf{\vec a}_v^{(t)} = \mathbf A_{v:}^\top\left[\mathbf{\vec h}_1^{(t-1)\top},\cdots,\mathbf{\vec h}_{|\mathcal V|}^{(t-1)\top} \right]^\top+ \mathbf{\vec b}_v $ ，它包含所有方向的边的激活值。

   如下图所示 (a) 表示一个图，颜色表示不同的边类型（类型 B 和类型 C ）；(b) 表示展开的一个计算步；(c) 表示矩阵$\mathbf{A}$$ \mathbf A $ ，$B^{\prime }$$ B^\prime $ 表示$B$$ B $ 的反向边，采用不同的参数。

   $\mathbf{A}\in {\mathbb{R}}^{D|\mathcal{V}|\times 2D|\mathcal{V}|}$$ \mathbf A \in \mathbb R^{D|\mathcal V|\times 2D|\mathcal V|} $ 对应于图中的边，它确定图中的节点如何相互通信。$\mathbf{A}$$ \mathbf A $ 的稀疏结构sparsity structure和参数绑定parameter tying 如下图所示。$\mathbf{A}$$ \mathbf A $ 由${\mathbf{A}}^{(\text{out})}\in {\mathbb{R}}^{D|\mathcal{V}|\times D|\mathcal{V}|}$$ \mathbf A^{(\text{out})}\in \mathbb R^{D|\mathcal V|\times D|\mathcal V|} $ 和${\mathbf{A}}^{(\text{in})}\in {\mathbb{R}}^{D|\mathcal{V}|\times D|\mathcal{V}|}$$ \mathbf A^{(\text{in})}\in \mathbb R^{D|\mathcal V|\times D|\mathcal V|} $ 组成，这两个子矩阵（通常都是稀疏矩阵）的参数由边的方向和类型决定。

   ${\mathbf{A}}_{v:}\in {\mathbb{R}}^{D|\mathcal{V}|\times 2D}$$ \mathbf A_{v:}\in \mathbb R^{D|\mathcal V|\times 2D} $ 由${\mathbf{A}}^{(\text{out})},{\mathbf{A}}^{(\text{in})}$$ \mathbf A^{(\text{out})},\mathbf A^{(\text{in})} $ 对应于节点$v$$ v $ 的两列组成；${\overrightarrow{\mathbf{b}}}_v\in {\mathbb{R}}^{2D}$$ \mathbf{\vec b}_v \in \mathbb R^{2D} $ 。

   

3. GRU 更新状态：

   $$\begin{array}{c}{\overrightarrow{\mathbf{z}}}_v^{(t)}=\sigma ({\mathbf{W}}^z{\overrightarrow{\mathbf{a}}}_v^{(t)}+{\mathbf{U}}^z{\overrightarrow{\mathbf{h}}}_v^{(t-1)})\\ {\overrightarrow{\mathbf{r}}}_v^{(t)}=\sigma ({\mathbf{W}}^r{\overrightarrow{\mathbf{a}}}_v^{(t)}+{\mathbf{U}}^r{\overrightarrow{\mathbf{h}}}_v^{(t-1)})\\ \stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t)}}=\tanh (\mathbf{W}{\overrightarrow{\mathbf{a}}}_v^{(t)}+\mathbf{U}({\overrightarrow{\mathbf{r}}}_v^{(t)}\odot {\overrightarrow{\mathbf{h}}}_v^{(t-1)}))\\ {\overrightarrow{\mathbf{h}}}_v^{(t)}=(1-{\overrightarrow{\mathbf{z}}}_v^{(t)})\odot {\overrightarrow{\mathbf{h}}}_v^{(t-1)}+{\overrightarrow{\mathbf{z}}}_v^{(t)}\odot \stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t)}}\end{array}$$

   这里采用类似 GRU 的更新机制，基于节点的历史状态向量和所有边的激活值来更新当前状态。$\overrightarrow{\mathbf{z}}$$ \mathbf{\vec z} $ 为更新门，$\overrightarrow{\mathbf{r}}$$ \mathbf{\vec r} $ 为复位门，$\sigma (x)=1/(1+e^{-x})$$ \sigma(x) = 1/(1+e^{-x}) $ 为 sigmoid 函数，$\odot$$ \odot $ 为逐元素乘积。

   我们最初使用普通的 RNN 来进行状态更新，但是初步实验结论表明：GRU 形式的状态更新效果更好。

   更新时使用了当前节点的历史信息${\overrightarrow{\mathbf{h}}}_v^{(t-1)}$$ \mathbf{\vec h}_v^{(t-1)} $ 、以及邻域节点的信息${\overrightarrow{\mathbf{a}}}_v^{(t)}$$ \mathbf{\vec a}_v^{(t)} $ 。

   GG-NN 可以视为：以邻域聚合信息${\overrightarrow{\mathbf{a}}}_v^{(1)}$$ \mathbf{\vec a}_v^{(1)} $ 作为输入的 GRU 。

c. 输出模型

1. 我们希望在不同的情况下产生几种类型的 one-step 输出。

   • node-level 输出：对每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，计算${\overrightarrow{\mathbf{o}}}_v=g({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{x}}}_v)$$ \mathbf{\vec o}_v = g\left(\mathbf{\vec h}_v^{(T)}, \mathbf{\vec x}_v\right) $ 。然后可以对${\overrightarrow{\mathbf{o}}}_v$$ \mathbf{\vec o}_v $ 应用一个 softmax 函数来得到每个节点在各类别的得分。

   • graph-level 输出：定义graph-level 的 representation 向量为：

     $${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\tanh (\sum _{v\in \mathcal{V}}\sigma \left(g_1({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{x}}}_v)\right)\odot \tanh \left(g_2({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{x}}}_v)\right))$$

     其中：

     • $\sigma \left(g_1({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{x}}}_v)\right)$$ \sigma\left(g_1\left(\mathbf{\vec h}_v^{(T)},\mathbf{\vec x}_v\right)\right) $ 起到 soft attention 机制的作用，它决定哪些节点和当前的graph-level任务有关。$\sigma (\cdot )$$ \sigma(\cdot) $ 为 sigmoid 函数（ attention 系数取值是 0 ~ 1 之间）。
     • $g_1(\cdot ),g_2(\cdot )$$ g_1(\cdot),g_2(\cdot) $ 都是神经网络，它们拼接${\overrightarrow{\mathbf{h}}}_v^{(T)}$$ \mathbf{\vec h}_v^{(T)} $ 和${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 作为输入， 输出一个实值向量。
     • $\tanh (\cdot )$$ \tanh (\cdot) $ 函数也可以替换为恒等映射。

   注意：这里的 GG-NN 给出的是非序列输出，实际上 GG-NN 支持序列输出，这就是下面介绍的 GGS-NN 模型。

6.1.3 GGS-NN 模型

1. 门控图序列神经网络 Gated Graph Sequence Neural Networks :GGS-NN 使用若干个 GG-NN 网络依次作用从而生成序列输出${\overrightarrow{\mathbf{o}}}^{(1)},\cdots ,{\overrightarrow{\mathbf{o}}}^{(K)}$$ \mathbf{\vec o}^{(1)},\cdots, \mathbf{\vec o}^{(K)} $ 。在第$k$$ k $ 个输出：

   • 定义所有节点的注解向量组成矩阵${\mathbf{X}}^{(k)}={[{\overrightarrow{\mathbf{x}}}_1^{(k)},\cdots ,{\overrightarrow{\mathbf{x}}}_{|\mathcal{V}|}^{(k)}]}^{\mathrm{\top }}\in {\mathbb{R}}^{|\mathcal{V}|\times D_a}$$ \mathbf X^{(k)} = \left[\mathbf{\vec x}_1^{(k)},\cdots, \mathbf{\vec x}_{|\mathcal V|}^{(k)}\right]^\top\in \mathbb R^{|\mathcal V|\times D_a} $ ，其中$D_a$$ D_a $ 为注解向量的维度。

     定义所有节点的输出向量组成矩阵${\mathbf{O}}^{(k)}={[{\overrightarrow{\mathbf{o}}}_1^{(k)},\cdots ,{\overrightarrow{\mathbf{o}}}_{|\mathcal{V}|}^{(k)}]}^{\mathrm{\top }}\in {\mathbb{R}}^{|\mathcal{V}|\times D_o}$$ \mathbf O^{(k)} = \left[\mathbf{\vec o}_1^{(k)},\cdots,\mathbf{\vec o}_{|\mathcal V|}^{(k)}\right]^\top\in \mathbb R^{|\mathcal V|\times D_o} $ ，其中$D_o$$ D_o $ 为输出向量的维度。

   • 我们使用两个 GG-NN 网络${\mathcal{F}}_{\mathcal{O}}^{(k)}$$ \mathcal F_{\mathcal O}^{(k)} $ 和${\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal X}^{(k)} $ ，其中${\mathcal{F}}_{\mathcal{O}}^{(k)}$$ \mathcal F_{\mathcal O}^{(k)} $ 用于从${\mathbf{X}}^{(k)}$$ \mathbf X^{(k)} $ 中预测${\mathbf{O}}^{(k)}$$ \mathbf O ^{(k)} $ 、${\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal X}^{(k)} $ 用于从${\mathbf{X}}^{(k)}$$ \mathbf X^{(k)} $ 中预测${\mathbf{X}}^{(k+1)}$$ \mathbf X^{(k+1)} $ 。${\mathbf{X}}^{(k+1)}$$ \mathbf X^{(k+1)} $ 可以视作一个“状态”，它从输出步output step$k$$ k $ 转移到输出步$k+1$$ k+1 $ 。

     每个${\mathcal{F}}_{\mathcal{O}}^{(k)}$$ \mathcal F_{\mathcal O}^{(k)} $ 和${\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal X}^{(k)} $ 均包含各自的传播模型和输出模型。我们定义第$k$$ k $ 个输出步的第$t$$ t $ 个时间步的状态矩阵分别为：

     $$\begin{array}{c}{\mathbf{H}}_{\mathcal{O}}^{(k,t)}={[{\overrightarrow{\mathbf{h}}}_{\mathcal{O},1}^{(k,t)},\cdots ,{\overrightarrow{\mathbf{h}}}_{\mathcal{O},|\mathcal{V}|}^{(k,t)}]}^{\mathrm{\top }}\in {\mathbb{R}}^{|\mathcal{V}|\times D_{\mathcal{O}}}\\ {\mathbf{H}}_{\mathcal{X}}^{(k,t)}={[{\overrightarrow{\mathbf{h}}}_{\mathcal{X},1}^{(k,t)},\cdots ,{\overrightarrow{\mathbf{h}}}_{\mathcal{X},|\mathcal{V}|}^{(k,t)}]}^{\mathrm{\top }}\in {\mathbb{R}}^{|\mathcal{V}|\times D_{\mathcal{X}}}\end{array}$$

     其中$D_{\mathcal{O}},D_{\mathcal{X}}$$ D_{\mathcal O},D_{\mathcal X} $ 为各自传播模型的状态向量的维度。如前所述，${\mathbf{H}}^{(k,1)}$$ \mathbf H^{(k,1)} $ 可以通过${\mathbf{X}}^{(k)}$$ \mathbf X^{(k)} $ 通过填充零得到，因此有：${\mathbf{H}}_{\mathcal{O}}^{(k,1)}={\mathbf{H}}_{\mathcal{X}}^{(k,1)}$$ \mathbf H^{(k,1)}_{\mathcal O} = \mathbf H^{(k,1)}_{\mathcal X} $ ，记作${\mathbf{H}}^{(k,1)}$$ \mathbf H^{(k,1)} $ 。

   • 我们也可以选择${\mathcal{F}}_{\mathcal{O}}^{(k)}$$ \mathcal F_{\mathcal O}^{(k)} $ 和${\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal X}^{(k)} $ 共享同一个传播模型，然后使用不同的输出模型。这种方式的训练速度更快，推断速度更快，并且大多数适合能够获得原始模型相差无几的性能。但是如果${\mathcal{F}}_{\mathcal{O}}^{(k)}$$ \mathcal F_{\mathcal O}^{(k)} $ 和${\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal X}^{(k)} $ 的传播行为不同，则这种变体难以适应。

   • ${\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal X}^{(k)} $ 的输出模型称为节点annotation output 模型，它用于从${\mathbf{H}}_{\mathcal{X}}^{(k,T)}$$ \mathbf H^{(k,T)}_{\mathcal X} $ 中预测${\mathbf{X}}^{(k+1)}$$ \mathbf X^{(k+1)} $ 。该模型在每个节点$v$$ v $ 上利用神经网络独立的预测：

     $${\overrightarrow{\mathbf{x}}}_v^{(k+1)}=\sigma \left(g_a({\overrightarrow{\mathbf{h}}}_{\mathcal{X},v}^{(k,T)},{\overrightarrow{\mathbf{x}}}_v^{(k)})\right)$$

     其中$g_a(\cdot )$$ g_a(\cdot) $ 为神经网络，${\overrightarrow{\mathbf{h}}}_{\mathcal{X},v}^{(k,T)}$$ \mathbf{\vec h}_{\mathcal X,v}^{(k,T)} $ 和${\overrightarrow{\mathbf{x}}}_v^{(k)}$$ \mathbf{\vec x}_v^{(k)} $ 的拼接作为网络输入，$\sigma (\cdot )$$ \sigma(\cdot) $ 为sigmoid 函数。

   整个网络的结构如下图所示，如前所述有${\mathbf{H}}_{\mathcal{O}}^{(k,1)}={\mathbf{H}}_{\mathcal{X}}^{(k,1)}$$ \mathbf H^{(k,1)}_{\mathcal O} = \mathbf H^{(k,1)}_{\mathcal X} $ ，记作${\mathbf{H}}^{(k,1)}$$ \mathbf H^{(k,1)} $ 。

   节点注解充当 LSTM 中 input feature 的作用，只不过节点注解可能是预测得到的（也可能是直接收集到的）。

   GGS-NN 可以理解为：把图$\mathcal{G}$$ \mathcal G $ 拷贝多次，每个拷贝运行一个 GG-NN，后一个GG-NN 的 input 由前一个 GG-NN 来生成。

   

2. GGS-NNs 的训练有两种方式：

   • 仅仅给定${\mathbf{X}}^{(1)}$$ \mathbf X^{(1)} $ ，然后执行端到端的模型训练。这种方式更为通用。

     我们将${\mathbf{X}}^{(k)},k>1$$ \mathbf X^{(k)},k\gt 1 $ 视为网络的隐变量，然后通过反向传播算法来联合训练。

   • 指定所有的中间注解向量：${\mathbf{X}}^{(1)},{\mathbf{X}}^{(2)},\cdots ,{\mathbf{X}}^{(K)}$$ \mathbf X^{(1)},\mathbf X^{(2)},\cdots,\mathbf X^{(K)} $ 。当我们已知关于中间注解向量的信息时，这种方式可以提高性能。

     考虑一个图的序列输出任务，其中每个输出都仅仅是关于图的一个部分的预测。为了确保图的每个部分有且仅被预测一次，我们需要记录哪些节点已经被预测过。我们为每个节点指定一个bit 作为注解，该比特表明节点到目前为止是否已经被“解释”过。因此我们可以通过一组注解来捕获输出过程的进度。

     此时，我们可以将注解的 label 信息（即${\mathbf{X}}^k$$ \mathbf X^{k} $ ）作为模型的额外输入。因此我们的 GGS-NN 模型中，GG-NN 和给定的注解是条件独立的。

     • 训练期间序列输出任务将被分解为单个输出任务，并作为独立的 GG-NN 来训练。
     • 测试期间，第$k$$ k $ 个输出预测到的注解（即${\hat{\mathbf{X}}}^{(k)}$$ \widehat{\mathbf X}^{(k)} $ ）当作为第$k+1$$ k+1 $ 个输出的网络输入。

6.2 实验

1. bAbI 任务旨在测试 AI 系统应该具备的推理能力。在 bAbI suite 中有20 个任务来测试基本的推理形式，包括演绎、归纳、计数和路径查找。

   • 我们定义了一个基本的转换过程 transformation procedure 从而将 bAbI 任务映射成 GG-NN 或者 GGS-NN 任务。

     我们使用已发布的 bAbI 代码中的 --symbolic 选项从而获取仅涉及entity 实体之间一系列关系的story 故事，然后我们将每个实体映射为图上的一个节点、每个关系映射为图上的一条边、每个story 被映射为一张图。

   • Question 问题在数据中以 eval 来标记，每个问题由问题类型（如has_fear）、问题参数（如一个或者多个节点）组成。我们将问题参数转换为初始的节点注解，第$i$$ i $ 个参数节点注解向量的第$i$$ i $ 位设置为 1 。

     如问题eval E > A true ，则：问题类型为 > ，问题参数为E, A ，节点的注解向量为：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_v=\{\begin{array}{ll}(1,0{)}^{\mathrm{\top }},& v=E\\ (0,1{)}^{\mathrm{\top }},& v=A\\ (0,0{)}^{\mathrm{\top }},& \text{other}\end{array}\end{array}$$

     问题的监督标签为true 。

   • bAbI 任务15 （Basic Deduction 任务）转换的符号数据集symbolic dataset 的一个示例：

     
     xxxxxxxxxx
     D is A
     B is E
     A has_fear F
     G is F
     E has_fear H
     F has_fear A
     H has_fear A
     C is H
     eval B has_fear H
     eval G has_fear A
     eval C has_fear A
     eval D has_fear F

     • 前8 行描述了事实 fact，GG-NN 将基于这些事实来构建Graph 。每个大写字母代表节点，is 和 has_fear 代表了边的label （也可以理解为边的类型）。
     • 最后4 行给出了四个问题，has_fear 代表了问题类型。
     • 每个问题都有一个输入参数，如 eval B has_fear H 中，节点 B 为输入参数。节点 B 的初始注解为标量1 （只有一个元素的向量就是标量）、其它节点的初始注解标量为 0 。

   • 某些任务具有多个问题类型，如bAbI 任务 4 具有四种问题类型：e,s,w,n 。对于这类任务，我们为每个类型的任务独立训练一个 GG-NN 模型。

     论文训练四个二元分类模型，而不是单个多分类模型。实际上也可以训练单个多分类模型。

   • 在任何实验中，我们都不会使用很强的监督标签，也不会给GGS-NN 任何中间注解信息。

2. 我们的转换方式虽然简单，但是这种转换并不能保留有关story 的所有信息，如转换过程丢失了输入的时间顺序。这种转换也难以处理三阶或者更高阶的关系，如 “昨天 John 去了花园” 则难以映射为一条简单的边。

   注意：将一般化的自然语言映射到符号是一项艰巨的任务，因此我们无法采取这种简单的映射方式来处理任意的自然语言。

   即使是采取这种简单的转化，我们仍然可以格式化描述各种bAbI 任务，包括任务19（路径查找任务）。我们提供的 baseline 表明：这种符号化方式无助于 RNN/LSTM 解决问题，但是GGS-NN 可以基于这种方式以少量的训练样本来解决问题。

   bAbI 任务19 为路径查找 path-finding 任务，该任务几乎是最难的任务。其符号化的数据集中的一个示例：

   
   xxxxxxxxxx
   E s A
   B n C
   E w F
   B w E
   eval path B A w,s

   • 开始的4 行描述了四种类型的边，s,n,w,e 分别表示东，南，西，北 。在这个例子中，e 没有出现。
   • 最后一行表示一个路径查找问题：path 表示问题类型为路径查找；B, A 为问题参数；w,s 为答案序列，该序列是一个方向序列。该答案表示：从B 先向西（到达节点E）、再向南可以达到节点 A 。

3. 我们还设计了两个新的、类似于 bAbI 的任务，这些任务涉及到图上输出一个序列。这两个任务包括：最短路径问题和欧拉回路问题。

   • 最短路径问题需要找出图中两个点之间的最短路径，路径以节点的序列来表示。

     我们首先生成一个随机图并产生一个 story，然后我们随机选择两个节点 A 和 B ，任务是找出节点 A 和 B 之间的最短路径。

     为了简化任务，我们限制了数据集生成过程：节点A 和 B 之间存在唯一的最短路径，并且该路径长度至少为 2 (即 A 和 B 的最短路径至少存在一个中间结点)。

   • 如果图中的一个路径恰好包括每条边一次，则该路径称作欧拉路径。如果一个回路是欧拉路径，则该回路称作欧拉回路。

     对于欧拉回路问题，我们首先生成一个随机的、2-regular 连接图，以及一个独立的随机干扰图。然后我们随机选择两个节点A 和 B 启动回路，任务是找出从 A 到 B 的回路。

     为了增加任务难度，这里添加了干扰图，这也使得输出的回路不是严格的“欧拉回路”。

     正则图是每个节点的degree 都相同的无向简单图，2-regular 正则图表示每个节点都有两条边。

4. 对于RNN 和 LSTM 这两个 baseline，我们将符号数据集转换为 token 序列：

   
   xxxxxxxxxx
   n6 e1 n1 eol n6 e1 n5 eol n1 e1 n2 eol n4 e1 n5 eol n3 e1 n4
   eol n3 e1 n5 eol n6 e1 n4 eol q1 n6 n2 ans 1

   其中 n<id> 表示节点、e<id> 表示边、q<id> 表示问题类型。额外的 token 中，eol 表示一行的结束end-of-line、ans 代表答案answer 、最后一个数字1 代表监督的类别标签。

   我们添加ans 从而使得 RNN/LSTM 能够访问数据集的完整信息。

5. 训练配置：

   • 本节中的所有任务，我们生成 1000 个训练样本（其中有 50 个用于验证，只有 950 个用于训练）、1000 个测试样本。

   • 在评估模型时，对于单个样本包含多个问题的情况，我们单独评估每个问题。

   • 由于数据集生成过程的随机性，我们为每个任务随机生成10 份数据集，然后报告了这10 份数据集上评估结果的均值和标准差。

   • 我们首先以 50 个训练样本来训练各个模型，然后逐渐增加训练样本数量为100、250、500、950 （最多950 个训练样本）。

     由于 bAbI 任务成功的标准是测试准确率在 95% 及其以上，我们对于每一个模型报告了测试准确率达到 95% 所需要的最少训练样本，以及该数量的训练样本能够达到的测试准确率。

   • 在所有任务中，我们展开传播过程为 5 个时间步。

   • 对于 bAbI 任务4、15、16、18、19 ，我们的 GG-NN 模型的节点状态向量${\overrightarrow{\mathbf{h}}}_v^{(t)}$$ \mathbf{\vec h}_v^{(t)} $ 的维度分别为 4、5、6、3、6 。

     对于最短路径和欧拉回路任务，我们的GG-NN 模型的节点状态向量${\overrightarrow{\mathbf{h}}}_v^{(t)}$$ \mathbf{\vec h}_v^{(t)} $ 维度为 20 。

   • 对于所有的 GGS-NN ，我们简单的令${\mathcal{F}}_{\mathcal{O}}^{(k)},{\mathcal{F}}_{\mathcal{X}}^{(k)}$$ \mathcal F_{\mathcal O}^{(k)},\mathcal F_{\mathcal X}^{(k)} $ 共享同一个传播模型。

   • 所有模型都基于 Adam 优化器训练足够长的时间，并使用验证集来选择最佳模型。

6.2.1 bAbI 任务

1. 单输出任务：bAbI的任务4（Tow Argument Relations）、任务15（Basic Deduction）、任务16（Basic Induction）、任务18（Size Reasoning） 这四个任务都是单输出任务。

   • 对于任务4、15、16，我们使用 node-level GG-NN；对于任务 18 我们使用 graph-level GG-NN 。

   • 所有 GG-NN 模型包含少于 600 个参数。

   • 我们在符号化数据集上训练 RNN 和 LSTM 模型作为 baseline。 RNN 和 LSTM 使用 50 维的embedding 层和 50 维的隐层，它们在序列末尾给出单个预测输出，并将输出视为分类问题。

     这两个模型的损失函数为交叉熵，它们分别包含大约5k 个参数（RNN）和30k 个参数 （LSTM ）。

   预测结果如下表所示。对于所有任务，GG-NN 仅需要50 个训练样本即可完美的预测（测试准确率 100%）；而 RNN/LSTM 要么需要更多训练样本（任务4）、要么无法解决问题（任务15、16、18）。

   

   对于任务4，我们进一步考察训练数据量变化时，RNN/LSTM 模型的性能。可以看到，尽管 RNN/LSTM 也能够几乎完美的解决任务，但是 GG-NN 可以使用更少的数据达到 100% 的测试准确率。

   

2. 序列输出任务：所有 bAbI 任务中，任务19（路径查找任务）可以任务是最难的任务。我们以符号数据集的形式应用 GGS-NN 模型，每个输出序列的末尾添加一个额外的 end 标签。在测试时，网络会一直预测直到预测到 end 标签为止。

   另外，我们还对比了最短路径任务和欧拉回路任务。

   下表给出了任务的预测结果。可以看到 RNN/LSTM 都无法完成任务， GGS-NN 可以顺利完成任务。另外 GGS-NN 仅仅利用 50 个训练样本就可以达到比 RNN/LSTM 更好的测试准确率。

   

3. 为什么RNN/LSTM 相对于单输出任务，在序列输出任务上表现很差？

   欧拉回路任务是 RNN/LSTM 最失败的任务，该任务的典型训练样本如下：

   
   xxxxxxxxxx
   3 connected-to 7
   7 connected-to 3
   1 connected-to 2
   2 connected-to 1
   5 connected-to 7
   7 connected-to 5
   0 connected-to 4
   4 connected-to 0
   1 connected-to 0
   0 connected-to 1
   8 connected-to 6
   6 connected-to 8
   3 connected-to 6
   6 connected-to 3
   5 connected-to 8
   8 connected-to 5
   4 connected-to 2
   2 connected-to 4
   eval eulerian-circuit 5 7       5,7,3,6,8

   这个图中有两个回路 3-7-5-8-6和 1-2-4-0，其中 3-7-5-8-6 是目标回路，而 1-2-4-0 是一个更小的干扰图。为了对称性，所有边都出现两次，两个方向各一次。

   对于 RNN/LSTM，上述符号转换为 token 序列：

   
   xxxxxxxxxx
   n4 e1 n8 eol n8 e1 n4 eol n2 e1 n3 eol n3 e1 n2 eol n6 e1 n8 eol
   n8 e1 n6 eol n1 e1 n5 eol n5 e1 n1 eol n2 e1 n1 eol n1 e1 n2 eol
   n9 e1 n7 eol n7 e1 n9 eol n4 e1 n7 eol n7 e1 n4 eol n6 e1 n9 eol
   n9 e1 n6 eol n5 e1 n3 eol n3 e1 n5 eol q1 n6 n8 ans 6 8 4 7 9

   注意：这里的节点ID 和原始符号数据集中的节点 ID 不同。

   • RNN/LSTM 读取整个序列，并在读取到 ans 这个token 的时候开始预测第一个输出。然后在每一个预测步，使用ans 作为输入，目标节点ID (视为类别标签) 作为输出。这里每个预测步的输出并不会作为下一个预测步的输入。

     我们的 GGS-NN 模型使用相同的配置，其中每个预测步的输出也不会作为下一个预测步的输入，仅有当前预测步的注解${\mathbf{X}}^{(k)}$$ \mathbf X^{(k)} $ 延续到下一个预测步，因此和 RNN/LSTM 的比较仍然是公平的。这使得我们的 GGS-NN 有能力得到前一个预测步的信息。

     一种改进方式是：在RNN/LSTM/GGS-NN 中，每个预测步可以利用前一个预测步的结果。

     实际上对于 BERT 等著名的模型，解码期间可以利用前一个预测步的结果。

   • 这个典型的样本有 80 个 token，因此我们看到 RNN/LSTM 必须处理很长的输入序列。如第三个预测步需要用到序列头部的第一条边3-7，这需要 RNN/LSTM 能够保持长程记忆。RNN 中保持长程记忆具有挑战性，LSTM 在这方面比 RNN 更好但是仍然无法完全解决问题。

   • 该任务的另一个挑战是：输出序列出现的顺序和输入序列不同。实际上输入数据并没有顺序结构，即使边是随机排列的，目标节点的输出顺序也不应该改变。bAbI 任务19 路径查找、最短路径任务也是如此。

     GGS-NN 擅长处理此类“静态”数据，而RNN/LSTM 则不然。实际上 RNN/LSTM 更擅长处理动态的时间序列。如何将 GGS-NN 应用于动态时间序列，则是将来的工作。

6.2.2 Program Verification

1. 我们在 GGS-NN 上的工作受到程序验证program verification中的实际应用的启发。自动程序验证的一个关键步骤是推断程序不变量program invariant，它逼近 approximate 程序执行中可达到的程序状态program state 的集合。寻找关于数据结构的不变量是一个悬而未决的问题。

   具体实验细节参考原始论文。

6.2.3 讨论

1. 思考GG-NN 正在学习什么是有启发性的。为此我们观察如何通过逻辑公式解决bAbI 任务15 。为此考虑回答下面的问题：

   
   xxxxxxxxxx
   B is E
   E has_fear H
   eval B has_fear

   要进行逻辑推理，我们不仅需要对 story里存在的事实进行逻辑编码，还需要将背景知识编码作为推理规则。如：$\text{is}(x,y)\wedge \text{has-fear}(y,z)\to \text{has-fear}(x,z)$$ \text{is}(x,y)\land \text{has-fear}(y,z) \rightarrow \text{has-fear}(x,z) $ 。

   我们对任务的编码简化了将 story 解析为Graph 的过程，但是它并不提供任何背景知识。因此可以将 GG-NN 模型视为学习背景知识的方法，并将结果存储在神经网络权重中。

2. 论文中的结果表明：GGS-NN 在一系列具有固有图结构的问题上有理想的归纳偏置 inductive bias，我们相信在更多情况下 GGS-NN 将是有用的。然而，需要克服一些限制才能使得它们更广泛地使用。 我们之前提到的两个限制是 bAbI 任务翻译不包含输入的时序 temporal order、也不包含三阶或更高阶的关系。我们可以想象解除这些限制的几种可能性，如拼接一系列的 GG-NN，其中每条边都有一个 GG-NN 并将高阶关系表示为因子图 factor graph 。

   一个更重大的挑战是如何处理less structured 的 input representation 。例如，在 bAbI 任务中，最好不要使用 symbolic 形式的输入。一种可能的方法是在我们的 GGS-NN 中融合 less structured 的输入和 latent vector 。但是，需要进行实验从而找到解决这些问题的最佳方法。

3. 当前的 GG-NN 必须在读取所有 fact 事实之后才能回答问题，这意味着网络必须尝试得出所见事实的所有后果，并将所有相关信息存储到其节点的状态中。这可能并不是一个理想的形式，最好将问题作为初始输入，然后动态地得到回答问题所需要的事实。

4. 我们对 GGS-NN 的进一步应用保持乐观态度。我们对继续开发端到端的可学习系统特别感兴趣，这些系统可以学习程序的语义属性，可以学习更复杂的图算法，并将这些思想应用于需要对知识库和数据库进行推理的问题。更一般而言，我们认为这些图神经网络代表了迈向如下模型的一步：这些模型可以将结构化的 representation 与强大的深度学习算法相结合，目的是在学习和推断inferring如何推理reason 和扩展这些 representation 的同时利用已知结构。