論文の概要: Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism

• arxiv url: http://arxiv.org/abs/2606.09484v1
• Date: Mon, 08 Jun 2026 13:39:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:07.160115
• Title: Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
• Title（参考訳）: 違いの検出は構造を理解しない:グラフ同型で失敗する大言語モデル
• Abstract要約: 大規模言語モデル(LLM)がグラフ同型を真に理解できるかどうかを検討する。 LLMは同型検出においてほぼ完全な精度を実現するが,この性能は明らかである。 この発見は、LLMが抽象グラフ構造を推論するよりもパターンを活用することを示唆している。
• 参考スコア（独自算出の注目度）: 1.1470070927586018
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: 大規模言語モデル (LLM) は様々な推論タスクにおいて顕著な性能を示したが、グラフの構造的推論能力は未だ不明である。 LLMがグラフ同型を真に理解できるかどうかは、グラフ理論の基本的な問題である。 LLMは同型検出の精度がほぼ良好であるのに対し,この性能は明らかである。 同一グラフが置換ノードラベルで示されるとき、LLMはそれらの同型を識別できない。 この発見は、LLMが抽象グラフ構造を推論するよりもパターンを活用することを示唆している。 置換不変性は有効な構造的推論の基本的な要件であるため、これらの結果はグラフ推論ベンチマークにおける成功を真の位相的理解の証拠として解釈すべきでないことを示している。

関連論文リスト

• Visual Graph Scaffolds for Structural Reasoning in Large Language Models [49.507575509154385]
  グラフは、大きな言語モデル(LLM)を強化するために使われてきた。 本稿では, LLM のグラフの値は情報提供だけでなく, 組織的推論にも当てはまる。 人間はグラフ構造化マインドマップを使って、枝分かれや収束する思考を整理し、グラフが推論支援の内的形態として機能するかどうかを問う。
  論文  参考訳（メタデータ） (2026-06-01T12:17:52Z)
• From Chains to Graphs: Self-Structured Reasoning for General-Domain LLMs [52.0811904328273]
  現実の推論には、複数の前提を統合し、サブプロブレムを並列に解決する必要がある。 最近のアプローチでは、外部に提供されたグラフに依存しており、LCMが独自のグラフ構造化推論を構築し、利用する方法については検討していない。 我々は,LLMが最終回答を生成する前に,その推論プロセスを構造化グラフとして明示的に表現できるフレームワークであるSelf-Graph Reasoning (SGR)を提案する。
  論文  参考訳（メタデータ） (2026-01-07T05:27:41Z)
• Do Larger Language Models Generalize Better? A Scaling Law for Implicit Reasoning at Pretraining Time [73.22651918134808]
  この研究は、モデルサイズのスケーリングによる直感的効果を示し、言語モデル(LM)におけるスケーリングと推論の関係に関する新たな洞察を提供する。 我々は,実世界の大規模知識グラフの構造と分布を再現する合成暗黙のマルチホップ推論環境において,ゼロからLMを事前学習する。 次に、実世界の事前学習における暗黙的推論の単純化とみなすことができるマルチホップ推論を必要とする、グラフの欠落したエッジを完遂するLMの能力を評価する。
  論文  参考訳（メタデータ） (2025-04-04T17:57:22Z)
• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  大規模言語モデル(LLM)は、期待される推論能力と推論能力のために、AIコミュニティで再編成されている。 我々は、グラフのこのようなパラメトリック表現、グラフ法則は、LLMがグラフデータを入力として理解させるソリューションであると信じている。
  論文  参考訳（メタデータ） (2024-10-16T00:01:31Z)
• Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path [53.71787069694794]
  大規模言語モデル(LLM)のグラフ推論能力に着目する。 グラフ記述変換,グラフ接続,最短パス問題という3つの基本グラフタスクにおけるLLMの能力を再考する。 この結果から,LLMはテキスト記述によるグラフ構造理解に失敗し,これらの基本課題に対して様々な性能を示すことが可能であることが示唆された。
  論文  参考訳（メタデータ） (2024-08-18T16:26:39Z)
• Can Graph Descriptive Order Affect Solving Graph Problems with LLMs? [55.5662721046769]
  大規模言語モデル(LLM)は、数学的推論や論理的推論を含む推論タスクにおいて大きな成功を収めた。 従来の研究は様々な手法を用いてLSMのグラフ推論能力について研究してきた。 重要な要素は、主に見過ごされ、グラフ記述がモデルに提示される即時順序である。
  論文  参考訳（メタデータ） (2024-02-11T09:46:24Z)
• GraphLLM: Boosting Graph Reasoning Ability of Large Language Model [7.218768686958888]
  GraphLLMは、グラフ学習モデルと大規模言語モデルを統合する、先駆的なエンドツーエンドアプローチである。 4つの基本グラフ推論タスクにおける経験的評価により,GraphLLMの有効性が検証された。 その結果、54.44%の精度が向上し、96.45%の文脈が短縮された。
  論文  参考訳（メタデータ） (2023-10-09T16:42:00Z)
• Structural Node Embeddings with Homomorphism Counts [2.0131144893314232]
  準同型は局所構造情報を捉えます 準同型数に基づくノード埋め込みの有効性を実験的に示す。 本手法は,有界木幅グラフクラスに対するグラフ準同型カウントの効率的な計算可能性に着目している。
  論文  参考訳（メタデータ） (2023-08-29T13:14:53Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。