Research map / Learning theory and algorithms / Clustering
Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
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.
Derives necessary and sufficient instance-specific conditions for expected misclassification below s in the labeled SBM and proposes IAC, a one-shot spectral clustering plus likelihood-based refinement algorithm that matches the bound in expectation and w.h.p.
Problem
Exact characterization of when hidden communities in the Labeled Stochastic Block Model can be recovered with expected misclassified nodes below s = o(n), with instance-specific (not minimax) guarantees and efficient computation.
Approach
Two-phase algorithm: a single spectral clustering pass (power method with singular value thresholding, trimming) followed by log n rounds of likelihood-based reassignment using empirically estimated label distributions; the analysis matches an instance-specific divergence D(alpha,p) lower bound in expectation, unlike prior minimax or high-probability-only results.
Key results
- Shows necessary and sufficient condition liminf n D(alpha,p)/log(n/s) >= 1 for expected misclassification at most s, for any s = o(n).
- IAC achieves this bound both in expectation and with high probability, with O(n (log n)^3) floating-point operations.
- Spectral initialization misclassifies O(1/p-bar) nodes w.p. at least 1 - exp(-c n p-bar); the likelihood refinement contracts errors by a factor 1/sqrt(n p-bar) per step.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IAC under the condition \liminf_{n\to\infty} nD(\alpha,p)/\log(n/s) \ge 1 | LSBM clustering · LSBM | expected misclassified nodes | Helped |
| Use IAC under the condition \liminf_{n\to\infty} nD(\alpha,p)/\log(n/s) \ge 1 | LSBM clustering · LSBM | misclassified nodes with high probability | Helped |
| Add iterative likelihood-based local improvement after spectral initialization | IAC · LSBM | misclassified nodes in H after each iteration: 1/\sqrt{n\bar{p}} | Helped |
Surprising findings
- Spectral clustering alone is conjectured to be insufficient for optimal rates in general LSBM because the optimal decision boundary is asymmetric, requiring non-Euclidean likelihood-based refinement.
Limitations
- Assumes fixed number of clusters K and linearly growing cluster sizes with constant alpha.
- Requires assumptions (A1)-(A3) including bounded likelihood ratios and sparse label regime p-bar = O(log n / n).
- Empirical evaluation details and code are not provided in the main text.
Experimental setup
Metrics: expected number of misclassified nodes high-probability misclassification bound computational complexity
Baselines: penalized local maximum likelihood estimation (Gao et al.) instance-specific LSBM algorithm (Abbe-Sandon style two-phase) minimax-optimal SBM algorithms
Builds on: stochastic block model Labeled Stochastic Block Model spectral clustering with power method penalized maximum likelihood for SBM recovery
Closest papers by meaning
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.90)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.89)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.89)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.88)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.87)
- Efficient Graph Matching for Correlated 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.