61
$\begingroup$

Recently I saw an MO post Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs? that got me interested. It is about a graph parameter that is derived from the Laplacian of a graph. Its origins are in spectral operator theory, but it is quite strong in characterizing important properties of graphs. So I was quite fascinated by the link it creates between different branches of mathematics.

I went through other posts on MO that discuss this topic as well, and in the meantime I read a few linked articles that work with the graph Laplacian. I understand that they view an (undirected) graph as a metric graph embedded in a surface, and the metric on the graph is approximated by Riemannian metrics which give the edge distance along the edges, and which is close to zero everywhere else on the surface. The eigenvalues of the surface Laplacian approximate the eigenvalues of the graph Laplacian, and a lot of surprisingly useful conclusions follow, about connectivity and embeddability of the graph, and even about minor-monotonicity.

I have gained a technical understanding of what is happening and how these eigenvalues (and their multiplicity) are determined, using the graph Laplacian. I also have a basic understanding of the role of a Laplacian in differential geometry, like the Laplacian of a function $f$ at a point $x$ measures by how much the average value of $f$ over small spheres around $x$ deviates from $f(x)$, or I think of it to represent the flux density of the gradient flow of $f$.

But I am failing to gain or develop such an intuition for the graph Laplacian. Conceptually or intuitively, what does a graph Laplacian represent? I am trying to understand, how can it be so powerful when applied to graphs? (I am aware that the graph Laplacian can be defined using the graph adjacency matrix, but I was unable to link this with my differential geometry intuition)

$\endgroup$
8
  • 4
    $\begingroup$ The graph Laplacian also factors heavily in a more algebraic or algebro-geometric story where graphs are discrete analogs of algebraic curves/Riemann surfaces (see e.g. arxiv.org/abs/math/0608360). $\endgroup$ Aug 12, 2020 at 14:28
  • 4
    $\begingroup$ The graph Laplacian is the flux density of the gradient flow of a graph (the flow on each edge being the difference between the values on the vertices). $\endgroup$
    – Will Sawin
    Aug 12, 2020 at 14:40
  • 1
    $\begingroup$ @WillSawin Thank you for your comment! What I am struggling with, in the articles I was reading, no value was assigned to the vertices (if I understood correctly). So what does the flow actually represent? It seems to come "out of nowhere". Or maybe the vertices are just viewed as abstract sinks / or sources? $\endgroup$
    – GraphX
    Aug 12, 2020 at 15:03
  • 1
    $\begingroup$ I posted an answer to a similar question there ... just in case it might be of interest $\endgroup$
    – ARG
    Aug 13, 2020 at 20:09
  • 1
    $\begingroup$ The coefficient of $x^k$ of the characteristic polynomial $det(xI + L)$ is the number of ways to take a subset of the edges of the directed graph such that the connected components form k directed trees. $\endgroup$
    – Jules
    Aug 13, 2020 at 20:32

5 Answers 5

42
$\begingroup$

How to understand the Graph Laplacian (3-steps recipe for the impatients)

  1. read the answer here by Muni Pydi. This is essentially a concentrate of a comprehensive article, which is very nice and well-written (see here).

  2. work through the example of Muni. In particular, forget temporarily about the adjacency matrix and use instead the incidence matrix.

Why? Because the incidence matrix shows the relation nodes-edges, and that in turn can be reinterpreted as coupling between vectors (the value at the nodes) and dual vectors (the values at the edges). See point 3 below.

  1. now, after 1 and 2, think of this:

you know the Laplacian in $R^n$ or more generally in differential geometry.

The first step is to discretize: think of laying a regular grid on your manifold and discretize all operations ( derivatives become differences between adjacent points). Now you are already in the realm of graph laplacians. But not quite: the grid is a very special type of graph, for instance the degree of a node is always the same.

So you need to generalize a notch further: forget the underlying manifold, and DEFINE THE DERIVATIVES and the LAPLACIAN directly on the Graph.

If you do the above, you will see that the Laplacian on the Graph is just what you imagine it to be, the Divergence of the Gradient. Except that here the Gradient maps functions on the nodes to functions on the edges (via the discrete derivative , where every edge is a direction..) and the divergence maps the gradient back into a nodes function: the one which measures the value at a node with respect to its neighbors. So, nodes-edges-nodes, that is the way (that is why I said focus on the incidence matrix)

Hope it helps

$\endgroup$
3
  • 1
    $\begingroup$ Thank you for a fantastic answer! I wish I could give more than just +1 votes. $\endgroup$
    – GraphX
    Aug 12, 2020 at 16:33
  • 1
    $\begingroup$ Not so fantastic, a lazy answer (I should have written more). Anyway, there is a FOURTH point, which will complete the journey. This one: above, the Laplacian is defined from the incidence matrix, whereas the standard definition employs the adjacency one. Fact: they are the same. Try to understand why and you become a :Laplacian Jedi . Good luck! $\endgroup$ Aug 12, 2020 at 17:38
  • 3
    $\begingroup$ Your answer is great and really helps me with my intuition. I find this topic of graph Laplacians really amazing. Maybe the answer to your Yedi question is: the Laplacian is normally defined $I-A$ but $I-A=DD^T$ where $D$ is the incidence matrix and $DD^T$ corresponds exactly to your nodes-edges-nodes statement. But let me check the signs here I think I am getting something wrong with the signs. $\endgroup$
    – GraphX
    Aug 12, 2020 at 19:28
17
+500
$\begingroup$

This is just a long comment, adding to the excellent answers above.

There is a great article from László Lovász "Discrete and Continuous: Two sides of the same?", written around 2000 (https://web.cs.elte.hu/~lovasz/telaviv.pdf) which might be of interest to you. In chapter 5 of this article, Lovász covers the graph Laplacian. He explains the relation to random walks on graphs and also the link to the Colin de Vérdière graph invariant which sparked your interest (your link in the OP).

In your OP, you are asking how can the graph Laplacian be so powerful when applied to graphs? I think two quotes from this article could be of special interest to you, because quote (1) relates to the "power" and quote (2) relates to where the "limitations" were in applying the graph Laplacian.

About the "power":

Quote (1)
"The Laplacian makes sense in graph theory, and in fact it is a basic tool. Moreover, the study of the discrete and continuous versions interact in a variety of ways, so that the use of one or the other is almost a matter of convenience in some cases. (...) Colin de Verdière’s invariant created much interest among graph theorists, because of its surprisingly nice graph-theoretic properties. (...) Moreover, planarity of graphs can be characterized by this invariant: $\mu(G) \leq 3$ if and only if G is planar. Colin de Verdière’s original proof of the “if” part of this fact was most unusual in graph theory: basically, reversing the above procedure, he showed how to reconstruct a sphere and a positive elliptic partial differential operator $P$ on it so that $\mu(G)$ is bounded by the dimension of the null space of $P$, and then invoked a theorem of Cheng (...) asserting that this dimension is at most $3$.

About the "limitations":

Quote (2)
"Later Van der Holst (...) found a combinatorial proof of this fact [$\mu(G) \leq 3$ if and only if G is planar]. While this may seem as a step backward (after all, it eliminated the necessity of the only application of partial differential equations in graph theory I know of), it did open up the possibility of characterizing the next case. Verifying a conjecture of Robertson, Seymour, and Thomas, it was shown by Lovász and Schrijver (...) that $\mu(G) \leq 4$ if and only if G is linklessly embedable in $\mathbb R^3$."

$\endgroup$
1
  • 1
    $\begingroup$ I did not know this paper. Thank you for this reference. Very interested in these quotes, especially in the second one. I have to see this article, and the combinatorial proof of Van der Holst. Great additional perspective! Very grateful for that! $\endgroup$
    – GraphX
    Aug 29, 2020 at 15:58
14
$\begingroup$

This is not really about the connection with graph theory, a topic I am rather ignorant of, but rather the connection to continuum notions, all of which I learned from this paper.

Consider a simplicial complex in 3 dimensions for simplicity of visualization. The 0-simplexes are vertices $(i)$, the 1-simplexes are bonds $(ij)$, 2-simplexes are triangles $(ijk)$, 3-simplexes are tetrahedra $(ijkl)$. Each simplex has an orientation and under permutation of vertices acquires a sign change of +1 or -1 if the permutation is even or odd respectively.

Now we can define functions ($p$-chains) on our simplicial complex, $$\phi = \sum_i \phi_i (i)$$ $$\alpha = \sum_{[ij]} \alpha_{ij} (ij)$$ $$\beta = \sum_{[ijk]} \beta_{ijk} (ijk)$$ $$\gamma = \sum_{[ijkl]} \gamma_{ijkl} (ijkl)$$ where the $\alpha_{ij}$ etc. are fully anti-symmetric and the sum is over equivalence classes of simplexes (i.e. we pick one representative for each simplex from its possible permutations).

Now we define a boundary operator $\partial_p$ on $p$-simplexes. On a 0-simplex, we have $\partial_0(i) = 0$. For a 1-simplex we have $$\partial_1(ij) = (j) - (i)$$ and we generalize this, $$\partial_p(i_0 \cdots i_{p-1}) = \sum_n (-1)^n (i_0 \cdots \hat{i}_n \cdots i_{p-1})$$ where the hat means that vertex is removed. This is equivalent to saying that the boundary of a $p$-simplex is the sum of the $p-1$-simplices which bound it, each oriented such that their "edges" are oppositely oriented. Thus for a triangle we find $$\partial_2(ijk) = (jk) + (ki) + (ij)$$ while for a tetrahedron we have $$\partial_3(ijkl) = (jkl) + (kli) + (lij) + (ijk)$$ This construction automatically satisfies $\partial_{p-1} \partial_{p} = 0$ due to the "oppositely oriented edges" condition above.

Next, define the coboundary operator $\partial_p^\dagger$ which takes $p$-chains to $p+1$-chains. The definition says $$\partial_p^\dagger (i_1 \cdots i_{p}) = \sum_{i_0@[i_1 \cdots i_{p}]} (i_0 \cdots i_{p})$$ where $@$ means "adjacent to". Thus for a 0-simplex, $$\partial_0^\dagger (j) = \sum_{i@j} (ij)$$ Note that the sum is over oriented 1-simplices which "point towards $(j)$". For a 1-simplex $(ij)$, $\partial_1^\dagger(ij)$ is the sum is over all triangles $(i_0 i_1 i_2)$ such that $\partial_2(i_0 i_1 i_2)$ contains $+(ij)$, and so on. This operator also satisfies $ \partial_{p+1}^\dagger \partial_p^\dagger = 0$ by construction.

The boundary and co-boundary operators act on $p$-chains linearly. We can draw an analogy with differential geometry --- in particular, the co-boundary operator is analogous to the exterior derivative, and $p$-chains are akin to exterior $p$-forms. As shown in the above-linked paper, we can think of $0$-chains as scalar fields, $1$-chains as vector fields, $2$-chains as pseudo-vector fields, and $3$-chains as pseudo-scalar fields. The properties of the boundary operators are then summed up in this figure (their $d$ is my $\partial^\dagger$):

enter image description here

Note that the correspondence is not an approximation (see the text for details), although one can make a connection with the continuum differential operators via a Taylor-expansion approximation in the continuum limit as the lattice spacing goes to zero.

One can now define certain vector-product operations, demonstrate Stoke's theorem, etc. utilizing this construction. In particular, we can define the Laplacian for $p$-chains as $$\Delta_p = - (\partial_{p+1}\partial_{p}^\dagger + \partial_{p-1}^\dagger \partial_p)$$ then from the figure we find the correspondence $$\Delta_0 \sim \mathrm{div}\,\mathrm{grad} $$ $$\Delta_1 \sim \mathrm{grad}\,\mathrm{div} - \mathrm{curl}\,\mathrm{curl}$$ $$\Delta_2 \sim \mathrm{grad}\,\mathrm{div} - \mathrm{curl}\,\mathrm{curl}$$ $$\Delta_3 \sim \mathrm{div}\, \mathrm{grad}$$

In particular, $\Delta_0 = -\partial_1 \partial_0^\dagger$ is the usual graph Laplacian, and one can show (with appropriate choice of representatives in the summations above), that $$\Delta_0 = A - D$$ where $A$ is the adjacency matrix and $D$ is the incidence matrix of the graph (see here). In coordinate notation, it looks like $$\Delta_0 \phi = - \partial_1 \partial_0^\dagger \sum_i \phi_i (i)$$ $$ = - \partial_1\sum_{i} \phi_i \sum_{j@i} (ji)$$ $$ = - \sum_{i} \phi_i \sum_{j@i} [(i) - (j)]$$ $$ = - \sum_{i} (i) \sum_{j@i} (\phi_i - \phi_j)$$ from which it is easy to see that the above expression is correct: $$ \Delta_0 \phi = \sum_{i} (i) \sum_{j@i} \phi_j - \sum_{i} (i) \sum_{j@i} \phi_i \\ = \sum_i (i) \sum_j (A_{ij} - D_{ij}) \phi_j $$ where $D_{ij} = \delta_{ij} z_i$ with $z_i$ being the coordination number of vertex $i$ and $A_{ij} = \delta_{i@j}$. The higher-order Laplacian operators are then related to the graph structure of certain bond/face/body-duals of the original graph.

There is a further connection to various topics such as de Rham cohomology, the Hodge decomposition and harmonic forms. In particular, we can decompose any $p$-chain into $$\sigma^p = \partial_{p-1}^\dagger \alpha^{p-1} + \partial_{p+1} \beta^{p+1} + \gamma^{p}$$ where $\gamma^{p}$ is a "harmonic chain" and satisfies $\Delta_p \gamma^{p} = 0$, and corresponds to a contribution which "winds around" the lattice topologically, i.e. $\gamma^{p} \in H_p$, the $p$'th homology group of the complex. I have not seen that made more explicit anywhere yet and don't know enough about the topics myself to really comment further.

$\endgroup$
1
  • $\begingroup$ thank you very much for this extra perspective on this topic! $\endgroup$
    – GraphX
    Aug 13, 2020 at 6:45
12
$\begingroup$

I wrote a blog post a while ago* on different ways of interpreting the graph laplacian from the perspectives of functional analysis, probability, statistics, differential equations, and topology, and how they connect. Some of these perspectives are covered in more detail by the other responses, but I don't necessarily think one view has primacy over the others. I think the perspective that helps connect these views is that while, as described above, it can be seen as a differential operator applied to the graph, the structure induced by that operator, in particular by its eigendecomposition, is intimately linked to the structure of the space on which it is operating, which is why so many properties can be "read off" of the Laplacian.

More recently, this lecture from Keenan Crane's discrete differential geometry class focuses largely on the differential geometric interpretation, but links to the graph perspective through the triangulation of the surface.

*Since I wrote it in 2015, there has been substantial work on the topological perspective, e.g., and graph neural networks have become ubiquitous.

$\endgroup$
1
  • $\begingroup$ Thank you very much for these useful links! $\endgroup$
    – GraphX
    Aug 14, 2020 at 7:02
8
$\begingroup$

Here is another interpretation of the Laplacian (for this answer I use the notation of this answer to a similar post, in particular $\nabla$ is the [graph] gradient and $\nabla^*$ is its adjoint (i.e. one of them is the incidence matrix and the other one is its transpose).

In short: the Laplacian $\nabla^* \nabla$ is the gradient (in the sense of calculus) of the energy functional.

Note: this interpretation makes it relatively clear that (on the space perpendicular to the constant function [and eventually the "alternating" function on a bipartite graph]) applying the random walk operator $P = \mathrm{Id} - \nabla^*\nabla$ will converge to the function with the smallest energy: one is following the gradient flow.

Longer version: given a function $f:X \to \mathbb{R}$ (on the vertices), look at its energy: $$ \mathcal{E}(f) = \|\nabla f\|_{\ell^2E}^2 $$ (if $f$ were a potential for an electrical current, then this would be the power/heat produced). On a graph the function $f$ is just a point in $n$-dimensional space (where $n = |X|$ is the number of vertices) so the energy $\mathcal{E}$ has a gradient (in the sense of calculus; the use of gradient here is not the same as the one of $\nabla$ above).

To compute this gradient, consider any $g$ and look at $$ \frac{\mathrm{d}}{\mathrm{d}t}\Big|_{t=0} \|\nabla(f+ tg)\|_{\ell^2}^2 $$ Since $\nabla(f+tg) = \nabla f + t \nabla g$ and $\|\nabla h\|^2 = \langle \nabla h \mid \nabla h \rangle$, one has $$ \frac{\mathrm{d}}{\mathrm{d}t}\Big|_{t=0} \|\nabla(f+ tg)\|_{\ell^2}^2 = \langle \nabla g \mid \nabla f \rangle $$ Using the definition of the adjoint this is equal to $\langle g \mid \nabla^* \nabla f \rangle$.

This means that $\nabla^* \nabla f$ is the gradient of $\mathcal{E}$ at the "point" $f$.

$\endgroup$
2
  • $\begingroup$ Thank you very much. An interesting view on the graph Laplacian as well! $\endgroup$
    – GraphX
    Aug 15, 2020 at 6:37
  • 2
    $\begingroup$ Actually, although I remained in the "graph Laplacian" setup, the same remains true for the Laplacian on manifolds (in the right function spaces with the correct metrics; so quite messier, which is why I only talked about the graph set-up): the Laplacian of a function $f$ gives the function $\Delta f$ you should (multiply by a very small scalar and then) remove from the function $f$ in order to decrease the energy. [I used "remove" but it could be "add" depending of which sign you use for the Laplacian] $\endgroup$
    – ARG
    Aug 17, 2020 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.