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.
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.
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.
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?