反復型グラフニューラルネットワークにおける停止（ハルティング）と収束（コンバージェンス）の違い

要旨: 反復型グラフニューラルネットワーク（RGNN）は、ある停止条件が満たされるまでメッセージパッシングを反復することで、標準的なGNNを拡張する。文献には様々なRGNNモデルが提案されている。本論文では、次の3つのモデルを研究する：収束するRGNN（すべての頂点表現が安定化する必要がある）、出力が収束するRGNN（出力分類のみが安定化する必要がある）、および停止するRGNN（頂点ごとの停止判定器が、停止するタイミングを決定する）。これらのモデルの表現力の関係を確立する。無向グラフ上では、収束するRGNNは、階層付き準双模倣不変の停止RGNNと同等の表現力を持ち、一方で出力が収束するRGNNは少なくとも同等の表現力を持つ。停止RGNNに関する既存の結果と組み合わせることで、単項二階論理（MSO）で表現可能な分類器に対する相対性として、収束するRGNNは厳密に階層付きモーダル mu-calculus（muGML）を表現し、出力が収束するRGNNは少なくとも muGML を表現することが示される。これらの結果は、和集約を用いるReLUネットワークに制限しても成立する。主要な技術的課題は、停止するRGNNを収束するものによってシミュレートすることである。グローバルな停止判定器がないと、頂点が局所的に異なる時刻で停止を決めてしまい、脱同期が生じる。本論文では、この非同期性にもかかわらず頂点が協調できるようにする「交通信号（traffic-light）」プロトコルを開発する。本研究はBollenら（2025）による未解決問題に答えるとともに、Pfluegerら（2024）のRGNNモデルが、収束が保証される場合でも完全な muGML の表現力を保持することを示す。