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,bar{S}))/(min set(w(S), w(bar(S)))) ≤ √(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 S 1 , ..., S ck , such that [ max i φ(S i ) ≤ C √(λ k log k) ] where λ k is the kth smallest eigenvalue of the normalized Laplacian and 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) ≤ 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.

Authors

• Anand Louis
• Prasad Raghavendra
• Prasad Tetali
• Santosh S. Vempala

Keywords

• approximation algorithms
• cheeger's inequality
• graph eigenvalues
• graph expansion
• small-set expansion