第45卷 第1期2022年1月计 算 机 学 报CHINESE JOURNAL OF COMPUTERSVol. 45 No. 1Jan.2022收稿日期:2019-11-24;在线发布日期:2020-02-04.本课题得到国家自然科学基金(No.62072463, No.71531012)、国家社会科学基金(No.18ZDA309)、北京市自然科学基金(No.4172032)、京东商城电子商务研究项目(No.413313012)、北大方正集团有限公司数字出版技术国家重点实验室开放课题资助.吴 博,博士研究生, 主要研究领域为图神经网络、深度学习.E-mail:wubochn@ruc.edu.cn.梁循(通信作者),博士,教授,计算机学会(CCF)会员,主要研究领域为神经网络、社会计算、自然语言处理.E-mail: xliang@ruc.edu.cn.张树森,博士研究生,主要研究领域为数据挖掘、社会计算. 徐 睿,博士研究生,主要研究领域为图像处理、机器学习.图神经网络前沿进展与应用吴 博 梁 循 张树森 徐 睿(中国人民大学信息学院 北京 100872)摘 要 图结构数据是现实生活中广泛存在的一类数据形式.宏观上的互联网、知识图谱、社交网络数据,微观上的蛋白质、化合物分子等都可以用图结构来建模和表示.由于图结构数据的复杂性和异质性,对图结构数据的分析和处理一直是研究界的难点和重点.图神经网络(Graph Neural Network,GNN)是近年来出现的一种利用深度学习直接对图结构数据进行学习的框架,其优异的性能引起了学者高度的关注和深入的探索.通过在图中的节点和边上制定一定的策略,GNN将图结构数据转化为规范而标准的表示,并输入到多种不同的神经网络中进行训练,在节点分类、边信息传播和图聚类等任务上取得优良的效果.与其他图学习算法相比较,GNN 能够学习到图结构数据中的节点以及边的内在规律和更加深层次的语义特征.由于具有对图结构数据强大的非线性拟合能力,因此在不同领域的图相关问题上,GNN都表现出更高的准确率和更好的鲁棒性.本文在现有GNN研究的基础上,首先概述了GNN的出现历程,并介绍了相关概念和定义.之后本文着重讨论和对比了GNN 中的各种算法框架,包括核心思想、任务划分、学习方式、优缺点、适用范围、实现成本等.此外,本文对GNN 算法在多个不同领域下的应用场景进行了详细的阐述,将GNN与其他图学习算法的优缺点作了联系和比较.针对存在的一些问题和挑战,本文勾画了GNN的未来方向和发展趋势,最后对全文进行了全面而细致的总结.关键词 图神经网络;深度学习;图结构数据;拉普拉斯矩阵;谱分解;节点特征聚合;图生成中图法分类号TP18 DOI号10.11897/SP.J.1016.2022.00035Advances and Applications in Graph Neural NetworkWU Bo LIANG Xun ZHANG Shu-Sen XU Rui(School of Information, Renmin University of China, Beijing 100872)Abstract As is known to all, Graph-structure data is a kind of data form widely existing in reallife. Internet network, knowledge graph, social network data in macro perspective, togetherwith protein, compound molecules data in micro perspective, are all can be modeled and representedby graph-structure. Because graph-structure data has complexity and heterogeneity attribute,the analysis and processing of graph-structure data have always been a difficulty in researchcommunity. The researchers have been studying the property information and topological structureinformation in graph and try to find out a way or method to learn and explore the graph automatically.In order to solve the problems above, Graph Neural Network (GNN) appears as akind of framework that uses deep learning to learn graph-structure data directly in recent years.On the one hand, the excellent performance of GNN has aroused high attention and deep explorationin research community. GNN transforms the graph-structure data into standard representationby making a series of certain strategies on the multifarious nodes and edges of the graph, andthen the representation can be input into a variety of different artificial neural networks for training,and achieves excellent results in tasks such as node classification, edge information dissemination,graph clustering and so on. On the other hand, when it is compared with other graphlearning algorithms, GNN can learn the internal rules and semantic features of node and edge featuresin graph-structure data. Because it has a strong nonlinear fitting ability to graph-structuredata, GNN has higher accuracy and better robustness on graph-structure related problems in differentfields. To make it more suitable and efficient for specific applications, there is a great dealof variants of GNN algorithm and framework are proposed in past few years. Based on the existingGNN research, this paper first summarizes the history of GNN, and introduces the relatedconcepts and definitions. After an overview of GNN theory, we then focus on the discussion andcomparison of various algorithms in GNN, including the core idea, task division, types of graphs,activation function, different dataset, advantages and disadvantages, the scope of application, implementationcosts, learning methods and benchmark network. We give a novel classification and divideGNN into five different artificial neural networks. In addition, the application of GNN algorithm inmany different fields is described in details such as natural language processing, molecule graph generationand so on. This paper gives an introduction to the other kinds of graph learning algorithmwhich are recognized as network embedding and graph kernel. We compare the advantages and disadvantagesbetween GNN and network embedding as well as graph kernel. Although GNN has beenvery popular over past years, these two kinds of graph learning algorithm are also to be proved competitivein some tasks. In view of the existing problems and challenges, this paper outlines the futuredirection and development trend of GNN, which includes depth of artificial neural network, dynamics,receptive field of GNN, the fusion of multi artificial neural networks, and the combination betweenartificial network embedding and GNN. Last but not least, we make a comprehensive and detailedsummary of the full text.Keywords graph neural network; deep learning; graph-structure data; laplacian matrix; spectraldecomposition; node feature aggregating; graph generating1 引 言近年来,深度学习[1]在多个领域取得明显优异的效果,特别是在计算机视觉、音频识别以及自然语言处理三个方面取得突破性进展.深度学习通过建立人工神经网络,对输入的信息和数据逐层进行特征的提取和筛选,最终获得分类和预测等任务的结果.相较于统计机器学习等浅层学习模式,深度学习所使用的神经网络架构具有多个功能各异的复杂网络层,其特征提取和识别的数量和质量显著提高,并且能够自底向上生成更加高级的特征表示.这使得机器能够获得抽象概念,具备更强的表征学习能力[2].诸如多层感知机(Multilayer Perceptron,MLP)[3]、卷积神经网络(Convolutional Neural Network,CNN)[4]、循环神经网络(Recurrent Neural Network, RNN)[5]、生成对抗网络(Generative Adversarial Network,GAN)[6]和自编码器(Auto-encoder,AE[7]等性能优异的神经网络已经成为许多研究领域解决问题的通用网络框架.但是随着研究的深入,研究人员发现深度学习并不能适应和解决所有的情况和问题.在过去十多年的发展中,深度学习取得的成就主要限定在了计算机视觉、自然语言处理和音频分析领域上.这些领域上的数据和信息有着比较显著的特点.文本、图像、音频、视频的数据格式在形式上有着统一而规整的尺寸和维度,它们也被称作欧式结构(EuclideanStructure)或者网格结构(Grid Structure)数据.除此之外,现实生活中存在大量的非欧式结构的图数据,例如互联网、知识图谱、社交网络、蛋白质、化合物分子等.尽管深度学习在欧式结构数据上取得巨大的成功,但在图结构数据上,基于神经网络的深度学习表现得并不好.在图结构数据中,节点与节点之间的边连接可能是均匀分布的,也可能是不均匀的.节点与节点之间没有严格意义上的先后顺序.对于36 计 算 机 学 报 2022年神经网络的输入端而言,这些数据没有固定的输入尺寸.在数学表达上,这些数据与欧式结构数据相比,每一个区块的特征矩阵维度都不是统一的,如图1所示.由于无法使用统一规整的算子对数据编排,导致CNN 等神经网络不能再直接对其进行诸如卷积和池化等操作,也就不再有局部连接、权值共享、特征抽象等性质[8].如何将CNN 等深度学习算法用于分析图结构数据上成为一个有挑战性和前沿性的课题.近年来Gori等人[9]用RNN 来压缩节点信息和学习图节点标签,首次提出图神经网络(GraphNeural Network,GNN)这一概念.之后文献[10]提出图卷积网络(Graph Convolutional Network,GCN),正式将CNN 用于对图结构数据建模.GCN通过整合中心节点和邻居节点的特征和标签信息,给出图中每个节点的规整表达形式,并将其输入到CNN 中.这样一来GCN 就能利用多尺度的信息,组合成更高层次的表达.其有效地利用了图结构信息和属性信息,为深度学习中其他神经网络迁移至图上提供了标准的范式.在新的研究思路的基础上,各种GNN 架构相继被构造出来,在多个领域的图结构数据中发挥了独特的作用,并促进了图相关的人工智能推理任务的发展.本文针对近年来出现的GNN 学习方法和研究现状进行了系统的归纳和梳理,并对它们的主要思想、改进以及局限性做了详尽分析.目前已有Xu等人[11]关于图卷积神经网络的综述,本文在全面对比分析的基础上,对目前主要的GNN 算法进行了更加合理的分类和介绍.除了图卷积神经网络,GNN主流算法还包括有图自编码器、图生成网络、图循环网络以及图注意力网络.本文对每类GNN 算法都给出了其定义和典型方法,将GNN 中每种算法的机制、优势、缺点、适用范围、实现成本等进行了提炼总结.在进行了相应的数据实验基础上,与其他基准图算法进行了比对.本文在第2节中给出关于GNN的基本概念和定义;在第3节分门别类的给出GNN的主要模型和算法;在第4节,对比和分析GNN 与网络嵌入(Network Embedding)以及图核(GraphKernel)方法的特性和优势.在第5节中,阐述目前GNN 在多个领域图数据上的具体应用;在第6节归纳和总结现有GNN 模型缺陷和不足,并对未来发展方向和趋势进行展望.最后在第7节对全文所述进行总结.图1 欧式结构和图结构数据比较2 概念与定义2.1 符号与定义GNN 是指使用神经网络来学习图结构数据,提取和发掘图结构数据中的特征和模式,满足聚类、分类、预测、分割、生成等图学习任务需求的算法总称.GNN 的历史最早可以追溯到2005年,Gori等人[9]第一次提出GNN 概念,用RNN 来处理无向图、有向图、标签图和循环图等.在这之后,Scarselli等人[12]和Micheli等人[13]继承和发展了该模式的GNN 算法,并做了一定程度的改进.早期阶段的GNN主要是以RNN 为主体框架,通过简单的特征映射和节点聚集为每个节点生成向量式表达,不能很好地应对现实中复杂多变的图数据.针对此情况,文献[10]提出将CNN 应用到图上,通过对卷积算子巧妙的转换,提出了图卷积网络(Graph ConvolutionalNetwok,GCN),并衍生了许多变体.GCN 实现了CNN 在图上的平移不变、局部感知和权值共享[14],为接下来其他GNN 框架的构造和改进提供思想上的指导和借鉴.下面给出GNN 中相关符号的说明和定义.1期 吴 博等:图神经网络前沿进展与应用 37定义1.图(Graph)是由节点(Vertex)和连接节点的边(Edge)所构成,通常记为G = (V,E).其中V ={v1,v2,… ,vn}代表节点集合,E ={e1,e2,… ,em }代表边集合.通常节点也被称为顶点或者交点.边也被称为链接或者弧.通用的图表示是一个五元组:G(V,E,A,X,D).其中AN×N 代表图的邻接矩阵,XN×F 代表节点的特征矩阵,DN×N 代表度矩阵,N 和F 分别代表节点的数量和节点的特征维度.定义2.组合拉普拉斯矩阵,又称标准拉普拉斯矩阵,由对角矩阵和邻接矩阵组合而成:L =D -A (1)该矩阵只在中心节点和一阶相连的节点上有非零元素,其余之处均为零.定义3.对称标准化拉普拉斯矩阵:Lsym =I-D-1/2AD-1/2 (2)其元素值由式(3)给出:Lsymi,j =1 i=j且deg(vi)≠0-1deg(vi)deg(vj) i ≠j 且vi 与vj 相连0 其他■■■||| |||(3)由于需要对邻居节点的数量进行统一并对特征值求平均,所以一般在谱分解图卷积中多用定义3的对称标准化拉普拉斯矩阵进行傅里叶变换和特征向量分解.2.2 图的类型不管是数学中的拓扑网络还是现实生活中的网络,都可以统一抽象为图.图的形式多种多样,按照图的边是否具有方向可以划分为有向图和无向图.边的属性称作权值,根据边是否具有权值可以将图划分为带权图和非带权图.此外还有异质图和同质图.同质图是指图中所有数据都为同一类型,即节点类型和边类型单一.而图中的数据类型不尽相同的为异质图,即具有多种类型的节点和边.事实上,GNN 不仅仅局限于图数据处理.从广义上看,由于可以在赋范空间内建立拓扑关联,现实世界的任何数据都可以被视作图结构数据,包括最为常见的文字、图像、音频和视频.因此在转变为图结构形式后,欧式结构的数据也可以输入到GNN中进行训练和问题求解.这在下文介绍的实验数据集上有所体现.3 图神经网络模型3.1 图卷积网络图卷积网络(Graph Convolutional Network,GCN)进行卷积操作主要有两种方法:一种是基于谱分解,即谱分解图卷积.另一种是基于节点空间变换,即空间图卷积.Bruna等人[10]第一次将卷积神经网路泛化到图数据上,提出两种并列的图卷积模型———谱分解图卷积和空间图卷积.Bruna等人对比分析了一般图结构数据和网格数据共有的特点和不同之处,综合运用了空间图卷积和谱分解处理图像聚类问题.下面本文对谱分解图卷积和空间图卷积进行详细的梳理和介绍.3.1.1 谱分解图卷积尽管文献[10]最早提出用CNN 分析图数据,但是谱分解图卷积与图信号处理(Graph Signal Processing)[15][16][17][18]有着密不可分的关联关系.文献[19]提出处理图上离散信号方法(Discrete SignalProcessing,DSP),该方法把节点特征视作图信号,用邻接矩阵表示图中信号的转移和扩散,利用傅里叶变换扩展图信号并进行过滤.在GCN 中,过滤器、卷积、傅里叶变换、谱分解等理念都在该文献中有涉及.在傅里叶变换中,文献[20]将图上的特征向量类比成拉普拉斯算子的特征函数,为傅里叶变换和卷积运算推广到图上奠定基础.拉普拉斯矩阵是半正定对称矩阵,因此可以进行特征分解,由此傅里叶变换中的特征函数可以转变为拉普拉斯矩阵的特征向量.所以谱分解其实是利用图的拉普拉斯矩阵进行特征分解.Chung[21]提出的谱图理论(SpectralGraph Theory)使得通过谱分解构造卷积核成为可能,其谱乘法器的平滑性支撑起了空间局部性.文献[10]通过操作图的拉普拉斯矩阵的特征向量来进行卷积操作,构造了卷积函数:Hl=σ(UGθ(Λ)UTX) (4)Gθ(Λ)=θ1 … 0︙ ⋱ ︙0 … θn■■||||■■||||(5)其中σ(·)是sigmoid激活函数,Hl 是每层的输出,θ=(θ1,θ2,… ,θn)是网络层参数,X 是节点特征向量.通过初始化权值,在数据训练中进行信息前向传播,并对损失函数求偏导将误差进行反向传播.但是缺点在于需要进行特征分解,在大图上特征分解的38 计 算 机 学 报 2022年计算代价很高.而且每一次前向传播需要计算U、Gθ(Λ)以及UT 三者的乘积,其计算复杂度与节点数量的平方成正比,即O(N2).由于Bruna等人提出的谱分解图卷积中卷积核参数多,在网络层传播过程中计算复杂度成幂指数增加,导致Bruna提出的图卷积算法主要限定于只具有低维特征的节点以及小规模图上,因此如何对参数缩减成为一个迫切需要解决的问题.在图信号处理领域,文献[22]使用切比雪夫多项式近似拟合参数,在图拉普拉斯矩阵上进行快速小波变换.文献[23]则使用Lanczos[24]算法将拉普拉斯矩阵进行正交相似变换,构造对角矩阵来生成krylov[24]子空间的正交基,并推广到矩阵函数.这些图信号快速过滤模型为谱分解图卷积加速计算提供了理论和方法上的指导.在此基础上,Defferrar等人[25]提出一种基于快速滤波递推公式的局部卷积算子,通常记作Chebyshev卷积算子.其思想是应用切比雪夫多项式对特征矩阵求解,卷积核可以被定义成如下形式:gθ(Λ)=ΣK-1k=0θkTk(Λ