A Comprehensive Survey on Graph Neural Networks

2019-01-03

× 文章目录

图神经网络模型综述 (2019-1-2) A Comprehensive Survey on Graph Neural Networks.

A Comprehensive Survey on Graph Neural Networks Zonghan Wu, Shirui Pan, Member, IEEE Chengqi Zhang, Senior Member, IEEE Philip S. Yu, Fellow, IEEE

摘要

近年来, 深度学习彻底改变了许多机器学习任务, 从图像分类和视频处理到语音识别和自然语言理解. 这些任务中的数据通常表示在欧几里德空间中. 然而, 越来越多的应用程序从非欧几里德域生成数据, 并表示为具有复杂关系和相互依赖性的图结构. 图数据的复杂性给现有的机器学习算法带来了重大挑战. 最近, 出现了许多关于扩展图形数据的深度学习方法的研究. 在本次调查中, 我们提供了数据挖掘和机器学习领域中图神经网络 (GNN) 的全面概述. 我们提出了一种新的分类法, 将最先进的图神经网络划分为不同的类别. 着眼于图卷积网络, 我们回顾了最近开发的替代架构; 这些学习范例包括图注意网络 (graph attention networks), 图自动编码器 (graph autoencoders), 图生成网络 (graph generative networks) 和图时空网络 (graph spatial-temporal networks). 我们进一步讨论了图神经网络在各个领域的应用, 并总结了现有算法在不同学习任务中的开源代码和基准. 最后, 我们在这个快速发展的领域提出潜在的研究方向.

引言

尽管深度学习已经在欧几里得数据中取得了很大的成功, 但从非欧几里得域生成的数据已经取得更广泛的应用, 它们需要有效分析. 例如, 在电子商务领域, 一个基于图的学习系统能够利用用户和产品之间的交互以实现高度精准的推荐. 在化学领域, 分子被建模为图, 新药研发需要测定其生物活性. 在论文引用网络中, 论文之间通过引用关系互相连接, 需要将它们分成不同的类别.
图数据的复杂性对现有机器学习算法提出了重大挑战, 因为图数据是不规则的. 每张图大小不同、节点无序, 一张图中的每个节点都有不同数目的邻近节点, 使得一些在图像中容易计算的重要运算 (如卷积) 不能再直接应用于图. 此外, 现有机器学习算法的核心假设是实例彼此独立. 然而, 图数据中的每个实例都与周围的其它实例相关, 含有一些复杂的连接信息, 用于捕获数据之间的依赖关系, 包括引用、朋友关系和相互作用.
最近, 越来越多的研究开始将深度学习方法应用到图数据领域. 受到深度学习领域进展的驱动, 研究人员在设计图神经网络的架构时借鉴了卷积网络、循环网络和深度自编码器的思想. 为了应对图数据的复杂性, 重要运算的泛化和定义在过去几年中迅速发展. 例如, 图 1 展示了受标准 2D 卷积启发得到的图卷积.

图神经网络简史

图神经网络的概念首先由 Gori 等人 (2005) 提出, 并由 Scarselli 等人 (2009) 进一步阐明. 这些早期的研究以迭代的方式通过循环神经架构传播邻近信息来学习目标节点的表示, 直到达到稳定的固定点. 该过程所需计算量庞大, 而近来也有许多研究致力于解决这个难题. 在本文中, 图神经网络代表的是所有用于图数据的深度学习方法.
受到卷积网络在计算机视觉领域所获巨大成功的激励, 近来出现了很多为图数据重新定义卷积概念的方法. 这些方法属于图卷积网络 (GCN) 的范畴. Bruna 等人 (2013) 提出了关于图卷积网络的第一项重要研究, 他们基于谱图论 (spectral graph theory) 开发了一种图卷积的变体. 自此, 基于谱的图卷积网络不断拓展、进阶. 由于谱方法通常同时处理整个图, 并且难以并行或扩展到大图上, 基于空间的图卷积网络开始快速发展. 这些方法通过聚集近邻节点的信息, 直接在图结构上执行卷积. 结合采样策略, 计算可以在一批 (batch) 更新的节点而不是在整个图中操作, 这种做法有望提高效率. 除了图卷积网络, 近几年还开发出了很多其他可选择的图神经网络. 这些方法包括图注意力网络 (GAT) 、图自编码器、图生成网络以及图时空网络.

图神经网络 vs. 网络嵌入

对图神经网络的研究与图嵌入或网络嵌入紧密相关, 这也是数据挖掘和机器学习社区日益关注的一个话题. 网络嵌入旨在通过保留网络拓扑结构和节点内容信息, 将网络顶点表示到低维向量空间中, 以使任何后续的图分析任务 (如分类、聚类和推荐) 都可以通过使用简单的现成学习机算法 (如用于分类的支持向量机) 轻松执行. 许多网络嵌入算法都是无监督算法, 它们大致可分为三组, 即矩阵分解、随机游走和深度学习方法. 用于网络嵌入的深度学习方法同时还属于图神经网络, 包括基于图自编码器的算法 (如 DNGR和 SDNE) 和具有无监督训练的图卷积神经网络 (如 GraphSage). 图 2 描述了本文中网络嵌入和图神经网络的区别.

分类与框架

这一部分内容给出了图神经网络的分类方法. 我们考虑到了所有能与神经架构组合成图神经网络的可微图模型, 把图神经网络最终分类为：图卷积网络、图注意力网络、图自编码器、图生成网络和图时空网络. 这些网络中, 图卷积网络在捕捉网络结构依存关系上扮演着核心角色. 如下图 3 所示, 属于其他类别的方法部分使用图卷积网络作为基础.

分类

Graph Convolution Networks (GCN)

GCN 的关键是学习一个函数 $ f $ 通过节点 $ v_i $ 自己的特征 $ X_i $ 和邻接点特征 $ X_j, j \in N(v_i) $ 来学习节点的表示. 下图 4 展示了 GCN 的学习过程, 通过从邻域聚合特征信息, 一个 GCN 层把每个节点的隐藏表征进行压缩. 在特征聚合之后, 非线性变换被应用到聚合后的输出上. 通过多层堆叠, 每个节点的最终隐藏表征获得了更深层次的邻域信息.

GCN 是很多 GNN 模型的基础, 图 5 展示了一些基于 GCN 的 GNN 模型.

Graph Attention Networks (GAT)

GAT 和 GCN 类似都是聚合邻居特征 (无论是通过直接融合邻接点信息亦或是随机游走得到的子图信息), 只不过其引入了 Attention 机制, 为重要的节点分配更高的权重 (通过端到端模型学习获取), 下图 6 展示了 GAT 和 GCN 的区别.

Graph Auto-encoders (GAE)

GAE 则是以一种非监督方式通过 encoder 获取低维的节点表示, 通过 decoder 重构图, GAE 是最受欢迎的图嵌入方法. 从最初的直接使用邻接矩阵作为 encoder 输入并重构, 演化到输入邻接矩阵并捕获一阶、二阶特征, 再到对属性图以 GCN 作为 encoder 的构建块、以链路预测作为 decoder 重构图的方法.

Graph Generative Networks (GGN)

GGN 则是想从图数据中生成出合理的结构, 有直接对节点和边信息进行交替分解生成的方法, 也有通过对抗网络生成的方法. 这方面的工作主要贡献在于化合物合成, 生成合理结构的过程就是新的化合物组合的过程.

Graph Spatial-temporal Networks

图时空网络旨在从时空图中学习未知的模式, 这在许多应用中越来越重要, 如交通预测和人类活动预测. 图时空网络的关键思想是同时考虑空间依赖和时间依赖, 许多当前的方法应用 GCN 来捕获依赖性以及一些 RNN 或 CNN 来模拟时间依赖性.

框架

图卷积是端到端训练框架. 图卷积网络可以以 (半) 监督或纯无监督的方式在端到端学习框架中训练, 依赖于学习任务和可用的标签信息.
节点级分类的半监督学习:
给定部分节点被标记的单个网络, 图卷积网络可以学习到一个鲁棒的模型, 高效识别未标记节点的类别标签. 为此, 可以通过堆叠一系列的图卷积层和 softmax 层来建立端到端框架进行多类别分类.
图级分类的监督学习:
给定一个图数据集, 图级分类旨在预测整个图的类别标签. 这一任务的端到端学习可以利用一个结合了图卷积层和池化步骤的框架实现.
图嵌入的无监督学习:
如果图中无可用类别标签, 我们可以在一个端到端框架中以完全无监督的方式学习图嵌入. 这些算法通过两种方式利用边级 (edge-level) 信息. 一种简单的方法是采用自编码器框架, 其中编码器使用图卷积层将图嵌入 latent representation 中, 然后使用解码器重构图结构. 另一种方法是利用负采样方法, 采样一部分节点对作为负对 (negative pair) , 而图中已有的节点作为正对 (positive pair). 然后在卷积层之后应用 logistic 回归层, 以用于端到端学习.

图卷积网络 (Graph Convolutional Networks)

本节概览图卷积网络 (GCN) , 这是很多复杂图神经网络模型的基础. GCN 方法分为两类, 分别基于谱和空间. 基于谱的方法通过从图信号处理的角度引入滤波器来定义图卷积, 其中图卷积运算被解释为从图信号中去除噪声. 基于空间的方法将图卷积表征为聚合来自近邻的特征信息. 虽然 GCN 在节点级别上运行, 但是图池化模块可以与 GCN 层交替, 将图粗粒化为高级子结构. 如图 5a 所示, 这种架构设计可用于提取图级表征、执行图分类任务. 图卷积网络包括基于谱、空间的 GCN.

基于谱的图卷积网络 (Spectral-based Graph Convolutional Networks)

基于谱的 GCN 方法基于图的拉普拉斯矩阵进行操作, 这类方法包括 Spectral CNN、Chebyshev Spectral CNN (ChebNet)、First order of ChebNet (1stChebNet) 和 Adaptive Graph Convolution Network (AGCN).
基于谱的 GCN 依赖于拉普拉斯矩阵的特征分解, 这对模型有着三点重要的影响:

对图的任何扰动都会导致特征基 (eigen basis) 的变化;
学习得到的 filters 是依赖于域的, 这意味着它们不能应用于具有不同结构的图;
特征分解需要 $ O(N^3) $ 的时间复杂度和 $ O(N^2) $空间复杂度.
由 ChebNet 和 1stChebNet 定义的 filter 是局部共享的, 其学习到的权重参数可以在图中的不同位置共享. 然而, 谱方法的一个共同缺点是它们需要将整个图加载到内存中以执行图卷积, 这在处理大图时是低效的.

基于空间的图卷积网络 (Spatial-based Graph Convolutional Networks)

基于空间的方法通过聚合来自邻居的特征信息来定义图卷积. 根据堆叠图卷积层的不同方式：基于循环的空间图卷积 (Recurrent-based Spatial GCN) 和 基于组合的空间图卷积 (Composition Based Spatial GCN). 前者包括图神经网络 (Graph Neural Networks, GNN) 、门控图神经网络 (Gated Graph Neural Networks, GGNN) 和随机稳态嵌入 (Stochastic Steady-state Embedding, SSE); 后者涉及了：Message Passing Neural Networks (MPNN)、GraphSage. 两者的区别如下图 7 所示, 基于循环的空间图卷积方法堆叠相同的卷积层以求更新隐状态, 而基于组合的图卷积方法堆叠不同的卷积层来更新隐状态. 此外, 还包括两大类之外的一些变体模型, 包括 Diffusion Convolution Neural Networks (DCNN)、PATCHY-SAN、Large-scale Graph Convolution Networks (LGCN)、Mixture Model Network (MoNet).

基于循环的方法试图获得节点的稳定状态, 基于组合的方法试图结合更高阶的邻域信息. 在每个卷积层中, 两者都必须在训练期间更新所有节点上的隐藏状态. 但是由于它们必须将所有中间状态存储到内存中, 因此不具备高效率. 为了解决这个问题, 已经提出了几种训练策略, 包括基于组合方法的子图训练 (sub-graph training) 模型 GraphSage 和基于循环方法的随机异步训练模型如 SSE.

基于谱和空间的 GCN 比较

基于谱和空间的 GCN 模型总结如下表

1、就效率而言, 基于谱的模型的计算成本随着图大小增加而急剧增加, 因为它们需要同时处理整个图执行特征向量计算, 这使得它们难以并行或扩展到大图形. 基于空间的模型具有处理大图的潜力, 因为它们通过聚合邻居节点直接在图域中执行卷积. 可以按批处理节点进行计算而不是在整个图上. 当邻居节点数量增加时, 则可以使用采样技术以提高效率.

2、在推广性方面, 基于谱的模型假定了一个固定大小的图, 使得它们对新的或不同大小的图的推广性很差. 另一方面, 基于空间的模型在每个节点上局部执行图卷积, 其卷积核权重可以容易地在不同位置和结构之间共享.

3、就灵活性而言, 基于谱的模型仅限于在无向图上工作. 在有向图上没有关于拉普拉斯矩阵的明确定义, 因此将基于谱的模型应用于有向图的唯一方法是将有向图转移到无向图. 基于空间的模型更灵活地处理多种输入, 例如边特征和边方向, 因为这些输入可以合并到聚合函数中.

因此, 近年来空间模型引起了越来越多的关注.

其他图神经网络(Beyond Graph Convolutional Networks)

本节概述了图卷积网络之外的其他图神经网络, 包括图注意力神经网络、图自编码器、图生成模型和图时空网络. 下表总结了每个类别下的主要方法, A 表示属性图 (attributed graphs), D 表示有向图, S 表示时空图 (spatial-temporal graphs).

图注意力网络 (Graph Attention Networks)

注意力机制几乎成为序列任务中的标配. 它的价值在于能够聚焦于对于不同对象最重要的部分. 该机制被证明在多项任务中有用, 如机器翻译和自然语言理解. 由于注意力机制的模型容量越来越大, 图神经网络在聚合信息、集成多个模型的输出、生成重要性导向的随机游走时, 可以从注意力机制中获益良多.

这部分介绍了图注意力网络的多种方法, 包括:

图注意力网络 (Graph Attention Network, GAT) :
GAT 是基于空间的图卷积模型, 在聚合邻接点的特征信息时, GAT 为不同的邻接点分配不同的注意力权重, 为了学习不同邻接点的权重, 采用 multi-heads 注意力机制.
门控注意力网络 (Gated Attention Network, GAAN) :
GAAN 同样采用 multi-heads 注意力机制, 不同于 GAT, GAAN 不是简单的为每个 head 分配相同的权重, 而是进一步引入了 self-Attention 机制为不同的 head 学习出相应的权重.
图注意力模型 (Graph Attention Model, GAM) :
GAM 是一个时序模型用于处理图分类任务, GAM 自适应的访问一个重要节点序列, 其定义为: $h_t = f_h(f_s(r_{t-1}, v_{t-1}, g, \theta_s), h_{t-1}, \theta_h)$ $ f_h $ 是 LSTM 网络, $ f_s $ 是步进网络 (step network) 从单前节点 $ v_{t-1} $ 跳转到一个邻接点 $ c_t $, 跳转时优先考虑具有更高重要性即具有关于 $ v_{t-1} $ 有着更高相关性得分 $ r_t $ 的节点.
注意力游走 (Attention Walks, AW) :
AW 模型不是真的在图中进行游走, 而是对共现矩阵 (co-occurance matrix) $ D $ 以不同的注意力权重进行分解 $E[D] = \tilde{P}^{(0)} \sum_{k=1}^{C} \alpha_k (P)^k$ 其中 $ \tilde{P}^{(0)} $ 是初始的节点位置矩阵, $ P $ 是概率转移矩阵.

注意力机制对图神经网络的贡献有三部分, 即在聚合特征信息时向不同近邻分配注意力权重、根据注意力权重集成多个模型, 以及使用注意力权重引导随机游走. 尽管我们把 GAT 和 GAAN 分类为图注意力网络的两种方法, 但是它们都可以作为基于空间的卷积网络. 二者的优势是它们可以适应性地学习近邻的重要性权重. 但是, 由于我们必须计算每对近邻之间的注意力权重, 因此计算成本和内存消耗会快速增长.

图自动编码器 Graph Auto-Encoders

图自编码器是一类网络嵌入方法, 旨在通过神经网络架构将网络顶点表征到低维向量空间. 典型的解决方案是使用多层感知机作为编码器来获取节点嵌入, 解码器重建节点的近邻统计, 如正逐点互信息 (positive pointwise mutual information, PPMI, 衡量两个事物之间的相关性) 或一阶、二阶接近度 (proximities). 最近, 研究人员尝试在设计图自编码器时用 GCN 作为编码器、结合 GCN 和 GAN, 或者结合 LSTM 和 GAN.

基于 GCN 的自编码器模型包括：

图自编码器 (Graph Auto-encoder, GAE):
GAE 是第一个把 GCN 引入编码器模型的, 使用 GCN 作为 encoder, 最小化重构误差.
对抗正则化图自编码器 (Adversarially Regularized Graph Autoencoder, ARGA):
采用生成对抗网络 (GAN) 的训练方案来规范图自动编码器. 在 ARGA 中, 编码器将节点的结构信息及其特征编码为 GCN 的隐藏表示, 并且解码器从编码器的输出重建邻接矩阵. GAN 在训练生成模型中在生成器和鉴别器之间进行 “最小 - 最大化” 游戏. 生成器生成尽可能真实的 “伪样本”, 而鉴别器尽可能将 “伪样本” 与真实样本区分开来. GAN 帮助 ARGA 规范学习到的节点隐藏表示以遵循先验分布, 即作为生成器工作的编码器试图使学习节点隐藏表示与实际先验分布无法区分. 另一方面, 鉴别器试图识别节点隐藏表示是从编码器中习得的还是真实的先验分布.
其他变体包括：
具备对抗正则化自编码器的网络表征 (Network Representations with Adversarially Regularized Autoencoders, NetRA):
NetRA 也是图自动编码器框架与 ARGA 有着相似的想法, 同样进行节点隐藏表示正则化, 通过对抗性训练使其符合的先验分布. 只不过不是重建邻接矩阵, 而是通过 Seq2Seq 架构重构从随机游走中采样的节点序列.
用于图表征的深度神经网络 (Deep Neural Networks for Graph Representations, DNGR):
DGNR 使用堆叠去噪自编码器重构正逐点互信息 PPMI, 堆叠去噪自动编码器能够学习数据背后的高度非线性规律性. 与传统的神经自动编码器不同, 它通过将输入随机切换为零来增加输入噪声. 学习的潜在表示更加健壮, 尤其是在输入存在缺失值的情况下.
结构化深度网络嵌入 (Structural Deep Network Embedding, SDNE):
SDNE 使用堆叠自编码器同时保留一、二阶邻近度, 其一阶邻近度定义如下: $L_{1st} = \sum_{i,j = 1}^{n} A_{i,j} || h_i^{(k)} - h_j^{(k)} ||^2$ 用两个节点的隐向量距离拟合一阶邻近度, 其二阶邻近度定义如下: $L_{2nd} = \sum_{i = 1}^{n} || (\hat{x_i} - x_i) \odot b_i||^2$ 用节点的输入表示和输出表示的距离拟合而阶邻近度以保留其邻居结构信息. $ b_i $ 是 0 项惩罚以解决稀疏问题.
深度递归网络嵌入 (Deep Recursive Network Embedding, DRNE):
DRNE 直接基于邻接点隐向量来重构节点隐向量. $L = \sum_{v \in V} || h_v - aggregate(h_u | u \in N(v))||^2$

DNGR 和 SDNE 仅基于拓扑结构学习节点嵌入, 而 GAE、ARGA、NetRA 和 DRNE 需要基于拓扑信息和节点内容特征学习节点嵌入. 图自编码器的一个挑战是邻接矩阵的稀疏性, 会导致解码器正条目 (positive entry) 的数量远远少于负条目. 为了解决这个问题, DNGR 重建了一个较稠密的矩阵——PPMI 矩阵, SDNE 对邻接矩阵的零条目进行惩罚, GAE 重新调整邻接矩阵中项的权重, NetRA 将图线性化为序列.

图生成网络 (Graph Generative Networks)

图生成网络的目标是基于一组可观察图来生成图. 其中的很多方法都是领域特定的. 例如, 在分子图生成方面, 一些研究将分子图的表征建模为字符串 “SMILES”. 在自然语言处理中, 生成语义图或知识图通常需要一个给定的句子. 最近, 研究人员又提出了多个通用方法. 一些研究将生成过程看成节点或边的形成, 而另一些则使用生成对抗训练. 该领域的方法要么使用 GCN 作为构造块, 要么使用不同的架构.

图生成网络主要分为基于 GCN 的图生成网络和其他图生成网络. 前者包括：分子生成对抗网络 (Molecular Generative Adversarial Networks, MolGAN) 和深度图生成模型 (Deep Generative Models of Graphs, DGMG) ；后者涉及 GraphRNN (通过两级循环神经网络使用深度图生成模型) 和 NetGAN (结合 LSTM 和 Wasserstein GAN 从基于随机游走的方法中生成图).

图时空网络 (Graph Spatial-Temporal Networks)

图时空网络同时捕捉时空图的时间和空间依赖. 时空图具备全局图结构, 每个节点的输入随着时间而改变. 例如在交通网络中, 使用每个传感器作为节点来连续记录某条道路的交通流动速度, 其中交通网络的边由传感器对之间的距离决定. 图时空网络的目标是预测未来节点值或标签, 或预测时空图标签. 近期研究探索了仅使用 GCN、结合 GCN 和 RNN 或 CNN, 以及专用于图结构的循环架构.

图时空网络主要分为基于 GCN 的图时空网络和其他图时空网络. 前者包括：Diffusion Convolutional Recurrent Neural Network (DCRNN)、CNN-GCN、时空 GCN (Spatial Temporal GCN, ST-GCN). 其他方法有 Structural-RNN, 一种循环结构化框架.

DCRNN 的优势是能够处理长期依赖, 因为它具备循环网络架构. 尽管 CNN-GCN 比 DCRNN 简单一些, 但 CNN-GCN 能够更高效地处理时空图, 这要归功于 1D CNN 的快速实现. 时空 GCN 将时间流作为图的边, 这导致邻接矩阵的大小呈平方增长. 一方面, 它增加了图卷积层的计算成本. 另一方面, 要捕捉长期依赖, 图卷积层必须多次堆叠. StructuralRNN 在同一个语义组内共享相同的 RNN, 从而改善了模型效率, 但是 StructuralRNN 需要人类先验知识来分割语义组.

未来研究方向

1、加深网络
深度学习的成功在于深度神经架构. 例如在图像分类中, 模型 ResNet 具有 152 层. 但在图网络中, 实证研究表明, 随着网络层数增加, 模型性能急剧下降. 根据论文, 这是由于图卷积的影响, 因为它本质上推动相邻节点的表示更加接近彼此, 所以理论上, 通过无限次卷积, 所有节点的表示将收敛到一个点. 这导致了一个问题：加深网络是否仍然是学习图结构数据的好策略？

2、感受野
节点的感受野是指一组节点, 包括中心节点和其近邻节点. 节点的近邻（节点）数量遵循幂律分布. 有些节点可能只有一个近邻, 而有些节点却有数千个近邻. 尽管采用了采样策略, 但如何选择节点的代表性感受野仍然有待探索.

3、可扩展性
大部分图神经网络并不能很好地扩展到大型图上. 主要原因是当堆叠一个图卷积的多层时, 节点的最终状态涉及其大量近邻节点的隐藏状态, 导致反向传播变得非常复杂. 虽然有些方法试图通过快速采样和子图训练来提升模型效率, 但它们仍无法扩展到大型图的深度架构上.

4、动态性和异质性
大多数当前的图神经网络都处理静态同质图. 一方面, 假设图架构是固定的. 另一方面, 假设图的节点和边来自同一个来源. 然而, 这两个假设在很多情况下是不现实的. 在社交网络中, 一个新人可能会随时加入, 而之前就存在的人也可能退出该社交网络. 在推荐系统中, 产品可能具有不同的类型, 而其输出形式也可能不同, 也许是文本, 也许是图像. 因此, 应当开发新方法来处理动态和异质图结构.