Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
This work addresses the problem of analyzing spectral partitioning algorithms for graph partitioning, offering incremental theoretical improvements with potential applications in image segmentation and clustering.
The paper improves Cheeger's inequality by proving that the spectral partitioning algorithm achieves a conductance bound of O(k) λ_2 / √λ_k for any graph, which is optimal up to a constant factor, providing theoretical justification for its empirical performance in image segmentation and clustering.
Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, φ(G) = O(k) λ_2 / \sqrt{λ_k}, and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if λ_k$ is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.