# Query-Limited Community Recovery in Stochastic Block Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 25 of 25)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning](https://mlsanity.com/paper/2101.01669/) (2021)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Clustering attributed graphs: models, measures and methods](https://mlsanity.com/paper/1501.01676/) (2015)
- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1601.02658/) (2016)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Recovering communities in the general stochastic block model without knowing the parameters](https://mlsanity.com/paper/1506.03729/) (2015)
- [Fundamental Limits of Spectral Clustering in Stochastic Block Models](https://mlsanity.com/paper/2301.09289/) (2023)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [Community Detection via Random and Adaptive Sampling](https://mlsanity.com/paper/1402.3072/) (2014)
- [Information-theoretic Limits for Community Detection in Network Models](https://mlsanity.com/paper/1802.06104/) (2018)
- [Community Detection in Bipartite Networks with Stochastic Blockmodels](https://mlsanity.com/paper/2001.11818/) (2020)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)
- [Efficient Graph Matching for Correlated Stochastic Block Models](https://mlsanity.com/paper/2412.02661/) (2024)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Harnessing Multiple Correlated Networks for Exact Community Recovery](https://mlsanity.com/paper/2412.02796/) (2024)
- [Active Learning for Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1605.02372/) (2016)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Network two-sample test for block models](https://mlsanity.com/paper/2406.06014/) (2024)
- [Active Community Detection with Maximal Expected Model Change](https://mlsanity.com/paper/1801.05856/) (2018)
- [Understanding the Limitations of Network Online Learning](https://mlsanity.com/paper/2001.07607/) (2020)

## Abstract (arXiv)

We study exact community recovery in the two-community stochastic block model on n vertices under limited and noisy access to network data. The learner may query a noisy neighborhood oracle that reveals each true neighbor of a queried vertex independently with fixed probability and never returns non-neighbors, subject to a finite query budget. We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph. For oracle-only access, balanced uniform querying gives a sharp non-adaptive benchmark: when each vertex is queried the same integer number of times, the observations reduce to an SBM with attenuated edge probabilities and the Abbe-Bandeira-Hall exact-recovery threshold applies. We show that this benchmark is not adaptively optimal: a two-stage adaptive strategy succeeds with n+o(n) queries in a regime where balanced uniform querying requires m n queries for some m>1. With an additional subsampled graph, we prove a sublinear-query adaptivity gap: balanced data-independent uniform querying with a sublinear budget does not improve over the subsampled graph alone, whereas adaptive querying can target a small set of uncertain vertices and achieve exact recovery. Thus adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery.