【论文笔记】基于门控图网络实现图到序列学习

2019 年 10 月 5 日 专知

【导读】本篇论文出自ACL 2018，作者丹尼尔·贝克（Daniel Beck）等。他们在门控神经网络的基础上，实现了图到序列的学习表示，本篇文章从理论和实验两部分介绍本篇论文。

论文地址：

https://arxiv.org/pdf/1806.09835.pdf

论文初读

作者在本篇论文中提出了一种图到序列（g2s）学习的模型，该模型利用encoder-decoder架构，采用一种基于门控图卷积网络（GCNN）的编码器，在不丢失信息的情况下整合完整的图结构，这样可以将“边“表示为标签方式。对于小尺寸标签词汇表，引入图转换，将”边“改为额外的节点，不但解决了参数爆炸问题，还确保了”边“具有特定图的隐向量。

与S2S模型相似，将输入的序列由嵌入向量表示，然后通过循环或卷积网络的编码器将向量转换为隐状态，隐状态被送到注意力机制中，通过解码生成单个上下文向量。

上图为作者论文中使用的模型，第一层是节点和位置嵌入的串联，位置：距根节点的距离。GGNN编码器使用由不同颜色表示的边参数（edge-wise paras）来更新嵌入（在该示例中为ARG0和ARG1）。编码器还为每个节点添加相应的反向边（图上是较浅的虚线箭头）和自循环边（图上是深色的虚线箭头）。所有参数在层之间共享，注意力机制和解码器组件类似于标准s2s模型。

门控图神经网络

为了更容易学习节点之间长距离关系，提出了门控图神经网络（GGNN），它采用与门控递归单元（GRU）类似的门控机制，每一次更新数据时，每个节点既能接收相邻节点的信息，有可以向相邻节点发送信息。

如图（a）中有4个节点，（c）可以看出节点之间连接关系，其中B，C，B'，C'是边的特征，均为D*D维矩阵。矩阵A 有In和out两列，表示双向信息。

传播模型

式（1）中h_v表示节点v的初态，是D维向量，当节点输入特征x维度小于D时，在后边补0。

式（2）即为图（c）中的矩阵A中选出来对应节点的两列；后边括号里边是将t-1时刻所有节点特征拼接。因此，式（2）表示节点与相邻节点间通过边的相互作用的结果。

式（3）-（6）类似GRU的计算过程。

输出模型

其中g是函数，表示利用逐个node的最终状态和初始输入分别求输出。

整张图输出一个值：

其中，i，j表示神经网络，红框是一种attention机制，用于选出哪个节点与整个graph的输出最相关。

本篇论文中与原始GGNN有所不同，但其核心内容不变。

从上图公式中可以看出，本篇论文与原始GGNN的不同之处：本篇论文中在计算隐状态、复位门和更新门时增加了偏置；特定标签的矩阵不共享任何组件；在计算之前将复位门应用于所有的隐状态；添加归一化常数。

双向性和位置嵌入

在带根有向无环图，节点嵌入信息自顶向下的方式传播。然而，我们希望反方向也具有信息流，基于RNN的编码器以同样的方式从右向左的传播中（如在双向RNN中）受益。Marcheggiani和Titov、Bastings等人通过向图中添加反向边，以及每个节点的自循环边来实现此目的。这些额外的边具有特定的标签，因此它们在网络中具有自己的参数。

在这项工作中，还遵循此过程以确保信息在图中均匀传播。然而，这提出了另一个缺陷：因为图基本上变成无向的，编码器现在不知道输入中存在的任何内在层次结构，作者通过向每个节点添加位置嵌入（positional embeddings）来解决这个问题。这些嵌入（embeddings）由表示距根节点的最小距离的整数值索引，并作为模型参数进行学习。这种位置嵌入仅限于有根DAG图：对于一般图，可以采用不同的距离概念。

Levi图变换

就提出的G2S模型，存在两个关键缺陷：

1）GGNN每个边类型有三个线性变换，这样会造成参数的数量爆炸。

2）边标签信息以网络中的GGNN参数的形式编码，这意味着每个标签在所有图中都具有相同的”表示“，但实际中，边中的潜在信息可能取决于他们在图形中出现的内容。理想情况下，边应该具有特定实例（instance-specific）的隐状态，与节点的方式相同，并且这些隐状态也应该通过注意力模块通知解码器中的决策。

为了解决以上两个缺陷，将输入图转换为等效的Levi图。