<![CDATA[Graph Laplacians]]>There’s been some new progress on graph Laplacians!

As a mathematical physicist, I’ve always been in love with the Laplacian:

\displaystyle{ \nabla^2 = \frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2} + \frac{\partial^2}{\partial z^2} }    

It shows up in many of the most fundamental equations of physics: the wave equation, the heat equation, Schrödinger’s equation… and Poisson’s equation:

\nabla^2 \phi = \rho

which says how the density of matter, \rho, affects the gravitational potential \phi.

As I’ve grown interested in network theory, I’ve gotten more and more interested in ‘graph Laplacians’. These are discretized versions of the Laplacian, where we replace 3-dimensional space by a ‘graph’, meaning something like this:

You can get a lot of interesting information about a graph from its Laplacian. You can also set up discretized versions of all the famous equations I mentioned.

The new progress is a simple algorithm for very efficiently solving Poisson’s equation for graph Laplacians:

• Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu, A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.

Here’s a very clear explanation of the general idea, conveying some sense of why it’s so important, without any nasty equations:

• Larry Hardesty, Short algorithm, long-range consequences, MIT News, 1 March 2013.

It begins:

In the last decade, theoretical computer science has seen remarkable progress on the problem of solving graph Laplacians — the esoteric name for a calculation with hordes of familiar applications in scheduling, image processing, online product recommendation, network analysis, and scientific computing, to name just a few. Only in 2004 did researchers first propose an algorithm that solved graph Laplacians in “nearly linear time,” meaning that the algorithm’s running time didn’t increase exponentially with the size of the problem.

At this year’s ACM Symposium on the Theory of Computing, MIT researchers will present a new algorithm for solving graph Laplacians that is not only faster than its predecessors, but also drastically simpler.



This animation shows two different “spanning trees” for a simple graph, a grid like those used in much scientific computing. The speedups promised by a new MIT algorithm require “low-stretch” spanning trees (green), in which the paths between neighboring nodes don’t become excessively long (red).

I can’t beat this article at its own game… except to clarify that ‘solving graph Laplacians’ means solving Poisson’s equation with a graph Laplacian replacing the usual Laplacian.

So, let me just supplement this article with the nasty equations saying what a graph Laplacian actually is. Start with a graph. More precisely, start with a simple graph. Such a graph has a set of vertices V and a set of edges E \subseteq V \times V, such that

(x,y) \in E \implies (y,x) \in E

which says the edges are undirected, and

(x,x) \notin E

which says there are no loops.

The graph Laplacian is an operator H that takes a function on the vertices of our graph,

\phi : V \to \mathbb{R}

and gives a new such function H\phi, as follows:

\displaystyle{ (H \phi)(x) = \sum_{y \,\, \textrm{such that} \, \,(x,y) \in E} \!\!\!\!\!\!\!\!\!\!\! (\phi(y) - \phi(x)) }

The version of Poisson’s equation for this graph Laplacian is thus

H \phi = \rho

But I should warn you: this operator H has eigenvalues that are less than equal to zero, like the usual Laplacian \nabla^2. People often insert a minus sign to make the eigenvalues ≥ 0.

There is a huge amount to say about graph Laplacians! If you want, you can learn more here:

• Michael William Newman, The Laplacian Spectrum of Graphs, Masters Thesis, Department of Mathematics, University of Manitoba, 2000.

I’ve been learning about some of their applications here:

• Ernesto Estrada, The Structure of Complex Networks: Theory and Applications, Oxford University Press, Oxford, 2011.

I hope sometime to summarize a bit of this material and push the math forward a bit. So, it was nice to see new progress on efficient algorithms for doing computations with graph Laplacians!

]]>