Near-Linear Time Approximation Algorithm for Balanced Separator

The goal of the Balanced Separator problem is to find a balanced cut in a given graph G(V,E), while minimizing the number of edges that cross the cut. It is a fundamental problem with applications in clustering, image segmentation, community detection, and as a primitive for divide-and-conquer on graphs.

Several input graphs of interest today, e.g. the web graph, are massive in size, and even quadratic algorithms are too slow to be used in practice. Hence, there is considerable interest in designing algorithms for fundamental graph problems that run in time nearly linear in the size of the graph. In this talk, we present such an algorithm for the Balanced Separator problem. Our algorithm achieves an approximation guarantee that is optimal for spectral algorithms.

Our main contribution is two fold:

1. We reduce the question of finding a good balanced cut to simulating O(log |V|) continuous time random walks. This part uses techniques from semidefinite programming, and matrix exponential updates.

2. We show how to approximately simulate the required continuous time random walks on G in time O(|E|) (up to poly-logarithmic factors). The natural approach of using a polynomial approximation does not suffice.
We show how to achieve such an approximation using rational approximations, techniques from numerical linear algebra and the celebrated result of Spielman and Teng on solving linear systems.

In this talk, we will focus only on the second part. This is joint work with Lorenzo Orecchia and Nisheeth K. Vishnoi.