論文の概要: Spectral Journey: How Transformers Predict the Shortest Path
- arxiv url: http://arxiv.org/abs/2502.08794v1
- Date: Wed, 12 Feb 2025 21:17:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-14 13:47:49.724032
- Title: Spectral Journey: How Transformers Predict the Shortest Path
- Title（参考訳）: スペクトルジャーニー:トランスフォーマーはいかにして最短経路を予測するか
- Authors: Andrew Cohen, Andrey Gromov, Kaiyu Yang, Yuandong Tian,
- Abstract要約: 単純,連結,無向グラフ上で最短経路を予測するために,スクラッチから訓練したデコーダのみのトランスフォーマー言語モデルについて検討する。
1)2層デコーダのみの言語モデルでは,最大10個のノードを含む単純な連結グラフ上で,最短経路の予測を学習することができる。
次に,線グラフのスペクトル埋め込み空間内のノードを欲求的に選択することで,最短経路を求めるスペクトル線ナビゲータ (SLN) を提案する。
- 参考スコア（独自算出の注目度）: 33.86718226718825
- License:
- Abstract: Decoder-only transformers lead to a step-change in capability of large language models. However, opinions are mixed as to whether they are really planning or reasoning. A path to making progress in this direction is to study the model's behavior in a setting with carefully controlled data. Then interpret the learned representations and reverse-engineer the computation performed internally. We study decoder-only transformer language models trained from scratch to predict shortest paths on simple, connected and undirected graphs. In this setting, the representations and the dynamics learned by the model are interpretable. We present three major results: (1) Two-layer decoder-only language models can learn to predict shortest paths on simple, connected graphs containing up to 10 nodes. (2) Models learn a graph embedding that is correlated with the spectral decomposition of the line graph. (3) Following the insights, we discover a novel approximate path-finding algorithm Spectral Line Navigator (SLN) that finds shortest path by greedily selecting nodes in the space of spectral embedding of the line graph.
- Abstract（参考訳）: デコーダのみのトランスフォーマーは、大きな言語モデルの性能を段階的に変化させる。
しかし、本当に計画を立てているのか、それとも推論しているのかについては意見が分かれている。
この方向に進むための道は、注意深く制御されたデータでモデルの振る舞いを研究することである。
次に、学習した表現を解釈し、内部で実行される計算をリバースエンジニアリングする。
単純,連結,無向グラフ上で最短経路を予測するために,スクラッチから訓練したデコーダのみのトランスフォーマー言語モデルについて検討する。
この設定では、モデルによって学習された表現と力学は解釈可能である。
1)2層デコーダのみの言語モデルでは,最大10個のノードを含む単純な連結グラフ上で,最短経路の予測を学習することができる。
2) モデルは線グラフのスペクトル分解と相関するグラフ埋め込みを学習する。
(3) 線形グラフのスペクトル埋め込み空間において,ノードを優しく選択することで最短経路を求めるスペクトル線ナビゲータ (SLN) が新たに発見された。
関連論文リスト
- Graph as Point Set [31.448841287258116]
本稿では,相互接続ノードを独立点の集合に変換するグラフ・ツー・セット変換法を提案する。
これにより、セットエンコーダを使用してグラフから学習することが可能になり、グラフニューラルネットワークの設計空間が大幅に拡張される。
提案手法の有効性を示すために,グラフから変換された点集合を入力として受け入れる変換器アーキテクチャであるPoint Set Transformer (PST)を導入する。
論文 参考訳（メタデータ） (2024-05-05T02:29:41Z) - Recurrent Distance Filtering for Graph Representation Learning [34.761926988427284]
反復的なワンホップメッセージパッシングに基づくグラフニューラルネットワークは、遠方のノードからの情報を効果的に活用するのに苦労していることが示されている。
これらの課題を解決するための新しいアーキテクチャを提案する。
我々のモデルは、ターゲットへの最短距離で他のノードを集約し、線形RNNを用いてホップ表現のシーケンスを符号化する。
論文 参考訳（メタデータ） (2023-12-03T23:36:16Z) - Deep Prompt Tuning for Graph Transformers [55.2480439325792]
ファインチューニングはリソース集約型であり、大きなモデルのコピーを複数保存する必要がある。
ファインチューニングの代替として,ディープグラフプロンプトチューニングと呼ばれる新しい手法を提案する。
事前学習したパラメータを凍結し、追加したトークンのみを更新することにより、フリーパラメータの数を減らし、複数のモデルコピーを不要にする。
論文 参考訳（メタデータ） (2023-09-18T20:12:17Z) - Path Neural Networks: Expressive and Accurate Graph Neural Networks [23.824156607376697]
グラフニューラルネットワーク(GNN)は最近、グラフ構造化データによる学習の標準的なアプローチになっている。
本稿では,ノードからの経路を集約することでノード表現を更新するPathNNを提案する。
これらの2つの変種は1-WLアルゴリズムよりも厳密に強力であることが証明され、理論的結果が実験的に検証された。
論文 参考訳（メタデータ） (2023-06-09T15:11:49Z) - PatchGT: Transformer over Non-trainable Clusters for Learning Graph
Representations [18.203910156450085]
我々は、新しいTransformerベースのグラフニューラルネットワーク、Patch Graph Transformer(PatchGT)を提案する。
グラフ表現を学習する従来のトランスフォーマーベースモデルとは異なり、PatchGTはノードから直接ではなく、トレーニング不可能なグラフパッチから学習する。
PatchGTは1-WL型GNNよりも高い性能を達成し,ベンチマークデータセット上でPatchGTが競合性能を達成することを示す実証的研究を行った。
論文 参考訳（メタデータ） (2022-11-26T01:17:23Z) - Pure Transformers are Powerful Graph Learners [51.36884247453605]
グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。
このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。
提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
論文 参考訳（メタデータ） (2022-07-06T08:13:06Z) - Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
現在のグラフニューラルネットワーク(GNN)アーキテクチャは、2つの重要なコンポーネントに依存している。
本稿では,学習可能なグラフテンプレートとの距離をグラフ表現のコアに配置する新しい視点を提案する。
この距離埋め込みは、Fused Gromov-Wasserstein (FGW) 距離という最適な輸送距離によって構築される。
論文 参考訳（メタデータ） (2022-05-31T12:24:01Z) - Pretraining Graph Neural Networks for few-shot Analog Circuit Modeling
and Design [68.1682448368636]
本稿では、新しい未知のトポロジや未知の予測タスクに適応可能な回路表現を学習するための教師付き事前学習手法を提案する。
異なる回路の変動位相構造に対処するため、各回路をグラフとして記述し、グラフニューラルネットワーク(GNN)を用いてノード埋め込みを学習する。
出力ノード電圧の予測における事前学習GNNは、新しい未知のトポロジや新しい回路レベル特性の予測に適応可能な学習表現を促進することができることを示す。
論文 参考訳（メタデータ） (2022-03-29T21:18:47Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
Graphonは任意のサイズでグラフを生成する非パラメトリックモデルであり、グラフから簡単に誘導できる。
解析可能でスケーラブルなグラフ生成モデルを構築するために,textitgraphon autoencoder という新しいフレームワークを提案する。
線形グルーポン分解モデルはデコーダとして機能し、潜在表現を活用して誘導されたグルーポンを再構成する。
論文 参考訳（メタデータ） (2021-05-29T08:11:40Z) - Auto-decoding Graphs [91.3755431537592]
生成モデルは、潜在コードからグラフを合成することを学ぶ自動デコーダである。
グラフは、おそらく接続パターンを特定するためにトレーニングされた自己アテンションモジュールを使用して合成される。
論文 参考訳（メタデータ） (2020-06-04T14:23:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。