論文の概要: Which Algorithms Can Graph Neural Networks Learn?

• arxiv url: http://arxiv.org/abs/2602.13106v1
• Date: Fri, 13 Feb 2026 17:09:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-16 23:37:54.05161
• Title: Which Algorithms Can Graph Neural Networks Learn?
• Title（参考訳）: ニューラルネットワークが学習できるアルゴリズムは?
• Authors: Solveig Wittig, Antonis Vasileiou, Robert R. Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris,
• Abstract要約: 本稿ではMPNNがアルゴリズムを学習できる十分な条件を特徴付ける一般的な理論的枠組みを提案する。 我々のフレームワークは、単一ソースのショートベストパス、最小スパンニングツリー、一般的な動的プログラミング問題など、幅広い種類のアルゴリズムに適用できる。
• 参考スコア（独自算出の注目度）: 14.935565203071528
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often referred to as neural algorithmic reasoning. The goal is to integrate algorithmic reasoning capabilities into larger neural pipelines. Many such architectures are based on (message-passing) graph neural networks (MPNNs), owing to their permutation equivariance and ability to deal with sparsity and variable-sized inputs. However, existing work is either largely empirical and lacks formal guarantees or it focuses solely on expressivity, leaving open the question of when and how such architectures generalize beyond a finite training set. In this work, we propose a general theoretical framework that characterizes the sufficient conditions under which MPNNs can learn an algorithm from a training set of small instances and provably approximate its behavior on inputs of arbitrary size. Our framework applies to a broad class of algorithms, including single-source shortest paths, minimum spanning trees, and general dynamic programming problems, such as the $0$-$1$ knapsack problem. In addition, we establish impossibility results for a wide range of algorithmic tasks, showing that standard MPNNs cannot learn them, and we derive more expressive MPNN-like architectures that overcome these limitations. Finally, we refine our analysis for the Bellman-Ford algorithm, yielding a substantially smaller required training set and significantly extending the recent work of Nerem et al. [2025] by allowing for a differentiable regularization loss. Empirical results largely support our theoretical findings.
• Abstract（参考訳）: 近年、神経アーキテクチャが個別のアルゴリズムを実行することを学習する能力を理解することへの関心が高まっている。 目標は、アルゴリズム推論機能をより大きなニューラルネットワークに統合することだ。 このようなアーキテクチャの多くは(メッセージパス)グラフニューラルネットワーク(MPNN)に基づいている。 しかし、既存の研究は主に経験的であり、形式的な保証が欠けているか、あるいは表現性にのみ焦点をあてている。 本研究では,MPNNが小さなインスタンスのトレーニングセットからアルゴリズムを学習し,任意のサイズの入力に対してその振る舞いを確実に近似できるような,十分な条件を特徴付けるための一般的な理論的枠組みを提案する。 我々のフレームワークは、単一ソースのショートパス、最小スパンニングツリー、および0$-$1$knapsack問題のような一般的な動的プログラミング問題を含む幅広いアルゴリズムに適用される。 さらに,従来のMPNNでは学習できないことが示され,これらの制約を克服する表現力のあるMPNNのようなアーキテクチャが導出される。 最後に,ベルマン・フォードアルゴリズムの解析を改良し,必要なトレーニングセットが大幅に小さくなり,Nerem et al [2025] の最近の業績が大幅に拡張された。 実験結果は理論的な結果に大きく貢献する。

関連論文リスト

• Mind The Gap: Deep Learning Doesn't Learn Deeply [16.284360949127723]
  本稿では,ニューラルネットワークが2つの疑問に対処してアルゴリズム推論をどのように学習するかを理解することを目的とする。 ニューラルネットワークが効果的なアルゴリズムを学習できないのはなぜなのか?
  論文  参考訳（メタデータ） (2025-05-24T10:11:36Z)
• Graph neural networks extrapolate out-of-distribution for shortest paths [13.300757448796361]
  グラフニューラルネットワーク(GNN)は、短いパスインスタンスの小さなセットに対して、スパーシリティ規則化された損失を最小限に抑えるために訓練される。 勾配降下により訓練されたGNNは、この損失を最小限に抑え、実際に外挿することができることを示す。
  論文  参考訳（メタデータ） (2025-03-24T21:52:05Z)
• 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)
• A Generalist Neural Algorithmic Learner [18.425083543441776]
  我々は、幅広いアルゴリズムを実行することを学習できる単一のグラフニューラルネットワークプロセッサを構築している。 マルチタスク方式でアルゴリズムを効果的に学習できることを示す。
  論文  参考訳（メタデータ） (2022-09-22T16:41:33Z)
• Graph Neural Networks are Dynamic Programmers [0.0]
  グラフニューラルネットワーク(GNN)は動的プログラミング(DP)と一致すると主張される ここでは、理論と抽象代数学の手法を用いて、GNNとDPの間に複雑な関係が存在することを示す。
  論文  参考訳（メタデータ） (2022-03-29T13:27:28Z)
• Neural network relief: a pruning algorithm based on neural activity [47.57448823030151]
  重要でない接続を非活性化する簡易な重要スコア計量を提案する。 MNIST上でのLeNetアーキテクチャの性能に匹敵する性能を実現する。 このアルゴリズムは、現在のハードウェアとソフトウェアの実装を考えるとき、FLOPを最小化するように設計されていない。
  論文  参考訳（メタデータ） (2021-09-22T15:33:49Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• 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)

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

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