# Understanding Regularized Spectral Clustering via Graph Conductance

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

## Key facts

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

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

- [BrainGB: A Benchmark for Brain Network Analysis with Graph Neural Networks](https://mlsanity.com/paper/2204.07054/) (2022)
- [Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods](https://mlsanity.com/paper/2111.04840/) (2021)
- [On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs](https://mlsanity.com/paper/2107.01495/) (2021)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Quantifying Structure in CLIP Embeddings: A Statistical Framework for Concept Interpretation](https://mlsanity.com/paper/2506.13831/) (2025)
- [Intensity Profile Projection: A Framework for Continuous-Time Representation Learning for Dynamic Networks](https://mlsanity.com/paper/2306.06155/) (2023)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Deep Contrastive Graph Representation via Adaptive Homotopy Learning](https://mlsanity.com/paper/2106.09244/) (2021)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)
- [Consistency between ordering and clustering methods for graphs](https://mlsanity.com/paper/2208.12933/) (2022)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Unfolded Laplacian Spectral Embedding: A Theoretically Grounded Approach to Dynamic Network Representation](https://mlsanity.com/paper/2508.12674/) (2025)
- [Ideological Isolation in Online Social Networks: A Survey of Computational Definitions, Metrics, and Mitigation Strategies](https://mlsanity.com/paper/2601.07884/) (2026)

## Abstract (arXiv)

This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochastic graphs create a lot of small trees that are connected to the core of the graph by only one edge. Graph conductance is sensitive to these noisy `dangling sets'. Spectral clustering inherits this sensitivity. The second part of the paper starts from a previously proposed form of regularized spectral clustering and shows that it is related to the graph conductance on a `regularized graph'. We call the conductance on the regularized graph CoreCut. Based upon previous arguments that relate graph conductance to spectral clustering (e.g. Cheeger inequality), minimizing CoreCut relaxes to regularized spectral clustering. Simple inspection of CoreCut reveals why it is less sensitive to small cuts in the graph. Together, these results show that unbalanced partitions from spectral clustering can be understood as overfitting to noise in the periphery of a sparse and stochastic graph. Regularization fixes this overfitting. In addition to this statistical benefit, these results also demonstrate how regularization can improve the computational speed of spectral clustering. We provide simulations and data examples to illustrate these results.