Many sparse cuts via higher eigenvalues

DOI10.1145/2213977.2214079MaRDI QIDQ5415540zbMATH OpenOpenAlexFDO

Authors Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0965

zbMATH Keywords

approximation algorithmsCheeger's inequalitygraph eigenvaluesgraph expansionsmall-set expansion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. conductance) is bounded as follows: [ phi(S) defeq frac{w(S,�ar{S})}{min set{w(S), w(�ar{S})}} leq 2sqrt{lambda_2} ] where $w$ is the total edge weight of a subset or a cut and $lambd{a}_2$ is the second smallest eigenvalue of the normalized Laplacian of the graph. Here we prove the following natural generalization: for any integer $kin[n]$, there exist $ck$ disjoint subsets $S_1,\mathrm{...},S_{ck}$, such that [ max_i phi(S_i) leq C sqrt{lambda_{k} log k} ] where $lambd{a}_i$ is the $i^{th}$ smallest eigenvalue of the normalized Laplacian and $c<1,C>0$ are suitable absolute constants. Our proof is via a polynomial-time algorithm to find such subsets, consisting of a spectral projection and a randomized rounding. As a consequence, we get the same upper bound for the small set expansion problem, namely for any $k$, there is a subset $S$ whose weight is at most a $$ fraction of the total weight and $phi(S)leCsqrtlambd{a}_{k}logk$. Both results are the best possible up to constant factors. The underlying algorithmic problem, namely finding $k$ subsets such that the maximum expansion is minimized, besides extending sparse cuts to more than one subset, appears to be a natural clustering problem in its own right.

Recommendations

• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Partitioning into expanders

Cited in

(26)

• Spectral concentration and greedy k-clustering
• A Cheeger cut for uniform hypergraphs
• Finding Cheeger cuts in hypergraphs via heat equation
• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• On hyperboundedness and spectrum of Markov operators
• Tighter spectral bounds for the cut size, based on Laplacian eigenvectors
• A generalized Cheeger inequality
• Sharp spectral bounds of several graph parameters using eigenvector norms
• Approximations for the isoperimetric and spectral profile of graphs and related parameters
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• Finding small sparse cuts by random walk
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
• A Schur complement Cheeger inequality
• A polynomial time algorithm for Rayleigh ratio on discrete variables: replacing spectral techniques for expander ratio, normalized cut, and Cheeger constant
• Partitioning into expanders
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Partitioning well-clustered graphs: spectral clustering works!
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Approximating non-uniform sparsest cut via generalized spectra
• Bipartite communities via spectral partitioning
• Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm
• Cheeger's inequalities for vertex expansion and reweighted eigenvalues
• Graph algorithm based submodular function for sparsest cut problem
• A Cheeger inequality for size-specific conductance
• Sparsest cut and eigenvalue multiplicities on low degree abelian Cayley graphs
• Testing cluster structure of graphs

This page was built for publication: Many sparse cuts via higher eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415540)