# Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2013.

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

- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Spectral Augmentations for Graph Contrastive Learning](https://mlsanity.com/paper/2302.02909/) (2023)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Structure-Aware Spectral Sparsification via Uniform Edge Sampling](https://mlsanity.com/paper/2510.12669/) (2025)
- [Non asymptotic bounds in asynchronous sum-weight gossip protocols](https://mlsanity.com/paper/2111.10248/) (2021)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Self-Attention as Transport: Limits of Symmetric Spectral Diagnostics](https://mlsanity.com/paper/2605.04893/) (2026)

## Abstract (arXiv)

Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ1 <= λ2 <=... <= λn <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, φ(G) = O(k) λ2 / √λk, and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if λk is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.