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

• URL: http://arxiv.org/abs/2410.05130v1
• Date: Mon, 7 Oct 2024 15:34:14 GMT
• Title: Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents
• Authors: Yuwei Hu, Runlin Lei, Xinyi Huang, Zhewei Wei, Yongchao Liu,
• Abstract summary: We introduce GraphAgent-Reasoner, a fine-tuning-free framework 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. Our framework demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.
• Score: 27.4884498301785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• A Hierarchical Language Model For Interpretable Graph Reasoning [47.460255447561906]
  We introduce Hierarchical Language Model for Graph (HLM-G), which employs a two-block architecture to capture node-centric local information and interaction-centric global structure. The proposed scheme allows LLMs to address various graph queries with high efficacy, efficiency, and robustness, while reducing computational costs on large-scale graph tasks. Comprehensive evaluations across diverse graph reasoning and real-world tasks of node, link, and graph-levels highlight the superiority of our method.
  arXiv  Detail & Related papers  (2024-10-29T00:28:02Z)
• GCoder: Improving Large Language Model for Generalized Graph Problem Solving [38.9131866084555]
  Large Language Models (LLMs) have demonstrated strong reasoning abilities, making them suitable for complex tasks such as graph computation. We introduce GCoder, a code-based LLM designed to enhance problem-solving in generalized graph problems. Our method involves constructing an extensive training dataset, GraphWild, featuring diverse graph formats and algorithms.
  arXiv  Detail & Related papers  (2024-10-24T18:40:36Z)
• NT-LLM: A Novel Node Tokenizer for Integrating Graph Structure into Large Language Models [26.739650151993928]
  Graphs are a fundamental data structure for representing relationships in real-world scenarios. Applying Large Language Models (LLMs) to graph-related tasks poses significant challenges. We introduce Node Tokenizer for Large Language Models (NT-LLM), a novel framework that efficiently encodes graph structures.
  arXiv  Detail & Related papers  (2024-10-14T17:21:57Z)
• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [90.98855064914379]
  We introduce ProGraph, a benchmark for large language models (LLMs) to process graphs. Our findings reveal that the performance of current LLMs is unsatisfactory, with the best model achieving only 36% accuracy. We propose LLM4Graph datasets, which include crawled documents and auto-generated codes based on 6 widely used graph libraries.
  arXiv  Detail & Related papers  (2024-09-29T11:38:45Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  Learning correspondences aims to find correct correspondences from the initial correspondence set with an uneven correspondence distribution and a low inlier rate. Recent advances usually use graph neural networks (GNNs) to build a single type of graph or stack local graphs into the global one to complete the task. We propose MGNet to effectively combine multiple complementary graphs.
  arXiv  Detail & Related papers  (2024-01-10T07:58:44Z)
• Talk like a Graph: Encoding Graphs for Large Language Models [15.652881653332194]
  We study the first comprehensive study of encoding graph-structured data as text for consumption by large language models (LLMs) We show that LLM performance on graph reasoning tasks varies on three fundamental levels: (1) the graph encoding method, (2) the nature of the graph task itself, and (3) interestingly, the very structure of the graph considered.
  arXiv  Detail & Related papers  (2023-10-06T19:55:21Z)
• Graph-ToolFormer: To Empower LLMs with Graph Reasoning Ability via Prompt Augmented by ChatGPT [10.879701971582502]
  We aim to develop a large language model (LLM) with the reasoning ability on complex graph data. Inspired by the latest ChatGPT and Toolformer models, we propose the Graph-ToolFormer framework to teach LLMs themselves with prompts augmented by ChatGPT to use external graph reasoning API tools.
  arXiv  Detail & Related papers  (2023-04-10T05:25:54Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• Model-Agnostic Graph Regularization for Few-Shot Learning [60.64531995451357]
  We present a comprehensive study on graph embedded few-shot learning. We introduce a graph regularization approach that allows a deeper understanding of the impact of incorporating graph information between labels. Our approach improves the performance of strong base learners by up to 2% on Mini-ImageNet and 6.7% on ImageNet-FS.
  arXiv  Detail & Related papers  (2021-02-14T05:28:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.