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

arXiv: https://arxiv.org/abs/2605.01484 · HTML: https://mlsanity.com/paper/2605.01484/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 9 of its 45 references that are in the map.
- First posted on arXiv 2 May 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 9 of 9)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation](https://mlsanity.com/paper/1604.08553/) (2016)
- [Algorithms for Large-scale Network Analysis and the NetworKit Toolkit](https://mlsanity.com/paper/2209.13355/) (2022)
- [Actions Speak Louder than Prompts: A Large-Scale Study of LLMs for Graph Inference](https://mlsanity.com/paper/2509.18487/) (2025)

## Abstract (arXiv)

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.