From the Inside: Algorithmic Spectral Graph Theory

By James R. Lee

At its most basic, spectral graph theory exploits the eigenvalues and eigenvectors of a graph to study it from a global perspective. While a myopic examination of a few vertices and edges (friends and friendships) in a social network might leave one in the dark about its community structure, even a single eigenvector can carry detailed information about large-scale phenomena. And it is well known that one can capitalize on this for algorithmic gain: For instance, Google’s PageRank algorithm uses this spectral viewpoint to determine the importance of websites related to a given search query.

If the story ended there, spectral graph methods would be yet another valuable tool in the algorithm designer’s toolkit. But we have just turned the first page: The Simons program is devoted to the idea that algorithmic spectral graph theory is intimately tied to the very core of algorithms and complexity theory.

Computers have been finding Traveling Salesman tours and Maximum Flows since at least the 1950s. In the 60s and 70s, numerical modeling of physical systems via the finite element method became an essential tool in many fields of science and engineering. Just weeks ago in Seoul, Subhash Khot was awarded the Nevanlinna prize for his work on the Unique Games Conjecture (about the difficulty of solving a certain class of constraint satisfaction problems). And at our kick-off boot camp earlier this fall, the Simons Institute hosted a series of three-part lectures showing how, for each of these fundamental problems, algorithmic spectral methods and their generalizations have led to a revolution in our understanding.

Although the areas of application are widely varying, one can identify a theme common to this new wave of algorithms—the use of “higher order” spectral analyses that view all the spectral information as a cohesive object, as opposed to simply a collection of eigenvalues and eigenvectors. Electrical flows, random spanning trees, high-dimensional spectral embeddings, and geometric representations of the Laplacian quadratic form play a fundamental role.

Another significant aspect of the program is the bi-directional interaction between spectral graph theory (SGT) and fields of mathematics like Markov processes, functional analysis, convex geometry, geometric PDE, and random matrix theory. Besides borrowing heavily from these fields, there are also recent advances in the other direction, where algorithmic considerations have led to progress on problems in pure math. Most spectacularly, long-term visitor Nikhil Srivastava, together with his coauthors Adam Marcus and Dan Spielman, resolved the long-standing Kadison-Singer problem in operator theory using ideas inspired by their work on graph sparsification.

The Institute will host three workshops in conjunction with the SGT program. The first concerned semi-definite optimization and approximation algorithms as a powerful generalization of the spectral approach. One can consider eigenvalues as the solution to an optimization problem over a spectrahedron. Powerful SDP relaxations of this form are at the forefront of approximation algorithms for NP-hard optimization problems.

The second workshop will highlight the interplay between spectral methods in theory and in practice. Many approaches to data analysis, machine learning, artificial intelligence, and scientific computing employ spectral techniques. By bringing theorists and practitioners together, we hope to enhance the research programs of both groups by tying algorithms with theoretical analyses to models that reflect real-world constraints.

The final workshop will address the fast solution of Laplacian linear systems and their use in algorithms for combinatorial problems. After Spielman and Teng developed the first near-linear time solvers for Laplacian linear systems, a sequence of advances has obtained solvers that are remarkably simple and thus closer to wide deployment in practice. Amazing developments have shown that these linear-algebraic methods can be employed to solve combinatorial problems. In particular, this has led to fast algorithms for computing maximum flows, beating algorithms that had stood as the best for over three decades.

Given the breadth and depth of the program, it’s safe to say that we should all take a moment to catch our breath. OK. Now let’s change the world, one spectral algorithm at a time.

Related Articles:

Letter from the Director
Profile of Luca Trevisan, the Simons Institute's Incoming Senior Scientist
From the Inside: Algorithms and Complexity in Algebraic Geometry
Research Vignette: On Sex, Math, and the Origin of Life
Research Vignette: Quantum PCP Conjectures