Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
2026-06-08 • Computation and Language
Computation and Language
AI summaryⓘ
The authors tested if large language models (LLMs) really understand when two graphs are the same in structure, a problem called graph isomorphism. Although the LLMs seemed very good at this task, the authors found they failed when the graphs were shown with their node labels shuffled. This means the models are likely using surface patterns instead of truly grasping the graph's shape. The authors conclude that current success on graph tasks doesn't prove LLMs understand graph structure deeply.
large language modelsgraph isomorphismstructural reasoningpermutation invariancegraph theorynode labelsgraph structuretopological understanding
Authors
Kumar Thushalika, Sukumar Kishanthan, Asela Hevapathige
Abstract
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.