点击上方“
PaperEveryday
”，选择加"
星标
"或“
置顶
”
顶会论文解读，第一时间分享
题目：
Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis
图神经网络的并行与分布式执行：深入并发性分析
作者：Maciej Besta 和 Torsten Hoefler
摘要
图神经网络（GNNs）是深度学习中最强大的工具之一。它们通常在无结构网络上解决复杂问题，如节点分类、图分类或链接预测，准确度很高。然而，GNNs 的推理和训练都很复杂，并且它们独特地结合了不规则图处理的特征与密集和规则计算。这种复杂性使得在现代大规模并行架构上有效执行 GNNs 变得非常具有挑战性。为了缓解这个问题，我们首先设计了一个 GNNs 中并行性的分类法，考虑了数据和模型并行性以及不同形式的流水线处理。然后，我们使用这个分类法来研究众多 GNN 模型、由 GNN 驱动的机器学习任务、软件框架或硬件加速器中的并行性量。我们使用了工作深度模型，并评估了通信量和同步。我们特别关注相关张量的稀疏性/密度，以了解如何有效地应用技术，如向量化。我们还正式分析了 GNN 流水线处理，并推广了已建立的 Message-Passing 类 GNN 模型，以覆盖任意流水线深度，促进未来的优化。最后，我们研究了不同形式的异步性，为未来异步并行 GNN 流水线铺平了道路。我们的分析结果综合了一系列见解，有助于最大化 GNN 性能，并全面列出了进一步研究高效 GNN 计算的挑战和机会。我们的工作将有助于推进未来 GNN 的设计。
关键词
引言
图神经网络（GNNs）正在以风暴般的速度接管机器学习（ML）的世界 [1]。它们已经被用于大量复杂问题，如节点分类、图分类或边缘预测。应用示例领域包括社会科学、生物信息学、化学、医学、网络安全、语言学、交通等 [1]。一些最近的成功案例包括成本效益高且快速放置高性能芯片 [2]、引导数学发现 [3] 或显著提高蛋白质折叠预测的准确性 [4]。
GNNs 概括了传统的深度学习（DL）和图处理。与前者不同，它们不在规则网格和高度结构化的数据上操作（例如，图像处理）；相反，数据是高度无结构的、不规则的，由此产生的计算是数据驱动的，缺乏直接的空间或时间局部性 [5]。此外，与后者不同，顶点和/或边与复杂数据和处理相关联。例如，在许多 GNN 模型中，每个顶点 i 都有一个分配的 k 维特征向量，并且每个这样的向量都与 i 的邻居的向量结合；这个过程迭代重复。因此，尽管这种 GNN 计算的整体风格类似于标签传播算法，如 PageRank [6]，但由于顶点特征的高维数，它带来了额外的复杂性。
然而，这只是最简单的 GNN 模型，如基本的图卷积网络（GCN）[7] 的工作方式。在许多（如果不是大多数）GNN 模型中，每个边也可能附有高维数据，并且在每次迭代中都会发生对边数据的复杂更新。例如，在图注意力网络（GAT）模型 [8] 中，要计算单个边（i，j）的标量权重，首先必须连接顶点 i 和 j 的特征向量的线性变换，然后构造这样一个结果向量与训练参数向量的点积。其他模型带来了更多的复杂性。例如，在门控图卷积网络（G-GCN）[9] 模型中，边权重可能是一个多维向量。
与此同时，并行和分布式处理已经成为计算效率的代名词。几乎每个现代计算架构都是并行的：核心形成一个插座，而插座形成一个非统一内存访问（NUMA）计算节点。节点可以进一步集成为刀片、机箱和机架。众多的内存库使数据分布成为可能。所有这些架构层次的部分都并行运行。即使是单个顺序核心也以向量化、流水线化或指令级并行（ILP）的形式提供并行性。此外，这样的架构通常是异构的：处理单元可以是 CPU 或 GPU、现场可编程门阵列（FPGA）或其他。如何利用所有这些丰富的特性来实现 GNN 工作负载的更多性能？
为了帮助回答这个问题，我们系统地分析了 GNNs 的不同方面，重点关注这些方面的并行性和分布。我们使用基本的理论并行计算机械，例如工作深度模型 [10]，来揭示与架构无关的见解。我们特别关注 GNNs 中计算的线性代数公式，并调查相关张量的稀疏性和密度。这为 GNN 计算中的性能关键特征提供了进一步的见解，并促进了向量化等并行化机制的应用。总的来说，我们的调查将有助于开发更高效的 GNN 计算。
为了系统分析，我们提出了一个深入的 GNNs 中并行性的分类法。该分类法识别了 GNNs 中的基本形式的并行性。虽然其中一些在传统深度学习中有直接等效项，我们还说明了其他特定于 GNNs 的形式。
为了确保我们的分析的广泛适用性，我们涵盖了 GNN 领域的许多不同方面。其中包括不同类别的 GNN 模型（例如，空间、谱、卷积、注意力、消息传递）、大量 GNN 模型（例如，GCN [7]、SGC [11]、GAT [8]、G-GCN [9]）、GNN 计算的部分（例如，推理、训练）、GNN 的构建块（例如，层、操作员/内核）、编程范式（例如，SAGA-NN [12]、GReTA [13]）、GNN 背后的执行方案（例如，reduce、activate、不同的张量操作）、GNN 框架（例如，NeuGraph [12]）、GNN 加速器（例如，HyGCN [14]）、GNN 驱动的 ML 任务（例如，节点分类、边缘预测）、小批量与全批量训练、不同形式的采样以及异步 GNN 流水线。
我们以对并行和分布式 GNNs 的总体见解以及一组研究挑战和机会结束我们的工作。因此，我们的工作可以作为在现代架构上执行 GNNs 的并行和分布式解决方案的开发指南，并为选择 GNN 领域的下一个研究方向提供帮助。
-
我们识别并分析了 GNNs 中的基本并行形式，并说明了它们在某种程度上与传统 DL 中的形式相匹配。这将促进设计未来的 GNN 系统更加有效，通过为系统设计者提供清晰的视野，让他们了解他们可以使用的并行化方法空间，以及这些方法如何组合。此外，它还将促进重用现有的大规模 DL 框架。
-
我们为总共 23 个模型的广泛谱系的 GNN 模型进行了分析，涵盖了所有主要类别的模型，即卷积、注意力、消息传递和线性/多项式/有理模型，研究了它们的可并行化性，并确定了它们的瓶颈和相关权衡。这将有助于将这些模型扩展到比今天更大的规模。由于最近的大规模 NLP 成功表明，这是一个使它们更强大的重要因素。
-
我们为异步 GNN 设计了一个广泛的理论框架，这将作为推动 GNNs 的可扩展性和性能的新型 GNN 模型和实现的蓝图。
-
我们回顾了挑战和机会，这将促进未来对大规模 GNNs 的研究。
III. 数据并行性
在传统的深度学习中，数据并行性的基本形式是在小批量内并行处理输入数据样本。每个工作器处理自己的样本部分，计算模型权重的部分更新，并使用诸如参数服务器或allreduce等策略与其他工作器同步这些更新。由于样本（例如图片3）是独立的，它们的处理很容易并行化，并且仅在更新模型参数时才需要同步。在图神经网络（GNNs）中，由于数据样本之间通常存在依赖关系，小批量并行性要复杂得多。此外，输入数据集通常非常庞大。因此，无论是否以及如何使用小批量处理，通常都不得不求助于图划分并行性，因为没有单个服务器能够将数据集装入内存。我们现在详细讨论这两种形式的GNN数据并行性。
A. 图划分并行性
一些图可能拥有超过250亿个顶点和超过10万亿条边，每个顶点和/或边可能有大量相关的特征向量。因此，不可避免地必须将这些图分布在不同的工作器上，因为它们不适合单个服务器的内存。我们将这种形式的GNN并行性称为图划分并行性，因为它根植于已建立的图划分问题和相关的最小割问题。图划分并行性的主要目标是以最小化工作器之间的通信和工作负载不平衡的方式将图分布在工作器上。我们在图9中说明了图划分的不同变体。在将图分布在不同的工作器和服务器上时，可以特别地分布顶点（边[结构]划分，即划分边），边（顶点[结构]划分，即划分顶点），或者边和/或顶点的输入特征（边/顶点[特征]划分，即划分边和/或顶点的输入特征向量）。重要的是，这些方法可以结合使用，例如，没有什么阻止同时使用边和特征向量划分。边划分可能是最广泛形式的图划分，但它在划分具有偏斜度分布的图时会带来大量的通信和工作不平衡。顶点划分可以在一定程度上缓解这个问题，但如果一个高学位顶点被分布到许多工作器中，它也会产生维护一致的分布式顶点状态的开销。有关边划分和顶点划分之间差异的文献非常丰富。
划分涉及通信，当图的某一部分依赖于存储在不同服务器上的另一部分时，可能会发生这种情况。这可能发生在图相关操作（Scatter, Aggregate）期间，如果划分了边或顶点，以及在神经网络相关操作（UpdateEdge, UpdateVertex）期间，如果划分了特征向量。划分通常不允许单个顶点属于多个划分（与小批量并行性不同，其中单个样本可能属于多个小批量）。但是，有一些策略可以减少通信，这些策略涉及在远程划分上缓存顶点。这样的方案将涉及在几个划分上维护给定顶点的多个副本。请注意，虽然图划分通常是在训练开始之前进行一次，但在原则上，也可以在训练期间重新应用划分，以缓解潜在的负载不平衡（例如，由于插入新顶点或边）。这样的方案是未来工作的一个有趣方向。
1） 全批量训练：图划分并行性通常用于缓解全批量训练的大型内存需求。在全批量训练中，必须存储每个GNN层中每个顶点的每个特征的所有激活。因此，执行和并行化此方案的常见方法是使用可以容纳其组合内存中的大量输入数据集的分布式内存大规模集群，以及图划分并行性。尽管如此，使用这样的集群可能是昂贵的，并且它仍然不能缓解缓慢的收敛。因此，通常使用小批量处理。
B. 小批量并行性
在GNNs中，如果数据样本是独立的图，那么小批量并行性类似于传统的深度学习。首先，一个小批量是这些图样本的集合，它们之间没有依赖关系。其次，样本（例如分子）可能有不同的大小。这可能会导致负载不平衡，类似于视频[16]。例如，单个数据集（例如ChemInformatics）[46]可能包含具有5个顶点和18条边的图，以及具有121个顶点和298条边的图。这种设置在图分类或图回归中很常见。我们在图8（右）中说明了这一点，并称之为独立小批量并行性。请注意，虽然图样本可能有不同的大小（例如，分子可能具有不同数量的原子和键），但它们的特征计数是相同的。
然而，在大多数GNN计算中，由于样本之间的依赖关系，小批量并行性更具挑战性（依赖小批量并行性）。具体来说，考虑节点分类。类似于图划分并行性，可能会经历负载不平衡问题，例如，因为顶点的度数可能不同。有几项工作缓解了这个问题[47]，[48]。
虽然图预测设置在数据科学工作中已经被探索[1]，[38]，[49]，但在系统设计研究中基本上没有被解决[50]。因此，据我们所知，没有详细的现有负载平衡研究或方案用于独立小批量并行性（与节点或边预测[50]不同）。以图作为样本的依赖小批量并行性更是很少被研究；例如，它甚至没有在大规模OGB挑战[38]中代表数据集。因此，我们在第VII节中将这些列为研究机会。
GNN小批量处理中的另一个关键挑战是在选择形成给定小批量的目标顶点时的信息丢失。在传统的深度学习中，随机选择样本。在GNNs中，直接应用这种策略将导致非常低的准确性。这是因为，当选择一组随机节点时，这个子集甚至可能根本不连接，但肯定会非常稀疏，并且由于缺少边，大量有关图的信息在Aggregate或Scatter操作期间丢失。这种信息丢失挑战在早期的GNN工作中通过全批量训练来规避[1]，[7]（参见第III-A1节）。不幸的是，全批量训练具有缓慢的收敛性（因为模型每个时期只更新一次，这可能需要处理数十亿个顶点），以及上述的大型内存需求。因此，两种最近针对特定小批量处理提出的方案专注于采样邻居，并适当选择目标顶点。
1） 邻域采样：在GraphSAGE[52]启动的一系列工作中，将每个选定的目标顶点v的采样邻居添加到小批量中。v的采样邻居通常不仅来自1跳，而且来自v的H跳邻域，其中H可能与图的直径一样大。采样邻居的确切选择取决于每个方案的细节。在GraphSAGE中，它们是为每个GNN层在实际训练之前对每个目标顶点进行采样的。
与邻域采样相关的一个挑战是它们的预选择开销。例如，在GraphSAGE中，除了前向和后向传播通道之外，还必须进行与GNN层数一样多的采样步骤，以便对每个层和每个目标顶点进行采样。虽然这可以通过也用于前向和后向传播的并行化方案来缓解，但它本质上增加了GNN计算的深度，乘以一个常数因子。
另一个相关的挑战是所谓的邻域爆炸，它与维护可能的许多这样的顶点的内存开销有关。在最坏的情况下，对于小批量中的每个顶点，假设保留其所有邻居直到H跳，必须维护O(kdH)的状态。即使这些顶点中的一些是小批量中的目标顶点，因此已经被维护，但当增加H时，它们的比率会变低。GraphSAGE通过从每个邻域中采样恒定分数的顶点而不是保留所有邻居来缓解这一点，但内存开销仍可能很大[53]。我们在图10中展示了一个邻域爆炸的例子。
2） 适当选择目标顶点：更近期的GNN小批量工作专注于适当选择包含在小批量中的目标节点，以便在不损失高准确性的情况下不需要支持顶点。例如，ClusterGCN首先对图进行聚类，然后将聚类分配给小批量[28]，[54]。这样，通过减少信息丢失，因为一个小批量通常包含一个紧密联系的顶点社区。但是，必须额外计算图聚类作为预处理形式。这可以与多种已建立的并行聚类例程之一并行化[40]。
C. 图划分与小批量/全批量训练
图划分主要用于将图完全保存在内存中（避免昂贵的磁盘访问），而小批量用于加快收敛速度。这两个之间的主要区别是在跨工作器分割图数据集时的主要目标。对于图划分并行性，目标是最大化计算效率，即通过最小化工作器之间的通信量来最小化运行时间。对于后者，重点是增加采样效率，即以最大化收敛速度的方式创建小批量。某些方案可能导致选择类似的顶点。例如，Cluster-GCN选择密集的聚类作为小批量，这样的聚类也可能是有效的图划分[28]。然而，情况并非总是如此，因为其他小批量处理方案并不一定专注于密集的聚类[55]。另一个区别是，虽然单个图划分由单个工作器处理（即多个工作器处理多个划分），但一个小批量由多个工作器处理。我们还注意到，可以考虑并行处理不同的小批量。这将涉及异步GNN训练，模型更新将异步进行。这样的方案可能会减慢收敛速度，但会提供更多的并行性潜力。
通常，图划分并行性与全批量训练一起使用[30]，[56]，[57]，[58]。然而，原则上，图划分并行性和小批量并行性是正交的，因此可以一起使用。例如，一个大型的小批量在内存不多的工作器上运行时，可以利用图划分并行性来避免I/O。这种方法也在传统的深度学习中被提出[59]，[60]。
D. 工作-深度分析
我们分析了使用全批量或小批量训练的不同GNN训练方案的工作/深度，见表II。
首先，所有方法都有一个公共的工作项O(Lmk + Lnk^2)，等于层数L乘以每层中进行的操作数，其中mk是稀疏图操作（Aggregate）的操作数，nk^2是密集神经网络操作（UpdateVertex）的操作数。这是全批量方法的总工作量。小批量方案有额外的工作项。基于支持顶点的方案（GraphSAGE，VR-GCN，FastGCN）有反映它们如何选择这些顶点的项。GraphSAGE和VR-GCN特别有一个高的项O(cLnk^2)由于邻域爆炸（c是每个邻域采样的顶点数）。FastGCN通过每层采样c个顶点来缓解邻域爆炸，结果是O(cLnk^2)的工作量。然后，专注于适当选择目标顶点的方法（GraphSAINT，Cluster-GCN）没有与邻域爆炸相关的工作项。相反，它们有预处理项W_pre表示。Cluster-GCN的W_pre取决于所选的聚类方法，这严重依赖于输入图的大小（n，m）。GraphSAINT则进行随机小批量选择，其工作量不一定随着n或m的增长而增长。
在深度方面，所有的全批量方案都依赖于层数L。然后，在每层中，两个瓶颈操作是密集的神经网络操作（UpdateVertex，例如矩阵-向量乘法）和稀疏图操作（Aggregate）。它们分别需要O(log k)和O(log d)的深度。小批量方案类似，主要区别是对于基于支持顶点的方案，O(log c)代替了O(log d)的项。这是因为这些方案中的Aggregate是在c个采样邻居上应用的。此外，在Cluster-GCN和GraphSAINT中，邻域可能最多有d个顶点，从而产生了O(log d)的项。然而，它们还具有额外的预处理深度项D_pre，这取决于所使用的采样或聚类方案。
总结来说，全批量和Mini-batch GNN训练方案具有相似的深度。请注意，这是通过在全批量训练方法中使用图划分并行性，以及在Mini-batch训练方案中使用Mini-batch并行性来实现的。相反，Mini-batch的整体工作量可能更大，这是由于支持顶点的开销，或者在选择目标顶点时进行额外的预处理。然而，Mini-batch具有更快的收敛速度，通常内存压力较小。
E. 平行性与收敛之间的权衡
在小批量中并行性的数量和收敛速度之间的效率权衡，是并行传统ANNs[34]的一个重要部分。简而言之，小的小批量会加速收敛，但可能限制并行性，而大的小批量可能会减慢收敛，但会有更多的并行性。在GNNs中，找到“正确”的小批量大小要复杂得多，因为样本之间存在相互依赖性。例如，一个由不相连的顶点组成的大的小批量，将导致非常低的准确性。另一方面，如果一个小批量很小，但它由形成簇的紧密连接的顶点组成，那么基于处理该小批量的更新的准确性可以很高[28]。
IV. 模型并行
在传统的神经网络中，模型通常很大。在图神经网络（GNNs）中，模型（W）通常较小，通常可以适应单台机器的内存。然而，为了提高吞吐量，大量使用各种形式的模型并行性；我们在第II-F节和图7中提供了概述。
在以下模型分析中，我们经常描绘所使用的线性代数对象和操作。为了清晰起见，我们指示它们的形状、密度和维度，使用小图形，见表III所列。有趣的是，GNN模型在LC（局部）公式中大量使用密集矩阵和向量，其维度由O(k)主导，并且相关的操作也是如此。另一方面，GL（全局）公式使用不同形状（方形、矩形、向量）的稀疏和密集矩阵，所使用的矩阵乘法可以是密集-密集（GEMM，GEMV）、密集-稀疏（SpMM）和稀疏-稀疏（SpMSpM）。其他操作是逐元素矩阵乘积或有理稀疏矩阵幂。这种丰富的操作多样性立即说明了使用不同类别模型的并行和分布式技术的巨大潜力。
A. 本地操作符并行性
在本地操作符并行性中，我们专注于并行化在单个顶点或边上执行的Scatter和Gather操作（即局部图元）。我们进一步通过考虑分别在LC和GL GNN模型公式中进行本地操作符并行性的调查来构建我们的研究。
1）
在GNN模型的LC公式中的并行性
：我们在图11中展示了LC GNN公式的通用工作和深度方程。总体而言，工作是任何预处理成本Wpre、后处理成本Wpost以及单个GNN层工作Wl乘以层数L的总和。在(1)中考虑的通用公式中，Wl等于评估每个边的ψ所需的工作量(mWψ)、评估每个顶点的⊕(nW⊕)以及评估每个顶点的φ(nWφ)。深度类似，主要区别在于单个GNN层的深度是计算ψ、⊕和φ的深度的简单总和（每个函数都并行评估每个顶点和边，因此不需要与n或m相乘）。
我们通过关注形成这些模型的三个函数：ψ、⊕和φ，来分析许多特定GNN模型的工作和深度。分析结果在表V和表VI中展示。我们根据最近的调查选择了代表性模型[23]。我们还指出模型是否属于卷积(C-GNN)、注意力(A-GNN)或消息传递(MP-GNN)模型类别[24]。
ψ的分析结果在表V中展示。我们为每个模型提供了ψ的公式，并展示了计算ψ所需的所有代数运算。所有C-GNN模型在预处理期间确定它们的ψ。这种预处理对应于邻接矩阵的行归一化(cij = 1/di)、列归一化(cij = 1/dj)或对称归一化(cij = 1/√didj)[1]。在所有这些情况下，它们的推导需要O(1)深度和O(m)工作量。然后，A-GNNs和MP-GNNs的ψ公式比C-GNNs复杂得多。细节取决于模型，但重要的是——几乎所有的模型都有O(k^2)工作量和O(log k)深度。最具计算强度的模型GAT，尽管其工作量等于O(dk^2)，但也有对数深度O(log k + log d)。这意味着在所有考虑的模型中，计算ψ可以有效地并行化。至于评估ψ时涉及的稀疏模式和操作类型，大多数模型使用GEMV。所有考虑的A-GNN模型还使用密集向量的转置。GAT还使用向量拼接和多达d个向量的和。最后，一个考虑的MP-GNN模型使用逐元素MV乘积。一般来说，每个考虑的GNN模型都使用密集矩阵和向量运算来为每个相关边获得ψ。
注意，ψ默认对应于“瞬态”的边特征向量，即它们是即时计算的，而不是显式存储的（与顶点特征向量不同）。然而，在某些情况下，您可能还想显式实例化边特征向量。这样的实例化将用于例如边分类或边回归任务。例如，Graph Networks by Battaglia等人[26]提供了一个允许这样做的GNN公式，也是一个LC公式。在这种情况下，关于并行性的洞见与本节提供的不同；主要的不同是需要额外的O(mk)内存开销来存储所有边特征向量。
⊕的分析在表VI中展示（与表V中的相同模型）。我们展示了模型的总工作量和深度。所有模型都需要密集矩阵-向量乘积和多达d个密集向量的和。深度是对数级的。工作量不同，GAT的工作量最高。
我们还展示了LC公式中的操作符并行性，重点关注GNN编程内核，在图12的顶部。我们提供了相应的通用工作-深度分析在表IV中。四个编程内核遵循相应LC函数(ψ, ⊕, φ)的工作和深度。
通信与同步：
在LC公式中的通信发生在Scatter内核（ψ的一部分），如果顶点特征向量被通信以形成边特征向量；传输的数据量达到O(mk)。类似地，在Aggregate内核(⊕)期间，也可能移动O(mk)数据。UpdateEdge(ψ)和UpdateVertex(φ)没有明确移动数据。然而，它们可能与通信密集型操作相关联；特别是A-GNNs和MP-GNNs通常与ψ和φ相关的复杂处理，参见表V和表VI。虽然这些处理涉及的矩阵尺寸高达O(k) × O(k)，它们容易适应单台机器的内存，但这可能会在未来改变，如果在未来的GNN模型中增加了特征维度k。
在GNN的默认同步变体中，必须在所有相同类型的内核计算完成后进行全局同步，以确保所有数据都已被相应的工作节点接收（Scatter和Aggregate之后）或所有特征向量都已更新（UpdateEdge和UpdateVertex之后）。在第IV-C3节中，我们讨论了如何通过允许异步执行来放宽这一要求。
2）
在GNN模型的GL公式中的并行性
：在表VII中分析了GL公式中的并行性。具有LC和GL公式的模型（例如，GCN）具有相同的工作量和深度。因此，基本上，它们提供了相同数量的并行性。然而，基于矩阵操作的GL公式提供了与LC公式不同的并行化方法的潜力。例如，有一个更多的向量化机会，因为一个人不是被迫分别向量化每个顶点或边的特征向量的处理（如在LC公式中），而是可以向量化整个矩阵H的派生。
还有在GL公式中设计但没有已知LC公式的模型，参见表V和表VI。这些模型使用邻接矩阵的多项式和有理数幂，参见第II-C3节和图4。这些模型只有一次迭代。它们也提供并行性，如对数深度所示（或对于需要反转邻接矩阵的有理模型是平方对数）。虽然它们只有一次迭代，使得L项消失，但它们需要派生给定幂x的邻接矩阵A（或其规范化版本）。重要的是，由于计算这些幂不与非线性（如许多只使用线性幂的模型）交织在一起，工作量和深度的增加只是对数级的，表明更多的并行性。然而，由于缺乏非线性，它们的代表性可能较低。
我们在图12（底部）中概述了两个GL模型（GCN和vanilla graph attention）的例子。在这张图中，我们还指出了LC GNN内核如何在GL公式的矩阵操作流程中反映出来。
3）
讨论：特征与结构与模型
：在局部卷积（LC）和全局卷积（GL）公式中，特征并行性都很简单（参见图12）。在前者中，可以在不同特征上并行执行二叉树约简中的特征并行性），或者并行更新边或顶点特征。在后者中，可以并行地将邻接矩阵的一行与潜在矩阵 ( H ) 的任何一列相乘（对应于不同的特征）。由于特征向量是密集的，它们可以连续存储在内存中，并容易地使用向量化。
在局部卷积（LC）和全局卷积（GL）公式中，都存在图邻域并行性。在前者中，通过并行执行 （针对单个特定特征）来实现。在后者中，通过并行化给定邻接矩阵行与给定特征矩阵列的乘法来实现。
在图神经网络（GNNs）中，也可以实现传统模型权重并行性，即将权重矩阵 ( W ) 分配给不同的工作者。然而，由于迄今为止文献中使用的权重矩阵大小较小[38]，[49]，它尚未成为研究的焦点。如果这种并行性在特征上变得有用，可以使用传统的深度学习技术来并行化模型权重处理[34]。
图[邻域]与图[划分]并行性
：图[划分]并行性用于将整个图分配给工作者，以便将图完全包含在内存中。图[邻域]并行性仅在单个顶点的邻居之间在聚合过程中使用，并且它可以与图[划分]并行性正交应用。例如，一个单一的图划分可能包含一个高度数的顶点，并且可以在这个划分内并行化应用于这个顶点的聚合。
图划分并行性与图邻域并行性之间的关系类似于宏观流水线并行性和微观流水线并行性之间的关系。具体来说，虽然在宏观流水线并行性中，将整个GNN层分配给工作者，但可以使用微观流水线并行性进一步并行化这单个层的部分，与宏观流水线结构正交。
B. 全局操作符并行性
在全局操作符并行性中，Scatter和Gather操作可以在顶点或边的集合上并行执行。这种方法可以利用图结构之外的额外结构来获得更高的性能。例如，可以利用类似于Karger算法中的图收缩和超顶点（用于最小割问题）或Shiloach和Vishkin算法中的挂钩树（用于连通分量问题）。这样的超顶点或树可能潜在地被用来加速Gather操作。
全局操作符并行性与图划分并行性之间的关系是：图划分并行性是一种直接的方法，它只涉及将顶点和边分布到不同的工作节点上，以便它们都能适应内存。而全局操作符并行性则更复杂，并且可以利用在处理的顶点/边集合之上的额外结构，如超顶点。
C. 流水线并行性
流水线并行性有两个一般性的好处。首先，它增加了计算的吞吐量，降低了整体处理运行时间。这是因为更多的操作可以在时间单位内完成。其次，它减少了计算中的内存压力。具体来说，可以将输入数据集分成块，并通过流水线阶段分别处理这些块，一次只需保持输入的一部分在内存中。在图神经网络（GNNs）中，流水线并行性通常与图划分并行性结合使用，其中块就是这些分区。我们区分两种主要形式的GNN流水线：微流水线（micro-pipelines）和宏流水线（macro-pipelines），见图7和第II-F节。
1）
微流水线并行性
：在微流水线并行性中，流水线阶段对应于GNN层内的运算。这里，为了简单起见，我们考虑一个图操作后跟一个神经操作，然后是一个非线性激活，参见图2。可以等效地考虑内核（Scatter, UpdateEdge, Aggregate, UpdateVertex）或相关函数（ψ, ⊕, φ）。这样的流水线化可以通过多达3倍的长度减少执行的操作序列，有效地形成了一个3阶段操作微流水线。已经有几项实际工作研究了使用硬件加速器的微流水线GNN操作；我们在第V节讨论了它们。
我们在一个示例微流水线（同步）的顶部面板中展示了一个示例（图13）。请注意，每个神经操作必须等待所有图操作完成后才能开始，因为在最坏的情况下，每个分区中可能有与所有其他分区相连的顶点。这是与传统深度学习（以及图3中的独立图的GNN设置）的重要区别，后者块之间没有块间依赖关系，因此可以在完成P1上的图操作后立即开始P1上的神经处理。
微流水线在深度上的具体好处取决于具体的GNN模型。假设一个简单的GCN，上述列出的四个操作分别需要O(log d), O(1), 和 O(1) 的深度。因此，由于Aggregate在时间上占主导地位，可以通过复制剩余阶段来平衡流水线。
2）
宏流水线并行性
：在宏流水线并行性中，流水线阶段是GNN层。这种流水线在传统深度学习中受到强烈研究，有如GPipe [95], PipeDream [96], 或Chimera [97]等设计。然而，流水线化GNN层更加困难，因为数据样本之间存在依赖关系，它只在早期开发阶段 [30]。在图13中，执行是完全流水线化的，即所有层都由不同的工作进程处理。
3）
异步流水线
：在异步流水线中，流水线阶段在前一个阶段完成之前就开始进行[96]。这个概念可以应用于GNNs中的微流水线和宏流水线。首先，在异步微流水线中，处理其图分区的工作进程在图操作完成之前就开始神经操作（图13，右上角面板）。其次，在异步宏流水线中，消除了层间同步，工作进程可以在前一个GNN层完成非线性激活后立即开始其分区上的图操作（图13，左下角面板）。最后，这两种形式可以结合使用，见图13（右下角）。
请注意，异步流水线可以与图分区（即异步处理不同的图分区）和迷你批次（即异步处理不同的迷你批次）一起使用。
4）
任意深度流水线的理论公式
：为了更好地理解GNN流水线，我们首先提供一个变种的(1)，即(2)，它定义了具有图划分并行性的异步消息传递GNN执行（图14）。在这个方程中，我们明确说明了，在计算给定顶点i的聚合（⊕）时，一些聚合的邻居可能来自“远程”图分区，其中i不属于；这样的i的邻居形成一个集合NR(i)。其他邻居来自同一个“本地”图分区，形成集合NL(i)。注意NR(i) ∪ NL(i) = N(i)。此外，在(2)中，我们还明确指出了当前训练迭代t，除了当前层l之外，使用双索引(t, l)。总的来说，(2)描述了标准的同步执行，因为要获得第l层和第t次训练迭代的特征向量，所有使用的特征向量都来自前一层l-1，在同一训练迭代t中。
不同形式的陈旧性和异步性可以通过修改层索引引入，使它们“指向更早的过去”，即使用过去层的陈旧特征向量。为此，我们将(2)推广到(3)，通过结合参数来完全控制这种陈旧性的范围。这些参数是Lφ（控制i自己的前一个特征向量的陈旧性），LLψ（控制来自i的本地邻居的特征向量陈旧性），和LRψ（控制来自i的其他分区的远程邻居的特征向量陈旧性）。此外，为了也允许在训练迭代方面的陈旧性和异步性，我们引入了类似的参数Tφ, TLψ, TRψ。然后我们定义(3)的行为，使这六个参数限制了允许的最大陈旧性，即(3)可以使用最多由给定的相应索引参数控制的过去层/迭代的特征向量。
现在，首先观察到当设置Lφ = LLψ = LRψ = 1和Tφ = TLψ = TRψ = 0时，我们得到了标准的同步方程（参见图13，左上角面板）。将这些参数中的任何一个设置为大于这个值都会引入陈旧性。例如，PipeGCN [56] 提出了使用TRψ = 1（所有其他参数为零）来流水线化GCN模型 [7]中的通信和计算。这样，模型被允许使用来自前一个训练迭代的远程分区的陈旧特征向量，从而实现通信-计算重叠（以稍微更长的收敛时间为代价）。另一个选择是只设置LRψ = 2（或更高的值）。这将使得异步宏流水线成为可能，因为不必等待最近的GNN层完成处理其他图分区就可以开始处理自己的特征向量。我们将基于(3)探索其他异步设计的工作留作未来的研究。
最后，我们也得到了异步计算陈旧梯度的等效公式，见图15。这为优化反向传播传递建立了类似的方法。
5）
超越微流水线和宏流水线
：我们注意到，上述两种流水线形式并不一定穷尽了GNNs中流水线执行的所有机会。例如，有大量关于并行流水线化归约树的工作[98]，这些可以进一步加速聚合操作（⊕）。
D. 人工神经网络（ANN）并行性
在某些图神经网络（GNN）模型中，例如GIN，密集的UpdateVertex或UpdateEdge核是多层感知机（MLP）。它们可以使用传统的深度学习并行化方法进行并行化，这些方法不是本文的工作重点；它们已在其他地方进行了广泛描述。总的来说，可以使用ANN操作符并行性（在一个层内并行处理单个NN操作符，例如计算单个神经元的值）和ANN流水线并行性（连续MLP层的并行流水线处理），参见图7。我们确定了GNN宏观流水线和传统ANN流水线之间的一个有趣差异。具体来说，在后者中，数据仅在流水线开始时需要。在前者中，数据（即图结构）在每个GNN层都需要。
E. GNN中的其他并行形式
在GNN中可以识别其他并行形式。首先，通过结合模型和数据并行性，可以获得——正如在传统深度学习中一样——混合并行性。模型并行性的更复杂形式也是可能的。一个例子是专家混合（MoE），其中不同的模型可以并行评估。目前，GNN中的MoE使用还处于初期阶段。
V. 框架、加速器、技术
我们最后分析现有的GNN软件框架和硬件加速器。对于这些，我们首先描述了这些系统使用的并行和分布式架构。
A. 并行和分布式计算架构
1）
单机器架构
：多核或众核并行性通常包含在通用CPU中。图形处理单元（GPU）提供了大量的并行性，以大量简单核心的形式存在。然而，它们通常要求计算问题被结构化，以适应“规则”的GPU硬件和并行性。此外，现场可编程门阵列（FPGA）非常适合于容易形成流水线的问题。最后，新提议包括在内存中处理（PIM），它将计算更接近数据。
GNNs具有不规则操作（即涉及许多随机内存访问）的“稀疏”特征，例如邻域上的归约，以及通常由顺序内存访问模式主导的“密集”常规操作，例如特征向量的转换。后者通常适合在GPU上有效处理，而前者更容易在CPU上有效处理。因此，这两种架构在GNNs的背景下都非常重要。我们的分析（表VIII，上半部分）表明，它们都得到了超过50%的可用GNN处理框架的支持。我们观察到，这些设计大多专注于在GPU上执行常规密集的GNN操作，将不规则的稀疏计算留给CPU。虽然这是一种有效的方法，但我们注意到，GPU已成功用于在不规则图处理中实现非常高性能，因此它们对于加速稀疏GNN操作也具有很高的潜力。
对GNN的硬件加速器（表VIII，下半部分）也有兴趣。大多数是ASIC提议（一些使用FPGA进行评估）；其中一些结合了PIM。随着异构计算的今天的重要性，开发针对GNN的特定加速器并将其与传统架构一起使用是一个重要的工作线索，我们预测，这在未来几年只会变得更加重要。
2）
多机器并行性
：虽然共享内存系统足以处理许多数据集，但GNN中的一个最新趋势是增加输入图的大小，这通常需要多节点设置以避免昂贵的I/O。我们观察到（表VIII，上半部分），不同的GNN软件框架支持分布式内存环境。然而，大多数系统专注于训练，为开发高效的分布式内存框架和技术留下了很大的空间，用于GNN推理。
B. 系统和设计决策的一般类别
首先支持GNN的系统通常属于两个类别中的一个。第一类是构建在图处理框架和范式之上的系统，它们增加了神经网络处理能力（例如Neugraph或Gunrock）。相反，第二类系统（例如最初的PyG设计）从深度学习框架开始，并向其扩展图处理能力。这两个类别通常分别关注LC和GL公式及其关联的执行范式。
第三类，也是最新的GNN系统类别，不是从传统的图处理或深度学习开始的。相反，它们从零开始针对GNN计算，专注于GNN特定的工作负载特性和设计决策。例如，Zhang等人分析了GNN的计算图，并提出了专门针对GNN的优化。
C. GNN系统中的并行性
最常支持的并行性形式是图分区并行性。这里，通常重用图处理领域中的许多既定技术。毫不奇怪，用于图分区的大多数方案都是基于将顶点分配给工作器的（“1D分区”）。这很容易开发，但会带来与负载平衡相关的挑战。通过也将每个邻域分配给工作器（“2D分区”），通常可以获得更好的负载平衡属性。虽然一些框架支持这种变体，但在这个方向上有更多的发展空间。我们还观察到，大多数系统支持分片，它使用单个大型输入图攻击节点或边分类/回归场景。例如，CAGNET结合了分片和复制，以通过通信避免加速GNN训练。
