スペクトル埋め込みがグラフのトポロジーを漏えいさせる：理論、ベンチマーク、適応的復元

要旨: グラフニューラルネットワーク（GNN）はリレーショナルデータに優れていますが、標準的なベンチマークは、グラフが中央に一括で利用可能であるという、現実には不自然な前提を置いています。実際には、連合学習（Federated Graph Learning）、分散システム、プライバシーに配慮したアプリケーションなどの設定では、グラフデータは局所化され、断片化され、ノイズを含み、かつプライバシーを漏えいさせやすい形で存在します。本稿では、この設定に対する統一的な枠組みを提案します。標準的なデータセットを、3つの戦略と4つの制御によって断片化されたベンチマークへ分解する LoGraB（Local Graph Benchmark）を導入します。ここでの制御とは、近傍半径 d、スペクトル品質 k、ノイズレベル sigma、およびカバレッジ比 p です。LoGraB は、グラフ再構築、局所化されたノード分類、ならびに断片間リンク予測を、Island Cohesion により支援します。さらに、ノイズを含むスペクトル断片に対する手法 AFR（Adaptive Fidelity-driven Reconstruction）を提案します。AFR は、ギャップ対打ち切り安定性比と構造エントロピーを組み合わせた忠実度（fidelity）指標によってパッチ品質を評価し、その後、RANSAC-Procrustes によるアラインメント、適応的なステッチング、そしてバンドル調整（Bundle Adjustment）を用いて断片を組み立てます。単一の大域的グラフを無理に強制するのではなく、AFR は大きな忠実な島を復元します。分離条件の下でのヒートカーネルによるエッジ回復、Davis--Kahan の摂動安定性、および有界なアラインメント誤差を示します。さらに、スペクトルギャップの仮定のもとで、十分な固有ベクトルが共有されていれば多項式時間のベイズ的回復が可能であることを保証する Spectral Leakage Proposition を確立します。これは、AFR の決定論的保証を補完するものです。9つのベンチマークでの実験により、LoGraB は断片化の下でモデルの強みと弱みを明らかにし、AFR は 9 件中 7 件のデータセットで最良の F1 を達成し、埋め込みごとの (epsilon,delta)-ガウス差分プライバシーの下では、AFR は epsilon=2 において防御されていない F1 の 75% を保持することが分かりました。匿名コードは https://anonymous.4open.science/r/JMLR_submission で利用可能です