Graph Partitioning via Adaptive Spectral Techniques

Source abstract

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’ Ɛ = (Ɛ vw ) v, sw∈V such that, for v ∈ V i and w ∈ V j , the entry Ɛ vw 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: Ɛ approximates the adjacency matrix of G in the operator norm, for vertices v ∈ V i , w ∈ V j ≠ V i 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.