The Laplacian Paradigm: Emerging Algorithms for Massive Graphs

Опубликовано 17 августа 2016, 3:00

We describe an emerging paradigm for the design of efficient algorithms for massive graphs. This paradigm, which we will refer to as the Laplacian Paradigm, is built on a recent suite of nearly-linear time primitives in spectral graph theory developed by Spielman and Teng, especially their solver for linear systems Ax = b, where A is the Laplacian matrix of a weighted, undirected n-vertex graph and b is an n-place vector. In the Laplacian Paradigm for solving a problem, we reduce the optimization or computational problem to one or multiple linear algebraic problems that can be solved efficiently by applying the nearly-linear time Laplacian solver and the algorithms in this suite for local clustering, spectral sparsification, and low stretch spanning trees. The Laplacian Paradigm has been used in a recent algorithm for computing an approximately maximum s-t flow in a capacitated, undirected graph. It 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 suite including the Laplacian solver itself have been significantly improved and 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. NOTE: Considering the recent colloquium talks by Dan Spielman and Jon Kelner on spectral graph sparsification, maximum flow computation, improved Laplacian linear solver, and application of Laplacian Paradigm to machine learning, respectively, I will focus technically on the local clustering algorithms in the context of motivating the Laplacian Paradigm. Joint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT).