The Laplacian Paradigm: Emerging Algorithms for Massive Graphs


July 27, 2011


Shanghua Teng




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).


Shanghua Teng

Shang-Hua Teng is the Seeley G. Mudd Professor and the Chairman of the Computer Science Department at USC Viterbi School of Engineering. He taught as an instructor in the Department of Mathematics of MIT and as a professor in the Computer Science Departments of Boston University, the University of Minnesota and UIUC. He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machine Corporation, and NASA Ames Research Center. He received a dual B.S. degree in computer science and in electrical engineering from Shanghai Jiao Tong University in 1985, a M.S. degree in computer science from University of Southern California (USC) in 1988, and a Ph.D. degree in computer science from Carnegie Mellon University (CMU) in 1991.

He is a recipient of the 2009 Fulkerson Prize (AMS-MPS) and the 2008 Gödel Prize (ACM-EATCS) for his joint work on Smoothed Analysis of Algorithms. He is also an ACM Fellow, Alfred P. Sloan Fellow, winner of Senior Xerox Award for Outstanding Faculty Research (UIUC), and has received NSF Faculty Early Career Development Award. He recently coauthored a paper which was chosen to be one of the two best papers for ACM STOC 2011. His research interests include spectral graph theory, computational game and economics theory, scientific computing, mathematical programming, and computational geometry. He has received more than ten US Patents for his work on compiler optimization and Internet technology.