自然语言处理知识图谱

一文详解图神经网络(一)

2022-06-27  本文已影响0人  晓柒NLP与药物设计

一. GNN原理介绍

1.1 GNN简介与优势

图(Graph)是一种数据结构,常见的图结构模式包含图的节点(node)和边(edge),其中边包含实体之间的关系(relationship)信息

传统的机器学习所用到的数据是欧氏空间(Euclidean Domain)的数据,欧氏空间下的数据最显著的特征就是有着规则的空间结构,比如图片是统一大小的长方形栅格,语音数据是一维序列,这些数据能够通过一维或二维的矩阵进行表示,进行卷积等操作较为高效。同时,存在一个核心的假设:样本之间是相互独立的

但是,在现实生活中许多数据都是不具备规则的空间结构,即是非欧氏空间下的数据,如电子交易、推荐系统等抽象出来的图谱,图谱中每个节点与其他节点的连接不是固定的。图神经网络可以对非欧氏空间的数据进行建模,捕获数据的内部依赖关系。

图神经网络(Graph Neural Network)是不规则的、无序的,除了能够学习结构化数据(输出数据为图结构数据)之外,还能学习到非结构化数据,⽐如文本(texts)和图⽚(images),并能够在提取出的图结构中进⾏推理(reasoning),比如NLP的句法依赖树(dependency tree of sentences)CV的场景图(scene graph of images)等都需要图推理模型

GNN本质上是⼀种连接模型,通过网络中节点之间的信息传递(message passing)的方式来获取图中的依存关系(dependence of graph)GNN通过从节点任意深度的邻居来更新该节点状态,这个状态能够表示状态信息

1.2 GNN Motivation

1.3 GNN与传统NN的区别

1.4 GNN模型分类:

二. GNN模型概述

2.1 GNN符号定义与含义说明

符号(notations) 说明(Descriptions)
\mathbb{R}^m m维欧氏空间
\alpha, a, A 标量,向量,矩阵
A^T 矩阵转置
I_N N维单位矩阵
g_w ⋆ x g_wx的卷积
N,N^v graph中的节点数
N^e graph中的边数
\mathcal{N}_v 节点v的邻域集
a^t_v 时间步t处节点v的向量a
h^t_v 节点v在时间步t的隐藏状态
e_{vw} 节点v到w的边特征
e_k 带标签k的边的特征
o^t_v 节点v在时间步t的输出
\odot Hadamard product哈达玛积

2.2 图神经网络原理

图神经网络的第一次提出在IEEE2009的《The Graph Neural Network Model》由锡耶纳大学提出,该论文将现有的神经网络模型扩展到处理图领域的数据

在图结构中,每个节点由它自身的特征以及与其相连的节点特征来定义该节点,GNN的目标是通过学习得到一个状态的嵌入向量(embedding)h_v\in \mathbb{R}^s,给定一张图G,用x_v表示结点v自身的特征,边特征用x_{v,u}表示。GNN的学习目标是获得每个结点的隐藏状态h_v\in \mathbb{R}^s(state embedding)。在t+1时刻,结点v的隐藏状态按照如下方式更新:
h_v=f(x_v,x_{co[v]},h_{ne[v]},x_{ne[v]})\tag{1}

举例,假设对于节点5,其隐藏状态的更新函数如下:


h_5=f(x_5,x_{(3,5)},x_{(5,6)},h_3,h_6,x_3,x_6)\tag{2}
利用更新函数f,不断地利用当前时刻邻居结点的隐藏状态作为部分输入来生成下一时刻中心结点的隐藏状态,最终需要一个输出函数,适应不同的下游任务,论文中称为局部输出函数(local output function),用g表示:
o_v=g(h_v,x_v)\tag{3}

收敛性证明:

假设将所有的状态向量,所有的输出向量,所有的特征向量和所有的节点特征而得到的向量叠加起来,分别用H,O,X,X_N表示,那么可以得到更加紧凑的表示:
H=F(H,X)\tag{4}

O=G(H,X_N)\tag{5}

Banach的不动点定理:无论输入H^0是什么形式,只要F是个压缩的映射,不断迭代压缩,最终都会收敛到某一个固定的点,即称之为不动点

f是用前馈神经网络实现,把每个邻居结点的特征、隐藏状态、每条相连边的特征以及结点本身的特征简单拼接在一起,在经过前馈神经网络后做一次简单的加和:
h_v^{t+1}=f(x_v,x_{co[v]},h_n^te[v],x_ne[v])=\sum_{u\in ne[v]}FNN([x_v;x_{(u,v)}];h^t_u;x_u)\tag{6}
f为压缩映射的等价条件是f的梯度(导数)要小于1,可以通过对雅可比矩阵(Jacobian Matrix)的惩罚项(Penalty)来实现,限制fH的偏导数矩阵的大小,则可以根据Banach的不动点定理,GNN使用如下的迭代方法来计算状态参量:
H^{t+1}=F(H^t,X)\tag{7}
其中H^t表示H的第t个迭代周期的张量。对于任意的初始值H_0公式(7)能通过快速收敛来得到公式(4)最终的固定点的解,证毕

fg的参数学习
不一定所有结点都是有监督的,模型的损失只通过有监督信号的结点得到,可以将损失函数定义为如下形式:
loss=\sum_{i=1}^p{(t_i-o_i)}\tag{8}
p表示监督节点的数目,t_io_i分别表示节点的真实值和预测值。损失函数的学习基于梯度下降策略,由以下步骤组成:

  1. 状态h_v^t按照f迭代更新T轮次,直到接近公式(4)的定点解的时刻T, 这时得到的H会接近不动点的解H^T\approx H
  2. 对于有监督信号的结点,将其隐藏状态通过g得到输出,进而算出模型的损失
  3. 反向传播时,权重W的梯度从loss计算得到,可以得到fg对最终隐藏状态h_v^{{T_n}}的梯度,然后W根据上一步中计算的梯度不断更新,经过T次,得到对h_v^0的梯度,然后该梯度用于更新模型的参数

2.3 GNN存在的问题

原始的GNN有如下的缺点:

三. GNN系列拓展

3.1 Graph Types

原始的GNN输入的图结构只包含带有标签信息的节点无向边,这是最简单的图结构,其它种类的图结构主要有有向图、异质图、带有边信息图和动态图,如下图:

3.2 Propagation Types

传播(propagation)指的是汇集从邻居节点和连接的边的信息来对节点进行更新的过程,这个过程模型中获取节点(或边)的隐藏状态,对于信息传播步骤(propagation step),有几种主要的GNN变体,而在输出步骤(output step)中,通常使用简单的前向传播的神经网络

不同的GNN的信息传播变体使用下图进行列出,这些变体采用不同的信息传播方式来从邻居节点中获取信息,并通过设定的更新器(updater)来对节点的隐藏状态进行更新


不同类别模型的Aggregator计算方法和Updater计算方法如下表:

在所有这些频域方法中,学习得到的滤波器都是基于拉普拉斯特征分解,也就是取决于图的结构,这也就意味着,在一个特定结构上训练得到的模型,并不能直接应用到另外一个结构不同的图上

上一篇 下一篇

猜你喜欢

热点阅读