# On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models

arXiv: https://arxiv.org/abs/2412.14315 · HTML: https://mlsanity.com/paper/2412.14315/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 19 references that are in the map.
- First posted on arXiv 18 Dec 2024.

## Builds on (most cited first, 10 of 10)

- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [Dueling Optimization with a Monotone Adversary](https://mlsanity.com/paper/2311.11185/) (2023)
- [Community Detection on Euclidean Random Graphs](https://mlsanity.com/paper/1706.09942/) (2017)
- [Higher-Order Spectral Clustering for Geometric Graphs](https://mlsanity.com/paper/2009.11353/) (2020)
- [Matrix Perturbation: Davis-Kahan in the Infinity Norm](https://mlsanity.com/paper/2304.00328/) (2023)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)

## Built on by (most cited first, 2 of 2)

- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)

## Abstract (arXiv)

In a graph bisection problem, we are given a graph G with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second smallest eigenvalue of the Laplacian of G. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from certain probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. On the positive side, we identify classes of semirandom adversaries under which spectral bisection using the unnormalized_ Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in these classes spectral bisection with the normalized_ Laplacian outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.