A Spectral Algorithm for Improving Graph Partitions

In the cut-improvement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any cut (C, V\C) that is t-correlated with the input cut, the cut output by the algorithm has conductance upper-bounded by a function of the conductance of (C, V\C) and t. In this paper we approach the cut-improvement problem from a spectral perspective: given a graph G and a cut (T,V\T), we first associate a natural unit vector to (T,V\T). Then we modify the standard spectral relaxation for G to bias it towards this vector, and use this relaxation to present a new cut-improvement algorithm, SpImprove. Our relaxation gives rise to a geometric notion of correlation among cuts. Moreover, we show that the classic sweep-cut rounding can still be applied and that we can solve our relaxation in nearly linear time by reducing it to an eigenvector computation. Further, we show how our approach is intimately connected to electrical networks in one limiting case. We believe this connection may be of independent interest. Finally, we compare our algorithm to the previous flow-based algorithm of Andersen and Lang. We show that SpImprove is likely to be faster and give better approximation guarantees in many settings.

Article

Download

View PDF