GraphDC：一种用于可扩展图算法推理的分治多智能体系统

# GraphDC: 用于可扩展图算法推理的分治多智能体系统

来源：https://arxiv.org/html/2605.06671
Jiaming Cui∗

###### 摘要

大型语言模型（LLMs）在许多数学问题上展现出了巨大的潜力。然而，它们在图算法任务上的表现仍不尽如人意，因为图在拓扑结构上天然更为复杂，且通常需要系统性的多步推理，尤其是在处理大规模图时。针对这一差距，我们提出了 GraphDC，这是一个用于可扩展图算法推理的分治（Divide-and-Conquer）多智能体框架。具体而言，受分治设计思想的启发，GraphDC 将输入图分解为较小的子图，将每个子图分配给专门的智能体进行局部推理，并利用主控智能体整合局部输出以及子图间的信息以生成最终解决方案。这种分层设计减轻了单个智能体的推理负担，缓解了计算瓶颈，并提高了在大规模图实例上的鲁棒性。广泛的实验表明，GraphDC 在多样任务和大小的图算法推理上一致优于现有方法，特别是在直接端到端推理可靠性较低的大规模实例上。

## 1 引言

图是表示实体间关系的基础数学概念 [26 (https://arxiv.org/html/2605.06671#bib.bib25), 14 (https://arxiv.org/html/2605.06671#bib.bib26), 1 (https://arxiv.org/html/2605.06671#bib.bib36), 9 (https://arxiv.org/html/2605.06671#bib.bib37), 8 (https://arxiv.org/html/2605.06671#bib.bib35)]。许多现实世界的问题，如传染病建模 [10 (https://arxiv.org/html/2605.06671#bib.bib38), 35 (https://arxiv.org/html/2605.06671#bib.bib39), 7 (https://arxiv.org/html/2605.06671#bib.bib40)]、供应链优化 [42 (https://arxiv.org/html/2605.06671#bib.bib43)] 和城市基础设施监控 [31 (https://arxiv.org/html/2605.06671#bib.bib42), 30 (https://arxiv.org/html/2605.06671#bib.bib41)]，都可以自然地建模为图，其目标是对实体间的结构依赖关系进行推理，而不是将实例独立对待。因此，图算法推理已成为众多领域的核心，包括社会网络分析 [3 (https://arxiv.org/html/2605.06671#bib.bib8), 18 (https://arxiv.org/html/2605.06671#bib.bib9)]、生物信息学 [44 (https://arxiv.org/html/2605.06671#bib.bib5)] 和知识图谱推理 [46 (https://arxiv.org/html/2605.06671#bib.bib10), 24 (https://arxiv.org/html/2605.06671#bib.bib11), 39 (https://arxiv.org/html/2605.06671#bib.bib12)]。多年来，人们提出了各种专用架构 [21 (https://arxiv.org/html/2605.06671#bib.bib27), 29 (https://arxiv.org/html/2605.06671#bib.bib28)] 来解决这些任务。虽然这些模型取得了良好的性能，但它们往往泛化能力和可用性有限 [43 (https://arxiv.org/html/2605.06671#bib.bib29), 41 (https://arxiv.org/html/2605.06671#bib.bib30)]：获得最先进的结果通常需要针对特定任务的设计，如定制化的预处理流程和解码器，这使得它们灵活性较低且难以适应。这限制了它们在任务定义、图特征或监督设置因数据集和应用而异时的适用性。

最近，大型语言模型（LLMs）在自然语言交互、可解释性以及跨多种数学任务的泛化能力方面展示了令人印象深刻的性能 [15 (https://arxiv.org/html/2605.06671#bib.bib13), 45 (https://arxiv.org/html/2605.06671#bib.bib14), 13 (https://arxiv.org/html/2605.06671#bib.bib15), 22 (https://arxiv.org/html/2605.06671#bib.bib16), 4 (https://arxiv.org/html/2605.06671#bib.bib17), 23 (https://arxiv.org/html/2605.06671#bib.bib34), 11 (https://arxiv.org/html/2605.06671#bib.bib33)]。这些特性使 LLMs 成为专用图模型的有吸引力的替代方案，因为它们为以最小的特定任务重新设计来解决不同的推理任务提供了统一接口。这激发了人们对其在图算法推理方面潜力的日益增长的兴趣。然而，单个 LLM 的推理能力本质上受到限制：随着图的大小和密度增加，LLM 在图算法推理任务上的准确率急剧下降。这种限制在算法推理中尤为明显，因为模型必须同时跟踪多跳依赖关系、保持结构一致性并执行多步逻辑操作。因此，直接将单个 LLM 应用于越来越大的图难以扩展。

参见图1说明：GraphDC 的框架。给定图上的数学问题，GraphDC 分两步解决。在“图-查询分解”步骤中，图分割器首先将图分解为若干子图。每个专用智能体然后根据问题描述器生成的子查询处理一个子图，并执行子图内算法推理。接下来，在“分层推理”步骤中，主控智能体聚合所有智能体的答案以及子图间信息，以回答原始问题。

为了减轻这种性能下降，人们探索了几种策略 [20 (https://arxiv.org/html/2605.06671#bib.bib18), 6 (https://arxiv.org/html/2605.06671#bib.bib19), 40 (https://arxiv.org/html/2605.06671#bib.bib20), 16 (https://arxiv.org/html/2605.06671#bib.bib21)]。例如，GITA [38 (https://arxiv.org/html/2605.06671#bib.bib3)] 通过图可视化增强提示，而 GraphAgent-Reasoner [17 (https://arxiv.org/html/2605.06671#bib.bib2)] 引入了一种多智能体系统，其中主控智能体协调一组较小的智能体。这些研究表明，为推理过程添加结构可以超越普通提示的性能。然而，现有方法仍面临巨大的可扩展性挑战。虽然后者在密集和复杂的图上实现了较高的准确率，但它需要为每个节点分配一个智能体，导致严重的可扩展性问题和平计算瓶颈。随着图规模的增大，这种协调成本迅速增长，使得该框架在处理大规模实例时成本高昂。同时，现实世界的图在规模和复杂性上持续增长，往往超过了单个 LLM 或简单协调的多智能体系统的有效推理能力。即使 LLM 不断改进，更大和更密集的图仍将继续带来新的可扩展性挑战。这提出了两个关键问题：(1) 如何对超出当前可扩展性限制的图进行有效推理，以及 (2) 如何在不产生 prohibitive 计算成本的情况下获得可靠的答案？

在这项工作中，我们重新审视数学的一个经典原则：分而治之，然后整合答案。受分布式图处理和分治范式 [28 (https://arxiv.org/html/2605.06671#bib.bib23), 19 (https://arxiv.org/html/2605.06671#bib.bib24)] 的启发，我们提出了 GraphDC，这是一种多智能体系统，它将节点划分为子图，为每个子图分配专用智能体，并采用主控智能体整合来自每个子图的输出以及子图间信息，以解决整体任务，从而实现可扩展的图算法推理。具体而言，我们首先将节点聚类为子图，并为每个子图分配一个智能体以进行子图内算法推理。然后，主控智能体聚合所有输出，结合子图间依赖关系，生成最终解决方案。与节点级智能体分配相比，这种设计减少了智能体数量和协调开销，同时保留了全局推理所需的结构信息。通过将每个智能体的范围限制在可管理的子图上，该框架提高了在复杂图实例上的可扩展性和推理可靠性。

我们通过广泛的实验验证了这一框架，证明了其在准确性和可扩展性方面的显著提升。我们的结果显示，GraphDC 一致优于强有力的基线方法，最大的改进出现在单智能体方法性能大幅下降的更大、更密集的图上。这些发现表明，子图级分解是扩展基于 LLM 的图算法推理的有效方法，并为处理超出当前单体方法范围的图实例提供了实用的方向。

我们的主要贡献总结如下：

- 据我们所知，我们是第一个提出用于可扩展图推理的分治多智能体系统（MAS）。我们的框架不是为每个节点分配一个智能体，而是将原始图分解为子图，使多个智能体能够协作解决大规模图推理问题。
- 为了支持这种分治 MAS，我们提出了一种针对下游推理任务的有效图分解算法。所提出的分解策略生成的子图更适合后续的智能体级推理，并促进了局部解决方案向全局答案的整合。
- 广泛的实验证明了我们要框架的有效性和可扩展性。结果表明，我们的方法在具有挑战性的图推理任务上取得了强大的性能，特别是在现有方法面临巨大困难的更大、更密集的图上。

本文的其余部分组织如下。第2节 (https://arxiv.org/html/2605.06671#S2) 回顾了相关工作。第3节 (https://arxiv.org/html/2605.06671#S3) 介绍了 GraphDC 框架，并描述了如何将其应用于图推理任务。第4节 (https://arxiv.org/html/2605.06671#S4) 评估了 GraphDC 的性能。最后，第5节 (https://arxiv.org/html/2605.06671#S5) 总结了论文并讨论了未来工作的方向。

## 2 相关工作

我们回顾了与我们工作最相关的三个研究方向：经典图算法、基于机器学习的图推理方法以及最近基于 LLM 的图推理方法。

### 2.1 经典图算法

经典图算法为图结构化数据的推理奠定了基础 [34 (https://arxiv.org/html/2605.06671#bib.bib46), 12 (https://arxiv.org/html/2605.06671#bib.bib49)]。大量工作研究了图上的连通性、最短路径、循环检测和关系推理等基础任务的精确且高效的算法 [32 (https://arxiv.org/html/2605.06671#bib.bib48), 33 (https://arxiv.org/html/2605.06671#bib.bib47), 25 (https://arxiv.org/html/2605.06671#bib.bib50)]。这些方法通常在计算上有坚实的基础，并且对于许多经典问题具有强大的理论保证。然而，它们通常是为具有明确定义的节点、边和目标的结构化图输入设计的，不太适合必须与丰富的上下文信息联合进行图推理的场景。在许多现代应用中，图实例伴随着异构的节点或边属性、文本描述、外部知识或自然语言查询 [26 (https://arxiv.org/html/2605.06671#bib.bib25), 14 (https://arxiv.org/html/2605.06671#bib.bib26), 44 (https://arxiv.org/html/2605.06671#bib.bib5)]。经典算法通常不提供将此类丰富数据纳入推理过程的原生机制。因此，虽然它们在定义明确的组合问题中仍然非常有效，但在需要结合图结构与非结构化或语义丰富信息的复杂图推理场景中灵活性较低。

### 2.2 基于机器学习的图推理

为了克服纯算法方法的僵化性，大量文献探索了将图与机器学习相结合的方法，特别是通过图神经网络、图变压器和其他图表示学习框架 [21 (https://arxiv.org/html/2605.06671#bib.bib27), 29 (https://arxiv.org/html/2605.06671#bib.bib28), 43 (https://arxiv.org/html/2605.06671#bib.bib29), 41 (https://arxiv.org/html/2605.06671#bib.bib30)]。这些方法可以编码图拓扑以及节点或边属性，并在包括社会网络、生物信息学和知识图谱在内的广泛应用中取得了强大的实证性能 [3 (https://arxiv.org/html/2605.06671#bib.bib8), 18 (https://arxiv.org/html/2605.06671#bib.bib9), 44 (https://arxiv.org/html/2605.06671#bib.bib5), 46 (https://arxiv.org/html/2605.06671#bib.bib10), 24 (https://arxiv.org/html/2605.06671#bib.bib11), 39 (https://arxiv.org/html/2605.06671#bib.bib12)]。与传统算法相比，它们能够更好地整合丰富数据并从监督中学习相关任务模式。然而，大多数这些方法在设计和训练上仍然是特定任务的。它们的成功往往依赖于精心选择的架构、采样策略、位置或结构编码、损失函数以及针对特定任务定制的下游解码器。此外，将它们应用于新的推理问题通常需要重新训练、重新设计或两者兼有。这限制了它们在寻求更通用的推理框架以在无大量特定任务工程的情况下跨图任务迁移的场景中的可用性。

### 2.3 基于 LLM 的图推理

最近，研究人员开始探索用于图推理的大型语言模型。这一系列工作受到 LLMs 在多种推理问题上强大的上下文学习、可解释性和任务泛化能力的驱动 [15 (https://arxiv.org/html/2605.06671#bib.bib13), 45 (https://arxiv.org/html/2605.06671#bib.bib14), 13 (https://arxiv.org/html/2605.06671#bib.bib15), 22 (https://arxiv.org/html/2605.06671#bib.bib16), 4 (https://arxiv.org/html/2605.06671#bib.bib17), 23 (https://arxiv.org/html/2605.06671#bib.bib34), 11 (https://arxiv.org/html/2605.06671#bib.bib33)]。现有的努力包括将图序列化为文本的基于提示的方法、通过视觉表示（如 GITA [38 (https://arxiv.org/html/2605.06671#bib.bib3)]）增强图推理的多模态方法，以及将推理分布在智能体之间的多智能体框架 [17 (https://arxiv.org/html/2605.06671#bib.bib2)]。与经典图算法和学习到的图编码器相比，这些方法为推理图问题提供了更统一的接口，无需特定任务的训练。然而，可扩展性仍然是一个主要瓶颈。对于单智能体 LLM 方法，随着图大小和密度的增加，推理质量迅速下降，因为模型必须在有限的上下文和推理预算内跟踪更多的结构依赖关系和更长的推理链。多智能体方法部分缓解了这一问题，但现有设计仍可能产生巨大的协调开销；例如，为每个节点分配一个智能体计算成本高昂，在大规模图上变得不切实际 [17 (https://arxiv.org/html/2605.06671#bib.bib2)]。相比之下，我们的工作专注于通过子图级分治进行可扩展的图算法推理，这减少了协调成本，同时保留了最终推理所需的全局信息。

## 3 提出的方法

为了克服第1节 (https://arxiv.org/html/2605.06671#S1) 和第2节 (https://arxiv.org/html/2605.06671#S2) 中讨论的局限性，并更好地利用 LLMs 进行图推理的能力，我们提出了一种新的多智能体协作框架 GraphDC，如图1 (https://arxiv.org/html/2605.06671#S1.F1) 所示。整体设计遵循一种简单但有效的直觉：与其强迫单个