Elamur Research⌕
☰
home / papers / 2026 / Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks

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

Paper · 2026 · Sunil Kumar Maurya and Xin Liu

Summary

Existing benchmarks for LLM graph reasoning, such as NLGraph, GraphQA, GraphPattern and GraphArena, give the model the entire graph as text. This limits them to tiny graphs of roughly 20–50 nodes. Real networks (social, web, peer-to-peer) are often far larger and can only be explored partially, for example through APIs. Maurya and Liu address this gap with EstGraph, a benchmark of synthetic graphs and real-world graphs of up to millions of nodes. It defines four estimation tasks:

  • graph size (number of nodes and edges)
  • number of communities
  • structural type of the graph
  • most influential nodes

Instead of edge lists, the prompts contain compact, task-specific statistics summarising random-walk samples, either simple or Metropolis-Hastings walks. This keeps the input within context limits. Reasoning models (o3, gemini-2.5-pro, sonnet-4, DeepSeek-V3.1) are compared against classical estimators. LLMs can infer meaningful global properties from walk summaries alone, but accuracy varies strongly by task and model. The work extends LLM graph evaluation to realistic, partially observable large-scale settings and offers practical usage guidance.

Key points

  • Scale and prompt size: EstGraph covers synthetic graphs up to 100k nodes and real-world graphs up to 2.39M nodes, including ego-Twitter, twitch-gamers, email-EuAll, as-skitter and wiki-Talk. For size estimation on real data, the walk-statistics prompts are up to 559x shorter than full graph descriptions.
  • Graph size estimation: relative error often stays below 20%. A simple random walk, which is easier to run in practice, can work nearly as well as unbiased Metropolis-Hastings sampling. Larger walk budgets generally improve estimates.
  • Graph structure (BA, ER, LFR, Grid):
    • Every model classified grids with 100% accuracy.
    • o3 reached 93.3% accuracy on both BA and ER graphs.
    • No model mislabelled a BA or LFR graph as ER.
  • Communities: LLM errors ranged from about 1.9 to 2.6 communities, for graphs with 5–12 communities. Among the classical baselines, Greedy and Louvain were nearly error-free, while Label propagation failed badly.
  • Influential nodes (Precision@20):
    • PageRank was the easiest measure to estimate; o3 led with 81%.
    • Shortest-path measures were much harder; o3 reached about 31–35% on betweenness and closeness, and other models did worse.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓The University of TokyoTokyo · Japan90 works · 9,156 citations🔬National Institute of Advanced Industrial Science and TechnologyTsukuba · Japan17 works · 2,760 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksEvaluation & benchmarks · 1,220 works

Cite

Cite as Sunil Kumar Maurya and Xin Liu. 2026. Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.1846

@inproceedings{maurya2026evaluating,
  title = {{Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks}},
  author = {Sunil Kumar Maurya and Xin Liu},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.1846},
  url = {https://doi.org/10.18653/v1/2026.acl-long.1846}
}

References

1 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Eugenio Angriman, Alexander van der Grinten, Michael Hamann, Henning Meyerhenke, and Manuel Pen-schuck. 2022. Algorithms for Large-Scale Network Analysis and the NetworKit Toolkit. In Hannah Bast, Claudius Korzen, Ulrich Meyer, and Manuel Pen-schuck, editors, Algorithms for Big Data: DFG Priority Pr… find

Updated

This page in Markdown → https://md.research.elamur.ai/free/en/papers/maurya-2026-evaluating-llms-large-scale-graph/