论文概要

这篇论文是第一个提出Graph Neural Network模型的论文，它将神经网络使用在图结构数据上，并细述了神经网络模型的结构组成、计算方法、优化算法、流程实现等等。论文后面还对模型的复杂度进行了评估，以及在现实任务上进行了实验和比较(比较算法为NL、L、FNN)。

图领域应用

对于图领域问题，假设函数  是将一个图  和图中的一个节点  转化为一个实值向量的函数 

那么监督学习的任务就在于从已知样本中学习得到这样的函数。

图领域的应用主要可以分为两种类型：专注于图的应用(graph-focused)和专注于节点的应用(node-focused)。对于graph-focused的应用，函数  和具体的节点无关，(即  )，训练时，在一个图的数据集中进行分类或回归。对于node-focused的应用，  函数依赖于具体的节点  ，即  ，如下例子

• 上图中(a)图是一个化学分子结构，能够使用图 进行表示，函数  可能用于估计这种化学分子对人体有害的概率，因此，我们并不关注分子中具体的原子(相当于节点)，所以属于graph-focused应用。

• 上图中(b)图是一张城堡的图片，图片中的每一种结构都由节点表示，函数  可能用于预测每一个节点是否属于城堡(图中的黑点)。这种类型属于node-focused应用。

GNN模型详述

GNN模型基于信息传播机制，每一个节点通过相互交换信息来更新自己的节点状态，直到达到某一个稳定值，GNN的输出就是在每个节点处，根据当前节点状态分别计算输出。有如下定义：

• 一个图  表示为一对  ，其中，  表示节点集合，  表示边集。

•  表示节点  的邻居节点集合。

•   表示以节点  为顶点的所有边集合。

•  表示节点  的特征向量。

•   表示边  的特征向量。

•   表示所有特征向量叠在一起的向量。

注：原论文里面说  表示label，但论文中的label指的是features of objects related to nodes and features of the relationships between the objects，也就是相关特征，所以这里一律使用特征向量翻译。

论文将图分为positional graph和nonpositional graph，对于positional graph，对于每一个节点  ，都会给该节点的邻居节点  赋予一个position值  ，该函数称为injective function，  。

假设存在一个图-节点对的集合  ，  表示图的集合，  表示节点集合，图领域问题可以表示成一个有如下数据集的监督学习框架

其中，  表示集合  中的第  个节点，  表示节点  的期望目标(即标签)。

节点  的状态用  表示，该节点的输出用  表示，  为local transition function，  为local output function，那么  和  的更新方式如下

其中，  为global transition function，  为global output function，分别是  和  的叠加形式。

根据Banach的不动点理论，假设  是一个压缩映射函数，那么上面式子有唯一不动点解，而且可以通过迭代方式逼近该不动点

其中，  表示  在第  个迭代时刻的值，对于任意初值，迭代的误差是以指数速度减小的，使用迭代的形式写出状态和输出的更新表达式为

GNN的信息传播流图以及等效的网络结构如下图所示

根据上图所示，顶端的图是原始的Graph，中间的图表示状态向量和输出向量的计算流图，最下面的图表示将更新流程迭代  次，并展开之后得到等效网络图。

学习算法

GNN的学习就是估计参数  ，使得函数  能够近似估计训练集

其中，  表示在图  中监督学习的节点个数，对于graph-focused的任务，需要增加一个特殊的节点，该节点用来作为目标节点，这样，graph-focused任务和node-focused任务都能统一到节点预测任务上，学习目标可以是最小化如下二次损失函数

优化算法基于随机梯度下降的策略，优化步骤按照如下几步进行

• 按照迭代方程迭代  次得到  ，此时接近不动点解：  。

• 计算参数权重的梯度  。

• 使用该梯度来更新权重  。

这里假设函数  是压缩映射函数，保证最终能够收敛到不动点。另外，这里的梯度的计算使用backpropagation-through-time algorithm。

为了表明前面的方法是可行的，论文接着证明了两个结论

理论1(可微性)：令  和  分别是global transition function和global output function，如果  和  对于  和  是连续可微的，那么  对  也是连续可微的。
理论2(反向传播)：令  和  分别是global transition function和global output function，如果  和  对于  和  是连续可微的。令  定义为

那么，序列  收敛到一个向量，  ，并且收敛速度为指数级收敛以及与初值  无关，另外，还存在

其中，  是GNN的稳定状态。

算法流程图如下

FORWARD用于迭代计算出收敛点，BACKWARD用于计算梯度。

Transition和Output函数实现

在GNN中，函数  不需要满足特定的约束，直接使用多层前馈神经网络，对于函数  ，则需要着重考虑，因为  需要满足压缩映射的条件，而且与不动点计算相关。下面提出两种神经网络和不同的策略来满足这些需求

1. Linear(nonpositional) GNN：

对于节点状态的计算，将方程  中的  改成如下形式

相当于是对节点  的每一个邻居节点使用  ，并将得到的值求和来作为节点  的状态。

由此，对上式中的函数  按照如下方式实现

其中，向量  ，矩阵  定义为两个前向神经网络的输出。更确切地说，令产生矩阵  的网络为transition network，产生向量  的网络为forcing network

transition network表示为 

forcing network表示为 

由此，可以定义  和 

其中，  ，  ，  表示将  维的向量整理(reshape)成  的矩阵，也就是说，将transition network的输出整理成方形矩阵，然后乘以一个系数就得到  。  就是forcing network的输出。

在这里，假定  ，这个可以通过设定transition function的激活函数来满足，比如设定激活函数为  。在这种情况下，  ，  和  分别是  的块矩阵形式和  的堆叠形式，通过简单的代数运算可得

该式表示  对于任意的参数  是一个压缩映射。

矩阵  的1-norm定义为

2. Nonelinear(nonpositional) GNN：在这个结构中，  通过多层前馈网络实现，但是，并不是所有的参数  都会被使用，因为同样需要保证  是一个压缩映射函数，这个可以通过惩罚项来实现

其中，惩罚项  在  时为  ，在  时为0，参数  定义为希望的  的压缩系数。

实验结果

论文将GNN模型在三个任务上进行了实验：子图匹配(subgraph matching)任务，诱变(mutagenesis)任务和网页排序(web page ranking)任务。在这些任务上使用linear和nonlinear的模型测试，其中nonlinear模型中的激活函数使用sigmoid函数。

子图匹配任务为在一个大图  上找到给定的子图  (标记出属于子图的节点)，也就是说，函数  必须学习到，如果  属于子图  ，那么  ，否则，  。实验结果中，nonlinear模型的效果要好于linear模型的效果，两个模型都要比FNN模型效果更好。

诱变问题任务是对化学分子进行分类，识别出诱变化合物，采用二分类方法。实验结果是nonlinear效果较好，但不是最好。

网页排序任务是学会网页排序。实验表明虽然训练集只包含50个网页，但是仍然没有产生过拟合的现象。

转自：https://zhuanlan.zhihu.com/p/76290138