Query-Limited Community Recovery in Stochastic Block Models
Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi · 2026
Read Query-Limited Community Recovery in Stochastic Block Models by Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02055.txt.
Introduction
Basu and co-authors study community recovery with few, noisy network queries. The network follows a two-community stochastic block model. A learner may query a noisy neighborhood oracle. Each true neighbor shows up with a fixed chance. Non-neighbors are never returned by the oracle. A finite query budget limits the whole search.
Balanced uniform querying gives a sharp baseline result. Equal queries per vertex reduce the data to a weaker block model. Known exact-recovery thresholds then apply directly. But that baseline is not the best adaptive choice. A two-stage adaptive strategy does better, they show. It succeeds with about n queries in a hard regime. A single subsampled graph copy can also help.
Catalog record
| CREATOR | Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02055
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Query-Limited Community Recovery in Stochastic Block Models Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi Abstract We study exact community recovery in the two-community stochastic block model on n 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 ) n+o(n) queries in a regime where balanced uniform querying requires m n mn queries for some m > 1 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. 0 0 footnotetext: Authors are listed in alphabetical order. Keywords. Stochastic block model, Community detection, Adaptive querying, Query complexity 1 Introduction Recovering latent community structure from network data is a fundamental problem in machine learning, statistics, and network science, with applications ranging from social and communication networks to biological and information systems [ 20 ] . The stochastic block model (SBM) is a canonical random-graph model for this task: in its simplest two-community form each vertex (among n vertices) belongs to one of two communities, an edge between two vertices is present with probability p if they are in the same community and with probability q otherwise. This model, introduced by Holland, Laskey, and Leinhardt [ 19 ] , and widely studied since, has become a standard framework for understanding the statistical and algorithmic limits of community detection. A central task here is exact recovery : reconstructing all community labels, up to a global label flip, from the observed graph. In the sparse logarithmic-degree regime, where p=\alpha\frac{\log n}{n} and q=\beta\frac{\log n}{n} , exact recovery exhibits a sharp phase transition governed by the quantity (\sqrt{\alpha}-\sqrt{\beta})^{2} : in particular, recovery is information-theoretically possible precisely above the classical Abbe–Bandeira–Hall threshold [ 3 ] . In many applications, however, the full graph is not directly observable. Edges may be missing because of subsampling, privacy restrictions, incomplete crawls, or noisy measurements, and additional information may be available only through local probes such as API queries, experiments, or surveys [ 18 , 24 , 30 ] . Motivated by such settings, prior work has investigated how additional imperfect observations—such as multiple correlated or subsampled graphs—can change the information-theoretic limits of exact recovery [ 17 , 28 ] . In these models, the observation mechanism is exogenous: it is specified ex ante by a fixed probabilistic model, independent of the procedure for exact recovery [ 17 , 28 , 29 , 1 ] . In this paper, we study a complementary source of information. Concretely, we introduce a query-limited model with access to a noisy neighborhood oracle: when queried at a vertex, the oracle reveals each true neighbor independently with probability w and never returns non-neighbors. Subject to a total budget of k queries, the learner must decide which vertices to query and how to allocate its queries. This model is closely related to edge subsampling, since both mechanisms introduce one-sided observation noise. But the key difference is operational: in a subsampled graph, the observation pattern is fixed independently of the learner, whereas in the oracle model the learner chooses where information is acquired, possibly non-uniformly and adaptively. This leads to a natural question: when can adaptive oracle querying improve exact recovery over uniform querying, and what initial information is required for such an improvement? We investigate this question in two models. In the oracle-only model, the learner has no initial graph observation and only has access to a noisy-neighborhood oracle. In the subsampled-graph-plus-oracle model, the learner first observes a subsampled graph G_{\mathrm{sub}} and may then use oracle queries to refine the recovery. This two-part formulation separates the case in which adaptivity can only improve constants from the case in which even coarse side information enables a sublinear-query adaptivity gap. Our work connects exact recovery to adaptive data acquisition for network inference. When local measurements are expensive, the learner must decide not only how to infer communities from partial observations, but also how to allocate a limited budget to enable exact recovery. Such measurements may come from API calls, experiments, surveys, or other procedures that reveal incomplete local neighborhood information. In this case, one can start with uniform querying as a natural baseline, but it need not be the most efficient strategy once a coarse global estimate can identify vertices that remain difficult to classify. Our results identify regimes in which adaptive querying can selectively target these “difficult” vertices and thereby improve the information-theoretic limits of exact recovery. In this sense, our work extends beyond exogenous observation settings studied in the literature on exact-recovery in the SBM with correlated side information, i.e., where the observation mechanism is fixed in advance, by making (adaptive) data acquisition itself part of the inference problem. Our contributions are as follows: 1 1 1 Omitted details and full proofs are available in the appendix. ( i ) A budgeted noisy-neighborhood oracle model. We introduce a query-limited noisy-neighborhood-oracle model for the logarithmic-degree two-community SBM. The oracle gives local observations with one-sided error, but unlike passive subsampling, the learner controls where those observations are made and may allocate queries adaptively. Thus exact recovery depends not only on how much information is available, but also on how it is acquired. ( ii ) Oracle-only access: a linear-regime adaptivity gap. We first analyze the oracle-only setting. For balanced uniform querying, where each vertex is queried the same (integer) number of times, the observed graph is again an SBM with attenuated edge probabilities. This gives a sharp threshold for uniform sampling via the Abbe-Bandeira-Hall criterion, with effective edge-retention factor \theta_{\mathrm{unif}}=1-(1-w)^{2k/n}. We then show that uniform querying is not necessarily optimal. For an explicit choice of parameters, a two-stage adaptive strategy first constructs a rough global sketch, identifies a sublinear set of uncertain vertices, and then spends additional queries only on that set. This strategy succeeds with n+o(n) queries, whereas balanced uniform querying requires x_{\star}n queries for some x_{\star}>1 . We also show that every successful oracle-only strategy requires \Omega(n) queries, so the adaptive construction matches the optimal query order while improving the uniform constant. ( iii ) Subsampled graph plus oracle access: a sublinear adaptivity gap. We next consider the setting in which the learner is also given a subsampled copy of the graph. In this case, the subsampled graph provides an initial global sketch before any oracle queries are made. We show that, with a sublinear budget