2020必火的图神经网络（GNN）是什么？有什么用？

作者： 刘忠雨、 李彦霖、 周洋

来源：大数据DT（ID：hzdashuju）

01 图的基本定义

图（Graph）是一个具有广泛含义的对象。在数学中，图是图论的主要研究对象；在计算机工程领域，图是一种常见的数据结构；在数据科学中，图被用来广泛描述各类关系型数据。许多图学习的理论都专注于图数据相关的任务上。

通常，图被用来表示物体与物体之间的关系。 这在生活中有着非常多的现实系统与之对应，比如化学分子、通信网络、社交网络等。事实上，任何一个包含二元关系的系统都可以用图来描述。因此，研究并应用图相关的理论，具有重大的现实意义。

本文，我们主要对图相关的概念做一些基础介绍，包括图的基本定义、图在计算机中的存储表示方法与遍历方法、图数据及其常见的应用场景、图数据深度学习的浅述。

在数学中，图由 顶点 （Vertex）以及连接顶点的 边 （Edge）构成。顶点表示研究的对象，边表示两个对象之间特定的关系。

图可以表示为顶点和边的集合，记为G = (V, E)，其中V是顶点集合，E是边集合。同时，我们设图G的顶点数为N，边数为M（如无特殊说明，本文中的图均如此表示）。一条连接顶点vi, vj∈V的边记为（vi, vj）或者eij。如图1-1所示，V = {v1, v2, v3, v4, v5}，E = {(v1, v2), (v1, v3), (v2, v4), (v2, v3), (v3, v4), (v4, v5)}。

▲图1-1 图G的定义

02 图的基本类型

1. 有向图和无向图

如果图中的边存在方向性，则称这样的边为有向边eij = ，其中vi是这条有向边的起点，vj是这条有向边的终点，包含有向边的图称为有向图，如图1-2所示。与有向图相对应的是无向图，无向图中的边都是无向边，我们可以认为无向边是对称的，同时包含两个方向：eij = = = eji。

▲图1-2 有向图

2. 非加权图与加权图

如果图里的每条边都有一个实数与之对应，我们称这样的图为加权图，如图1-3所示，该实数称为对应边上的权重。在实际场景中，权重可以代表两地之间的路程或运输成本。一般情况下，我们习惯把权重抽象成两个顶点之间的连接强度。与之相反的是非加权图，我们可以认为非加权图各边上的权重是一样的。

▲图1-3 加权图

3. 连通图与非连通图

如果图中存在孤立的顶点，没有任何边与之相连，这样的图被称为非连通图，如图1-4所示。相反，不存在孤立顶点的图称为连通图。

▲图1-4 非连通图

4. 二部图

二部图是一类特殊的图。我们将G中的顶点集合V拆分成两个子集A和B，如果对于图中的任意一条边eij均有vi∈A，vj∈B或者vi∈B，vj∈A，则称图G为二部图，如图1-5所示。二部图是一种十分常见的图数据对象，描述了两类对象之间的交互关系，比如：用户与商品、作者与论文。

▲图1-5 二部图

03 图数据的应用场景

我们提到图，更多的是带有一种数学上的理论色彩，在实际的数据场景中，我们通常将图称为 网络 （Network），与之对应的，图的两个要素（顶点和边）也被称为 节点 （Node）和 关系 （Link），比如我们熟知的社交网络、物流网络等概念名词。

为了达成统一并与 神经网络 （Neural Networks）中的“网络”概念区分开来（尽管神经网络也是一种网络）。

图数据是一类比较复杂的数据类型，存在非常多的类别。这里我们介绍其中最重要的4类： 同构图 （Homogeneous Graph）、 异构图 （Heterogeneous Graph）、 属性图 （Property Graph）和 非显式图 （Graph Constructed from Non-relational Data）。

1. 同构图： 同构图是指图中的节点类型和关系类型都仅有一种。同构图是实际图数据的一种最简化的情况，如由超链接关系所构成的万维网，这类图数据的信息全部包含在邻接矩阵里。

2. 异构图： 与同构图相反，异构图是指图中的节点类型或关系类型多于一种。在现实场景中，我们通常研究的图数据对象是多类型的，对象之间的交互关系也是多样化的。因此，异构图能够更好地贴近现实。

3. 属性图： 相较于异构图，属性图给图数据增加了额外的属性信息，如图1-9所示。对于一个属性图而言，节点和关系都有标签（Label）和属性（Property），这里的标签是指节点或关系的类型，如某节点的类型为“用户”，属性是节点或关系的附加描述信息，如“用户”节点可以有“姓名”“注册时间”“注册地址”等属性。属性图是一种最常见的工业级图数据的表示方式，能够广泛适用于多种业务场景下的数据表达。

4. 非显式图： 非显式图是指数据之间没有显式地定义出关系，需要依据某种规则或计算方式将数据的关系表达出来，进而将数据当成一种图数据进行研究。比如计算机3D视觉中的点云数据，如果我们将节点之间的空间距离转化成关系的话，点云数据就成了图数据。

▲图1-9 属性图

在我们研究多元化对象系统的时候，图是一种非常重要的视角。在现实世界中，图数据有着十分广泛的应用场景。下面我们举几个例子进行说明，如图1-10所示。

▲图1-10 图数据应用示例 ^{[1, 19]} 

• 社交网络

社交网络是十分常见的一类图数据，代表着各种个人或组织之间的社会关系。 如图1-10的a图展示了在线社交网络中的用户关注网络：以用户为节点，用户之间的关注关系作为边。这是一个典型的同构图，一般用来研究用户的重要性排名以及相关的用户推荐等问题。

随着移动互联网技术的不断深入，更多元化的媒体对象被补充进社交网络中，比如短文本、视频等，如此构成的异构图可以完成更加多样化的任务。

• 电子购物

电子购物是互联网中的一类核心业务，在这类场景中， 业务数据通常可以用一个用户–商品的二部图来描述 ，在如图1-10的b图所展示的例子中，节点分为两类：用户和商品，存在的关系有浏览、收藏、购买等。

用户与商品之间可以存在多重关系，如既存在收藏关系也存在购买关系。 这类复杂的数据场景可以用属性图轻松描述。 电子购物催生了一项大家熟知的技术应用—推荐系统。用户与商品之间的交互关系，反映了用户的购物偏好。例如，经典的啤酒与尿布的故事：爱买啤酒的人通常也更爱买尿布。

• 化学分子

以原子为节点，原子之间的化学键作为边，我们可以将分子视为一种图数据进行研究，分子的基本构成以及内在联系决定了分子的各项理化性质，通常我们用其指导新材料、新药物的研究任务，如图1-10的c图所示。

• 交通网络

交通网络具有多种形式，比如地铁网络中将各个站点作为节点，站点之间的连通性作为边构成一张图，如图1-10的d图所示。通常在交通网络中我们比较关注的是路径规划相关的问题：比如最短路径问题，再如我们将车流量作为网络中节点的属性，去预测未来交通流量的变化情况。

• 场景图

场景图是图像语义的一种描述方式，它将图像中的物体当作节点，物体之间的相互关系当作边构成一张图。场景图可以将关系复杂的图像简化成一个关系明确的语义图。 场景图具有十分强大的应用场景，如图像合成、图像语义检索、视觉推理等。

图1-10的e图所示为由场景图合成相关语义图像的示例，在该场景图中，描述了5个对象：两个男人、一个小孩、飞盘、庭院以及他们之间的关系，可以看到场景图具有很强的语义表示能力。

• 电路设计图

我们可以将电子器件如谐振器作为节点，器件之间的布线作为边将电路设计抽象成一种图数据。在参考文献 ^[1] 中，对电路设计进行了这样的抽象，如图1-10的f图所示，然后基于图神经网络技术对电路的电磁特性进行仿真拟合，相较于严格的电磁学公式仿真，可以在可接受的误差范围内极大地加速高频电路的设计工作。

图数据的应用场景远不止这些，还有诸如描述神经网络计算过程的计算图、传感器阵列网络、由各类智能传感器构成的物联网。事实上，如果要找一种最具代表性的数据描述语言与现实数据对应，那么图应该是最具竞争力的候选者。 总的来说，图数据的应用跨度大、应用场景多，研究图数据具有广泛且重要的现实意义。

04 图数据深度学习

作为一种重要的数据类型，图数据的分析与学习的需求日益凸显，许多 图学习 （Graph Learning）的理论均专注于图数据相关的任务学习。

谱图理论 （Spectral Graph Theory） ^[2] 是将图论与线性代数相结合的理论，基于此理论发展而来的谱聚类相关算法 ^[3] ，可以用来解决图的分割或者节点的聚类问题。

统计关系学习 （Statistical Relational Learning） ^[4] 是将关系表示与似然表示相结合的机器学习理论，区别于传统的机器学习算法对数据 独立同分布 （independent and Identically Distributed，数据对象是同类且独立不相关的）的假设，统计关系学习打破了对数据的上述两种假设，对图数据的学习具有更好的契合度。

为了更加贴合实际场景中的异构图数据， 异构信息网络 （Heterogeneous Information Network） ^[5] 分析被提出，用以挖掘异构图中更加全面的结构信息和丰富的语义信息。

由于这些年深度学习在实际应用领域取得的巨大成就，表示学习和端对端学习的概念日益得到重视，为了从复杂的图数据中学习到包含充分信息的向量化表示，出现了大量网络表示学习（Network Embedding） ^[6] 的方法。然而网络表示学习很难提供表示学习加任务学习的端对端系统，基于此， 图数据的端对端学习系统仍然是一个重要的研究课题。

由于图数据本身结构的复杂性，直接定义出一套支持可导的计算框架并不直观。与图数据相对应的数据有图像、语音与文本，这些数据是定义在欧式空间中的规则化结构数据，基于这些数据的张量计算体系是比较自然且高效的。

图1-11给出了图数据与其他几类常见类型数据的对比。图像数据呈现出规则的2D栅格结构，这种栅格结构与卷积神经网络的作用机制具有良好的对应。文本数据是一种规则的序列数据，这种序列结构与循环神经网络的作用机制相对应。

▲图1-11 图像和语音文本数据类型

受 图信号处理 （Graph Signal Processing） ^[7] 中对图信号卷积滤波的定义的启发，近几年发展出了一套基于图卷积操作并不断衍生的神经网络理论。本文将这类方法统称为 图神经网络 （Graph Neural Network，GNN ^[8-10] ）。下面我们简述其发展历程。

2005年，Marco Gori等人发表论文 ^[11] ，首次提出了图神经网络的概念。在此之前，处理图数据的方法是在数据的预处理阶段将图转换为用一组向量表示。这种处理方法最大的问题就是图中的结构信息可能会丢失，并且得到的结果会严重依赖于对图的预处理。GNN的提出，便是为了能够将学习过程直接架构于图数据之上。

随后，其在2009年的两篇论文 ^{[12, 13]} 中又进一步阐述了图神经网络，并提出了一种监督学习的方法来训练GNN。但是，早期的这些研究都是以迭代的方式，通过循环神经网络传播邻居信息，直到达到稳定的固定状态来学习节点的表示。这种计算方式消耗非常大，相关研究开始关注如何改进这种方法以减小计算量。

2012年前后，卷积神经网络开始在视觉领域取得令人瞩目的成绩，于是人们开始考虑如何将卷积应用到图神经网络中。2013年Bruna等人首次将卷积引入图神经网络中，在引文 ^[14] 中基于频域卷积操作的概念开发了一种图卷积网络模型，首次将可学习的卷积操作用于图数据之上。

自此以后，不断有人提出改进、拓展这种基于频域图卷积的神经网络模型。但是基于频域卷积的方法在计算时需要同时处理整个图，并且需要承担矩阵分解时的很高的时间复杂度，这很难使学习系统扩展到大规模图数据的学习任务上去，所以基于空域的图卷积被提出并逐渐流行。

2016年，Kipf等人 ^[15] 将频域图卷积的定义进行简化，使得图卷积的操作能够在空域进行，这极大地提升了图卷积模型的计算效率，同时，得益于卷积滤波的高效性，图卷积模型在多项图数据相关的任务上取得了令人瞩目的成绩。

近几年，更多的基于空域图卷积的神经网络模型的变体 ^[16-18] 被开发出来，我们将这类方法统称为GNN。 各种GNN模型的出现，大大加强了学习系统对各类图数据的适应性，这也为各种图数据的任务学习奠定了坚实的基础。

自此，图数据与深度学习有了第一次真正意义上的结合。GNN的出现，实现了图数据的端对端学习方式，为图数据的诸多应用场景下的任务，提供了一个极具竞争力的学习方案。

在本文的最后，我们给出图数据相关任务的一种分类作为结尾。

1. 节点层面（Node Level）的任务

节点层面的任务主要包括分类任务和回归任务。这类任务虽然是对节点层面的性质进行预测，但是显然不应该将模型建立在一个个单独的节点上，节点的关系也需要考虑。节点层面的任务有很多，包括学术上使用较多的对论文引用网络中的论文节点进行分类，工业界在线社交网络中用户标签的分类、恶意账户检测等。

2. 边层面（Link Level）的任务

边层面的任务主要包括边的分类和预测任务。边的分类是指对边的某种性质进行预测；边预测是指给定的两个节点之间是否会构成边。常见的应用场景比如在社交网络中，将用户作为节点，用户之间的关注关系建模为边，通过边预测实现社交用户的推荐。目前，边层面的任务主要集中在推荐业务中。

3. 图层面（Graph Level）的任务

图层面的任务不依赖于某个节点或者某条边的属性，而是从图的整体结构出发，实现分类、表示和生成等任务。目前，图层面的任务主要应用在自然科学研究领域，比如对药物分子的分类、酶的分类等。

参考文献

[1] Zhang G, He H, Katabi D. Circuit-GNN: Graph Neural Networks for Distributed Circuit Design[C]//International Conference on Machine Learning. 2019: 7364-7373.

[2] F. R. Chung. Spectral Graph Theory. American Mathematical Society, 1997.

[3] Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4): 395-416.

[4] Koller D, Friedman N, D~eroski S, et al. Introduction to statistical relational learning[M]. MIT press, 2007.

[5] Shi C, Li Y, Zhang J, et al. A survey of heterogeneous information network analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 29(1): 17-37.

[6] Cui P, Wang X, Pei J, et al. A survey on network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(5): 833-852.

[7] Shuman D I, Narang S K, Frossard P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE signal processing magazine, 2013, 30(3): 83-98.

[8] Zhou J, Cui G, Zhang Z, et al. Graph neural networks: A review of methods and applications[J]. arXiv preprint arXiv:1812.08434, 2018.

[9] Zhang Z, Cui P, Zhu W. Deep learning on graphs: A survey[J]. arXiv preprint arXiv:1812.04202, 2018.

[10] Wu Z, Pan S, Chen F, et al. A comprehensive survey on graph neural networks[J]. arXiv preprint arXiv:1901.00596, 2019.

[11] Gori M, Monfardini G, Scarselli F. A new model for learning in graph domains[C]//Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. IEEE, 2005, 2: 729-734.

[12] Micheli A. Neural network for graphs: A contextual constructive approach[J]. IEEE Transactions on Neural Networks, 2009, 20(3): 498-511.

[13] Scarselli F, Gori M, Tsoi A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80.

[14] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[15] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

[16] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems. 2017: 1024-1034.

[17] Velikovi P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.

[18] Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry [C]//Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017: 1263-1272.

[19] Johnson J, Gupta A, Fei-Fei L. Image generation from scene graphs[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018: 1219-1228.