# Impact of regularization on Spectral Clustering

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2013.

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

- [Hessian Eigenspectra of More Realistic Nonlinear Models](https://mlsanity.com/paper/2103.01519/) (2021)
- [Topological Relational Learning on Graphs](https://mlsanity.com/paper/2110.15529/) (2021)
- [A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning](https://mlsanity.com/paper/2311.03524/) (2023)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [Robust and Communication-Efficient Federated Domain Adaptation via Random Features](https://mlsanity.com/paper/2311.04686/) (2023)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Community detection by spectral methods in multi-layer networks](https://mlsanity.com/paper/2403.12540/) (2024)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings](https://mlsanity.com/paper/2109.04526/) (2021)
- [Consistency between ordering and clustering methods for graphs](https://mlsanity.com/paper/2208.12933/) (2022)
- [Latent class analysis by regularized spectral clustering](https://mlsanity.com/paper/2310.18727/) (2023)
- [Overlapping and nonoverlapping models](https://mlsanity.com/paper/2111.01392/) (2021)
- [Latent class analysis with weighted responses](https://mlsanity.com/paper/2310.10984/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Latent class analysis for multi-layer categorical data](https://mlsanity.com/paper/2408.05535/) (2024)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)
- [Goodness-of-Fit Tests for Latent Class Models with Ordinal Categorical Data](https://mlsanity.com/paper/2602.21572/) (2026)
- [A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation](https://mlsanity.com/paper/2609.09211/) (2026)
- [Exact Community Recovery in Bipartite Networks](https://mlsanity.com/paper/2609.12445/) (2026)

## Abstract (arXiv)

The performance of spectral clustering can be considerably improved via regularization, as demonstrated empirically in Amini et. al (2012). Here, we provide an attempt at quantifying this improvement through theoretical analysis. Under the stochastic block model (SBM), and its extensions, previous results on spectral clustering relied on the minimum degree of the graph being sufficiently large for its good performance. By examining the scenario where the regularization parameter τ is large we show that the minimum degree assumption can potentially be removed. As a special case, for an SBM with two blocks, the results require the maximum degree to be large (grow faster than log n) as opposed to the minimum degree. More importantly, we show the usefulness of regularization in situations where not all nodes belong to well-defined clusters. Our results rely on a `bias-variance'-like trade-off that arises from understanding the concentration of the sample Laplacian and the eigen gap as a function of the regularization parameter. As a byproduct of our bounds, we propose a data-driven technique textitDKest (standing for estimated Davis-Kahan bounds) for choosing the regularization parameter. This technique is shown to work well through simulations and on a real data set.