Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents

## Abstract

Abstract Recent research has explored the use of Large Language Models (LLMs) for tackling complex graph reasoning tasks. However, due to the intricacies of graph structures and the inherent limitations of LLMs in handling long text, current approaches often fail to deliver satisfactory accuracy, even on small-scale graphs and simple tasks. To address these challenges, we introduce GraphAgent-Reasoner, a fine-tuning-free framework that utilizes a multi-agent collaboration strategy for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. The agents collaborate to solve the overall problem, significantly reducing the amount of information and complexity handled by a single LLM, thus enhancing the accuracy of graph reasoning. By simply increasing the number of agents, GraphAgent-Reasoner can efficiently scale to accommodate larger graphs with over 1,000 nodes. Evaluated on the GraphInstruct dataset, our framework demonstrates near-perfect accuracy on polynomial-time graph reasoning tasks, significantly outperforming the best available models, both closed-source and fine-tuned open-source variants. Our framework also demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.

## 1 Introduction

Graphs, as a crucial data structure for modeling complex real-world relationships, are ubiquitous across various scenarios, e.g. citation networks, recommendation networks. Many important applications like drug discovery (Stokes et al., ), traffic forecasting (Jiang & Luo, ), and financial detection (Motie & Raahemi, ), require reasoning over graphs to be realized.
Noticing the powerful general knowledge and language processing capabilities of Large Language Models (LLMs) (Brown et al., ), a significant amount of works have focused on using LLMs to perform various reasoning tasks, such as mathematical formula derivation (Meadows et al., ), commonsense reasoning (Madaan et al., ), and multi-hop question answering (Creswell et al., ). However, most of them primarily involve shallow or sequential reasoning. To bring the LLM reasoning closer to human thinking, it is necessary for LLMs to master deeper and more complex reasoning, such as graph reasoning.

Despite significant efforts by researchers to enable LLMs to memorize, comprehend, and perform basic reasoning on graph structures, several issues still persist: 1) The scale of graphs that can be handled is limited.
Describing graph structures in natural language inevitably leads to excessively long inputs.
Due to context length limitations and the shortcomings of LLMs in handling lengthy text (Liu et al., ), previous works (Chai et al., ; Fatemi et al., ; Perozzi et al., ) could only handle graphs of very limited size (e.g. fewer than 20 nodes and 100 edges).
2) The performance on graph reasoning tasks is relatively poor. Unlike text, which can tolerate some degree of semantic deviation, reasoning and computation on graphs must be highly precise. However, current works demonstrate poor accuracy (average 20$\sim$60%) in various graph reasoning tasks like connectivity and shortest path.
3) Lacking explicit reasoning paths. Taking the shortest path as an example, the responses of existing models resemble a heuristic search approach to finding the shortest path on a graph, rather than strictly executing an algorithm. This makes it difficult to determine whether LLMs are genuinely deriving the answer through correct reasoning or merely making educated guesses.
Although GraphWiz (Chen et al., ) attempts to generate explicit reasoning paths through fine-tuning, it often fails due to the presence of incomplete or wrong reasoning paths in its training data.
Furthermore, GraphWiz exhibits overfitting, where it tends to treat new or unrelated questions as one of the fine-tuned problems, which will be detailed in Section 5.3.

Motivation. The ultimate goal of graph reasoning is to enable LLMs to leverage graph-related knowledge or algorithms to solve real-world graph problems. However, with the development of information science and hardware storage, the scale of graphs and information per node become too large for a single LLM to handle. To address this, a natural idea is to use distributed approaches, where a large graph is stored across multiple LLMs separately and compute collaboratively. Therefore, just as graph algorithms have generally evolved from non-distributed to distributed forms (Meng et al., )), we hope that LLMs can also learn the concept of distributed processing, thereby harnessing the power of swarm intelligence to solve graph problems in real-world scenarios.

Figure: Figure 1: The current situation of LLMs in solving graph problems. Previous methods using a single LLM often failed due to the complex graph structures. In contrast, our approach leverages agents collaboration to effectively address graph problems.
Refer to caption: x1.png

Our Contribution. To address the above limitations, in this paper, we propose the GraphAgent-Reasoner(GAR) framework, which leverages the power of swarm intelligence to solve graph reasoning problems, as shown in Figure 1. We follow a node-centric approach, assigning an agent to each node, allowing it to focus on processing its own information and communicate with neighbors.
Thus, we can easily scale up the size of graphs that can be processed by simply increasing the number of agents.
At the same time, under the direction of a Master LLM, graph problems are decomposed into smaller, node-centric tasks, which are assigned to agents for collaborative resolution.
This approach significantly reduces the scale and complexity of information each agent needs to process, thereby greatly improving the overall accuracy.
Furthermore, since agents must clearly transmit the processed information to neighboring agents, the reasoning process becomes transparent, demonstrating the framework solves graph reasoning problems through clear and correct reasoning, rather than lucky guessing. In summary, our contributions are as follows:

- •
We propose GraphAgent-Reasoner, the first LLM-based multi-agents framework for graph reasoning, which requires no fine-tuning and can utilize any LLM as the underlying reasoning model. Our framework achieves near-perfect accuracy on various polynomial-time tasks, significantly surpassing the performance of existing methods.
- •
Our framework expands the scale of graph reasoning tasks handled by LLMs from 100 nodes to 1,000 nodes, demonstrating exceptional scalability. Furthermore, as the graph size increases, our framework does not exhibit the significant performance degradation seen in other methods and maintains robust accuracy.
- •
We explore the performance of our framework in real-world applications like webpage importance analysis, showcasing its potential for addressing complex graph reasoning problems in real-life situations.

## 2 Preliminaries and Related Works

Preliminaries. In general scenarios, when discussing LLMs solving graph reasoning problems, the input is a ($\mathcal{G}$,$\mathcal{Q}$) pair. $\mathcal{G}$ is a graph represented as $\mathcal{G}=(\mathcal{V},\mathcal{E},\{s_{i}\},\{t_{i}\})$, where $\mathcal{V}$ is the node set and $\mathcal{E}$, the edge set. For each node $v_{i}\in\mathcal{V}$, a sequential text node feature $s_{i}$ is associated; similarly, for each edge $e_{i}\in\mathcal{E}$, a sequential text edge feature $t_{i}$ is assigned. The graph $\mathcal{G}$ is described in natural language, typically using edge or adjacency list representation. $\mathcal{Q}$ is a task-specific instruction or problem description. LLMs will process the ($\mathcal{G}$,$\mathcal{Q}$) pair and return an answer string $A$.

Large Language Models for Graph Reasoning.
To further enhance the reasoning capabilities of LLMs, many works have attempted to improve the performance of LLMs in graph reasoning. Wang et al. () first introduces the NLGraph Benchmark to evaluate the performance of LLMs on various graph reasoning tasks. Fatemi et al. () explores the impact of different graph encoding methods and graph structure types on the performance of LLMs in graph reasoning tasks. Additionally, it introduces another benchmark called GraphQA. Considering the lengthy nature of describing graph structures in text, Chai et al. () and Perozzi et al. () respectively use Transformers and GNNs to encode graph structures and attempt to align them with LLMs. Inspired by how humans understand structural information through the visual modality, Wei et al. () generates corresponding visual images based on graph structures and provides them to visual LLMs for graph reasoning. Chen et al. () conducted Supervised Fine-Tuning and Directly Prefered Optimization on LLMs, enhancing the performance of LLMs and encouraging them to output explicit reasoning paths.

Large Language Model based Multi-Agents.
Recent advancements in LLMs have spurred interest in their application within multi-agent systems. LLM-based multi-agent frameworks leverage the natural language understanding and reasoning capabilities of LLMs to enable agents to collaborate, communicate, and solve complex tasks in a distributed manner. Existing multi-agents works for problem solving primarily focuses on applications such as Software Development (Dong et al., ; Hong et al., ; Qian et al., ), Embodied Agents (Zhang et al., ; Mandi et al., ; Chen et al., ) and Science Debate (Xiong et al., ; Chan et al., ). However, using LLM-based multi-agents to handle graph data has been less explored, especially in the areas of graph reasoning and graph computation tasks. This may be due to the hallucination issue inherent in LLMs (Huang et al., ), where their responses are factually incorrect. This problem becomes more complex in a multi-agent setting, as the hallucinations of a single agent may propagate to other nodes by communication (Guo et al., ). This requires the performance of individual agents be sufficiently stable to ensure the correct operation of the entire multi-agent system.

## 3 Limitations of Single LLM in Graph Reasoning

Although LLMs exhibit strong language processing and logical reasoning capabilities, problems with the Transformer architecture and Attention mechanism (Vaswani et al., ) still limit the scale and accuracy when they process graph problems. There are two primary limitations:

Figure: Figure 2: The performance of a single LLM in memorizing first-order neighboring nodes. As the number of nodes increases, all models exhibit significant memory errors.
Refer to caption: x2.png

The graph structure is too complex to memorize and understand for a single LLM.
Using adjacency or edge lists to describe graph structures in natural language is the most intuitive and direct method, facilitating the processing of graph data by LLMs through text. However, this approach inevitably leads to a lengthy context, as the number of edges can grow quadratically with the number of nodes.
As the graph scales up and becomes denser, the graph structure becomes highly complex, requiring a large amount of tokens to describe the edge relationships. When the text becomes too lengthy, it becomes difficult for LLMs to properly allocate attention, and they may even struggle with simple tasks such as key-value pair matching Liu et al. (). This presents significant challenges for LLMs in identifying key information for graph reasoning tasks from the lengthy context. Figure 2 shows the performance of a single LLM in memorizing one-hop neighbor nodes. We observe that as the number of nodes in the graph increases, various LLMs exhibit a significant decline in accuracy.
If a single LLM cannot even correctly recall basic graph structural information like node neighbors, it becomes difficult to proceed with more complex graph reasoning or computation.

Furthermore, the graph structure is described in a sequential manner.
LLMs have to identify implicit graph structures from sequential text. Since the processing of LLMs is a black-box operation, it is difficult to assert that they truly construct graph structures implicitly and thereby understand them. Huang et al. () conducted extensive experiments to explore whether LLMs treat the input prompts as graphs or merely as paragraphs with keywords on TAGs. The results show that the performance of LLMs in handling TAGs primarily stems from the context rather than the graph structure. LLMs tend to process the graph description as linearized paragraphs rather than graphs.

A single LLM struggles to solve reasoning problems in real-world scenarios.
Researchers train LLMs on graph reasoning tasks to empower them to utilize learned graph-related knowledge or algorithms to tackle real-world graph problems. However, in practical scenarios, the amount of information associated with each node can be enormous. Take citation networks as an example: a single node represents a paper, and its node information includes the title, abstract, and references, which could amount to several thousand tokens. In addition to the complexity of graph structures, the need to handle a large amount of node information further exacerbates the burden on a single LLM and highlights its shortcomings in processing long contexts. Moreover, using a single LLM to handle the entire network is inefficient, as it cannot coherently process the entire network’s problems. Typically, it is necessary to manually compress or summarize the information for each node and then feed local subgraphs to the LLM for processing (Guo et al., ; Chen et al., ).

Furthermore, many current works (Chen et al., ; Perozzi et al., ) require training GNNs or fine-tuning LLMs on individual or multiple graph reasoning tasks. However, when transferring to other graph tasks, a certain degree of performance degradation occurs, and retraining or fine-tuning for new graph tasks consumes a significant amount of time and resources. Whether LLMs can apply the graph knowledge and algorithms learned during the training process to actual graph reasoning also remains an open question. We explored this question in 5.3 and observed significant overfitting in LLMs fine-tuned on specific graph reasoning tasks. Therefore, the ideal solution would be to leverage the powerful general knowledge acquired during the pre-training phase of LLMs through an appropriate approach, enabling them to handle graph reasoning tasks as naturally as they do with natural language problems.

## 4 GraphAgent-Reasoner

To solve the limitations above, we propose a novel framework based on multi-agent collaboration called GraphAgent-Reasoner as shown in Figure 3, aiming to solve graph reasoning problems explicitly and correctly.
The interface of the framework is a Master LLM, which is responsible for processing the textual input of graph problems, constructing the agent network, directing them to collaboratively solve the problem, and finally aggregating the states of all agents to derive the solution.
Its implementation is based on the React Agent proposed by Yao et al. (), which is capable of reasoning based on the environment and executing corresponding actions, as detailed later.
The pipeline of GAR consists of four steps: Graph Construction, Algorithm Establishing, Distributed Execution and Master Summarization.

Figure: Figure 3: The framework of GraphAgent-Reasoner. Given a graph problem, the Master LLM will first construct agents network according to graph strcutures. It then sequentially performs Algorithm Establishing, Distributed Execution and Master Summarization, as detailed in this section.
Refer to caption: x3.png

Graph Construction.
Given an input pair ($\mathcal{G}$, $\mathcal{Q}$), the Master LLM first extracts the node and edge information from the textual description of graph $\mathcal{G}$.
It then constructs an agent for each node and initializes the node’s state and neighbor information, forming an interconnected network of agents.
Each agent independently maintains its state and neighbor data, communicates with adjacent agents based on instructions from the Master LLM, and updates its state in each round.

Algorithm Establishing.
To accommodate diverse graph tasks and fully exploit the knowledge embedded in LLMs during pre-training, we propose a unified solution approach framed within a distributed paradigm as shown in Algorithm 1.
This approach requires the Master LLM to specify six core components for each problem: State, Message, Initialization, Send, Update, and Termination.

- •
State: The local information maintained by each node, representing its current state. This can include attributes like node features, labels, or any other task-specific data. The states evolve as nodes receive messages and update their information.
- •
Message: The data transmitted between nodes during the communication phase. Messages typically contain information that neighboring nodes need to perform updates, such as feature values, distances, or other task-relevant information.
- •
Initialization: At the start of the execution, each node initializes its state with predefined values, which may be based on node IDs, input features or task-specific requirements. This step ensures that the graph is ready to begin the communication process.
- •
Send: After initialization, each node generates messages based on its current state and sends them to its neighboring nodes. This step is repeated in each iteration, allowing nodes to continuously exchange information with their neighbors.
- •
Update: Upon receiving messages from its neighbors, each node updates its state by aggregating the incoming messages and combining them with its current state. This iterative process enables nodes to refine their information over time.
- •
Termination: The algorithm halts when a predefined stopping condition is met, such as reaching a fixed number of iterations, achieving convergence, or satisfying a task-specific criterion. Once the termination condition is reached, each node will send its final state to the Master LLM, and the execution terminates.

Figure: Algorithm 1 Distributed Paradigm

Since LLMs lack prior knowledge of this distributed paradigm, to facilitate the Master LLM’s understanding and application of the framework, we develop a distributed algorithm library that adheres to this distributed paradigm, from which the Master LLM can query relevant algorithm templates to generate distributed solutions within this paradigm. Specifically, we selected classic distributed graph algorithms and documented their implementations under this distributed paradigm. Some examples are presented in Appendix A.1. Drawing on prior work (Zheng et al., ; Meng et al., ), we endeavor to write detailed reasoning steps of each part in the algorithm to encourage the agent to think step by step as much as possible, which plays an important role in enhancing the success rate of individual agents.

When receiving a problem input, the Master LLM first retrieves the $k$ algorithms most relevant to the problem description from the distributed algorithm library. If there are algorithms suitable for handling the problem, the Master LLM will adjust the algorithm according to the problem description, such as changing the initialization and termination conditions (e.g., the source node in the shortest path problem). If there are no appropriate algorithms, the Master LLM will design a distributed algorithm following the distributed paradigm based on the examples of the retrieved algorithms. For some generated examples, see Appendix A.2.

Distributed Execution. After the distributed algorithm is designed, the Master LLM will relay the approach to each agent node for execution according to the process outlined in Algorithm 1. Each agent will first initialize its state based on node information and algorithm rules and then send an initial message to neighboring agents. Subsequently, each agent will iteratively execute the operations of receiving messages, updating its state, and sending messages according to the algorithm rules, synchronizing progress after each communication round.
Communication will continue until the maximum number of iterations is reached or the termination condition is met.

Master Summarization. Finally, the final state of all agent nodes will be aggregated to the Master LLM, which will summarize the results conclude based on the problem and return the final answer in natural language form.

## 5 Experiments

In this section, we summarize the key experiments conducted with GAR. We begin by highlighting some of the most exciting results from our analysis here:

- •
R1: GAR achieves near-perfect accuracy on polynomial-time graph reasoning problems, significantly surpassing existing closed-source models and open-source models fine-tuned on extensive data.
- •
R2: GAR maintains high accuracy on larger-scale graphs (up to 1000 nodes), demonstrating superior scalability.
In contrast, as the number of nodes increases, other models exhibit a significant decline in performance or become incapable of handling the problem at all due to the context length limitation.
- •
R3: GAR showcases a robust understanding and application of graph algorithms in real-world graph reasoning scenarios, highlighting its potential for addressing complex graph problems encountered in daily life. In contrast, other open-source models that have undergone extensive fine-tuning on graph reasoning datasets fail to apply the learned graph reasoning knowledge when confronted with rephrased real-world graph problems.

Datasets. We conduct our experiments on the graph reasoning tasks proposed in GraphInstruct (Chen et al., ). This dataset contains nine graph reasoning problems with different time complexity, ranging from linear and polynomial complexity to NP-complete.

- •
Linear. Cycle Detection (Detect if a given graph $\mathcal{G}$ contains any cycles), Connectivity (Assess if two nodes $u$ and $v$ in a given graph $\mathcal{G}$ are connected via a path), Bipartite Graph Check (Judge if a given graph $\mathcal{G}$ is bipartite), and Topological Sort (Find a topological ordering of vertices in a directed acyclic graph $\mathcal{G}$).
- •
Polynomial. Shortest Path (Compute the shortest path between two specific nodes $u$ and $v$ in a given graph $\mathcal{G}$), Maximum Triangle Sum (Find the maximum sum of weights for any connected triplet of vertices in a given graph $\mathcal{G}$), and Maximum Flow (Calculate the maximum flow from a source node $s$ to a sink node $t$ in a directed graph $\mathcal{G}$).

Due to the complexity of NP-complete problems, there are currently no mature exact distributed algorithms available for their solution. Consequently, the Master LLM is unable to design correct and effective distributed algorithms based on the knowledge acquired during pre-training. Therefore, in our experiments, we only consider linear and polynomial-time problems. Detailed information of the dataset and partial test results for NP-complete problems will be presented in Appendix B.

Setting. The underlying reasoning LLM of Agent Node used in our framework is ChatGPT-4o-mini-2024-07-18, and the base model of Master LLM is ChatGPT-4-turbo(OpenAI, ). The temperature is consistently set to 0. Our framwork is built upon AgentScope (Gao et al. ()), an innovative platform to easily build reliable, high-performance multi-agent applications.

### 5.1 Experiment 1: Performance on GraphInstruct

In this experiment, we evaluate the performance of GAR on polynomial-time tasks of the GraphInstruct dataset. The results are shown in Table 1.
We see GAR exhibits near-perfect results on these tasks, significantly outperforming other models. Especially on shortest and triangle tasks with high time complexity, GAR substantially improves the performance of LLMs. Problems that a single LLM struggles to solve have been effectively resolved through collaboration by agents after being decomposed into smaller, node-centric tasks.

As the number of nodes increases, the graph structures become more complex, making the solution of graph problems increasingly difficult. To investigate how the performance of models varies with increasing problem complexity, we conduct experiments on cycle detection and shortest path problems, gradually increasing the number of nodes from 5 to 100. The results are presented in Figure 4.

Figure: (a) Cycle Detection
Refer to caption: x4.png

We see with the number of nodes increasing, both ChatGPT-4 and Graphwiz exhibit a significant decline in performance. However, the accuracy of GAR remains stable, almost unaffected by the graph size, demonstrating robust scalability. Although the scale of the graph is increasing, the information processed by each agent has not significantly increased. Each agent still only handles its own information and communicates with neighboring agents. We observe that GAR occasionally makes errors in specific cases, likely due to the increasing communication rounds as the number of nodes and edges grows. Even when handling simple node-centric tasks, a single agent still has the potential to make mistakes.
Therefore, as the number of agents and communication rounds increases, the overall likelihood of errors also rises. This can be improved by enhancing the capability of individual agents (such as using stronger LLMs as the underlying reasoning model) or by more finely designed prompts.

**Table 1: Performance of GraphAgent-Reasoner and other models on polynomial-time tasks of GraphInstruct test set. Each task contains 400 test cases, with a maximum of 100 nodes. The first best result for each task is highlighted in bold, and the second best result is highlighted underlined.**
| Models | Linear | Polynomial | Average |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| cycle | connect | bipartite | topology | shortest | triangle |  |  |
| Closed-source Models |  |  |  |  |  |  |  |
| GPT-4 (zero-shot) | 38.75 | 17.00 | 65.25 | 5.00 | 9.25 | 5.75 | 23.50 |
| GhatGPT (2-shot) | 51.25 | 43.75 | 70.75 | 4.50 | 3.50 | 17.25 | 31.83 |
| GPT-4 (2-shot) | 52.50 | 62.75 | 74.25 | 25.25 | 18.25 | 31.00 | 44.00 |
| Fine-tuned Open-source Models |  |  |  |  |  |  |  |
| Naive SFT (LLaMA 2-7B) | 73.75 | 83.50 | 41.25 | 4.00 | 9.50 | 30.00 | 40.17 |
| Naive SFT (Mistral-7B) | 73.75 | 83.50 | 78.50 | 1.00 | 23.00 | 47.00 | 51.13 |
| GraphWiz (LLaMA 2-7B) | 91.50 | 87.00 | 74.00 | 18.00 | 28.00 | 38.25 | 56.13 |
| GraphWiz (Mistral-7B) | 92.00 | 89.50 | 72.00 | 19.00 | 31.25 | 38.75 | 57.08 |
| GraphWiz-DPO (LLaMA 2-7B) | 89.00 | 82.50 | 84.75 | 46.75 | 24.00 | 52.75 | 63.29 |
| GraphWiz-DPO (Mistral-7B) | 85.50 | 79.50 | 85.50 | 85.25 | 12.50 | 29.00 | 62.88 |
| GraphAgent-Reasoner | 99.50 | 100.00 | 100.00 | 96.50 | 99.75 | 93.25 | 98.00 |

### 5.2 Experiment 2: Performance on Large-Scale
Graphs

In this experiment, we evaluate the performance of current LLMs on large-scale graphs. The largest graph size handled by existing graph reasoning work is 100 nodes (Chen et al., ), which is still far from sufficient for real-world graph reasoning scenarios. To evaluate the reasoning performance of existing models on larger graphs, we conduct shortest path experiments on graphs with 100, 200, 500, and 1000 nodes. Due to the excessively long input text (reaching 16,000 tokens for 1000 nodes) and the money cost, we only create 20 test samples for each graph size. The results are shown in Table 2.

**Table 2: Performance on large-scale graphs dealing with shortest path problems. x/20 indicates that out of 20 test samples, x samples are correct. NA signifies that testing could not be conducted due to the fact that the context length limit is exceeded.**
| Graph Size | 100 | 200 | 500 | 1000 |
| --- | --- | --- | --- | --- |
| Graphwiz (LLaMA 2-7B) | 0/20 | 0/20 | NA | NA |
| Graphwiz (LLaMA 2-7B-DPO) | 0/20 | 0/20 | NA | NA |
| Chatgpt-3.5-turbo-16k | 0/20 | 0/20 | 0/20 | 0/20 |
| Chatgpt-4-32k | 0/20 | 1/20 | 0/20 | 0/20 |
| GraphAgent-Reasoner | 20/20 | 20/20 | 20/20 | 18/20 |

We see the two GraphWiz models fine-tuned on the LLaMA2-7B (Touvron et al., ) base model are unable to handle graphs with 500 or more nodes due to the context length limitation (the context length limit for Llama2 is 4096 tokens). Although ChatGPT-3.5-turbo-16k and ChatGPT-4-32k can manage longer contexts, they output wrong answers in almost all test samples, with only ChatGPT-4-32k being correct in one 200 nodes test sample. In contrast, GAR maintains a high accuracy in large-scale graph, only failed in two 1000-node test samples, further demonstrating its robust scalability.

### 5.3 Experiment 3: Case Study

In this experiment, we explore the application of two graph reasoning models, Graphwiz and GAR, in real-world graph reasoning scenarios. We present a case study of webpage importance analysis in Figure 5.

Figure: Figure 5: The importance analysis in webpage network. While the GraphWiz fails due to incorrect graph assessments, GAR correctly uses the PageRank algorithm to identify nodes 16, 14, and 5 as the most important.
Refer to caption: x6.png

Although GraphWiz performed well on fine-tuned tasks, it exhibits severe overfitting when faced with real-world graph problems, failing to apply the graph reasoning knowledge learned during the fine-tuning phase.
Since GraphWiz uses a consistent graph node description, the sentence "The nodes are numbered from 0 to …" appears across all datasets during the mixed-task instruction tuning.
When the actual problem has nodes numbered from 1 to 20, it still assumes the existence of node 0. As a result, both GraphWiz models first output that the graph has 21 nodes and an incorrect number of edges.
Furthermore, neither of the two GraphWiz models recognizes that this is a problem associated with web page importance ranking.
Instead, they approach it as the bipartite graph check or topological sort problems they had been fine-tuned on. Additionally, neither model generates an explicit and correct reasoning path.
These observations indicate that there is still a significant gap between excelling in classic graph reasoning tasks and effectively solving real-world graph reasoning problems. In contrast, GAR correctly identifies that the problem should be solved using knowledge related to PageRank (Yang et al., ) and designs an algorithm that adhered to the distributed paradigm (Note: the distributed algorithm library does not contain a PageRank algorithm template).
GAR then assigns the algorithm to agent nodes for execution, ultimately obtaining the PageRank value for each node and arriving at the correct conclusion.
Through the distributed paradigm, GAR effectively bridges the powerful knowledge learned by LLMs with the solving of real-world graph reasoning problems, which enables it to flexibly handle practical issues in a distributed manner.
This case study demonstrates the feasibility of using GAR to solve real-world graph reasoning problems, indicating its substantial practical applicability and offering researchers and practitioners a powerful framework to address such tasks.

## 6 Conclusion

We first summarize three key issues faced by existing LLMs in graph reasoning tasks: limited graph scale, poor performance, and the lack of explicit reasoning paths. We then reflect on the limitations of a single LLM in addressing graph reasoning problems, such as the graph structures being too complex to memorize and understand and the overwhelming information in real-world graph reasoning scenarios. To address these challenges, we propose GraphAgent-Reasoner, a framework based on multi-agent collaboration to solve graph reasoning problems. This framework demonstrates superior accuracy and scalability, significantly surpassing existing closed-source and fine-tuned open-source models. Our experiments show its robust scalability, maintaining high accuracy on large graphs (up to 1,000 nodes). Our case study on webpage importance analysis further illustrates its capability to handle real-world graph reasoning problems. Future work will focus on designing more accurate and scalable LLM-based multi-agent graph reasoning frameworks, aiming to apply them to larger and more complex real-world reasoning scenarios.

## Appendix A Distributed algorithms under the distributed paradigm

### A.1 Example of distributed algorithms in distributed algorithm library

Shortest Path: See Figure 6.

Connectivity: See Figure 7.

Figure: Figure 6: Distributed algorithm for shortest path problem under the distributed paradigm.
Refer to caption: x7.png

Figure: Figure 7: Distributed algorithm for connectivity problem under the distributed paradigm.
Refer to caption: x8.png

### A.2 Example of distributed algorithms designed by the Master LLM

PageRank: See Figure 8.

Hamilton Path: See Figure 9.

Subgraph Matching: See Figure 10.

Figure: Figure 8: Distributed algorithm for pagerank calculation under the distributed paradigm.
Refer to caption: x9.png

Figure: Figure 9: Distributed algorithm for hamilton path problem under the distributed paradigm.
Refer to caption: x10.png

Figure: Figure 10: Distributed algorithm for subgraph matching problem under the distributed paradigm.
Refer to caption: x11.png

## Appendix B The GraphInstruct Dataset

The statistics and detailed information of GraphInstruct are shown in Table 3. Hamilton Path and Subgraph Matching are NP-complete problems.

**Table 3: The detailed information of GraphInstruct dataset.**
| Problem | Definition | Node Range | Test Size |
| --- | --- | --- | --- |
| Cycle Detection | Detect if a given graph $\mathcal{G}$ contains any cycles. | [2, 100] | 400 |
| Connectivity | Assess if two nodes $u$ and $v$ in a given graph $\mathcal{G}$ are connected via a path. | [2, 100] | 400 |
| Bipartite Graph Check | Judge if a given graph $\mathcal{G}$ is bipartite. | [2, 100] | 400 |
| Topological Sort | Find a topological ordering of vertices in a directed acyclic graph $\mathcal{G}$. | [2, 50] | 400 |
| Shortest Path | Compute the shortest path between two specific nodes $u$ and $v$ in a given graph $\mathcal{G}$. | [2, 100] | 400 |
| Maximum Triangle Sum | Find the maximum sum of weights for any connected triplet of vertices in a given graph $\mathcal{G}$. | [2, 25] | 400 |
| Maximum Flow | Calculate the maximum flow from a source node $s$ to a sink node $t$ in a directed graph $\mathcal{G}$. | [2, 50] | 400 |
| Hamilton Path | Determine if a given graph $\mathcal{G}$ has a Hamiltonian path that visits each vertex exactly once. | [2, 50] | 400 |
| Subgraph Matching | Verify if there exists a subgraph in $\mathcal{G}$ that is isomorphic to a given graph $\mathcal{G}^{\prime}$. | [2, 30] | 400 |

Hamilton Path Execution Example.

Problem Description:

Determine whether or not there is a Hamiltonian path in an undirected graph. In an undirected graph, (i,j) means that node i and node j are connected with an undirected edge. Given a graph, you need to output Yes or No, indicating whether there is a Hamiltonian path in the graph. Q: The nodes are numbered from 0 to 5, and the edges are: (0, 3) (0, 1) (0, 2) (0, 4) (1, 5) (1, 4) (1, 2) (1, 3) (2, 4) (2, 5) (3, 5) (3, 4). Is there a Hamiltonian path in this graph?

Execution Process:

## Appendix C Execution examples of GraphAgent-Reasoner

Shortest Path Execution Example.

Problem Description:

Find the shortest distance from a source node to other nodes in an undirected graph. In an undirected graph, (i,j,k) means that node i and node j are connected with an undirected edge with weight k. The graph has 8 nodes, and the edges are: (0,7,9) (0,1,7) (0,4,9) (1,7,1) (2,7,7) (2,6,5) (2,5,8) (3,5,9) (3,4,8) (3,6,1) (4,7,7) (4,5,6) (5,7,6). Give the weight of the shortest distance from node 1 to other node.

Execution Process:

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: Please see the above weaknesses
soundness: 3
strengths: 1. The paper is well-written and easy to follow.

2. This paper identifies a critical issue that larger graph size leads to performance drop in graph reasoning task.

3. The proposed framework achieves promising results compared to baselines, especially in larger graphs.
summary: The paper presents GraphAgent-Reasoner (GAR), a scalable and accurate framework for graph reasoning that leverages Large Language Models (LLMs) through a multi-agent collaboration strategy. By decomposing complex graph problems into node-centric tasks assigned to individual agents, GAR reduces the processing load on a single LLM, enabling the system to scale efficiently to graphs with over 1,000 nodes without a loss in accuracy. Unlike previous methods limited by LLMs' handling of long inputs, GAR achieves near-perfect accuracy on polynomial-time tasks, significantly outperforming existing models
weaknesses: 1. Though the performance in large-scale graph reasoning tasks is promising, the overall novelty of this framework is limited. Multi-agent systems have been proposed in many other domains, and this work seems to simply adopt the idea for the graph reasoning task without a specific design tailored to it.

2. The implementation details for Experiment 2 are unclear. How is the dataset constructed, and what do the 20 samples look like? I would suggest that the authors add more details to improve the soundness of the experiments.

3. The experiments are not comprehensive. Although all experiment results look favorable according to the paper, I am wondering about the performance limits of this framework. At what graph size does the performance begin to drop? 

4. Though the authors claim that they aim to address the challenges of large graphs, I still believe this issue is not well-addressed. The largest graph size in this paper is 1,000, yet many real-world applications involve graphs much larger than 1,000 nodes. How can this framework be adapted to such scenarios? Especially, how could we optimize efficiency to handle these larger graphs? It seems that the computational cost is very large by modeling each node as an agent, which makes it not scalable to really large graphs. What is the computational cost?

5. Many important details are missing, such as how the messages are prepared and sent and how each agent updates their state. Though the authors provide some examples in the appendix, the paper lacks a description of the principled design of these important components in the main content.

6.	The proposed GAR is given some distributional algorithms for solving graph problems. For a fair comparison, the baselines should also be given a list of graph algorithms, such as algorithms for finding the shortest path, to solve the given tasks. Could you please clarify if these baselines are given such algorithms?

---

confidence: 5
contribution: 4
initial_rating: 5
presentation: 4
questions: 1. In lines 301-302, it states, "Communication will continue until the maximum number of iterations is reached or the termination condition is met." Could the authors clarify the specific criteria for the termination condition?
2. Could the authors verify the performance of GAR in more complex graph reasoning tasks from GraphInstruct, such as Hamilton Path and Subgraph Matching, to provide a more comprehensive evaluation of its accuracy and scalability?
3. The paper seems to underutilize the reasoning and generative capabilities of LLMs, which could potentially improve GAR’s interpretability and effectiveness in graph reasoning tasks. Could the authors clarify this?
soundness: 3
strengths: 1. This paper introduces a fine-tuning-free approach based on multi-agent collaboration to decompose complex graph reasoning problems into smaller, node-centric tasks, effectively improving accuracy while ensuring scalability.
2. This paper illustrates the inherent limitations of single LLMs in graph reasoning tasks in detail. Moreover, extensive experimental results show that the proposed GAR with multi-agent collaboration consistently outperforms all baselines, achieving near-perfect accuracy on polynomial-time graph reasoning tasks.
3. The paper is well-organized and written, with a clear problem setup, related work, methodology, and experimental evaluation.
summary: This paper proposes GraphAgent-Reasoner (GAR), a framework that leverages a multi-agent collaboration strategy for precise and scalable graph reasoning. It consists of four key steps: Graph Construction, Algorithm Establishing, Distributed Execution, and Master Summarization. Extensive experiments on graph reasoning tasks from GraphInstruct indicate that GAR significantly improves accuracy while preserving robust scalability, surpassing both closed-source and fine-tuned open-source models.
weaknesses: 1. The paper does not provide comprehensive ablation and hyperparameter studies, such as evaluating the impact of using different LLMs, varying the maximum number of iterations, and the effect of incorporating a distributed algorithm library.
2. The paper lacks an analysis of the computational complexity, efficiency, and resource requirements of the proposed GAR, including the training/inference time, memory usage, and API costs, which would help assess its scalability and practical applicability. 
3. The paper misses some important baselines, particularly the single LLM utilizing various advanced prompting techniques such as Chain-of-Thought (CoT) [1], Tree of Thought (ToT) [2], and Iteration of Thought (IoT) [3]. Comparing the proposed GAR with these baselines would further demonstrate its effectiveness and scalability.
4. Several typos are present in the paper. For example, In line 80, "Reasoner(GAR) framework, ..." lacks a space after "Reasoner". In line 173, it would be beneficial to spell out "TAG" as "Text-Attributed Graph" for clarity. In the caption of Figure 4 (line 374), there are missing spaces after "GPT4" and "GraphWiz".

**Reference**  
[1] Chain-of-thought prompting elicits reasoning in large language models, NeurIPS, 2022.  
[2] Tree of Thoughts: Deliberate Problem Solving with Large Language Models, NeurIPS, 2023.  
[3] Iteration of Thought: Leveraging Inner Dialogue for Autonomous Large Language Model Reasoning, 2024.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. In the appendix, Table 3 mentions that GraphInstruct dataset has 9 problem types and has maximum flow, hamilton path and subgraph matching problems. The authors only provide experimental results for 6 types of problems. What about the results for the other problem types? Without investigating these complex problems, the claimed contributions about their framework in solving complex graph reasoning problems appear to be problematic.
 
2. It appears the distributed algorithms suffers from high computational complexity. Can you provide a table showing how the number of agents needed, reasoning time, token consumption, and corresponding expenses with increasing graph size? Comparisons with baselines are needed.

3. Did the authors conduct repeated experiments in the reported results? No descriptions about repeated experiments were given. 

4. In the appendix (P13, P18, P19 and P20), a Hamilton Path Execution Example is provided.  However, I found the execution result by GraphAgent-Reasoner seems to be wrong. I also test this problem with GPT4-turbo and obtain a correct path, making me doubt about the soundness of this work.
 
5. There is a distributed algorithm for PageRank in the appendix, but no relevant quantity experiments are given.
 
6. In Figure 4(a), why GraphAgent and GraphWiz-DPO’s performance is better with a size of 80 than with 60?
soundness: 1
strengths: 1. This paper analyzes why a single LLM cannot effectively handle large-scale graph analysis problems from a memory perspective, offering a novel insight.
2. The paper constructs a multi-agent framework for distributed graph reasoning, which can solve several fundamental graph theory problems mentioned in the paper. The results demonstrate that GraphAgent-Reasoner can achieve good performance on certain problems.
summary: This paper presents a multi-agent framework named GraphAgent-Reasoner for solving graph reasoning problems. Inspired by distributed algorithms, the framework provides detailed algorithmic processing steps for several fundamental graph theory tasks that can be processed in a distributed manner, and presents a general multi-agent distributed strategy for handling graph reasoning problems. The paper uses part of the GraphWiz dataset and compares against GraphWiz-DPO, demonstrating that proposed framework and algorithms can achieve good performance on certain fundamental graph theory problems.
weaknesses: 1. The paper claims to solve complex graph reasoning problems, but only 6 out of 9 problem types in GraphWiz dataset were evaluated. Of the remaining three categories, one (maximum flow) was marked as Medium by GraphWiz authors, and two (hamilton path and subgraph matching) were marked as Hard. No corresponding results were provided. If distributed algorithms are not a universal graph reasoning method, this paper appears to be over-claiming.
2. According to the algorithms in appendix, I think the method may suffer from high computational cost. Comparisons about reasoning time, token consumption, and corresponding expenses are needed.
3. There are many issues about experiment settings and presentation, making me feel the paper was not well-prepared. See the questions below.