Partitioning into Expanders
Shayan Oveis Gharan, Luca Trevisan · 2013
Let G = (V, E) be an undirected graph, λk be the kth smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that λk > 0 if and only if G has at most k – 1 connected components. We prove a robust version of this fact. If λk > 0, then for some 1 ≤ ℓ ≤ k – 1, V can be partitioned into ℓ sets P1, …, Pℓ such that each Pi is a low-conductance set in G and induces a high conductance induced subgraph. In particular, and G[Pi] ≳ λk/k2-expander. We make our results algorithmic by designing a simple polynomial time spectral algorithm to find such partitioning of G with a quadratic loss in the inside conductance of Pi's. Unlike the recent results on higher order Cheeger's inequality [6, 9], our results does not use higher order eigenfunctions of G. If there is a sufficiently large gap between λk and λk+1, more precisely if then our algorithm finds a k partitioning of V into sets P1, …, Pk such that the induced subgraph G[Pi] has a singnificantly larger conductance than the conductance of Pi in G. Such a partitioning may represent the best k clusterings of G. Our algorithm is a simple local search that only uses the Spectral Partitioning algorithm as a subroutine. We expect to see further applications of this simple algorithm in clustering applications. Let ρ(k) = mindisjoint max1≤i≤k φ(Ai) be the order k conductance constant of G, in words, ρ(k) is the smallest value of the maximum conductance of any k disjoint subsets of V. Our main technical lemma shows that if (1 + ∊)ρ(k) < ρ(k+1), then V can be partitioned into k sets P1, …, Pk such that for each 1 ≤ i ≤ k, φ(G[Pi]) ≳ ∊ · ρ(k + 1)/k and φ(Pi) ≤ k · ρ(k). This significantly improves a recent result of Tanaka [13] who assumed an exponential (in k) gap between ρ(k) and ρ(k + 1).