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

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

Problem Statement
Existing benchmarks for evaluating the graph reasoning capabilities of Large Language Models (LLMs), such as NLGraph, GraphQA, and GraphArena, are limited by the context window constraints of current models. Consequently, these benchmarks utilize small graphs (typically 10–50 nodes) where the entire structure can be encoded in the prompt. However, real-world graphs (e.g., social, peer-to-peer, and web networks) often contain millions of nodes and are frequently only partially accessible via APIs. This creates a gap in understanding how LLMs perform on large-scale graph tasks where full visibility is impossible. Specifically, there is a lack of evaluation regarding the ability of LLMs to estimate global graph properties—such as size, community structure, and node centrality—using only partial, local information derived from sampling.

Methodology
The authors propose EstGraph, a new benchmark dataset and framework designed to evaluate LLM reasoning on large graphs under conditions of limited accessibility. The methodology centers on using random walk sampling to extract local statistics from graphs ranging up to 2.39 million nodes, which are then summarized into prompts that fit within LLM context limits.

1. Dataset Construction:

   • Synthetic Graphs: Generated using NetworkX and NetworKit, including Barabasi-Albert (BA/power-law), Erdos-Renyi (ER/random), and Gaussian Random Partition (GRP) graphs. These are categorized into Small (100–1k), Medium (1k–10k), and Large (10k–100k) scales.
   • Real-World Graphs: Five datasets from the SNAP repository (e.g., ego-Twitter, as-skitter, wiki-Talk) with node counts ranging from 81k to 2.39 million.
   • Community Graphs: 20 LFR (Lancichinetti-Fortunato-Radicchi) graphs with known community structures (5–12 clusters) for community detection tasks.

2. Sampling Strategy:

   • Instead of providing full edge lists, the framework employs Simple Random Walks (SRW) and Metropolis-Hastings (MH) walks to sample nodes.
   • To address context length limitations, the raw walk data is not fed directly. Instead, task-specific prompt constructions are generated that summarize walk statistics. These statistics include:
     • Walk length and number of unique nodes/edges.
     • Time to first node collision (indicative of local density).
     • Return times to the source node.
     • Cumulative unique nodes discovered at 10% increments.
     • Degree distributions (highest/lowest degree nodes, average degree).
     • Anonymized node names to prevent leakage of total node counts.

3. Evaluation Tasks:
   The benchmark evaluates LLMs on four distinct estimation tasks:

   • Graph Size Estimation: Predicting the total number of nodes and edges.
   • Community Count Estimation: Predicting the number of clusters in LFR graphs.
   • Graph Structure Identification: Classifying the graph type (BA, ER, LFR, or Grid) based on degree distribution patterns.
   • Influential Node Ranking: Identifying top-$k$ nodes based on Betweenness Centrality, Closeness Centrality, and PageRank.

4. Models and Baselines:

   • LLMs: Evaluated on reasoning-capable models including gemini-2.5-pro, sonnet-4, o3 (OpenAI), and DeepSeek-V3.1.
   • Baselines: Classical graph estimation algorithms including Uniform Sampling, MH sampling, Max-degree Random Walk, and Return-time Based Estimation.

Key Results

• Graph Size Estimation: LLMs demonstrated the ability to estimate graph sizes with reasonable accuracy. For synthetic datasets, models like o3 achieved median relative errors below 20%, sometimes outperforming classical baselines. On real-world datasets, gemini-2.5-pro provided the best estimations among LLMs, though errors were higher than on synthetic data. The authors note that while unbiased sampling (MH) is theoretically superior, simple random walks (SRW) provided competitive results in practical settings where MH is difficult to implement.
• Community Detection: LLMs could detect the presence of communities with a mean absolute error of approximately 2 clusters (for graphs with 5–12 communities). However, they were not yet reliable for precise counting compared to classical algorithms like Greedy Modularity and Louvain, which achieved near-zero error on subgraphs.
• Structure Identification: LLMs successfully distinguished between graph types based on degree distributions. o3 performed best overall, correctly identifying Grid and ER graphs. The models demonstrated an ability to differentiate between the uniform degree distribution of ER graphs and the skewed distributions of BA and LFR graphs, though confusion occasionally occurred between BA and LFR types.
• Node Ranking: Performance varied significantly by metric. LLMs struggled with shortest-path-based metrics (Betweenness and Closeness Centrality) due to the difficulty of inferring global paths from local walks. However, they performed notably better on PageRank, which correlates with visitation frequency in random walks. The o3 model significantly outperformed others in PageRank estimation, achieving ~80% Precision@20.

Significance and Contributions
The paper claims four primary contributions:

1. EstGraph Benchmark: The introduction of a large-scale benchmark dataset and four tasks specifically designed to test LLM reasoning on graphs that are too large for full visibility, bridging the gap between small-scale algorithmic benchmarks and real-world data constraints.
2. Prompt Engineering for Large Graphs: The proposal of task-specific prompt constructions that encode random walk statistics. This approach reduces prompt length by up to 559x compared to naive edge-list encoding, enabling the evaluation of graphs with millions of nodes within current context limits.
3. Empirical Evaluation: A comprehensive evaluation of reasoning LLMs on estimation tasks across diverse graph structures (synthetic and real-world) and scales, demonstrating that LLMs can leverage local statistics to infer global properties.
4. Practical Recommendations: The provision of guidelines for large graph analysis with LLMs, such as using median aggregation to handle outlier estimates, utilizing multiple short-to-medium walks to reduce local bias, and recognizing that PageRank-like measures are more feasible to estimate than shortest-path metrics.

The authors conclude that while LLMs are not yet a replacement for specialized graph algorithms, they can provide reasonable estimates for large graph properties when equipped with appropriate sampling and prompting strategies. The work highlights the potential for LLMs to serve as a complementary tool for analyzing large-scale networks where full graph access is infeasible.