A Comprehensive Survey on Graph Neural Networks（图神经网络的综合研究）

近年来，深度学习彻底改变了很多机器学习任务，从图像分类，视频处理到语音识别、自然语言处理等，但是通常来说，这些任务的数据都是欧式数据。现实中，很多数据都是非线性的，不是欧式数据，因此被表示为数据之间复杂关系和相互依赖的图结构。图数据的复杂性给现有的机器学习算法带来了重大挑战。最近，出现了许多关于扩展图数据的深度学习方法的研究。本文对图神经网络（GNNs）在数据挖掘和机器学习方面的应用做了全面.

lijfrank

2220人浏览 · 2019-07-10 22:15:08

lijfrank · 2019-07-10 22:15:08 发布

近年来，深度学习彻底改变了很多机器学习任务，从图像分类，视频处理到语音识别、自然语言处理等，但是通常来说，这些任务的数据都是欧式数据。现实中，很多数据都是非线性的，不是欧式数据，因此被表示为数据之间复杂关系和相互依赖的图结构。
图数据的复杂性给现有的机器学习算法带来了重大挑战。最近，出现了许多关于扩展图数据的深度学习方法的研究。本文对图神经网络（GNNs）在数据挖掘和机器学习方面的应用做了全面概述。
提出一种新的分类方法对GNNs各种方法进行分类。着眼于图卷积网络(GCN),回顾了一些最近提出来的新的架构，包括Graph attention networks（图注意力网络），Graph autoencoders（图自编码），Graph generative networks（图生成网络）以及Graph spatial-temporal networks（图时空网络）。
另外，进一步讨论了图神经网络在各个领域的应用，总结了现有算法在不同任务中的开源代码，并提出了领域的潜在研究方向。

1 简介

神经网络近期的成功推动了模式识别和数据挖掘的研究，许多机器学习任务，例如目标检测，机器翻译，语音识别，曾经都严重依赖棘手的特征工程提取数据集的特征，现在已经被端到端的学习模式彻底改变，也就是卷积神经网络（CNN），长短时记忆网络（LSTM），和自编码（AE）。深度学习在许多领域的成功部分归功于快速发展的计算资源(如GPU)和大量训练数据，部分归功于深度学习从欧氏数据(如图像、文本和视频)中提取有效的数据表示。以图像分析为例，图像为欧式空间的规则表示，CNN能够利用图像数据的平移不变性，局部连结性和组合性，也就是CNN能够为各种图像分析任务提取整个数据集共享的局部特征。
深度学习在欧式数据上取得了巨大的成功，但是，越来越多的应用需要对非欧式数据进行分析。例如，在电子商务中，一个基于图的学习系统能够利用用户与商品之间的交互做出非常准确的推荐；在化学中，需要识别被建模为图结构的分子的生物活性以发现新的药物；在引文网络中，论文需要通过被引用的关系相互连接，然后通过挖掘关系被分成不同的组。**图数据不规则，每个图的无序节点大小是可变的，且每个结点有不同数量的邻居结点，因此一些重要的操作如卷积能够在图像数据上轻易计算，但是不适用于图数据，可见图数据的复杂性给现有的机器学习算法带来了巨大的挑战。**此外，现有的机器学习算法假设数据之间是相互独立的，但是，图数据中每个结点都通过一些复杂的连接信息与其他邻居相关，这些连接信息用于捕获数据之间的相互依赖关系，包括，引用，关系，交互。
近年来，人们对扩展基于图数据的深度学习越来越感兴趣。在深度学习的驱动下，研究人员借鉴 CNN,LSTM,深度AE的思想设计了图神经网路的架构。为了处理复杂的图数据，在过去几年中，对重要算子的泛化和定义发展越来越快。例如，图1说明了图卷积算子是如何受标准2-D卷积算子的启发的。本文对图神经网络进行了一个全面的概述。
在这里插入图片描述
图 1 2-D卷积和图卷积

1.1 GNN简史

图神经网络的表示法最早在Gori等(2005)[16]中提出，在Scarselli等(2009)[17]中进一步阐述。这些早期的研究通过迭代的方式，利用循环神经结构传播邻居信息，直到达到一个稳定的不动点，来学习目标节点的表示。这些过程计算代价大，因此很多研究在克服这些困难[18],[19].本文推广图神经网络术语表示所有的针对图数据的深度学习方法。
受CNN在计算机视觉领域巨大成功的启发，很多方法致力于重新定义卷积算子，这些方法都属于图卷积网络（GCN）。Bruna et al.(2013)首次基于谱图理论[20]设计了一种图卷积的变体，自此，基于谱图的卷积网络[12]、[14]、[21]、[22]、[23]的改进、扩展和逼近越来越多。但是谱图方法一般同时处理整个图，而且难以并行处理或缩放，所以近年来基于空间的图卷积[24], [25], [26], [27]发展越来越快。这些方法通过聚集节点信息直接在图域进行卷积。结合抽样策略，计算可以在批节点而不是整个图[24]，[27]上进行，能够减少计算复杂度。
近年来，除了图形卷积网络外，还出现了许多新的图形神经网络。这些方法包括图注意网络(GAN)、图的自动编码器(GAE)、图的生成网络(GGN)和图时空网络(GSTN)。

1.2 GNN的相关研究

相关的GNN综述很少，Bronstein et al.[8]使用几何深度学习的符号，概述了非欧式域的深度学习方法，包括图形和流形。因为是先驱性工作，所以漏掉了几个重要的基于空间的方法，包括[15]、[19]、[24]、[26]、[27]、[28]。此外，本研究未涵盖一些新开发的架构，而这些架构对于GCN同样重要。本文对图注意网络(GAN)、图的自动编码器(GAE)、图的生成网络(GGN)和图时空网络(GSTN)等学习范式进行了综合评述。 Battaglia等人[29]将位置图网络作为构建块学习关系数据，使用统一的框架对部分神经网络做了回顾。但是，这个泛化的网络高度抽象，对原始论文中的方法阐述不足。Lee等人[30]对GNN的分支GAT部分进行了总结。最近，张[31]等对GNN做了一个最近的研究，但是缺少对GGN和GSTN的研究。综上，现有GNN方面的综述都不完整。

1.3 GNN vs 网络嵌入

GNN的研究与图嵌入或网络嵌入密切相关，是数据挖掘和机器学习[32],[33],[34],[35],[36],[37]日益关注的另一个课题。网络嵌入致力于在一个低维向量空间进行网络节点表示，同时保护网络拓扑结构和节点的信息，便于后续的图像分析任务，包括分类，聚类，推荐等，能够使用简单现成的机器学习算法（例如，使用SVM分类）。许多网络嵌入算法都是典型的无监督算法，它们可以大致分为三种类型[32]，即，矩阵分解[38]、[39]、随机游走[40]、深度学习。基于深度学习的网络嵌入属于GNN，包括图自编码算法，基于无监督训练的图卷积神经网络。图2描述了网络嵌入和GNN的区别。
在这里插入图片描述
图2 网络嵌入 VS GNN 图3 GNN分类

1.4 文章的创新性

新的分类方法
提出新的GNN算法分类，分为五种类型GCN,GAN,GAE,GGN,GSTN。同时文章分析了网络嵌入和GNN的区别，并展示了GNN架构之间的联系。
综合性调研
对每种具有代表性的算法进行详细的描述，并进行相应的比较和总结，是目前为止最详细的概述。
丰富的资源
提供了丰富的GNN资源，包括最先进的算法，基准数据集，公开源码，实际应用。
未来方向
对现有算法的局限性进行了研究，并提出该领域可能的发展方向。

2 基本的图概念的定义

本文中和GNN有关的符号定义如下：
|符号|含义|符号|含义||--|--|--|--||| | |
图：图 $G = (V, E, A)$ ,其中V节点集合，E边集合，A邻接矩阵。 $v_{i} \in V$ 描述一个点， $e_{i j}=\left(v_{i}, v_{j}\right) \in E$ 描述两个节点之间的边，A是一个 $\times N$ 的矩阵，其中
$A_{i j}=\left\{\begin{array}{ll}{w_{i j}} & {\text { if } \quad e_{i j}=\left(v_{i}, v_{j}\right) \in E} \\ {0} & {\text {if } e_{i j} \notin E}\end{array}\right.$
连接一个节点的边是一个节点的度，degree $\left(v_{i}\right)=\sum A_{i}$ .
图与节点属性X关联， $\in R^{N \times D}$ 是一个特征矩阵，且 $X_{i} \in R^{D}$ 表示节点 $v_{i}$ 的特征向量。当D=1D=1时， $\in R^{N}$ 表示图的特征向量。
有向图：
有向图中所有边都是从一个节点指向另一个节点。对于有向图， $ij\neq A ji$ 。无向图是所有边都无方向的图。对于无向图， $A i j = A j i$ 。
时空图:
时空图是一种特征矩阵X随时间变化的图， $G = (V, E, A, X)$ ，其中 $\in R^{T \times N \times D}$ ，T是时间步长。

3 GNN分类和框架

本节介绍文章对GNN分类的方法，将任何可微分模型（包含了神经结构）作为GNN。将GNN分为五种类型GCN,GAN,GAE,GGN,GSTN。其中GCN在捕获结构依赖性方面起到了重要作用，如图3所示(1.3节中)，其他的方法都部分利用了GCN作为构建模型的块。表2总结了每一类方法的代表性方法。
表2 GNN分类的代表性方法
在这里插入图片描述

3.1 GNNs分类

**GCNs：**GCNs将传统数据的卷积算子泛化到图数据，这个算法的关键是学习一个函数 $f$ ，能够结合 $v_i$ 邻居节点的特征 $X_j$ 和其本身特征 $X_i$ 生成 $v_i$ 的新表示， $j∈N(v_i)$ 。图4展示了GCNs的节点表示学习。图5展示了一些基于GCN的图神经网络模型。
在这里插入图片描述

图5 基于GCN构建的不同网络

GAN： GAN与GCN类似，致力于寻找一个聚合函数，融合图中相邻的节点，随机游动和候选模型，学习一种新的表示。关键区别是：GAN使用注意力机制为更重要的节点，步或者模型分配更大的权重，权重个网络一起学习。图6展示了GCN和GAN在聚合邻居节点信息时候的不同。
在这里插入图片描述
图6 GCN和GAN的不同图7 基于循环和基于组合的GCN
(GCN边的权重是一个固定的值，GAN是通过端到端的网络结构学习，因此重要的点权重更大)

GAE： GAE是一种无监督学习框架，通过编码器学习一种低维点向量，然后通过解码器重构图数据。GAE是一种常用的学习图嵌入的方法，既适用于无属性信息[41]、[42]的普通图，还适用于是有属性图[61]、[62]。对于普通的图，大多数算法直接预先得到一个邻接矩阵，或者构建一个信息丰富的矩阵，也就是点对互信息矩阵，或者邻接矩阵填充自编码模型，并捕获一阶和二阶信息[42]。对于属性图，图自编码模型利用GCN[14]作为一个构建块用于编码，并且通过链路预测解码器[59],[61]重构结构信息。
GGN： GGN旨在从数据中生成可信的信息，生成给定图经验分布的图从根本上来说是具有挑战性的，主要因为图是复杂的数据结构。为了解决这个问题，研究员探索了将交替形成节点和边作为生成过程的因素，并借助[66],[67]作为训练过程。GGN一个很有前途的应用领域是化合物合成。在化学图中，视原子为节点，化学键为边，任务是发现具有一定化学和物理性质的可合成的新分子。
GSTN： GSTN从时空图中学习不可见的模式，在交通预测和人类活动预测等应用中越来越重要。例如，底层道路交通网络是一个自然图，其中每个关键位置是一个节点，它的交通数据是被连续监测的。通过建立有效的GSTN，能够准确预测整个交通的系统的交通状态[70],[71]。GSTN的核心观点是，同时考虑空间依赖性和时间依赖性。目前很多方法使用GCNs捕获依赖性，同时使用RNN[70],或者CNN[71]建模时间依赖关系。

3.2 框架

GNN，尤其是GCN，通过用谱图理论和空间局部性重新定义图卷积，试图在图数据上重复CNN的成功。使用图结构和节点信息作为输入，GCN的输出能够利用以下的一种机制用于不同的图分析任务：

Node-level输出用于点回归和分类任务。图卷积模型直接给定节点的潜在表示，然后一个多层感知机或者softmax层用作GCN最后一层。
Edge-level输出与边分类和链路预测任务相关。为了预测一条边的便签或者连接强度，附加函数从图卷积模型中提取两个节点的潜在表示作为输入。
Graph-level输出和图分类任务相关，池化模块用于粗话一个图为子图或者对节点表示求和/求平均，以获得图级别上的紧凑表示。

表3列出了主要GCNs方法的输入和输出。特别对每种方法的GCN层和最后一层之间的输出机制进行了总结。输出机制可能涉及几个池化操作，建在后面讨论。
表3 GCN 总结
在这里插入图片描述
端到端训练框架：GCN可以在端到端学习框架中进行(半)监督或无监督的训练，取决于学习任务和标签信息的可用性。

node-level半监督分类。给定一个部分节点被标记而其他节点未标记的网络，GCN可以学习一个鲁棒的模型，有效地识别未标记节点[14]的类标签。为此，可以构建一个端到端的多分类框架，通过叠加几个图形卷积层，紧跟着一个softmax层。
graph-level监督分类。给定一个图数据集，图级分类旨在预测整个图[55]，[56]，[74]，[75]的类标签(s)，端到端学习框架，通过结合GCN和池化过程[55,56]实现。具体的，通过GCN获得每个图里每个节点固定维数的特征表示，然后，通过池化求图中所有节点的表示向量的和，以得到整个图的表示。最后，加上多层感知机和softmax层，可以构造一个端到端的图分类。图5（a）展示了这样一个过程。
无监督图嵌入。图中没有标签数据的时候，可以在端到端的框架中以无监督的方式学习一种图嵌入。这些算法以两种方式利用边级信息。一种简单的：利用自编码框架，编码器利用GCN将图嵌入到潜在的表示中，解码器利用潜在的表示重构图结构[59,61]。另一种方式：利用负采样方法，抽取一部分节点对作为负对，图中剩余的节点对作为正对，之后利用逻辑回归层，形成一个端到端的学习框架[24]。

4 图卷积网络

GCNs分为两类：spectral-based 和spatial-based，Spectral-based方法从图信号处理的角度[76]引入滤波器来定义图卷积，此使图卷积被解释为从图信号中去除噪声。Spatial-based的方法将图卷积表示为来自邻居节点的特征信息的结合。GCNs在节点级作用时，图池化模块可以与GCN交错定义，将图粗话为高水平子结构。如图5（a）所示，这样一个结构设计能够提取图水平的表示并用于图分类任务。