A Tractable Fully Bayesian Method for the Stochastic Block Model
This provides a more efficient method for researchers analyzing graph structures, though it appears incremental as it builds on existing Bayesian approaches.
The authors tackled the problem of Bayesian inference in stochastic block models for graph clustering and model selection, deriving a tractable algorithm that solves both tasks concurrently without needing to check all model candidates, with empirical and theoretical results showing scalability, accuracy, and conciseness.
The stochastic block model (SBM) is a generative model revealing macroscopic structures in graphs. Bayesian methods are used for (i) cluster assignment inference and (ii) model selection for the number of clusters. In this paper, we study the behavior of Bayesian inference in the SBM in the large sample limit. Combining variational approximation and Laplace's method, a consistent criterion of the fully marginalized log-likelihood is established. Based on that, we derive a tractable algorithm that solves tasks (i) and (ii) concurrently, obviating the need for an outer loop to check all model candidates. Our empirical and theoretical results demonstrate that our method is scalable in computation, accurate in approximation, and concise in model selection.