GraphArena: Evaluating and Exploring Large Language Models on Graph Computation

• URL: http://arxiv.org/abs/2407.00379v2
• Date: Sat, 15 Feb 2025 09:39:28 GMT
• Title: GraphArena: Evaluating and Exploring Large Language Models on Graph Computation
• Authors: Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, Jia Li,
• Abstract summary: GraphArena is a tool designed to evaluate Large Language Models (LLMs) on real-world graph problems. Evaluation of over 10 LLMs reveals that even top-performing LLMs struggle with larger, more complex graph problems. We explore four potential solutions to address this issue, including chain-of-thought prompting, instruction tuning, code writing, and scaling test-time compute.
• Score: 38.65000765032749
• License:
• Abstract: The ``arms race'' of Large Language Models (LLMs) demands new benchmarks to examine their progresses. In this paper, we introduce GraphArena, a benchmarking tool designed to evaluate LLMs on real-world graph computational problems. It offers a suite of four polynomial-time tasks (e.g., Shortest Distance) and six NP-complete challenges (e.g., Traveling Salesman Problem). GraphArena features a rigorous evaluation framework that classifies LLM outputs as correct, suboptimal (feasible but not optimal), hallucinatory (properly formatted but infeasible), or missing. Evaluation of over 10 LLMs reveals that even top-performing LLMs struggle with larger, more complex graph problems and exhibit hallucination issues. We further explore four potential solutions to address this issue and improve LLMs on graph computation, including chain-of-thought prompting, instruction tuning, code writing, and scaling test-time compute, each demonstrating unique strengths and limitations. GraphArena complements the existing LLM benchmarks and is open-sourced at https://github.com/squareRoot3/GraphArena.

Related papers

• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  Large language models (LLMs) are reorganizing in the AI community for their expected reasoning and inference abilities. We believe this kind of parametric representation of graphs, graph laws, can be a solution for making LLMs understand graph data as the input.
  arXiv  Detail & Related papers  (2024-10-16T00:01:31Z)
• 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)
• Graph Reasoning with Large Language Models via Pseudo-code Prompting [25.469214467011362]
  This paper investigates whether prompting via pseudo-code instructions can improve the performance of large language models (LLMs) in solving graph problems. Our experiments demonstrate that using pseudo-code instructions generally improves the performance of all considered LLMs.
  arXiv  Detail & Related papers  (2024-09-26T14:52:40Z)
• Can LLM Graph Reasoning Generalize beyond Pattern Memorization? [46.93972334344908]
  We evaluate whether large language models (LLMs) can go beyond semantic, numeric, structural, reasoning patterns in the synthetic training data and improve utility on real-world graph-based tasks. We find that while post-training alignment is most promising for real-world tasks, empowering LLM graph reasoning to go beyond pattern remains an open research question.
  arXiv  Detail & Related papers  (2024-06-23T02:59:15Z)
• MathVerse: Does Your Multi-modal LLM Truly See the Diagrams in Visual Math Problems? [99.0305256706604]
  We introduce MathVerse, an all-around visual math benchmark designed for an equitable and in-depth evaluation of MLLMs. We meticulously collect 2,612 high-quality, multi-subject math problems with diagrams from publicly available sources. This approach allows MathVerse to comprehensively assess whether and how much MLLMs can truly understand the visual diagrams for mathematical reasoning.
  arXiv  Detail & Related papers  (2024-03-21T17:59:50Z)
• Integrating Graphs with Large Language Models: Methods and Prospects [68.37584693537555]
  Large language models (LLMs) have emerged as frontrunners, showcasing unparalleled prowess in diverse applications. Merging the capabilities of LLMs with graph-structured data has been a topic of keen interest. This paper bifurcates such integrations into two predominant categories.
  arXiv  Detail & Related papers  (2023-10-09T07:59:34Z)
• Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis [7.099257763803159]
  We evaluate the capabilities of four Large Language Models (LLMs) in addressing several analytical problems with graph data. We employ four distinct evaluation metrics: Correctness, Fidelity, and Rectification. GPT models can generate logical and coherent results, outperforming alternatives in correctness.
  arXiv  Detail & Related papers  (2023-08-22T06:32:07Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)

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.