数据可以在许多应用领域中自然地用图结构graph structure
来表达,包括蛋白质组织学proteomics
、图像分析、场景描述、软件工程、自然语言处理。最简单的图结构包括单节点single node
、序列sequence
。但是在一些应用中,信息被组织成更复杂的图结构,如树、无环图、带环图。传统上,数据关系探索一直是归纳式逻辑编程inductive logic programming
的社区中许多研究的主题。最近,数据关系探索data relationships exploitation
这个研究主题已经朝着不同的方向发展,这也是因为统计statistics
和神经网络中的相关概念在这些领域中的应用。
在机器学习中,结构化数据通常与(有监督的或者无监督的)learning
的目标相关联,例如一个函数 application
通常可以分为两大类,分别称作 graph-focused
应用、node-focused
应用 。
在 graph-focused
应用中,函数
此时每个图具有一个
representation
,并且每个图具有一个target
。
例如,可以用一个图
在下图中,图片由区域邻接图region adjacency graph
来表达,其中节点表示均匀图片强度的区域,边代表这些区域的邻接关系。在这种情况下,可以根据图片的内容通过
在 node-focused
应用中,函数
此时每个节点具有一个
representation
,并且每个节点具有一个target
。
例如目标检测 application
包括检查图片中是否包含给定的对象,如果是,则定位给定对象的位置。这个问题可以通过一个函数 1
、否则 0
。
另一个例子来自于网页分类。web
可以通过一个图来表达,其中节点代表网页,边代表网页之间的超链接,如下图所示。可以利用 web connectivity
以及网页内容来实现多种目的purposes,
,如页面的主题分类。
传统的机器学习 application
通过使用预处理 preprocessing
阶段来处理图结构化数据graph structured data
,该阶段将图结构化信息映射到更简单的 representation
,如实值向量。换句话讲,预处理步骤首先将图结构化数据 "挤压squash
" 为实数向量,然后使用 list-based
数据处理技术来处理 preprocessed
的数据。然而,在预处理阶段,一些重要的信息(如每个节点的拓扑依赖性 topological dependency
)可能会丢失,并且最终结果可能以不可预知的方式unpredictable manner
取决于预处理算法的细节。
最近,有各种方法试图在预处理阶段尽可能地保留数据的图结构特性,其思想是:使用图节点之间的拓扑关系对底层的图结构化数据进行编码,以便在数据正式处理步骤(即预处理步骤之后的模型处理阶段)中融合图结构化信息。这组技术包括 recursive neural network: RNN
、马尔科夫链Markov chain: MC
,并且通常可以同时应用于 graph-focused
问题和 node-focused
问题。论文 《The Graph Neural Network Model》
提出的方法扩展了这两种方法(即 RNN
和马尔科夫链),因为该方法可以直接处理图结构化信息。
现有的 RNN
是以有向无环图directed acyclic graph
作为输入的神经网络模型。该方法估计函数 node-focused application
中,此时,图必须经过预处理阶段。类似地,采用预处理阶段之后,我们可以处理某些类型的带环图。RNN
已被应用于多个问题,包括逻辑术语分类 logical term classification
、化合物分类、logo
识别、网页评分、人脸定位 face localization
。
RNN
也与支持向量机有关,其中支持向量机采用特殊的 kernel
对图结构化数据进行操作,其中:
diffusion kernel
是基于热扩散方程heat diffusion equation
。《Marginalized kernels between labeled graphs》
和 《Extensions of marginalized graph kernels》
中提出的 kernel
利用了图随机游走生成的向量。《Convolution kernels for natural language》
、《Kernels for structured natural language data》
、《Convolution kernels with feature selection for natural language processing tasks》
中设计的 kernel
使用了一种计算两棵树的公共子结构数量的方法。事实上,类似于支持向量机方法,RNN
自动将输入的图编码为内部 representation
。然而,在 RNN
中内部编码是模型自动学到的,而在支持向量机中内部编码是由用户手动设计的。
另一方面,马尔科夫链模型可以建模事件之间的因果关系,其中因果关系由图来表达。最近,针对特定种类马尔科夫链模型的随机游走理论已成功应用于网页排名ranking
算法的实现。互联网搜索引擎使用排名算法来衡量网页的相对重要性。这类度量值通常与其它页面特征一起被搜索引擎所利用,从而对用户 query
返回的 URL
进行排序。人们已经进行了一些尝试来扩展这些具有学习能力的模型,以便可以从训练样本中学习模型参数。这些模型能够泛化结果从而对集合中的所有网页进行评分。更一般地,人们已经提出了几种其它统计方法,这些方法假设数据集由模式 pattern
、以及模式之间的关系 relationship
组成。这些技术包括:随机场random field
、贝叶斯网络、统计关系学习、transductive learning
、用于图处理的半监督方法。
在论文 《The Graph Neural Network Model》
中,作者提出了一种有监督的神经网络模型,该模型同时适用于 graph-focused application
和 node-focused application
。该模型将这两个现有模型(即 RNN
和马尔科夫链)统一到一个通用框架中。论文将这种新颖的神经网络模型称作图神经网络 graph neural network: GNN
。论文将证明 GNN
是 RNN
和随机游走模型的扩展,并且保留了它们的特性 characteristics
。
GNN
模型扩展了 RNN
,因为 GNN
可以处理更通用的图,包括带环图、有向图、无向图,并且无需任何预处理步骤即可处理 node-focused application
。GNN
方法通过引入 learning
算法、以及扩大可建模过程的种类从而扩展了随机游走理论。 GNN
基于信息扩散机制 information diffusion mechanism
。图由一组单元unit
来处理,每个单元对应于图上的一个节点,这些节点根据图的连通性进行链接。这些单元更新它们的状态并交换信息,直到它们到达稳定的平衡stable equilibrium
。然后,基于单元的状态unit state
计算每个节点的输出。扩散机制是受约束constrained
的,从而确保始终存在唯一的稳定平衡。
这种实现机制已经在细胞神经网络、Hopfield
神经网络中使用。在那些神经网络模型中,连通性是根据预定义的图来指定的,网络连接本质上是循环 recurrent
的,神经元状态是通过松弛relaxation
到平衡点equilibrium point
来计算的。GNN
与那些神经网络不同之处在于:GNN
可以处理更加通用的图,并且采用更通用的扩散机制。
在论文 《The Graph Neural Network Model》
中,作者将介绍一种学习算法,该算法在一组给定的训练样本上估计 GNN
模型的参数。此外,参数估计算法的计算代价需要被考虑。还值得一提的是,《Computation capabilities of graph neural networks》
已经证明了 GNN
展示出一种普遍的逼近特性,并且在不严厉的条件下,GNN
可以逼近图上大多数实际有用的函数
定义图
节点和边可能含有额外的信息,这些信息统称为标签信息(它和监督学习中的标记label
不是一个概念),并以实值向量的形式来表示。
all
标签向量。scheme
:如果 注意,这里的符号定义与大多数论文的符号定义不同。
节点标签通常包含节点的特征,边标签通常包含节点之间关系的特征。如下图中:节点标签可能代表区块的属性,如:面积、周长、颜色的平均强度。边标签可能代表区块region
之间的相对位置,如:重心之间的距离、轴线之间的角度。我们未对边作出任何假设,有向边和无向边都是允许的。但是,当不同类型的边共同存在于同一个图
图 positional
的、或者是 nonpositional
的。nonpositional graph
是前面所讲的那些图。positional graph
与之不同,节点 unique
的整数标识符,从而指示每个邻居的逻辑位置logical position
。 形式上,对于positional graph
中的每个节点,存在一个映射函数 position
region adjacency graph
(如上图所示) :可以用
注意,位置信息可以通过对邻居节点分配位置编号来显式地给出,也可以通过对邻居节点进行排序从而隐式地给出。
本文考虑的领域是 (graph, node) pair
的集合 graph
的集合,graph
的节点集合的集合,即:
其中:desired target
(可能为向量也可能为标量),
有趣的是,unique
的、断开的大图,因此可以将 pair
domain
仅由一个图组成,如大部分的 web
网络(如下图所示)。
我们所提出方法的直观想法是:图中的节点代表对象或概念,而边代表它们之间的关系。每个概念自然地由它的特征和相关的概念来定义。因此,我们可以可以将一个状态向量state vector
representation
,并可用于产生输出
令 parametric
的函数,称之为局部转移函数 local transition function
,用于表示节点对其邻域的依赖性。令 local output function
,用于描述如何产生输出。那么
其中:
注意:这里有递归定义,其中节点
的状态向量 依赖于其邻居的状态向量集合 。而邻居的状态向量又依赖于邻居的邻居的状态向量集合。 注意:这里的邻域依赖性使得计算状态向量所依赖的节点规模迅速膨胀。假设平均邻域大小为
10
个节点,如果最多依赖于5
阶邻域,那么计算每个状态向量需要依赖于5
阶邻域内的10
万个邻域节点。
备注:
备注一:可以采用不同的邻域概念。例如,人们可能希望删除标签 2-hop
或者多个 hop
的节点。
备注二:上式用于无向图。在处理有向图时,函数
本文中为了保持符号紧凑,我们使用无向图的形式。然而,除非特殊说明,否则本文中提出的所有结果也适用于有向图、以及混合有向与无向的图。
备注三:通常而言,转移函数 parameters
可能都依赖于节点
然而为了简单起见,我们对所有节点共享相同的转移函数和输出函数(包括它们的参数)。
如果没有参数共享则模型的容量太大导致难以训练且很容易过拟合。
令
其中:
global transition fucntion
,它由 global output function
,它由 令图和节点的 pair
对的集合为
Banach
不动点理论 fixed point theorem
为上述方程解的存在性和唯一性提供了理论依据。根据 Banach
不动点理论,当 contraction map
。即存在
其中
本文中我们假设 GNN
模型中,这个条件是通过适当的选择转移函数来实现的。
上述公式能够同时处理位置图positional graph
和非位置图nonpositional graph
。
对于位置图,null
值。例如:
其中:
即:如果 null
值
对于位置无关的图,我们可以将
其中 nonpositional form
,而原始形式被称作 positional form
。
注意,这里对邻居节点采用
sum
聚合。也可以采用max
聚合或者attention
聚合。
为实现 GNN
模型,我们必须解决以下问题:
求解以下方程的算法:
从训练集中学习
Banach
不动点理论不仅保证了解的存在性和唯一性,还给出了求解的方式:采用经典的迭代式求解:
其中
对于任意初始值
这可以解释为由很多处理单元unit
组成的神经网络,每个处理单元通过 encoding network
,它类似于 RNN
的编码网络。在编码网络中,每个单元根据邻居单元的状态、当前节点的信息、邻居节点的信息、边的信息,通过
当 RNN
,其中神经元之间的连接可以分为内部连接internal connection
和外部连接external connection
:内部连接由实现处理单元的神经网络架构(如前馈神经网络)决定,外部连接由图的边来决定。
如下图所示:上半图对应一个图Graph
,中间图对应于编码网络,下半图对应于编码网络的展开图unfolding graph
。在展开图中,每一层layer
代表一个时间步,layer
之间的链接(外部连接)由图的连接性来决定,layer
内神经元的链接(内部连接)由神经网络架构决定。
内部连接决定
如何更新状态 ,外部连接决定节点之间的依赖关系。
假设训练集为:
其中: target
(可能为标量可能为向量),
graph-focused
任务,可以引入一个和任务目标相关的、特殊的节点,只有该节点包含监督信息,即 node-focused
任务,每个节点都可以包含监督信息。假设采用平方误差,则训练集的损失函数为:
其中
也可以在损失函数中增加罚项从而对模型施加约束。
我们可以基于梯度下降算法来求解该最优化问题,求解方法由以下几步组成:
通过下面的迭代公式求解求解
其解接近
注意:这一步要求
求解梯度
通过梯度来更新参数
梯度 GNN
中发生的扩散过程diffusion process
以非常高效的方式进行。这种扩散过程与 RNN
中发生的扩散过程非常相似,而后者是基于backpropagation-through-time: BPTT
算法计算梯度的。在这种情况下,编码网络从时刻 unfold
到初始时刻 unit
BPTT
是在展开图上执行传统的反向传播算法。 首先计算时间步 BPTT
要求存储每个单元在每个时间步 Almeida-Pineda
算法提出了一个非常高效的处理方式:由于我们假设状态向量 BPTT
算法仅需要存储
下面两个定理表明这种简单直观方法的合理性:
定理(可微性Differentiability
):如果全局转移函数
其证明见原始论文。值得注意的是,对于一般动力学系统而言该结论不成立。对于这些动力学系统而言,参数的微小变化会迫使其从一个固定点转移到另一个固定点。而 GNN
中的
定理:如果全局转移函数
则序列
更进一步有:
其中