Introduction to Graph Neural Network翻译-第六章 图循环网络

还有一种趋势是在传播步骤中使用来自rnn的门机制，如GRU [Cho et al.， 2014]或LSTM [Hochreiter and Schmidhuber, 1997]，以减少普通GNN模型的限制，提高图上长期信息传播的有效性。

6.1 GATED GRAPH NEURAL NETWORKS

Li等人[2016]提出在传播步骤中使用门循环单元(GRU)的GGNN。
它将递归神经网络展开固定数量的$T$T步，并随时间反向传播以计算梯度。

具体地说，传播模型的基本递归是:

$\begin{aligned} \mathbf{a}_{v}^{t} &=\mathbf{A}_{v}^{T}\left[\mathbf{h}_{1}^{t-1} \ldots \mathbf{h}_{N}^{t-1}\right]^{T}+\mathbf{b} \\ \mathbf{z}_{v}^{t} &=\sigma\left(\mathbf{W}^{z} \mathbf{a}_{v}^{t}+\mathbf{U}^{z} \mathbf{h}_{v}^{t-1}\right) \\ \mathbf{r}_{v}^{t} &=\sigma\left(\mathbf{W}^{r} \mathbf{a}_{v}^{t}+\mathbf{U}^{r} \mathbf{h}_{v}^{t-1}\right) \\ \widetilde{\mathbf{h}}_{v}^{t} &=\tanh \left(\mathbf{W} \mathbf{a}_{v}^{t}+\mathbf{U}\left(\mathbf{r}_{v}^{t} \odot \mathbf{h}_{v}^{t-1}\right)\right) \\ \mathbf{h}_{v}^{t} &=\left(1-\mathbf{z}_{v}^{t}\right) \odot \mathbf{h}_{v}^{t-1}+\mathbf{z}_{v}^{t} \odot \widetilde{\mathbf{h}}_{v}^{t} \end{aligned}\tag{6.1}$avt​zvt​rvt​hvt​hvt​​=AvT​[h1t−1​…hNt−1​]T+b=σ(Wzavt​+Uzhvt−1​)=σ(Wravt​+Urhvt−1​)=tanh(Wavt​+U(rvt​⊙hvt−1​))=(1−zvt​)⊙hvt−1​+zvt​⊙hvt​​(6.1)

节点$v$v首先聚集来自其邻居的消息，其中$\mathbf{A}_v$Av​是图邻接矩阵$\mathbf{A}$A的子矩阵，并且表示节点$v$v与其邻居的连接。类似GRU的更新函数使用来自每个节点的邻居和前一个时间步长的信息来更新节点的隐藏状态。
向量$\mathbf{a}$a收集节点$v$v的领域信息，$\mathbf{z,r}$z,r是更新门和重置门，$\odot$⊙是Hardamard product operation。

GGNN模型是针对需要输出序列的图数据定义的问题而设计的，而现有模型侧重于产生单个输出，如节点级或图数据级分类。

Li等[2016]进一步提出了门控图序列神经网络(GGS-NNs)，它使用多个$\text{GGNNs}$GGNNs产生一个输出序列$\mathbf{o}^{(1)}...\mathbf{o}^{(K)}$o(1)...o(K)。
如图6.1所示，对于第$k$k个输出步骤，节点标注矩阵表示为$\mathbf{X}^{(k)}$X(k)。

在这个架构中使用了两个$\text{GGNNs}$GGNNs:
(1)$F_o^{(k)}$Fo(k)​从$\mathbf{X}^{(k)}$X(k)中预测$\mathbf{o}^{(k)}$o(k);
(2)$F_x^{(k)}$Fx(k)​从$\mathbf{X}^{(k)}$X(k)中预测$\mathbf{X}^{(k+1)}$X(k+1)。
我们使用$\mathbf{H}^{(k,t)}$H(k,t)表示第$k$k个输出步骤的第$t$t个传播步骤。
$\mathbf{H}^{(k,1)}$H(k,1)在每个第$k$k步的值由$\mathbf{X}^{(k)}$X(k)初始化。
$\mathbf{H}^{(t,1)}$H(t,1)在每个第$t$t步的值由$\mathbf{X}^{(t)}$X(t)初始化。
$F_o^{(k)},F_x^{(k)}$Fo(k)​,Fx(k)​可用于不同的模型或共享相同的参数。

该模型在BABI任务和程序验证任务上都得到了应用，并证明了其有效性。

6.2 Tree LSTM

通过基于树或图的传播过程，LSTM的使用方式也与GRU类似。

Tai等人[2015]提出了对基本LSTM架构的两个扩展: Child-Sum Tree-LSTM 和 N-ary Tree - LSTM。
与标准的$\text{LSTM}$LSTM单元一样，每个$\text{Tree-LSTM}$Tree-LSTM（由$v$v索引）包含输入输出门$\mathbf{i}_v,\mathbf{o}_v$iv​,ov​，存储单元$\mathbf{c}_v$cv​,和隐藏状态$\mathbf{h}_v$hv​。
$\text{Tree-LSTM}$Tree-LSTM单元放弃单个遗忘门，但对每个孩子$k$k使用遗忘门$\mathbf{f}_{vk}$fvk​，从而允许节点$v$v相应地从其子节点聚集信息。
$\text{Child-Sum Tree-LSTM}$Child-Sum Tree-LSTM的方程为：

$\begin{aligned} \widetilde { \mathbf { h } } _ { v } ^ { t - 1 } & = \sum _ { k \in N _ { v } } \mathbf { h } _ { k } ^ { t - 1 } \\ \mathbf { i } _ { v } ^ { t } & = \sigma \left( \mathbf { W } ^ { i } \mathbf { x } _ { v } ^ { t } + \mathbf { U } ^ { i } \widetilde { \mathbf { h } } _ { v } ^ { t - 1 } + \mathbf { b } ^ { i } \right) \\ \mathbf { f } _ { v k } ^ { t } & = \sigma \left( \mathbf { W } ^ { f } \mathbf { x } _ { v } ^ { t } + \mathbf { U } ^ { f } \mathbf { h } _ { k } ^ { t - 1 } + \mathbf { b } ^ { f } \right) \\ \mathbf { o } _ { v } ^ { t } & = \sigma \left( \mathbf { W } ^ { o } \mathbf { x } _ { v } ^ { t } + \mathbf { U } ^ { o } \widetilde { \mathbf { h } } _ { v } ^ { t - 1 } + \mathbf { b } ^ { o } \right) \\ \mathbf { u } _ { v } ^ { t } & = \tanh \left( \mathbf { W } ^ { u } \mathbf { x } _ { v } ^ { t } + \mathbf { U } ^ { u } \widehat { \mathbf { h } } _ { v } ^ { t - 1 } + \mathbf { b } ^ { u } \right) \\ \mathbf { c } _ { v } ^ { t } & = \mathbf { i } _ { v } ^ { t } \odot \mathbf { u } _ { v } ^ { t } + \sum _ { k \in N _ { v } } \mathbf { f } _ { v k } ^ { t } \odot \mathbf { c } _ { k } ^ { t - 1 } \\ \mathbf { h } _ { v } ^ { t } & = \mathbf { o } _ { v } ^ { t } \odot \tanh \left( \mathbf { c } _ { v } ^ { t } \right) \end{aligned} \tag{6.2}$hvt−1​ivt​fvkt​ovt​uvt​cvt​hvt​​=k∈Nv​∑​hkt−1​=σ(Wixvt​+Uihvt−1​+bi)=σ(Wfxvt​+Ufhkt−1​+bf)=σ(Woxvt​+Uohvt−1​+bo)=tanh(Wuxvt​+Uuhvt−1​+bu)=ivt​⊙uvt​+k∈Nv​∑​fvkt​⊙ckt−1​=ovt​⊙tanh(cvt​)​(6.2)

其中$x_v^t$xvt​是在标准$\text{LSTM}$LSTM设置中$t$t时刻的输入向量，
$\odot$⊙是 Hardamard product operation.

如果树中每个节点的子节点的数量最多为$K$K，并且子节点可以从$1$1到$K$K排序，则可以应用$\text{N-array Tree-LSTM}$N-array Tree-LSTM。
对于节点$v$v，$\mathbf{h}_{vk}^{t},\mathbf{c}_{vk}^t$hvkt​,cvkt​代表其第$k$k个孩子在时间$t$t的隐藏状态和存储单元。

$\begin{aligned} \mathbf { i } _ { v } ^ { t } &= \sigma \left( \mathbf { W } ^ { i } \mathbf { x } _ { v } ^ { t } + \sum _ { l = 1 } ^ { K } \mathbf { U } _ { l } ^ { i } \mathbf { h } _ { v l } ^ { t - 1 } + \mathbf { b } ^ { i } \right) \\ \mathbf { f } _ { v k } ^ { t } & = \sigma \left( \mathbf { W } ^ { f } \mathbf { x } _ { v } ^ { t } + \sum _ { l = 1 } ^ { K } \mathbf { U } _ { k l } ^ { f } \mathbf { h } _ { v l } ^ { t - 1 } + \mathbf { b } ^ { f } \right) \\ \mathbf { o } _ { v } ^ { t } & = \sigma \left( \mathbf { W } ^ { o } \mathbf { x } _ { v } ^ { t } + \sum _ { l = 1 } ^ { K } \mathbf { U } _ { l } ^ { o } \mathbf { h } _ { v l } ^ { t - 1 } + \mathbf { b } ^ { o } \right) \\ \mathbf { u } _ { v } ^ { t } & = \tanh \left( \mathbf { W } ^ { u } \mathbf { x } _ { v } ^ { t } + \sum _ { l = 1 } ^ { K } \mathbf { U } _ { l } ^ { u } \mathbf { h } _ { v l } ^ { t - 1 } + \mathbf { b } ^ { u } \right) \\ \mathbf { c } _ { v } ^ { t } & = \mathbf { i } _ { v } ^ { t } \odot \mathbf { u } _ { v } ^ { t } + \sum _ { l = 1 } ^ { K } \mathbf { f } _ { v l } ^ { t } \odot \mathbf { c } _ { v l } ^ { t - 1 } \\ \mathbf { h } _ { v } ^ { t } & = \mathbf { o } _ { v } ^ { t } \odot \tanh \left( \mathbf { c } _ { v } ^ { t } \right) \end{aligned} \tag{6.3}$ivt​fvkt​ovt​uvt​cvt​hvt​​=σ(Wixvt​+l=1∑K​Uli​hvlt−1​+bi)=σ(Wfxvt​+l=1∑K​Uklf​hvlt−1​+bf)=σ(Woxvt​+l=1∑K​Ulo​hvlt−1​+bo)=tanh(Wuxvt​+l=1∑K​Ulu​hvlt−1​+bu)=ivt​⊙uvt​+l=1∑K​fvlt​⊙cvlt−1​=ovt​⊙tanh(cvt​)​(6.3)

相较于$\text{Child-Sum Tree-LSTM}, $N-\text{ary Tree-LSTM}$N−ary Tree-LSTM为每个子节点$k$k，引入单独的参数矩阵，这允许模型根据其子节点条件为每个节点学习更细粒度的表示。

6.3 graph LSTM

这两种类型的$\text{Tree-LSTMs}$Tree-LSTMs可以很容易地适应图。Zayats和Ostendorf[2018]中的 graph-structured LSTM就是N-ary Tree-LSTM应用于图的一个例子。
然而，它只是一个简化版本，因为图中的每个节点最多有两条传入边（来自它的父节点和兄弟节点）。Peng等人[2017]提出了基于关系提取任务的Graph LSTM的另一种变体。
图和树的主要区别在于图的边有的标签。并且Peng等人利用不同的权重矩阵来表示不同的标签：

$\begin{aligned} \mathbf { i } _ { v } ^ { t } & = \sigma \left( \mathbf { W } ^ { i } \mathbf { x } _ { v } ^ { t } + \sum _ { k \in N _ { v } } \mathbf { U } _ { m ( v , k ) } ^ { i } \mathbf { h } _ { k } ^ { t - 1 } + \mathbf { b } ^ { i } \right) \\ \mathbf { f } _ { v k } ^ { t } & = \sigma \left( \mathbf { W } ^ { f } \mathbf { x } _ { v } ^ { t } + \mathbf { U } _ { m ( v , k ) } ^ { f } \mathbf { h } _ { k } ^ { t - 1 } + \mathbf { b } ^ { f } \right) \\ \mathbf { o } _ { v } ^ { t } & = \sigma \left( \mathbf { W } ^ { o } \mathbf { x } _ { v } ^ { t } + \sum _ { k \in N _ { v } } \mathbf { U } _ { m ( v , k ) } ^ { o } \mathbf { h } _ { k } ^ { t - 1 } + \mathbf { b } ^ { o } \right) \\ \mathbf { u } _ { v } ^ { t } & = \tanh \left( \mathbf { W } ^ { u } \mathbf { x } _ { v } ^ { t } + \sum _ { k \in N _ { v } } \mathbf { U } _ { m ( v , k ) } ^ { u } \mathbf { h } _ { k } ^ { t - 1 } + \mathbf { b } ^ { u } \right) \\ \mathbf { c } _ { v } ^ { t } & = \mathbf { i } _ { v } ^ { t } \odot \mathbf { u } _ { v } ^ { t } + \sum _ { k \in N _ { v } } \mathbf { f } _ { v k } ^ { t } \odot \mathbf { c } _ { k } ^ { t - 1 } \\ \mathbf { h } _ { v } ^ { t } & = \mathbf { o } _ { v } ^ { t } \odot \tanh \left( \mathbf { c } _ { v } ^ { t } \right) \end{aligned} \tag{6.4}$ivt​fvkt​ovt​uvt​cvt​hvt​​=σ(Wixvt​+k∈Nv​∑​Um(v,k)i​hkt−1​+bi)=σ(Wfxvt​+Um(v,k)f​hkt−1​+bf)=σ(Woxvt​+k∈Nv​∑​Um(v,k)o​hkt−1​+bo)=tanh(Wuxvt​+k∈Nv​∑​Um(v,k)u​hkt−1​+bu)=ivt​⊙uvt​+k∈Nv​∑​fvkt​⊙ckt−1​=ovt​⊙tanh(cvt​)​(6.4)

其中 $m(v,k)$m(v,k)代表节点$v,k$v,k之间的边标签，$\odot$⊙是元素积（Hardamard product operation）。

梁等人[2016]提出了一种图LSTM网络来解决语义对象解析任务。该算法采用置信度驱动的策略自适应地选择起始节点，并确定节点更新顺序。它遵循将现有的LSTM泛化为图结构数据的相同思想，但具有特定的更新顺序，而上述方法与节点的顺序无关。

6.4 sentence LSTM

张某等人。[2018c]提出了一种改进文本编码的$\text{Sentence-LSTM(S-LSTM)}$Sentence-LSTM(S-LSTM)。
它将文本转换为图，并利用$Graph-LSTM$Graph−LSTM来学习表示。
$\text{S-LSTM}$S-LSTM在许多NLP问题中表现出很强的表示能力。

具体地说，$\text{S-LSTM}$S-LSTM模型将每个单词视为图中的一个节点，并添加一个超节点。对于每一层，单词节点可以聚合来自其相邻单词以及超级节点的信息。
超节点可以聚集来自所有单词节点以及其自身的信息。 不同节点的连接可以在图6.2中找到。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dPGCctEA-1590728154935)(https://s1.ax1x.com/2020/05/12/YN5OG8.png)]

这些连接设置背后的原因是，超节点可以提供全局信息来解决远距离依存问题，并且单词节点可以根据其相邻的单词来建模上下文信息。
因此，每个词都可以获得足够的信息，并对局部和全局信息进行建模。

$\text{S-LSTM}$S-LSTM模型可用于许多自然语言处理(NLP)任务。词的隐藏状态可用于解决序列标注、词性标注等词级任务。超节点的隐藏状态可以用来解决句子分类等句子级任务。
该模型在几个任务上取得了有希望的结果，而且它的表现也超过了强大的Transformer[Vaswani等人，2017]模型。