原始图神经网路 Introduction to Graph Neural Networks chapter4 ---Vanilla graph neural network

本文主要参考

• introduction to Graph Neural Networks

引言

原始图神经网络(GNN)于2009年提出，本文简述一下他的原理一些变种和在表达能力以及训练性能上的局限。
在一开始被提出时，他主要是为了扩展神经网络，处理图状数据。

表示和输入

一个节点由他本身的特征和他周围的节点所定义。GNN的目标是为了学习一个嵌入状态$h_v∈{\Bbb{D}}^s$hv​∈Ds(其中英文是embedding我是这么翻译的，如果更好的翻译可以指出)，这个$h_v$hv​记录了来自邻居节点的信息。这个$h_v$hv​用来生成一个输出$o_v$ov​就比如说对于节点标签的预测分布。一个典型的如图1所示，原始图神经网路用来处理无向同质图，其中每个图中节点都有输入特征$x_v$xv​而且每个边也都有特征。本文用co[v]和ne[v]来表示每个点边的集合和邻接点的集合。同时为了处理更复杂的图形，例如异质图，与之相对应的GNN变种在后面的博客中会进一步提到。

$图1$图1

模型(Model)

在给定节点和边的输入特征的情况下，下面来说一下如何获得点的嵌入状态$h_v$hv​和嵌入输出(output embedding)。
为了让每个节点状态由周围节点决定，那么我们可以用一个参数函数，称之为局部转移函数$f$f(local transition function)，为了输出一个节点，就要用一个参数函数g，叫做$f$f(local output function)。然后通过以下公式

$h_v=f(x_v,x_{co[v]},h_{ne[v]},x_{ne[v]}) (4.1)$hv​=f(xv​,xco[v]​,hne[v]​,xne[v]​)(4.1)

$o_v=g(h_v,x_v) (4.2)$ov​=g(hv​,xv​)(4.2)

参数说明$x_v$xv​表示的是第v个节点的特征输入，$x_{ne[v]}$xne[v]​表示是第v个节点的邻接点的特征输入，$x_{co[v]}$xco[v]​则表示的是x的邻接边的特征输入，$h_{ne[v]}$hne[v]​表示的是邻接点的状态。很显然可以总结出来，x表示的是输入，而h表示的是状态。

例如在例子中，$x_1$x1​周围的四个节点就是邻接点，四条边为$co[v]$co[v]。

让$H,O,X,and X_N$H,O,X,andXN​成为压缩状态，输出，特征和节点特征的矩阵。即$H$H成为所有节点的状态矩阵，$O$O成为所以节点嵌入输出的矩阵，$X$X成为所有特征(包括点和边),$X_N$XN​表示所有点的输入特征。
那么有
$H=F(H,X) (4.3)$H=F(H,X)(4.3)

$O=G(H,X_N) (4.4)$O=G(H,XN​)(4.4)

$F和G$F和G分别是全局转移函数和全局输出函数。他们是所有的局部函数一种压缩(也类似于矩阵的形式压缩函数)。

对于迭代，GNN使用传统的规划方式。

$H^{t+1}=F(H^t,X)(4.5)$Ht+1=F(Ht,X)(4.5)

学习策略与损失函数

基于我们的目标信息也即监督学习的监督值来定义损失函数。
$loss=\sum_{i=1}^{p}(t_i-o_i)(4.6)$loss=i=1∑p​(ti​−oi​)(4.6)

$p$p是监督节点的个数，学习算法是梯度下降并且依据下列步骤

• 通过公式(4.1)来学习$h_v^t$hvt​直到公式(4.3)中$H(t)=H(t-1)$H(t)=H(t−1)，称之为H的定值(fixed value)
• 梯度权重w由损失计算
• 权重由损失更新

通过这些策略，可以得到一个训练特别的监督或者半监督任务的模型。同时得到每个节点的隐藏状态。原始GNN开始将神经网络和图领域结合。

局限

• 在得到H的顶点中，会出现计算上的低效，可以通过放宽对于fixed value的规定，通过多层GNN来训练
• GNN在迭代中每次都是用一样的参数，而神经网络则使用不同的参数，后者可以更适合结构化的提取特征。此外，更新隐藏状态作为一个时序过程可以通过应该RNN的核函数例如GRU和LSTM
• 有一些隐藏信息会被忽略。比如我们只有边的输入而没有边的状态，但是在知识图谱中，同样类型的信息在不同边上传递时应有不同。但如何学习边的隐藏状态仍是问题。
• 最后，如果T很大，那么使用fixed points极不合适。使用fixed points会使我们过多关注点的表达而不是整个图。而在fixed values的值的分布上，fixed values会很平滑而导致不能区分每个点之间的区别。

结语

为了解决这些问题，一些变种被提出，例如Gated Graph Neural networks(GGNN)（门控图神经网路）来解决第一个问题。Relational GCN(R-GCN)（GCN为图卷积网络， R-GCN为关系图卷积网络）来解决有向图。