论文阅读（26）Gated graph sequence neural networks

1. 论文相关

Published as a conference paper at ICLR 2016

2. 摘要

图结构数据经常出现在化学、自然语言语义、社会网络和知识库等领域。在这项工作中，我们研究了图形结构输入的特征学习技术。我们的出发点是之前在图神经网络方面的工作（Scarselli等人，2009），我们将其修改为使用门控循环单元（gated recurrent units）和现代优化技术（modern optimization techniques），然后扩展到输出序列（output sequences）。其结果是一类灵活且广泛有用的神经网络模型，当问题是图结构时，相对于纯基于序列的模型（例如LSTM），具有良好归纳偏差（favorable inductive biases）的工作模型。我们展示了一些简单的人工智能（bAbI）和图算法学习任务的能力。然后，我们证明它在程序验证的问题上达到了最先进的性能，其中子图需要描述为抽象的数据结构。

2.2 主要贡献

我们的主要贡献是对输出序列的图神经网络的扩展。以前对图形结构输入的特征学习的研究主要集中在产生单一输出的模型上，例如图形级分类，但是许多图形输入的问题都需要输出序列。示例包括图上的路径、具有所需属性的图节点的枚举，或与开始和结束节点混合的全局分类序列。我们不知道现有的图特征学习工作是否适合这个问题。我们的激励应用程序来自程序验证，需要输出逻辑公式，我们将其作为一个顺序输出问题来制定。第二个贡献是强调了图神经网络（以及我们在这里开发的进一步扩展）是一类广泛有用的神经网络模型，适用于当前该领域面临的许多问题。

2.3 设置

图上的特征学习有两种设置：（1）学习输入图的表示；（2）在生成输出序列的过程中学习内部状态的表示。这里，（1）主要是通过之前对图神经网络的研究来实现的（Scarselli等人，2009年）；我们对这个框架做了一些小的调整，包括改变它以使用循环神经网络相关的现代实践（modern practices）。（2）这一点很重要，因为我们希望图结构问题的输出不仅仅是单个分类。在这些情况下，挑战在于如何学习图上编码已经生成的部分输出序列（例如，如果输出路径，则为目前为止的路径）以及仍然需要生成的部分输出序列（例如，剩余路径）的特征。我们将展示GNN框架如何适应这些设置，从而产生一种新的基于图的神经网络模型，我们称之为门控图序列神经网络（Gated Graph Sequence Neural Networks ，GGS-NNs）。

我们在bAbI任务的实验（Weston等人，2015）和图算法学习任务中说明了这个通用模型的各个方面，这些任务说明了模型的能力。然后我们提出一个应用程序来验证计算机程序。当试图证明诸如内存安全（即程序中没有空指针引用）之类的属性时，核心问题是找到程序中使用的数据结构的数学描述。遵循Brockschmidt等人（2015年），我们将其描述为一个机器学习问题，我们将学习从一组表示内存状态的输入图映射到已实例化的数据结构的逻辑描述。而Brockschmidt等人（2015）依靠大量的手工特征工程，我们证明该系统可以用GGS-NN代替，而无需任何精确度成本。

3. 图神经网络

在本节中，我们回顾了图形神经网络（Graph Neural Networks ，GNNs）（Gori等人，2005年；Scarselli等人，2009年），并介绍了将贯穿始终的符号和概念。

GNNs是根据图结构G=（V，E）定义的通用神经网络结构。节点v∈V从1，…，|V|取唯一值，边是对e =（v，v'）∈V×V。我们将在这项工作中集中在有向图上，因此（v，v'）表示有向边v→v'，但我们注意到框架可以很容易地适应无向图；参见scarselli等人（2009）。节点v的节点向量（或节点表示或节点嵌入）用h_v∈R^D表示。图也可以包含每个节点v的节点标签l_v∈\{1，…，L_V \}和每个边的边标签或边类型l_e∈\{1，…，L_E \}。当S是一组节点时，我们将重载符号并让h_S = \{ h_v | v \in S\};当S是一组边时，我们将重载符号并让l_S = \{l_e | e \in S\}。

函数IN(v) = \{v'|(v',v)\in E \}返回前一个节点(predecessor nodes) v',v'→v。
类似地，OUT(v) = \{v'|(v,v’)\in E \}是一个后继节点(successor nodes) v'的集合,边v'→v。节点v相邻的所有节点的集合为NBR(v) =IN(v) \cup OUT(v)，节点v进出的所有边的集合为Co(v) = \{(v',v")\in E | v =v' \lor v= v"\} 。

GNNs通过两个步骤将图映射到输出。首先，有一个传播步骤来计算每个节点的节点表示；第二，输出模型o_v = g(h_v，l_v)从节点表示和相应的标签映射到每个节点v∈V的输出o_v。在符号g中，我们保留对参数的依赖性，并且我们将一直这样做。该系统具有端到端可微性，所有参数均采用基于梯度的优化方法联合学习。

3.1 传播模型(PROPAGATION MODEL)

在这里，迭代过程传播节点表示(iterative procedure propagates node representations)。初始节点表示h_v^{(1)}被设置为任意值，然后每个节点表示都会根据下面的循环进行更新，直到收敛，其中t表示时间步骤：

image.png

Scarselli等人（2009）讨论了几种变体，包括位置图形式（positional graph forms）、特定于节点的更新（node-specific updates）和相邻节点的替代表示（alternative representations of neighborhoods）。具体来说，斯卡塞利等人（2009）建议分解f^*(·)为每个边缘项的总和：

image.png

其中f(·)是h_{v'}的线性函数或神经网络。f的参数取决于标签的配置，例如在以下线性情况下，A和b是可学习的参数：

image.png

2.2 输出模型与学习（OUTPUT MODEL AND LEARNING）

输出模型是按节点定义的，是映射到输出的可微分函数g(h_v,l_v)。这通常是线性或神经网络映射。斯卡塞利等人（2009）关注每个节点独立的输出，这些输出通过映射最终节点表示h_v^{(T)}来实现，到每个节点v∈V的输出o_v = g(h_v^{(T)}，l_v)。为了处理图级分类，他们建议创建一个虚拟的“超级节点”(dummy “super node”)，通过一种特殊的边连接到所有其他节点。因此，图级回归或分类可以以与节点级回归或分类相同的方式处理。

学习是通过Almeida-Pineda算法（Almeida，1990；Pineda，1987）完成的，该算法通过运行传播到收敛，然后根据收敛解计算梯度。这样做的好处是不需要存储中间状态来计算梯度。缺点是必须对参数进行约束，以便传播步骤是收缩图。这是为了确保收敛性，但可能会限制模型的表现力。当f(·)是一个神经网络时，鼓励在网络雅可比矩阵(network’s Jacobian)的1-范数上使用惩罚项。请参阅附录A中的一个示例，该示例给出了收缩图(contraction maps)在图中长范围传播信息时遇到困难的直觉。

4. 门控图神经网络（GATED GRAPH NEURAL NETWORKS）

我们现在描述门控图神经网络（Gated Graph Neural Networks ,GG-NNs），我们对GNN的改变，适用于非顺序输出。我们将在下一节中描述顺序输出。GNN的最大修改是，我们使用门控循环单位（Gated Recurrent Units）（Cho等人，2014年），将循环展开固定数量的步骤T，并通过时间进行反向传播，以计算梯度。这比Almeida-Pineda算法需要更多的内存，但它消除了约束参数以确保收敛的需要。我们还扩展了底层表示和输出模型。

4.1节点注释(NODE ANNOTATIONS)

在GNNs中，由于收缩映射(contraction map)约束确保固定点独立于初始化，因此在初始化节点表示中没有点。GG-NNS不再是这样，它允许我们将节点标签作为额外的输入。为了区分这些作为输入的节点标签和前面介绍的节点标签，我们将它们称为节点注释，并使用向量x来表示这些注释。

为了说明如何使用节点注释，考虑一个训练图神经网络的示例任务，以预测是否可以从给定图上的节点s到达节点t。对于此任务，有两个与问题相关的特殊节点，s和t。为了将这些节点标记为特殊节点，我们给它们一个初始注释。第一个节点s获取注释x_s=[1,0]^T，第二个节点t获取注释x_t=[0,1]^T。所有其他节点v的初始注释都设置为x_v=[1,0]^T。直观地说，这将标记s为第一个输入参数和t为第二个输入参数。然后，我们使用这些标签向量初始化节点状态向量h_v^{(1)}，方法是将x_v复制到第一个维度并填充使用额外的0,允许大于注释（annotation）大小的隐藏状态。

在可达性示例中，传播模型很容易学习将s节点注释传播到所有可从s中访问的节点，例如，通过将与前向边(forward edges)关联的传播矩阵（propagation matrix）在位置（0,0）设置为1。这将导致沿前向边复制节点表示的第一个维度。使用此参数设置，传播步骤将使所有可从s访问的节点的第一位节点表示设置为1。然后，输出步骤分类器可以通过查看某个节点在其表示向量的前两个维度中是否有非零条目，很容易地判断该节点t是否可从s中访问。

4.2 传播模型

传播模型的基本循环是：（recurrence）

image.png

矩阵A \in R^{D|V|*2D|V|}决定了图中的节点如何相互通信。A中的稀疏结构和参数连接(parameter tying)如图1所示。稀疏结构对应于图的边，每个子矩阵中的参数由边的类型和方向决定。A_{v:} \in R^{D|V|*2D}是节点v对应的A^{(out)}和A^{(in)}的两列块。 公式1是初始化步骤，它将节点注释复制到隐藏状态的第一个组件中，并用零填充其余部分。公式2是通过传入和传出边在图的不同节点之间传递信息的步骤，这些边的参数取决于边的类型和方向。a_{v}^{(t)} \in R^{2D}包含从两个方向的边激活。其余的是类似GRU的更新，其中包含来自其他节点的信息，以及来自上一个时间步骤的信息，以更新每个节点的隐藏状态。z和r是更新和重置门，\sigma (x) =1/(1+e^{-x})是逻辑sigmoid函数，并且\bigodot是元素乘法(element-wise multiplication)。我们最初尝试了一个普通的重复神经网络风格的更新(vanilla recurrent neural network-style update)，但在初步实验中，我们发现这种类似GRU的传播步骤更有效。

image.png

4.3 输出模型(OUTPUT MODELS)

我们希望在不同的情况下产生几种类型的一步输出。第一，GG-NNs通过为每个节点v \in V生成支持节点选择任务o_v = g(h_v^{(T)}，x_v)输出节点得分，并在节点得分上应用Softmax。其次，对于图级输出，我们将图级表示向量定义为:

image.png

其中\sigma (i(h_v^{(T)}，x_v))充当软注意机制(soft attention mechanism)，决定哪些节点与当前图级任务相关。i和j是采用h_v^{(T)}和x_v连接的神经网络作为输入和输出实值向量。tanh函数也可以用标识替换。

5. 门控图序列神经网络(GATED GRAPH SEQUENCE NEURAL NETWORKS)

在这里，我们描述门控图序列神经网络（Gated Graph Sequence Neural Networks,GGS-NNs），其中几个GG-NNs按顺序操作以产生输出序列o^{(1)}...o^{(K)}。
对于k^{th}输出步骤，我们将节点注释的矩阵表示为\chi ^{(k)} = [x_1^{(k)},...,x_{|V|}^{(k)} ]^T \in R^{|V|*L_V}。我们用两个GG-NNs F_o^{(k)}和F_{\chi}^{(k)}：F_o^{(k)}来从\chi ^{(k)}预测o^{(k)}，F_{\chi}^{(k)}从\chi ^{(k)}预测\chi ^{(k+1)}。

\chi ^{(k+1)}被视为从步骤k到k+1的状态。F_o^{(k)}和F_{\chi}^{(k)}这两个都包含一个传播模型和一个输出模型。在传播模型中，我们表示节点向量的矩阵 k^{th}输出步骤的 t^{th}传播步骤为H^{(k,t)} = [h_1^{(k,t)};...;H_{|V|}^{(k,t)}]^T \in R^{|V|*D}

和前面一样，在步骤k中，我们设置了H^{(k,1)}通过 0-extending \chi ^{(k)} 的每一个节点。模型概述如图2所示。或者，F_o^{(k)}和F_{\chi}^{(k)}可以共享一个传播模型，并且只具有单独的输出模型。这种简单的变种更容易训练和评估，以及在许多情况下，可以达到与完整模型相同的性能水平。但在某些情况下，F_o^{(k)}和F_{\chi}^{(k)}理想的传播行为不一样，这个变种可能不太管用。

我们引入了一个节点注释输出模型，用于从H^{(k,T)}预测\chi ^{(k+1)}。 每个节点的预测都是独立地使用一个神经网络j(H_v^{(k,T)},x_v^{(k)})来完成的，它将H_v^{(k,T)}和x_v^{(k)}的连接（concatenation）作为输入，输出一个实值分数的向量：

image.png

训练GGS-NNs有两种设置：指定所有中间注释\chi ^{(k)}，或训练仅给定\chi ^{(k)}、图和目标序列的完整模型端到端。前者可以提高我们对特定中间信息（表示在节点的中间状态）的领域知识的性能，而后者更一般。我们都描述过。

带有观察到的注释的序列输出（Sequence outputs with observed annotations）
考虑到为一个图进行序列预测的任务，其中每个预测都只是图的一部分。为了确保我们准确地预测图中每个部分的输出一次，每个节点都有一个位就足够了，表明到目前为止是否已经“解释”了该节点。在某些设置中，少量注释足以捕获输出过程的状态。在这种情况下，我们可能希望通过指示目标中间注释的标签将此信息直接输入到模型中。在某些情况下，这些注释可能是足够的，因为我们可以定义一个模型，在给定注释的情况下，在该模型中，GG-NNs是条件独立的。

在这种情况下，在训练时，给出了注释\chi ^{(k)}序列预测任务分解为单步预测任务，可以训练为单独的GG-NNs。在测试时，一个步骤中的预测注释将用作下一个步骤的输入。这类似于在完全观察数据时训练定向图形模型（training directed graphical models）。

序列输出通常带有潜在注释（Sequence outputs with latent annotations）

更加一般化，当中间节点注释\chi ^{(k)}在训练过程中不可用时，我们将其视为网络中的隐藏单元，通过对整个序列进行反向传播，共同训练整个模型。

6. 解释性应用（EXPLANATORY APPLICATIONS）

在本节中，我们将给出具体说明GGS-NNs用法的示例应用程序。我们专注于选择bAbI人工智能（AI）任务（Weston等人，2015年）和两个图算法学习任务。

6.1 巴比任务（BABI TASKS）

BABI任务旨在测试人工智能系统应该具备的推理能力（reasoning capabilities）。在BABI套件中，有20个任务测试推理的基本形式，如演绎、归纳、计数和路径查找。

我们定义了一个基本的转换过程，将BABI任务映射到GG-NNs 或 GGS-NNs。我们使用发布的babi代码中的--symbolic选项来获取只涉及实体之间关系序列的故事，然后将其转换为一个图。每个实体都映射到一个节点，并且每个关系都映射到一个边，边标签由该关系给出。整个故事(story)被消耗(consumed)并映射到一个图。问题在数据中以eval标记，由问题类型（例如has_fear）和一些参数（例如一个或多个节点）组成。参数转换为初始节点注释，其中的第i位是第i参数节点的注释向量设置为1。例如，如果eval行是eval E>A true，那么E将得到初始注释x_E^{(1)} = [1,0]^T，A将得到x_A^{(1)} = [0,1]^T，以及所有其他节点v，x_v^{(1)} = [0,0]^T。问题类型为1（对于“>”），输出为类1（对于“true”）。有些任务有多个问题类型，例如任务4，它有4个问题类型：E、S、W、N。对于这些任务，我们只需为每个任务训练一个单独的GGNN。在任何实验中，我们都不会使用强监督标签或给GGS-NNs任何中间注释。

虽然很简单，但这种转换并不能保存有关故事的所有信息（例如，它丢弃输入的时间顺序），也不容易处理三元和更高阶关系（例如，昨天约翰去花园(Yesterday John went to the garden)时不容易映射到简单的边）。我们还强调，将一般自然语言映射为符号形式是一项非常重要的任务，[2]因此我们不能将这种方法直接应用于任意自然语言。放宽这些限制是为了将来的工作。

然而，即使有了这个简单的转换，也有各种各样的bAbI任务可以被定义，包括任务19（路径查找），这无疑是最困难的任务。我们提供基线来证明符号表示对RNN或LSTM没有显著的帮助，并且表明GGS-NNs通过少量的训练实例解决了这个问题。我们还开发了两个新的类似bAbI的任务，包括在图上输出序列：最短路径和一个简单形式的欧拉电路（在随机连接的2-正则图上）。这些实验的目的是为了说明GGS-NNs在各种问题上的能力。

image.png

在这里，前8行描述了事实，GG-NN将使用这些事实构建一个图。大写字母是节点、is 和 has_fear被解释为边缘标签或边缘类型。最后4行是针对该输入数据提出的4个问题。这些行中的has_fear被解释为问题类型。对于这个任务，在每个问题中，只有一个节点是特殊的，例如eval b has_fear中的b，我们将单个值1分配给这个特殊节点的注释向量，将0分配给所有其他节点。

对于RNN和LSTM，数据转换为如下令牌序列：

image.png

其中n<id>是节点，e<id>是边缘，q<id>是问题类型，添加额外的标记eol（行尾，end-of-line）和ans（应答），以便RNN&LSTM访问数据集中的完整信息。最后一个数字是类标签。

image.png

在这里，前4行描述了边，s、n、w、e（本例中没出现e）都是不同的边类型。最后一行是路径问题，答案是方向w，s的序列，因为从B到A的路径是先向西到E，然后向南到A。问题行中的s，n，w，e被视为输出类。

更多训练细节: 对于本节中的所有任务，我们生成1000个训练示例和1000个测试示例，50个训练示例用于验证。在评估模型性能时，对于一个示例中包含多个问题的所有BABI任务，对不同问题的预测进行独立评估。由于数据集生成过程中存在随机性，我们为每个任务生成了10个这样的数据集，并报告了10个数据集的评估性能的平均值和标准偏差(standard deviation)。

对于所有解释性任务，我们从仅在50个训练示例训练不同的模型开始，逐渐将训练示例的数量增加到100、250、500和950（保留50个训练示例以供验证），直到模型的测试精度达到95%或以上，Babi Standard Weston等人取得了成功（2015）。对于每种方法，我们报告了它需要达到95%精度的最小训练示例数，以及它达到的训练示例数的精度。在所有这些情况下，我们将传播过程展开5个步骤。对于bAbI任务4，15，16，18，19，我们使用了GG-NN和节点向量h_v^{(t)}的大小分别设为D=4，D=5，D=6，D=3，D=6。对于本节中的所有GGS-NNs，我们使用了F_o^{(k)}和F_{\chi}^{(k)}共享单个传播模型的简单变体。对于最短路径和欧拉电路任务(shortest path and Eulerian circuit tasks)，我们使用D = 20。所有模型都用Adam进行了足够长的训练（Kingma&BA，2014年），验证集用于选择最佳模型来评估和避免过度拟合的模型。

6.1.1单步输出（SINGLE STEP OUTPUTS）

我们选择四个适合上述限制的BABI任务，需要单步输出：4（两个参数关系，Two Argument Relations）、15（基本演绎，Basic Deduction）、16（基本归纳，Basic Induction）和18（大小推理，Size Reasoning）。对于任务4、15和16，使用节点选择GG-NN。对于任务18，我们使用了graph level分类版本。所有的GGNN网络都包含不到600个参数[3]。

作为基线，我们在原始序列形式的符号数据上训练RNN和LSTM模型。RNN和LSTM使用50维嵌入和50维隐藏层；它们预测序列末尾的单个输出，并将输出视为分类问题，损失为交叉熵。RNN和LSTM分别包含约5K和30K参数。

测试结果见表1。对于所有任务，GG-NN仅使用50个训练示例即可达到完美的测试精度，而RNN/LSTM基线要么使用更多的训练示例（任务4），要么无法解决任务（任务15、16和18）。

在表2中，我们进一步分解了任务4基线的性能，因为训练数据的数量不同。虽然RNN和LSTM几乎都能完美地解决这一任务，但GGNN的数据量却少得多，精度达到100%。


image.png
5.1.2 顺序输出（SEQUENTIAL OUTPUTS）

bAbI任务19（寻径，Path Finding）可以说是所有bAbI任务中最困难的任务（参见例如（Sukhbaatar等人，2015年），该任务报告了所有不使用强监督的方法的精确度低于20%。我们将一个GGS-NN应用于这个问题，再次应用于数据的符号形式（因此结果与（Sukhbaatar等人，2015）中的结果不可比较）。在每个输出序列的末尾添加一个额外的“end”类；在测试时，网络将继续进行预测，直到预测“end”类为止。

表3给出了此任务的结果。RNN和LSTM都无法完成此任务。然而，只有50个训练实例，我们的GGS-NNs比RNN和LSTM获得更好的测试精度。


image.png

5.2 学习图算法（LEARNING GRAPH ALGORITHMS）

我们进一步开发了两个新的基于图上算法问题的类bAbI任务：最短路径和欧拉电路。首先，我们生成随机图，并生成一个列出图中所有边的故事。问题来自于选择两个随机节点A和B，请求连接两个选定节点的最短路径（表示为节点序列）。我们将数据生成限制为只生成长度至少为2的从A到B的唯一最短路径的问题。对于欧拉电路，我们生成一个随机的两个正则（two-regular）连通图和一个单独的随机分心图（separate random distractor graph）。问题给出两个节点A和B并启动电路，然后问题是返回给定子图上的欧拉电路（再次表示为一系列节点），该子图从A到B开始。结果如表3所示。RNN和LSTM在这两项任务上都失败了，但GGS-NNs只学习使用50个训练示例做出完美的预测。

6 用GGS-NNS进行程序验证（PROGRAM VERIFICATION WITH GGS-NNS）

我们在GGS NNS上的工作是由程序验证中的实际应用所推动的。程序自动验证的一个关键步骤是程序不变量的推导，它近似于执行过程中可达到的程序状态集。寻找数据结构的不变量是一个开放的问题。例如，考虑右边的简单C函数。

为了证明这个程序确实连接了两个列表A和B，并且所有指针引用都是有效的，我们需要（在数学上）在循环的每次迭代中描述程序的堆。为此，我们使用分离逻辑（O'hearn等人，2001；Reynolds，2002），它使用归纳谓词来描述抽象数据结构。例如，列表

Segment被定义为ls（x，y）x=y v，n.ls（n，y）x→7 val:v，next:n，其中7→val:v，next:n表示指向一个内存区域，该区域包含一个具有val的结构以及值依次为和的下一个字段。在布尔逻辑中，connective是一个与连词，但它还要求其运算符引用堆的“单独”部分。因此，ls（cur null）意味着cur要么为空，要么指向堆上的两个值，在这里由ls再次描述。公式t.ls（acur）ls（curnull）ls（b）是循环的不变量（即，在进入循环时和每次迭代后保持不变）。使用它，我们可以证明没有程序运行会因为取消引用一个未分配的内存地址（这个属性称为内存安全）而失败，并且该函数确实使用一个霍尔风格的验证方案连接了两个列表（霍尔，1969）。XXVn,V，Nn,,t
这个过程中最困难的部分是提出描述数据结构的公式，这就是我们建议使用机器学习的地方。给定一个程序，我们运行它几次，然后在相关的程序位置提取内存状态（以图形表示；见下文），然后预测分离逻辑公式。静态程序分析工具（例如（Piskac等人，2014））可以检查候选公式是否足以证明所需的属性（例如，内存安全）。
6.1形式化
将堆状态表示为一个图作为输入，我们考虑了表示程序堆的有向、可能是循环图。这些图可以从程序的内存状态自动构建。每个图节点对应于内存中存储一系列指针的地址（我们在这项工作中忽略非指针值）。图边缘反映这些指针值，即，有标记为0，…，k的边缘分别指向节点。节点的一个子集被标记为对应于程序变量。VV0，…，vkVV0，…，vk
示例输入图在图3中显示为“输入”。其中，节点ID（即内存地址）显示在节点中。边缘标签对应于程序中的特定字段，例如，本例中的0对应于上一节中示例函数中的下一个指针。对于二叉树，还有两种指向树节点的左、右子级的指针类型。
输出表示我们的目标是用数学方法描述堆的形状。在我们的模型中，我们将自己局限于分离逻辑的语法限制版本，其中公式的形式为x1，…，xn.a1……am，其中每个原子式为ls（x，y）（从到的列表）、tree（x）（从中开始的二进制树）或none（x）（在处没有数据结构）。存在量词用于为堆节点命名，这些节点需要描述形状，但不由程序变量标记。例如，要描述“panhandle list”（以循环结尾的列表），需要命名循环中的第一个列表元素。在分离逻辑中，这可以表示为t.ls（x，t）ls（t，t）。人工智能XYXX
我们可以为这个问题生成合成（标记）数据集。为此，我们修复了一组谓词，如ls和tree（扩展可以考虑双链接列表段、多树），以及它们的归纳定义。然后，我们使用一组给定的程序变量枚举实例化谓词的分离逻辑公式。最后，对于每个公式，我们枚举满足该公式的堆图。结果是一个由堆图对和我们的学习过程使用的关联公式组成的数据集。...
6.2作为GGS-NNS的配方
从数据生成过程中很容易得到中间预测步骤的节点注释。因此，我们用观察到的注释（在训练时观察到的，而不是测试时观察到的）来训练ggs-nn的变体，以从堆图推断公式。注意，也可以使用未观察到的集气站。-

神经网络变种和做端到端学习。该过程将分离逻辑公式的生成分解为一系列步骤。我们首先决定是否声明存在变量，如果是，选择与变量对应的节点。一旦声明了存在主义，我们将遍历所有变量名，并生成一个分离逻辑公式，描述与当前变量对应的节点上的根数据结构。
下面是预测分离逻辑公式的完整算法alg。1。我们使用三个显式节点注释，即命名（由程序变量标记的堆节点或声明的存在量化变量）、活动（参见算法）和解释（堆节点是已经预测的数据结构的一部分）。初始节点标签可以直接从输入图中计算出来：“isnamed”是打开的，对于由程序变量标记的节点，“active”和“is explained”总是关闭的（在第2行中完成）。算法中的注释行使用gg-nn实现，即alg。1是我们的ggs-nn模型的一个实例。图3显示了算法运行的开始，其中每个步骤与算法的一行相关。
6.3模型设置详细信息
我们使用完整的GGS-NN模型，其中和f有单独的传播模型。对于ggs-nn管道中的所有gg-nn组件，我们将传播过程展开10个时间步骤。与步骤（†）相关的ggs nns（决定是否需要声明更为存在量化的变量）和（）（确定需要声明为存在量化的节点）使用=16维节点表示。对于所有其他GGS-NN组件，使用=8。Adam（Kingma&BA，2014）用于优化，模型在20个图形的小批量上进行训练，并进行优化，直到训练误差非常低。对于图级分类任务，我们还人为地平衡了类，使每个小批量中每个类的示例数相等。所有的GGS-NN组件包含的参数都小于5K，并且在训练过程中没有观察到过拟合。X（k）DD
6.4批次预测详情
在实践中，将给出一组堆图作为输入，并期望单个输出公式描述所有输入图并与之一致。不同的堆图可以是程序执行过程中不同点的堆状态快照，也可以是具有不同输入的同一程序的不同运行。我们称之为“批量预测”设置，与本文描述的单图预测相比。

为了进行批处理预测，我们同时为每个图运行一个ggs-nn。对于每一个预测步骤，该步骤中的所有ggs nns的输出在一批图中进行聚合。
对于节点选择输出，公共命名变量将不同图形上的节点链接到一起，这是在一批中聚合预测的关键。我们计算特定命名变量的得分，其中vg（t）映射变量名T对于图中的节点，是已命名变量的输出分数T在图表中。当对所有使用as分数的名称应用SoftMax时，这相当于计算（Toselect=t）=q（Toselect=vg（t））的模型。GOT磷G前列腺素
对于图级分类输出，我们将一批图中特定类的分数相加，或者等价地计算（class=k）=q（class=k）。节点注释输出会独立地为每个图更新，因为不同的图具有完全不同的节点集。但是，当算法尝试更新一个命名变量的注释时，所有图中与该变量关联的节点都会更新。在培训过程中，中间步骤的所有标签都可以从数据生成过程中获得，因此培训过程可以再次分解为单输出单图培训。磷G前列腺素
Brockschmidt等人讨论了允许嵌套数据结构（例如列表列表）的更复杂的方案。（2015）。我们还成功地将ggs-nn模型扩展到了这个案例中。更多有关这方面的详细信息，请参见附录C。
6.5实验。
在本文中，我们生成了一个包含三个程序变量的327个公式的数据集，每个公式有498个图，产生了大约160000个公式/堆图组合。为了进行评估，我们使用对公式（即，测试集中的公式不在培训集中）的6:2:2分割，将数据分割为培训、验证和测试集。我们通过测试时预测的公式是否在逻辑上等同于基本真理来衡量正确性；通过规范化公式的名称和顺序来近似等效，然后进行精确的相等比较。
我们将我们基于GGS神经网络的模型与之前开发的方法进行了比较（Brockschmidt等人，2015）。早期的方法将每个预测步骤视为标准分类，并且需要复杂的、手动的、特定于问题的特征工程，以达到89.11%的精度。相比之下，我们的新模型在没有特征工程和很少的领域知识的情况下进行了培训，获得了89.96%的准确率。
我们的ggs-nn模型发现的一个示例堆图和相应的分离逻辑公式如图4所示。此示例还涉及嵌套数据结构和上一节中开发的批处理扩展。
我们还成功地在程序验证框架中使用了我们的新模型，为定理证明器提供了所需的程序不变量，以证明插入排序等列表操作算法集合的正确性。下表4列出了一组基准列表操作程序和由GGS-NN模型发现的分离逻辑公式不变量，并成功地在验证框架中使用，以证明相应程序的正确性。

当前管道的进一步扩展已经证明能够成功地证明更复杂的程序，如排序程序和各种其他列表操作程序。

8 相关工作

最密切相关的工作是GNN，我们已经在上面详细讨论过。Micheli（2009）提出了另一个密切相关的模型，主要在输出模型上与GNN不同。GNN已应用于多个领域（Gori等人，2005年；Di-Massa等人，2006年；Scarselli等人，2009年；Uwents等人，2011年），但它们似乎并未在ICLR社区中广泛使用。我们在这里的部分目的是宣传GNN作为一个有用和有趣的神经网络变体。

我们从GNN到GG NNS的适应，到Domke（2011）和Stoyanov等人的工作，可以得出一个类比。（2011）在结构化预测设置中。其中信念传播（必须运行到接近收敛以获得良好的梯度）被截断信念传播更新所取代，然后对模型进行训练，使截断迭代在固定的迭代次数后产生良好的结果。同样，递归神经网络（Goller&Kuchler，1996；Socher等人，2011）被扩展到树LSTMS（Tai等人，2015）类似于我们在GG NNS中使用GRU更新，而不是标准的GNN重复，目的是改善图结构中信息的长期传播。

本文所表达的将特定问题的神经网络组装成学习组件的一般思想有着悠久的历史，至少可以追溯到Hinton（1988）为预测人与人之间的关系而根据家族树结构组装神经网络的工作。类似的想法出现在Hammer&Jain（2004）和Bottou（2014）中。

图形内核（Shervashidze et al.，2011；Kashima et al.，2003）可用于具有图形结构输入的各种基于内核的学习任务，但我们不知道学习内核和输出序列的工作。PeloZi等人。（2014）通过在图上随机遍历将图转换为序列，然后使用基于序列的方法学习节点嵌入。Sperduti&Starita（1997）将图形映射到图形向量，然后使用输出神经网络进行分类。有几个模型利用了图结构上节点表示的类似传播。布鲁纳等。（2013）将卷积推广到图结构。他们的工作和GNN之间的区别类似于卷积网络和循环网络之间的区别。Duvenaud等人（2015）还考虑对图进行卷积样运算，构建一个成功的图特征的可学习、可微变量。卢西等人。（2013）将任意无向图转换为具有不同方向的多个不同DAG，然后向每个根向内传播节点表示，训练一组模型。在上述所有问题中，重点都是一步到位的问题。

GNN和我们的扩展具有许多与指针网络相同的理想属性（Vinyals等人，2015年）；当使用节点选择输出层时，可以选择输入节点作为输出。有两个主要的区别：第一，在GNN中，图结构是显式的，这使得模型不那么一般，但可以提供更强的泛化能力；第二，指针网络要求每个节点都有属性（例如，空间中的位置），而GNN可以表示仅由它们在图中的位置定义的节点，这是M使它们在不同的维度上更加通用。

GGS nns与软对准和注意力模型有关（例如，Bahdanau等人（2014年）；Kumar等人（2015年）；Sukhbaatar等人（2015））在两个方面：第一，等式7中的图表示使用上下文来关注哪些节点对当前决策很重要；第二，程序验证示例中的节点注释跟踪到目前为止解释过哪些节点，这为确保输入中的每个节点用于产生输出的序列。

9 讨论

9.1 正在学习什么？（What is being learned?）

考虑到GG-NNs正在学习的，这是有指导意义的。要做到这一点，我们可以在babi任务15如何通过逻辑公式来解决之间进行类比。举个例子，假设有一个子集需要回答右边的一个例子。

要进行逻辑推理（logical reasoning），我们不仅需要对故事中的事实进行逻辑编码，还需要将背景世界知识编码为推理规则，例如 ：

image.png

我们对任务的编码简化了将故事解析为图形式，但它不提供任何背景知识。GG-NN模型可以看作是学习这一点，结果存储在神经网络权重中。

9.2 讨论：

本文的结果表明，在一系列问题上，GGS NNS具有理想的诱导偏差，这些问题具有一些内在的图结构，我们相信在更多的情况下，GGS NNS将是有用的。然而，为了使其更广泛地应用，还需要克服一些限制。我们前面提到的两个限制是babi任务转换不包含输入的时间顺序或三元和更高阶关系。我们可以想象解除这些限制的几种可能性，例如连接一系列的gg nns，其中每个边有一个gg nns，并将高阶关系表示为因子图。更重要的挑战是如何处理不太结构化的输入表示。例如，在babi任务中，最好不要使用输入的符号形式。一种可能的方法是在我们的GGS NNS中加入较少的结构化输入和潜在向量。然而，需要实验来找到解决这些问题的最佳方法。

当前的GGS NNS公式仅在所有事实都被消耗掉之后才指定一个问题。这意味着网络必须尝试派生所见事实的所有后果，并将所有相关信息存储到节点表示中的节点。这可能不理想；最好开发将问题作为初始输入的方法，然后动态地派生出回答问题所需的事实。

我们对ggs-nns的进一步应用持乐观态度。我们特别感兴趣的是继续开发端到端的可学习系统，该系统可以学习程序的语义特性，可以学习更复杂的图形算法，并将这些思想应用于需要对知识库和数据库进行推理的问题。更一般地说，我们认为这些图神经网络代表着朝着一个模型迈进的一步，该模型可以将结构化表示与强大的深度学习算法相结合，目的是在学习和推断如何推理和扩展这些表示的同时，利用已知的结构。

参考资料

[1] Graph-to-Sequence Learning using Gated Graph Neural Networks
[2] 论文笔记：GGNN (门控图神经网络) 非常好，原理讲的很详细
[3] 《GATED GRAPH SEQUENCE NEURAL NETWORKS》结合代码的论文阅读笔记
[4] 【笔记】GATED GRAPH SEQUENCE NEURAL NETWORKS

[5] 深度学习基础：RNN、LSTM和GRU
[6] GRU神经网络

代码

[1] microsoft/gated-graph-neural-network-samples
[2] yujiali/ggnn
[3] calebmah/ggnn.pytorch

论文

[1] Gated graph sequence neural networks

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,194评论 6赞 490
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,058评论 2赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 156,780评论 0赞 346
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,388评论 1赞 283
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,430评论 5赞 384
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,764评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,907评论 3赞 406
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,679评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,122评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,459评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,605评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,270评论 4赞 329
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,867评论 3赞 312
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,734评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,961评论 1赞 265
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,297评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,472评论 2赞 348

推荐阅读更多精彩内容