Uncertainty quantification in the stochastic block model with an unknown number of classes
Preprint
Abstract
We study the frequentist properties of Bayesian statistical inference for the stochastic block model, with an unknown number of classes of varying sizes. We equip the space of vertex labellings with a prior on the number of classes and, conditionally, a prior on the labels. The number of classes may grow to infinity as a function of the number of vertices, depending on the sparsity of the graph. We derive non-asymptotic posterior contraction rates of the form $P_{\theta_{0,n}}\Pi_n(B_n\mid X^n)\le \epsilon_n$, where $X^n$ is the observed graph, generated according to $P_{\theta_{0,n}}$, $B_n$ is either $\{\theta_{0, n}\}$ or, in the very sparse case, a ball around $\theta_{0,n}$ of known extent, and $\epsilon_n$ is an explicit rate of convergence. These results enable conversion of credible sets to confidence sets. In the sparse case, credible tests are shown to be confidence sets. In the very sparse case, credible sets are enlarged to form confidence sets. Confidence levels are explicit, for each $n$, as a function of the credible level and the rate of convergence. Hypothesis testing between the number of classes is considered with the help of posterior odds, and is shown to be consistent. Explicit upper bounds on errors of the first and second type and an explicit lower bound on the power of the tests are given.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Posterior Contraction Rates for Stochastic Block ModelsSankhya A, 2020
- Probabilistic Community Detection With Unknown Number of CommunitiesJournal of the American Statistical Association, 2018
- Proof of the Achievability Conjectures for the General Stochastic Block ModelCommunications on Pure and Applied Mathematics, 2017
- Minimax rates of community detection in stochastic block modelsThe Annals of Statistics, 2016
- Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery2015
- Classification and estimation in the Stochastic Blockmodel based on the empirical degreesElectronic Journal of Statistics, 2012
- Integration of biological networks and gene expression data using CytoscapeNature Protocols, 2007
- Detecting functional modules in the yeast protein–protein interaction networkBioinformatics, 2006
- Asymptotic Methods in Statistical Decision Theory1986
- Stochastic blockmodels: First stepsSocial Networks, 1983