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

2013/01/23 by Kwok, Tsz Chiu, Lau, Lap Chi, Lee, Yin Tat +2 · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.1301.5584

Abstract

Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=λ₁ <= λ₂ <=... <= λ_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) λ₂ / √(λ_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.

Cited by

• Structure-Aware Spectral Sparsification via Uniform Edge Sampling
• Polynomial complexity sampling from multimodal distributions using Sequential Monte Carlo

Related

• Multi-way spectral partitioning and higher-order Cheeger inequalities
• Partitioning into Expanders
• Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm
• A linear k-fold Cheeger inequality
• Max Cut and the Smallest Eigenvalue