論文の概要: Graph neural networks extrapolate out-of-distribution for shortest paths

• arxiv url: http://arxiv.org/abs/2503.19173v1
• Date: Mon, 24 Mar 2025 21:52:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-26 16:53:43.475887
• Title: Graph neural networks extrapolate out-of-distribution for shortest paths
• Title（参考訳）: グラフニューラルネットは最短経路のアウト・オブ・ディストリビューションを外挿する
• Authors: Robert R. Nerem, Samantha Chen, Sanjoy Dasgupta, Yusu Wang,
• Abstract要約: グラフニューラルネットワーク(GNN)は、短いパスインスタンスの小さなセットに対して、スパーシリティ規則化された損失を最小限に抑えるために訓練される。 勾配降下により訓練されたGNNは、この損失を最小限に抑え、実際に外挿することができることを示す。
• 参考スコア（独自算出の注目度）: 13.300757448796361
• License:
• Abstract: Neural networks (NNs), despite their success and wide adoption, still struggle to extrapolate out-of-distribution (OOD), i.e., to inputs that are not well-represented by their training dataset. Addressing the OOD generalization gap is crucial when models are deployed in environments significantly different from the training set, such as applying Graph Neural Networks (GNNs) trained on small graphs to large, real-world graphs. One promising approach for achieving robust OOD generalization is the framework of neural algorithmic alignment, which incorporates ideas from classical algorithms by designing neural architectures that resemble specific algorithmic paradigms (e.g. dynamic programming). The hope is that trained models of this form would have superior OOD capabilities, in much the same way that classical algorithms work for all instances. We rigorously analyze the role of algorithmic alignment in achieving OOD generalization, focusing on graph neural networks (GNNs) applied to the canonical shortest path problem. We prove that GNNs, trained to minimize a sparsity-regularized loss over a small set of shortest path instances, exactly implement the Bellman-Ford (BF) algorithm for shortest paths. In fact, if a GNN minimizes this loss within an error of $\epsilon$, it implements the BF algorithm with an error of $O(\epsilon)$. Consequently, despite limited training data, these GNNs are guaranteed to extrapolate to arbitrary shortest-path problems, including instances of any size. Our empirical results support our theory by showing that NNs trained by gradient descent are able to minimize this loss and extrapolate in practice.
• Abstract（参考訳）: ニューラルネットワーク(NN)は、その成功と広く採用されているにもかかわらず、トレーニングデータセットでよく表現されていない入力へのアウト・オブ・ディストリビューション(OOD)の抽出に苦慮している。 OOD一般化ギャップに対処することは、小さなグラフでトレーニングされたグラフニューラルネットワーク(GNN)を大規模で実世界のグラフに適用するなど、トレーニングセットと大きく異なる環境にモデルがデプロイされる場合、極めて重要である。 堅牢なOOD一般化を達成するための有望なアプローチの1つは、ニューラルネットワークアライメントのフレームワークである。これは、特定のアルゴリズムパラダイム(例えば動的プログラミング)に似たニューラルアーキテクチャを設計することで、古典的なアルゴリズムからのアイデアを取り入れている。 この形式のトレーニングされたモデルは、古典的なアルゴリズムがすべてのインスタンスで動作するのと同じように、優れたOOD機能を持つことを期待しています。 我々は,標準最短経路問題に適用したグラフニューラルネットワーク(GNN)に着目し,OOD一般化におけるアルゴリズムアライメントの役割を厳密に分析した。 GNNは,最短経路の少数のインスタンスに対して,スパーシリティ規則化された損失を最小限に抑えるために訓練され,Bellman-Ford (BF) アルゴリズムを正確に実装している。 実際、GNNがこの損失を$\epsilon$のエラーで最小化した場合、$O(\epsilon)$のエラーでBFアルゴリズムを実装します。 その結果、トレーニングデータに制限があるにもかかわらず、これらのGNNは任意の最短パス問題に外挿されることが保証される。 我々の経験的結果は、勾配降下によって訓練されたNNが、この損失を最小限に抑え、実際に外挿できることを示すことによって、我々の理論を支持する。

関連論文リスト

• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  グラフニューラルネットワークは、様々なアプリケーションにまたがる強力なパフォーマンスで認識されている。 BPには、その生物学的妥当性に挑戦する制限があり、グラフベースのタスクのためのトレーニングニューラルネットワークの効率、スケーラビリティ、並列性に影響を与える。 半教師付き学習のケーススタディを用いて,GNNに適した新しい前方学習フレームワークであるDFA-GNNを提案する。
  論文  参考訳（メタデータ） (2024-06-04T07:24:51Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Graph Neural Networks are Dynamic Programmers [0.0]
  グラフニューラルネットワーク(GNN)は動的プログラミング(DP)と一致すると主張される ここでは、理論と抽象代数学の手法を用いて、GNNとDPの間に複雑な関係が存在することを示す。
  論文  参考訳（メタデータ） (2022-03-29T13:27:28Z)
• Graph Neural Networks for Wireless Communications: From Theory to Practice [10.61745503150249]
  グラフニューラルネットワーク(GNN)は、無線通信問題におけるグラフトポロジ(グラフトポロジ)というドメイン知識を効果的に活用することができる。 理論的保証のために、GNNは従来のニューラルネットワークに比べてトレーニングサンプルがはるかに少ない無線ネットワークにおいて、ほぼ最適性能を達成できることを示す。 設計ガイドラインでは,無線ネットワークにおける一般的な設計問題に適用可能な統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-03-21T08:39:44Z)
• Algorithms for Efficiently Learning Low-Rank Neural Networks [12.916132936159713]
  低ランクニューラルネットワークの学習アルゴリズムについて検討する。 単層ReLUネットワークに最適な低ランク近似を学習するアルゴリズムを提案する。 低ランク$textitdeep$ネットワークをトレーニングするための新しい低ランクフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-02-02T01:08:29Z)
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks [79.74580058178594]
  目的関数の幾何学的構造を解析することにより、刈り取られたニューラルネットワークを訓練する性能を解析する。 本稿では,ニューラルネットワークモデルがプルーニングされるにつれて,一般化が保証された望ましいモデル近傍の凸領域が大きくなることを示す。
  論文  参考訳（メタデータ） (2021-10-12T01:11:07Z)
• Binary Graph Neural Networks [69.51765073772226]
  グラフニューラルネットワーク(gnns)は、不規則データに対する表現学習のための強力で柔軟なフレームワークとして登場した。 本稿では,グラフニューラルネットワークのバイナライゼーションのための異なる戦略を提示し,評価する。 モデルの慎重な設計とトレーニングプロセスの制御によって、バイナリグラフニューラルネットワークは、挑戦的なベンチマークの精度において、適度なコストでトレーニングできることを示しています。
  論文  参考訳（メタデータ） (2020-12-31T18:48:58Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

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

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