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

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.

arXiv commentAccepted for oral presentation at the 2nd International Workshop on Graph-Augmented LLMs (GaLM), held in conjunction with the 35th ACM International Conference on Information and Knowledge Management (CIKM 2026)