Abstract
本研究では、不均一超グラフ確率ブロックモデル（HSBM）におけるコミュニティ検出問題を扱う。ここでは、サイズの異なる超辺が共存する。この設定は、高次およびマルチビューの相互作用を捉え、次の基本的な問いを提起する：検出閾値の下にある複数の一様超グラフ層を組み合わせることで、弱い復元が可能になるのだろうか？我々は、この問いに対して、複数の対称確率テンソルに基づき生成される、r 個のブロックをもつ一般クラスの不均一 HSBM に対する、弱い復元のための Kesten--Stigum 型の下界を確立することで答える。r=2 の場合、弱い復元は、すべての一様超グラフ層にわたる信号対雑音比（SNR）の総和が 1 を超えるときに可能であることを示し、(Chodrow et al., 2023) における予想の肯定的部分を確認する。さらに、最適に重み付けされた非バックトラッキング作用素によってこの閾値を達成する、多項式時間のスペクトルアルゴリズムを提示する。重みなしの非バックトラッキング行列に対しては、スペクトル法が別のアルゴリズム的閾値を達成し、これもまた (Chodrow et al., 2023) で予想されていたものである。
我々のアプローチは、不均一超グラフ上の重み付き非バックトラッキング作用素に関するスペクトル理論を発展させ、外れ値固有値と固有ベクトルの重なりについての正確な特徴づけを含む。さらに、重み付き不均一超グラフに合わせて調整した新しい Ihara--Bass の公式を導入する。これにより、低次元表現が効率よく得られ、証明可能なスペクトル復元アルゴリズムへとつながる。以上をまとめると、これらの結果は、不均一超グラフのクラスタリングに対する、原理に基づき計算効率の高いアプローチを提供するとともに、異質な高次相互作用を集約する上での最適重み付けの役割を明らかにする。
