Introduction to Graph Neural Network翻译-第四章Vanilla Graph Neural Networks

4. Vanilla Graph Neural Networks

在本节中，我们将描述Scarselli等人提出的Vanilla GNN[2009]。
我们还列出了Vanilla GNN在表示能力和训练效率方面的局限性。
在本章之后，我们将讨论Vanilla GNN模型的几种变体。

4.1 介绍

GNN的概念最早是在Gori等人[2005]，Scarselli等 [2004，2009]提出的。
为简单起见，我们将讨论Scarselli等人提出的模型[2009]，其目的是扩展现有的神经网络，以处理图结构化数据。

节点自然是由其特征和图中的相关节点定义的。GNN的目标是学习状态嵌入$\mathbf{h}_v\in \mathbb{R^s}$hv​∈Rs，
该状态是对每个节点的邻居信息信息编码。
状态嵌入$\mathbf{h}_v$hv​用于产生输出$\mathbf{o}_v$ov​，例如预测节点标签的分布。

在Scarselli等[2009]，一个典型的图如图4.1所示。

Vanilla GNN模型处理无向齐次图，其中图中的每个节点
都有它的输入特征$\mathbf{x}_v$xv​，并且每条边也可以有它的特征。
本文使用$co[v],ne[v]$co[v],ne[v]来代表节点$v$v的边和邻居的集合。
对于处理其他更复杂的图，例如异构图，可以在后面的章节中找到GNN的相应变体。

4.2 模型

在给定节点和边的输入特征的情况下，接下来我们将讨论模型如何获得节点嵌入$\mathbf{h}_v$hv​和输出嵌入$\mathbf{o}_v$ov​。

为了根据输入领域更新节点的状态，所有节点共享一个称为局部转移函数的参数函数$f$f。
为了产生节点的输出，有一个参数函数$g$g，称为局部输出函数。然后，$\mathbf{h}_v,\mathbf{o}_v$hv​,ov​的定义如下：

$\mathbf{h}_v = f(\mathbf{x}_v,\mathbf{x}_{co[v]},\mathbf{h_{ne[v]}},\mathbf{x}_{ne[v]}) \tag{4.1}$hv​=f(xv​,xco[v]​,hne[v]​,xne[v]​)(4.1)

$\mathbf{o}_{v}=g\left(\mathbf{h}_{v}, \mathbf{x}_{v}\right) \tag{4.2}$ov​=g(hv​,xv​)(4.2)

其中，$\mathbf{x}$x表示输入特征，$\mathbf{h}$h表示隐藏状态。
$co[v]$co[v]是与节点$v$v相连的边集合，$ne[v]$ne[v]是节点$v$v的邻居集合。
所以$\mathbf{x}_{v}, \mathbf{x}_{c o[v]}, \mathbf{h}_{n e[v]}, \mathbf{x}_{n e}[v]$xv​,xco[v]​,hne[v]​,xne​[v]分别代表$v$v的特征，它的边的特征，节点$v$v在图中邻居的状态和特征。
以图4.1中的$l_1$l1​节点为例，$\mathbf{x}_{l_1}$xl1​​是$l_1$l1​的输入特征。$co[l_1]$co[l1​]包含了边$l_{(1,4)},l_{(1,6)},l_{(1,2)},l_{(3,1)}$l(1,4)​,l(1,6)​,l(1,2)​,l(3,1)​。
$ne[l_1]$ne[l1​]包含了节点$l_2,l_3,l_4,l_6$l2​,l3​,l4​,l6​。

设$\mathbf{H},\mathbf{O},\mathbf{X},\mathbf{X}_N$H,O,X,XN​是分别由所有状态，所有输出，所有特征，所有节点特征堆叠而成的矩阵。然后我们有一个紧凑的形式：

$\mathbf{H}=F(\mathbf{H}, \mathbf{X}) \tag{4.3}$H=F(H,X)(4.3)

$\mathbf{O}=G\left(\mathbf{H}, \mathbf{X}_{N}\right)\tag{4.4}$O=G(H,XN​)(4.4)

其中，$F$F是全局转换函数，$G$G是全局输出函数。
它们分别由图中所有节点的局部转换函数$f$f和局部输出函数$g$g的堆叠而成。
$\mathbf{H}$H的值是方程$(4.3)$(4.3)的不动点，并且假设$F$F是压缩映射的情况下是唯一定义的。

在Banach不动点定理[Khamsi和Kirk，2011]的建议下，GNN使用以下经典迭代方案来计算状态：

$\mathbf{H}^{t+1}=F\left(\mathbf{H}^{t}, \mathbf{X}\right)\tag{4.5}$Ht+1=F(Ht,X)(4.5)

$\mathbf{H}^t$Ht代表$H$H的第$t$t次迭代。动力系统方程$(4.5)$(4.5)以指数速度收敛于方程$(4.3)$(4.3)的解，对于任意初值$\mathbf{H}(0)$H(0)。
注意，$f$f和$g$g中描述的计算可以解释为FNN。

在介绍了GNN的框架后，下一个问题是如何学习局部转移函数$f$f和局部输出函数$g$g的参数。
对于有监督的目标信息（对于确定的节点$\mathbf{t}_v$tv​），损失可以写为：

$\text {loss}=\sum_{i=1}^{p}\left(\mathbf{t}_{i}-\mathbf{o}_{i}\right)\tag{4.6}$loss=i=1∑p​(ti​−oi​)(4.6)

其中$p$p是有监督节点的数目。该学习算法基于梯度下降策略，由以下步骤组成。

• 状态$\mathbf{h}_v^t$hvt​由等式$(4.1)$(4.1)更新，直到时间步$\mathbf{T}$T。然后我们得到了方程$(4.3)$(4.3)的近似不动点解：$\mathbf{H}(T)\approx\mathbf{H}$H(T)≈H。
• 根据损失计算权重梯度$\mathbf{W}$W。
• 根据在上一步骤中计算的梯度来更新权重$\mathbf{W}$W。

运行该算法后，我们可以获得针对有监督/半监督任务以及图中节点的隐藏状态训练的模型。

vanilla GNN模型提供了一种有效的方法来对图数据进行建模，这是将神经网络纳入图域的第一步。

4.3 局限性

尽管实验结果表明，GNN是用于对结构数据进行建模的强大架构，但vanilla GNN仍然存在一些局限性。

• 首先，通过迭代更新节点的隐藏状态来获得不动点，计算效率较低。该模型需要$T$T步计算才能逼近不动点。
  如果放宽不动点的假设，我们可以设计一个多层GNN来获得节点及其邻域的稳定表示。
• 其次，Vanilla GNN在迭代中使用相同的参数，而大多数流行的神经网络在不同的层使用不同的参数，这是一种分层的特征提取方法。此外，节点隐含状态的更新是一个顺序的过程，可以受益于RNN中的GRU和LSTM核。
• 第三，在边上也有一些信息量大的特征，这些特征在Vanilla GNN中不能有效地建模。例如，知识图谱中的边代表关系类型，通过不同边的消息传播应根据其类型的不同而不同。此外，如何学习边的隐藏状态也是一个重要的问题。
• 最后，如果$\mathbf{T}$T很大，如果我们把注意力集中在节点的表示上而不是图上，则不适合使用不动点，因为不动点中的表示分布在值上要平滑得多，而且用于区分每个节点的信息量要小得多。

除了普通GNN之外，还提出了几个变体来解决这些限制。
例如，门控图神经网络（GGNN）[Li等人，2016]被提出用于解决第一个问题。
关系GCN（R-GCN）[Schlichtkrull等人，2018]被提出用于处理有向图。更多细节见以下章节。