When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
This work addresses the fundamental limits of graphon estimation, which is crucial for network analysis, but it is incremental as it builds on and confirms prior independent results.
The paper provides a lower bound on estimation accuracy for block graphons, showing that every estimator incurs error at least on the order of min(ρ, √(ρk²/n²)) in the δ₂ metric, ruling out nontrivial estimation when k ≥ n√ρ.
Block graphons (also called stochastic block models) are an important and widely-studied class of models for random networks. We provide a lower bound on the accuracy of estimators for block graphons with a large number of blocks. We show that, given only the number $k$ of blocks and an upper bound $ρ$ on the values (connection probabilities) of the graphon, every estimator incurs error at least on the order of $\min(ρ, \sqrt{ρk^2/n^2})$ in the $δ_2$ metric with constant probability, in the worst case over graphons. In particular, our bound rules out any nontrivial estimation (that is, with $δ_2$ error substantially less than $ρ$) when $k\geq n\sqrtρ$. Combined with previous upper and lower bounds, our results characterize, up to logarithmic terms, the minimax accuracy of graphon estimation in the $δ_2$ metric. A similar lower bound to ours was obtained independently by Klopp, Tsybakov and Verzelen (2016).