arXiv cs.CL· Kumar Thushalika, Sukumar Kishanthan, Asela Hevapathige·· 12 小时前AI 评分38
研究发现 LLM 在图同构检测上高分是假象：节点标签置换后即失效
Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
AI 导读
LLM 在图同构检测上接近满分，但把同一张图的节点标签打乱后便无法识别其同构关系，说明模型依赖的是表面模式而非抽象图结构推理。该研究指出置换不变性是有效结构推理的基本要求，因此图推理基准上的高分不应被当作真正拓扑理解的证据。论文已被 CIKM 2026 的 GaLM 研讨会接收为 oral 报告。
正文 · 原文
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.
| Comments: | Accepted 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) |
| Subjects: | Computation and Language (cs.CL) |
| Cite as: | arXiv:2606.09484 [cs.CL] |
| (or arXiv:2606.09484v2 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2606.09484 arXiv-issued DOI via DataCite |
Submission history
From: Sukumar Kishanthan [view email]
[v1]
Mon, 8 Jun 2026 13:39:25 UTC (25 KB)
[v2]
Sun, 25 Oct 2026 01:54:37 UTC (116 KB)
来源：arXiv cs.CL · arxiv.org