論文の概要: On Halting vs Converging in Recurrent Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2604.25551v1
- Date: Tue, 28 Apr 2026 12:17:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-29 16:49:17.847068
- Title: On Halting vs Converging in Recurrent Graph Neural Networks
- Title（参考訳）: リカレントグラフニューラルネットワークにおけるHalting vs Convergingについて
- Authors: Jeroen Bollen, Stijn Vansummeren,
- Abstract要約: リカレントグラフニューラルネットワーク(RGNN)は、停止条件を満たすまでメッセージパッシングを繰り返すことで、標準的なGNNを拡張している。
様々なRGNNモデルが文献で提案されている。
本稿では,RGNNの収束,RGNNの出力収束,RGNNの停止という3つのモデルについて検討する。
- 参考スコア（独自算出の注目度）: 2.260258863997296
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Recurrent Graph Neural Networks (RGNNs) extend standard GNNs by iterating message-passing until some stopping condition is met. Various RGNN models have been proposed in the literature. In this paper, we study three such models: converging RGNNs, where all vertex representations must stabilise; output-converging RGNNs, where only the output classifications must stabilise; and halting RGNNs, where a per-vertex halting classifier determines when to stop. We establish expressiveness relationships between these models: over undirected graphs, converging RGNNs are equally expressive as graded-bisimulation-invariant halting RGNNs, while output-converging RGNNs are at least as expressive. Combined with prior results on halting RGNNs, this shows that, relative to the classifiers expressible in monadic second-order logic (MSO), converging RGNNs express exactly the graded modal $μ$-calculus ($μ$GML), and output-converging RGNNs express at least $μ$GML. These results hold even when restricting to ReLU networks with sum aggregation. The main technical challenge is simulating halting RGNNs by converging ones: without a global halting classifier, vertices may locally decide to halt at different times, causing desynchronisation. We develop a "traffic-light" protocol that enables vertices to coordinate despite this asynchrony. Our results answer an open question from Bollen et al. (2025) and show that the RGNN model of Pflueger et al. (2024) retains full $μ$GML expressiveness even when convergence is guaranteed.
- Abstract（参考訳）: リカレントグラフニューラルネットワーク(RGNN)は、停止条件を満たすまでメッセージパッシングを繰り返すことで、標準的なGNNを拡張している。
様々なRGNNモデルが文献で提案されている。
本稿では、全ての頂点表現が安定化しなければならないRGNNの収束、出力の分類のみを安定化しなければならないRGNNの出力収束、頂点ごと停止する分類器が停止するタイミングを決定するRGNNの3つのモデルについて検討する。
我々はこれらのモデル間の表現性関係を確立する:無向グラフ上、収束RGNNは、少なくとも出力収束RGNNが表現性を持つのに対して、次数化ビシミュレーション不変停止RGNNと等しく表現性を持つ。
RGNNを停止させる前の結果と組み合わせると、モナディックな二階述語論理(MSO)で表現可能な分類器と比較して、収束RGNNは正確にグレード付きモダルの$μ$-calculus(μ$GML)を表現し、出力収束RGNNは少なくとも$μ$GMLを表す。
これらの結果は、総和でReLUネットワークに制限しても成り立つ。
主要な技術的課題は、RGNNを収束させることで停止をシミュレートすることである:グローバル停止分類器がなければ、頂点は異なるタイミングで停止することをローカルに決定し、非同期を引き起こす。
我々は,この非同期性に拘わらず,頂点の協調を可能にする「トラヒックライト」プロトコルを開発した。
以上の結果から,Pflueger et al (2024) の RGNN モデルは収束が保証された場合でもフルμ$GML 表現性を保っていることを示す。
関連論文リスト
- Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational
and Temporal Graphs [8.095679736030146]
2つの変数と数量化器を持つ一階述語論理の断片である$mathcalFOC$NNについて検討する。
本稿では,線形時間で実行可能な,前処理ステップに似た単純なグラフ変換手法を提案する。
我々の結果は,グラフ変換によるR$2$-GNNが,合成および実世界のデータセットのベースライン手法よりも優れていることを一貫して示している。
論文 参考訳（メタデータ） (2023-11-03T00:33:24Z) - $p$-Laplacian Based Graph Neural Networks [27.747195341003263]
グラフネットワーク(GNN)は、グラフ上の半教師付きノード分類において優れた性能を示す。
我々は、離散正規化フレームワークからメッセージパッシング機構を導出する$p$GNNと呼ばれる新しい$p$LaplacianベースのGNNモデルを提案する。
新たなメッセージパッシング機構は低域通過フィルタと高域通過フィルタを同時に動作させることで,ホモ親和性グラフとヘテロ親和性グラフの両方に対して$p$GNNを有効にすることができることを示す。
論文 参考訳（メタデータ） (2021-11-14T13:16:28Z) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳（メタデータ） (2021-10-27T11:48:50Z) - On the Universality of Graph Neural Networks on Large Random Graphs [22.720758067273195]
グラフニューラルネットワーク(GNN)の潜在位置乱数グラフに対する近似能力について検討する。
大きなグラフ極限では、GNNはc-GNNとして知られるある種の連続的なモデルに収束することが知られている。
我々は,c-SGNNが連続限界におけるc-GNNよりも厳格に強力なことを示す。
論文 参考訳（メタデータ） (2021-05-27T12:52:36Z) - Identity-aware Graph Neural Networks [63.6952975763946]
グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。
ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。
既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
論文 参考訳（メタデータ） (2021-01-25T18:59:01Z) - A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。
本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。
UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文 参考訳（メタデータ） (2020-10-05T04:57:18Z) - The Surprising Power of Graph Neural Networks with Random Node
Initialization [54.4101931234922]
グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。
標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。
本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。
我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
論文 参考訳（メタデータ） (2020-10-02T19:53:05Z) - Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。
これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
論文 参考訳（メタデータ） (2020-08-04T18:57:36Z) - Global Attention Improves Graph Networks Generalization [30.134738629447927]
本稿では,低ランクグローバルアテンション(LRGA)モジュールをグラフニューラルネットワーク(GNN)に導入することを提唱する。
表現型GNNの特定のファミリーに着目し、LRGAで拡張することで、強力なグラフ同型テストへのアルゴリズム的アライメントが得られることを示す。
現実的な観点からは、既存のGNNレイヤをLRGAで拡張することで、現在のGNNベンチマークにおける技術結果の状態を生成できる。
論文 参考訳（メタデータ） (2020-06-14T09:01:57Z) - Bilinear Graph Neural Network with Neighbor Interactions [106.80781016591577]
グラフニューラルネットワーク(GNN)は,グラフデータ上で表現を学習し,予測を行う強力なモデルである。
本稿では,グラフ畳み込み演算子を提案し,隣接するノードの表現の対の相互作用で重み付け和を増大させる。
このフレームワークをBGNN(Bilinear Graph Neural Network)と呼び、隣ノード間の双方向相互作用によるGNN表現能力を向上させる。
論文 参考訳（メタデータ） (2020-02-10T06:43:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。