技術要約：$\sqrt{n}$ を超えるコミュニティ数を持つ確率的ブロックモデルの相転移

1. 問題設定

本論文は、コミュニティ数 $K$ がノード数 $n$ に伴って増加する（$K \ge \sqrt{n}$ のレジームにおける）確率的ブロックモデル（SBM）におけるコミュニティ回復の計算限界について扱う。

標準的なSBMでは、ノードは $K$ 個のコミュニティに分割され、エッジはノードが同じコミュニティに属するかどうか（確率 $p$）、あるいは異なるコミュニティに属するかどうか（確率 $q$）に基づいて独立に生成される。中心となる課題は、観測された単一のグラフから潜在的なコミュニティ割り当てを回復することである。

歴史的に、$K$ が固定されている場合、統計物理学ではケステン・スティグム（KS）閾値として知られる「計算障壁」が推測されてきた。この閾値を下回る場合、情報理論的には非自明な回復が可能であるが、多項式時間内での回復は不可能であると推測されている。Chinら（2025）による最近の研究は、疎なグラフ（接続確率が $1/n$ のスケールで変化するケース）において、$K \gg \sqrt{n}$ のレジームではこの見解に異を唱えた。彼らは、非逆トラックパス（non-backtracking paths）を数え上げることで、KS閾値を下回る領域でも多項式時間での回復が可能であることを示した。彼らは以下の新しい相転移閾値を提案した：
$$\lambda \gtrsim_{\log} \left( \frac{q + \lambda}{K} \right)^{1 - \log_n(K)}$$
ここで $\lambda = p - q$ である。

本論文は、このレジームに関する2つの未解決問題について調査する：

1. Q1: この新しい閾値は、疎なレジーム（$q \sim 1/n$）かつ $K \ge \sqrt{n}$ の場合においても成立するか？
2. Q2: より密なレジーム（$q \gg 1/n$）において、相転移はどこで起こり、どのようなアルゴリズムが最適か？

2. 手法

著者らは、低次多項式（LDP）下界と、モチーフ計数に基づく構成的なアルゴリズム上界を組み合わせた二角的なアプローチを採用している。

2.1. 低次多項式（LDP）下界

計算の困難さを確立するために、著者らは次数 $D = O(\log n)$ の多項式に限定された推定器の性能を分析する。LDP予想は、もし次数 $O(\log n)$ の多項式が問題を解けないのであれば、いかなる多項式時間アルゴリズムも成功できないというものである。

• 目的: パーティション（組合せ論的なタスク）を直接出力する代わりに、著者らは中心化されたメンバーシップ行列のエントリ $x_{ij} = \mathbb{1}\{z_i = z_j\} - 1/K$ の推定に焦点を当てる。
• 手法: 置換不変な多項式の準直交基底を構築する。以前の著作では正規化のための単純なプロキシが使用されていたが、本論文では多項式の正確な二次のモーメントに基づいた洗練された正規化戦略を導入している。
• 重要な洞察: 基底要素（モチーフ）間の相関を分析することで、任意の次数 $D$ の多項式とターゲットとなる $x_{ij}$ との相関が消失する正確な条件を導出する。この条件が臨界値 $\lambda_c$ を定義する。

2.2. モチーフ計数によるアルゴリズム上界

導出された閾値の上方で回復が可能であることを証明するために、著者らは特定のグラフモチーフ（部分グラフ）をノードのペア $(i, j)$ に付随させてカウントするアルゴリズムを設計する。

• 戦略: アルゴリズムは、ノード $i$ と $j$ を含む特定のモチーフ $G$ の出現回数をカウントする。もし $i$ と $j$ が同じコミュニティに属していれば、カウント数は異なるコミュニティに属している場合よりも有意に高くなる。
• モチーフの選択: 最適なモチーフは、密度レジーム $q \sim n^{-\alpha}$ に依存する。
  • 特定の有理密度の場合は、クリーク（完全グラフ）や自己回避パスのような単純なモチーフで十分である。
  • 一般的な有理密度の場合は、著者らは**「ファスナー（fastener）付きサイクル・ブローアップ」**と呼ばれる複雑なモチーフを構築する。これは、サイクルを取り、各ノードを頂点の層へと「ブローアップ」し、ターゲットとなるノード $i$ と $j$ をこれらの層に「ファスナー」エッジを介して接続することで形成される。
• 後処理: 集中度と多項式時間の複雑さを保証するために、著者らは**中央値（Median-of-Means, MoM）**の手順を用いる。グラフを互いに素な部分集合に分割し、各部分集合上でモチーフのカウントを計算し、それらのカウントの中央値を取ることで、コミュニティの関係を推定する。

3. 主な貢献と結果

貢献 1: 厳密なLDP下界

著者らは、任意のグラフ密度に対して、低次多項式が以下の閾値 $\lambda_c$ 未満でコミュニティ回復に失敗することを証明した：
$$\sup_{r \ge 1} \frac{n \lambda_c^{2r}}{K \lambda_c^r + K^2 \bar{q}^r} = 1$$
ここで $\bar{q} = q(1-q)$ である。

• レジーム $K \le \sqrt{n}$: 最大値は $r=1$ で達成され、標準的なケステン・スティグム閾値を回収する。
• レジーム $K \ge \sqrt{n}$: 最大値は $r > 1$ で達成される。疎なレジーム（$q \sim 1/n$）では、この閾値は多項式対数因子（poly-logarithmic factors）の範囲内で Chinら（2025）によって推測されたものと一致する。より密なレジームにおいては、多項式時間でのコミュニティ回復に関する新たな下界を提供する。

貢献 2: モチーフ計数による成功的な回復

著者らは、特定のモチーフをカウントすることで、閾値 $\lambda_c$ の上方で多項式時間でのコミュニティ回復が可能であることを証明した。

• 疎なレジーム ($q \sim 1/n$): 回復は、非逆トラックパス（または長さ $\log n$ の自己回避パス）をカウントすることによって達成される。これは Chinら（2025）の結果を裏付けるものである。
• 中程度の疎・密レジーム ($q \sim n^{-\alpha}$):
  • $q \sim n^{-2/(m+1)}$ の場合、$m$-クリークをカウントすることで回復が可能である。
  • $q \sim n^{-(m-2)/(m-1)}$ の場合、長さ $m-1$ の自己回避パスをカウントすることで回復が可能である。
  • 一般的な有理指数の場合、ファスナー付きサイクル・ブローアップのモチーフが最適である。
• 結果: $\alpha \in (0, 1] \cap \mathbb{Q}$ である $q \sim n^{-\alpha}$ に対して、多項式時間での弱回復の相転移は、レベル $\lambda_c$（多項式対数因子の範囲内）で発生する。

4. 意義と主張

本論文は、多くのコミュニティが存在するレジーム（$K \ge \sqrt{n}$）における相転移に関して、Chinら（2025）の推測を支持する強力な証拠を提供すると主張している。

• レジームの統一: 本研究は、異なる密度レジームにおける計算障壁の理解を統一する。非逆トラックパスが疎なレジームにおいて最適である一方で、グラフがより密になるにつれて、より複雑なモチーフ（クリークやサイクル・ブローアップなど）が必要かつ最適になることを示している。
• モチーフの最適性: 本論文は、密度パラメータ $\alpha$ と最適なモチーフの幾何学的構造との間の直接的な関連性を確立している。グラフの疎さに応じて、最適なアルゴリズムの「形状」が変化することを示している。
• 限界と未解決問題:
  • 著者らは、自分たちの境界値には（上下の境界が定数項のレベルで一致していないため）多項式対数因子が含まれていることを認めている。
  • 有理数ではない密度指数の場合、回復は次数 $O(\log n / \log \log n)$ の多項式によって可能であるが、そのような多項式が厳密な多項式時間内に計算可能かどうかは依然として未解決の問いである。
  • 相転移の正確な位置（鋭いものか緩やかなものか）、および正確な定数を持つアルゴリズムの存在は、依然として開かれた問題である。

要約すると、本論文は $K \ge \sqrt{n}$ の場合のコミュニティ回復の計算閾値を厳密に特徴付けており、その障壁が、コミュニティ数、グラフ密度、およびそれらを検出するために必要なモチーフの複雑さの相互作用によって決定されることを証明している。