Abstract
本稿では、ランダムグラフにおける局所幾何の検出問題を研究する。平均サイズが k の隠れたコミュニティが
mathbb{S}^{d-1} 上のランダム幾何グラフとして生成される一方、残りのすべての辺は Erd\H{o}s--R\'enyi モデル
mathcal{G}(n, p) に従う、モデル \mathcal{G}(n, p, d, k) を導入する。ランダム幾何グラフは、潜在ベクトルの内積を
mathbb{S}^{d-1} 上で閾値化することで生成され、各辺は周辺確率として p に等しい確率を持つ。したがって、
mathcal{G}(n, p, d, k) と
mathcal{G}(n, p) は周辺分布のレベルでは区別不能であり、信号は局所幾何によって誘導される辺間の依存関係のみに存在する。
検出の情報理論的限界と計算論的限界の両方を調べる。情報理論的側面では、上界は符号付き三角形カウントに基づく3つのテスト（大域テスト、スキャンテスト、制約付きスキャンテスト）に従う。一方、下界は2つの相補的な方法による。すなわち、Wishart--GOE 比較による打ち切り二次モーメントと、KLダイバージェンスのテンソル化である。これらの結果を総合すると、固定した p に対して検出閾値が d = \widetilde{\Theta}(k^2 \vee k^6/n^3) で確定することが分かり、さらに p が消失する場合には、完全モデル（すなわち k = n）からの最先端の境界を拡張する。計算論的側面では、計算—統計のギャップを特定し、低次数多項式の枠組みによって証拠を提示するとともに、長さ \ell \geq 4 の符号付きサイクルカウントが劣っている（最適でない）ことを示す。
