When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?

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(ρ, √ρ k2/n2) 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≥ n√ρ. 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).