📊 statistics

Query-Limited Community Recovery in Stochastic Block Models

This paper demonstrates that adaptive querying strategies can strictly improve the information-theoretic limits of exact community recovery in Stochastic Block Models under limited and noisy data access, achieving success with significantly fewer queries than non-adaptive uniform approaches.

Original authors: Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi

Published 2026-06-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive mystery: a city of $n$ people is divided into two secret groups (let's call them Team Red and Team Blue). You don't know who belongs to which team, but you know that people on the same team are more likely to be friends with each other than with people on the other team. Your goal is to figure out the team of every single person perfectly.

Usually, you would just look at a complete map of all friendships. But in this paper, the authors imagine a scenario where that map is broken, blurry, or missing huge chunks. You can't see the whole picture. Instead, you have a limited budget of "magic questions" you can ask.

The Magic Question (The Oracle)

Think of a "Noisy Neighborhood Oracle" as a slightly unreliable detective. If you ask the detective about a specific person (let's call them Alice), the detective will try to list Alice's friends.

The Catch: The detective is honest but forgetful. If Alice is friends with Bob, the detective might forget to mention Bob (with a fixed probability).
The Good News: The detective never lies. If the detective says "Alice is friends with Bob," then they definitely are. They just miss some true friends.
The Limit: You only have a limited number of questions (a budget) to ask. You can't ask about everyone.

The paper asks: How should you spend your limited questions to solve the mystery?

The Two Strategies

The authors compare two ways of spending your questions:

1. The "Fair Share" Strategy (Uniform Querying)
Imagine you have 100 questions and 100 people. The "Fair Share" strategy says: "Let's just ask one question about every single person." You treat everyone the same.

The Result: This works, but it's inefficient. You might waste questions on people who are already easy to figure out, while not having enough questions left to solve the tricky cases. It's like using a sledgehammer to crack a nut, then realizing you don't have enough sledgehammers left for the hard nuts.

2. The "Smart Detective" Strategy (Adaptive Querying)
This strategy is like a detective who thinks before they act.

Step 1: You ask a few questions about everyone just to get a rough sketch. You might not know everyone's team yet, but you can spot the "confusing" people—those whose friends seem to belong to both teams equally.
Step 2: You stop asking about the easy people (who are clearly Red or Blue). You save all your remaining questions to focus only on the confusing people.
The Result: By targeting your limited resources where they are needed most, you can solve the mystery perfectly even when the "Fair Share" strategy fails.

The Two Scenarios

The paper tests this idea in two different situations:

Scenario A: The Blank Slate (Oracle-Only)
You have no map at all. You only have your magic questions.

The Finding: Even here, the "Smart Detective" wins. If you use the "Fair Share" method, you might need, say, 1.1 questions per person to solve it. But the "Smart Detective" can solve it with just 1.0 question per person (plus a tiny bit extra for the hard cases).
The Analogy: It's like trying to find a needle in a haystack by poking the whole haystack evenly vs. poking the spots that look most suspicious. The smart way saves you a little bit of effort, but you still need to poke almost the whole haystack.

Scenario B: The Cracked Map (Subsampled Graph + Oracle)
Now, imagine you are given a cracked, blurry map first. It shows some friendships, but many are missing. You can't solve the mystery with just this map. Then, you get your limited magic questions to fix the map.

The "Fair Share" Failure: If you use the "Fair Share" strategy here, you waste your questions on people the map already shows clearly. You end up with a budget of questions that is too small to fix the blurry parts. You fail.
The "Smart Detective" Success: The "Smart Detective" looks at the blurry map, spots exactly which people are still confusing, and uses all their questions to fix just those specific spots.
The Big Win: In this scenario, the "Smart Detective" can solve the mystery with a budget of questions that is tiny (sublinear) compared to the size of the city. The "Fair Share" strategy fails completely. This is a massive difference. It's like being able to fix a broken window with a single piece of tape if you know exactly where the crack is, whereas trying to tape the whole window frame would use up all your tape and still leave it broken.

The Secret Weapon: "Leave-One-Out" Screening

How does the "Smart Detective" know who is confusing without making mistakes? The paper uses a clever trick called "Leave-One-Out Screening."

Imagine you are trying to guess if Alice is on Team Red.

You look at all her friends except one specific friend, Bob.
You guess Alice's team based on everyone except Bob.
Then, you ask your magic question specifically about Bob to see if he confirms or denies your guess.

By separating the "clues used to make the guess" from the "clues used to check the guess," the detective avoids tricking themselves. This ensures that when they decide to spend their precious remaining questions on a "confusing" person, they are actually right about that person being confusing.

The Bottom Line

The paper proves that how you gather information matters just as much as how much information you gather.

If you have a limited budget of noisy checks, blindly checking everyone is inefficient.
If you have a rough draft of the data (a blurry map), using a smart, two-step strategy to target your limited budget on the "hard-to-figure-out" parts allows you to solve the puzzle perfectly, whereas a random or uniform approach will fail.

In short: Don't spread your questions thin; aim them at the trouble spots.

Technical Summary: Query-Limited Community Recovery in Stochastic Block Models

Problem Formulation
This paper investigates the problem of exact community recovery in the two-community Stochastic Block Model (SBM) on $n$ vertices under conditions of limited and noisy data access. The underlying graph $G \sim \text{SBM}(n, p, q)$ is defined with edge probabilities $p = \alpha \frac{\log n}{n}$ and $q = \beta \frac{\log n}{n}$ for vertices within and between communities, respectively. The learner does not observe the full graph directly. Instead, access is granted through a noisy neighborhood oracle and, in a secondary model, a subsampled graph.

The oracle operates with one-sided noise: when a vertex $v$ is queried, the oracle reveals each true neighbor independently with probability $w$ and never reports non-neighbors. The learner operates under a finite query budget $k$ . The core challenge is to determine how the allocation of these queries—specifically, the trade-off between uniform (non-adaptive) and adaptive strategies—affects the information-theoretic thresholds for exact recovery (recovering all labels up to a global flip).

The authors analyze two distinct settings:

Oracle-Only Access: The learner has no initial graph observation and relies entirely on the oracle transcript.
Subsampled Graph Plus Oracle: The learner first observes a subsampled graph $G_{sub}$ (where edges are retained with probability $s$ ) and then uses the oracle to refine the recovery.

Methodology and Technical Approach
The paper contrasts non-adaptive uniform querying with adaptive two-stage strategies. A primary technical hurdle identified is that adaptive querying disrupts the homogeneous observation structure standard in SBM analysis, as query counts become dependent on previous observations and the selection of vertices for refinement introduces bias.

To address this, the authors introduce a leave-one-out screening framework. This mechanism is distinct from its use in prior passive observation models; here, it serves as the structural engine for adaptive recovery. The framework operates as follows:

Separation of Data: For any vertex $v$ , the method partitions the available information into disjoint sets: a reference set used to construct a preliminary label (excluding edges incident to $v$ ), a screening set used to decide if $v$ is ambiguous, and a fresh comparison set reserved for the final likelihood test.
Two-Stage Strategy:
1. Stage 1 (Coarse Estimation): A budget is spent (uniformly or otherwise) to generate a rough global sketch and identify a "screened set" $A$ of vertices with uncertain labels.
2. Stage 2 (Refinement): The remaining budget is concentrated exclusively on the vertices in $A$ . Fresh oracle queries are used to classify these vertices against the pre-computed, disjoint reference sets.

Key Contributions and Results

1. Oracle-Only Model: Linear-Regime Adaptivity Gap

Uniform Benchmark: The authors establish that balanced uniform querying (where each vertex is queried $m = k/n$ times) reduces the problem to an SBM with attenuated edge probabilities. Exact recovery is possible if and only if $\theta_{unif}(k,w)(\sqrt{\alpha} - \sqrt{\beta})^2 > 2$ , where $\theta_{unif}$ is the edge-retention factor. This requires a linear query budget $k = \Omega(n)$ .
Adaptive Improvement: The paper demonstrates that uniform querying is not adaptively optimal. A two-stage adaptive strategy can achieve exact recovery with $n + o(n)$ queries in regimes where uniform querying requires $mn$ queries for some $m > 1$ .
Lower Bound: Despite the improvement in constants, the authors prove that any successful oracle-only strategy requires a linear number of queries ( $k = \Omega(n)$ ). Thus, adaptivity improves the constant factor in the linear regime but does not reduce the query complexity order.

2. Subsampled Graph Plus Oracle Model: Sublinear Adaptivity Gap

Uniform Failure: When a subsampled graph $G_{sub}$ is available, uniform querying with a sublinear budget ( $k = o(n)$ ) fails to improve the exact-recovery threshold beyond what $G_{sub}$ alone provides. If $G_{sub}$ is below the recovery threshold, uniform oracle queries cannot rescue the recovery because they cannot target the specific ambiguous vertices.
Adaptive Success: In contrast, an adaptive strategy can utilize $G_{sub}$ to identify a small set of uncertain vertices. By concentrating the sublinear budget exclusively on this set, the strategy achieves exact recovery in regimes where uniform querying fails.
Significance: This establishes a genuine sublinear adaptivity gap. Unlike the oracle-only model where the gap is in the linear constant, the presence of side information allows adaptive acquisition to fundamentally change the feasibility of exact recovery within a sublinear budget.

Significance and Claims
The paper claims to extend the literature on exact recovery in SBMs with correlated side information by making data acquisition itself part of the inference problem. While prior work treated observation mechanisms as exogenous (fixed in advance), this work treats the allocation of queries as a decision variable.

The authors identify specific regimes where:

Adaptive querying provides no information-theoretic benefit over uniform querying (e.g., in the oracle-only model with sublinear budgets, where recovery is impossible regardless of strategy).
Coarse side information (the subsampled graph) enables a genuine adaptivity gap, allowing adaptive strategies to succeed where uniform strategies fail with the same budget.

The work is theoretical and asymptotic, focusing on the information-theoretic limits of the balanced two-community logarithmic-degree SBM with independent one-sided oracle noise. It does not propose specific experimental deployments or claim immediate practical applications but aims to clarify the fundamental limits of limited local measurements in network recovery.