【阅读】Distributed Graph Neural Network Training: A Survey——翻译

另一篇：【阅读】A Comprehensive Survey on Distributed Training of Graph Neural Networks

摘要

图神经网络（GNNs）是一种在图上学习的深度学习模型，并已成功应用于许多领域。尽管 GNN 有效，但 GNN 有效地扩展到大型图仍然具有挑战性。作为一种补救措施，分布式计算成为训练大规模 GNN 的一种有前途的解决方案，因为它能够提供丰富的计算资源。然而，图结构的依赖性增加了实现高效分布式 GNN 训练的难度，导致大量通信和工作负载不平衡。近年来，在分布式 GNN 训练方面做出了很多努力，并提出了一系列训练算法和系统。然而，缺乏对从图处理到分布式执行的优化技术的系统回顾。在本次调查中，我们分析了分布式 GNN 训练的三大挑战，即海量特征通信、模型精度损失和工作负载不平衡。然后，我们为分布式 GNN 训练中的优化技术引入了一种新的分类法，以应对上述挑战。新分类法将现有技术分为四类，即 GNN 数据分区、GNN 批处理生成、GNN 执行模型和 GNN 通信协议。我们仔细讨论了每个类别中的技术。最后，我们分别总结了用于多 GPU、GPU 集群和 CPU 集群的现有分布式 GNN 系统，并讨论了可扩展 GNN 的未来发展方向。

简介

        GNN 是处理图建模问题的强大工具，并已广泛应用于各种应用，包括社交网络（例如，社交垃圾邮件发送者检测 [87、112]、社交网络分析 [91]）、生物信息学（例如，蛋白质界面预测 [35]、疾病-基因关联 [83]）、药物发现 [11、66]、流量预测[61]、医疗保健 [2、21]、推荐 [32、49、 55、111]、自然语言处理 [134、145] 和其他 [26、85、133、141、144]。通过将图结构信息集成到深度学习模型中，GNN 可以获得比传统机器学习和数据挖掘方法明显更好的结果。

        GNN 模型通常包含多图卷积层，其中每个顶点聚合其邻居的最新状态，更新顶点的状态，并将神经网络（即转换）应用于顶点的更新状态。以传统的图卷积网络（GCN）为例，在每一层中，一个顶点使用求和函数聚合邻居状态和自己的状态，然后应用单层 MLP 来转换新状态。如果层数为 𝐿，则此类过程重复 𝐿次。第𝐿层生成的顶点状态被下游任务使用，如节点分类、链路预测等。在过去的几年中，许多研究工作在图神经网络模型的设计方面取得了显着进展。突出的模型包括 GCN [108]、GraphSAGE [46]、GAT [95]、GIN [118] 和许多其他特定于应用程序的 GNN 模型 [128、130]。迄今为止，有数十项调查审查了 GNN 模型 [114、116、135、147]。另一方面，为了有效地开发不同的 GNN 模型，基于各种深度学习库 [8、14、34、44、68、104] 提出了许多面向 GNN 的框架。提出了许多新的优化来加速 GNN 训练，包括 GNN 计算内核 [19、38、52、53、81、93、129]、高效编程模型 [51、113、117] 以及新硬件的充分利用 [18] , 42, 124, 148]。然而，这些框架和优化主要侧重于在单机上训练 GNN，而不太关注输入图的可扩展性。

        如今，由于海量大图数据的普遍存在，大规模图神经网络 [62, 70] 成为热门话题。具有数十亿个顶点和数万亿条边的图很常见，例如新浪微博、微信、Twitter 和 Facebook 中的社交网络。然而，大多数现有的 GNN 模型仅在小型图数据集上进行测试，无法或低效地处理大型图数据集 [50]。这是因为以前的 GNN 模型很复杂，在处理大型图时需要大量计算资源。一系列工作通过设计可扩展的 GNN 模型实现了大规模图神经网络。他们使用简化 [36、47、110]、量化 [4、33、54、71、90、100、101、107、139]、采样 [20、123、125] 和蒸馏 [24、121、131] 来设计高效模型。另一行工作采用分布式计算对 GNN 进行训练。因为在处理大图时，单个设备（如GPU）有限的内存和计算资源成为大规模GNN训练的瓶颈，而分布式计算提供了更多的计算资源（如多GPU、CPU集群等）来提高训练效率。在设计高效的分布式 GNN 训练框架（例如 PipeGCN [99]、BNS-GCN [98]）和分布式 GNN 训练系统（例如AliGraph [150]、DistDGL [142]、ROC [58]）方面已经做出了许多努力.

        在本次调查中，我们重点关注具有分布式计算的大型图神经网络的工作，也就是分布式 GNN 训练。它将模型训练的全部工作量分配给一组workers，所有workers并行处理工作量。然而，由于 GNN 中的数据依赖性，将现有的分布式机器学习方法 [96、103] 应用于 GNN 并非易事，因此提出了许多优化分布式 GNN 训练管道的新技术。尽管有很多关于 GNN 模型的调查 [114、135、147]，但据我们所知，系统地审查分布式 GNN 训练技术的努力很少。最近，Besta 等人[9] 只回顾了 GNN 的并行计算范式，而 Abadal [1] 从算法到硬件加速器对 GNN 计算进行了调查。

        为了清楚地组织分布式 GNN 训练的技术，我们引入了一个通用的分布式 GNN训练管道，它由三个阶段组成——数据分区、GNN 模型优化和梯度聚合。前两个阶段涉及 GNN 特定的执行逻辑，包括图处理和图聚合。最后一个阶段与传统的分布式机器学习相同。在这种通用分布式 GNN训练管道的背景下，我们讨论了分布式 GNN 训练的三个主要挑战，这些挑战是由图形数据中的数据依赖性引起的，并且需要新的分布式 GNN 特定技术。为了更好地帮助读者理解解决上述挑战的各种优化技术，我们引入了一种新的分类法，将这些技术分为四个正交类别，即 GNN 数据分区、GNN 批处理生成、GNN 执行模型和 GNN 通信协议。该分类法不仅涵盖了mini-batch 分布式 GNN 训练和全图分布式 GNN 训练中使用的优化技术，还讨论了从图处理到模型执行的技术。我们仔细审查了每个类别中的现有技术，然后描述了来自工业界或学术界的 23 个具有代表性的分布式 GNN 系统和框架。最后，我们简要讨论分布式 GNN 训练的未来方向。

        本次调查的贡献如下：

        • 这是第一个关注高效分布式 GNN 训练优化技术的调查，并且它可以帮助研究人员快速了解分布式 GNN 训练的概况。

        • 通过考虑端到端分布式GNN训练的生命周期，我们引入了分布式GNN训练技术的新分类。在高层，新的分类法由四个正交类别组成，即GNN数据分区、GNN批处理生成、GNN执行模型和GNN通信协议。

        • 我们为新分类法中的每个类别提供了详细而全面的技术摘要。

        • 我们审查了从工业界到学术界的 23 个具有代表性的分布式 GNN 培训系统和框架。

        • 我们讨论了分布式GNN 训练的未来方向。

2 图神经网络的预测

图和图分区。图 𝐺 = (𝑉 , 𝐸) 由顶点集 𝑉 和边集 𝐸 组成。顶点𝑣 ∈ 𝑉 的邻居集用𝑁 (𝑣)表示，𝑣 的程度用𝑑 = |𝑁 (𝑣)|表示。在有向图中，顶点𝑣 ∈ 𝑉 的传入和传出邻居的集合分别用𝑁𝑖𝑛 (𝑣) 和𝑁𝑜𝑢𝑡 (𝑣) 表示，对应度用𝑑𝑖𝑛 = |𝑁𝑖𝑛 (𝑣)|和𝑑𝑜𝑢𝑡 = |𝑁𝑜𝑢𝑡 (𝑣)|.一条边 𝑒 ∈ 𝐸 由 (𝑢, 𝑣) 表示，其中 𝑢, 𝑣 ∈ 𝑉。𝐺的相邻矩阵由𝑨表示，其中当(𝑢,𝑣)∈𝐸时，𝑨的条目𝑎𝑢𝑣等于1，否则𝑎𝑢𝑣=0。图中的每个顶点𝑣都有一个初始特征向量𝒙𝒗 ∈ R𝐷 ，其中𝐷是特征向量的维数，图的特征矩阵由𝑿表示。

        可以在分布式设置中对图形进行分区。对于边切割图分区𝐺 = (𝑉 , 𝐸) 分为𝑃 分区{𝐺𝑖 = (𝑉𝑖, 𝐸𝑖 )}, 1 ≤ 𝑖, 𝑗 ≤ 𝑃, 满足𝑉 = ∪𝑉𝑖, 𝑉𝑖 ∩ 𝑉𝑗 = ∅, 1 ≤ 𝑖, 𝑗 ≤ 𝑃. 交叉边的端点称为边界顶点𝐺 是内部顶点。对于顶点切割图分区𝑃 分区应满足𝐸 = ∪𝐸𝑖, 𝐸𝑖 ∩ 𝐸𝑗 = ∅, 1 ≤ 𝑖, 𝑗 ≤ 𝑃. 顶点可以在分区之间复制，并且顶点的复制数量𝑣 称为复制因子。当顶点的复制因子大于1时，该顶点称为边界顶点𝐺 是内部顶点。

图形神经网络（GNNs）。给定一个图表𝐺 具有相邻矩阵𝑨 和特征矩阵𝑿 其中每行是初始特征向量𝒙𝒗 顶点的𝑣 在图表中𝐺, 一𝑙-GNN中的第三层通过聚合来自相应邻域的特征来更新顶点特征，该过程可以在如下矩阵视图中形式化

其中，𝑯 𝒍 是隐藏嵌入矩阵，并且𝑯 0 = 𝑿 , 𝑾 𝒍−1是模型权重𝑨 是标准化的𝑨 和𝜎 是非线性函数，例如Relu、Sigmoid等。等式1是GNN计算的全局视图。GNN计算的局部视图是单个顶点的计算。给定一个顶点𝑣, 局部计算𝑙-消息传递模式[41]中的第层可以形式化如下

 其中，⊕是聚合函数，𝜙是更新函数，𝒉𝒍-1𝒆𝒖，𝒗是第(𝑙-1)层的边(𝑢,𝑣)的隐藏嵌入。

 GNN 训练方法。为了训练一个 GNN 模型，一个基本的解决方案是在单个 epoch 中更新一次模型参数，这种训练方法称为全图 GNN 训练。然而，全图 GNN 训练是内存密集型的 [108]，因为它需要访问整个训练图并且不能扩展到大图。或者，我们可以选择在单个 epoch 的过程中多次更新 GNN 模型参数。这被称为小批量 GNN 训练。一个 epoch 被分成多次迭代，每次迭代用 batch（也就是整个训练数据集的一个子集）更新 GNN 模型。一个小批量可以在一台机器上处理，也可以由多台机器协同处理（称为大批量训练）。图形采样是一种为 GNN 模型生成小批量的流行工具。到目前为止，已经提出了许多基于采样的 GNN [17、23、46、56、125、151]，根据不同类型，它们可以分为节点采样、层采样和子图采样。不同的批量生成方法会影响训练效率和训练精度。

3 分布式GNN训练与挑战

3.1 通用分布式GNN训练流水线

        为了更好地理解端到端分布式 GNN 训练的一般工作流程，我们将训练流水线分为数据划分、GNN 模型优化和梯度聚合三个阶段。图 1 可视化了端到端分布式 GNN 训练工作流程的高级抽象。

数据分区。这是一个支持分布式训练的预处理阶段。它将输入数据（即图形和特征）分配给 一组工人。考虑到 GNN 中的训练数据是相互依赖的，数据划分阶段变得比传统分布式机器学习中的更为复杂。如图 1 所示，分区数据（即子图）之间的跨worker边暗示了数据依赖性。如果我们承认分区之间的数据依赖性，分布式训练效率会因通信而降低；如果我们简单地忽略数据依赖性，模型的准确性就会被破坏。因此，数据分区是端到端分布式 GNN 训练效率的关键阶段。

GNN 模型优化。这是分布式 GNN 训练的核心阶段，它执行 GNN 模型的训练逻辑（即前向计算和反向计算）。我们进一步将这个阶段分为计算图生成、执行模型和通信协议。首先，每个 worker 从分区的输入图和特征生成一个计算图，然后用计算图执行 GNN 模型以计算损失和梯度。然而，由于数据依赖性，计算图的生成和 GNN 模型的执行与传统的深度学习模型有很大不同。如果不访问远程输入数据，可能无法正确生成小批量训练策略的计算图。执行模型涉及 GNN 模型的层图聚合，并且聚合表现出不规则的数据访问模式。在分布式全图训练中，各层中的图聚合需要通过通信协议访问顶点远程邻居中的隐藏特征，并且还应考虑层与层之间的同步模式。因此，与传统的分布式机器学习相比，由于 GNN 中的数据依赖性，计算图生成和模型执行变得更加复杂。

 梯度聚合。该阶段负责聚合最新的局部梯度以获得全局梯度并更新模型参数。在 GNN 的背景下，模型尺寸通常很小，模型更新逻辑与其他机器学习模型相同。经典分布式机器学习中现有的梯度聚合技术可以直接应用于分布式 GNN 训练。

3.2 分布式 GNN 训练的挑战

        由于数据依赖性，有效训练分布式 GNN 并非易事。我们总结了以下三大挑战。

 挑战 #1：海量特征交流。对于分布式 GNN 训练，在 GNN 模型优化阶段会产生大量特征通信。当GNN 模型以 mini-batch 方式训练时，计算图生成（即 mini-batch 构造）需要访问远程图和特征，如图 1 中的操作 1○ 以创建用于本地训练的批次。即使在使用集中式图存储（例如 CPU 内存）进行的多 GPU 训练中，计算图的生成也会导致从图存储到worker（例如 GPU 内存）的大量数据移动。现有的实证研究表明，小批量构建的成本成为端到端训练中的瓶颈 [57, 140]。当 GNN 模型以全图方式训练时，计算图可以与分区图相同而无需通信，但是每层中的图聚合需要访问顶点远程邻居中的隐藏特征（在图 1 中的操作 2 ○ ）导致大量隐藏特征（或嵌入）通信。总之，GNN 模型的分布式小批量训练和分布式全图训练都受到海量特征通信的影响。

挑战 #2：模型准确性的损失。 Mini-batch GNN 训练比全图训练更具可扩展性，因此被大多数现有的分布式 GNN 训练系统采用。然而，随着模型深度的增加，精确的小批量训练会遇到邻居爆炸问题。事实上的解决方案是通过采样或忽略跨worker边缘来构造一个近似的小批量。虽然近似的 mini-batches 提高了训练效率，但它不能保证理论上模型的收敛性 [58]。因此，对于分布式 mini-batch GNN 训练，我们需要在模型精度和训练效率之间做出权衡。此外，有发展全图分布式GNN训练的趋势，这种训练具有收敛性保证，能够达到与单节点训练相同的模型精度。

挑战 #3：工作负载不平衡。工作负载平衡是分布式计算中的一个内在问题。然而，GNN 模型的各种工作负载特征增加了在worker之间划分训练工作负载平衡的难度。因为很难以简单统一的方式对 GNN 工作负载进行建模。如果没有正式的成本模型，经典的图划分算法就不能用来平衡worker之间的 GNN 工作量。此外，分布式 mini-batch GNN 训练要求每个 worker 处理具有相同批大小（即子图大小）的相同数量的 mini-batch，而不是简单地平衡子图中的顶点数量。综上所述，在分布式环境下训练 GNN 很容易遇到工作负载不平衡的情况，从而导致 worker 相互等待，破坏训练效率。

 3.3 分布式 GNN 训练技术的分类

        为了通过解决上述挑战实现分布式 GNN 训练并优化效率，过去几年提出了许多新技术。大多数现有作品从系统或框架的角度展示了自己的技术贡献，并没有很好地从技术角度回顾相关工作。在本次调查中，我们根据端到端分布式训练管道中的阶段组织分布式 GNN 特定技术，从而引入了一种新的分类法。通过这样的设计，我们将分布式 GNN 训练流水线中相同阶段优化的类似技术整理在一起，帮助读者充分理解分布式 GNN 训练中不同阶段的现有解决方案。

        根据以往的实证研究，由于数据依赖性，分布式GNN训练的瓶颈一般出现在pipeline中的数据划分和GNN模型优化阶段，而新的 GNN 特定技术位于这些阶段。此外，各种训练策略（例如，小批量训练、全图训练）带来不同的工作负载模式，并导致在模型优化中使用不同的优化技术。例如，模型优化阶段的计算图生成对小批量训练很重要，而通信协议对全图训练很重要。因此，我们的新分类法将分布式 GNN 特定技术分为四类（即 GNN 数据分区、GNN 批处理生成、GNN 执行模型和 GNN 通信协议），如图 2 所示。在下文中，我们介绍了每个类别的概述类别。

 GNN 数据分区。在这个类别中，我们回顾了分布式 GNN 训练的数据分区技术。数据分区的目标是平衡工作负载并最小化 GNN 工作负载的通信成本。 GNN训练是分布式图计算的一个实例，很多传统的图划分方法可以直接使用。然而，由于 GNN 工作负载的新特征，它们对于分布式 GNN 训练来说并不是最优的。研究人员付出了很多努力来设计指导传统图形划分方法的 GNN 友好成本模型。此外，图和特征是 GNN 中两种典型的数据类型，它们都是分区的。一些作品将特征与图结构解耦并独立划分。在第 4 节中，我们详细阐述了现有的 GNN 数据分区技术。

GNN 批量生成。在这个类别中，我们回顾了用于小批量分布式 GNN 训练的 GNN 批量生成技术。小批量生成的方法会影响训练效率和模型精度。图采样是为大规模 GNN 训练生成小批量的一种流行方法。然而，标准的图采样技术没有考虑分布式环境的因素，并且一个worker上的每个采样器都会频繁访问其他worker的数据，从而导致大量通信。最近，引入了几种针对分布式设置优化的新GNN 批量生成方法。我们进一步将它们分为分布式采样小批量生成和基于分区的小批量生成。此外，已经对缓存进行了广泛研究，以减少 GNN 批处理生成期间的通信。在第 5 节中，我们详细阐述了现有的 GNN 批量生成技术。

GNN 执行模型。在这个类别中，我们回顾了计算图生成和计算图执行的执行模型。在计算图的生成过程中，采样和特征提取是占总训练时间的两个主要操作。为了提高效率，提出了不同的执行模型以充分利用计算资源。图聚合应该在计算图生成之后进行，我们称之为计算图执行。在此阶段，每个节点的邻居状态在前向计算中聚合，梯度在后向计算中分散回邻居。由于数据依赖性和不规则的计算模式，传统的机器学习并行模型（例如，数据并行，模型并行等）对于图聚合不是最优的，特别是当特征向量是高维时。从图算子执行顺序的角度，我们将计算图执行模型分为one-short执行模型和chunk-based执行模型。从图聚合的同步时效性角度，我们将计算图执行模型分为同步执行模型和异步执行模型。基于去除不同的同步点，异步执行模型可以进一步分为两类。这些技术的详细描述在第 6 节中介绍。

    GNN 通信协议。在这个类别中，我们回顾了分布式全图并行训练的通信协议。分布式全图训练的图聚合需要访问远程隐藏嵌入访问，因为顶点的邻居不能总是在图分区的本地。基于图聚合中的同步和异步执行模型，这些通信协议也可以分别分为同步通信协议和异步通信协议。前者假设在每一层中，模型访问最新的嵌入，而后者假设在每一层中模型被允许访问过时的嵌入（或历史嵌入）。第 7 节详细介绍了各种通信协议。

4 GNN 数据分区

        在本节中，我们回顾了分布式 GNN 训练中 GNN 数据分区的现有技术。图 3 描述了这些技术的概述。考虑到图和特征是 GNN 中两种典型的数据类型，我们将划分方法分为图划分和特征划分。优化目标是工作负载平衡以及通信和计算最小化，旨在解决挑战 #1 和 #3。此外，成本模型是捕获 GNN 工作负载特征的另一个关键组件。在下文中，我们首先介绍成本模型，然后分别讨论图形分区和特征分区。