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 报告。
正文 · AI 翻译
摘要：大语言模型（LLM）在多种推理任务上表现出色，但其在图结构上的结构推理能力仍不明确。我们研究 LLM 是否能真正理解图同构——图论中的一个基本问题。尽管 LLM 在同构检测上达到近乎完美的准确率，我们表明这一表现是虚假的。当相同的图以置换后的节点标签呈现时，LLM 无法识别它们的同构关系。这一发现表明，LLM 利用的是模式，而非对抽象图结构进行推理。由于置换不变性是有效结构推理的基本要求，这些结果表明，图推理基准上的成功不应被解读为真正拓扑理解的证据。
| 评论： | 被第二届图增强大语言模型国际研讨会（GaLM）接收为口头报告，该研讨会与第 35 届 ACM 国际信息与知识管理会议（CIKM 2026）联合举办 |
| 主题： | 计算与语言（cs.CL） |
| 引用为： | arXiv:2606.09484 [cs.CL] |
| （或 arXiv:2606.09484v2 [cs.CL] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2606.09484 arXiv 颁发的 DOI（通过 DataCite） |
提交历史
来自：Sukumar Kishanthan [查看邮箱]
[v1]
2026 年 6 月 8 日星期一 13:39:25 UTC（25 KB）
[v2]
2026 年 10 月 25 日星期日 01:54:37 UTC（116 KB）
来源：arXiv cs.CL · arxiv.org