图神经网络综述

GNN简介与起源

​ 关于GNN的起源来自于两种思维的碰撞，一种是卷积神经网络CNN，另一种是图嵌入（graph embedding）。众所周知，CNN擅长提取多尺度的局部特征并将其组合为更高级的表示。CNN的核心特点是局部链接，权重共享，多层叠加。类推可以发现，这些特点可良好移植到图结构中。首先，图结构是最典型局部连接结构；其次，共享权重可减少计算量；最后，多层结构保证了分级处理问题的可能。但局限的是，CNN只能良好处理欧几里得数据，诸如一维文本数据和二维图像数据，这些数据都可以看作规则连接的图结构特例。对于图结构，CNN的卷积核和池化操作很难迁移到图上。图嵌入就是对图的节点，边或子图进行学习得到一个低维的向量表示。图嵌入常见模型由DeepWalk，Node2Vec等，但这些方法普遍有严重不足，一是节点编码中权重未进行共享而导致权重数量随着节点增多线性增大。再是直接嵌入方法缺乏泛化能力，无法将模型泛化到处理新的图。基于此，两者结合，提出了图神经网路GNN。

GNN与传统NN区别

​ 传统神经网络诸如CNN和RNN因都需要节点的特征按照一定的顺序排列，而图结构并没有特定的顺序，导致它们不能适当处理图结构输入。若将图拆分为所有可能的多个序列，将会造成非常大的计算冗余。GNN采用在每个节点上分别进行传播的方式进行学习，由此忽略节点顺序，从而GNN输出会随着输入的不同而不同。另外，GNN通过邻居节点的加权求和来更新节点隐藏状态。传统神经网络主要处理的数据对象是欧式空间的，例如文本序列，图片等等，而图神经网络主要是处理非欧空间的数据，例如社群关系，知识图谱等。具体到图神经网络的两种实现形式，第一种是将非欧空间的图转换为欧式空间的图，也就是基于谱域的实现，另一种是直接在图上抽特征，随机游走等的方式来做的，就是基于空域的实现。

GNN分类

​ 从空域视角看图卷积神经网络，本质上是一个迭代式聚合邻居的过程，这一行为启发了一大类模型对聚合操作的重新设计，这些设计在某些方面大大加强了图神经网络对图数据的适应性，下面对图神经网络的典型变体和通用表达框架进行介绍。

GraphSAGE

​ GraphSAGE从两个方面对GCN进行了改动，一方面是通过采样邻居策略将GCN由全图训练方式改造成以节点为中心的小批量训练，这使得大规模图数据的分布式训练变得可能。另一方面对聚合邻居的操作进行了扩展，提出了替换GCN操作的几种新的方式。

​ 在之前的GCN模型中，训练方式是一种全图形式，也就是一轮迭代，所有节点样本的损失只会贡献一次梯度数据，无法做到DNN中常用的小批量式更新，这是很低效的。GraphSAGE从聚合邻居出发，对邻居进行随机采样来控制实际运算时节点K阶子图的数据规模，在此基础上对采样的子图进行随机组合来完成小批量式的训练。在GCN中，节点在k+1层的特征只与其邻居在K层的特征有关，即节点在第k层的特征只与自己的K阶子图有关。GraphSAGE研究了几种新的聚合方法，即对聚合节点数量自适应，使聚合操作对聚合节点具有排列不变性。总之，GraphSAGE对空域视角下的GCN做了一次解构，提出了几种邻居的聚合操作算子，同时通过采样邻居，大大提高了算法的工程价值。在引文[61]中通过该方法完成了对工业级大规模推荐系统的应用，且效果十分显著。

图注意力网络GAT

​ 图注意力网络通过注意力机制对邻居节点做聚合操作，实现了对不同邻居权重的自适应分配，从而大幅提高图神经网络的表达能力。图注意力网络通过注意力机制来对邻居节点做聚合操作，实现对不同邻居权重的自适应分配，从而大大提高了图神经网络模型的表达能力。

​ DNN中的注意力机制是通过人对信息处理机制的轻重来启发的。注意力机制的核心在于对给定信息进行权重分配，权重高的信息意味着需要系统进行重点加工。注意力机制里包含三要素：Query，Source，Attention Value。即当前中心节点的特征向量，所有邻居的特征向量，中心节点经过聚合操作后的新的特征向量。具体到网络结构中，图注意力层比GCN里的图卷积层多了一个自适应的边权重系数维度。

GNN的General Framework

（1）消息传播神经网络MPNN

MPNN通过消息传播机制对多种GCN模型做出一般化总结。其基本思路为：节点的表示向量都是通过消息函数M和更新函数U进行K轮消息传播机制的迭代后得到。MPNN的核心在于消息函数和更新函数，原则上可以把他们设计成任意一种DNN模型，MPNN的消息函数是作用在RDF三元组上，因此对于常见的同构图，异构图，属性图等都具有一定的适应性。

（2）非局部神经网络NLNN

非局部神经网络NLNN是对注意力机制的一般化总结，GTA即为其一个特例。NLNN通过non-local操作将任意位置的输出响应计算为所有位置特征的加权和。位置可以是图像中的空间坐标，也可以是序列数据中的时间坐标，在图数据中，位置可以直接以节点替代。

（3）图网络GN

Graph Network是比MPNN和NLNN，对GNN的更一般的总结，基本计算单元包含三个元素，节点的状态，边的状态，图的状态。GN对图里面的节点，边，图全都维护了相应的状态，这三者可分别对应节点层面的任务，边层面的任务，全图层面的任务，这也就是说GN可依据图数据以及相关任务的实际情况，对GN进行相应的简化处理。

GNN应用

网络分析

​ 在社会网络分析领域，引文网络是最为常见的数据，即节点为论文，连边关系为引用关系，常见的数据集包括Cora，DBLP，Citeseer等.这些常见的网络的数据集的描述如表1以所示。一个典型的分类任务是给定每篇文章的内容信息和文章之间的引用关系，将每篇文章分类到对应的领域中．例如，在节点的半监督分类场景下，已知节点的属性信息包括文章的标题或摘要信息，以及节点之间的引用关系构成的网络信息， 给定少量的数据标签，通过机器学习的方式，对网络中的每个节点的所属领域进行划分．在该任务中，图卷积神经网络将节点文本属性和引用网络结构有效的建模，取得了巨大的成功。

交通预测

​ 交通预测问题也是图卷积神经网络得到广泛应用的任务之一．其目的是在给定历史交通速度和路线图的情况下，预测未来的交通的速率．在交通预测问题中，节点表示在道路中放置的传感器，而边则表示节点对的物理距离．每个节点包含一个时序的特征．相比于传统的图分析问题．交通预测问题中包括时间和空间两个方面的建模，而如何利用图卷积神经网络更好地建模交通中的路网带来了机遇和挑战。

推荐系统

​ 图卷积神经网络被认为能够很好地建模图的结构属性和节点特征信息，而推荐系统既可以被视为一个矩阵补全问题， 也可以被视为是二部图（ 用户和商品） 的链接预测问题．相比传统的方法，图卷积神经网络能够更好地利用在推荐系统中普遍存在的用户属性和商品属性信息，这也是图卷积神经网络能够在推荐系统任务上引起人们广泛关注的原因。

计算机视觉

​ 图卷积神经网络在计算机视觉中的应用，主要用在少样本学习，零样本学习，点云建模等领域。在图片分类方面，主要创新在零样本学习和少样本学习上的表现，在计算机视觉领域，研究者在完成包括物体识别，图片分类，语义分割过程中，更多关注物体在少量样本或复杂语义情况下的建模和学习过程，对图关联的注意较少，而图卷积神经网络着重关注了此方面，是对图数据建模的有效方法。

自然语言处理

​ 图卷积神经网络在自然语言处理领域有大量的应用．在该领域中， 较为常见的图数据为知识图谱、句法依赖图和抽象含义表达图、词共现图以及其他方式构建的图．抽象含义表达（即AMR）是一种将一个句子的含义编码为有根有向图．在使用图卷积神经网络模型后，各项自然语言处理任务的结果都出现了一定的提升。图结构的使用，使得对象之间的复杂的语义关系得到了有效地挖掘。相比传统的对于自然语言处理的序列化建模，使用图卷积神经网络能够挖掘出非线性的复杂语义关系。

生物化学

​ 除了传统的图数据的建模外，图卷积神经网络在生物化学等领域也受到了研究人员的大量关注。相比传统的图数据的研究，在生物化学领域，人们通常将一个化学结构或一个蛋白质视为一个图，图中的节点是更小的分子，边代表键或者相互作用。