Research map / Learning theory and algorithms / Clustering
On the Robustness of Spectral Algorithms for Semirandom 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.
Shows unnormalized spectral bisection stays strongly consistent under monotone semirandom adversaries (adding internal edges to SSBM/NSSBM and DCM), while normalized spectral bisection can misclassify a constant fraction of vertices.
Problem
Determining which semirandom (monotone, helpful-adversary) models allow Laplacian-based spectral bisection to exactly recover planted communities, and how normalized vs. unnormalized Laplacians compare under such adversaries.
Approach
Uses a Davis-Kahan style perturbation plus entrywise leave-one-out analysis of the second eigenvector of the unnormalized Laplacian, noting internal edges are orthogonal to the ideal eigenvector u2* so adversarial internal edge insertions do not disturb it; constructs an NSSBM instance where a sparse cut inside P1 misleads the normalized Laplacian.
Key results
- Unnormalized spectral bisection is strongly consistent under NSSBM with gap condition n(p-q) >= C(sqrt(n pbar log n)+log n).
- Normalized spectral bisection (symmetric and random-walk) incurs misclassification of at least 24% with probability 1-1/n on a constructed NSSBM instance with pbar=6p, q=p/2.
- In numerical experiments (n=2000), unnormalized spectral bisection achieves 100% agreement for all pbar while normalized variants drop below 70% before the predicted threshold.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the unnormalized Laplacian rather than the normalized Laplacian | Spectral bisection on NSSBM instances · NSSBM | recovery quality | Helped |
| Increase internal edge probabilities while keeping crossing-edge probability q fixed | Unnormalized spectral bisection · Benchmark distribution, varying internal probability | agreement: 100% | No clear effect |
| Increase internal edge probabilities while keeping crossing-edge probability q fixed | Normalized spectral bisection and other tested matrices · Benchmark distribution, varying internal probability | agreement: below 70% | Hurt |
| Use a sweep cut of n/2 vertices instead of classifying by eigenvector signs (ablation) | Unnormalized Laplacian spectral bisection · Benchmark distribution, sweep cut | agreement: 100% | No clear effect |
Surprising findings
- Normalized spectral clustering, usually favored, is inconsistent under helpful monotone adversaries while unnormalized is strongly consistent.
- Unnormalized spectral bisection remains exactly correct even when the adversary adds many internal edges, with the eigenvector concentrating more strongly around the ideal one.
Limitations
- Only insertion-only monotone adversaries; crossing edge deletions are not allowed.
- Gap conditions have non-optimal constants and require internal edge probabilities bounded by pbar.
- Experiments are small-scale synthetic graphs run on CPU-only Colab.
Experimental setup
Datasets: synthetic graphs from NSSBM and DCM distributions
Benchmarks: synthetic NSSBM benchmark distribution n=2000
Metrics: agreement with planted bisection strong consistency
Baselines: normalized spectral bisection adjacency spectral bisection
Builds on: Davis-Kahan theorem stochastic block model semirandom model
Closest papers by meaning
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.89)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.89)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.89)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.88)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.88)
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.