# Improved Analysis of Spectral Algorithm for Clustering

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2019.

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

- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization](https://mlsanity.com/paper/2408.10084/) (2024)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [An Improved and Generalised Analysis for Spectral Clustering](https://mlsanity.com/paper/2511.23261/) (2025)
- [Topology-induced Operators Reveal Complementary Graph Representations without Training](https://mlsanity.com/paper/2609.08152/) (2026)

## Abstract (arXiv)

Spectral algorithms are graph partitioning algorithms that partition a node set of a graph into groups by using a spectral embedding map. Clustering techniques based on the algorithms are referred to as spectral clustering and are widely used in data analysis. To gain a better understanding of why spectral clustering is successful, Peng et al. (2015) and Kolev and Mehlhorn (2016) studied the behavior of a certain type of spectral algorithm for a class of graphs, called well-clustered graphs. Specifically, they put an assumption on graphs and showed the performance guarantee of the spectral algorithm under it. The algorithm they studied used the spectral embedding map developed by Shi and Malic (2000). In this paper, we improve on their results, giving a better performance guarantee under a weaker assumption. We also evaluate the performance of the spectral algorithm with the spectral embedding map developed by Ng et al. (2001).