Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap

Abstract

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.

References in corpus (3)

• Clustering is difficult only when it does not matter
• Multi-way expansion constants and partitions of a graph
• On the practically interesting instances of MAXCUT

Cited by in corpus (8)

• Flow-Based Algorithms for Local Graph Clustering
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Eigenvalue ratios of nonnegatively curved graphs
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• Impact of regularization on Spectral Clustering
• Convex Programming Based Spectral Clustering
• Multi-way expanders and imprimitive group actions on graphs
• Embedding approximately low-dimensional ${\ell }_2^2$ metrics into ${\ell }_1$