Research map / Graph learning / Graph algorithms and clustering
Query-Limited Community Recovery in Stochastic Block Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies exact recovery in a two-community logarithmic-degree SBM when the learner can only query a one-sided noisy neighborhood oracle (oracle-only) or also observes a subsampled graph, showing adaptive querying beats uniform querying in both settings.
Problem
Exact community recovery in the two-community SBM under limited, noisy, budgeted access via a noisy neighborhood oracle, with and without an initial subsampled graph.
Approach
Models data acquisition as part of inference: a two-stage adaptive strategy (coarse global sketch, then leave-one-out screening and refinement of a sublinear uncertain set) can beat balanced uniform querying in the oracle-only linear regime, and with a subsampled graph yields a sublinear-budget adaptivity gap.
Key results
- Two-stage adaptive strategy succeeds with n+o(n) queries for alpha=16, beta=1, w=1-2^{-1/6}, where balanced uniform querying needs about 1.087n queries.
- Every oracle-only exact-recovery strategy requires Omega(n) queries.
- With a sublinear budget k=o(n) and a subsampled graph, uniform querying fails while adaptive targeting achieves exact recovery (theorem with alpha=16, beta=1, w=1/2, s=2(1-eps)/9).
Surprising findings
- Balanced uniform querying is not adaptively optimal in the oracle-only linear regime; adaptivity improves the linear constant.
- Data-independent sublinear uniform querying gives no improvement over the subsampled graph alone, while adaptive targeting does.
Limitations
- Results are asymptotic and restricted to the balanced two-community logarithmic-degree SBM with independent one-sided oracle noise.
- Sharp optimal constants and a full adaptive phase diagram are not characterized.
- Non-divisible budgets are handled only up to a one-query rounding window.
Experimental setup
Metrics: exact recovery probability overlap query complexity
Baselines: balanced uniform querying subsampled graph alone
Builds on: Abbe-Bandeira-Hall exact recovery threshold maximum likelihood estimation for SBM subsampled correlated SBM
Closest papers by meaning
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.90)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.90)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.89)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.89)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.87)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.