Search papers, labs, and topics across Lattice.
Microsoft ResearchAaltoIndraprastha Institute of InformationUniversity of LiverpoolJun 1, 2026arXiv:2606.02055This paper investigates community recovery in the two-community stochastic block model using limited and noisy network data access through a neighborhood oracle. The authors establish that while balanced uniform querying provides a non-adaptive benchmark for recovery, an adaptive two-stage querying strategy significantly reduces the number of required queries from \(mn\) to \(n+o(n)\) in certain scenarios. Additionally, they reveal that incorporating a subsampled graph does not enhance recovery under uniform querying, but adaptive querying can effectively target uncertain vertices to achieve exact recovery.
Adaptive querying can reduce the number of required queries for exact community recovery from linear to sublinear, challenging traditional benchmarks.
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.
