图神经网络前沿进展与应用

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

引言

近年来,深 度 学 习[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 的一些制约因素和 未来发展方向进行探讨.

网络深度

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

动态性

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

感受域

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

多网络的融合

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

与网络嵌入的结合

网络嵌入可以将原始图数据的高维稀疏矩阵转 变为低维度稠密的向量,这可以大幅度压缩存储空 间,并提取有效的图信息.一般图节点的原始特征矩 阵是高维稀疏的,对于一个 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 的输入端进行改进.