新人友好~「图神经网络前沿进展与应用」中文综述

图神经网络最新综述论文

图结构数据是现实生活中广泛存在的一类数据形式.宏观上的互联网、知识图谱、社交网络数据,微观上 的蛋白质、化合物分子等都可以用图结构来建模和表示.由于图结构数据的复杂性和异质性,对图结构数据的分析 和处理一直是研究界的难点和重点.图神经网络(GraphNeuralNetwork,GNN)是近年来出现的一种利用深度学 习直接对图结构数据进行学习的框架,其优异的性能引起了学者高度的关注和深入的探索.通过在图中的节点和 边上制定一定的策略,GNN 将图结构数据转化为规范而标准的表示,并输入到多种不同的神经网络中进行训练, 在节点分类、边信息传播和图聚类等任务上取得优良的效果.与其他图学习算法相比较,GNN 能够学习到图结构 数据中的节点以及边的内在规律和更加深层次的语义特征.由于具有对图结构数据强大的非线性拟合能力,因此 在不同领域的图相关问题上,GNN 都表现出更高的准确率和更好的鲁棒性. 本文在现有 GNN 研究的基础上,首先 概述了 GNN 的出现历程,并介绍了相关概念和定义.之后本文着重讨论和对比了 GNN 中的各种算法框架,包括 核心思想、任务划分、学习方式、优缺点、适用范围、实现成本等. 此外,本文对 GNN 算法在多个不同领域下的应用 场景进行了详细的阐述,将 GNN 与其他图学习算法的优缺点作了联系和比较.针对存在的一些问题和挑战,本文勾画了 GNN 的未来方向和发展趋势,最后对全文进行了全面而细致的总结。

https://cjc.ict.ac.cn/online/onlinepaper/WB-2022121103627.pdf

引言

近年来, 深 度 学 习[1]在 多 个 领 域 取 得 明 显 优 异的效果, 特别是在计算机视觉、音频识别以及自 然语言处理 三 个 方 面 取 得 突 破 性 进 展.深 度 学 习 通过建立人 工 神 经 网 络,对 输 入 的 信 息 和 数 据 逐 层进行特征 的 提 取 和 筛 选,最 终 获 得 分 类 和 预 测 等任务的结 果.相 较 于 统 计 机 器 学 习 等 浅 层 学 习 模式,深度学 习 所 使 用 的 神 经 网 络 架 构 具 有 多 个 功能各异的 复 杂 网 络 层,其 特 征 提 取 和 识 别 的 数 量和质量显 著 提 高,并 且 能 够 自 底 向 上 生 成 更 加 高级的特征表示.这使得机器能够获得抽象概念, 具备 更 强 的 表 征 学 习 能 力[2].诸 如 多 层 感 知 机 (MultilayerPerceptron,MLP)[3]、卷 积 神 经 网 络 (ConvolutionalNeuralNetwork,CNN)[4]、循 环 神 经网络(RecurrentNeuralNetwork,RNN)[5]、生成 对 抗 网 络 (Generative Adversarial Network,GAN)[6]和自编码器(Auto-encoder,AE [7]等性能优 异的神经网络已经成为许多研究领域解决问题的通 用网络框架.

但是随着研究的深入,研究人员发现深度学习 并不能适应和解决所有的情况和问题.在过去十多 年的发展中,深度学习取得的成就主要限定在了计 算机视觉、自然语言处理和音频分析领域上.这些领 域上的数据和信息有着比较显著的特点.文本、图 像、音频、视频的数据格式在形式上有着统一而规整 的尺寸和维度,它们也被称作欧式结构(Euclidean Structure)或者网格结构(GridStructure)数据.除 此之外,现实生活中存在大量的非欧式结构的图数 据,例如互联网、知识图谱、社交网络、蛋白质、化合 物分子等.尽管深度学习在欧式结构数据上取得巨 大的成功,但在图结构数据上,基于神经网络的深度 学习表现得并不好.在图结构数据中,节点与节点之 间的边连接可能是均匀分布的,也可能是不均匀的. 节点与节点之间没有严格意义上的先后顺序.对于神经网络的输入端而言,这些数据没有固定的输入 尺寸.在数学表达上,这些数据与欧式结构数据相 比,每一个区块的特征矩阵维度都不是统一的,如图 1所示.由于无法使用统一规整的算子对数据编排, 导致 CNN 等神经网络不能再直接对其进行诸如卷 积和池化等操作,也就不再有局部连接、权值共享、 特征抽象等性质[8].如何将 CNN 等深度学习算法 用于分析图结构数据上成为一个有挑战性和前沿性 的课题.近年来 Gori等人[9]用 RNN 来压缩节点信 息和学习图节点标签,首次提出图神经网络(Graph NeuralNetwork,GNN)这一概念.之后文献[10]提出 图 卷 积 网 络 (Graph Convolutional Network, GCN),正式将 CNN 用于对图结构数据建模.GCN 通过整合中心节点和邻居节点的特征和标签信息, 给出图中每个节点的规整表达形式,并将其输入到 CNN 中.这样一来 GCN 就能利用多尺度的信息, 组合成更高层次的表达.其有效地利用了图结构信 息和属性信息,为深度学习中其他神经网络迁移至 图上提供了标准的范式.在新的研究思路的基础上, 各种 GNN 架构相继被构造出来,在多个领域的图 结构数据中发挥了独特的作用,并促进了图相关的人工智能推理任务的发展。

本文针对近年来出现的 GNN 学习方法和研究现状进行了系统的归纳和梳理,并对它们的主要思 想、改进以及局限性做了详尽分析.目前已有 Xu等 人[11]关于图卷积神经网络的综述,本文在全面对比 分析的基础上,对目前主要的 GNN 算法进行了更 加合理的分类和介绍.除了图卷积神经网络,GNN 主流算法还包括有图自编码器、图生成网络、图循环 网络以及图注意力网络.本文对每类 GNN 算法都 给出了其定义和典型方法,将 GNN 中每种算法的 机制、优势、缺点、适用范围、实现成本等进行了提炼 总结.在进行了相应的数据实验基础上,与其他基准 图算法进行了比对.本文在第2节中给出关于 GNN 的基本概念和定义;在第3节分门别类的给出 GNN 的主要模型和算法;在第4节,对比和分析 GNN 与 网络嵌入(NetworkEmbedding)以 及 图 核 (Graph Kernel)方法的特性和优势.在第5节中,阐述目前 GNN 在多个领域图数据上的具体应用;在第6节归 纳和总结现有 GNN 模型缺陷和不足,并对未来发 展方向和趋势进行展望.最后在第7节对全文所述 进行总结.

图神经网络模型

图卷积网络 

图 卷 积 网 络 (GraphConvolutionalNetwork, GCN)进行卷积操作主要有两种方法:一种是基于 谱分解,即谱分解图卷积.另一种是基于节点空间变 换,即空间图卷积.Bruna等人[10]第一次将卷积神 经网路泛化到图数据上,提出两种并列的图卷积模 型———谱分解图卷积和空间图卷积.Bruna等人对 比分析了一般图结构数据和网格数据共有的特点和 不同之处,综合运用了空间图卷积和谱分解处理图 像聚类问题.下面本文对谱分解图卷积和空间图卷 积进行详细的梳理和介绍。

图自编码器

在 深 度 学 习 领 域,自 编 码 器 (Auto-encoder, AE)是一类将输入信息进行表征学习的人工神经网 络.自编码器一般包含编码器和解码器两个部分,基 于自编码器的 GNN 被称为图自编码器(GraphAuto-encoder,GAE),可以半监督或者无监督地学习 图节点信息.如图3所示

在图自编码器上,文献[54]提出基于深度神经网络的 表 示 模 型 (Deep NeuralNetworkforGraph Representations,DNGR).DNGR 采用随机游走模 型(RandomSurfingModel)获取图结构信息,生成 概率共现 矩 阵,并 在 概 率 共 现 矩 阵 的 基 础 上 计 算 PPMI矩阵.在图节点嵌入表示学习上,DNGR 设计 了一个叠加去噪自编码器(StackedDenoisingAuto-encoder,SDA),输入 PPMI矩阵学习图节点低维 表示,并且输入的一部分会被随机置零以提高模型 的鲁棒性.DNGR的优点在于能学习到有向图中更 多的结构信息,其生成的低维嵌入表示可以用于不 同的下游任务.但缺点是忽略了图属性信息,没有将 图属性和图结构信息一并纳入到模型框架中,因此 图结构的轻微变化就会影响节点表示的好坏.针对 节点内容信息的收集,Wang 等人[55]提出一种边缘 图 自 编 码 器 (Marginalized Graph Autoencoder, MGAE)算法.其在自编码器中使用基于谱分解的 图卷积网络层,整合节点属性特征和图结构信息,使得它们之间能进行数据交互.MGAE堆叠多层图形 自编码器,以建立一个深层次的架构来学习有效的 节点表示.Wang等人认为在训练中随机噪声引起 的干扰可能会提供更有效的输出表示,因此会在节点 内容特征中动态地加入一些干扰项.通过将某些特征 值置为零,获得在大规模图上学习的能力.MGAE构 建了优化器以确保编码的节点属性信息和真实属性 信息之间的误差最小化.在得到每个节点的表示后, MGAE使用谱聚类算法得到图聚类结果。

图生成网络

建模和生成图是研究生物工程和社会科学网络 的基础.图生成网络(GraphGenerativeNetwork, GGN)是一类用来生成图数据的 GNN,其使用一定 的规则对节点和边进行重新组合,最终生成具有特 定属性和要求的目标图.然而,在图上模拟复杂分 布,并从这些分布中有效地采样是比较困难的.因为 有些图数据具有非唯一性、高维性质,图中边缘之间 存在复杂的非局部依赖性.因此不能假设所有的图 数据都来自于同一个先验分布,尤其是对于异质图, 模型在识 别 过 程 中 必 须 要 具 有 平 移 不 变 性.因 此 GGN 着重用来解决这类问题和克服其中的难点. GGN 的输入可以是节点或者边向量,也可以是给定 的图嵌入表示,然后对采样的数据学习后合成各种 任务所需要的图.

图循环网络

图循环网络(GraphRecurrentNetwork,GRN) 是最早出现的一种 GNN 模型.相较于其他的 GNN 算法,GRN 通常将图数据转换为序列,在训练的过 程中序列会不断地递归演进和变化.GRN 模型一般 使用 双 向 循 环 神 经 网 络 (BidirectionalRNN,BiRNN)和长短期记忆网络(LongShort-Term MemoryNetwork,LSTM)作为网络架构.

图注意力网络

注意力机制可以让一个神经网络只关注任务学 习所 需 要 的 信 息,它 能 够 选 择 特 定 的 输 入[96].在 GNN 中引入注意力机制可以让神经网络关注对任 务更加相关的节点和边,提升训练的有效性和测试 的精度,由此形成图注意力网络(GraphAttention Network,GAT).

图神经网络总结分析

通过前文的归纳和分析, 从总体上看, 图神经网络可以分为五类: 图卷积网络、图自编码器、图生成网络、图循环网络和图注意力网络.每种图神经网络 都有自己对图结构数据处理的一套算法和体系,其 中的原理和适用的范围也有一定差别.当然它们之 间不是相互孤立和排斥的,例如文献[59,65]的图自 编码器中包含图卷积层,文献[91,95]的图循环网络 为了图序列学习更有效,也会加入注意力模块.而图 注意力网络也大多以其他图神经网络框架为基础, 构建合适的节点、边以及图注意力网络层.因此在实 际操作当中,需要根据图的分布和特征信息,以及任 务的实际需求,选择合适的图神经网络,来更加有效 地学习图结构数据. 表7是 GNN 机制、优点、缺点、 适用范围及实现成本汇总表。

图神经网络应用

由于 GNN 能较好地学习图结构数据的特征, 因此在许多图相关的领域有着广泛的应用.若按照 应用中图的层次结构划分,则大体可以分为节点、边 和图层面.在节点层面,常见的有节点分类、节点聚 合、节点表示学习.在边层面,则有边分类、边聚类以 及链接预测.在图层面,图分类、图生成、子图划分、 图相似度分析等应用较为广泛.按照图的种类划分, 可以分为引文网络、社交网络、交通网络、图像、化合 物分子结构、蛋白质网络等.按照应用领域划分,可 以分为自然语言处理、图像处理、轨迹预测、物理化 学和 药 物 医 学 等.为 了 方 便 说 明 和 阐 述, 本 文 从 GNN 的主要应用领域这一角度出发,对近年来出现 的 GNN 应用实例进行分类归纳。

图神经网络未来研究方向

GNN 的核心在于规范化表示的图结构数据并 用深度神经网络进行学习.经过近些年的不断发展, 通过大量数学证明和实验分析后,GNN 在理论上和实践上都被证实是对图结构数据处理的一种有效方 法和框架.尽管 GNN 在各个领域的图数据上取得 了不俗的表现和较好的普适性,但是 GNN 仍然存 在一定的不足和需要完善的地方.根据目前国内外 的研究现状,下面本文对 GNN 的一些制约因素和 未来发展方向进行探讨.

1 网络深度 

在计算机视觉、自然语言处理和音频处理中,神 经网络的层数可以叠加多层.在一定范围内,神经网 络层数的增加可以更好地提取数据中的特征信息. 例如深层残差网络 ResNet [150]可以达到152层.但 是 GNN 的邻居节点聚合中,随着网络层数的增加, 邻居节点的阶数会不断扩张,导致中心节点聚合特 征数量成指数变多.这在大规模数据集上,尤其是节 点之间的边连接数量较多时表现的非常明显.随之 而来的是训练过程中计算复杂度的剧增,并可能导 致过拟合的现象发生.这也就意味着随着层数的增 加,GNN 模型性能会急剧下降.如果想要加深网络 层数,就必须限制每层节点数量.但是这也会使得特 征聚集的量变少,导致节点之间信息传播受阻.如何 解决这一矛盾性问题是将来研究的重点之一.

2 动态性 

就目前来看,现有的 GNN 大多处理的是静态 齐次图.一方面,GNN 框架会假定图结构是固定的; 另一方面,GNN 框架会假设图中的节点和边来自于 单一源分布.然而,这两个假设在许多情况下并不能 同时成立.在社交网络中,新的人可以随时进入网 络,并且现有的人也可以退出网络.在推荐系统中, 产品可能有不同的类型,其输入可能有不同的形式, 如文本或图像.特别是在超大规模的图中,节点的个 数和边的个数可能有百万、千万乃至上亿.尤其是随 着数据的增加和改变,节点和边的个数以及节点和 边的类型都可能发生动态的变化.在这些任务处理 中,图的动态变化是不能忽视的.特别是在固定尺寸 下,因为某个节点或者边发生改变而重新学习整个 图将会使得代价十分昂贵.而大多数 GNN 对于大 型图不具 有 很 好 的 伸 缩 性.其 主 要 原 因 是 当 堆 叠 GNN 的多个层时,节点的最终状态涉及大量邻居的 隐藏状态,导致反向传播的高复杂性.虽然目前有一 定的文献[94-95,136-137]在研究图的时空动态性,但是面 对更大规模和更加复杂的动态异质图数据时还不够 有效.因此如何对图的动态性进行有效的适应是未 来的研究方向之一.

3 感受域 

一个节点的感受域是指一组节点集合,包括中 心节点及其邻居节点.感受域大小是决定邻居节点 数量的关键参数.在大规模图数据集中,平均每个节 点周围有多个邻居节点存在.随着网络层数的增加, 邻居节点会递归增加数目,感受域也随之快速扩张.  这可能会超过存储空间的上限.此外,一些节点可能 只有一个邻居,而另外节点可能有多达数千个邻居. 邻居节点分布不均衡使得每个中心节点的感受域大 小不一致.尽管可以通过添加“哑结点”和删除邻居 节点的方式保持数据大小和维度的一致,但是在特 征的聚集和融合中不可避免的会有信息损失现象发 生,而现有的采样方法还不能完全解决该问题.

4 多网络的融合 

由于现实世界数据的复杂性,抽象出来的图结 构也会有很多的种类和变体.有向无向、异质非异 质、带权不带权等等,大部分的 GNN 仅能处理其中 的某一种类型.而更普遍的情况是各种各样的图混 杂在一起,并且希望 GNN 能满足诸如节点分类、图 分类、可视化、图生成等多种任务需求.在这种复杂 的高强度的任务要求下,单一的神经网络作用过于 有限.因此对于更加复杂的情况,有必要进行多网络 融合.目前比较主流的多网络融合方式是 GCN 与 其他 GNN 算法相结合.例如在节点属性和图拓扑 结构信息的获取上,GCN 明显具有较高的性能和良 好的适应性,在节点分类问题上会表现良好.鉴于其 优点,在 GAE中不乏部分模型使用 GCN 作为编码 器,取得较好的效果.但如果还需要进行链接预测、 节点生成或者图生成,GCN 则有点力不从心了.此 时可以再增设一个 GGN,输入 GCN 处理后的节点 嵌入向量,在 GGN 内生成概率分布,完成生成式任 务.如果图在不断地递归演进,形成了图序列.则可以 利用 GRN来处理,以攘括多个步骤下的图信息.因此 在 GNN框架中构造不同用途的深度神经网络,从不 同的侧面来提取和整合数据的特征是十分有必要的. 此 外 可 以 对 诸 如 深 度 置 信 网 络 (DeepBeliefNetwork)[151]、Transformer [152]等神经网络进行改造,将 其泛化和应用至图结构数据学习上。

5 与网络嵌入的结合 

网络嵌入可以将原始图数据的高维稀疏矩阵转 变为低维度稠密的向量,这可以大幅度压缩存储空 间,并提取有效的图信息.一般图节点的原始特征矩 阵是高维稀疏的,对于一个 N ×F 的特征矩阵,当 F 比较大时,所需要的存储空间也相应的增加.如果 矩阵比较稀疏,那么存储效率也会比较低下.网络嵌 入则可以利用图结构信息,生成低维连续的节点特 征表示,避免存储空间浪费.其次,由于生成的节点 嵌入表示包含了部分邻居节点信息,所以中心节点 的感受域也可以相应的减少.对于多层图卷积和需要迭代压缩的 GNN 来说,一定程度上可以减少网 络层数和迭代压缩次数.例如 Kipf等人[27]半监督 GCN 复杂度为O(|E|FC),DeepWalk [110]的复杂 度为O(log(N)).当边连接比较密集并且节点特征 维度很大时,复杂度较高.如果对节点特征降维,使 得降维之后的维度 F' ≪ F ,这样总体复杂度变为 O(log(N))+O(|E|F'C).尽管增加了网络嵌入 的计算时间,但是在图卷积层可以大幅度降低计算 开销,这样可以提高训练的有效性以及降低计算复 杂度.文献[66,76,86]就使用随机游走等网络嵌入方法 来为 GNN 模型构建输入序列,除此之外未来研究 中也可以尝试诸如 Node2vec [77]、LINE [153]等网络 嵌入方法来对 GNN 的输入端进行改进.