Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

机器之心编辑部专栏

VLDB 2022最佳研究论文:克服通信挑战,新框架SANCUS实现GNN高效训练

近年来,图神经网络(GNN)在社交媒体、电子商务、知识图谱、推荐系统、生命科学等领域得到了广泛应用。随着图数据规模的快速增长,亟需发展分布式大规模图神经网络高效训练技术。现有的方法主要采用中心化的参数服务器(PS)架构,计算节点间的大量网络通信成为了训练的性能瓶颈。

为了克服这一挑战,本文提出了一种陈旧性感知且通信回避的去中心化全图 GNN 训练框架 SANCUS,实现了高效地分布式神经网络训练。SANCUS 通过利用历史嵌入,主动创造异步性,避免了大量通信;设计了跳过广播(skip-broadcast)机制,训练时动态重塑通信拓扑,实现了嵌入的灵活传输。为了自适应地维护历史嵌入,提出了嵌入有界陈旧性指标,并从理论上证明了陈旧性感知训练框架的收敛性。实验结果表明,与 SOTA 方法相比,在不损失精度的前提下,SANCUS 可以节约高达 74% 的网络通信,平均吞吐量提升至少 1.86 倍。SANCUS 将传统分布式机器学习中的有界梯度陈旧性泛化到去中心化分布式 GNN 中的历史嵌入上,理论上新指标可以推广至其他分布式 GNN 训练架构。

图片

  • 论文链接:https://www.vldb.org/pvldb/vol15/p1937-peng.pdf

  • 代码链接:https://github.com/chenzhao/light-dist-gnn

  • 更多详细信息:http://home.cse.ust.hk/~leichen/

一、引言

如今神经网络 (GNNs) 因为具有良好的学习性能,已广泛应用于不同领域的预测分析任务。但面对大规模图,GNN 仍面临着巨大挑战,主要表现为随着数据和模型规模的增长而产生的占用内存和计算资源的爆炸式增长。分布式 GNN 训练成为了一种有效的解决方案。流行的基于采样的分布式 GNN 训练存在信息损失、采样开销大、收敛性保证难的问题,本文聚焦全图 GNN 的分布式训练。分布式全图 GNN 训练,除了占用大量的内存外,由于不规则邻域访问和迭代学习过程的耦合,计算节点间产生了密集的通信,包括梯度、模型参数以及嵌入的传输,这使得高效的分布式 GNN 训练更具挑战性。目前如阿里巴巴、亚马逊、微软等公司研发的分布式 GNN 系统主要采用中心化参数服务器 (PS) 架构。为了追求效率和可伸缩性,PS 架构需要昂贵的预处理和复杂工作流。对于大规模神经网络,研究表明去中心化的架构在理论上更具有优越性。在神经网络方面,CAGNET 是当前最先进的去中心化的训练算法。然而,CAGNET 在训练过程中需要大量同步,产生了大量的额外通信开销。

针对上述挑战,本文提出了陈旧性感知且通信回避的去中心化分布式 GNN 训练框架 SANCUS。它将 GNN 训练视作一系列矩阵乘法,通过对历史嵌入进行自适应的缓存和跳过广播,极大地降低了训练过程中的网络通信。同时,设计了有界陈旧性指标,并基于指标动态缓存历史嵌入,实现了主动地 GNN 异步训练。此外,从理论上证明了新框架下模型的收敛性,并通过大量实验验证了 SANCUS 通信避免的效果和精度的稳定性。

二、SANCUS 介绍

2.1 框架概述

图片

上图展示了 SANCUS 框架的基本训练流程,主要包括五个步骤:(1)数据加载,(2)陈旧性边界检查,(3)嵌入广播,(4)GNN 模型计算,以及(5)结果缓存。接下来分别介绍这些步骤。

图片

(1)如上图所示,将全图的整个稀疏邻接矩阵和密集嵌入矩阵横向划分为矩阵块和(i [1,4]),与完整的权重矩阵 W 一起存入,每个 GPU 保留自己的完整模型副本;

(2)在每个 GPU 上,广播上一轮 GNN 计算结果之前,根据陈旧性指标检查嵌入的陈旧性,如果对应 GPU 的嵌入陈旧度在规定边界内,则跳过嵌入广播,并用缓存的历史嵌入迭代模型计算;

(3)否则,如果特征的陈旧性超过边界,则将最新嵌入一对多并行广播到所有 GPU,在缓存中更新。在 GPU 轮询一轮之后,就可以为一层更新整个嵌入矩阵 H;

(4)将最新嵌入或缓存的历史嵌入加载到 GNN 模型中进行计算;

(5)在广播之前,更新的嵌入被分派到下一迭代的陈旧性检查中。

2.2 传播算法和训练过程

图片

训练过程如上图所示,将分布式 GNN 视作矩阵乘法序列,以避免聚合过程中密集的邻居获取。邻接矩阵 A 和嵌入矩阵 H 被分块存放到不同的设备,对并行的分布式进程 P(i),定义了矩阵乘法图片的中间结果图片。SANCUS 利用 Ring-AllReduce 进行前向、反向传播。

图片

SANCUS 的传播算法如上图所示。计算设备并行分别对每个层进行训练。在向其他设备广播之前,先检查进程 j 的嵌入图片的陈旧性。若进程状态是活跃,则将图片从根 rank 通过环形通信拓扑中的一对多广播依次复制到所有设备,并相应地缓存。否则,如果进程陈旧,SANCUS 将执行跳播。这一迭代进程 j 停止广播图片,所有其他设备重复使用历史嵌入图片的缓存版本。每个设备在本地进一步计算中间结果图片,用于计算嵌入图片。在得到最新嵌入图片后,检查图片是否在陈旧性边界内,对应更新进程状态标识 F(i)。在反向传播时,梯度图片以类似的方式广播。为最后,为了更新模型,执行 AllReduce 整合来自所有设备的梯度结果并将其发送到所有 ranks。

三、缓存历史嵌入管理机制和自适应跳播机制

3.1 缓存历史嵌入

为进一步降低设备间通信,在训练中主动的利用历史嵌入。历史嵌入缓存在每个 GPU 中,只保留一份最近用到的嵌入。进程图片活跃以广播嵌入子矩阵图片的最新结果或陈旧以重复使用历史图片,具体如下式所示:

图片

3.2 自适应跳过广播

SANCUS 实现了一种通信原语,即一种跳过广播 (Skip-Broadcast) 机制,以达到设备间的通信和批量同步。

特别地,SANCUS 允许在训练过程中无缝重构通信拓扑结构。SANCUS 为每个进程 i 存储一个状态标志,指示该设备上进程计算的嵌入相应的状态。具体来说,活跃状态意味着该进程需要广播嵌入的最新版本到所有其他设备进程,并缓存。如果状态陈旧, 则跳播并让其他设备使用缓存的陈旧嵌入。

3.3 嵌入陈旧性的三种度量及其管理机制

跳过广播机制可以有效降低通信量,但每个设备上存在不同版本的嵌入,在系统中主动的创造了不一致性。为了将不一致控制在合理范围,需要对陈旧的历史嵌入进行管理,具体来说,利用边界来约束嵌入陈旧度。为保持去中心化, SANCUS 在每个设备上设计了轻量本地状态跟踪器以进行高效的有界嵌入陈旧性检查。

陈旧性最基本的定义是:让图片和 e 分别表示陈旧嵌入的 epoch 数和当前 epoch 数,可容忍的陈旧 epochs 的最大值为图片,即历史嵌入满足图片。在每图片个 epochs 之后广播嵌入。照此定义检查陈旧性的算法如下。这个检查算法和 Algorithm 1 组成 SCS-E 算法。

图片

接着,SANCUS 提出了更加灵活的自适应陈旧性度量:每个进程必须在最多个 epoch 接收到来自邻居的陈旧嵌入后,向其他设备广播最新嵌入。检查算法 Algorithm 2 和 Algorithm 1 组成 SCS-A 算法。

图片

最后,SANCUS 还提出了基于变化值的自适应陈旧性度量:给定边界, ,当嵌入变化超过,就需广播最新版本。这里不需要版本追踪,只用考虑变化量大小。Algorithm 4 和 Algorithm 1 组成 SCS-H 算法。

图片

理论支撑:文中作者分析了系统的通信成本界限。证明了 SANCUS 中嵌入和梯度的近似误差都是有边界的,同时保证了训练的收敛。SANCUS 的收敛速度比基于抽样的神经网络方法更快也更接近于全图训练。

四、实验结果

实验选取的主要模型是 GCN。实验在四种不同的 GPU 配置上进行:①通过 PCIe 3.0 X 16 连接的 8 个 RTX 2080 Ti;②通过 10Gbps 以太网连接的两台服务器,每个服务器通过 PCIe 3.0 有 4 个 RTX 2080 Ti;③四个通过 NVLink 连接的 A100 40GB;④ 4 个通过 NVLink 连接的 V100 32GB。作者在 Flickr、Reddit、Amazon 和 ogbn-products 上使用①评估,在 ogbn-products 上使用①②③评估。对当前最大的 ogbn-papers100M 数据集使用③,而④作为常用的训练环境配与其他 SOTA 系统进行总体比较。作者亦实现了 GAT 模型展示系统通用性。

对于 Flickr、Reddit、Amazon、ogbn-products 和 ogbn-papers100M,总的训练 epoch 数分别为 300/300/400/500/200。对于陈旧度界限,选择范围 [1,7] 的,范围 [1,5] 中的,和范围 [0.01,0.05] 中的来控制变化幅度。

4.1 不同环境下的通信避免情况

图片

数据集以规模递增顺序展示,以此展示模型的可扩展性。图中只展示精度损失在 0.01 以内的结果。与 SOTA 工作 CAGNET 和有界梯度法 SkipG 相比,我们的所有系统进一步避免了至少 35% 到 74% 的通信。虽然基于传统梯度陈旧度的 SkipG 也优于 CAGNET,但它以准确性为代价。此外,如图所示,在不同的数据集上,SANCUS 的各种变体仍比 SkipG 获得了 29% 到 63% 的通信降低。SANCUS 在 Flickr 上使用 SCS-H3(=0.03)避免了约 74% 的通信,在 Reddit 上使用 SCS-A3 避免了 48% 的通信,在 ogbn-products 上使用 SCS-H3 避免了 50% 的通信。

为进一步显示训练时间的改进,下表给出了 epoch 中计算和通信的具体时间。

图片

接下来,用表现最差的 SANCUS 变体 SCS-E1/A1/H1(避免通信最少)演示通用性。下图根据 GPU 配置、GPU 数量、GNN 总层数和 ogbn-products、Flickr、Reddit 和 ogbn-papers100M 上的隐藏特征大小来表示系统的变量。

图片

具体来说,图 a 中不同 GPU 配置下的通信时间差异很大。尽管 GPU 配置对通信本身有很大的影响, SANCUS 仍在所有配置中展示了良好的通信避免表现 -- 无论是单机多卡还是多服务器环境。进一步检查,SCS-A1 可以在所有设置 (包括多服务器设置) 中一致地实现最少的通信开销。再者,如图 b 所示,随着 GPU 数量增加,相对于 CAGNET 的总成本依然不断降低。虽然通信成本随 GPU 数量增加而增加,但是 SANCUS 可以将使用 8 个 GPU 的通信成本,减少到接近使用 2 个 GPU 的 SOTA 工作 CAGNET 的通信成本,并减少 67% 的计算成本。更重要的是,SANCUS 避免的通信比例随着 GPU 使用数量反而增加,这是中心化 PS 架构难以实现的。此外,当增加隐藏特征大小时,与 CAGNET 相比,SANCUS 变体的通信增加更少也更慢。以上总结了 SANCUS 的鲁棒性和通用性。

4.2 通信避免情况下准确率的表现

图片

SANCUS 所有的策略变体都收敛到与全图 SOTA 工作非常接近或相同的准确率值(<0.005),甚至更高。此外,达到满意精度的时间也快得多。

4.3 与 SOTA 的对比

在常用的 Reddit 数据集上,上表比较了表现最差的 SANCUS 变体 SCS-A1 与五个相关 SOTA 分布式系统的吞吐量(epoch /second),包括:CAGNET、RoC、Dorylus、基于采样的 PaGraph 和 DGCL。可以看到,避免通信最少的 SCS-A1 仍然优于所有相关的 SOTA 分布式 GNN 系统。SCS-A1 策略平均吞吐量至少快 1.86 倍,每秒可以处理 10.3 个 epochs。与目标是低成本的全图分布式 GNN 训练系统 Dorylus 相比,SANCUS 的速度是 68.7 倍,成本仅为 20%。

4.4 跳播机制下的 epoch 分布

如图绘制了在 SANCUS 训练中实际执行广播的相应 epoch。图中 SCS-E1 每 2 个 epoch 就会广播最新结果。因此,橙色点表示的缓存 epoch 有规律地增加。对于自适应方案 SCS-A 和 SCS-H,通过观察点间间距的变化发现广播呈不规则模式,尤其是基于变化量的 SCS-H。

4.5 历史嵌入的缓存占用情况

在 SANCUS 训练过程中,GPU 内存占用分为三部分:本地数据(即嵌入、本地邻接矩阵和全权矩阵)、矩阵运算内存和历史嵌入缓存。与 CAGNET 相比,SANCUS 唯一额外消耗的是历史嵌入缓存。因此,下表说明了缓存占用情况。总的来说,对于现代 GPU 来说,缓存成本很低。

图片

4.6 陈旧性度量的有效性分析和边界选择

图片

如图 a 中的、图 b 中的和图 c 和 d 中的所示。随着陈旧度边界的增大,波动越大,收敛越不稳定,但避免通信越多。虽然收敛速度会有所下降,但由于跳播避免了大量通讯时间,总训练时间仍然更短。较大的陈旧度边界有助于提高吞吐量,但会对准确性产生负面影响。在实际应用中,可根据场景需求,结合收敛速度、通信避免量、准确率来相应调整、和。虽然这仍是一个开放研究问题,但从结果可以得出,和的自适应策略在所有试验数据集和系统配置中均可达到合理的平衡。

五、总结

本论文提出了一个分布式神经网络训练系统 SANCUS。这是第一个主动的利用嵌入陈旧性感知制造异步性以避免通信的去中心化神经网络系统,可以在提高训练效率的同时保持模型性能。作者提出了一组新颖的有界嵌入陈旧性度量指标:epoch 固定的陈旧性、epoch 自适应的陈旧性和基于方差变化的 epoch 自适应陈旧性;并将历史嵌入缓存和有界嵌入陈旧性检查应用到去中心化的神经网络中,以自适应地跳过计算节点之间的数据广播。在大规模基准图数据集的大量实验结果验证了 SANCUS 的高效性和有效性,以及从传统分布式机器学习中被动解决梯度陈旧性到 SANCUS 中主动基于历史嵌入陈旧性与其自适应管理策略的必要性。更多的技术细节和实验可以阅读原论文:https://www.vldb.org/pvldb/vol15/p1937-peng.pdf。

理论SANCUS去中心化全图GNN训练框架
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

重构技术

代码重构(英语:Code refactoring)指对软件代码做任何更动以增加可读性或者简化结构而不影响输出结果。 软件重构需要借助工具完成,重构工具能够修改代码同时修改所有引用该代码的地方。在极限编程的方法学中,重构需要单元测试来支持。

基准技术

一种简单的模型或启发法,用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

分块技术

将标注好词性的句子按句法结构把某些词聚合在一起形成比如主语、谓语、宾语等等。

暂无评论
暂无评论~