CNN已老，GNN来了！清华大学孙茂松组一文综述GNN

来源:Arxiv ,新智元

深度学习的最大软肋是什么？

这个问题的回答仁者见仁，但图灵奖得主Judea Pearl大概有99.9%的几率会说，是无法进行因果推理。

对于这个问题，业界正在进行积极探索，而其中一个很有前景的方向就是图神经网络(Graph Neural Network, GNN)。

最近，清华大学孙茂松教授组在 arXiv 发布了论文Graph Neural Networks: A Review of Methods and Applications，作者对现有的GNN模型做了详尽且全面的综述。

作者：周界*、崔淦渠*、张正彦*，杨成，刘知远，孙茂松

“图神经网络是连接主义与符号主义的有机结合，不仅使深度学习模型能够应用在图这种非欧几里德结构上，还为深度学习模型赋予了一定的因果推理能力。”论文的共同第一作者周界说。

“在深度学习方法的鲁棒性与可解释性受到质疑的今天，图神经网络可能为今后人工智能的发展提供了一个可行的方向。”

GNN最近在深度学习领域受到了广泛关注。然而，对于想要快速了解这一领域的研究人员来说，可能会面临着模型复杂、应用门类众多的问题。

“本文希望为读者提供一个更高层次的视角，快速了解GNN领域不同模型的动机与优势。”周界告诉新智元：“同时，通过对不同的应用进行分类，方便不同领域的研究者快速了解将GNN应用到不同领域的文献。”

毫不夸张地说，论文中的图表对于想要了解学习GNN乃至因果推理等方向的研究者来说，简直应该高清打印过塑然后贴在墙上以作参考——

GNN的各种变体，通过比对各自的 aggregator & updater，就能轻松分辨不同的GNN模型。这只是这篇综述强大图表的一个示例。

想要快速了解GNN，看这篇文章绝对没错

在内容上，模型方面，本文从GNN原始模型的构建方式与存在的问题出发，介绍了对其进行不同改进的GNN变体，包括如何处理不同的图的类型、如何进行高效的信息传递以及如何加速训练过程。最后介绍了几个近年来提出的通用框架，它们总结概括了多个现有的方法，具有较强的表达能力。

在应用上，文章将GNN的应用领域分为了结构化场景、非结构化场景以及其他场景并介绍了诸如物理、化学、图像、文本、图生成模型、组合优化问题等经典的GNN应用。

典型应用场景介绍

文章最后提出了四个开放性问题，包括如何处理堆叠多层GNN造成的平滑问题，如何处理动态变化的图结构，如何使用通用的方法处理非结构化的数据以及如何将其扩展到更大规模的网络上。

作者还整理了一个GNN论文列表：

https://github.com/thunlp/GNNPapers

原始GNN及其局限性

GNN的概念首先是在F. Scarselli等人的论文The graph neural network model（F. Scarselli et. al. 2009）中提出的。在这里，我们描述了原始的GNN，并列举了原始GNN在表示能力和训练效率方面的局限性。

接着，我们介绍了几种不同的GNN变体，这些变体具有不同的图形类型，利用不同的传播函数和训练方法。

最后，我们介绍了三个通用框架，分别是message passing neural network (MPNN)，non-local neural network (NLNN)，以及graph network(GN)。MPNN结合了各种图神经网络和图卷积网络方法；NLNN结合了几种“self-attention”类型的方法；而图网络GN可以概括本文提到的几乎所有图神经网络变体。

图神经网络

如前所述，图神经网络(GNN)的概念最早是Scarselli等人在2009年提出的，它扩展了现有的神经网络，用于处理图(graph)中表示的数据。在图中，每个节点是由其特性和相关节点定义的。

虽然实验结果表明，GNN是建模结构化数据的强大架构，但原始GNN仍存在一些局限性。

首先，对于固定节点，原始GNN迭代更新节点的隐藏状态是低效的。如果放宽了固定点的假设，我们可以设计一个多层的GNN来得到节点及其邻域的稳定表示。

其次，GNN在迭代中使用相同的参数，而大多数流行的神经网络在不同的层中使用不同的参数，这是一种分层特征提取方法。此外，节点隐藏状态的更新是一个顺序过程，可以从RNN内核(如GRU 和 LSTM)中获益。

第三，在边上也有一些无法在原始GNN中建模的信息特征。此外，如何学习边的隐藏状态也是一个重要的问题。

最后，如果我们把焦点放在节点的表示上而不是图形上，就不适合使用固定点，因为在固定点上的表示的分布在数值上是平滑的，区分每个节点的信息量也比较少。

图神经网络的变体

在这一节，我们提出图神经网络的几种变体。首先是在不同图类型上运行的变体，这些变体扩展了原始模型的表示能力。其次，我们列出了在传播步骤进行修改（卷积、门机制、注意力机制和skip connection）的几种变体，这些模型可以更好地学习表示。最后，我们描述了使用高级训练方法的标题，这些方法提高了训练效率。

图2概述了GNN的不同变体。

一览GNN的不同变体

图的类型(Graph Types)

在原始GNN中，输入的图由带有标签信息的节点和无向的边组成，这是最简单的图形格式。然而，世界上有许多不同的图形。这里，我们将介绍一些用于建模不同类型图形的方法。

图类型的变体

有向图(Directed Graphs )

图形的第一个变体是有向图。无向边可以看作是两个有向边，表明两个节点之间存在着关系。然而，有向边比无向边能带来更多的信息。例如，在一个知识图中，边从head实体开始到tail实体结束，head实体是tail实体的父类，这表明我们应该区别对待父类和子类的信息传播过程。有向图的实例有ADGPM (M. Kampffmeyer et. al. 2018)。

异构图(Heterogeneous Graphs)

图的第二个变体是异构图，异构图有几种类型的节点。处理异构图最简单的方法是将每个节点的类型转换为与原始特征连接的一个one-hot特征向量。异构图如GraphInception。

带边信息的图(Edge-informative Graph)

图的另外一个变体是，每条边都有信息，比如权值或边的类型。例如G2S和R-GCN。

使用不同训练方法的图变体

训练方法变体

在传播步骤进行修改的GNN变体

传播步骤变体

GNN的三大通用框架

除了图神经网络的不同变体之外，我们还介绍了几个通用框架，旨在将不同的模型集成到一个框架中。

J. Gilmer等人(J. Gilmer et. al. 2017)提出了消息传递神经网络(message passing neural network， MPNN)，统一了各种图神经网络和图卷积网络方法。

X. Wang等人(X. Wang et. al. 2017)提出了非局部神经网络(non-local neural network, NLNN)，它结合了几种“self-attention”风格的方法。

P. W. Battaglia等人(P. W. Battaglia et. al. 2018)提出了图网络(graph network, GN)，它统一了统一了MPNN和NLNN方法以及许多其他变体，如交互网络(Interaction Networks)，神经物理引擎(Neural Physics Engine)，CommNet，structure2vec，GGNN，关系网络(Relation Network)，Deep Sets和Point Net。

几个尚未解决的问题

尽管GNN在不同领域取得了巨大成功，但值得注意的是，GNN模型还不能在任何条件下，为任何图任务提供令人满意的解决方案。这里，我们将陈述一些开放性问题以供进一步研究。

浅层结构

传统的深度神经网络可以堆叠数百层，以获得更好的性能，因为更深的结构具备更多的参数，可以显著提高网络的表达能力。然而，GNN总是很浅，大多数不超过三层。

实验显示，堆叠多个GCN层将导致过度平滑，也就是说，所有顶点将收敛到相同的值。尽管一些研究人员设法解决了这个问题，但这仍然是GNN的最大局限所在。设计真正的深度GNN对于未来的研究来说是一个令人兴奋的挑战，并将对进一步深入理解GNN做出相当大的贡献。

动态图形另一个具有挑战性的问题是如何处理具有动态结构的图形。静态图总是稳定的，因此对其进行建模是可行的，而动态图引入了变化的结构。当边和节点出现或消失时，GNN不能自适应地做出改变。目前对动态GNN的研究也在积极进行中，我们认为它是一般GNN的具备稳定性和自适应性的重要里程碑。

非结构性场景

我们讨论了GNN在非结构场景中的应用，但我们没有找到从原始数据中生成图的最佳方法。在图像域中，一些研究可以利用CNN获取特征图，然后对其进行上采样，形成超像素作为节点，还有的直接利用一些对象检测算法来获取对象节点。在文本域中，有些研究使用句法树作为句法图，还有的研究采用全连接图。因此，关键是找到图生成的最佳方法，使GNN在更广泛的领域发挥更大的作用。

可扩展性问题

如何将嵌入式算法应用于社交网络或推荐系统这类大规模网络环境，是几乎所有图形嵌入算法面对的一个致命问题，GNN也不例外。对GNN进行扩展是很困难的，因为涉及其中的许多核心流程在大数据环境中都要消耗算力。

这种困难体现在几个方面：首先，图数据并不规则，每个节点都有自己的邻域结构，因此不能批量化处理。其次，当存在的节点和边数量达到数百万时，计算图的拉普拉斯算子也是不可行的。此外，我们需要指出，可扩展性的高低，决定了算法是否能够应用于实际场景。目前已经有一些研究提出了解决这个问题的办法，我们正在密切关注这些新进展。

结论

在过去几年中，GNN已经成为图领域机器学习任务的强大而实用的工具。这一进展有赖于表现力，模型灵活性和训练算法的进步。在本文中，我们对图神经网络进行了全面综述。对于GNN模型，我们引入了按图类型、传播类型和训练类型分类的GNN变体。

此外，我们还总结了几个统一表示不同GNN变体的通用框架。在应用程序分类方面，我们将GNN应用程序分为结构场景、非结构场景和其他18个场景，然后对每个场景中的应用程序进行详细介绍。最后，我们提出了四个开放性问题，指出了图神经网络的主要挑战和未来的研究方向，包括模型深度、可扩展性、动态图处理和对非结构场景的处理能力。