A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model

Overview & Synopsis

We study exact community recovery in the Degree-Corrected Poisson Stochastic Block Model (DC-SBM) through the maximum profile likelihood estimator. Our main contribution is identifying an explicit complexity constant $C(\pi,S)$, which closely captures the exact recovery threshold. This constant combines a weighted Chernoff--Hellinger separation between communities with a Kullback--Leibler correction induced by the degree-normalized block volumes. We rigorously prove that $C(\pi,S)>1$ ensures the strong consistency of the maximum profile likelihood estimator, yielding exact community recovery down to the logarithmic sparsity scale. We conjecture that $C(\pi,S)=1$ represents the sharp information-theoretic threshold, providing an upper bound on the exact-recovery transition, and we discuss analogies with the binary SBM and binary DC-SBM cases. Additionally, we establish weak consistency when the average degree diverges, offering a unified picture across sparse and dense regimes. The proofs require new control of the profile likelihood in the presence of heterogeneous degree parameters, whose node-specific weights fundamentally alter the geometry and concentration of the recovery problem.