# Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 18 Aug 2024.

## Placed in

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

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

- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Looped Transformers are Better at Learning Learning Algorithms](https://mlsanity.com/paper/2311.12424/) (2023)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [ToolNet: Connecting Large Language Models with Massive Tools via Tool Graph](https://mlsanity.com/paper/2403.00839/) (2024)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [GraphWiz: An Instruction-Following Language Model for Graph Problems](https://mlsanity.com/paper/2402.16029/) (2024)
- [VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context](https://mlsanity.com/paper/2405.04950/) (2024)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models](https://mlsanity.com/paper/2405.09220/) (2024)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)

## Built on by (most cited first, 10 of 10)

- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation](https://mlsanity.com/paper/2502.18771/) (2025)
- [HiBench: Benchmarking LLMs Capability on Hierarchical Structure Reasoning](https://mlsanity.com/paper/2503.00912/) (2025)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning](https://mlsanity.com/paper/2501.07845/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Are Large Language Models Good Temporal Graph Learners?](https://mlsanity.com/paper/2506.05393/) (2025)
- [From Sequence to Structure: Uncovering Substructure Reasoning in Transformers](https://mlsanity.com/paper/2507.10435/) (2025)
- [GraphGhost: Tracing Structures Behind Large Language Models](https://mlsanity.com/paper/2510.08613/) (2025)
- [Generalization in LLM Problem Solving: The Case of the Shortest Path](https://mlsanity.com/paper/2604.15306/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have achieved great success in various reasoning tasks. In this work, we focus on the graph reasoning ability of LLMs. Although theoretical studies proved that LLMs are capable of handling graph reasoning tasks, empirical evaluations reveal numerous failures. To deepen our understanding on this discrepancy, we revisit the ability of LLMs on three fundamental graph tasks: graph description translation, graph connectivity, and the shortest-path problem. Our findings suggest that LLMs can fail to understand graph structures through text descriptions and exhibit varying performance for all these three fundamental tasks. Meanwhile, we perform a real-world investigation on knowledge graphs and make consistent observations with our findings. The codes and datasets are available.