論文の概要: Learning to Execute Graph Algorithms Exactly with Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2601.23207v1
• Date: Fri, 30 Jan 2026 17:31:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-02 18:28:15.586719
• Title: Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークによるグラフアルゴリズムの抽出学習
• Authors: Muhammad Fetrat Qharabagh, Artur Back de Luca, George Giapitzakis, Kimon Fountoulakis,
• Abstract要約: 有界および有限精度制約下でのグラフアルゴリズムの正確な学習可能性について検証する。 局所的な命令は、小さなトレーニングセットから学習できることを示し、完全なグラフアルゴリズムは、誤りなく、高い確率で、推論中に実行可能であることを示す。
• 参考スコア（独自算出の注目度）: 13.971482610625527
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact learnability results for graph algorithms under bounded-degree and finite-precision constraints. Our approach follows a two-step process. First, we train an ensemble of multi-layer perceptrons (MLPs) to execute the local instructions of a single node. Second, during inference, we use the trained MLP ensemble as the update function within a graph neural network (GNN). Leveraging Neural Tangent Kernel (NTK) theory, we show that local instructions can be learned from a small training set, enabling the complete graph algorithm to be executed during inference without error and with high probability. To illustrate the learning power of our setting, we establish a rigorous learnability result for the LOCAL model of distributed computation. We further demonstrate positive learnability results for widely studied algorithms such as message flooding, breadth-first and depth-first search, and Bellman-Ford.
• Abstract（参考訳）: グラフニューラルネットワークが何を学べるか、特にアルゴリズムを実行する能力を理解することは、依然として中心的な理論上の課題である。 本研究では,有界および有限精度制約下でのグラフアルゴリズムの正確な学習性について述べる。 私たちのアプローチは2段階のプロセスに従っています。 まず,マルチ層パーセプトロン(MLP)のアンサンブルを訓練し,単一ノードの局所命令を実行する。 第2に,トレーニング済みMLPアンサンブルをグラフニューラルネットワーク(GNN)内の更新関数として使用する。 ニューラル・タンジェント・カーネル(NTK)理論を応用して、局所的な命令は小さなトレーニングセットから学習できることを示し、完全なグラフアルゴリズムを誤りなく高い確率で実行できるようにする。 設定の学習能力を説明するため,分散計算のLOCALモデルに対して,厳密な学習性を実現する。 さらに,メッセージフラッディング,幅優先検索,深度優先探索,ベルマン・フォードなど,広く研究されているアルゴリズムに対して,肯定的な学習性を示す。

関連論文リスト

• Distributed Graph Neural Network Inference With Just-In-Time Compilation For Industry-Scale Graphs [6.924892368183222]
  グラフニューラルネットワーク(GNN)は様々な分野で顕著な成果を上げている。 グラフデータのスケールの急激な増加は、GNN推論に重大なパフォーマンスボトルネックをもたらしている。 本稿では,GNNを新しいプログラミングインタフェースで抽象化する分散グラフ学習のための革新的な処理パラダイムを提案する。
  論文  参考訳（メタデータ） (2025-03-08T13:26:59Z)
• Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks [13.351162559710124]
  無限幅限界における2層完全連結ネットワークのトレーニング力学について検討する。 このようなモデルの十分な大規模なアンサンブルが、高い確率で正確に実行するためにどのように訓練されるかを示す。 対数的に多くのトレーニングデータだけを用いて効率よく達成できることを示します。
  論文  参考訳（メタデータ） (2025-02-24T00:50:02Z)
• How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
  グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。 この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-08T10:19:56Z)
• Layer-wise training for self-supervised learning on graphs [0.0]
  大規模グラフ上でのグラフニューラルネットワーク(GNN)のエンドツーエンドトレーニングは、いくつかのメモリと計算上の課題を示す。 本稿では,GNN層を自己教師型で学習するアルゴリズムであるレイヤワイズ正規化グラフInfomaxを提案する。
  論文  参考訳（メタデータ） (2023-09-04T10:23:39Z)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  グラフネットワーク(GNN)は、グラフ構造化データから学習する際、顕著な能力を示した。 最適化と一般化の観点から、GNNと一般化を比較した分析の欠如がまだ残っている。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。 これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T15:05:59Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

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

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