大规模图神经网络研究综述

图神经网络凭借其处理非欧氏空间数据及其复杂特征方面的优越性受到了大量的关注, 并且被广泛应用于推荐系统、 知识图谱、交通道路分析等场景中. 面对大规模数据, 图结构的不规则性、节点特征的复杂性以及训练样本之间的依赖性对图 神经网络模型的计算效率、内存管理以及分布式系统中的通信开销造成了巨大的压力. 为应对和缓解以上问题, 研究者从应用 场景、算法模型、编程框架和硬件结构等多个层面对其进行了优化. 本文主要回顾和总结了算法模型及编程框架方面的优化, 为读者了解面向大规模数据的图神经网络采样算法以及框架优化相关工作提供帮助, 为未来算法-框架协同优化奠定基础. 具 体来说, 本文首先简要介绍图神经网络模型中的消息传递机制, 分类介绍常见的图神经网络模型, 并分析其在大规模数据训练 中面临的困难和挑战；然后对面向大规模数据的图神经网络算法模型进行分类总结和分析, 包括基于节点、边和子图的采样算 法；接着介绍图神经网络编程框架加速的相关进展, 主要包括主流框架的介绍以及优化技术的分类总结和分析；最后对未来面 向大规模数据的图神经网络研究进行展 望.

1 引言

图结构能够有效表征自然界和社会生活中广泛 存在的复杂关系, 如基因结构[1-2]、通信网络[3]、交 通路线[4]、社交网络[5-6]等. 针对相互关联的图数 据, 图计算能够有效挖掘其结构信息, 但是不具备对 其节点特征 (比如, 社交网络中用户兴趣、年龄等附 加信息) 的学习能力. 另一方面, 神经网络模型通过 海量参数训练能够灵活表示数据的复杂特征, 在图片、视频、文本等基于欧氏空间的数据上表现出优越 的性能[7-9] , 但其无法直接应用于非欧氏空间的图 数据. 综合图计算和神经网络的优势, 图神经网络 (Graph Neural Network, GNN)[10-11]凭借其在处理 非欧氏空间数据及其复杂特征方面的优越性受到了 大量的关注, 并被广泛应用于网络链接预测[12]、推 荐系统[13-14]、交通道路分析[15]等场景中。

实际应用场景中通常需要处理海量数据. 2019 年, 阿里巴巴研究团队在其工作[16]中提到常见的电 商平台往往存在百亿级节点、千亿级边, 其存储开 销超过 10TB. 在面向大规模数据的图神经网络中, 图数据的不规则性、特征复杂性以及训练过程中样 本间的依赖性对模型计算效率、内存管理、以及分 布式系统中的通信开销造成了巨大的压力. 下面我 们将图神经网络模型在大规模数据应用中面临的挑 战按照来源分为图数据结构、图神经网络模型、数 据规模和硬件平台四类, 分别介绍. (1) 图数据结构. 图结构数据的不规则性、稀疏 性、动态性、节点邻居数量呈幂律分布以及样本间 的相互依赖, 对高效的访存造成了一定的压力, 尤其 对面向大规模数据场景的分布式计算系统提出了更 大的挑战. (2) 图神经网络模型. 节点的高纬表示是图神经网络模型区别与传统图算法的典型特征, 在增强 了模型表示能力的同时, 也造成了更大的计算和内 存开销, 尤其是在大规模数据的应用中面临更大的 挑战. 其迭代更新的机制设计使得深层的图神经网 络模型面临邻居节点爆炸的问题. (3) 数据规模. 典型的图神经网络模型采用整 批训练的模式, 这在大规模数据的应用中存在内存 限制的问题. 在基于分批训练模式的图神经网络模 型中, 数据大规模性增大了数据划分和迭代更新的 难度. (4) 硬件结构. 图神经网络模型在图数据结构 和复杂特征方面的建模需求使得模型既需要灵活的 不规则数据读取, 又需要高效的密集计算. 目前 CPU 在灵活读取方面表现较好, GPU 支持高效的 密集计算, 但二者都不能同时满足这两点需求. 图 神经网络的需求和硬件结构的不匹配增加了大规模 图神经网络模型加速的难度.

为应对和缓解上述困难和挑战, 研究者通过优 化硬件结构、编程框架、算法模型以及应用模型 (如 图 1所示), 来提高图神经网络模型的可拓展性、加速模型运行过程以及减小内存开销[17-18] . 在应用模型方面, 针对自然语言处理、交通道 路预测、推荐系统等不同的应用场景提出具体的处 理策略[4,13,19] , 以提高图神经网络模型在具体任务 上的处理效率. 在算法模型方面, 典型的图神经网络模型采用 整批训练的方式, 要求将完整的图数据载入内存, 在面向大规模数据训练 (尤其是基于 GPU 进行训 练) 时往往面临内存不足的问题. 针对这一问题, 一些研究工作提出通过采样算法实现图神经网络模 型的分批训练, 比如 GraphSage[20] , FastGCN[21] , Cluster-GCN[22]等. 在编程框架方面, 图神经网络迭代更新的 表示机制导致训练样本之间相互依赖, 使得 TensorFlow、Pytorch 等典型的神经网络框架无法 有效地实现模型分批训练及其高效运行. 计算过 程中的特征复杂性对原有图计算框架提出了更大的内存和计算需求. 结合传统神经网络和图计算框架 的特点, Deep Graph Library(DGL)[23]、PyTorch Geometric(PyG)[24]等面向图神经网络的编程框架 被提出来缓解这一问题.

在硬件结构方面, 一些研究者结合 CPU、GPU、 FPGA 等硬件的结构特征, 在计算、访存等方面提 出了对应的优化策略[25-27] . 或者针对图神经网络的 特征设计了专用的硬件加速结构, 比如 HyGCN[28] . 基于以上大量的研究工作, 目前已有综述从应 用模型、算法模型、编程框架以及硬件结构四个方 面总结和分析图神经网络相关的进展, 表 1列出了 本文相关的 5 篇综述. 综述[29]总结了图神经网络在算法和应用方面 的主要进展, 将 GNN 算法分为循环 GNN、图卷积 神经网络 (Graph Convolutional Network, GCN)、 图自编码器和时空 GNN 四类进行介绍, 并总结了 开源的数据集、已有方法的实现和应用场景. 综 述[30]将图神经网络模型的设计过程总结为消息传 播模式、采样方法和池化操作三个子模块的设计, 并 总结了不同的图神经网络模型和应用场景. 除了 分类介绍 GNN 算法模型和应用场景, 综述[31]还 总结了已有的典型框架: 消息传播网络 (Message Passing Neural Network, MPNN)、非局部神经网 络 (Non-Local Neural Network, NLNN)、图网络 (Graph Network, GN) 和混合网络模型 (Mixture Model Networks, MoNet). 综述[32]主要从算法模型 和应用场景两方面总结了图卷积神经网络 (GCN) 的提出、发展和应用. 综述[33]主要总结了 GNN 在 算法、软硬件加速器方面的进展, 首先从计算过程的 角度介绍了 GNN 的基础操作和算法分类, 然后从 软件 (编程框架) 和硬件两个方面总结了 GNN 加 速器相关的工作, 最后展望了今后加速器设计可能 的方向: 软硬件结合、图感知和以通信为中心. 综 述[34]总结了现有图神经网络编程框架的设计和实 现方案, 分类分析了其中的优化技术, 并对开源的 图神经网络编程框架进行了试验评估. 综述[35]首先 概述了 GNN 基础知识、典型算法、应用场景和主流编程框架, 然后介绍了 GNN 加速结构的整体设 计, 并从 GNN 加速面临的挑战出发详细介绍了计 算、片内访存、片外访存方面的关键技术。 总的来说, 综述[29-32]侧重于总结和分析采用整 图 (full-batch) 训练模式的图神经网络模型及其相 关应用场景. 然而, 当图中的节点或边的数量达到 百万甚至十亿级时, 训练过程往往会超出单块 GPU 的内存限制. 针对这一问题, 一些方法的提出促 进了图神经网络模型从全图训练方式到分批 (minibatch) 训练方式的转变。其中, 采样算法为图神经 网络模型的分批训练提供支持, 为其在大规模数据 中的应用奠定了基础. 面向图神经网络的编程框架 结合了深度学习框架和图结构的具体特征, 提高了 存储利用率和计算效率, 促进了图神经网络模型在 大规模数据中的应用. 相关综述[33-34]主要总结了图 神经网络编程框架方面的进展. 综述[36-38]主要针 对分布式平台, 总结和分析了分布式 GNN 在算法 模型、软件框架和硬件平台等方面的相关进展. 与现有综述相比, 本文主要针对大规模图神经 网络, 从算法模型和框架优化两个方面对现有研究 进行了调研、总结和分析. 本文首先对 GNN 的基 础知识和典型算法进行介绍和总结; 总结分析了基 于不同粒度采样策略的图神经网络模型; 总结分析 了主流的加速框架及其相关技术. 为后续图神经网 络模型在大规模数据数据应用中框架-算法的协同 优化提供更多的思路.

本文的内容安排如图 2所示. 第 2 部分简要介 绍图神经网络, 包括消息传递机制、常见的图神经 网络模型及其在针对大规模数据训练时面临的困难 和挑战. 第 3 部分分类总结和分析图神经网络模型 针对大规模数据的优化工作, 主要包含对不同粒度 的采样算法的介绍. 第 4 部分介绍和总结图神经网 络编程框架加速方面的进展, 包括对主流框架的介 绍和相关加速技术的分类总结. 第 5 部分对全文进 行总结并对面向大规模数据的图神经网络在算法模 型和编程框架方面的未来研究进行展望.

2 图神经网络

图神经网络 (Graph Neural Network, GNN) 是 面向图结构数据的神经网络模型[10-11] , 主要用于对 图数据中的节点进行向量表示及其相关任务[39-40] , 融合了图计算和神经网络模型的优势, 能够在捕捉 图结构的同时抽象出节点包含的复杂特征[41] . 其 中, 图计算模型能够很好地捕捉图的拓扑结构特征, 但无法处理节点的高维特征. 典型神经网络模型通 常用于处理欧氏空间数据, 比如, 卷积神经网络适用 于处理网格类数据[42] , 循环神经网络在捕捉序列信 息方面表现较好[43] . 综上, 针对非欧氏空间的复杂 图数据, 图结构本身不规则并且节点包含复杂特征, 其建模过程需要一种新的处理机制. 目前比较受欢 迎的消息传播模式通过获取高阶邻居信息来提升节 点的表达能力, 主要包括邻居聚合和节点更新两个 步骤[44] . 本节将从消息传递机制出发. 首先简要介绍基 于此的图神经网络模型中的两个主要操作, 聚合和 更新操作. 然后分类介绍常见的图神经网络模型: 图卷积神经网络、图注意力网络、循环图神经网络以及基于自编码器的图神经网络. 并针对每一类图 神经网络模型, 分析其在大规模数据训练过程中存 在的挑战. 最后对图神经网络模型在面向大规模数 据训练过程中存在的挑战进行总结.

3 图神经网络采样算法

针对图神经网络在大规模数据训练中面临的挑 战, 一些研究工作在算法模型方面进行了对应的优 化. 大部分工作集中在针对数据的优化方面, 主要 通过不同粒度的采样算法实现分批训练以应对数据大规模性在计算效率和内存开销方面带来的挑战. 根据采样粒度，已有的采样算法可以分为基于节点 的采样算法、基于层的采样算法以及基于子图的采 样算法. 下文将分别介绍和分析三类采样算法及其 涉及的具体模型.

4 图神经网络框架加速

图神经网络中计算过程包含图结构数据的不规 则访存 (集中于聚合阶段) 和复杂特征的大量计算 (集中于更新阶段). 然而, 传统神经网络编程框架只 擅长加速规则数据的计算效率, 在不规则访存方面 性能较差. 图计算框架在图遍历等不规则访存任务 上表现较好, 但并不适用于节点复杂特征的访存和 计算. 针对以上问题, 不少研究者提出了面向图神 经网络模型的编程框架并进行了相关优化技术的探 索, 为面向大规模数据的图神经网络模型运行以及 优化奠定了基础. 本节将分别对编程框架和相关优 化技术进行分析和总结.

5 总结与展望

数据大规模性是图神经网络模型在应用中面临 的主要挑战之一, 大量的研究工作从不同的角度进 行了性能优化和加速. 针对现有综述在这一方面的 空白, 本文分析总结了现有图神经网络模型存在的 具体挑战, 并从算法模型和编程框架两个方面介绍 了图神经网络在大规模数据应用中的相关进展. 下 文将对面向大规模数据的图神经网络模型中存在的 挑战进行总结, 并总结本文在算法模型和编程框架 方面的综述工作. 然后对未来相关工作进行展望.