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)
Best Answer
How to understand the Graph Laplacian (3-steps recipe for the impatients)
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).
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.
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