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

Abstract

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 (, 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 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).

Tasks

Reproductions