論文の概要: Graph Neural Networks are Dynamic Programmers

• arxiv url: http://arxiv.org/abs/2203.15544v1
• Date: Tue, 29 Mar 2022 13:27:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-30 12:42:59.113847
• Title: Graph Neural Networks are Dynamic Programmers
• Title（参考訳）: グラフニューラルネットワークは動的プログラマである
• Authors: Andrew Dudzik, Petar Veli\v{c}kovi\'c
• Abstract要約: グラフニューラルネットワーク(GNN)は動的プログラミング(DP)と一致すると主張される ここでは、理論と抽象代数学の手法を用いて、GNNとDPの間に複雑な関係が存在することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent advances in neural algorithmic reasoning with graph neural networks (GNNs) are propped up by the notion of algorithmic alignment. Broadly, a neural network will be better at learning to execute a reasoning task (in terms of sample complexity) if its individual components align well with the target algorithm. Specifically, GNNs are claimed to align with dynamic programming (DP), a general problem-solving strategy which expresses many polynomial-time algorithms. However, has this alignment truly been demonstrated and theoretically quantified? Here we show, using methods from category theory and abstract algebra, that there exists an intricate connection between GNNs and DP, going well beyond the initial observations over individual algorithms such as Bellman-Ford. Exposing this connection, we easily verify several prior findings in the literature, and hope it will serve as a foundation for building stronger algorithmically aligned GNNs.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)を用いたニューラルアルゴリズム推論の最近の進歩は、アルゴリズムアライメントの概念によって支えられている。 ニューラルネットワークは、個々のコンポーネントがターゲットアルゴリズムとうまく一致している場合、推論タスク(サンプルの複雑さの観点から)の実行を学習するのがよいでしょう。 特に、GNNは、多くの多項式時間アルゴリズムを表現する一般的な問題解決戦略である動的プログラミング(DP)と整合していると主張されている。 しかし、このアライメントは本当に実証され、理論的に定量化されましたか? ここでは、圏論と抽象代数学の手法を用いて、GNNとDPの間に複雑な関係があることを示し、ベルマン・フォードのような個々のアルゴリズムに対する最初の観測をはるかに超えている。 この接続を公開し、文献におけるいくつかの先行的な発見を容易に検証し、より強力なアルゴリズムに整合したGNNを構築する基盤となることを期待する。

関連論文リスト

• Deep Equilibrium Algorithmic Reasoning [18.651333116786084]
  我々は異なる観点からニューラルネットワークの解法を研究する。 アルゴリズムの解はしばしば平衡であるため、平衡方程式を解くことによって直接解を見つけることができる。 我々のアプローチでは、列車とテスト時間の両方において、アルゴリズムの実際のステップ数に関する情報を必要としない。
  論文  参考訳（メタデータ） (2024-10-19T10:40:55Z)
• The Deep Equilibrium Algorithmic Reasoner [20.375241527453447]
  グラフニューラルネットワーク(GNN)が古典的アルゴリズムの実行を学習できることを示す。 我々は、ネットワークをトレーニングしてアルゴリズムの問題を解き、直接平衡を求めることができることを予想し、実証的に検証する。
  論文  参考訳（メタデータ） (2024-02-09T14:46:50Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  ニューラルネットワークにおけるアルゴリズム発見は、時としてより複雑であることを示す。 単純な学習問題でさえ、驚くほど多様なソリューションを許容できることが示されています。
  論文  参考訳（メタデータ） (2023-06-30T17:59:13Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• The Logic of Graph Neural Networks [0.9355115132408681]
  グラフニューラルネットワーク(gnns)は、グラフ上の機械学習問題のディープラーニングアーキテクチャである。 GNNの表現力はWeisfeiler-Lemanアルゴリズムと可変カウント論理によって正確に特徴付けられることが示されている。
  論文  参考訳（メタデータ） (2021-04-29T19:23:26Z)
• Learning Graph Neural Networks with Approximate Gradient Descent [24.49427608361397]
  ラベルがノードまたはグラフに添付されているかどうかに応じて、2種類のグラフニューラルネットワーク(GNN)が調査されます。 gnnトレーニングアルゴリズムの設計と解析のための包括的なフレームワークを開発した。 提案アルゴリズムは,GNNの根底にある真のパラメータに対する線形収束率を保証する。
  論文  参考訳（メタデータ） (2020-12-07T02:54:48Z)
• Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks [55.98291376393561]
  グラフニューラルネットワーク(GNN)は、ソフトウェアエンジニアリングタスクを学習するための強力なツールとして登場した。 リカレントニューラルネットワーク(RNN)は、長いシーケンシャルな推論の連鎖に適しているが、プログラム構造を自然に組み込んでいるわけではない。 本稿では,新しいGNNアーキテクチャ,IPA-GNN(Instruction Pointer Attention Graph Neural Networks)を導入する。
  論文  参考訳（メタデータ） (2020-10-23T19:12:30Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• Neural Bipartite Matching [19.600193617583955]
  本稿では,ニューラルネットワークが複雑なアルゴリズムに適用される方法について述べる。 単一のGNNから生成された機能のみに基づいて、ニューラル実行によって実現される。 評価の結果,ネットワークがほぼ100%の時間で最適なマッチングを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-05-22T17:50:38Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。 ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。 モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
  論文  参考訳（メタデータ） (2020-03-14T05:45:55Z)

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

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