大规模并行图计算：从理论到实践
图 (Graph) 适用于在理论意义上表示多个实体组间的联系，并且已在数据科学领域中用于实现各种目的，包括按网络热度排名、社交网络设计以及协助导航。许多情况下，这类应用需要处理包含数千亿条边的图，这些图因太大而无法在单台消费级机器上进行处理。对图算法进行扩展的典型方法是在分布式设置下运行，即划分多台计算机间的数据（和算法），并行执行计算。虽然这种方法可以处理包含数万亿条边的图，但同时也带来了新的挑战。换言之，由于每台计算机一次只能看到输入图的一小部分，因此我们需要处理机器间通信，并设计可划分在多台计算机上的算法。
协助导航
https://ai.googleblog.com/2021/01/addressing-range-anxiety-with-smart.html数千亿条边
https://doi.org/10.1007/s00778-019-00548-x
2008 年，用于实现分布式算法的框架 MapReduce 面世。它在提供良好容错能力的同时以透明方式处理机器间的通信，并指引了许多分布式计算框架的开发，包括 Pregel、Apache Hadoop 以及许多其他框架。尽管如此，开发超大图分布式计算算法的挑战依然存在，并且在这种情况下，即使是设计解决基本问题（例如：连通分量、最大匹配或最短路径）的高效算法都已成热门研究领域。虽然近期的研究验证了解决许多问题的新算法，包括我们用于连通分量（在理论和实践中）以及层次聚类的算法，但是仍然需要能够更快速解决各种问题的方法。
MapReduce
https://research.google/pubs/pub62/Pregel
https://research.google/pubs/pub37252/层次聚类
https://ai.googleblog.com/2018/03/balanced-partitioning-and-hierarchical.html
今天，我们将展示两篇近期针对此问题发表的论文，整个过程包括：先为分布式图算法构建理论模型，然后演示如何应用该模型。所提出的模型“自适应大规模并行计算 (AMPC)”增强了 MapReduce 的理论功能，同时提供在更少的计算回合下解决许多图问题的途径。我们还展示了如何在实践中有效地实现 AMPC 模型。我们介绍的这套算法包含用于最大独立集、最大匹配、连通分量和最小生成树的算法，其运行速度是当前最先进方法的 7 倍。
自适应大规模并行计算
https://dl.acm.org/doi/10.1145/3323165.3323208在实践中有效地实现 AMPC 模型
https://dl.acm.org/doi/abs/10.14778/3424573.3424579
MapReduce 的局限性
为了解 MapReduce 在开发图算法上的局限性，我们考虑了连通分量问题的简化变体。其中，输入是一组有根树，目标是针对每个节点计算其树的根。但即使是这个看似简单的问题，也不容易在 MapReduce 中得到解决。实际上，在大规模并行计算 (MPC) 模型（即，MapReduce、Pregel、Apache Giraph 以及许多其他分布式计算框架背后的理论模型）中，人们普遍认为此问题至少需要多轮与 log n 成正比的计算，其中 n 是图中的总节点数。虽然 log n 看似不是一个大数字，但处理包含数万亿条边的图的算法通常会在每轮计算中将数百太字节的数据写入磁盘中，因此即便是稍微减少几轮计算也可节省大量资源。
大规模并行计算
https://dl.acm.org/doi/10.5555/1873601.1873677人们普遍认为
https://drops.dagstuhl.de/opus/volltexte/2020/11819/
关于查找根节点的问题。节点以蓝色圆形表示。灰色箭头从每个节点指向其父节点。根节点是没有父节点的节点。橙色箭头的路径展示了算法在从节点到其所属树的根节点的过程
在用于查找连通分量和计算层次聚类的算法中，我们发现了一个类似的子问题。我们发现，可通过使用分布式哈希表 (DHT)（这项服务使用大量键值对进行初始化，然后实时返回与所提供键关联的值）来实现这些算法，从而避免 MapReduce 的局限性。在我们的实现中，DHT 会为每个节点储存其父节点。然后，处理图节点的机器可以使用 DHT 并沿着这个树到达根位置。虽然使用 DHT 能够很好地解决这个具体问题（尽管它依赖于深度较小的输入树），但我们不清楚这种思路能否得到更广泛的应用。
连通分量
https://research.google/pubs/pub43122/层次聚类
https://papers.nips.cc/paper/2017/hash/2e1b24a664f5e9c18f407b2f9c73e821-Abstract.html
自适应大规模并行计算模型
为了将此方法扩展到其他问题上，我们开始开发一种模型，从理论上分析利用 DHT 的算法。产生的 AMPC 模型基于完善的 MPC 模型构建，并且正式描述了通过使用分布式哈希表引入的功能。
MPC 模型中有大量机器，它们通过同步回合中传递的消息进行通信。一个回合中发送的消息是在下一回合开始的时候传递的，并构成该回合的整个输入（即，机器不会保留从一个回合到下一回合的信息）。在第一个回合中，我们可以假设输入随机分布在机器间。我们的目标是最大限度地减少计算回合数，同时确保每个回合机器间都能实现负载平衡。
MPC 模型中的计算。每一列在后续计算回合中表示一台机器。当所有机器完成一个计算回合后，系统会传递该回合中发送的所有消息，并且下一回合将会开始
然后，我们通过引入一种新方法对 AMPC 模型进行形式化，其中机器每个回合会对一个只写的分布式哈希表进行写入，而非通过消息进行通信。在新回合开始后，上一回合的哈希表将变为只读状态，而一个新的只写输出哈希表将可供使用。重要的是，只有通信方法发生变化，每台机器的通信量和可用空间则完全按照 MPC 模型中的方式受到限制。因此，在较高级别上，所添加的 AMPC 模型功能是每台机器可以选择要读取的数据，而非被动获得一份数据。
AMPC 模型中的计算。当所有机器已完成一个计算回合后，它们生成的数据将保存到分布式哈希表中。在下一回合中，每台机器可以从此分布式哈希表中读取任意值并写入新的分布式哈希表
算法和经验评估
得益于机器通信方式中这个看似细微的差异，我们能够为许多基本图问题设计出速度更快的算法。特别是，我们证明了无论图的大小如何，都能在回合数固定的情况下找到连通分量、最小生成树、最大匹配以及最大独立集。
连通分量、最小生成树、最大匹配
https://dl.acm.org/doi/abs/10.14778/3424573.3424579最大独立集
https://dl.acm.org/doi/10.1145/3323165.3323208
为了研究 AMPC 算法的实际适用性，我们将 Flume C++（FlumeJava 的 C++ 版本）与 DHT 通信层相结合，对该模型进行了实例化。我们评估了用于最小生成树、最大独立集和最大匹配的 AMPC 算法，并发现其速度可以达到未使用 DHT 的实现的 7 倍。同时，AMPC 实现完成任务所使用的平均回合数是 未使用 DHT 的实现的 1/10，并且向磁盘写入的数据也更少。
FlumeJava
https://research.google/pubs/pub35650/AMPC 算法
https://dl.acm.org/doi/abs/10.14778/3424573.3424579
我们 AMPC 模型的实现利用了硬件加速的远程直接内存访问 (RDMA)，该技术允许读取远程机器的内存，延迟时间为数微秒，仅比读取本地内存慢一个数量级。虽然一些 AMPC 算法比其对应的 MPC 算法传递更多数据，但前者的整体速度更快，因为它们主要使用 RDMA 执行快速读取，而非用更多时间写入磁盘。
结论
受到高效的实际实现启发，我们借助 AMPC 模型构建了一个理论框架，然后开发了提供良好经验性能并保持良好容错属性的新理论算法。我们很高兴看到 AMPC 模型已成为进一步研究的主题，同时了解到使用 AMPC 模型或其实际实现能够更高效地解决哪些其他问题。
进一步研究的主题
https://dl.acm.org/doi/10.1145/3350755.3400230
致谢
本文中所提到的两篇论文的共同作者包括 Soheil Behnezhad、Laxman Dhulipala、Hossein Esfandiari 和 Warren Schudy。另外，感谢 Graph Mining 团队的成员所给予的协助，特别感谢 Mohammad Hossein Bateni 对本文的贡献。如需详细了解我们近期对可扩展图算法的研究，请观看我们最近在 Graph Mining and Learning 研讨会中发布的视频。
更多 AI 相关阅读：