# Consistency of Cheeger and Ratio Graph Cuts

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2014.

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

- [The Geometry of Adversarial Training in Binary Classification](https://mlsanity.com/paper/2111.13613/) (2021)
- [Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning](https://mlsanity.com/paper/2211.15223/) (2022)
- [Towards Understanding the Mechanism of Contrastive Learning via Similarity Structure: A Theoretical Analysis](https://mlsanity.com/paper/2304.00395/) (2023)
- [Understanding the Generalization Performance of Spectral Clustering Algorithms](https://mlsanity.com/paper/2205.00281/) (2022)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)

## Abstract (arXiv)

This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective functionals defined on proximity graphs of the given sample. Our focus is on functionals based on graph cuts like the Cheeger and ratio cuts. We show that minimizers of the these cuts converge as the sample size increases to a minimizer of a corresponding continuum cut (which partitions the ground truth measure). Moreover, we obtain sharp conditions on how the connectivity radius can be scaled with respect to the number of sample points for the consistency to hold. We provide results for two-way and for multiway cuts. Furthermore we provide numerical experiments that illustrate the results and explore the optimality of scaling in dimension two.