Query-Limited Community Recovery in Stochastic Block Models
Title: Achieving Exact Community Recovery in Stochastic Block Models with Minimal Queries
Abstract
This paper investigates the problem of exact community recovery within the two-community stochastic block model comprising $n$ vertices, focusing on scenarios where access to network data is constrained and noisy. The learning algorithm interacts with a noisy neighborhood oracle that, for each queried vertex, independently discloses its true neighbors with a fixed probability while never returning non-neighbors. This interaction is governed by a strict finite query budget. We analyze two distinct access frameworks: one relying solely on the oracle, and another combining oracle access with a single subsampled copy of the underlying graph.
In the oracle-only setting, we identify balanced uniform querying as a sharp non-adaptive baseline. Specifically, when every vertex is queried an identical integer number of times, the resulting observations effectively transform the problem into a Stochastic Block Model with reduced edge probabilities, allowing the application of the established Abbe-Bandeira-Hall exact-recovery threshold. However, we demonstrate that this non-adaptive benchmark is not adaptively optimal. By employing a two-stage adaptive strategy, exact recovery can be achieved using only $n+o(n)$ queries. This stands in contrast to balanced uniform querying, which necessitates $mn$ queries (where $m > 1$) in the same regime.
Furthermore, when a subsampled graph is available alongside oracle access, we establish the existence of a sublinear-query adaptivity gap. We prove that a data-independent uniform querying strategy with a sublinear budget offers no advantage over relying on the subsampled graph alone. In contrast, adaptive querying allows the learner to focus on a small subset of vertices with high uncertainty, thereby enabling exact recovery. These findings illustrate that adaptive data acquisition can strictly enhance the information-theoretic limits for exact recovery.
Source: arXiv Generated at: 2026-06-02 00:00:00 UTC
