Partitioning into Expanders

Let G=(V,E) be an undirected graph, lambdak be the k-th smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that lambdak > 0 if and only if G has at most k-1 connected components. We prove a robust version of this fact. If lambdak>0, then for some 1≤ ℓ≤ k-1, V can be em partitioned into l sets P1,ldots,Pl such that each Pi is a low-conductance set in G and induces a high conductance induced subgraph. In particular, φ(Pi)=O(l3√λl) and φ(G[Pi]) >= λk/k2). 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 [LOT12,LRTV12], our algorithmic results do not use higher order eigenfunctions of G. If there is a sufficiently large gap between lambdak and lambdak+1, more precisely, if λk+1 >= poly(k) lambdak1/4 then our algorithm finds a k partitioning of V into sets P1,...,Pk such that the induced subgraph G[Pi] has a significantly larger conductance than the conductance of Pi in G. Such a partitioning may represent the best k clustering 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.