"Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities"
Shayan Oveis Gharan
Stanford University
Monday, April 16, 2012, 2:00 pm
EBU3B, Room 4140
Abstract:
A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.
In this talk I show an analogous characterization holds for higher multiplicities, i.e., there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into Rk, and then apply geometric considerations to the embedding.
Our techniques also yield a nearly optimal tradeoff between the expansion of sets of size n/k, and λk, the kth smallest eigenvalue of the normalized Laplacian matrix. In particular, we show that in every graph there are at least k/2 disjoint sets (one of which will have size at most 2n/k) each having expansion at most O((λk log k)1/2). This bound is tight up to constant factors, for the ``noisy hypercube'' graphs.
Based on a joint work with James R. Lee, and Luca Trevisan.