六、AGL [2020]

发布于 2023-07-17 23:38:24 字数 97282 浏览 0 评论 0 收藏 0

为了利用图机器学习技术来解决工业级的图分析任务，我们需要构建一个可扩展的scalable 、容错性的fault-tolerance、同时包含训练和推理的学习系统。但是由于图的数据依赖性，图机器学习任务的计算图和传统机器学习任务完全不同。
- 在传统机器学习任务中，我们假设样本之间的计算图相互独立。这也是现有的、经典的参数服务器parameter server 框架假设的数据并行性。
- 但是在图机器学习任务中，每个节点的计算图依赖于该节点 k-hop 邻居。
  
  这种数据依赖性使得我们不再能够将训练或推理样本存储在磁盘中、然后通过 piepeline 来访问。相反，我们必须将图数据存储在内存中以便快速访问数据。这使得我们无法基于现有的参数服务器框架简单地构建用于图学习任务的学习和推理系统。
多家公司致力于为各种图机器学习技术设计新颖的系统架构：
- Facebook 展示了一种大规模graph embedding 系统 PyTorch-BigGraph: PBG，该系统旨在从 multi-relation 数据中生成无监督的节点 embedding。但是 PBG 不适合处理丰富属性的图（节点属性或边属性）。
- 已有 Deep Graph Library: DGL、PyTorch Geometric: PyG、AliGraph 用于大规模、带属性的图上训练 GNN 。
  - DGL、PyG 被设计为单机系统，它通过在巨型机（如具有 2TB 内存的 AWS x 1.32 x large）来处理工业级的图数据。
  - AliGraph 是一个分布式系统，它实现了分布式的、内存的图存储引擎graph store engine，该引擎需要在训练 GNN 模型之前独立部署。
但是，实际的工业级图数据可能非常庞大。Facebook 中的社交网络包括超过 20 亿节点和超过1万亿条边，蚂蚁金服Ant Financial 的异质金融网络、阿里巴巴Alibaba 电商网络包含数十亿节点和数千亿条以及丰富的属性信息。下表总结了几个最新的 SOTA 图机器学习系统报告的图数据的规模。考虑到节点、边关联的特征，这种规模的图数据可能会产生高达 100TB 的数据。

这些数据不可能存储在像 DGL 这样的单机中。此外，保存图数据的图存储引擎和 worker 之间的通信将非常庞大。例如，假设包含节点的子图包含 1000 个节点、10000 条边，我们有一个 batch 的子图，这可能会导致 1MB 的 bulk 在图存储引擎和 worker 之间通信，这是我们无法容忍的。另外，这需要结构良好的、足够大带宽的网络。

总之：
- 首先，现有的工业级的学习系统要求图数据要么在单台机器的内存中（这使得工业级数据无法存储）、要么要求图数据在自定义的图存储引擎中（这导致图存储引擎和 worker 之间的庞大通信开销）。这使得学习系统无法扩展到更大规模的图数据。
- 其次，它们需要额外的开发来支持 graph store，无法很好地利用已有的基础设施（例如 MapReduce 或者参数服务器）来实现容错的目的。
- 最后，大多数学习系统都侧重于图模型的训练，但是忽略了系统的完整性。例如，忽略了部署图模型时优化 inference 任务。
考虑所有这些问题，论文 《AGL: A Scalable System for Industrial-purpose Graph Machine Learning》 提出了 Ant Graph machine Learning system: AGL ，这是用于工业级图学习的集成系统。
AGL 系统设计的关键洞察是基于图神经网络计算图背后的消息传递方案。
- 在GNN 的训练阶段，我们提出构造 k-hop 邻域。该邻域提供节点的完备信息的子图，从而用于计算基于消息传递机制的、每个节点的 k-hop embedding 。
  
  将原始图分解为小的子图片段pieces（即 k-hop邻域）的好处是每个节点的计算图独立于其它节点。这意味着我们仍然可以享受经典的参数服务器框架所具有的容错性、灵活的模型一致性等优势，而无需付出额外的精力来维护图存储引擎。
- 在 GNN 的推断阶段，我们提出将训练好的K 层GNN 模型划分为 K 个分片slice、以及一个和模型预测相关的分片。
  
  通过分片，在第 $k$ $ k $ 层我们首先合并每个节点的入边 in-edge 邻居的 embedding ，然后将自己的 embedding 传播到各自的出边 out-edge 邻居。 $k$ $ k $ 从 1 开始到 K 。
- 我们将训练和推断阶段的消息传递机制抽象化，然后简单地使用 MapReduce 来实现它们。
  
  由于 MapReduce 和参数服务器已经成为工业界常用的基础设置，因此即使在价格低廉且广泛使用的商用机器上，我们的图机器学习系统仍然可以受益于诸如容错性、可扩展性之类的属性。
- 此外，和基于 DGL,AliGraph 等架构的推断相比，我们的推断的实现最大程度地利用了每个的 embedding，从而显著加速了推断工作。
- 此外，我们提出了几种技术从而加速训练过程中的、从 model-level 到 operator-level 的浮点数计算。
结果，和 DGL/PyG 相比，我们在单台机器上成功地加速了 GNN 的训练，并在实际应用场景中使用商用机器的 CPU 集群实现了近线性near-linear 的加速。实验结果表明：在具有 $6.23 \times 10^{9}$ $ 6.23\times 10^9 $ 个节点、 $3.38 \times 10^{11}$ $ 3.38\times 10^{11} $ 条边的大规模图上，AGL 使用 100 个 worker可以在14 个小时内训练完一个 2-layer GAT 模型，其中包括 $1.2 \times 10^{8}$ $ 1.2\times 10^8 $ 个目标节点target nodes ，训练7 个 epoch 模型就达到收敛。

另外，模型只需要 1.2 小时即可完成对整个图的推断。

据我们所知，这是 graph embedding 的最大规模的应用，并证明了我们的系统在实际工业场景的高可扩展性和效率。

6.1 消息传递机制

这里我们重点介绍 GNN 中的消息传递机制。然后我们介绍了 K-hop 邻域的概念，从而帮助实现图学习任务中的数据独立性。消息传递机制、K-hop 邻域在我们的系统设计中都起着重要的作用。
定义有向图 $G = {V, E, A, X, E}$ $ \mathcal G = \{\mathcal V, \mathcal E, \mathbf A, \mathbf X, \mathbf E\} $ ，其中：
- $V$ $ \mathcal V $ 为节点集合， $E \subset V \times V$ $ \mathcal E\sub \mathcal V\times \mathcal V $ 为边的集合。
- $A \in R^{| V | \times | V |}$ $ \mathbf A\in \mathbb R^{|\mathcal V|\times |\mathcal V|} $ 为邻接矩阵。
  - $A_{i, j} > 0$ $ A_{i,j}\gt 0 $ 表示节点 $v_{j} \to v_{i}$ $ v_j\rightarrow v_i $ 之间存在有向边，且边的权重为 $A_{i, j}$ $ A_{i,j} $ 。
  - $A_{i, j} = 0$ $ A_{i,j}=0 $ 表示节点 $v_{j} \to v_{i}$ $ v_j\rightarrow v_i $ 之间不存在有向边。
- $X \in R^{| V | \times d_{n}}$ $ \mathbf X\in \mathbb R^{|\mathcal V|\times d_n} $ 为所有节点的特征构成的特征矩阵，第 $i$ $ i $ 行 ${\vec{x}}_{i} \in R^{d_{n}}$ $ \mathbf{\vec x}_i\in \mathbb R^{d_n} $ 为节点 $v_{i}$ $ v_i $ 的特征向量， $d_{n}$ $ d_n $ 为节点特征向量的维度。
- $E \in R^{| V | \times | V | \times d_{e}}$ $ \mathbf E\in \mathbb R^{|\mathcal V|\times |\mathcal V|\times d_e} $ 为所有边的特征构成的特征张量，第 $(i, j)$ $ (i,j) $ 维度 ${\vec{e}}_{i, j} \in R^{d_{e}}$ $ \mathbf{\vec e}_{i,j}\in \mathbb R^{d_e} $ 为有向边 $v_{j} \to v_{i}$ $ v_j\rightarrow v_i $ 的特征向量， $d_{e}$ $ d_e $ 为边特征向量的维度。
- 这里我们认为无向图是特殊的有向图。对于无向图的每条边 $(v_{i}, v_{j})$ $ (v_i,v_j) $ ，我们分解为两条有向边 $(v_{j} \to v_{i}), (v_{i} \to v_{j})$ $ (v_j\rightarrow v_i),(v_i\rightarrow v_j) $ 。
- 定义 $N_{v}^{+}$ $ \mathcal N_v^+ $ 为节点 $v$ $ v $ 的入边 in-edge 邻居集合， $N_{v}^{-}$ $ \mathcal N_v^- $ 为节点 $v$ $ v $ 的出边 out-edge 邻居集合：
  $N_{v}^{+} = {u : A_{v, u} > 0}, N_{v}^{-} = {u : A_{u, v} > 0}$
  节点 $v$ $ v $ 的所有邻居定义为： $N_{v} = N_{v}^{+} \cup N_{v}^{-}$ $ \mathcal N_v =\mathcal N_v^+ \cup \mathcal N_v^- $ 。
- 节点 $v$ $ v $ 的所有入边的集合记作 $E_{v}^{+}$ $ \mathcal E_v^+ $ ，节点 $v$ $ v $ 的所有出边的集合记作 $E_{v}^{-}$ $ \mathcal E_v^- $ ，节点 $v$ $ v $ 的所有边的集合记作 $E_{v}$ $ \mathcal E_v $ ：
  $\begin{matrix} E_{v}^{+} = {(u \to v) : A_{v, u} > 0}, E_{v}^{-} = {(v \to u) : A_{u, v} > 0} \\ E_{v} = E_{v}^{+} \cup E_{v}^{-} \end{matrix}$
AGL 主要关注基于消息传递机制的 GNN 。在 GNN 的每一层都通过聚合目标节点的in-edge 邻居的信息从而生成intermediate embedding 。在堆叠几层 GNN layer 之后，我们得到了 final embedding，它集成integrate 了目标节点的整个感受野。

具体而言，第 $k$ $ k $ 层 GNN layer 的计算范式paradigm 为：
${\vec{h}}_{v}^{(k + 1)} = ϕ^{(k)} ({{\vec{h}}_{i}^{(k)}}_{i \in {v} \cup N_{v}^{+}}, {{\vec{e}}_{v, u}}_{A_{v, u} > 0}; W_{ϕ}^{(k)})$
其中：
- ${\vec{h}}_{v}^{(k)}$ $ \mathbf{\vec h}_v^{(k)} $ 为节点 $v$ $ v $ 在第 $k$ $ k $ 层的 intermediate embedding ，并且 ${\vec{h}}_{v}^{(0)} = {\vec{x}}_{v}$ $ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v $ 。
- 函数 $ϕ^{(k)}$ $ \phi^{(k)} $ 的参数为 $W_{ϕ}^{(k)}$ $ \mathbf W_\phi^{(k)} $ ，它的输入包括：节点 $v$ $ v $ 及其入边邻居的 embedding、节点 $v$ $ v $ 的入边关联的边特征。
可以在消息传递机制中表达GNN 的上述计算。即：
- 收集 keys（如 node id）以及对应的 values（如 embedding）。
- 对于每个节点：
  - 首先merge入边邻居的所有 values，从而使得目标节点具有新的 value。
  - 然后通过出边来将新的value 传播propagate 到其它节点。
经过 $K$ $ K $ 次这样的融合、传播过程，我们完成了 GNN 的计算。后续讨论中我们将这种机制推广到 GNN 的训练和推断过程中。
定义节点 $v$ $ v $ 的 k-hop 邻域为 $G_{v}^{k} = (V_{v}^{k}, E_{v}^{k}, X_{v}^{k}, E_{v}^{k})$ $ \mathcal G_v^k=\left(\mathcal V_v^k,\mathcal E_v^k,\mathbf X_v^k,\mathbf E_v^k\right) $ ，其中：
- $V_{v}^{k} = {v} \cup {u : d (v, u) \leq k}$ $ \mathcal V_v^k=\{v\}\cup\{u:d(v,u)\le k\} $ 为所有距离节点 $v$ $ v $ 小于等于 $k$ $ k $ 的节点组成的集合。
  
  $d (v, u)$ $ d(v,u) $ 表示从节点 $u$ $ u $ 到节点 $v$ $ v $ 的最短路径。
- $E_{v}^{k} = {(u, u^{'}) : (u, u^{'}) \in E and u \in V_{v}^{k} and u^{'} \in V_{v}^{k}}$ $ \mathcal E_v^k=\{(u,u^\prime):(u,u^\prime)\in\mathcal E \text{ and }u\in \mathcal V_v^k\text{ and }u^\prime \in \mathcal V_v^k\} $ 为起点、终点都位于 $V_{v}^{k}$ $ \mathcal V_v^k $ 中的边的集合。
- $X_{v}^{k}$ $ \mathbf X_v^k $ 由 $V_{v}^{k}$ $ \mathcal V_v^k $ 中所有节点的特征向量组成。
- $E_{v}^{k}$ $ \mathbf E_v^k $ 由 $E_{v}^{k}$ $ \mathcal E_v^k $ 中所有边的特征向量组成。
定理：节点 $v$ $ v $ 的 k-hop 邻域为 $G_{v}^{k} = (V_{v}^{k}, E_{v}^{k}, X_{v}^{k}, E_{v}^{k})$ $ \mathcal G_v^k=\left(\mathcal V_v^k,\mathcal E_v^k,\mathbf X_v^k,\mathbf E_v^k\right) $ 包含了 sufficient 和necessary 的信息来使得一个 k 层 GNN 模型生成节点 $v$ $ v $ 的 embedding 。

该定理可以通过数学归纳法来证明。这个定理显示了 GNN 的计算和 k-hop 邻域之间的关系。可以看到：在一个 k 层 GNN 模型中，节点 $v$ $ v $ 的第 $k$ $ k $ 层的 embedding 仅取决于其 k-hop 邻域，而不是整个图。

6.2 系统

这里我们首先概述我们的 AGL 系统，然后我们详细说明了三个核心模块（即 GraphFlat、GraphTrainer、GraphInfer ），最后我们给出了一个demo 来说明如何使用AGL 系统实现简单的 GCN 模型。

6.2.1 系统总览

我们构建 AGL 的主要动机是：
- 工业界渴望一个支持图数据训练和推断的集成系统，并且具有可扩展性scalability，同时具有基于成熟的工业基础设施（如 MapReduce、参数服务器等）的容错性。
  
  即，工业界不需要具有巨大内存和高带宽网络的单个巨型机或自定义的图存储引擎，因为这对于互联网公司升级其基础设施而言代价太大。
  
  我们试图提供一种基于成熟和经典基础设施的解决方案，该方案易于部署，且同时享受容错性等各种优点。
- 其次，我们需要基于成熟的基础设施扩展到工业级规模图数据的解决方案。
- 最后，除了优化训练之外，我们的目标是在图上加速推断任务。因为在实践过程中，与未标记数据（通常需要推断数十亿节点）相比，标记数据通常非常有限（例如只有千万级别）。
设计 AGL 的原则是基于 GNN 背后的消息传递机制。即，对于每个节点我们首先合并其入边in-edge 邻居的信息，然后向该节点的出边 out-edge 邻居传播消息。

我们将这种规则反复应用于训练和推断过程，并设计了 GraphFlat 、GraphTrainer 和 GraphInfer 。
- GraphFlat 在训练过程中生成独立的 K-hop 邻域。
- GraphTrainer 训练节点的 embedding 。
- GraphInfer 通过训练好的 GNN 模型来推断节点的 embedding 。
根据动机和设计原则， AGL 利用 MapReduce 和 Parameter Server 等几种强大的并行体系架构，通过精心设计的分布式实现来构建每个组件。结果，即使将 AGL 部署在具有相对较低的算力和有限内存的计算机的集群上，AGL 和几种先进的系统相比，仍然具有相当的效果effectiveness 和更高的效率efficiency 。而且，AGL 具有对数十亿节点、数千亿边的工业级规模的图执行完整的图机器学习的能力。

下图描述了 AGL 的系统架构，它由三个模块组成：
- GraphFlat：是基于消息传递的、高效的efficient 、分布式的distributed 生成器，用于生成包含每个目标节点完整信息子图的 K-hop 邻域。这些小的 K-hop 邻域被展平flatten 为 protobuf 字符串，并存储在分布式文件系统上。
  
  由于 K-hop 邻域包含每个目标节点的足够的和必要的信息，因此我们可以将其中的一个或者batch 加载到内存中，而不是加载整个图，并且可以像其他任何传统学习方法一样进行训练。
  
  此外，我们提出了一种重索引 re-indexing 技术以及一个采样sampling 框架，从而处理真实应用场景中的 hub 节点（具有非常多的邻居）。
  
  我们的设计基于以下观察：标记节点的数量是有限的，我们可以将标记节点关联的那些 K-hop 邻域存储在磁盘中，而不会花费太多代价。
- GraphTrainer：基于GraphFlat 保证的数据独立性，GraphTrainer 利用许多技术（如 pipeline、剪枝pruning、边分区edge-partition ）来降低 I/O 开销，并在训练 GNN 模型期间优化浮点数计算。
  
  结果，即使在基于商用机器的通用 CPU 集群上，GraphTrainer 在实际工业场景中也能获得很高的近线性 near-linear 加速。
- GraphInfer：这是一个分布式推断模块，可以将 K 层 GNN 模型分成 K 个分片 slice，并基于 MapReduce 应用 K 次消息传递。
  
  GraphInfer 最大限度地利用了每个节点的 embedding，因为第 k 层的所有intermediate embedding 都将传播到下一轮的消息传递。这显著提高了推断速度。
可以看到，AGL 仅适用于基于消息传递的半监督 GNN 模型。

6.2.2 GraphFlat

训练 GNN 的主要问题是图数据之间固有的数据依赖性。要对每个节点进行前向传播，则我们必须读取节点关联的邻居、以及邻居的邻居，依此类推。这使得我们无法在现有的参数服务器上部署这类模型，因为参数服务器假设数据并行。

此外，对于大多数工业公司而言，开发额外的图存储引擎来查询每个节点的子图代价太大。

并且这种做法也无法利用现有成熟、且容错性好的常规基础设施。

但是，目标节点的 k-hop 邻域提供了足够的、必要的信息来生成第 k 层节点 embedding。因此，我们可以根据目标节点，将工业级规模的图划分为大量的、微小的 k-hop 邻域，然后在训练阶段将其中的一个或一批（而不是整个图）加载到内存中。

沿着这个思路，我们开发了 GraphFlat，一个高效的 k-hop 邻域的分布式生成器。此外，我们还进一步引入了重索引 re-indexing 策略，并设计了一个采样框架来处理 hub 节点并确保 GraphFlat 的负载均衡。
分布式的k-hop 邻域生成器：我们基于消息传递的机制设计一个分布式 pipeline 来生成 k-hop 邻域，并使用 MapReduce 基础设施来实现它。下图说明了这个 pipeline 的工作流。

背后的关键洞察是：对于每个节点 $v$ $ v $ ，我们首先从入边邻居 $N_{v}^{+}$ $ \mathcal N_v^+ $ 接受、合并信息，然后将合并后的消息传播给出边邻居 $N_{v}^{-}$ $ \mathcal N_v^- $ 。通过反复执行该过程 $k$ $ k $ 次，我们得到节点 $v$ $ v $ 的 k-hop 邻域。

假设我们将node table 和 edge table 作为输入。假设 node table 由节点 ID、节点特征组成，edge table 由源节点ID、目标节点 ID、边特征组成。生成 K-hop 邻域的 piepline 的总体流程如下：
- Map 阶段：Map 阶段仅在pipeline 的开始执行一次。对于某个节点，Map 阶段生成三种信息：自身信息（即节点特征）、入边信息（入边的特征和入边的邻居节点）、出边信息（出边的特征和出边的邻居节点）。
  
  注意：我们将节点 ID 设为 shuffle key，并将各种信息作为 value，从而用于下游的 Reduce 阶段。
- Reduce 阶段：Reduce 阶段运行 K 次从而生成 K-hop 邻域。
  
  在第 $k$ $ k $ 轮中：
  - reducer 首先收集相同 shuffle key （即相同的节点 id ）的所有的 values（即三种类型的信息），然后将自己的信息self information和入边信息作为新的self information 。注意：新的 self information 是节点的 k-hop 邻域。
  - 然后，新的 self information 传播到出边的节点。
    
    注意：在下一个 reduce 阶段之前，所有出边的信息保存不变。
  - 最后，reducer 向磁盘输出新的数据记录，其中每个节点 id 作为 shuffle key，而更新后的信息作为新的 value 。
- Storing 阶段：在经过 K 轮 Reduce 阶段之后，最终的 self information 就是节点的 K-hop 邻域。
  
  我们将所有目标节点的 self information 转换为 protobuf 字符串，并存储到分布式文件系统中。
在整个 MapReduce pipeline 中，关键操作是合并 merging 和传播 propagation。在每轮迭代中，给定节点 $v$ $ v $ ，我们将其self information 和上一轮的入边信息合并，然后合并后的结果作为节点 $v$ $ v $ 的 self information 。然后，我们将新的 self information 通过出边传播到出边节点。在 pipeline 的最后，每个目标节点的 k-hop 邻域将展平flatten 为 protobuf 字符串。这就是为什么我们将这个 pipeline 称作 GraphFlat。

注意，由于节点的 k-hop 邻域将这个节点和其它节点区分开，因此我们也将其称作 GraphFeature。

在整个迭代过程中，update 和 propagate 的都是节点的 self information，边的信息保持不变（边的方向、特征、权重）。
采样和重索引：前面介绍的分布式 pipeline 在大多数情况下都能很好地工作。但是由于存在 hub 节点，因此图的 degree 可能会发生倾斜，尤其是在工业场景中。这使得某些节点的 k-hop 邻域可能覆盖几乎整个图。
- 一方面，在GrapFlat 的 Reduce阶段，处理此类hub 节点的 reducer 可能会比其它 reducer 慢得多，因此会不利于 GraphFlat 的负载均衡。
- 另一方面，这些 hub 节点的巨大的 k-hop 邻域可能使得 GraphFlat 和下游模型训练产生 Out Of Memory:OOM 问题。
- 此外，倾斜的数据也可能导致训练到的 GNN 模型的准确率较差。
因此，我们采用了重索引re-indexing 策略，并为 GraphFlat 中的 reducer 设计了一个采样框架。下图说明了 GraphFlat 中带重索引和采样策略的 reducer。在执行重索引、采样策略时引入了三个关键组件：
- 重索引 Re-indexing：当某个 shuffle key （即节点 ID）的入度超过预定阈值（如 10k）时，我们将通过添加随机后缀来更新 shuffle key。这个随机后缀用于将原始shuffle key 的数据记录随机划分到更小的块 piece 。
- 采样框架Sampling framework：我们建立了分布式采样框架，并实现了一套采样策略（如：均匀采样、加权采样），从而降低 k-hop 邻域的规模，尤其是对于那些 hub 节点。
- 倒排索引 Inverted indexing：该组件负责用原始的shuffle key 来替换重索引的 shuffle key。之后，数据记录将输出到磁盘，等待用于下游任务。
在采样之前，重索引组件将同一个 hub 节点关联的数据记录均匀地映射到一组 reducer。这有助于缓解那些 hub 节点可能引起的负载均衡问题。然后，采样框架针对 shuffle key 随机采样其一小部分数据记录。此后，合并、传播操作就像原始 Reducer 一样执行。接下来，倒排索引组件将重索引的 shuffle key 恢复为原始的 shuffle key（即节点 ID）从而应用于下游任务。

通过重索引，我们将 hub 节点的处理过程划分为一组 reducer，从而很好地保持了负载均衡。通过采样，我们将 k-hop 邻域的规模降低到可接受的大小。

6.2.3 GraphTrainer

为了对 GraphFlat 生成的 k-hop 邻域进行有效的训练，我们实现了分布式的图训练框架： GraphTrainer。如下图所示。

GraphTrainer 的总体架构遵循参数服务器的设计，参数服务器由两部分组成：
- worker：worker 在模型训练期间执行大量计算。
- server：server 在模型训练期间维持图模型参数的最新版本。
由于 k-hop 邻域包含足够的、必要的信息来训练 GNN 模型，因此 GraphTrainer 的训练 worker 变得相互独立。它们只需要处理自己的数据分区partition 即可，不需要与其它 worker 进行额外的交流。因此，GNN 模型的训练变得类似于传统机器学习模型的训练（在传统的机器学习模型中，每个 worker 的训练数据都是独立的）。

此外，由于大多数 k-hop 邻域都是很小的子图，占用的内存很少，因此 GraphTrainer 中的训练 worker 仅需要部署在计算资源（即 CPU、内存、网络带宽）有限的商用机器上。

考虑到 k-hop 邻域的性质以及 GNN 训练计算的特点，我们提出了几种优化策略，包括训练 training pipeline、图剪枝graph pruning、边划分edge partition ，从而提高训练效率。
训练工作流 workflow：训练工作流主要包含两个阶段，即子图向量化subgraph vectorization、模型计算。我们以节点分类任务为例来说明这两个阶段。

在节点分类任务中，可以将一个 batch 的训练样本形式化为三元组的集合：
$B = {< TargetedNodeID, Label, GraphFeature >}$
和直接执行模型计算的常规机器学习模型的训练过程不同，GNN 的训练过程必须将 GraphFeature 描述的子图合并在一起，然后将合并的子图向量化为以下三个矩阵：
- 邻接矩阵 $A_{B}$ $ \mathbf A_\mathcal B $ ：包含合并子图的节点和边的稀疏矩阵，矩阵中的边按照 destination 节点排序（因为是有向图）。
- 节点特征矩阵 $X_{B}$ $ \mathbf X_\mathcal B $ ：包含合并子图的节点的特征的特征矩阵。
- 边特征矩阵 $E_{B}$ $ \mathbf E_\mathcal B $ ：包含合并子图的边的特征的特征矩阵。
注意：这三个矩阵包含有关 $B$ $ \mathcal B $ 中所有目标target节点的 k-hop 邻域的所有信息。它们将与节点 ID 和 label 一起馈入模型计算阶段。基于这三个矩阵以及目标节点的 ID 和 label，模型计算阶段负责执行前向传播计算和反向传播计算。
优化策略：这里我们详细阐述三种不同级别的、graph-specific 的优化策略，从而提高训练效率。即： training pipeline（batch-level）、图剪枝graph pruning（graph-level）、边分区edge partition（edge-level）。
- training pipeline：在 GNN 模型训练期间，每个 worker 首先从磁盘读取一个 batch 的训练数据，然后执行子图向量化和模型计算。按顺序依次执行这些步骤非常耗时。
  
  为解决这个问题，我们构建了一个包含两阶段的 pipeline：预处理阶段（包括数据读取和子图向量化）、模型计算阶段。
  
  这两个阶段以并行的方式执行。由于预处理阶段所花费的时间相对于模型计算阶段更短，因此经过几轮训练之后，总的训练时间几乎等于仅执行模型计算所花的时间。
- graph training：给定batch $B$ $ \mathcal B $ 的三个矩阵 $A_{B}, X_{B}, E_{B}$ $ \mathbf A_\mathcal B, \mathbf X_\mathcal B,\mathbf E_\mathcal B $ ，我们有：
  $H_{B}^{(k + 1)} = Φ^{(k)} (H_{B}^{(k)}, A_{B}, E_{B}; W_{Φ}^{(k)})$
  其中：
  - $H_{B}^{(k)}$ $ \mathbf H_{\mathcal B}^{(k)} $ 为 $B$ $ \mathcal B $ 中所有目标节点的所有 k-hop 邻域中节点的第 $k$ $ k $ 层 intermediate embedding 构成的矩阵。
  - $Φ^{(k)}$ $ \Phi^{(k)} $ 表示第 $k$ $ k $ 层的聚合函数。
  假设一共有 $K$ $ K $ 层，则 $B$ $ \mathcal B $ 中所有k-hop 邻域中所有节点最终的 embedding 为 $H_{B}^{(K)}$ $ \mathbf H_\mathcal B^{(K)} $ 。但是，上式包含大量不必要unnecessary 的计算。
  - 一方面，只有 $B$ $ \mathcal B $ 中的目标节点是标记节点。仅仅这些标记节点的 embedding 需要提供给模型的剩余部分（比如损失函数计算的部分）。这意味着 $H_{B}^{(K)}$ $ \mathbf H_\mathcal B^{(K)} $ 中剩余的 embedding 对于模型的剩余部分来讲是不必要的。
  - 另一方面，三个矩阵 $A_{B}, X_{B}, E_{B}$ $ \mathbf A_\mathcal B, \mathbf X_\mathcal B,\mathbf E_\mathcal B $ 只能为目标节点提供足够的、必要的信息。因此，由于缺乏足够的信息， $H_{B}^{(K)}$ $ \mathbf H_\mathcal B^{(K)} $ 中剩余的 embedding 可能无法正确生成。
  为解决这些问题，我们提出了一种图剪枝策略，从而减少上述不必要的计算。给定目标节点 $v$ $ v $ ，对于任意节点 $u$ $ u $ ，我们令 $d (v, u)$ $ d(v,u) $ 表示从节点 $u$ $ u $ 到节点 $v$ $ v $ 的最短路径。
  
  给定一个 batch 的目标节点 $V_{B}$ $ \mathcal V_\mathcal B $ ，对于任意节点 $u$ $ u $ ，我们定义节点 $u$ $ u $ 和 $V_{B}$ $ \mathcal V_\mathcal B $ 的距离为：
  $d (V_{B}, u) = min ({d (v, u)}_{v \in V_{B}})$
  在深入研究 GNN 模型的计算范式之后，我们有以下观察：给定第 $k$ $ k $ 层 embedding 之后，第 $k + 1$ $ k+1 $ 层 embedding 的感受野变为 1-hop 邻域。这种观察促使我们从 $A_{B}$ $ \mathbf A_\mathcal B $ 中裁剪不必要的节点和边。
  
  具体而言，在第 $k$ $ k $ 层中，我们将 $d (V_{B}, u) > K - k + 1$ $ d(\mathcal V_\mathcal B,u)\gt K-k+1 $ 的所有节点 $u$ $ u $ 及其关联的边，都从 $A_{B}$ $ \mathbf A_\mathcal B $ 中裁剪掉，从而生成一个裁剪的邻接矩阵 $A_{B}^{(k)}$ $ \mathbf A_\mathcal B^{(k)} $ 。
  
  因此，上式重写为：
  $H_{B}^{(k + 1)} = Φ^{(k)} (H_{B}^{(k)}, A_{B}^{(k)}, E_{B}; W_{Φ}^{(k)})$
  注意：如果将邻接矩阵视为稀疏张量，则模型计算中仅涉及非零值。本质上，图裁剪策略是减少每层邻接矩阵中的非零值的数量。因此，它确实有助于减少大多数GNN 算法中的不必要的计算。此外，每个 $A_{B}^{(k)}$ $ \mathbf A_\mathcal B^{(k)} $ 都可以在子图向量化阶段预先计算好。借助于 training pipeline 策略，几乎不需要额外的时间来执行图剪枝。
  
  上图的右侧给出了一个示例，从而说明针对一个目标节点（即节点 A）的图剪枝策略。
  
  读者注：随着 $k$ $ k $ 的增加，我们需要越来越少的邻域节点就可以生成目标节点的 embedding 。
- Edge partitioning：如上式所示，聚合器 $Φ^{(k)}$ $ \Phi^{(k)} $ 用于沿着每个节点在稀疏邻接矩阵 $A_{B}^{(k)}$ $ \mathbf A_\mathcal B^{(k)} $ 中的边，从而聚合每个节点的信息。在模型计算阶段，将会频繁地应用稀疏矩阵乘法等几种聚合算子aggregation operator ，这使得聚合的优化对于图机器学习系统而言变得非常重要。
  
  但是，传统的深度学习框架（例如 TensorFlow,PyTorch）很少解决该问题，因为它们不是专门为图机器学习系统设计的。
  
  为解决该问题，我们提出了一种边分区策略来并行地执行图聚合。关键的洞察是：节点仅沿着指向它的边（入边）来聚合信息。如果具有相同目标节点的所有边都可以使用同一个线程来处理，那么多线程聚合将非常有效。因为任何两个线程之间都不会发生冲突。为实现该目标，我们将稀疏邻接矩阵划分为 $t$ $ t $ 部分，并且确保具有相同 destination 节点的边落在相同的分区partition 。
  
  边分区策略在上图的中间部分的顶部区域来说明。
  
  在边分区之后，每个分区将由一个线程独立地执行聚合操作。
  - 一方面，一个 batch 的训练样本中，节点的数量通常远大于线程数。
  - 另一方面，在GraphFlat 中应用采样之后，每个节点的邻居数量（即邻接矩阵中每行的非零项的数量）不会太大。
  因此，多线程聚合可以实现负载均衡load balancing ，从而在训练 GNN 模型时获得显著加速。

6.2.4 GraphInfer

在工业级规模的图上执行 GNN 模型推断可能是一个棘手的问题。
- 一方面，推断任务的数据规模和使用频率可能比工业场景中训练任务的数据规模和使用频率高得多。这需要一个设计良好的推断框架来提高推断任务的效率。
- 另一方面，由于 GraphFeatures 描述的不同 k-hop 邻域可能会相互重叠，因此直接在 GraphFeatures 上进行推断可能会导致大量重复 embedding 推断，因此变得非常耗时。
因此，我们通过遵循消息传递机制设计了 GraphInfer，它是一种用于大型图上进行 GNN 模型推断的分布式框架。
- 我们首先执行层次的模型分割hierarchical model segmentation，从而将训练好的 K 层 GNN 模型拆分为 K+1 个分片 slices。
- 然后，基于消息传递机制，我们开发了 MapReduce pipeline ，从而从底层到高层的顺序推断不同的分片slice。
  
  具体而言，第 $k$ $ k $ 个 Reduce 阶段加载第 $k$ $ k $ 个模型分片slice，合并入边in-edge邻居上一层embedding 来生成第 $k$ $ k $ 层的 intermediate embedding。然后通过出边out-edge 传播这些 intermediate embedding 到destination node 从而用于第 $k + 1$ $ k+1 $ 层的 Reduce 阶段。
下图描述了 GraphInfer 的整体架构。

这就是模型并行。因为推断期间只需要前向传播，不需要反向传播，因此不需要维持 GNN 的节点状态，因此可以通过 map-reduce 来计算。
GraphInfer 总结如下：
- 层次的模型分割Hierarchical model segmentation：一个 K 层的 GNN 模型以模型层次方面拆分为 $K + 1$ $ K+1 $ 个分片slice。具体而言，第 $k$ $ k $ 个分片slice由第 $k$ $ k $ 层 GNN layer 的所有参数组成，而第 $K + 1$ $ K+1 $ 个分片slice 由最终prediction layer 的所有参数组成。
- Map阶段：类似于 GraphFlat，这里的 Map 阶段仅仅在 pipeline 的开始运行依次。对于每个节点，Map 阶段也生成三种信息，即：自信息 self information、入边信息 in-edge information、出边信息 out-edge information。
  
  然后，节点ID 设置为 shuffle key、各种信息设置为 value，从而用于下游的 Reduce 阶段。
- Reduce 阶段：Reduce 阶段运行 $K + 1$ $ K+1 $ 轮，其中前 $K$ $ K $ 轮将生成第 $K$ $ K $ 层的节点 embedding，最后一轮将执行最终预测。
  - 对于前 $K$ $ K $ 轮，reducer 的作用类似于 GraphFlat。但是在合并阶段，reducer 这里不会生成 k-hop 邻域，而是加载其模型分片slice 从而根据self-information、in-edge information 从而推断节点 embedding，并将结果设置为新的 self-information。
    
    注意，在第 $K$ $ K $ 轮中，reducer 推断出第 $K$ $ K $ 层的的节点 embedding，只需要将其输出给最后一个 Reduce 阶段，而不是将所有三种信息都输出给最后一个 Reduce 阶段。
  - 最后的 Reduce 阶段负责推断最终的预测得分，并将其作为推断结果输出。
上述 pipeline 中没有重复的推断，这在很大程度上减少了时间成本。此外，在对整个图的一部分执行推断任务的情况下，类似于 GraphTrainer 中的剪枝策略也可以在 pipeline 中使用。值得注意的是，我们还在 GraphInfer 中实现了前面介绍的采样和索引策略，从而保持与 GraphFlat 中数据处理的一致性，这可以为基于 GraphFlat 和 GraphTrainer 训练的模型提供无偏推断。

6.2.5 示例

下面的代码展示了AGL 的用法：通过GraphFlat 执行数据生成、通过 GraphTrainer 进行模型训练、通过 GraphInfer 执行模型推断。此外，我们还给出了有关如何实现简单 GCN 模型的示例。


########### GraphFlat ###########
GraphFlat -n node_table -e edge_table -h hops -s sampling_strategy ;
########### GraphTrainer ###########
GraphTrainer -m model_name -i input -t train_strategy -c dist_configs ;
########### GraphInfer ###########
GraphInfer -m model -i input -c infer_configs ;
########### Model File ###########
class GCNModel :
  def __init__ (self , targetID , GraphFeatue , label , ...)
    # get adj , node_feature and edge_feature from GraphFeatue
    adj , node_feature , edge_feature = subgraph_vectorize (GraphFeatue )
    ....
    # pruning edges for different layers
    adj_list = pruning ( adj )
  def call ( adj_list , node_feature , ...) :
    # initial node_embedding with raw node_feature , like :
    # node_embedding = node_feature
    ....
    # multi - layers
    for k in range ( multi_layers ):
      node_embedding = GCNlayer ( adj_list [k], node_embedding )
      # other process like dropout
      ...
    target_node_embedding = look_up ( node_embedding , targetID )
    return target_node_embedding
...
class GCNLayer :
  def __init__ (...)
    # configuration and init weights
    ...
  def call (self , adj , node_embedding ):
    # some preprocess
    ...
    # aggregator with edge_partition
    node_embedding = aggregator (adj , node_embedding )
    return node_embeddin

对于前面描述的每个模块，我们分别提供了一个封装良好的接口。
- GraphFlat 将原始输入转换为 k-hop 邻域。用户只需要选择一种采样策略，并准备一个 node table 和一个 edge table，即可为目标节点生成 k-hop 邻域。这些 k-hop 邻域是 GraphTrainer 的输入，并被形式化为三元组的集合 $B = {< TargetedNodeID, Label, GraphFeature >}$ $ \mathcal B=\{<\text{TargetedNodeID, Label, GraphFeature}>\} $ 。
- 然后，通过为 GraphTrainer 提供一组配置，如模型名称、输入、分布式训练配置（worker 数量、参数服务器数量）等等，将在集群上分布式训练 GNN 模型。
- 之后，GraphInfer 将加载训练好的模型以及推断数据，从而执行推断过程。
这样，开发人员只需要关心 GNN 模型的实现即可。
这里我们以 GCN 为例，说明如何在 AGL 中开发 GNN 模型。
- 首先，我们应该使用子图向量化函数subgraph vectorize function 将 GraphFeature 解析为邻接矩阵、节点特征矩阵、边特征矩阵（如果需要）。
- 然后，通过调用剪枝函数pruning function 启用剪枝策略，则会生成一个邻接矩阵的列表adj_list。
- 然后，adj_list 中的第 $k$ $ k $ 个元素（代表者第 $k$ $ k $ 层邻接矩阵的剪枝）以及第 $k - 1$ $ k-1 $ 层的 intermediate embedding 将被馈入第 $k$ $ k $ 层。
  
  注意，在每个 GCNLayer 中，通过调用聚合函数aggregator function，信息将从入边的邻居聚合到目标节点。
通过这些接口，可以快速实现 GNN 模型，并且与单台机器的代码没有什么区别。

6.3 实验

数据集：我们使用三个数据集，包括两个流行的数据集Cora,PPI，以及一个工业级的社交网络User-User Graph: UUG（由支付宝 Alipay 提供）。
- Cora：引文网络数据集，包含2708 个节点、5429 条边。每个节点关联一个 1433 维的特征，节点属于七种类别中的一个。
- PPI：蛋白质相互作用数据集，由 24 个独立的图组成。这些图一共包含56944 个节点、818716 条边。每个节点关联一个 50 维的特征，节点属于121 种类别种的几个。
- UUG：包含从支付宝的各种场景中收集的大量社交关系，其中节点代表用户、边代表用户之间的各种关系。它包含高达 $6.29 \times 10^{9}$ $ 6.29\times 10^9 $ 个节点、 $3.38 \times 10^{11}$ $ 3.38\times 10^{11} $ 条边。每个节点关联一个 656 维特征，节点属于两个类别中的一种。
  
  据我们所知，这是所有文献中图机器学习任务的最大规模的属性图 attributed graph 。
根据之前论文的配置，我们将 Cora,PPI 数据集分别拆分为三部分：training/validation/test 。对于 UUG 数据集，我们一共有 $1.5 \times 10^{8}$ $ 1.5\times 10^8 $ 个标记节点，我们选择其中的 $1.2 \times 10^{8}$ $ 1.2\times 10^8 $ 个节点作为训练集、 $5 \times 10^{6}$ $ 5\times 10^6 $ 个节点作为验证集、 $1.5 \times 10^{7}$ $ 1.5\times 10^7 $ 个节点作为测试集。注意：训练集、验证集、测试集相互之间没有交叉的。

所有这些数据集的统计信息见下表所示。
评估的配置：我们将 AGL 和两个著名的开源图机器学习系统进行比较，从而证明我们系统的有效性effectiveness、效率effciency、和可扩展性scalability ：
- Deep Graph Library:DGL：一个 Python package，可以基于现有的面向张量的框架（如 PyTorch/MXNet）为图结构数据提供接口。
- PyTorch Geometric:PyG：一个基于 PyTorch 的深度学习库，用于对不规则结构的数据（如 Graph图、点云point cloud、流形manifold）进行深度学习。
对于每个系统，我们分别在两个公共数据集（Cora,PPI）上评估了三种广泛使用的 GNN：GCN、GAT、GraphSAGE。另外，我们将这三个模型对应的原始论文报告的那些 GNN 的性能作为 baseline 。

为了公平地进行比较，我们仔细地调优了这些 GNN 的超参数（如学习率、dropout ratio 等）。对于 Cora,PPI 的实验，embedding size 分别设置为 16 和 64 。所有的 GNN 模型使用 Adam 优化器优化，最多训练 200 个 epoch。

对于 UUG 数据集，embedding size 仅为 8 。

为了减小方差，我们为每个实验记录了 10 次运行后的平均结果。

注意，在评估公共数据集的训练效率时，所有系统都在独立容器（机器）上以相同的CPU （Intel Xeon E5-2682 v4@2.50GHz）运行。

对于 UUG 实验，我们将系统部署在蚂蚁金服的集群上，从而验证我们的 AGL 在工业场景中的真实性能。注意，这里集群并不是只有我们这个任务，还有其它任务此时都在这个集群上运行，这在工业环境中很常见。我们通过改变 worker 数量来分析收敛曲线和加速比，从而验证AGL 的可扩展性。

但是，DGL 和 PyG 都无法在 UUG 数据集上运行，因为这两个系统无法支持分布式模式，并且以单机模式运行会导致 OOM 问题。因此我们不包括 DGL 和 PyG 在 UUG 数据集上的结果。
评估指标：我们从几个方面来评估AGL 。
- 首先，我们报告 Cora,PPI 的准确率和 micro-F1 得分，从而证明不同系统训练的GNN 模型的有效性。
- 其次，我们报告训练阶段每个 epoch 的平均时间成本，从而证明不同系统的训练效率。
- 此外，我们使用 UUG 数据集训练节点分类模型，并对整个 User-User Graph 进行推断。通过报告训练阶段和推断阶段的时间成本，我们证明了 AGL 在工业场景的优越性。
- 最后，我们报告了工业级的 UUG 数据集的收敛曲线和训练的加速比，从而证明了 AGL 的可扩展性。

6.3.1 公开数据集

这里我们报告了两个公共数据集（Cora,PPI）上AGL 和 DGL,PyG 的对比，从而评估不同系统的效果和效率。
效果Effectiveness：下表给出了不同的图机器学习系统实现的三个GNN 模型（GCN,GAT,GraphSAGE）在两个公共数据集、一个工业数据集上的效果。

评估指标为：对于 Cora 数据集为准确率、对于 PPI 数据集为 micro-F1、对于 UUG 数据集为 AUC。同时我们还报告了这些 GNN 模型在原始论文中提供的结果作为 baseline 。

结论：
- 在这两个公共数据集上，AGL 实现和训练的所有这三个GNN 模型的性能都可以和 PyG/DGL 中的模型相媲美。
  
  大多数情况下，GNN 模型的性能偏差都小于 0.01。但是，对于 PPI 上的 GraphSAGE ，这三个系统的性能均高于 baseline，这是由于传播阶段的差异所致。具体而言，在聚合邻域信息时，这三个系统采用 add 算子，而原始论文使用 concat 算子。
- 此外，AGL 的这三个 GNN 模型都可以很好地在 UUG 上工作并取得合理的结果。其中 GAT 的效果最佳，这是可以预期的，因为它为不同邻居学习了不同的权重。
效率Efficiency：基于 PPI 数据集，我们比较了三个图机器学习系统上训练的不同深度（1 层、2 层、3 层）的不同 GNN 模型（GCN, GraphSAGE, GAT ）的训练效率。

下表报告了所有训练任务每个 epoch 的平均时间成本。同时我们还给出了不同优化策略的结果（即图剪枝、边分区）。具体而言：
- 下标为 Base 表示不采用任何优化策略的原始 pipeline 方法。
- 下标为 +pruning 表示采用图剪枝优化策略的方法。
- 下标为 +partition 表示采用边分区优化策略的方法。
- 下标为 +pruning&partition 表示同时采用图剪枝和边分区优化策略的方法。
注意，我们的系统是专为工业级规模的图而设计的。在训练阶段，数据将从磁盘而不是内存加载（PyG 和 DGL 就是从内存加载）。因此我们将 AGLBase 视为公平的 baseline 。尽管我们的系统是为工业级规模的图上分布式训练 GNN 模型而设计的，它也证明了在单机模式standalone mode 下 CPU 的出色的训练速度。下表为单机模式下，PPI 数据集训练阶段每个 epoch 的时间成本（单位秒）。

通常在训练阶段，AGL 与 PyG 相比实现了 5 ~ 13 倍的加速、与 DGL 相比实现了 1.2 ~ 3.5 倍的加速。对于所有不同深度的三个GNN 模型上，AGL 在不同程度上都优于其它两个图机器学习系统。

此外，我们还进一步验证了所提出的优化策略（即图剪枝、边分区）的优越性。
- 首先，图剪枝策略或边分区策略在不同 GNN 模型上都能很好地工作。这可以通过比较 AGL + pruning vs AGL_base、以及 AGL + edge partitioning vs AGL_base 得以证明。
  
  并且，当采用 AGL + pruning + partition 时，这两种优化策略可以实现更大的提升。
- 其次，这两种策略在不同情况下的加速比有所不同。
  - 边分区策略在 GCN, GraphSAGE 中的加速比要比 GAT 更高。
  - 图剪枝策略在训练1 层 GNN 模型时不起作用，但是在训练更深层 GNN 时效果很好。
  这种观察是由于两种策略背后的不同见解 insight 引起的。图剪枝策略旨在减少不必要的计算（通过裁剪不会用于传播信息给目标节点的边来进行）。边划分策略以一种有效的、并行的方式实现了邻居之间的信息聚合。
  - 一方面，这两种策略优化了训练 GNN 模型的一些关键step，因此它们能够使得GNN 模型的训练受益。
  - 另一方面，也存在一些限制。
    - 例如，如果我们训练一个 1 层的 GNN 模型，则图剪枝策略不起作用是合理的。因为每条边在将信息传播到目标节点中都扮演着角色，并且没有不必要的计算。
    - 此外，如果模型包含比沿着边聚合信息更稠密的计算（如计算注意力），则这些策略的效果将会被降低，因为稠密的计算将占据总时间成本中的大部分。

6.3.2 工业数据集

我们使用MapReduce 和参数服务器来实现 AGL，并将其部署在由一千多台计算机组成的 CPU 集群中，每台计算机由具有 64G 内存、200G HDD 的 32-core CPU 组成。然后我们对工业数据集（即 UUG 数据集）进行实验，从而证明 AGL 在工业场景中的可扩展性和效率。
工业级的训练：可扩展性scalability 是工业级图机器学习系统最重要的标准之一。这里我们集中在两个方面评估 AGL 的训练可扩展性，即收敛convergence 和加速比speedup 。为此，我们使用不同数量的worker 来在工业级的 UUG 数据集上训练 GAT 模型，并且在下图中分别报告了收敛性和加速比的结果。
- 收敛性：左图给出了 AGL 在收敛性方面的训练可扩展性。其中 y 轴表示 GNN 模型的 AUC、x 轴表示训练的 epoch 数量。
  
  一般而言，无论训练 worker 的数量如何，AGL 最终都可以收敛到相同水平的 AUC。如左图所示，尽管分布式模式下需要更多的训练 epoch 数量，但是收敛曲线最终达到单机训练的 AUC 相同的水平。因此，在分布式训练下可以保证模型的有效性，这证明了 AGL 无需考虑收敛性就可以扩展到工业级规模的图。
  
  这里是训练 AUC 还是验证 AUC？论文并未讲清楚。
  
  此外可以看到：在相同 epoch 情况下，分布式训练的效果通常略差于单机。这似乎是一个普遍现象。
- 加速比：我们还展示了加速比方面的训练可扩展性。如右图所示，AGL 实现了近线性near-linear 的加速，斜率约为 0.8 。这意味着如果将训练 worker 的数量增加一倍，则训练速度将提高到 1.8 倍。
  
  注意：
  - 在实验中，我们将训练 worker 的数量从 1 扩展到 100，间隔为 10 。结果，AGL 实现了持续的高的加速比，并且斜率几乎不降低。例如，当训练 worker 的数量达到 100 个时，我们的速度加快 78 倍，仅略低于预期的 80 。
  - 所有这些实验都是在实际生产环境中的集群上进行的。可能在同一台物理机上运行了不同的任务。随着训练 worker 的增加，网络通信的开销可能会略有增加，从而导致加速比曲线的斜率扰动。这再次证明了AGL 系统在工业级场景中的鲁棒性。
值得注意的是，在 UUG 上训练 2 层 GAT 模型只需要大约 14 个小时，直到收敛为止。具体而言：
- GraphFlat 使用大约 1000 个 worker 需要 3.7 个小时来生成 GraphFeature。
- GraphTrainer 只需要 100 个 worker 大约 10 个小时来训练 GAT 模型。
整个 pipeline 可以在 14 个小时内完成，这对于工业级应用而言非常出色。

如果只有 100 个 worker，那么需要 37 个小时来生成 GraphFeature，此时总的 pipeline 耗时为 47 个小时。可以看到：最大的时间消耗在 GraphFeature 生成上面。

此外，在训练阶段，训练任务的每个 worker 只需要 5.5 GB 的内存（总计 550GB ），这远远少于存储整个图的内存成本（35.5 TB）。

总之，由于 AGL 巧妙的体系结构的设计，AGL 满足了在工业级图上训练 GNN 模型的工业可扩展性的要求。
工业级的推断：我们在整个 UUG 数据集上评估了 GraphInfer 的效率，数据集包含 $6.23 \times 10^{9}$ $ 6.23\times 10^9 $ 个节点、 $3.38 \times 10^{11}$ $ 3.38\times 10^{11} $ 条边。在下表中，我们报告了推断任务消耗的时间和资源。

由于没有图机器学习系统能够处理如此大的图，因此我们将 GraphInfer 和基于 GraphFeature 的原始推断模块进行了比较。注意，所有这些实验的并发度concurrency 都相同，即 1000 个 worker 。

可以看到：GraphInfer 在时间成本和资源成本上始终优于原始推断模块。对于两层的 GAT 模型（模型生成的 embedding 维度为 8 维），GraphInfer 需要大约 1.2 小时来推断 62.3 亿个节点的预估得分，这大约是原始推断模块所花费时间的 1/4 。此外，GraphInfer 还分别节省了 50% 的 CPU 成本、76% 的内存成本。

与基于 GraphFeature 的原始推断模块相比，GraphInfer 通过采用消息传递方案避免了重复计算，这就是它优于原始推断模块的原因。