Approximating the exponential, the lanczos method and an Õ( m )-time spectral algorithm for balanced separator

We give a novel spectral approximation algorithm for the balanced (edge-)separator problem that, given a graph G, a constant balance b ∈ (0,1/2], and a parameter γ, either finds an Ω(b)-balanced cut of conductance O(√γ) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least γ, and runs in time ~O(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute exp(-L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to exp(-A)v for a class of symmetric positive semidefinite (PSD) matrices A and a given vector v, in time roughly ~O(m A ), independent of the norm of A, where m A is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting symmetric and diagonally-dominant matrices in ~O(m A ) time. Finally, using old and new uniform approximations to e -x we show how to obtain, via the Lanczos method, a simple algorithm to compute exp(-A)v for symmetric PSD matrices that runs in time roughly O(t A ⋅ √norm(A)), where t A is the time required for the computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O(√γ), for balanced separator that runs in time O(m/√γ). This latter algorithm matches the running time, but improves on the approximation guarantee of the Evolving-Sets-based algorithm by Andersen and Peres for balanced separator.

Authors

• Lorenzo Orecchia
• Sushant Sachdeva
• Nisheeth K. Vishnoi

Keywords

• balanced graph partitioning
• lanczos method
• matrix exponential
• spectral algorithms
• uniform approximation