Bayesian estimation from few samples: community detection and related problems
This work addresses fundamental challenges in community detection for graph analysis, with potential applications in network science, but it appears incremental as it builds on existing methods like sum-of-squares and method of moments.
The authors tackled Bayesian estimation problems, particularly community detection in sparse graphs, by proposing a meta-algorithm based on low-degree polynomials and tensor decomposition, achieving tight sample complexity bounds that match or exceed known statistical and computational thresholds, including the first recovery guarantees for mixed-membership models in constant average degree graphs.
We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for community detection in the sparse stochastic block model, a widely-studied class of estimation problems for community detection in graphs. We obtain the first recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) in constant average degree graphs---up to what we conjecture to be the computational threshold for this model. We show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten--Stigum bound---giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the best-possible low-degree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments.