Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
作者: Kumar Thushalika, Sukumar Kishanthan, Asela Hevapathige
分类: cs.CL
发布日期: 2026-06-08
💡 一句话要点
揭示大型语言模型在图同构理解中的局限性
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 图同构 大型语言模型 结构推理 模式识别 图论
📋 核心要点
- 现有大型语言模型在图同构检测上表现良好，但缺乏对图结构的深层理解。
- 论文通过分析LLMs在节点标签置换情况下的表现，揭示其推理能力的局限性。
- 实验结果显示，LLMs在面对同构图的标签变化时，无法正确识别同构关系，表明其推理依赖于模式识别而非结构理解。
📝 摘要（中文）
大型语言模型（LLMs）在多种推理任务上表现出色，但其在图结构推理方面的能力尚不明确。本文研究了LLMs是否真正理解图同构这一图论中的基本问题。尽管LLMs在同构检测上几乎达到完美准确率，但我们表明这种表现是虚幻的。当相同的图以置换的节点标签呈现时，LLMs未能识别它们的同构性。这一发现表明，LLMs利用模式而非对抽象图结构进行推理。由于置换不变性是有效结构推理的基本要求，这些结果表明，在图推理基准测试中的成功不应被解读为真正的拓扑理解的证据。
🔬 方法详解
问题定义：本文旨在探讨大型语言模型在图同构推理中的真实能力，现有方法在面对节点标签置换时表现出明显的不足，无法有效识别同构图。
核心思路：通过对比LLMs在不同节点标签下的同构图表现，论文揭示了其推理过程中的模式依赖性，而非真正的结构理解。
技术框架：研究采用了图同构的标准测试集，设计了多组实验以验证LLMs在不同条件下的表现，主要模块包括数据准备、模型推理和结果分析。
关键创新：论文的创新在于揭示了LLMs在图同构问题上的表面成功与实际推理能力之间的差距，强调了置换不变性的重要性。
关键设计：实验中使用了多种图结构和节点标签的组合，设计了特定的评估指标来量化模型在同构识别上的表现，确保了实验的严谨性。
📊 实验亮点
实验结果显示，尽管LLMs在同构检测中表现出近乎完美的准确率，但在节点标签置换的情况下，其识别能力显著下降，表明其推理依赖于模式而非结构理解。这一发现为图推理领域提供了新的视角。
🎯 应用场景
该研究对图结构理解的应用具有重要意义，尤其是在社交网络分析、化学分子结构识别和计算机视觉等领域。通过揭示LLMs的局限性，未来的研究可以更好地设计出具备真正结构理解能力的模型，从而推动相关领域的发展。
📄 摘要（原文）
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.