# Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 8 Jun 2026.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [A Survey of Frontiers in LLM Reasoning: Inference Scaling, Learning to Reason, and Agentic Systems](https://mlsanity.com/paper/2504.09037/) (2025)
- [A Survey of Large Language Models for Graphs](https://mlsanity.com/paper/2405.08011/) (2024)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [CoRe: Benchmarking LLMs Code Reasoning Capabilities through Static Analysis Tasks](https://mlsanity.com/paper/2507.05269/) (2025)
- [LLMs for Relational Reasoning: How Far are We?](https://mlsanity.com/paper/2401.09042/) (2024)
- [When Do LLMs Help With Node Classification? A Comprehensive Analysis](https://mlsanity.com/paper/2502.00829/) (2025)
- [NLPerturbator: Studying the Robustness of Code LLMs to Natural Language Variations](https://mlsanity.com/paper/2406.19783/) (2024)
- [Order Matters: Exploring Order Sensitivity in Multimodal Large Language Models](https://mlsanity.com/paper/2410.16983/) (2024)
- [The Order Effect: Investigating Prompt Sensitivity to Input Order in LLMs](https://mlsanity.com/paper/2502.04134/) (2025)
- [Set-LLM: A Permutation-Invariant LLM](https://mlsanity.com/paper/2505.15433/) (2025)
- [Graph Learning in the Era of LLMs: A Survey from the Perspective of Data, Models, and Tasks](https://mlsanity.com/paper/2412.12456/) (2024)
- [Can LLMs perform structured graph reasoning?](https://mlsanity.com/paper/2402.01805/) (2024)
- [Comprehension Without Competence: Architectural Limits of LLMs in Symbolic Computation and Reasoning](https://mlsanity.com/paper/2507.10624/) (2025)
- [Grounding LLM Reasoning with Knowledge Graphs](https://mlsanity.com/paper/2502.13247/) (2025)
- [Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners](https://mlsanity.com/paper/2511.10234/) (2025)

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

- [The Illusion of Replacement: Rethinking Specialized Machine Learning Models in the Foundation Model Era](https://mlsanity.com/paper/2608.28980/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have shown impressive performance on diverse reasoning tasks, yet their capacity for structural reasoning in graphs remains unclear. We investigate whether LLMs can genuinely understand graph isomorphism -a fundamental problem in graph theory. While LLMs achieve near-perfect accuracy on isomorphism detection, we show this performance is illusory. When identical graphs are presented with permuted node labels, LLMs fail to identify their isomorphism. This finding suggests that LLMs exploit patterns rather than reasoning about abstract graph structure. Since permutation invariance is a fundamental requirement for valid structural reasoning, these results indicate that success on graph reasoning benchmarks should not be interpreted as evidence of genuine topological understanding.