【图深度学习时代降临】清华朱文武组一文综述GraphDL五类模型

2019 年 1 月 7 日 新智元

新智元报道

来源：arxiv 编辑：文强，肖琴，金磊

【新智元导读】今天新智元介绍清华大学朱文武教授组的一篇预印版综述论文，全面回顾图(graph)深度学习，从半监督、无监督和强化学习三大角度，系统介绍了GNN、GCN、图自编码器(GAE)等5大类模型及其应用和发展。

要说最近学界值得关注的趋势，图神经网络(Graph Neural Network, GNN)或者说图深度学习(Graph Deep Learning)绝对算得上一个。

昨天，阿里巴巴达摩院发布2019十大技术趋势，其中就包括“超大规模图神经网络系统将赋予机器常识”：

单纯的深度学习已经成熟，而结合了深度学习的图神经网络将端到端学习与归纳推理相结合，有望解决深度学习无法处理的关系推理、可解释性等一系列问题。强大的图神经网络将会类似于由神经元等节点所形成网络的人的大脑，机器有望成为具备常识，具有理解、认知能力的AI。

此前，新智元曾经报道过清华大学孙茂松教授组对图神经网络(GNN)的综述(arxiv预印版)，全面阐述了GNN及其方法和应用，便于读者快速了解GNN领域不同模型的动机与优势。

今天，新智元再介绍另一篇清华大学与GNN有关的综述，这次是朱文武教授组发布在arxiv的预印版论文 Deep Learning on Graphs: A Survey。

作者：张子威，崔鹏，朱文武

在这项工作中，作者全面回顾了应用于图(graph)的各种深度学习方法，从以下三方面系统阐述这些方法及其差异：

半监督方法，包括图神经网络(GNN)和图卷积网络(GCN)
无监督方法，包括图自动编码器(GAE)
最新进展，包括图递归神经网络（Graph RNN）和图强化学习(Graph RL)

从互联网、供应链、化合物的分子结构、感染的传播途径，到世界上最复杂的结构——人脑神经系统，都可以用图(Graph)来表示。

然而，由于图的特殊性，将其应用于深度学习并非易事。图深度学习的潜力巨大已无需赘言，想要快速入门并掌握相关线索，这无疑又是一份极好的资料。

作者在论文中写道，

我们的研究与已有文献的不同之处在于，我们系统而全面地回顾了Graph的不同深度学习架构，而不是专注于一个特定的分支。

其次，我们关注的是不同的深度学习模型可以如何应用于图，这与传统的网络嵌入不同。后者指将节点嵌入到低维向量空间中，可以被视为图深度学习的具体例子(而且它们也可以使用非深度学习方法)。

关于网络嵌入，可以参考朱文武老师组另一篇综述：Peng Cui, Xiao Wang, Jian Pei, Wenwu Zhu. A Survey on Network Embedding. IEEE TKDE, 2018”

论文(点击“阅读原文”访问)：https://arxiv.org/pdf/1812.04202v1.pdf

以下是新智元对这篇综述的摘译。

三大角度，全面回顾图深度学习(GraphDL)

在过去10年中，深度学习一直是人工智能和机器学习领域“皇冠上的明珠”，在声学、图像和自然语言处理中表现出优越的性能。深度学习从底层数据提取复杂模式的表达能力已经得到充分认识。

另一方面，图(graph) [注1：“图”(Graphs)也被称为“网络”(networks)，本文交替采用这两个术语] 在现实世界中无处不在，它代表着各种对象及其相互关系，如社交网络、电子商务网络、生物网络和交通网络。

图具有复杂的结构，其中包含丰富的潜在价值。

因此，如何利用深度学习方法进行图数据分析，在过去的几年里引起了相当多的研究关注。

这个问题非常重要，因为将传统的深度学习架构应用到图中存在几个挑战:

不规则域(Irregular domain)。与图像、音频、文本等具有清晰网格结构的数据不同，图处于不规则的域中，使得很难将一些基本的数学运算推广到图中。例如，卷积神经网络(CNN)中的基本操作“卷积”和“池化”，在图数据中并不能直接地定义。这通常被称为几何深度学习问题。

不同的结构和任务。图本身具有复杂的结构。例如，图可以是异质的或同质的，加权的或不加权的，有符号的或无符号的。此外，图的任务也有很大的不同，可以是node-focused问题，如节点分类和链接预测，也可以是graph-focused问题，如图分类和图生成。不同的结构和任务需要不同的模型架构来处理特定的问题。

可扩展性和并行化。在大数据时代，真实的图很容易就会有数百万个节点和边，例如社交网络或电子商务网络。因此，如何设计具有线性时间复杂度的可扩展模型，成为一个关键问题。此外，由于图的节点和边是相互连接的，通常需要作为一个整体进行建模，因此，如何进行并行计算是另一个关键问题。

跨学科性。图常常与其他学科相关联，例如生物学、化学或社会科学。跨学科性既带来机遇，也带来了挑战：领域知识可以被用来解决特定的问题，但是集成领域知识可能使得模型设计更加困难。例如，在生成分子图(molecular graphs)时，目标函数和化学约束通常是不可微的，因此不容易应用基于梯度的训练方法。

为了应对这些挑战，研究人员在这一领域做出了巨大的努力，产生了丰富的相关论文和方法的文献。采用的架构也有很大的差异，从监督到无监督，从卷积到递归。然而，据我们所知，很少有人系统地总结这些不同方法之间的差异和联系。

本文试图通过对图深度学习方法进行全面回顾来填补这一空白。

如图1所示，我们将现有的方法分为三大类：半监督方法、无监督方法和最近的进展。

图1：图深度学习方法的分类

具体来说，半监督方法包括图神经网络(GNN)和图卷积网络(GCN)；无监督方法主要有图自编码器(GAE)；最近的进展包括图递归神经网络和图强化学习。

那么这些分类有什么区别呢？先看下这张表：

一些图深度学习方法的主要区别

从广义上来看，GNN和GCN是半监督的，因为它们利用节点属性和节点标签来针对特定任务端到端地训练模型参数。

而GAE主要关注学习使用无监督方法的表示。最新提出的方法则使用其他一些独特算法。

在接下来的部分，我们将详细介绍这些方法，主要介绍它们的发展历史，以及这些方法如何解决图的挑战。我们还分析了这些模型之间的差异，以及如何组合不同的架构。最后，我们简要概述了这些方法的应用，并讨论了未来的研究方向。

清晰图表，详尽阐述 GNN、GCN、GAE等5类模型

图神经网络(GNN)

图神经网络是图数据最原始的半监督深度学习方法。

GNN的思路很简单：为了编码图的结构信息，每个节点可以由低维状态向量表示。对于以图为中心的任务，建议添加一个特殊节点，这个节点具有与整个图相对应的唯一属性。

回顾过去，GNN统一了一些处理图数据的早期方法，如递归神经网络和马尔可夫链。

展望未来，GNN中的概念具有深远的启示：许多最先进的GCN实际上遵循与邻近节点交换信息的框架。事实上，GNN和GCN可以统一到一个通用框架中，GNN相当于GCN使用相同层来达到的稳定状态。

从概念角度来看，GNN是非常重要的，但它也有几个缺点：

首先，在其计算过程中，公式(具体公式可查看原文)中的映射必须是压缩映射，这就严重限制了建模能力。

其次，由于在梯度下降步骤之间需要许多迭代，因此GNN在计算上的代价是昂贵的。

或许是因为这些原因，GNN并未被社区所熟知。

图卷积网络(GCN)

除了GNN，图卷积网络(GCN)是图的另一类半监督方法。由于GCN通常可以像标准的CNN那样通过反向传播来训练特定任务的损失，所以本文主要关注其采用的体系结构。

下表总结了本文所研究的GCN的主要特征：

不同图卷积网络之间的比较

可以看到在本文所研究的22种GCN方法中，从类型角度看分为两种，一种是光谱域(Spectral)、另一种是空间域(Spatial)。

在卷积操作过程中，每种方法所采用的技术也大不相同，主要包括插值核(Interpolation Kernel)、多项式、First-order以及Random Walk等等。

在Readout方面，主要包括分层聚类、分层聚类+FC、Set2set等等技术。当然在在可扩展性、节点特征以及其它改进方面也各不相同。

图自编码器(GAE)

自编码器(AE)和变分自编码器(VAE)广泛应用于无监督学习中，它们适用于学习无监督信息的图节点表示。下表总结了本文所研究的GAE主要特征：

不同GAE之间的比较

可以看到，在本文所研究的10种GAE方法中，7种属于自编码器(AE)、3种属于变分自编码器(VAE)。

每种方法采用的降维方法也有所不同，主要包括L2-Reconstruction、拉普拉斯特征映射(Laplacian Eigenmap)、递归Reconstruction、排序、GAN等等。

在可扩展性、节点特征以及其它改进方面也各不相同。

除了上述两个主要分类外，也有一些进展值得讨论。

首先是对抗性训练方案，尤其是生成对抗网络(GAN)，这是最近机器学习领域的一个热门话题。

GAN的基本思想是构建两个相关联的模型，一个判别器和一个生成器。生成器的目的是通过产生假数据来“欺骗”判别器，判别器的目的是区分样本是真实数据还是由生成器产生的假数据。然后，两个模型可以通过极大极小博弈进行联合训练，从而相互受益。

S. Pan等人 [83]将对抗训练方案作为一个额外的正则化项纳入GAE。整个架构如图9所示。具体来说，编码器用作生成器，判别器的目的是区分潜在表示是来自生成器还是来自先验分布。这样，自动编码器就被强制匹配先验分布以作为正则化。

图9：文献[83]中ARGA/ARVGA的框架

最新的进展

除了前面提到的半监督方法和无监督方法之外，我们在这一节中还讨论了一些最新的高级方法。它们的主要特性如表5所示。

表5：一些最新进展的主要特性

图递归神经网络

递归神经网络(RNN)，例如GRU或LSTM是建模序列数据的一个实际标准，在GNN中用于模拟节点状态。

RNN也可以用于图级别。为了消除歧义，我们将这种架构称为Graph RNNs。

You et al. [94]将Graph RNN应用于图生成问题。具体来说，他们采用两个RNN，一个用于生成新的节点，另一个用于以自回归的方式为新添加的节点生成边。结果表明，与传统的基于规则的图生成模型相比，这种分层RNN结构在具有可接受的时间复杂度的同时，能够有效地从输入图中学习。

动态图神经网络(Dynamic Graph Neural Network, DGNN)[95]提出利用 time-aware LSTM[100]来学习动态图中的节点表示。作者表明， time-aware LSTM可以很好地建模边形成的顺序和时间间隔，从而有利于图的广泛应用。

也可以将Graph RNN与其他架构(如GCN或GAE)结合使用。例如RMGCNN[96]将LSTM应用于GCN的结果，逐步重构图，如图10所示，旨在解决图的稀疏性问题。Dynamic GCN[97]应用LSTM在动态网络中收集不同时间片段的GCN结果，目的是获取空间和时间图信息。

图10：RMGCNN的框架

图强化学习

GCPN[98]利用RL生成目标导向的分子图，以处理不可导目标和约束。实验结果证明了GCPN在各种图生成问题中的有效性。

MolGAN[99]也采用了类似的思想，即使用RL生成分子图。MolGAN建议直接生成完整的图，而不是通过一系列的动作来生成图，这对小分子很有效。

基于图的深度学习的应用和未来方向

应用

除了标准图推理等任务，如节点分类或图分类，基于深度学习的方法也已经应用于广泛的学科，如建模社会影响、推荐、化学、物理、疾病或药物预测、自然语言处理、计算机视觉、交通预测、程序归纳、以及求解基于图的NP问题。

这些应用还表明，基于图的深度学习不仅有助于挖掘现有图数据背后的丰富价值，而且还通过将关系数据自然地建模为图，有助于推进其他学科的发展，极大地扩大了基于图的深度学习的适用性。

以下几个正在进行或未来的方向值得关注：

不同类型的图。由于图数据结构极其不同，现有的方法无法处理所有的图数据。下一个重要的方向是设计特定的深度学习模型来处理这些不同类型的图。

动态图。大多数现有方法关注于静态图。然而，许多真实图本质上是动态的，其中节点、边及其特征可以随着时间的推移而改变。例如，在社交网络中，人们可能建立新的社会关系，删除旧的关系，他们所扮演的角色，例如爱好和职业可以随着时间的推移而改变。新用户可以加入网络，老用户可以离开。如何对动态图的演化特征进行建模，并支持模型参数的增量更新，在很大程度上仍是未解决的问题。