要約
伝統的に、グラフにおけるコミュニティ検出はスペクトル法または確率的グラフィカルモデルの事後推論を使用して解決されてきました。最近の研究では、確率的ブロックモデルなどのランダムグラフ族に焦点を当て、これらの両方のアプローチを統一し、信号対雑音比に基づいて統計的および計算的な検出閾値を特定しています。コミュニティ検出をグラフ上のノードごとの分類問題として再定式化することで、学習の観点からも研究することができます。本稿では、教師あり学習設定でコミュニティ検出問題を解くための新しい種類のグラフニューラルネットワーク（GNNs）を提案します。データ駆動的方式で生成モデルにアクセスせずに、これらのGNNsは二値および多クラス確率的ブロックモデルにおいて信念伝播アルゴリズムの性能に匹敵するか、それ以上の性能を示すことが示されています。特に、エッジ隣接のライングラフ上で定義される非バックトラッキング作用素をGNNsに追加することを提案します。また、当社のモデルは実世界のデータセットでも良好な性能を達成しています。さらに、線形GNNsでのコミュニティ検出問題に関する最適化ランドスケープの最初の分析を行い、特定の単純化と仮定のもとで局所最小値と全局所最小値での損失値が大きく離れていないことを示しています。