Abstract:

In a sparse stochastic block model with two communities of
unequal sizes we derive two posterior concentration inequalities, that
imply (1) posterior (almost-)exact recovery of the community structure
under sparsity bounds comparable to well-known sharp bounds in the
planted bi-section model; (2) a construction of confidence sets for the
community assignment from credible sets, with finite graph sizes. The
latter enables exact frequentist uncertain quantification with Bayesian
credible sets at non-asymptotic graph sizes, where posteriors can be
simulated well. There turns out to be no proportionality between
credible and confidence levels: for given edge probabilities and a
desired confidence level, there exists a critical graph size where the
required credible level drops sharply from close to one to close to
zero. At such graph sizes the frequentist decides to include not most of
the posterior support for the construction of his confidence set, but
only a small subset of community assignments containing the highest
amounts of posterior probability (like the maximum-a-posteriori
estimator). It is argued that for the proposed construction of
confidence sets, a form of early stopping applies to MCMC sampling of
the posterior, which would enable the computation of confidence sets at
larger graph sizes.
Paper available at: https://arxiv.org/abs/2108.07078