Graph Partitioning via Adaptive Spectral Techniques

In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a 'latent' partition V-1, ... , V-k. Moreover, consider a 'density matrix' epsilon = (epsilon(nw))(nw is an element of V) such that, for nu is an element of V-i and w is an element of V-j, the entry epsilon(rw) is the fraction of all possible V-i-V-j-edges that are actually present in G. We show that on input (G,k) the partition V-1, ... ,V-k can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: epsilon approximates the adjacency matrix of G in the operator norm, for vertices nu is an element of V-i, w is an element of V-j not equal V-i the corresponding column vectors epsilon(r), epsilon(w) are separated, and G is sufficiently 'regular' with respect to the matrix epsilon. This result in particular applies to sparse graphs with bounded average degree as n = not equal V -> proportional to, and it has various consequences on partitioning random graphs.