Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks

• URL: http://arxiv.org/abs/2605.01484v1
• Date: Sat, 02 May 2026 15:11:52 GMT
• Title: Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
• Abstract summary: In real-world data, the size of graphs can be significantly larger, and in many cases, not fully accessible.<n>We propose a large graph benchmark dataset, EstGraph, and introduce four distinct tasks designed to estimate large graph properties.<n>We evaluate the reasoning abilities of LLMs on these tasks using a wide variety of graph datasets.
• Score: 4.0636315905272475
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: With the rapidly improving reasoning abilities of Large Language Models (LLMs), there is also a rising demand to use them in a wide variety of domains. This brings about the need to carefully evaluate the limits of the capabilities of these models with various tests and benchmarks. Graph structures are ubiquitous in real-world data, and are often used to represent and analyze relationship patterns within data. Many benchmarks have already been proposed in the graph literature to test the reasoning ability of LLMs to follow and execute graph algorithms. However, due to the limited context length of LLMs, these benchmarks consist of very small graphs. In real-world data, the size of graphs can be significantly larger, and in many cases, not fully accessible. In this paper, we examine a class of problems that arises with very large graphs having limited accessibility. We propose a large graph benchmark dataset, EstGraph, and introduce four distinct tasks designed to estimate large graph properties. We evaluate the reasoning abilities of LLMs on these tasks using a wide variety of graph datasets. In addition, we provide task-specific prompt constructions based on random walk sampling of large graphs (up to millions of nodes) that effectively convey sufficient information to LLMs within the limits of context length.

Related papers

• Are Large Language Models Suitable for Graph Computation? Progress and Prospects [31.182390464506053]
  Large language models (LLMs) have been increasingly explored for graph computation.<n>We provide a comprehensive review of LLMs for graph computation through a role-based taxonomy.<n>Our review indicates that LLMs are promising for simple, small-scale tasks, but remain unreliable for large-scale and exactness-demanding tasks.
  arXiv  Detail & Related papers  (2026-06-05T03:24:38Z)
• Exploring Graph Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation [26.19182768810174]
  Graph-structured data has become increasingly prevalent across various domains, raising the demand for effective models to handle graph tasks.<n>Traditional graph learning models like Graph Neural Networks (GNNs) have made significant strides, but their capabilities in handling graph data remain limited in certain contexts.<n>In recent years, large language models (LLMs) have emerged as promising candidates for graph tasks, yet most studies focus primarily on performance benchmarks.
  arXiv  Detail & Related papers  (2025-02-26T03:03:46Z)
• 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.<n>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)
• How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension [53.6373473053431]
  This work introduces a benchmark to assess large language models' capabilities in graph pattern tasks.<n>We have developed a benchmark that evaluates whether LLMs can understand graph patterns based on either terminological or topological descriptions.<n>Our benchmark encompasses both synthetic and real datasets, and a variety of models, with a total of 11 tasks and 7 models.
  arXiv  Detail & Related papers  (2024-10-04T04:48:33Z)
• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [70.03602551880526]
  We introduce ProGraph, a benchmark for large language models (LLMs) to process graphs.<n>Our findings reveal that the performance of current LLMs is unsatisfactory, with the best model achieving only 36% accuracy.<n>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)
• Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path [53.71787069694794]
  We focus on the graph reasoning ability of Large Language Models (LLMs)<n>We revisit the ability of LLMs on three fundamental graph tasks: graph description translation, graph connectivity, and the shortest-path problem.<n>Our findings suggest that LLMs can fail to understand graph structures through text descriptions and exhibit varying performance for all these fundamental tasks.
  arXiv  Detail & Related papers  (2024-08-18T16:26:39Z)
• Exploring the Potential of Large Language Models in Graph Generation [51.046188600990014]
  Graph generation requires large language models (LLMs) to generate graphs with given properties. This paper explores the abilities of LLMs for graph generation with systematical task designs and experiments. Our evaluations demonstrate that LLMs, particularly GPT-4, exhibit preliminary abilities in graph generation tasks.
  arXiv  Detail & Related papers  (2024-03-21T12:37:54Z)
• 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)
• Beyond Text: A Deep Dive into Large Language Models' Ability on Understanding Graph Data [13.524529952170672]
  Large language models (LLMs) have achieved impressive performance on many natural language processing tasks. We aim to assess whether LLMs can effectively process graph data and leverage topological structures to enhance performance. By comparing LLMs' performance with specialized graph models, we offer insights into the strengths and limitations of employing LLMs for graph analytics.
  arXiv  Detail & Related papers  (2023-10-07T23:25:22Z)

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.