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 V1,. . ., Vk. Moreover, consider a ‘density matrix’ = (vw)v, swV such that, for v Vi and w Vj, the entry vw is the fraction of all possible Vi−Vj-edges that are actually present in G. We show that on input (G, k) the partition V1,. . ., Vk can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: approximates the adjacency matrix of G in the operator norm, for vertices v Vi, w Vj ≠ Vi the corresponding column vectors v, w are separated, and G is sufficiently ‘regular’ with respect to the matrix . This result in particular applies to sparse graphs with bounded average degree as n = #V → ∞, and it has various consequences on partitioning random graphs