Name
Title | ||
|---|---|---|
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) l2/√lk,] 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 lk 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 spectral algorithms for other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2488608.2488611 | symposium on the theory of computing |
Keywords | DocType | Volume |
constant factor,spectral partitioning algorithm,constant factor approximation algorithm,maximum cut,performance guarantee,undirected graph,constant k,graph g,improved cheeger,sparse cut,empirical performance,higher order spectral gap,graph partitioning | Conference | abs/1301.5584 |
Citations | PageRank | References |
26 | 1.23 | 31 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tsz Chiu Kwok | 1 | 46 | 2.10 |
| Lap Chi Lau | 2 | 554 | 35.27 |
| Yin Tat Lee | 3 | 396 | 36.67 |
| Shayan Oveis Gharan | 4 | 323 | 26.63 |
| Luca Trevisan | 5 | 2995 | 232.34 |