「大规模图神经网络系统」最新2022综述：从算法到系统

来自东北大学最新《大规模图神经网络系统》综述论文

图神经网络(GNN)是一类基于深度学习的处理图域信息的方法, 它通过将图广播操作和深度学习算法结合, 可以让图的结构信息和顶点属性信息都参与到学习中, 在顶点分类、图分类、链接预测等应用中表现出良好的效果和可解释性, 已成为一种广泛应用的图分析方法. 然而现有主流的深度学习框架(如TensorFlow、PyTorch等)没有为图神经网络计算提供高效的存储支持和图上的消息传递支持, 这限制了图神经网络算法在大规模图数据上的应用. 目前已有诸多工作针对图结构的数据特点和图神经网络的计算特点, 探索了大规模图神经网络系统的设计和实现方案. 首先对图神经网络的发展进行简要概述, 总结了设计图神经网络系统需要面对的挑战; 随后对目前图神经网络系统的工作进行介绍, 从系统架构、编程模型、消息传递优化、图分区策略、通信优化等多个方面对系统进行分析; 最后使用部分已开源的图神经网络系统进行实验评估, 从精确度、性能、扩展性等多个方面验证这些系统的有效性.

http://www.jos.org.cn/html/2022/1/6311.htm

图神经网络概述

深度学习在对象检测[1,2]、机器翻译[3,4]、语音识别[5]、物理系统[6,7]等领域取得了革命性的成功, 推动了对模 式识别和数据挖掘的研究. 现有的深度学习方法能够处理欧式空间表示下的规则数据, 例如图像数据可以表示为 欧几里得空间中的规则网络, 而现实中的很多应用的数据以图的形式来表示. 比如在社交网络[8]中, 可以通过图来 表示对象之间的关联关系, 从而能够进行社区发现、聚类[9]等算法. 在生物领域[10] , 可以通过图来表示蛋白质分子 之间的关系, 从而能够对蛋白质进行分类. 在引文网络[11]领域, 可以用图来表示论文之间的引用关系, 从而能够对论文按领域进行分组. 在电子商务领域, 可以用图来表示用户和商品之间的交互关系, 从而能够对用户进行商品的 推荐. 由于图数据的不规则性和稀疏性, 每个顶点可能具有不同数量的邻居, 并且图数据之间具有依赖性, 图中每个顶点的计算依赖于其他的顶点, 所以导致很多深度学习方法无法直接应用在图数据中. 例如, 卷积只能对图像或文本这样的欧几里德数据进行操作, 无法直接应用于图数据, 限制了深度学习方法在图领域的发展. 

随着图领域深度学习方法逐渐受到广泛关注, 近些年出现了很多图神经网络算法, 这些方法通过在传统深度 学习模型中添加图操作, 应用图的结构信息和属性信息, 来处理图数据的复杂性, 成为解决图学习问题的有效方 法. 比较典型的工作有 Structure2Vec[12]、GCN[13]、FastGCN[14]、AS-GCN[15]、GraphSAGE[16]等. 

图神经网络算法将传统深度学习的方法, 如卷积, 扩展到了图数据领域, 并结合数据传播的思想形成了在图上的深度学习算法, 其 在社交网络、推荐系统[17]、知识图谱[18]、链接预测[19]等领域都取得了良好的效果. 图神经网络受到广泛关注的原因如下: 首先, 现有标准神经网络无法正确处理图数据的输入, 因为其按照特定 顺序处理节点特征, 而图中的顶点没有自然顺序. 图神经网络算法采用在顶点上传播信息的计算方式, 忽略顶点的 输入顺序解决了这个问题. 第二, 在标准神经网络中, 图中顶点的依赖关系仅能作为顶点特征输入, 而图神经网络 算法根据图中顶点的依赖关系进行信息传播, 保留了图结构的信息, 为下游深度学习任务提供了更加完整的信息. 第三, 推理是高级人工智能的一个重要研究课题, 图神经网络强大的表示能力, 为进一步生成强大的神经模型提供 了基础. 

现有的深度学习框架如 TensorFlow[20]、PyTorch[21]、MXNet[22]以及 CNTK[23] , 和图处理框架 PowerLyra[24]、 PowerGraph[25]、Garaph[26]、Pregel[27]、TuX2[28]都不能很好地支持图神经网络的计算, 这阻碍了图神经网络的进一 步发展, 也限制了图神经网络在大规模数据中的应用. 因此突破现有框架限制, 开发专用于图神经网络训练的系 统, 对于充分发挥图神经网络的潜力十分重要. 

本文首先分析图神经网络算法的计算模式, 提出大规模图神经系统训练存在的挑战, 并对现有系统进行介绍. 然后从系统架构、通信优化等多个维度对这些系统进行详细的分析和对比, 对图神经网络系统的不同优化技术进 行总结和分析, 并对目前已经开源的图神经网络系统设计实验, 从多个方面测评系统的性能, 验证系统有效性.

大规模图神经网络训练的挑战

随着图神经网络在不同领域的应用越来越广, 对训练图神经网络系统的性能要求也越来越高. 结合对图嵌入[42-44]以及图神经网络[45, 46]的分析, 本文对设计开发神经网络训练系统存在的挑战进行如下总结.

(1) 现有深度学习系统不能很好地抽象图传播过程. 现有的深度学习系统处理的是规则数据, 规则数据中每个样本的计算图是独立的, 与其他样本无关, 而图神经网络是将深度神经网络和迭代图传播结合起来进行计算的, 图数据的每个样本(即图顶点)之间具有依赖性, 所以现有系统不能自然地表达和有效地支持图传播模型. 如何突破现有框架的局限, 设计一种适用于图神经网络的系统架构是发展图神经网络的重要问题;

(2) 训练大规模图神经网络的计算、存储复杂度高. 真实世界中的尺寸都非常大, 而且由于顶点之间具有复杂的依赖性, 随着图神经网络层数的增加, 计算成本和内存空间需求呈指数级增长. 例如Facebook的社交网络图包含超过20亿个顶点和1万亿条边, 这种规模的图在训练时可能会产生100 TB的数据. 所以针对大图的训练, 如何设计计算和存储策略以利用有限的资源来使系统达到理想的性能也是发展图神经网络系统的一大挑战;

(3) 图计算局部性差导致系统开销问题. 真实世界图的稀疏性会导致非常差的空间局部性, 在单机系统中这会导致Cache命中率降低. 而在分布式系统中, 这会导致频繁的跨节点访问, 进而产生大量的消息传递开销. 所以如何针对图的特殊性质减少系统开销是提高系统性能的一大挑战;

(4) 图的幂律分布导致分布式计算负载均衡问题. 对于具有数亿个顶点的大型图, 通常需要对图进行分布式处理, 图神经网络算法不同于传统的图算法, 平衡的图分区不仅依赖于分区内的顶点数量, 还依赖于分区内顶点邻居的数量, 多层图神经网络模型中不同顶点多阶邻居的数量可能相差极大, 并且这些分区之间需要频繁的数据交换, 如何对图数据进行合理的分区来保证分布式训练的性能是对于分布式系统的重大挑战;

(5) 异构计算架构中的任务划分和负载调度的合理性问题. GPU的广泛应用为训练深度学习模型带来了很多机会和挑战. 在利用GPU加速神经网络的训练时, 通常将数据存储在主机内存中, 在计算时需要将数据传输到GPU, 由于图神经网络算法在反向传播阶段的复杂性, 需要频繁的在主机和GPU之间进行数据传输, 如何设计合理的调度方案来最大程度地减少数据传输成本也是提高系统性能的一大挑战.

为了应对这些挑战, 出现了很多针对图神经网络的训练框架, 其中单机系统如PyTorch Geomertic、DGL、NeuGraph. 图神经网络通常处理非常大且不规则的图, 这些大图无法存储在单个设备中, 因此必须以分布式方式进行分区和处理, 其中分布式图神经网络框架如Euler、AliGraph、Roc、AGL. 接下来本文将介绍若干典型的单机图神经网络系统以及分布式图神经网络系统.

图神经网络系统介绍

图神经网络算法将深度神经网络的运算(如卷积、梯度计算)与迭代图传播结合在一起: 每个顶点的特征都是由其邻居顶点的特征结合一组深度神经网络来计算. 但是, 现有的深度学习框架不能扩展和执行图传播模型, 因此缺乏高效训练图神经网络的能力, 并且现有框架一般采用数据/模型并行来分布式训练深度神经网络, 这种并行计算方法难以直接应用于图神经网络, 因此限制了训练大规模图神经网络的能力. 而现有的图处理系统虽然能够表示迭代图传播模型, 并能有效支持大规模图的迭代计算, 但是缺乏支持神经网络计算的关键能力, 如张量抽象、自动微分等. 因此, 为了支持图神经网络在大规模图上的应用, 以及对更复杂图神经网络结构的探索, 开发针对图神经网络的训练系统是十分有必要的.

目前具有代表性的图神经网络框架: DGL[47]、PyTorch Geometric[48]、NeuGraph[49]、EnGN[50]、Euler[51]、PSGraph[52]、AliGraph[53]、Roc[54]、AGL[55]、PGL[56]. DGL[47]是易于使用, 高性能且可扩展的Python库, 用于图结构的深度学习, 能够与主流的深度学习框架集成, 例如Tensorflow[20]、PyTorch[21]、MXNet[22]. PyTorch Geometric[48]是基于PyTorch构建的深度学习库, 用于处理非结构化数据的深度学习. NeuGraph[49]是一种将数据流系统和图处理系统结合起来训练图神经网络的框架, 它构建在现有的数据流引擎之上, 使用Python和C++作为开发语言. EnGN[50]是一种以边为中心, 专门用于大规模图神经网络训练的加速器. Euler[51]与PSGraph[52]是一个与深度学习工具集成的大规模分布式图学习框架, 支持用户在数十亿点数百亿边的图上进行模型训练. AliGraph[53]是由阿里巴巴团队开发的采样建模训练一体化的图神经网络平台. Roc[54]是一种用于快速图神经网络训练的分布式多GPU框架. AGL[55]是用于工业用途图学习的集成系统, 利用传统基础架构(MapReduce、参数服务器[57])实现了容错性和一致性. PGL (paddle graph learning)[56]是由百度开发的基于PaddlePaddle的高效灵活的图学习框架.

图神经网络系统总结和分析

本节从系统架构、处理模型、图分区策略、通信优化策略、以及社区活跃度与系统易用性方面, 对现有图神经网络系统进行分析和对比, 并从多个维度对系统的特点进行总结, 以表格的形式清晰的展示系统的共性与不同, 来为研究人员提供有效参考.

(1) 系统架构. DGL和PyTorch Geometric都是结合现有的深度学习框架来实现的, 并且针对图神经网络的特点做了多种优化, 达到了很好的性能. 结合现有深度学习框架来实现的系统, 更加方便用户使用, 能够帮助其更快地实现图神经网络模型. 但结合现有深度学习框架来实现的系统, 在针对图操作的优化上有很多局限性. NeuGraph采用了一种新的架构, 将图模型和数据流模型结合起来, 以支持高效的图神经网络训练, 这种架构既弥补了现有数据流引擎不能有效地支持图计算的缺点, 又弥补了图引擎不能支持数据流编程模型的缺点. EnGN在统一的处理模型基础上, 开发了一个定制的EnGN加速器, 它集成了一个神经图处理单元(NGPU), 可以在统一的体系结构中执行特征提取, 聚合和更新操作. EnGN的专用加速器突破了硬件结构的限制, 相比于其他系统配备的多个CPU或GPU, 大大降低了成本和能源开销. AliGraph、Euler和PGL的架构类似, 都采用分层架构, 构建于现有数据流框架之上, 并且都构建在CPU平台上. Roc将图神经网络的计算分布在多个计算节点上, 每个计算节点可以包含多个GPU, 每个计算节点在子图上执行图神经网络的训练, 并与CPU通信来获得输入张量并保存中间结果. Roc采用分布式多GPU的架构不仅解决了单节点系统对于大规模图的限制, 并且比基于CPU的系统更高效. AGL、PSGraph都是利用现有大数据处理系统和参数服务器的并行体系结构来组建的基于CPU的分布式图神经网络训练框架, 这些系统具有良好的容错性和可伸缩性.

(2) 处理模型. DGL和PyTorch Geometric通过使用面向图的消息传递接口包装深度学习系统, 来支持针对图神经网络的编程. 这种消息传递模型很好地表示了图上的数据流动, 整个模型分为两步. 第1步: “消息”生成操作, 这个操作定义在每个边上, 通过将边的特征与两端顶点特征组合为每一条边生成一条“消息”. 第2步: 更新操作, 定义在每个顶点上, 通过汇总顶点入边传入的消息来更新顶点特征. 通过系统提供的消息传递接口, 用户可以快速实现图神经网络的原型制作. PGL也采用消息传递范式构建图神经网络的接口, 并提供多种聚合方法, 提高了并行处理效率. NeuGraph提出了一种新的处理模型SAGA-NN, 提高了在顶点和边上执行批量操作的灵活性, 提供了在图计算和数据流调度中实现优化的机会, 提高了系统性能. EnGN提供一种以边为中心的处理模型, 将图神经网络的计算抽象为特征提取, 聚合和更新3个阶段. EnGN与其他3个系统不同, 在处理模型基础上定制了针对图神经网络的加速器, 不依赖于现有的深度学习系统, 并拥有独特的数据流处理方法. EnGN优化了顶点数据和边数据移动的内存访问模式. 对于大图中的源顶点数据访问, 采用图切片技术, 并确保对源节点的访问仅引起对连续内存地址的访问. 对于聚合和更新阶段中的随机目标顶点访问, EnGN利用哈希边数据布局和多级缓存方法来避免写冲突并提高片上缓冲器中的数据命中率.

(3) 图分区策略. 平衡的图分区是实现分布式图神经网络系统的关键之一. Euler采用简单的哈希方法将图的顶点进行分片, 这种分片方式使各个节点拥有目标顶点的数量基本一致, 但是在每个顶点的子图中拥有的邻居数量是不同的, 所以每个节点的计算负载并不均衡. AliGraph则提供了多种内置的图分区算法供用户选择, 比如适合处理稀疏图的METIS方法, 适合稠密图的点割和边割方法, 这种方法虽然为用户提供了多种选择, 但需要用户自己去判断使用哪种分区方式, 给用户造成很大不便. Roc采用一种在线线性回归模型来优化图分区. 这种基于线性回归的图分区方法在图神经网络系统中能够达到比传统分区更好的性能.

(4) 通信优化策略. 针对通信开销影响分布式系统性能的问题, Euler采用的是缓存对应顶点k阶内的邻居顶点信息, 这种方式虽然直接避免了计算节点之间的通信, 但是造成了很严重的内存浪费, 并且在幂律分布的图中还会使各个计算节点之间负载不均衡. AGL采用的策略和Euler相同, 但是AGL提出了重新索引的策略来均衡负载. AliGraph提出了一种缓存重要顶点的邻居的方法来降低通信开销, 同时提出了一种对顶点重要性的度量标准, 既能有效减低通信开销, 又防止产生巨大的存储成本, 避免资源浪费. ROC引入了代价模型, 可以最大程度地减少CPU和GPU之间的数据传输. 这种动态的方法突破了手动优化的局限, 将影响通信的多种因素综合考虑, 从而更好的降低通信成本, 提高系统性能. PGL的分布式参数服务器提供了一种高效的参数更新策略: GeoSSD, 在全异步的条件下进行参数更新, 并重叠模型训练与节点通信, 在保证模型效果的前提下提升了训练效率.

(5)社区活跃度与系统易用性. PyTorch Geometric、DGL、AliGraph、Euler、PSGraph、PGL为开源系统, 这里的社区活跃度以GitHub上讨论区的数量为标准, 这其中最活跃的社区为PyTorch Geometric. 在系统易用性方面, 从配置文件的完整度、对其他系统的依赖度、用户使用的方便度多个角度综合考量, 这其中DGL和PyTorch Geometric的易用性排在前列, 而Euler与PSGraph虽然给出了配置文件, 但在配置系统时, 需要配置其他多个依赖包, 并且数据处理过程繁琐, 不易用户使用. 本文为系统的社区活跃度和易用性给出星级评价, 星级越高, 系统在这两方面表现越好, 其中空白符号表示系统未开源.

本文对目前的图神经网络系统从多个维度进行了综合分析, 对这些系统的共同特性进行提取, 并总结归纳, 见表1.

总结

本文首先简要介绍了图神经网络的发展, 并对典型的图神经网络算法的计算模式进行了介绍, 并简要分析了图神经网络训练的难点. 然后本文对现有图神经网络系统做了详细描述, 并对这些系统从系统架构、处理模型以及优化策略和系统易用性等多个角度进行分析和总结, 总结了针对图神经网络系统的多种优化技术, 最后使用目前可用的开源系统验证了现有分布式图神经网络系统的有效性. 经过论文分析与总结, 发现现有图神经网络系统仍存在以下问题, 同时也是未来的研究方向: 首先, 目前系统所采用的架构仍依赖于现有数据流框架, 现有数据流框架针对深度神经网络的运算做了一系列优化, 但缺少针对图操作的优化尤其是高效分布式图操作, 与这些框架结合起来搭建系统, 制约了分布式图神经网络系统的进一步发展. 第二, 目前系统所采用的小批量并行计算方式, 并不适用于基于谱方法的图卷积网络, 本文通过实验发现, 采用这种并行计算方式会对基于谱方法图卷积网络的训练精度产生影响. 第三, 图的分区操作和通信管理是影响系统性能的关键因素, 尽管目前的系统已经在这两方面提出多种优化, 减少了内存消耗和通信开销, 但这两者仍存在非常大的优化空间.

参考文献 

[1] Redmon J, Divvala S, Girshick R, Farhadi A. You only look once: Unified, real-time object detection. In: Proc. of the 2016 IEEE Conf. on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016. 779–788. [doi: 10.1109/CVPR.2016.91] 

[2] Ren SQ, He KM, Girshick R, Sun J. Faster R-CNN: Towards real-time object detection with region proposal networks. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2017, 39(6): 1137-1149. [doi:10.1109/TPAMI.2016.2577031] 

[3] Luong MT, Pham H, Manning CD. Effective approaches to attention-based neural machine translation. In: Proc. of the 2015 Conf. on Empirical Methods in Natural Language Processing. Lisbon: Association for Computational Linguistics, 2015. 1412–1421. [doi: 10.18653/v1/D15-1166] 

[4] Wu YH, Schuster M, Chen ZF, et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv: 1609.08144, 2016. 

[5] Hinton G, Deng L, Yu D, Dahl GE, Mohamed AR, Jaitly N, Senior A, Vanhoucke V, Nguyen P, Sainath TN, Kingsbury B. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 2012, 29(6): 82-97. [doi:10.1109/MSP.2012.2205597] 

[6] Sanchez-Gonzalez A, Heess N, Springenberg JT, Merel J, Riedmiller M, Hadsell R, Battaglia P. Graph networks as learnable physics engines for inference and control. In: Proc. of the 35th Int’l Conf. on Machine Learning. Stockholm: PMLR, 2018. 4470–4479. 

[7] Battaglia PW, Pascanu R, Lai M, Rezende DJ, Kavukcuoglu K. Interaction networks for learning about objects, relations and physics. In: Proc. of the 30th Int’l Conf. on Neural Information Processing Systems. Barcelona: NIPS, 2016. 4509–4517. [doi: 10.5555/3157382.3157601] 

[8] Hamilton WL, Ying R, Leskovec J. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017, 40(1): 52-74. http://arxiv.org/pdf/1709.05584