GNN初探,The graph neural network model浅析

GNN初探,The graph neural network model浅析

图神经网络的任务分类

  • 图神经网络的任务主要分为:graph-focused、node-focused;其中,graph-focused关心的是对整个图的分类,node-focused则更加精细,是以图中各节点为对象进行任务。
  • graph-focused任务需要人为添加一个node用来代表整个神经网络的输出,从而与node-focused相统一。

图神经网络的计算与优化过程

设计思路

  • 一般的嵌入方法难以生成稳定的嵌入网络,而GNN设计时紧靠Banach不动点理论进行,通过不动点的稳定性巧妙地得到可以稳定训练的网络。但是由于不动点的引进,训练过程较普通的神经网络更复杂。GNN的梯度下降过程由于不动点的引进不能直接使用,需要通过特定的公式进行更新。

数学定义

  • 图G:\((N, E)\),其中\(N\)表示节点(node)集合,\(E\)表示边(edge)集合。
  • \(ne[n]\)表示节点\(n\)的邻居节点集合
  • \(co[n]\)表示以节点\(n\)为顶点的边的集合。
  • \(l_n∈R^{lN}\)表示节点\(n\)​的特征向量。
  • \(l_{(n_1, n_2)}∈R^{lE}\)表示边\((n_1, n_2)\)的特征向量
  • \(l\)表示所有特征向量拼接的向量

从单个节点总体认知GNN训练的大概流程

  • GNN的训练过程与传统机器学习不同,每一大步训练都分为两个阶段:
  1. 图网络计算(更新的是各节点的状态值,依据Banach不动点理论,迭代出状态的收敛点)
  2. 输出网络的训练(更新嵌入神经网络和输出神经网络的权重,根据特定的问题定制的LOSS函数使用梯度下降对输出网络的参数进行更新)
  • 经过以上这两步反复迭代多次,即可将GNN训练完成。

  • GNN的单个节点输入该点的状态值以及与其相关联的边特征、节点特征;输出为该节点的状态值(最后得到的状态值是不动点)

不动点的计算过程

  • GNN中有两种主要函数(都包含待更新的权值,但求不动点时不更新): global transition function \(f_w\)global output function \(g_w\)global transition function 将该点状态值、节点的邻居节点和邻接边的数据映射为该节点的状态值。 global output function 则根据具体任务将节点的状态值、节点的邻居节点和邻接边的数据映射为输出的结果。对于位置图(positional graph)(需要考虑节点之间的相对位置,如:在上方或下方连接)需要在\(f_w\)中加入inject函数:\(\upsilon_n:ne[n]\to{1,...|N|}\)以加入相对位置信息。
  • 两个函数的定义如下(节点\(n\)的状态表示为\(x_n∈R^{s}\)):

\[x_n=f_w(l_n, l_{co[n]}, x_{ne[n]}, l_{ne[n]})\] \[o_n=g_w(x_n, l_n)\] 依据Banach不动点理论(原论文是将整个图中所有节点的\(f_w\)\(g_w\)分别叠加为\(F_w\)\(G_w\),根据不动点理论得出的结果,即每次把所有节点的特征值叠在一起当输入,输出所有节点的拼接值;单看一个节点,则有以下结论),以上两式可以迭代求出不动点:

\[x_n(t+1)=f_w(l_n, l_{co[n]}, x_{ne[n]}(t), l_{ne[n]})\] \[o_n(t)=g_w(x_n(T), l_n), n∈N\]

  • 迭代求不动点的过程与嵌入类似(将一个节点的图信息转化为特征向量),可以看作图embedding。

反向传播

  • 迭代出不动点后,针对目标任务的LOSS函数,使用梯度下降等算法对\(f_w\)\(g_w\)中的权重进行更新。但是由于不动点的引进不能像普通神经网络直接使用,需要通过特定的公式进行更新。
  • LOSS函数定义如下:

\[ e_w=\sum^{p}_{i=1}\sum^{q_i}_{j=1}(t_{i, j}-\varphi_w(G_i, n_{i, j}))^2 \]

\[ 其中,t为数据的正确分类,\varphi_w(G, n)=[G_w(\Psi(w), l_N)]_n \]

\[ \Psi(w)=F_w(\Psi(w), l) \]

  • 首先,引入中间函数\(z(t)\)

\[ z(t)=z(t+1)\cdot\frac{\partial F_w}{\partial x}(x, l)+\frac{\partial e_w}{\partial o}\cdot\frac{\partial G_w}{\partial x}(x, l_N) \]

  • 经证明,序列\(z(t), z(t-1), ...\)收敛至一个向量\(z\),即\(z=\lim_{t \to -\infty}z(t)\),并且收敛速度为指数级收敛,且与\(z(T)\)初值无关。
  • 此外,还存在:

\[ \frac{\partial e_w}{\partial w}=\frac{\partial e_w}{\partial o}\cdot\frac{\partial G_w}{\partial x}(x, l_N)+z\cdot\frac{\partial F_w}{\partial w}(x, l), 其中,x为GNN的稳定状态 \]

  • GNN即使用上式进行梯度下降。

伪代码

  • 整个训练过程的伪代码如下:
GNN伪代码
GNN伪代码

Transition与Output函数的几种实现(原论文)

  • 由于要使用Banach不动点理论,\(f_w\)需要满足一定的条件(\(g_w\)不用满足,原文直接使用DNN)
  • 原文给出了两种可用的\(f_w\)
  • 两种方法都基于将\(f_w(l_n, l_{co[n]}, x_{ne[n]}, l_{ne[n]})\)改写成

\[ \sum_{u\in ne[n]}h_w(l_n,l_{(n,u)},x_u,l_u),n\in N \] 即,对各邻居节点计算\(h_w\)之后求和。然后在此基础上分为Linear和nonLinear两种。

  1. Linear(nonpositional) GNN

\[ h_w(l_n,l_{(n,u)},x_u,l_u)=A_{n,u}x_u+b_n \]

\[ A_{n,u}=\frac{\mu}{s|ne[u]|}\cdot resize(\phi_w(l_n,l_{n,u},l_u)) \]

其中,s为状态向量的维度,即节点个数;\(\phi_w\)函数为一层激活函数为\(tanh\)(或其他使\(f_w\)满足压缩映射条件的激活函数)的DNN

\[ b_w=\rho_w(l_n) \]

\(b_w\)将特征向量映射为与节点数相同维度的向量。

  1. Nonelinear(nonpositional) GNN
  • \(h_w\)为DNN,但LOSS函数添加一个惩罚项以保证\(F_w\)为压缩映射函数:

\[ e_w=\sum^{p}_{i=1}\sum^{q_i}_{j=1}(t_{i, j}-\varphi_w(G_i, n_{i, j}))^2+\beta L(\left\|\frac{\partial F_w}{\partial x}\right\|) \]

\[ 其中,L(y)在y>\mu时为(y-\mu)^2,在y\leq\mu时为0,\mu \in (0,1),\mu被称为F_w的压缩系数 \]

后记

  • GNN的数据在网络的训练中与一般的神经网络不同,GNN会将每个数据单独建立为一个节点,并且在每一大步训练中对整个图更新。
  • 节点的状态值实际上为图嵌入,与词嵌入的思想一致。
  • GNN与普通神经网络的最大区别在于图嵌入的过程、压缩映射函数的选择和训练(前向传播中的迭代操作)。

参考资料

  • https://ieeexplore.ieee.org/document/4700287
  • https://zhuanlan.zhihu.com/p/76290138