論文の概要: Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers

• arxiv url: http://arxiv.org/abs/2503.01805v1
• Date: Mon, 03 Mar 2025 18:33:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:26:32.444095
• Title: Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers
• Title（参考訳）: 変圧器を用いたグラフタスクのアルゴリズム推論における深さ-幅のトレードオフ
• Authors: Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher, Orr Fischer, Ran Gilad-Bachrach, Amir Globerson,
• Abstract要約: 線形幅, 一定の深さでグラフベースの問題を解くのに十分であることを示す。 これは、幅の適度な増加は、推論時間の観点から有利な、より浅いモデルを可能にすることを示唆している。 本研究は,グラフベースアルゴリズムのトランスフォーマー実装の複雑で興味深い展望を示すものである。
• 参考スコア（独自算出の注目度）: 33.63507016806947
• License:
• Abstract: Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorithmic tasks a key question is what is the minimal size of a transformer that can implement a task. Recent work has begun to explore this problem for graph-based tasks, showing that for sub-linear embedding dimension (i.e., model width) logarithmic depth suffices. However, an open question, which we address here, is what happens if width is allowed to grow linearly. Here we analyze this setting, and provide the surprising result that with linear width, constant depth suffices for solving a host of graph-based problems. This suggests that a moderate increase in width can allow much shallower models, which are advantageous in terms of inference time. For other problems, we show that quadratic width is required. Our results demonstrate the complex and intriguing landscape of transformer implementations of graph-based algorithms. We support our theoretical results with empirical evaluations.
• Abstract（参考訳）: トランスフォーマーは機械学習の分野に革命をもたらした。 特に、グラフベースのタスクを含む複雑なアルゴリズム問題の解決に使用することができる。 このようなアルゴリズム的なタスクでは、タスクを実装するトランスフォーマーの最小サイズは何か、という重要な疑問がある。 最近の研究は、グラフベースのタスクに対してこの問題を探求し始めており、サブ線形埋め込み次元(すなわちモデル幅)では対数深度が十分であることを示している。 しかし、ここで論じるオープンな疑問は、幅が線形に成長することが許されたときに何が起こるかである。 ここでは、この設定を分析し、線形幅、一定の深さでグラフベースの問題を解くのに十分である、という驚くべき結果を与える。 これは、幅の適度な増加は、推論時間の観点から有利なモデルよりもはるかに浅いモデルを可能にすることを示唆している。 その他の問題に対しては、2次幅が必要であることを示す。 本研究は,グラフベースアルゴリズムのトランスフォーマー実装の複雑で興味深い展望を示すものである。 我々は経験的評価で理論結果を支持する。

関連論文リスト

• Transformers Struggle to Learn to Search [32.231381064112085]
  基礎的なグラフ接続問題をテストベッドとして使用し、最小限の高被覆データを効果的に生成し、小型変圧器を訓練する。 適切なトレーニング分布が与えられると、トランスフォーマーは検索を学ぶことができる。 また、文脈内で検索を行うこと(すなわち、チェーン・オブ・シント)は、より大きなグラフで検索することを学ぶことができないことを解決しない。
  論文  参考訳（メタデータ） (2024-12-06T01:29:24Z)
• Understanding Transformer Reasoning Capabilities via Graph Algorithms [25.08208816144745]
  我々は、トランスフォーマースケーリングレギュレーションがアルゴリズムの様々なクラスを完璧に解けるかを検討する。 その結果、トランスフォーマーは多くのグラフ推論タスクで優れており、特殊なグラフニューラルネットワークよりも優れています。
  論文  参考訳（メタデータ） (2024-05-28T18:31:14Z)
• Simulation of Graph Algorithms with Looped Transformers [6.0465914748433915]
  理論的観点から, グラフ上のアルゴリズムをシミュレートするトランスフォーマーネットワークの能力について検討する。 このアーキテクチャは、Dijkstraの最も短い経路のような個々のアルゴリズムをシミュレートできることを示す。 付加的なアテンションヘッドを利用する場合のチューリング完全度を一定幅で示す。
  論文  参考訳（メタデータ） (2024-02-02T02:48:03Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。 様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
  論文  参考訳（メタデータ） (2022-05-27T14:36:55Z)
• 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)
• Graphs for deep learning representations [1.0152838128195467]
  グラフ信号処理(GSP)の最近の進歩に基づくグラフ形式化について紹介します。 すなわち、ディープニューラルネットワークの潜在空間を表すためにグラフを使用します。 このグラフ形式化によって,頑健性の確保,学習プロセスの設計における任意の選択量の削減,入力に付加された小さな一般化の改善,計算複雑性の低減など,さまざまな質問に答えることができることが示されています。
  論文  参考訳（メタデータ） (2020-12-14T11:51:23Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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