# A Schur Complement Cheeger Inequality

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

## Key facts

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

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

- [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)

Cheeger's inequality shows that any undirected graph G with minimum nonzero normalized Laplacian eigenvalue λG has a cut with conductance at most O(√λG). Qualitatively, Cheeger's inequality says that if the relaxation time of a graph is high, there is a cut that certifies this. However, there is a gap in this relationship, as cuts can have conductance as low as Theta(λG). To better approximate the relaxation time of a graph, we consider a more general object. Instead of bounding the mixing time with cuts, we bound it with cuts in graphs obtained by Schur complementing out vertices from the graph G. Combinatorially, these Schur complements describe random walks in G restricted to a subset of its vertices. As a result, all Schur complement cuts have conductance at least Omega(λG). We show that unlike with cuts, this inequality is tight up to a constant factor. Specifically, there is a Schur complement cut with conductance at most O(λG).