# Bayesian estimation from few samples: community detection and related problems

arXiv: https://arxiv.org/abs/1710.00264 · HTML: https://mlsanity.com/paper/1710.00264/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2017.

## Built on by (most cited first, 28 of 28)

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Curvature-based Clustering on Graphs](https://mlsanity.com/paper/2307.10155/) (2023)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Sliding down the stairs: how correlated latent variables accelerate learning with neural networks](https://mlsanity.com/paper/2404.08602/) (2024)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)
- [Matrix Estimation for Individual Fairness](https://mlsanity.com/paper/2302.02096/) (2023)
- [Streaming Belief Propagation for Community Detection](https://mlsanity.com/paper/2106.04805/) (2021)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Random Separating Hyperplane Theorem and Learning Polytopes](https://mlsanity.com/paper/2307.11371/) (2023)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)

## Abstract (arXiv)

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.