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!

26 Responses to Graph Laplacians

  1. Naoki Shimode says:

    Maybe there is a tiny typo?

    (H\psi) = \sum \psi (y) - d(x) \psi(x)

    (Not \Psi, but \psi)

    • John Baez says:

      Thanks—fixed. I cut-and-paste some of this equation from Part 15 of my network theory series, where I discussed how graph Laplacians were both self-adjoint and infinitesimal stochastic, meaning they’re good both for describing Schrödinger’s equation on a graph (where time evolution is unitary) and a random walk on that graph (where time evolution is stochastic). So, that’s another place to read more about what graph Laplacians are good for!

  2. Arjun Jain says:

    In

    \displaystyle{ (H \psi)(x) = \sum_{y \,\, \textrm{such that} \, \,(x,y) \in E} \!\!\!\!\!\!\!\!\!\!\! \Psi(y) \quad - \quad d(x) \Psi(x) },

    shouldn’t \Psi be \psi?

  3. Alex says:

    I’m confused. I see a text by an Ernesto Estrada called “The Structure of Complex Networks: Theory and Applications”. Are they the same person?

  4. davidtweed says:

    One area that these Laplacians end up being applied is in preconditioning more general equations over graphs, as described in the overview here. The idea is roughly to use a laplacian system to approximate a more complicated linear system, solve that quickly and then “subtract off in an appropriate way” that solution to get a smaller-magnitude general system that’s the remains. This can then be laplacian approximated and solved, etc. I can see how this would work with general matrix/graph equations, but it apparently also has connections with network flows.

  5. larryy says:

    Trivial point, but I believe
    (x,x) \notin E
    normally says there are no self-terminations, not that “there are no loops”.

  6. westy31 says:

    There is a simple way to solve Laplacians on graphs. For each vertex, you simply make the potential equal to the weighted sum of its neighbours, with the admittances as weight factors. If you repeat this a number of times, you generally converge to a solution.

    (This is easy to try, for example in a spreadsheet.)

    The number of iterations is probably roughly proportional to the number of vertices times the number of neighbours 2 vertices are apart on average as. I guess the authors have found a smart way to use a spanning tree backbone to speed things up. I wonder if it works for non-linear graphs too, this could be important in fluid dynamics.

    Gerard

    • westy31 says:

      Hmm…, for a tree-shaped network, ie with no loops, you can solve the Laplacian in a single iteration, by working up the branches toward the main stem. So if you combine that with the method I described above, that might indeed work. Interesting!
      Gerard

      • davidtweed says:

        In the article I linked it explains that a tree is indeed very easily and efficiently soluble, but unfortunately its solution is significantly different to the general Laplacian. One of the keys to this approach is apparently adding back in just enough of the edges that complete loops that really significantly affect the solution to get a very good approximation while not minimising the amount of work in addition to the work required for solving a tree.

    • John Baez says:

      When the popular article says “solving graph Laplacians”, they are actually referring to solving Poisson’s equation

      H \phi = \rho

      for \phi given \rho, where H is a graph Laplacian. You seem to be talking about solving the Laplace equation

      H \phi = 0

      Does your method generalize to that? There should be some pretty easy way…

      The number of iterations is probably roughly proportional to the number of vertices times the number of neighbours 2 vertices are apart on average as.

      Sorry, I’m not sure I understand that sentence: it reminds me of how Germans put prepositions at the end, like “I woke this this morning up.” Maybe you mean

      The number of iterations is probably roughly proportional to the number of vertices times the average distance between two vertices.

      where the distance between two vertices is defined to be the length of the shortest path connecting them?

      • westy31 says:

        Yes, generalizing the method to the Poison equation is possible.
        You use (my first latex):
        V_j \to (\sum (V_j Y_{ji})-\rho_i)/\sum (Y_{ji})

        But you need also
        \sum \rho_i  =0
        Otherwise the

        You are also right about the sentence I mixed up.

        Gerard

        • westy31 says:

          Retry Latex:
          $V_i \rightarrow (\sum(V_j Y_{ji})-\rho_ii)/\sum(Y_{ji})) $

        • westy31 says:

          Retry2 Latex:
          latex$ V_i \rightarrow (\sum(V_j Y_{ji})-\rho_ii)/\sum(Y_{ji})) $

        • John Baez says:

          Your LaTeX is converging to correctness! I’m glad you’re trying to use LaTeX.

          If you look directly above the box you type into here, you’ll see these directions:

          You can use HTML in your comments. You can also use LaTeX, like this:

          $latex E = m c^2$

          The word ‘latex’ comes right after the first dollar sign, with a space after it.

          I’ve attempted to fix your LaTeX, but you also have a sentence that doesn’t reach the end. I think I get your overall point, though.

        • westy31 says:

          Sorry about my messy replies. The unfinished sentence is about the fact that in the circuit, there is no net influx. Interestingly, this means \rho integrated over space is zero.

  7. anonymous says:

    I find the definition of graph Laplacian peculiar. If I would write the discretized version of the ordinary Laplacian it would involve the function at three discretization points whereas ordinary partial derivative would involve just difference between the function at two discretization points which would resemble your graph Laplacian more.

    Can one define such thing as partial derivative on graph and how would that differ from the laplacian?

    • John Baez says:

      Anonymous wrote:

      I find the definition of graph Laplacian peculiar.

      This definition gives the usual discretization of the ordinary Laplacian if our graph is a lattice like this:

      or something similar in any other dimension. For example, in the 1-dimensional case, where we have a chain of vertices with each vertex i connected to its neighboring vertices i+1 and i-1 by edges, this definition gives

      (H \psi)(i) = \psi(i-1) - 2 \psi(i) + \psi(i+1)

      which is (up to a constant factor) the usual discretization of the 2nd derivative.

  8. westy31 says:

    While working on geometry and circuits, a nice side result I obtained last week is a formula for the N-circumsphere of an N-simplex in terms of squared distances only:
    http://westy31.home.xs4all.nl/Circumsphere/ncircumsphere.htm

  9. […] There are other matrices that are defined by the graph. Perhaps the most familiar is the Laplacian, which has recently been a topic on this blog (see parts 15, 16 and 20 of the series, and this recent post). […]

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s