A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model
Abstract
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(π,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(π,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(π,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.
Related
- Optimal Community Recovery by Spectrally Initialized Variational EM in General Stochastic Block Models
- A Model-threshold Dimension Bound and Sharp Critical Ends for Smooth Singular Sets of Constant Positive σk-curvature Metrics
- Dual-Corrected Stochastic Block Model (DC2SBM): A Generalized Structure Detection Method for Attributed Networks
- A stochastic Carleson embedding theorem with constant e and the vector of Riesz transforms
- The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
BibTeX
@misc{arts2026threshold,
title = {{A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model}},
author = {Lucie Arts},
howpublished = {HAL},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2609.15793},
eprint = {2609.15793},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05732032v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model
AU - Lucie Arts
PY - 2026
DA - 2026/08/31
PB - HAL
DO - 10.48550/arxiv.2609.15793
UR - https://hal.science/hal-05732032v1
AB - 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(π,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(π,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(π,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.
ER -