GraphDC is a multi-agent framework for graph algorithm reasoning that uses divide-and-conquer: it splits the input graph into smaller subgraphs, assigns each to a specialized agent for local reasoning, and uses a master agent to integrate local outputs with inter-subgraph information to produce the final answer. This hierarchical design reduces the reasoning burden on individual agents and improves scalability and robustness on large graphs. Experiments show GraphDC consistently outperforms existing methods on diverse graph algorithm tasks, especially on larger instances where direct end-to-end reasoning fails.
Main takeaways:
- GraphDC decomposes graphs into subgraphs, assigns local reasoning to specialized agents, and integrates results via a master agent.
- Inspired by divide-and-conquer algorithms; reduces per-agent reasoning burden and alleviates computational bottlenecks.
- Consistently beats existing methods on graph algorithm reasoning across tasks and scales.
- Especially strong on large graph instances where end-to-end reasoning is unreliable.
- Demonstrates that hierarchical multi-agent design improves robustness and scalability for complex structured reasoning.