論文の概要: Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners

• arxiv url: http://arxiv.org/abs/2610.14982v1
• Date: Sat, 10 Oct 2026 14:57:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.139458
• Title: Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners
• Title（参考訳）: アルゴリズムレゾネーターの急激な洪水は、すべてのヒントを埋めるには十分ではない
• Abstract要約: SALSA-CLRSにおける幅優先探索では,すべてのトレーニングヒントを再現できるが,深いグラフでは失敗する。 これを未熟な洪水と呼び、2つのルートを辿る。
• 参考スコア（独自算出の注目度）: 1.5397834466394758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recurrent algorithmic reasoners are trained with per-step hints on small graphs and run for many more steps on large ones. On breadth-first search in SALSA-CLRS, we find that a reasoner can reproduce every training hint and still fail on deep graphs: after some exact steps, it declares nodes reached before the search gets there. We call this a premature flood and trace two routes to it. In our GRU processor with a degree input, the flood is carried in the hidden state and set off when that input is in the tail of the training distribution. Setting the input higher at inference brings the flood sooner, and none of the six flooding models counts steps. Without the input, summing the neighbors' states instead of averaging them also breaks the processor. In the benchmark's own GIN and PGN, trained with its code, some seeds instead flood from a fixed step, on sparse and dense graphs alike. Clamping the degree input or adding 200 dense training graphs removes every failure of the GRU processor. Detaching the state between steps avoids the flood in that processor (0 of 23 seeds, against 6 under full backpropagation) but not with sums or a residual update, and two published remedies leave floods. None of the benchmark's test sets is both deep and dense, but its deepest one shows the second route: on its Delaunay graphs at 1,600 nodes, one GIN seed floods from step 18. We therefore recommend auditing the range of every input and aggregate, which catches the first route, and testing on deep graphs, which catches both.
• Abstract（参考訳）: 繰り返しアルゴリズム推論器は、小さなグラフ上のステップ毎のヒントで訓練され、大きなグラフ上でさらに多くのステップを実行する。 SALSA-CLRSの幅優先探索では、推論器はすべてのトレーニングヒントを再現でき、深いグラフで失敗する。 これを未熟な洪水と呼び、2つのルートを辿る。 次数入力のGRUプロセッサでは、その入力がトレーニング分布の尾部にあるとき、洪水を隠蔽状態に運び、起動する。 推論時にインプットを高く設定すると、洪水は早くなり、6つのフラッディングモデルのうちどれもステップをカウントしない。 入力がなければ、平均化せずに隣人の状態を和らげることもプロセッサを壊す。 ベンチマークでトレーニングされたGINとPGNでは、固定されたステップから種が、疎密で密度の高いグラフに溢れている。 次数入力のクランプや200の高密度なトレーニンググラフの追加は、GRUプロセッサのすべての障害を取り除く。 ステップ間の状態の分離は、プロセッサの洪水(23種中0個、完全なバックプロパゲーション下で6個)を避けるが、合計や更新は行わない。 ベンチマークのどのテストセットも深さも密度もありませんが、最も深いテストセットは第2のルートを示しています。 したがって、最初のルートをキャッチするすべての入力とアグリゲーションの範囲を監査し、両方をキャッチするディープグラフをテストすることを推奨する。

関連論文リスト

• Spectral Flow Certificates for Depth-Aware Long-Range Propagation in Graph Neural Networks [0.0]
  グラフニューラルネットワークは、ローカルメッセージパッシングを通じて情報を伝達するが、グラフトポロジ自体が、長時間のタスクを解決するためのトレーニングを静かに防止することができる。 グラフの正規化ラプラシアンから数秒で計算される単一スカラーであるスペクトルフロー認証(SFC)を提案する。 SFCは、訓練されたGNN長距離精度の2倍以上のばらつきを説明できる。
  論文  参考訳（メタデータ） (2026-05-16T19:55:28Z)
• Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
  本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。 この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。 我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-02-27T18:12:58Z)
• Careful Selection and Thoughtful Discarding: Graph Explicit Pooling Utilizing Discarded Nodes [53.08068729187698]
  本稿では,ノードと最終表現ベクトルの関係を明示的に活用してノードを選択するグラフ明示プール法を提案する。 提案手法の有効性を検証するため,12種類の広く使用されているデータセットを対象とした総合的な実験を行った。
  論文  参考訳（メタデータ） (2023-11-21T14:44:51Z)
• Edge2Node: Reducing Edge Prediction to Node Classification [0.0]
  我々はEdge2Nodeという予備的なアイデアを導入し、スコアリング関数を必要とせずに、各エッジへの埋め込みを直接取得することを提案した。 この考えは、エッジ予測タスクに与えられたグラフ G に基づいて新しいグラフ H を作成し、その後、G 上のエッジ予測タスクを H 上のノード分類タスクに還元することを提案している。
  論文  参考訳（メタデータ） (2023-11-06T07:28:16Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  グラフニューラルネットワーク(GNN)は、入力グラフを介して学習されたメッセージパッシングを実行する。 最大100のメッセージパッシングステップを持つディープGNNをトレーニングし、いくつかの最先端の結果を得る。
  論文  参考訳（メタデータ） (2021-06-15T08:50:10Z)
• Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。 本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。 実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
  論文  参考訳（メタデータ） (2020-10-29T08:55:33Z)
• Topology-Aware Graph Pooling Networks [51.9008939769679]
  ポーリング操作はコンピュータビジョンや自然言語処理タスクに有効である。 グラフデータ上でプーリング操作を実行する上での課題のひとつは、グラフ上で明確に定義されていない局所性の欠如である。 本稿では,グラフトポロジを明示的に考慮したトポロジ対応プーリング(TAP)層を提案する。
  論文  参考訳（メタデータ） (2020-10-19T20:14:30Z)
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling [31.812988573924674]
  グラフニューラルネットワーク(GNN)では、プール演算子は入力グラフの局所的な要約を計算し、そのグローバルな特性をキャプチャする。 グラフトポロジ全体を保存しながら粗いグラフを生成するGNNのためのプール演算子であるNode Decimation Pooling (NDP)を提案する。 NDPは、最先端のグラフプーリング演算子よりも効率的であり、同時に、様々なグラフ分類タスクにおける競合性能にも達する。
  論文  参考訳（メタデータ） (2019-10-24T21:42:12Z)

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

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