【GNN综述1-模型与应用】 Graph Neural Networks: A Review of Methods and Applications

最新讲解 清华刘知远等人综述：图神经网络，方法与应用 - 知乎

转载 纪厚业 并参考

详细解读和翻译见蝈蝈儿

近年来，图神经网络的研究成为深度学习领域的热点。近日，清华大学孙茂松组在 arXiv 上发布预印版综述文章 Graph Neural Networks: A Review of Methods and Applications。

此文章相比于《Deep Learning on Graphs：A Survey》而言，该文章主要针对图神经网络模型、应用的分类及需要解决的一些问题进行分析和概述。

paper对已知的图模型进行一个详细的review，主要关于其本体模型、变体(该文章在图神经网络相关内容的分类为五大类：图卷积神经网络和图注意力网络；图时域差分网络；动态图模型；图自编码器；图生成网络，分类很分散)

三大通用框架 MPNN（Message Passing Neural Network）、NLNN（Non-local Neural Network）以及 Deepmind 的 GN（Graph Network）。

对应用进行系统的分类，主要包含结构化场景、非结构化场景及其他场景下的应用及方法。

提出了四个开放性问题提：浅层层结构（深层结构会带来过平滑） 、动态图处理、非结构化场景、可扩展性方面。

除了这篇综述外，文章作者在 Github 中更新了该领域的参考文章列表（https://github.com/thunlp/GNNPapers），供各位读者参考查看。

目录

1.引言

2.模型

2.1 图分类

2.2 传播类型

2.3 训练方法

2.4 通用框架

3.GNN数学描述

4.应用

5.开放问题

5 总结

---

摘要

作者描述的核心内容有：①需要处理包含图数据的场景：许多包含丰富元素关系的任务、构建物理系统、预测蛋白质结构、疾病分类等；处理如图和文本等非结构化数据、提取结构推理等方面。②图神经网络可以通过在节点之间信息传递来捕获图之间的依赖关系，同时图从任意深度的邻居节点获取相应信息。

1.引言

作者在背景介绍方面，主要描述了图数据的普遍性和一些潜在的任务，大家做这方面的可以参考引用相关内容。此外，作者介绍了①基本的研究动机②值得研究的原因③其他的相关综述的介绍。同样的，我在这里方便大家对比查看，采用思维导图（图1）描述相关内容。

图1 Introduction

和Deep Learning on Graphs：A Survey论文中不同的分类方式，该文章在图神经网络相关内容的分类为：图卷积神经网络和图注意力网络；图时域差分网络；动态图模型；图自编码器；图生成网络等新的五个方面。但是相比于上一篇论文而言，这些点比较分散，所以为了方便同学们阅读，还是按照每一章来进行概述，涉及到相关内容的时候会再次介绍。

详细描述如下：

图是一种数据结构，它对一组对象（节点）及其关系（边）进行建模。近年来，由于图结构的强大表现力，用机器学习方法分析图的研究越来越受到重视。图神经网络（GNN）是一类基于深度学习的处理图域信息的方法。由于其较好的性能和可解释性，GNN 最近已成为一种广泛应用的图分析方法。

大量的学习任务都要求能处理包含丰富的元素间关联关系的图数据，例如物理系统建模、疾病分类以及文本和图像等非结构数据的学习等。图形神经网络（GNNs）是一种连接模型，通过图形节点之间的消息传递捕获图形的依赖性。

图（Graph）是一种对一组对象（node）及其关系（edge）进行建模的数据结构。由于图结构的强大表示能力，近年来用机器学习分析图形的研究越来越受到关注，例如社会科学中的社交网络，自然科学中的物理系统和蛋白质交互网络，以及知识图谱和许多研究领域都可以用图结构来进行表示。由于图神经网络（GNN）的高性能和高可解释性，该方法已经被广泛应用与图分析当中。

GNN 的第一个动机源于卷积神经网络（CNN）。CNN 的广泛应用带来了机器学习领域的突破并开启了深度学习的新时代。然而 CNN 只能在规则的 Euclidean 数据上运行，如图像（2 维网格）和文本（1 维序列）。如何将 CNN 应用于图结构这一非欧几里德空间，成为 GNN 模型重点解决的问题。

▲ 图1. 左：图像（欧几里得空间） 右：图（非欧几里德空间）

GNN 的另一个动机来自图嵌入（Graph Embedding），它学习图中节点、边或子图的低维向量空间表示。DeepWalk、LINE、SDNE 等方法在网络表示学习领域取得了很大的成功。然而，这些方法在计算上较为复杂并且在大规模上的图上并不是最优的，GNN 旨在解决这些问题。（该研究主要是用来学习图节点，边或子图的低维表示。在图形分析领域，传统的机器学习方法通常依赖于手工设计的特征，并且受到其不灵活性和高成本的限制。基于表示学习和词嵌入的思想，第一个基于表示学习的图嵌入方法 DeepWalk 通过应用 SkipGram 模型来生成随机游走序列，类似的方法还有 node2vec，LINE 和 TADW 。然后，这些方法有两个严重的缺点：（1）在 encoder 中，节点之间没有共享参数，这导致计算效率低下，因为这意味着参数的数量随着节点的数量线性增长；（2）直接嵌入方法缺乏泛化能力，这意味着它们无法处理动态图形或推广到新图形。）

基于 CNN 和 graph embedding，图神经网络（GNN）被提出来集体聚合来自图结构的信息。该方法可以模拟由元素及其依赖性组成的输入和输出。此外，图神经网络还可以使用 RNN 内核同时对图上的扩散过程进行建模。

图神经网络值得研究的根本原因如下：

1. CNN 和 RNN 这样的标准神经网络无法处理没有自然节点顺序的不规则图数据，而 GNN 在每个节点上分别传播，忽略了节点的输入顺序。即，GNS 的输出对于节点的输入顺序是不变的。

2. 图中的边表示了两个节点之间的依赖关系的信息。在标准的神经网络中，这些依赖信息只是作为节点的特征。然后，GNN 可以通过图形结构进行传播，而不是将其作为特征的一部分。通常，GNN 通过其邻域的状态的加权和来更新节点的隐藏状态。

3. 推理是高级人工智能的一个非常重要的研究课题，人脑中的推理过程几乎都是基于从日常经验中提取的图形。标准神经网络已经显示出通过学习数据分布来生成合成图像和文档的能力，同时它们仍然无法从大型实验数据中学习推理图。然而，GNN 探索从场景图片和故事文档等非结构性数据生成图形，这可以成为进一步高级 AI 的强大神经模型。

这篇文章对图神经网络进行了广泛的总结，并做出了以下贡献： 

• 文章详细介绍了图神经网络的经典模型。主要包括其原始模型，不同的变体和几个通用框架。

• 文章将图神经网络的应用系统地归类为结构化场景、非结构化场景和其他场景中，并介绍了不同场景中的主要应用。

• 本文为未来的研究提出四个未解决的问题。文章对每个问题进行了详细分析，并提出未来的研究方向。

2.模型

在这一章，作者主要是针对文献中关于提升图神经网络在处理非结构化数据方面的模型能力进行论述和总结。主要涵盖以下三个方面：原始（original）图神经网络相关工作、图神经网络的变种、三个通用框架（MPNN、NLNN及GN）。文中关于图的符号和表示在原文的Table.1中都阐述的比较清楚，和我之前所分享的综述区别不是很大。总结的思维导图如下图2所示。

图2 models

在这一章，可以对基本的GNN网络框架有大致的了解，涉及相关感兴趣的内容，如LSTM、GRU或者RL嵌入等可以自行研究。

详细描述如下

在模型这一部分中，文章首先介绍了最经典的图神经网络模型 GNN，具体阐述了 GNN 的模型与计算方式，然而 GNN 模型仍然存在一定的限制，比如较高的计算复杂度以及表示能力不足等等。

后续的很多工作致力于解决 GNN 存在的种种问题，在 2.2 一节中文章详细介绍了 GNN 的不同变体。具体来说，文章分别介绍了适应于不同图类型、采用不同的信息传递方式以及采用了不同的训练方法的变体。

▲ 图2. 不同的GNN变体

2.1 图分类

在 2.2.1 节中，图分类--文章介绍了处理不同图类型的 GNN 变体，包括有向图、异质图和具有边信息的图。

在原始的 GNN 中，输入的图形包括带有标签信息的节点和无向的边，这是一种最简单的图形式。但在现实生活中，存在多种图的变体，主要包括有向图、异构图和带有边信息的图。

有向图：即图中的边是存在方向的。有向边可以带来比无向边更多的信息。

异构图：即图中存在多种类型的节点。处理异构图的最简单方法是将每个节点的类型转换为与原始特征连接的 one-hot 特征向量。

带有边信息的图：即图中的每条边也存在权重或类型等信息。这种类型的图有两种解决办法，一种是将图形转化为二部图，原始边也作为节点，并将其分割成两条新的边，分别连接原始边的两端节点；第二种方法是调整不同的权重矩阵，以便在不同类型的边缘上传播。

2.2 传播类型

在 2.2.2 节中，传播类型--文章对于采用不同信息传递方式的变体进行了总结与概括。主要分为以下四个类别：

对于获取节点或者边的隐藏状态，神经网络中的传播步骤和输出步骤至关重要。在传播步骤方面的改进主要有卷积、注意力机制、门机制和跳跃连接（skip connection），而在输出步骤通常遵循简单的前馈神经网络设置。

卷积。Graph Convolutional Network（GCN）希望将卷积操作应用在图结构数据上，主要分为Spectral Method和Spatial Method（Non-spectral Method）两类。Spectral Method希望使用谱分解的方法，应用图的拉普拉斯矩阵分解进行节点的信息收集。Spatial Method直接使用图的拓扑结构，根据图的邻居信息进行信息收集。

注意力机制。Graph Attention Network 致力于将注意力机制应用在图中的信息收集阶段。

门机制。这些变体将门机制应用于节点更新阶段。Gated graph neural network 将 GRU 机制应用于节点更新。很多工作致力于将 LSTM 应用于不同类型的图上，根据具体情境的不同，可以分为 Tree LSTM、Graph LSTM 和 Sentence LSTM 等。

残差连接。注意到堆叠多层图神经网络可能引起信息平滑的问题，很多工作将残差机制应用于图神经网络中，文中介绍了 Highway GNN 和 Jump Knowledge Network 两种不同的处理方式。

2.3 训练方法

原始图卷积神经网络在训练和优化方法中具有若干缺点。例如，GCN 需要完整的图拉普拉斯算子，这对于大图来说是计算成本十分高。而且，层 (L) 的节点的嵌入是通过层 (L-1) 的所有该节点的邻居来进行计算的。因此，单个节点的感知域相对于层数呈指数增长，单个节点的计算梯度成本很高。最后，GCN 针对固定图形进行独立训练，缺乏归纳学习的能力。

该方面的改进主要是提出了以下方法：

W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” NIPS 2017, pp. 1024–1034, 2017.

J. Chen, T. Ma, and C. Xiao, “Fastgcn: fast learning with graph convolutional networks via importance sampling,” arXiv preprint arXiv:1801.10247, 2018.

W. Huang, T. Zhang, Y. Rong, and J. Huang, “Adaptive sampling towards fast graph representation learning,” in NeurIPS 2018, 2018, pp. 4563–4572.

J. Chen, J. Zhu, and L. Song, “Stochastic training of graph convolutional networks with variance reduction.” in ICML 2018, 2018, pp. 941–949.

Q. Li, Z. Han, and X.-M. Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” arXiv preprint arXiv:1801.07606, 2018.

文章还对于不同的信息传递方式进行了公式化总结。简单来说，信息传递函数主要包括信息收集（agggregation）和节点信息更新（update）两个部分，在表格中列出了每种方法的不同配置。

▲ 表1. 采用不同消息传递函数的GNN变体总结

在 2.2.3 节中，文章介绍了 GNN 的不同训练方法。譬如 GraphSAGE 从附近的邻居收集信息，并且能够应用于 inductive learning 领域；FastGCN 使用了 importance sampling 的方法，使用采样替代使用节点所有的邻居信息，加快了训练过程。 

2.4 通用框架

在 2.3 节中，文章介绍了近年来文献中提出的图神经网络通用框架 MPNN（Message Passing Neural Network）、NLNN（Non-local Neural Network）以及 Deepmind 的 GN（Graph Network）

MPNN 将模型总结为信息传递阶段和节点更新阶段，概括了多种图神经网络和图卷积神经网络方法。NLNN 总结了很多种基于自注意力机制的方法。GN 提出了更加通用的模型，能够总结概括几乎所有文中提到的框架，并且拥有更加灵活的表示能力、易于配置的块内结构以及易于组合的多模块架构。

▲ 图3. GN Block组合成复杂网络结构

a. MPNN利用了不同地GNN和GCN（graph convolutionnetwork）方法；

针对图结构的监督学习框架，MPNN框架抽象了几种最流行的图形结构数据模型（如图卷积中的光谱方法和非光谱方法，门控神经网络，交互网络，分子图卷积，深度张量神经网络等）之间的共性，
b. NLNN利用了几种“self-attention”（自注意力）类型的方法；

NLNN利用深度学习捕捉长范围的依赖关系，这是对非局部平均运算 3 的一种泛化，非局部运算通过计算对所有位置的特征的加权和来得到当前位置的影响，此处的位置集合可以是空间、时间或者时空。
c. GN概括了本文中提到的几乎所有图形神经网络变体

GN被提出来泛化和扩展多种图神经网络，以及 MPNN 和 NLNN 方法。本文主要介绍了图的定义、GN block、核心 GN 计算单元、计算步骤和基本设计原则。详细的内容扩展会另外写到专门针对该文献的阅读笔记当中。

3.GNN数学描述

参考

状态由自身节点状态+自身特征决定

输出由状态+邻居特征决定

4.应用

该章主要从三种场景来概括GNN的常见应用：结构化场景（数据有明确的关系结构）、非结构化场景（关系结构不明确）、其他应用场景（如组合优化或者生成模型）。其相关应用的总结可以参考原作中的Table.3，内容主要包含：文本类、图像类、化学类、知识图谱、组合优化及图生成等。这一章的内容比较简单，也是方便大家参考如何结合实际的应用场景应用自己的算法或者理论，依照惯例，思维导图如下图3所示。

图3 application

详细描述如下

GNN 被应用在众多的领域，文章具体将应用分为了结构化场景、非结构化场景以及其他三个类别。

在结构化场景中，GNN 被广泛应用在社交网络、推荐系统、物理系统、化学分子预测、知识图谱等领域。文章中主要介绍了其在物理、化学、生物和知识图谱中的部分应用。

在非结构领域，文章主要介绍了在图像和文本中的应用。在其他领域，文章介绍了图生成模型以及使用 GNN 来解决组合优化问题的场景。

▲ 图4. GNN的应用示例

图形神经网络已经在监督，半监督，无监督和强化学习设置的广泛问题领域中进行了探索，这里仅列举了一些代表性的应用。

▲ 表2. 文章介绍的应用总结

5.开放问题

文章在最后一章提出了四个开放性问题：①图神经网络结构比较浅，如何加深层数并且避免过平滑；②动态图问题；③非结构化场景下，进一步优化算法和模型；④伸缩性，主要由于：图都是非常规欧式空间数据，每个节点的邻居节点不同；计算整个图的拉普拉斯矩阵成本昂贵；我们需要指定相应的尺度变换规模，否则难以正常应用。

尽管现在很多算法都在图神经网络上发挥了作用，但是优化的空间还很大，和实际结合的能力还需要进一步提升，这些都可以作为我们硕士期间、博士期间的研究课题

详细描述如下

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

文章最后提出了图神经网络领域的四个开放问题：

1. 浅层结构。经验上使用更多参数的神经网络能够得到更好的实验效果，然而堆叠多层的 GNN 却会产生 over-smoothing 的问题。具体来说，堆叠层数越多，节点考虑的邻居个数也会越多，导致最终所有节点的表示会趋向于一致。

传统的深度神经网络可以堆叠数百层以获得更好的性能，因为更深的结构具有更多的参数，从而能够显著提高表示能力。而图神经网络通常都很浅，大多数不超过三层。正如 5 中的实验所示，堆叠多个 GCN 层将导致过度平滑，也就是说，所有顶点将收敛到相同的值。尽管一些研究人员设法解决了这个问题6，7，但它仍然是 GNN 的最大限制。设计真正的深度 GNN 对于未来的研究来说是一个令人兴奋的挑战，并将对理解 GNN 做出相当大的贡献。

2. 动态图。目前大部分方法关注于在静态图上的处理，对于如何处理节点信息和边信息随着时间步动态变化的图仍是一个开放问题。

另一个具有挑战性的问题是如何处理具有动态结构的图形。静态图是稳定的，因此可以容易地建模，而动态图则引入变化的结构。当边和节点出现或消失时，GNN 无法自适应地更改。
动态 GNN 正在积极研究中，我们认为它是一般 GNN 的稳定性和适应性的重要里程碑。

3. 非结构化场景。虽然很多工作应用于非结构化的场景（比如文本），然而并没有通用的方法用于处理非结构化的数据。

虽然我们已经讨论了 GNN 在非结构场景中的应用，但我们发现没有最佳方法可以从原始数据生成图形。因此，找到最佳图形生成方法将提供 GNN 可以做出贡献的更广泛的领域。

4. 扩展性。虽然已经有一些方法尝试解决这个问题，将图神经网络的方法应用于大规模数据上仍然是一个开放性问题。

如何在社交网络或推荐系统等网络规模条件下应用嵌入方法对于几乎所有图形嵌入算法来说都是一个致命的问题，而 GNN 也不例外。扩展 GNN 很困难，因为许多核心步骤在大数据环境中的计算成本都十分高。

5 总结

在过去的几年中，图形神经网络已成为图域中机器学习任务的强大而实用的工具。这一进展归功于表达能力，模型灵活性和训练算法的进步。在本次调查中，我们对图神经网络进行了全面的分析。对于 GNN 模型，我们引入了按图类型，传播类型和训练类型分类的变体。此外，我们还总结了几个统一表示不同变体的一般框架。在应用程序分类方面，我们将 GNN 应用程序划分为结构场景，非结构场景和其他场景，然后对每个场景中的应用程序进行详细介绍。最后，我们提出了四个开放性问题，指出了图神经网络的主要挑战和未来研究方向，包括模型深度，可扩展性，处理动态图和非结构场景的能力。