ラベルなしランダムグラフの相関の検証

我々は、n個のラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題を研究します。これは仮説検定問題として形式化されており、帰無仮説の下では、2つのグラフは独立に生成されます；対立仮説の下では、2つのグラフはある潜在的なノードの対応に基づいてエッジ相関があり、しかし帰無仮説と同じ周辺分布を持っています。ガウス加重完全グラフおよび密なエルデシュ＝レーニーグラフ（エッジ確率がn^{-o(1)}である場合）について、最適な検定誤り確率がnに対してゼロから一に相転移する鋭い閾値を決定します。エッジ確率がn^{-Ω(1)}の希薄なエルデシュ＝レーニーグラフについては、定数因子内の閾値を決定します。この不可能性結果の証明は条件付き第二モーメント法の応用であり、我々は観察された両方のグラフのエッジを含む交差グラフの典型的な挙動に条件付けることによって尤度比の切り取られた第二モーメントを制限し、エッジ上の誘導されたランダム置換のサイクル構造を考慮します。特に、希薄なレジームでは、臨界下のエルデシュ＝レーニーグラフの擬似森林構造と、エッジ置換の短い軌道から組み立てられることができるサブ擬似森林の慎重な列挙を利用してこれを達成します。