論文の概要: Transformers Can Learn Connectivity in Some Graphs but Not Others

• arxiv url: http://arxiv.org/abs/2509.22343v1
• Date: Fri, 26 Sep 2025 13:39:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.462247
• Title: Transformers Can Learn Connectivity in Some Graphs but Not Others
• Title（参考訳）: 変換器はいくつかのグラフで接続性を学ぶことができるが、他のグラフは学習できない
• Authors: Amit Roy, Abulhair Saparov,
• Abstract要約: 変換器は、各ノードを低次元のサブ空間に埋め込むことができる「グリッドのような」有向グラフ上で接続性を学ぶことができる。 基礎となるグリッドグラフの次元性は、接続タスクを学習するトランスフォーマーの能力の強い予測子であることがわかった。 モデルスケールの増大により、グリッドグラフ上の接続性を推測する一般化がますます向上する。
• 参考スコア（独自算出の注目度）: 6.191674550652997
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reasoning capability is essential to ensure the factual correctness of the responses of transformer-based Large Language Models (LLMs), and robust reasoning about transitive relations is instrumental in many settings, such as causal inference. Hence, it is essential to investigate the capability of transformers in the task of inferring transitive relations (e.g., knowing A causes B and B causes C, then A causes C). The task of inferring transitive relations is equivalent to the task of connectivity in directed graphs (e.g., knowing there is a path from A to B, and there is a path from B to C, then there is a path from A to C). Past research focused on whether transformers can learn to infer transitivity from in-context examples provided in the input prompt. However, transformers' capability to infer transitive relations from training examples and how scaling affects the ability is unexplored. In this study, we seek to answer this question by generating directed graphs to train transformer models of varying sizes and evaluate their ability to infer transitive relations for various graph sizes. Our findings suggest that transformers are capable of learning connectivity on "grid-like'' directed graphs where each node can be embedded in a low-dimensional subspace, and connectivity is easily inferable from the embeddings of the nodes. We find that the dimensionality of the underlying grid graph is a strong predictor of transformers' ability to learn the connectivity task, where higher-dimensional grid graphs pose a greater challenge than low-dimensional grid graphs. In addition, we observe that increasing the model scale leads to increasingly better generalization to infer connectivity over grid graphs. However, if the graph is not a grid graph and contains many disconnected components, transformers struggle to learn the connectivity task, especially when the number of components is large.
• Abstract（参考訳）: 推論能力はトランスフォーマーベース大規模言語モデル(LLM)の応答の事実的正しさを保証するために不可欠であり、因果推論などの多くの設定において、推移的関係性に関する堅牢な推論が有効である。 したがって、推移的関係(例えば、A が B を、B が C を、A が C を、A が C を、知っている)を推測する作業において、トランスフォーマーの能力を調べることが不可欠である。 推移関係を推定するタスクは、有向グラフにおける接続のタスクと等価である(例えば、A から B への経路が存在し、B から C への経路が存在することを知っていれば、A から C への経路が存在する)。 過去の研究は、入力プロンプトで提供される文脈内例から、トランスフォーマーがトランジシティーを推測できるかどうかに焦点をあてた。 しかし、トランスフォーマーがトレーニング例から推移的関係を推測する能力や、スケーリングが能力にどのように影響するかは未解明である。 本研究では, 様々な大きさのトランスフォーマーモデルを学習し, 様々なグラフサイズに対する遷移関係を推定する能力を評価するために, 有向グラフを生成することにより, この問題に答える。 その結果,変換器は低次元のサブ空間に各ノードを埋め込むことができる「グリッドライク」グラフ上で接続性を学習でき,ノードの埋め込みから容易に接続を推測できることがわかった。 基礎となるグリッドグラフの次元性は、高次元グリッドグラフが低次元グリッドグラフよりも大きな課題をもたらすような接続タスクを学習するトランスフォーマーの能力の強い予測子であることがわかった。 さらに,モデルスケールの増大がグリッドグラフ上の接続性を推論する一般化の促進につながることが観察された。 しかし、グラフがグリッドグラフではなく、多くの非接続コンポーネントを含んでいる場合、トランスフォーマーは接続タスク、特にコンポーネントの数が大きい場合の学習に苦労する。

関連論文リスト

• A Survey of Graph Transformers: Architectures, Theories and Applications [54.561539625830186]
  近年の研究では、多種多様なアーキテクチャ、説明可能性の向上、グラフトランスフォーマーの実用化などが提案されている。 グラフ変換器のアーキテクチャは,その構造情報処理戦略に従って分類する。 本稿では,分子,タンパク質,言語,視覚,交通,脳,物質データなど,グラフトランスフォーマーの実用化例を紹介する。
  論文  参考訳（メタデータ） (2025-02-23T10:55:19Z)
• Towards Mechanistic Interpretability of Graph Transformers via Attention Graphs [16.249474010042736]
  本稿では,グラフニューラルネットワーク(GNN)とグラフ変換器の機械的解釈性向上のための新しいツールであるAttention Graphsを紹介する。 注意グラフは、入力ノード間の情報の流れを記述するために、トランスフォーマー層とヘッドにまたがる注意行列を集約する。
  論文  参考訳（メタデータ） (2025-02-17T22:35:16Z)
• SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity [74.51827323742506]
  グラフ上でのトランスフォーマーにおける多層アテンションの導入の必要性を評価する。 本研究では,一層伝播を一層伝播に還元できることを示す。 これは、グラフ上で強力で効率的なトランスフォーマーを構築するための新しい技術パスを示唆している。
  論文  参考訳（メタデータ） (2024-09-13T17:37:34Z)
• Graph Transformers: A Survey [15.68583521879617]
  グラフトランスフォーマーは機械学習の最近の進歩であり、グラフ構造化データのためのニューラルネットワークモデルの新たなクラスを提供する。 この調査は、グラフトランスフォーマー研究における最近の進歩と課題について、詳細なレビューを提供する。
  論文  参考訳（メタデータ） (2024-07-13T05:15:24Z)
• How Transformers Learn Causal Structure with Gradient Descent [44.31729147722701]
  自己注意はトランスフォーマーが因果構造をエンコードすることを可能にする。 我々は、潜在因果構造を学習する必要があるコンテキスト内学習タスクを導入する。 我々は、文脈内学習タスクで訓練されたトランスフォーマーが、様々な因果構造を回復できることを示す。
  論文  参考訳（メタデータ） (2024-02-22T17:47:03Z)
• Graph Inductive Biases in Transformers without Message Passing [47.238185813842996]
  新しいグラフ誘導バイアス変換器(GRIT)は、メッセージパッシングを使わずにグラフ誘導バイアスを組み込む。 GRITは、さまざまなグラフデータセットにまたがる最先端の実証的なパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2023-05-27T22:26:27Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。 このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。 提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
  論文  参考訳（メタデータ） (2022-07-06T08:13:06Z)
• A Generalization of Transformer Networks to Graphs [5.736353542430439]
  標準モデルと比較して4つの新しい特性を持つグラフトランスを紹介します。 アーキテクチャはエッジ特徴表現に拡張され、化学(結合型)やリンク予測(知識グラフにおけるエンタリティ関係)といったタスクに重要なものとなる。
  論文  参考訳（メタデータ） (2020-12-17T16:11:47Z)

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

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