Abstract:
We describe an emerging paradigm, which we refer to as the Laplacian Paradigm, for the design of efficient algorithms for massive graphs. This paradigm is built on a recent collection of nearly-linear-time primitives in Spectral Graph Theory developed by Spielman and Teng. Their key primitive is a solver for a linear system, Ax = b, where A is the Laplacian matrix of a weighted, undirected n-vertex graph and b is an n-dimensional vector. Other primitives include nearly-linear-time algorithms for local clustering, spectral sparsification, and low stretch spanning trees. When applying the Laplacian Paradigm, we reduce the input problem to one or multiple problems that can be efficiently solved by these spectral primitives.
The Laplacian Paradigm has been used in a recent algorithm for computing an approximately maximum s-t flow in an undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows as well as the fastest known algorithm for approximating minimum s-t cut in a graph. The Laplacian paradigm has also been applied to obtain nearly-linear-time algorithms for applications in semi-supervised learning, image process, web-spam detection, eigenvalue approximation, and for solving elliptic finite element systems.
Recently, almost all original primitives in this collection including the Laplacian solver itself have been significantly improved. Practical implementation might become available in the near future. The goal of this presentation is to encourage more researchers to consider the use of the Laplacian Paradigm to develop faster algorithms for solving fundamental problems in combinatorial optimization, scientific computing, machine learning, network analysis, and other applications that involve massive graphs.
Joint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT).
