### Multiway Spectral Partitioning and Higher-Order Cheeger InequalitiesMultiway Spectral Partitioning and Higher-Order Cheeger Inequalities

Access Restriction
Subscribed

 Author Lee, James R. ♦ Gharan, Shayan Oveis ♦ Trevisan, Luca Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Cheeger's inequality ♦ Sparsest cut ♦ Spectral algorithms ♦ Spectral clustering Abstract A basic fact in spectral 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. It has been conjectured that an analogous characterization holds for higher multiplicities: There are $\textit{k}$ eigenvalues close to zero if and only if the vertex set can be partitioned into $\textit{k}$ subsets, each defining a sparse cut. We resolve this conjecture positively. Our result provides a theoretical justification for clustering algorithms that use the bottom $\textit{k}$ eigenvectors to embed the vertices into $R^{k},$ and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal quantitative connection between the expansion of sets of size ≈ $\textit{n}/\textit{k}$ and $λ_{k},$ the $\textit{k}th$ smallest eigenvalue of the normalized Laplacian, where $\textit{n}$ is the number of vertices. In particular, we show that in every graph there are at least $\textit{k}/2$ disjoint sets (one of which will have size at most $2\textit{n}/\textit{k}),$ each having expansion at most $O(√λ_{k}$ log $\textit{k}).$ Louis, Raghavendra, Tetali, and Vempala have independently proved a slightly weaker version of this last result. The √log $\textit{k}$ bound is tight, up to constant factors, for the “noisy hypercube” graphs. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-12-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 6 Page Count 30 Starting Page 1 Ending Page 30

#### Open content in new tab

Source: ACM Digital Library