論文の概要: Simulation of Graph Algorithms with Looped Transformers

• arxiv url: http://arxiv.org/abs/2402.01107v3
• Date: Tue, 01 Oct 2024 20:30:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-03 15:17:45.752367
• Title: Simulation of Graph Algorithms with Looped Transformers
• Title（参考訳）: ループ変換器を用いたグラフアルゴリズムのシミュレーション
• Authors: Artur Back de Luca, Kimon Fountoulakis,
• Abstract要約: 理論的観点から, グラフ上のアルゴリズムをシミュレートするトランスフォーマーネットワークの能力について検討する。 このアーキテクチャは、Dijkstraの最も短い経路のような個々のアルゴリズムをシミュレートできることを示す。 付加的なアテンションヘッドを利用する場合のチューリング完全度を一定幅で示す。
• 参考スコア（独自算出の注目度）: 6.0465914748433915
• License:
• Abstract: The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how neural networks can replicate reasoning steps with relational data. In this work, we study the ability of transformer networks to simulate algorithms on graphs from a theoretical perspective. The architecture we use is a looped transformer with extra attention heads that interact with the graph. We prove by construction that this architecture can simulate individual algorithms such as Dijkstra's shortest path, Breadth- and Depth-First Search, and Kosaraju's strongly connected components, as well as multiple algorithms simultaneously. The number of parameters in the networks does not increase with the input graph size, which implies that the networks can simulate the above algorithms for any graph. Despite this property, we show a limit to simulation in our solution due to finite precision. Finally, we show a Turing Completeness result with constant width when the extra attention heads are utilized.
• Abstract（参考訳）: ニューラルネットワークを用いたグラフアルゴリズムの実行は、最近、有望な経験的進歩のために大きな関心を集めている。 このことは、ニューラルネットワークが推論ステップをリレーショナルデータで再現する方法について、さらなる理解を動機付けている。 本研究では,理論的な観点から,グラフ上のアルゴリズムをシミュレートするトランスフォーマーネットワークの能力について検討する。 私たちが使用しているアーキテクチャは、グラフと相互作用する追加の注意頭を持つループ変換器です。 我々は,このアーキテクチャがDijkstraの最短経路,Breadth- and Depth-First Search,Kosarajuの強結合成分,および複数のアルゴリズムを同時にシミュレーションできることを示す。 ネットワーク内のパラメータ数は入力グラフのサイズによって増加しないため、ネットワークは上記のアルゴリズムを任意のグラフに対してシミュレートすることができる。 この性質にもかかわらず、有限精度による解のシミュレーションには限界がある。 最後に,付加的なアテンションヘッドを利用する場合のチューリング完全度を一定幅で示す。

関連論文リスト

• Online Learning Of Expanding Graphs [14.952056744888916]
  本稿では,信号ストリームからグラフを拡張するためのオンラインネットワーク推論の問題に対処する。 ネットワークに加入したばかりのノードや,それまでのノードに対して,さまざまなタイプの更新を可能にする戦略を導入する。
  論文  参考訳（メタデータ） (2024-09-13T09:20:42Z)
• Understanding Transformer Reasoning Capabilities via Graph Algorithms [25.08208816144745]
  我々は、トランスフォーマースケーリングレギュレーションがアルゴリズムの様々なクラスを完璧に解けるかを検討する。 その結果、トランスフォーマーは多くのグラフ推論タスクで優れており、特殊なグラフニューラルネットワークよりも優れています。
  論文  参考訳（メタデータ） (2024-05-28T18:31:14Z)
• Layer-wise training for self-supervised learning on graphs [0.0]
  大規模グラフ上でのグラフニューラルネットワーク(GNN)のエンドツーエンドトレーニングは、いくつかのメモリと計算上の課題を示す。 本稿では,GNN層を自己教師型で学習するアルゴリズムであるレイヤワイズ正規化グラフInfomaxを提案する。
  論文  参考訳（メタデータ） (2023-09-04T10:23:39Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• SynGraphy: Succinct Summarisation of Large Networks via Small Synthetic Representative Graphs [4.550112751061436]
  大規模ネットワークデータセットの構造を視覚的に要約するSynGraphyについて述べる。 入力グラフに類似した構造特性を持つために生成されたより小さなグラフを描画する。
  論文  参考訳（メタデータ） (2023-02-15T16:00:15Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• Oversquashing in GNNs through the lens of information contraction and graph expansion [6.8222473597904845]
  本稿では,情報収縮に基づく過疎分析のためのフレームワークを提案する。 オーバーカッシングを緩和するグラフ再配線アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-06T08:44:39Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• Graph Kernel Neural Networks [53.91024360329517]
  本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。 これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。 私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
  論文  参考訳（メタデータ） (2021-12-14T14:48:08Z)
• Geometrically Principled Connections in Graph Neural Networks [66.51286736506658]
  我々は、幾何学的深層学習の新興分野におけるイノベーションの原動力は、幾何が依然として主要な推進力であるべきだと論じている。 グラフニューラルネットワークとコンピュータグラフィックスとデータ近似モデルとの関係:放射基底関数(RBF) 完全連結層とグラフ畳み込み演算子を組み合わせた新しいビルディングブロックであるアフィンスキップ接続を導入する。
  論文  参考訳（メタデータ） (2020-04-06T13:25:46Z)

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

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