Many Sparse Cuts via Higher Eigenvalues

Cheeger’s fundamental inequality states that any edge-weighted graph has a vertex subset S such that its expansion (a.k.a. conductance) is bounded as follows: φ(S) def w(S, S̄) min{w(S), w(S̄)} 6 2 λ2, where w is the total edge weight of a subset or a cut and λ2 is the second smallest eigenvalue of the normalized Laplacian of the graph. Here we prove the following natural generalization: for any integer k ∈ [n], there exist ck disjoint subsets S1,..., Sck, such that max i φ(Si) 6 C λk log k where λi is the i th smallest eigenvalue of the normalized Laplacian and c < 1, C> 0 are suitable absolute constants. Our proof is via a polynomial-time algorithm to find such subsets, consisting of a spectral projection and a randomized rounding. As a consequence, we get the same upper bound for the small set expansion problem, namely for any k, there is a subset S whose weight is at most a O(1/k) fraction of the total weight and φ(S) 6 C λk log k. Both results are the best possible up to constant factors. The underlying algorithmic problem, namely finding k subsets such that the maximum expansion is minimized, besides extending sparse cuts to more than one subset, appears to be a natural clustering problem in its own right