基于门结构的顺序图卷积网络

GATED GRAPH SEQUENCE NEURAL NETWORKS ICLR2016

Yujia Li & Richard Zemel

Department of Computer Science, University of TorontoMarc

Brockschmidt & Daniel Tarlow

Microsoft Research原文链接：https://arxiv.org/pdf/1511.05493.pdf

简介：

图模型广泛存在于生活中，如化学、自然语言处理、社交网络、知识图谱等领域。相比较于传统链式结构或者树状数据结构，图结构数据更加灵活。因此文章考虑将图作为机器学习任务中的输入。传统图中学习任务如节点和图的分类，链路预测等仅仅要求得到图或者节点的embedding表示。实际中，很多任务要求得到图或者节点的一串序列表示。基于此思路，文章在图神经网络基础上做了相应改进以处理序列问题。 
传统GNN（GRAPH NEURAL NETWORKS)模型：

传统GNN模型为节点embedding传播的迭代模型，每个节点其初始化表示可以设置为任意值，随着节点embedding迭代直到节点收敛为止，如图所示

也可以将f*分解为多项之和，其中每一项与该边的出边和入边相关

其中f与该节点的label相关，可以通过线性函数或者神经网络表示。对于GNN模型的学习可以采用Almeida-Pineda算法，当节点embedding传播稳定后，才开始计算梯度。

GG-NNs（GATED GRAPH NEURAL NETWORKS）模型：

相比于GNN模型，GG-NNs模型固定了模型传播更新的次数为T，同时，与GNN不同，GG-NNs不随机初始化节点，而是通过节点标注（Node Annotations）初始化节点。同时，对于网络节点间的影响传播，引入了门的机制，其节点标注更新过程如下

而为了实现节点序列化输出，文章提出了Gated Graph Sequence Neural Networks(GGS-NNs),包括两个GG-NNs Fo^k和Fx^k，其中Fo^k负责根据当前节点标注产生输出，Fx^k负责产生下一步输出，其中Fo^k和Fx^k都包括传播模型和输出模型，文章中，Fo^k和Fx^k使用同一传播模型，GGS-NNs结构如图所示

其中，对于输出模型，可以选择不同表示方法，对于节点选择，可以采用

而对于网络级别的表示，则可以采用

对于根据网络第k步在最终T此更新状态H^(k,T)预测下一步状态X^(k+1)，即节点标注输出，则可以采用

同时，对于模型训练方法也有两种，一种是只初始化第一步时节点标注X^1，或者每一步X^k都需要初始化。同时，在训练过程中，GGS-NNs的训练可以通过不同GG-NNs单步进行训练，测试时可以序列测试。

实验：

文章考虑BABI任务，BABI任务集包含20种不同类型任务，BABI数据集中，每一篇文本对应一个故事。文章将故事映射为图结构，其中故事中实体映射为节点，实体关系对应为边。当一个故事中存在多个问题时，对每种类型训练一个新的模型。文章实验结果分析，相比较于LSTM，GGS-NNs能更好处理这种带有逻辑结构的问题。

思考：

相比较于传统的处理方式，GGS-NNs有效利用图模型进行相关任务，但是对于图中每一个节点每个时间步都需要传播训练，当处理大规模网络数据时，效率较差。同时，由于限制模型传播更新的次数为T，因此，GGS-NNs并不能完全收敛，损失了较长路径中的传播信息。

参考： 1.https://zhuanlan.zhihu.com/p/28170197