(1997-),女,硕士,主要研究领域为分布式系统
(1994-),男,博士生,主要研究领域为分布式图计算
(1995-),男,博士生,主要研究领域为分布式图计算
(1982-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为大数据处理和分布式系统
(1962-),男,博士,教授,博士生导师,CCF会士,主要研究领域为数据库和分布式系统
图神经网络(GNN)是一类基于深度学习的处理图域信息的方法, 它通过将图广播操作和深度学习算法结合, 可以让图的结构信息和顶点属性信息都参与到学习中, 在顶点分类、图分类、链接预测等应用中表现出良好的效果和可解释性, 已成为一种广泛应用的图分析方法. 然而现有主流的深度学习框架(如TensorFlow、PyTorch等)没有为图神经网络计算提供高效的存储支持和图上的消息传递支持, 这限制了图神经网络算法在大规模图数据上的应用. 目前已有诸多工作针对图结构的数据特点和图神经网络的计算特点, 探索了大规模图神经网络系统的设计和实现方案. 首先对图神经网络的发展进行简要概述, 总结了设计图神经网络系统需要面对的挑战; 随后对目前图神经网络系统的工作进行介绍, 从系统架构、编程模型、消息传递优化、图分区策略、通信优化等多个方面对系统进行分析; 最后使用部分已开源的图神经网络系统进行实验评估, 从精确度、性能、扩展性等多个方面验证这些系统的有效性.
Graph neural network (GNN) is used to process graph structure data based on deep learning techniques. It combines graph propagation operations with deep learning algorithms to fully utilize graph structure information and vertex features in the learning process. GNNs have been widely used in a range of applications, such as node classification, graph classification, and link prediction, showing promised effectiveness and interpretability. However, the existing deep learning frameworks (such as TensorFlow and PyTorch) do not provide efficient storage support and message passing support for GNN’s training, which limits its usage on large-scale graph data. At present, a number of large-scale GNN systems have been designed by considering the data characteristics of graph structure and the computational characteristics of GNNs. This study first briefly reviews the GNNs, and summarizes the challenges that need to be faced in designing GNN systems. Then, the existing work on GNN training systems is reviewed, and these systems are analyzed from multiple aspects such as system architecture, programming model, message passing optimization, graph partitioning strategy and communication optimization. Finally, several open source GNN systems are chosen for experimental evaluation to compare these systems in terms of accuracy, efficiency, and scalability.
深度学习在对象检测[
随着图领域深度学习方法逐渐受到广泛关注, 近些年出现了很多图神经网络算法, 这些方法通过在传统深度学习模型中添加图操作, 应用图的结构信息和属性信息, 来处理图数据的复杂性, 成为解决图学习问题的有效方法. 比较典型的工作有Structure2Vec[
图神经网络受到广泛关注的原因如下: 首先, 现有标准神经网络无法正确处理图数据的输入, 因为其按照特定顺序处理节点特征, 而图中的顶点没有自然顺序. 图神经网络算法采用在顶点上传播信息的计算方式, 忽略顶点的输入顺序解决了这个问题. 第二, 在标准神经网络中, 图中顶点的依赖关系仅能作为顶点特征输入, 而图神经网络算法根据图中顶点的依赖关系进行信息传播, 保留了图结构的信息, 为下游深度学习任务提供了更加完整的信息. 第三, 推理是高级人工智能的一个重要研究课题, 图神经网络强大的表示能力, 为进一步生成强大的神经模型提供了基础.
现有的深度学习框架如TensorFlow[
本文首先分析图神经网络算法的计算模式, 提出大规模图神经系统训练存在的挑战, 并对现有系统进行介绍. 然后从系统架构、通信优化等多个维度对这些系统进行详细的分析和对比, 对图神经网络系统的不同优化技术进行总结和分析, 并对目前已经开源的图神经网络系统设计实验, 从多个方面测评系统的性能, 验证系统有效性.
早期的图神经网络研究[
随着卷积神经网络在欧式数据上的成功应用, 比如图像分类、对象检测、机器翻译, 开始出现了图卷积的概念. CNN[
近些年提出了很多重新定义图卷积概念的方法, 主要分为两类. 基于谱方法图神经网络[
谱方法将图上的信号变换到谱域, 在谱域实现图卷积的定义, 再将结果变换到空间域. 较早出现的ChebyNet是基于谱方法的图卷积神经网络, 通过将谱域的卷积核做参数化, 并利用多项式的函数对卷积核近似, 来将参数进行降维, 且不需要做特征分解, 降低了计算代价. 除此之外, 还有AGCN等, 都属于基于谱方法的图卷积神经网络.
空间方法通过图上的信息聚合来定义图卷积, 通过将中心顶点的特征和其邻居的特征进行卷积, 来更新中心顶点特征. 空间方法的图卷积运算本质上是沿着边传播顶点信息. 其中具有代表性工作的是GCN, 它既是空间方法的起点, 也是谱方法的一个特例. 其他的基于空间方法的工作还有GraphSAGE、GAT等. 通常情况下顶点邻居分布并不均匀, GraphSAGE通过对每个顶点进行固定数量邻居的采样, 然后将获得的信息进行聚合来更新顶点. GAT针对每一个顶点计算相应的隐藏信息, 通过引入注意力机制, 可以将模型应用于未知图结构的数据, 在顶点分类任务中取得了比较好的结果.
后来又发展出了许多其他类型的图神经网络, 包括图自动编码器GAE[
图神经网络的典型计算过程: 本文结合一种广泛应用的图神经网络模型GraphSAGE, 简要介绍图神经网络的典型计算过程. GraphSAGE是一种用于学习顶点表示的图神经网络算法, 通过对顶点邻域进行采样和聚合来生成顶点的嵌入. 其中图
Visual illustration of GraphSAGE
GraphSAGE计算过程示意图
(1)对顶点
(2)在顶点上进行
(3)在第
(4)在聚合邻居顶点表示后, 将顶点当前层的表示与聚合的邻居向量连接起来, 输入到非线性激活函数中生成新的顶点表示.
(5)将顶点迭代
(6)在反向传播过程中, 计算第
(7)用
随着图神经网络在不同领域的应用越来越广, 对训练图神经网络系统的性能要求也越来越高. 结合对图嵌入[
(1)现有深度学习系统不能很好地抽象图传播过程. 现有的深度学习系统处理的是规则数据, 规则数据中每个样本的计算图是独立的, 与其他样本无关, 而图神经网络是将深度神经网络和迭代图传播结合起来进行计算的, 图数据的每个样本(即图顶点)之间具有依赖性, 所以现有系统不能自然地表达和有效地支持图传播模型. 如何突破现有框架的局限, 设计一种适用于图神经网络的系统架构是发展图神经网络的重要问题;
(2)训练大规模图神经网络的计算、存储复杂度高. 真实世界中的尺寸都非常大, 而且由于顶点之间具有复杂的依赖性, 随着图神经网络层数的增加, 计算成本和内存空间需求呈指数级增长. 例如Facebook的社交网络图包含超过20亿个顶点和1万亿条边, 这种规模的图在训练时可能会产生100 TB的数据. 所以针对大图的训练, 如何设计计算和存储策略以利用有限的资源来使系统达到理想的性能也是发展图神经网络系统的一大挑战;
(3)图计算局部性差导致系统开销问题. 真实世界图的稀疏性会导致非常差的空间局部性, 在单机系统中这会导致Cache命中率降低. 而在分布式系统中, 这会导致频繁的跨节点访问, 进而产生大量的消息传递开销. 所以如何针对图的特殊性质减少系统开销是提高系统性能的一大挑战;
(4)图的幂律分布导致分布式计算负载均衡问题. 对于具有数亿个顶点的大型图, 通常需要对图进行分布式处理, 图神经网络算法不同于传统的图算法, 平衡的图分区不仅依赖于分区内的顶点数量, 还依赖于分区内顶点邻居的数量, 多层图神经网络模型中不同顶点多阶邻居的数量可能相差极大, 并且这些分区之间需要频繁的数据交换, 如何对图数据进行合理的分区来保证分布式训练的性能是对于分布式系统的重大挑战;
(5)异构计算架构中的任务划分和负载调度的合理性问题. GPU的广泛应用为训练深度学习模型带来了很多机会和挑战. 在利用GPU加速神经网络的训练时, 通常将数据存储在主机内存中, 在计算时需要将数据传输到GPU, 由于图神经网络算法在反向传播阶段的复杂性, 需要频繁的在主机和GPU之间进行数据传输, 如何设计合理的调度方案来最大程度地减少数据传输成本也是提高系统性能的一大挑战.
为了应对这些挑战, 出现了很多针对图神经网络的训练框架, 其中单机系统如PyTorch Geomertic、DGL、NeuGraph. 图神经网络通常处理非常大且不规则的图, 这些大图无法存储在单个设备中, 因此必须以分布式方式进行分区和处理, 其中分布式图神经网络框架如Euler、AliGraph、Roc、AGL. 接下来本文将介绍若干典型的单机图神经网络系统以及分布式图神经网络系统.
图神经网络算法将深度神经网络的运算(如卷积、梯度计算)与迭代图传播结合在一起: 每个顶点的特征都是由其邻居顶点的特征结合一组深度神经网络来计算. 但是, 现有的深度学习框架不能扩展和执行图传播模型, 因此缺乏高效训练图神经网络的能力, 并且现有框架一般采用数据/模型并行来分布式训练深度神经网络, 这种并行计算方法难以直接应用于图神经网络, 因此限制了训练大规模图神经网络的能力. 而现有的图处理系统虽然能够表示迭代图传播模型, 并能有效支持大规模图的迭代计算, 但是缺乏支持神经网络计算的关键能力, 如张量抽象、自动微分等. 因此, 为了支持图神经网络在大规模图上的应用, 以及对更复杂图神经网络结构的探索, 开发针对图神经网络的训练系统是十分有必要的.
目前具有代表性的图神经网络框架: DGL[
DGL是用于图结构深度学习的Python库, 通过与主流的深度学习框架集成, 能够实现从传统的张量运算到图运算的自由转换. DGL提供基于消息传递的编程模型来完成图上的计算, 结合消息融合等优化技术使系统达到了比较好的性能.
DGL的API主要有两部分, 一是消息函数:
二是累和函数:
其中,
消息张量的大小正比于图中边的数量, 因而当图增大时, 消息张量消耗的内存空间也会显著上升. 为了避免生成消息张量带来的额外存储开销, DGL实现了消息融合技术, 将send函数和recv函数合并成了
PyTorch Geometric, 是一个基于PyTorch构建的深度学习库, 可以对非结构化数据进行建模和训练. 该库利用专用CUDA内核实现了高性能训练. PyTorch Geometric提供一个简单的消息传递API, 将卷积算子推广到不规则域, 具体表示为:
其中,
NeuGraph提出了一种新的框架, 根据图神经网络是将标准神经网络与迭代图传播结合起来的这一特点, NeuGraph在数据流中引入以顶点为中心的消息传递模型, 将图模型和数据流模型结合, 来支持并行图神经网络计算. NeuGraph还将图计算的优化方法如数据分区、调度, 引入到了数据流框架中, 来支持高效的图神经网络训练.
NeuGraph提出了一种新的处理模型SAGA-NN, 它将数据流和顶点编程模式相结合来表示图神经网络的计算. SAGA-NN将前向计算分为4个阶段: Scatter、ApplyEdge、Gather和ApplyVertex. ApplyEdge和ApplyVertex提供了两个用户定义函数, 供用户在边和顶点上声明神经网络计算. ApplyEdge函数定义每个边上的计算, 以
NeuGraph在数据流抽象的基础上引入了特定的图分区方法, 可以解决GPU内存的物理限制问题. 通过2D图分区方法, NeuGraph将顶点数据分割成
EnGN是一种处理大规模图神经网络的专用加速器架构, 并且EnGN提出了一种使用专用架构的以边为中心的数据流模型. EnGN将常见的图神经网络计算模式抽象为特征提取, 聚合和更新3个阶段. 在特征提取阶段, 神经网络来压缩图中每个顶点的属性. 聚合阶段通过聚合在特征提取中生成的每个顶点的邻居属性, 来产生统一的输出特征, 其中聚合函数的选择包括各种算术运算, 例如max, min和add. 在传播迭代结束时, 更新阶段会利用学习到的参数进一步压缩聚合阶段中获得的输出特征, 并在输出之前将非线性激活函数或GRU/LSTM函数应用于图的每个顶点.
在以边为中心的数据路模型基础上, EnGN集成了一个神经图处理单元(NGPU), 能够在统一的体系结构中执行特征提取, 聚合和更新操作. 它具有一个PE数组, 每个PE单元都包含一个本地寄存器, 用于存储临时结果并充当PE间通信的中介. EnGN提出了图属性感知(GPA)数据流, 来分离顶点的输入属性和硬件计算结构. 以这种方式, PE阵列的同一列中的每个PE负责顶点属性的单个维, 而同一行中的每个PE处理单个顶点. 输入顶点属性的尺寸变得独立于硬件体系结构, 并且可以连续地注入到PE阵列中, 而与阵列大小和属性尺寸无关. 通过这种方式, 处理单元可以处理具有任意尺寸属性的顶点. RER (ring-edge-reduce)阵列同一列中的每个PE连接到环形网络中的邻居, 同一列中的每个PE仅与其两个最近的邻居(北, 南)通信. PE将其数据发送到北部邻居, 并接收从南部邻居发送的数据以进行汇总. 以此方式, PE可以基于环型数据流从边解析的控制信号来选择要聚合的相关顶点.
Euler是集成了深度学习系统TensorFlow的基于CPU的分布式图神经网络框架, 支持图分割和高效稳定的分布式训练, 可以轻松支持数十亿点、数百亿边的计算规模.
Euler系统抽象为图引擎、图操作算子、算法实现3个部分, 可以快速地扩展一个图学习算法. 该系统整体可以分为3层: 最底层的分布式图引擎, 中间层图语义的算子, 高层的图表示学习算法. 在底层图引擎部分, Euler采用了分布式存储的架构, 整个图在引擎内部用哈希方法切分为多个子图, 每个计算节点被分配一个或几个子图. 在进行迭代图广播时, 顶层操作被分解为多个对子图的操作, 并由各个计算节点并行执行, 充分利用了各个计算节点的计算能力. 在中间层Euler提供了多种图操作的算子, 如全局带权采样点和边, 基于给定顶点的邻居操作等等. 利用灵活的图操作算子, Euler不仅支持传统的以图为中心的学习模式, 且可以把基于图的学习方法结合到传统的学习任务中, 实现端到端训练. Euler在算法层内置了多种常见算法以及几种创新算法, 如Scalable-GCN, 一种加速GCN训练的方法.
AliGraph是由阿里巴巴开发的图神经网络系统, AliGraph总体上由5层组成, 如
Architecture of the AliGraph system[
AliGraph系统架构
AliGraph建立在分布式环境中, 因此整个图被划分并分别存储在不同的节点中. 图分区的目标是最大程度地减少顶点在不同计算节点中的交叉边的数量. 系统实现了4种内置的图形分区算法: METIS、顶点切割和边缘切割分区、二维分区、流式分区策略. 除此之外, 为了进一步降低通信开销, AliGraph提出了一种在本地缓存重要顶点邻居的优化方法, 但顶点邻居过多会导致存储成本增加. 通过对顶点重要程度的度量, AliGraph可以在通信成本和存储成本之间做到很好的平衡. 并且AliGraph证明了只需要缓存少量重要顶点即可实现通信成本的显著降低.
Roc是用于快速图神经网络训练的分布式多GPU框架. 其性能提升得益于Roc的图分区和内存管理优化实现. 系统利用多计算节点多GPU的计算资源在完整的现实世界图上训练大型图神经网络模型, 来达到更好的性能和可扩展性.
图神经网络算法将计算密集型深度神经网络操作与数据密集型图传播混合在一起, 因此在分布式环境中实现负载均衡的图分区是非常困难的. Roc使用在线线性回归模型来对图分区进行建模. 在图神经网络架构的训练阶段, Roc建立了一种成本模型, 用于预测在输入图上执行图神经网络操作的执行时间, 成本模型既包含与图相关的部分, 如图中顶点和边的数量, 也包含与硬件相关的部分, 如执行该操作的GPU内存访问的次数. 在图神经网络的每次训练迭代期间, Roc使用成本模型来预测计算图分区, 并使用图分区的结果来并行化训练. 在每次训练迭代结束时, 子图的实际运行时间将发送回Roc图分区模块, 该程序通过最小化实际运行时间与预测运行时间之间的差异来更新成本模型. Roc还将GPU内存管理形式化为成本最小化问题: 给定输入图, 图神经网络结构和GPU设备, 找到张量子集以缓存在GPU内存中, 最大程度地减少CPU和GPU之间的数据传输. 为了快速求解成本模型, Roc引入了动态规划算法以快速找到全局最优解.
PSGraph使用Spark和PyTorch作为资源管理和计算平台, 使用参数服务器架构作为分布式训练架构. PSGraph通过参数服务器为Spark提供支持, 以有效地训练数十亿规模的图数据, 并将PyTorch集成到Spark中来实现神经网络的训练.
PSGraph由参数服务器、计算引擎和主节点构成. 参数服务器用于存储高维数据和模型, 它支持不同的数据结构, 除此之外, PSGraph还为用户提供实现新数据结构的接口, 支持按行索引和列索引的数据分区方式, 提供不同的同步协议以控制工作进程之间的同步, 以及实现多种常用运算符来操作参数服务器上的数据, 每个参数服务器定期将本地数据分区存储到HDFS. 计算引擎由Spark和PyTorch实现, 用于存储数据、计算并创建参数服务器代理来管理Spark和参数服务器之间的数据通信. 主节点负责资源分配、任务监视和故障恢复.
AGL是用于工业用途图学习的集成系统. 在AGL系统中图神经网络的计算构建于消息传递模型基础之上, 其迭代图传播过程使用MapReduce来实现. 在训练图神经网络阶段, AGL通过构造k-hop邻域, 来提供信息完整的子图, 通过从边合并邻居的消息来计算每个顶点的嵌入. AGL将原始图分解成子图, 来使每个顶点的计算图可以独立于其他顶点.
AGL的核心有3个模块: GraphFlat, GraphTrainer和GraphInfer. GraphFlat是基于消息传递的高效分布式图生成器, 用于生成顶点的
PGL是由百度开发的基于PaddlePaddle的高效灵活的图学习框架. PGL实现了高度并行的图神经网络消息传递机制, 并依托于自研的分布式图引擎以及大规模参数服务器PaddleFleet, 可以支持十亿节点百亿边的超大规模图训练.
PGL总体上由3层组成, 最底层分布式图引擎、分布式图训练模块以及分布式参数服务器PaddleFleet. 底层分布式图引擎以图切片的形式存储超大规模图, 提供图信息访问、子图采样等操作算子, 由上层模型调用. PGL预置了丰富的图学习模型, 这些模型涵盖了同构与异构、图表示学习与图神经网络等样例. 分布式参数服务器PaddleFleet提供了一种高效的参数更新策略: GeoSSD, 在全异步的条件下进行参数更新, 降低了节点间通信对训练速度的影响.
PGL采用类似于DGL的消息传递范式构建图神经网络的接口, 能够帮助用户快速构建自定义图神经网络, 用户只需要编写send和recv函数即可. 目前, PGL提供两种聚合方法. 一种是Scatter-Gather, 用于常规聚合计算. 另一种是基于LodTensor特性实现的并行通用的消息聚合方法. PGL将消息组织为PaddlePaddle中的LodTensor, 将消息作为可变长度序列进行拼接, 并引入一个索引数据结构来记录张量序列, 利用LodTensor的特性可以快速的执行并行聚合. 此外, PGL还支持异构图学习, 可以对包含多个节点类型和多个边类型的异构图进行建模, 并且可以描述不同类型之间的复杂连接.
本节从系统架构、处理模型、图分区策略、通信优化策略、以及社区活跃度与系统易用性方面, 对现有图神经网络系统进行分析和对比, 并从多个维度对系统的特点进行总结, 以表格的形式清晰的展示系统的共性与不同, 来为研究人员提供有效参考.
(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采用的是缓存对应顶点
(5)社区活跃度与系统易用性. PyTorch Geometric、DGL、AliGraph、Euler、PSGraph、PGL为开源系统, 这里的社区活跃度以GitHub上讨论区的数量为标准, 这其中最活跃的社区为PyTorch Geometric. 在系统易用性方面, 从配置文件的完整度、对其他系统的依赖度、用户使用的方便度多个角度综合考量, 这其中DGL和PyTorch Geometric的易用性排在前列, 而Euler与PSGraph虽然给出了配置文件, 但在配置系统时, 需要配置其他多个依赖包, 并且数据处理过程繁琐, 不易用户使用. 本文为系统的社区活跃度和易用性给出星级评价, 星级越高, 系统在这两方面表现越好, 其中空白符号表示系统未开源.
本文对目前的图神经网络系统从多个维度进行了综合分析, 对这些系统的共同特性进行提取, 并总结归纳, 见
Summarization of GNN systems
系统总结
维度 | PyG | DGL | NeuGraph | EnGN | AliGraph | Euler | Roc | PSGraph | AGL | PGL |
并行处理架构 | 单机多卡 | 单机多卡 | 单机多卡 | ASIC | 多机分
|
多机分
|
多机多卡 | 多机分
|
多机分
|
多机分
|
底层深度学习框架 | PyTorch | 混合 | TensorFlow | 自研 | TensorFlow | TensorFlow | 自研 | PyTorch | 自定义 | PaddlePaddle |
编程模型 | 消息传递 | 消息传递 | 以顶点为中心 | 以边为
|
以顶点为中心 | 以顶点为中心 | - | 以顶点为中心 | 消息传递 | 消息传递 |
消息传递优化 | - | 消息融合 | SAG融合 | 属性感知 | 顶点采样 | 顶点采样 | - | 顶点采样 | 重新索引 | LodTensor |
图分区
|
- | - | 2D划分 | 图切片 | 多种方法 | 哈希 | 在线线性优化 | 图切片 | - | 图切片 |
通信优化策略 | - | - | - | 多级缓存 | 缓存重要
|
缓存 |
动态编程算法 | 缓存 |
缓存 |
GeoSSD |
社区
|
★★★ | ★★ | ☆ | ☆ | ★ | ★★ | ☆ | ★★ | ☆ | ★ |
系统
|
★★★ | ★★★ | ☆ | ☆ | ★★ | ★ | ☆ | ★ | ☆ | ★ |
本节结合系统特点, 对现有系统所采用的优化技术进行总结和分析, 并将优化技术汇总分类, 详细阐述具体优化技术的实施方案. 在本节最后, 对目前训练大规模图神经网络存在的挑战、具体优化方案、图神经网络系统三者之间的关联关系做出详细解释, 表明了现有的优化技术是如何解决目前存在的挑战, 以及这些优化技术被哪些系统所采用.
图神经网络的并行计算方式与其他深度学习方法的计算方式不同. 首先, 图神经网络的计算具有顶点依赖性, 以卷积图神经网络为例, 对于一个图, 图卷积网络采用图卷积运算逐层的获取顶点的信息, 在每一层, 要获取一个顶点的表示, 需要通过采集邻居顶点的信息, 然后进行线性变换.
An example of two-layer convolution graph neural network
两层卷积图神经网络示意图
第1种是小批量训练方法的并行计算方法. 这种训练方法通过对目标顶点进行一阶或多阶邻居的采样, 将训练目标顶点所需要的每层邻居都采样到内存中, 然后计算目标顶点的表示并用于最终任务. 这种计算方法会造成大量的计算开销和内存开销, 但其通过采样将整张图上的计算分解为多个独立的计算任务, 从而为并行计算提供了可能. 如
Parallel computation method for small batch training
小批量训练并行计算方法
第2种是利用图数据流的并行计算方法. 这种方法将图处理的方式引入到图神经网络的并行计算中, 首先将图的边信息, 即图的邻接矩阵进行分块处理, 在并行处理边的信息块时, 引入边对应的源顶点信息和目标顶点信息来计算边上的中间信息, 然后根据边对应的目的顶点对中间信息进行聚合计算, 在处理完所有边块之后再对聚合的结果进行变换, 并将输出结果作为下一层新的顶点特征.
Graph data flow parallel computation method
图数据流并行计算方法
第3种是基于MapReduce模型的并行计算方法. 计算过程如
MapReduce-based parallel computation method
基于MapReduce的并行计算方法
在处理图神经网络的计算时, 一种广泛采用的思路是先将源顶点的信息发送到边上, 在边上结合边自身的信息生成中间消息, 最后由目的顶点将对应的中间消息进行聚合, 并结合自身信息输入到神经网络中进行计算生成新的顶点表示. 但是通常情况下, 图中的顶点的邻居不止一个, 因此边的数量会远远多于顶点的数量, 所以生成的中间消息的数量急剧增大, 当图增大时, 中间消息消耗的内存空间也会显著上升, 这会导致计算效率的降低和计算资源利用率的下降.
在大多数图神经网络算法中, 边上的函数通常是元素级操作, 例如GCN算法在边上的操作是乘法, 乘法操作的变量是边对应的两个顶点的度, 在这种情况下, 对于每个目的顶点, 可以使用乘法对指向目的顶点的边进行GCN算法相应的操作, 将生成的结果直接累加到目的顶点上, 最后根据目的顶点的最终结果进行计算和更新, 这种计算方式无需消耗任何额外成本来创建和维护中间消息.
Message fusion technology
消息融合技术
在分布式计算图神经网络时, 进行图分区后会把所有子图都发送到不同的计算节点, 然后并行执行图神经网络的计算. 对图神经网络的训练, 通常需要用GPU来进行加速, 但是GPU的内存通常比较小, 为了支持大规模的图, 不需要将与每个子图相关的所有中间结果都放入GPU内存中, 而是使用空间较大的主存来保存所有数据, GPU用来计算并起到缓存部分数据的作用. 但是, 在GPU和主机之间传输数据会对运行时性能产生影响, 所以应该以最大程度地减少数据传输. 一种最直接的策略就是缓存, 通过在GPU端缓存一部分数据信息来避免重复的数据传输. 那么, 如何执行缓存策略来使数据移动产生的开销最小, 更进一步, 如何利用除了直接缓存以外的方式来进一步减少数据移动.
利用调度方式来减少数据移动[
Scheduling method
调度方式
利用动态内存管理来减少数据移动[
通常真实世界图数据往往服从幂律分布, 所以不同顶点的访问频率差异会很大, 高阶顶点的访问频率可能是低阶顶点访问频率的数百倍甚至上千倍, 这会导致严重的访问不平衡问题, 而图神经网络的计算依赖于顶点的邻居, 所以对于高阶顶点的邻居的访问频率也会随之上升. 在分布式情况下, 频繁的访问会带来大量的通信开销, 并且高阶顶点的邻居通常数量庞大, 通过高阶顶点来访问其邻居的开销会严重影响系统的性能, 降低训练效率.
目前一种直接的想法是在每个计算节点中, 在本地缓存一些重要顶点的邻居来降低通信成本[
AliGraph提出将顶点
在图神经网络的训练中, GPU的有效利用对于提升性能至关重要, 特别是对于大型图. 由于GPU内存的物理限制, 大图数据往往无法全部加载到GPU存储器, 因此可以将图的顶点信息和边信息进行切分. 2D图划分是一种特定于图的分区方式, 通过将图数据分割成块, 可以对信息进行分批处理. 对于每一个边数据块, 首先输入其对应的原顶点属性和目的顶点属性块, 然后根据算法对边块对应的顶点信息进行计算并生成中间数据块, 最后再根据目的顶点对中间数据块进行聚合计算生成新的顶点数据块. 除了该种图划分方法, 顶点切割分区、边缘切割分区和流式分区都是可以应用于图神经网络的分区策略.
图神经网络将计算密集型的深度神经网络与数据密集型的图传播操作混合在一起, 并且顶点计算具有依赖性, 每个顶点的计算负载不一样, 使得在分布式情况下难以静态计算良好的负载平衡分区. Roc采用的在线线性回归模型可以用于优化图分区. 在图神经网络系统的训练阶段, 学习一种成本模型, 用于预测在输入图上执行图神经网络操作的执行时间. 为了获得执行图神经网络操作的运行时性能, 成本模型既包含与图相关的特征, 如图中顶点和边的数量, 也包含与硬件相关的特征, 如执行该操作的GPU内存访问次数. 在训练迭代期间, Roc使用成本模型中的预测结果来计算新的图分区, 并使用新的图分区进行并行化训练. 在每次训练迭代结束时, 子图的实际运行时间将发送回图分区程序, 该程序通过最小化实际运行时间与预测运行时间之间的差异来更新成本模型. 实验表明这种基于线性回归的图分区方式的性能比现有的图分区策略高1.4倍.
针对大规模图神经网络训练存在的挑战, 本节总结了多种优化技术, 并详细阐述了各典型系统的解决方案.
The correlations between challenges, solutions, and systems
挑战-解决方案-系统关联关系
本文对现有开源的图神经网络系统Euler、PyTorch Geometric、DGL以及AliGraph进行配置, 并从多个维度测试系统性能. 所有单机系统的实验都独立运行于相同实验环境中CPU: Intel(R) Core(TM) i7-7800X; 运行内存: 64 GB; GPU: NVIDIA Corporation Device GT 1080×2; 显存: 11 GB. 可扩展性实验运行于阿里云平台. 实验测试所采用的算法包括: 图卷积神经网络GCN、图注意力网络GAT、以及归纳式学习算法GraphSAGE. 本文的实验设置总结于
Experimental setup
实验设置
环境及设置参数 | 对应值 |
CPU | Intel(R) Core(TM) i7-7800X @ 3.50 GHz |
内存 | 50 GB |
显卡 | NVIDIA Corporation Device GT 1080×2 |
测试系统 | Euler PyG DGL AliGraph |
数据集 | Cora Citeseer Pubmed Google |
算法 | GCN GAT GraphSAGE |
实验使用的数据集包括: Cora、Citeseer、PubMed[
本文从多个方面对图神经网络系统进行了测试. 首先, 论文将图神经网络算法在原始论文中提供的精确度作为基线, 与测评系统的实验准确度进行比较, 以验证测评系统训练图神经网络模型的有效性. 这里的有效性是指系统训练后的算法模型能够在给定数据集的测试精度上与原论文基本保持一致. 第二, 论文对测评系统训练图神经网络模型的时间进行比较, 以证明系统的性能, 为了减少差异, 论文为每个实验记录了10次运行后的平均结果. 通过分析实验结果, 论文进一步验证了上述总结的优化技术的有效性. 第三, 为证明小批量训练方法对基于谱方法的GCN模型精度的影响, 论文采用小批量训练方法来分布式训练GCN模型, 将结果与全批量训练的精确度进行对比. 第四, 为测评系统的存储复杂度, 论文记录各系统训练图神经网络模型时的内存消耗. 第五, 论文针对分布式系统进行实验, 以验证其可扩展性. 大规模图神经网络的训练必须依靠分布式来实现, 而对于分布式系统来说, 能否在扩展性方面实现线性加速是衡量系统性能的重要指标.
Basic information of the datasets
数据集基本信息
数据集 | Cora | Citeseer | PubMed | Web-Google | |
节点 | 2708 | 3327 | 19717 | 232965 | 875713 |
边 | 5429 | 4732 | 44338 | 11606919 | 5105039 |
特征 | 1433 | 3703 | 500 | 603 | 300 |
类型 | 引文网络 | 引文网络 | 引文网络 | 社交网络 | 网页超链接 |
(1)精度.
The comparison of accuracy for GNN systems on various datasets
不同系统在不同数据集上训练图神经网络算法的精度(%)
数据集 | 算法 | 原始论文精度 | DGL | PyTorch Geometric | Euler |
Cora | GCN | 81.5 | 81.0 (0.5) | 80.2 (1.3) | 80.7 (0.8) |
GAT | 83.0 | 83.0 (0.0) | 82.0 (1.0) | 82.0 (1.0) | |
GraphSAGE | - | 82.9 | 78.0 | 83.4 | |
PubMed | GCN | 79.0 | 79.0 (0.0) | 81.4 (2.4) | 79.1 (0.1) |
GAT | 79.0 | 78.8 (0.2) | 80.0 (1.0) | 78.9 (0.1) | |
GraphSAGE | - | 78.3 | 80.1 | 81.7 | |
Citeseer | GCN | 70.3 | 70.8 (0.5) | 71.4 (1.1) | 70.8 (0.5) |
GAT | 72.5 | 70.6 (1.9) | 72.8 (0.3) | 72.0 (0.5) | |
GraphSAGE | - | 70.4 | 70.8 | 71.3 |
(2)性能. 本文文首先对比了PyG-CPU, DGL-CPU, Euler这3个系统在GCN和GAT算法上的性能, 实验使用了Cora、Citeseer、PubMed[
Performance comparison chart (PyG-cpu vs. DGL-cpu vs. Euler)
PyG-CPU、DGL-CPU、Euler性能对比图
然后本文对比了PyG-GPU, DGL-GPU在GCN、GAT、GraphSAGE这3个算法上的性能, 在Cora、Citeseer、PubMed[
Performance comparison chart (PyG-GPU vs. DGL-GPU)
PyG-GPU、DGL-GPU性能对比图
小批量并行训练方式对基于谱方法GCN模型精度的影响. 基于空间方法的图卷积网络使用的是小批量梯度下降方法, 这种方法可以直接用于分布式训练环境中. 而基于谱方法GCN的训练与其不同, 使用的是全批量梯度下降方法, 其中的图卷积运算需要利用图中顶点之间的交互来传播顶点的特征向量, 计算每个样本的梯度无法被分解, 所以无法在分布式环境中直接使用全批量梯度下降方法训练GCN. 目前大多数系统采用的分布式训练方法是: 对图中用于最终任务的顶点进行
Accuracy comparison chart (GCN-single vs. GCN-distributed)
GCN单机与分布式精度对比图
(3)内存消耗.
Memory consumption(GB) for 200 epochs of the systems
系统训练200个epoch的内存消耗(GB)
数据集 | 算法 | DGL | PyTorch Geometric | Euler |
Cora | GCN | 0.91 | 0.38 | 0.57 |
GAT | 0.31 | 0.51 | 0.90 | |
PubMed | GCN | 0.43 | 0.51 | 1.12 |
GAT | 0.47 | 0.51 | 0.91 | |
Citeseer | GCN | 0.38 | 0.51 | 0.47 |
GAT | 0.47 | 0.73 | 0.72 | |
GCN | 9.47 | 42.93 | 5.16 | |
GAT | 45.91 | 内存溢出 | 4.02 |
(4)可扩展性. 本文对现有分布式图神经网络系统AliGraph进行实验, 记录其在80万个顶点500万条边的Google数据集[
Training time(one epoch) of Aligraph
Aligraph训练一个epoch所需时间
Scalability comparison of multi-GPU(PyG vs. DGL)
单机多卡可扩展性对比(PyG vs. DGL)
本文首先简要介绍了图神经网络的发展, 并对典型的图神经网络算法的计算模式进行了介绍, 并简要分析了图神经网络训练的难点. 然后本文对现有图神经网络系统做了详细描述, 并对这些系统从系统架构、处理模型以及优化策略和系统易用性等多个角度进行分析和总结, 总结了针对图神经网络系统的多种优化技术, 最后使用目前可用的开源系统验证了现有分布式图神经网络系统的有效性. 经过论文分析与总结, 发现现有图神经网络系统仍存在以下问题, 同时也是未来的研究方向: 首先, 目前系统所采用的架构仍依赖于现有数据流框架, 现有数据流框架针对深度神经网络的运算做了一系列优化, 但缺少针对图操作的优化尤其是高效分布式图操作, 与这些框架结合起来搭建系统, 制约了分布式图神经网络系统的进一步发展. 第二, 目前系统所采用的小批量并行计算方式, 并不适用于基于谱方法的图卷积网络, 本文通过实验发现, 采用这种并行计算方式会对基于谱方法图卷积网络的训练精度产生影响. 第三, 图的分区操作和通信管理是影响系统性能的关键因素, 尽管目前的系统已经在这两方面提出多种优化, 减少了内存消耗和通信开销, 但这两者仍存在非常大的优化空间.
10.1109/CVPR.2016.91]]]>
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.
10.18653/v1/D15-1166]]]>
et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv: 1609.08144, 2016.]]>
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.
10.5555/3157382.3157601]]]>
Hamilton WL, Ying R, Leskovec J. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017, 40(1): 52–74.
10.1007/978-3-540-39658-1_52]]]>
10.5555/3295222.3295399]]]>
Jeong C, Jang S, Park E, Choi S. A context-aware citation recommendation model with BERT and graph convolutional networks. Scientometrics, 2020, 124(3): 1907–1922.
10.1145/3097983.3098061]]]>
10.1137/1.9781611974973.71]]]>
10.5555/3294771.3294869]]]>
10.1109/APWeb.2010.60]]]>
10.24963/ijcai.2017/250]]]>
Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019–1031.
et al. TensorFlow: A system for large-scale machine learning. In: Proc. of the 12th USENIX Conf. on Operating Systems Design and Implementation. Savannah: USENIX Association, 2016. 265–283. [doi: 10.5555/3026877.3026899]]]>
http://pytorch.org.]]>
Chen R, Shi JX, Chen YZ, Zang BY, Guan HB, Chen HB. PowerLyra: Differentiated graph computation and partitioning on skewed graphs. ACM Trans. on Parallel Computing, 2018, 5(3): 13.
Low Y, Bickson D, Gonzalez J, Guestrin C, Kyrola A, Hellerstein JM. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proc. of the VLDB Endowment, 2012, 5(8): 716–727.
10.1145/1807167.1807184]]]>
10.5555/3154630.3154684]]]>
Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G. The graph neural network model. IEEE Trans. on Neural Networks, 2009, 20(1): 61–80.
10.1109/IJCNN.2010.5596796]]]>
LeCun Y, Bengio Y, Hinton G. Deep learning. Nature, 2015, 521(7553): 436–444.
10.5555/3157382.3157527]]]>
Levie R, Monti F, Bresson X, Bronstein MM. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Trans. on Signal Processing, 2019, 67(1): 97–109.
10.24963/ijcai.2019/264]]]>
10.1609/aaai.v33i01.3301922]]]>
Cai HY, Zheng VW, Chang KCC. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Trans. on Knowledge and Data Engineering, 2018, 30(9): 1616–1637.
Cui P, Wang X, Pei J, Zhu WW. A survey on network embedding. IEEE Trans. on Knowledge and Data Engineering, 2019, 31(5): 833–852.
Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey. Knowledge-based Systems, 2018, 151: 78–94.
Wu ZH, Pan SR, Chen FW, Long GD, Zhang CQ, Yu PS. A comprehensive survey on graph neural networks. IEEE Trans. on Neural Networks and Learning Systems, 2021, 32(1): 4–24.
Liang SW, Wang Y, Liu C, He L, Li HW, Xu DW, Li XW. EnGN: A high-throughput and energy-efficient accelerator for large graph neural networks. IEEE Trans. on Computers, 2020.
https://github.com/alibaba/euler]]>
10.1109/ICDE48307.2020.00137]]]>
Zhu R, Zhao K, Yang HX, Lin W, Zhou C, Ai BL, Li Y, Zhou JG. Aligraph: A comprehensive graph neural network platform. Proc. of the VLDB Endowment, 2019, 12(12): 2094–2105.
https://github.com/PaddlePaddle/PGL]]>
10.1145/3097983.3098029]]]>
Sen P, Namata G, Bilgic M, Getoor L, Galligher B, Eliassi-Rad T. Collective classification in network data. AI Magazine, 2008, 29(3): 93.
http://snap.stanford.edu/data/web-Stanford.html]]>