The graph Laplacian 2

In the previous blog, we saw the Laplacian defined in the context of solving for current flowing through an electrical circuit. We mentioned that the Laplacian is used in studying diffusion on graphs. Now, how could one possibly see it as a diffusion operator on a structure which does not allow differentiation? We should ask ourselves what the key aspect of diffusion is that is modeled by the heat equation. Sticking to the one-dimensional version for ease (though the intuition applies to more dimensions), we note that the second derivative can be approximated by

\frac{d^2 f}{dx^2} \approx \frac{f(x+h) - 2f(x) + f(x-h)}{h^2} = \frac{(f(x+h) - f(x)) + (f(x-h) - f(x)}{h^2}.

Seen this way, the second derivative can be seen as an average changes of the function values around a reference point. The diffusion equation therefore can be interpreted to mean something like, “The rate of change in time of a quantity (which we take to be concentration) at a point is proportional to the average of the change of concentration values around the point”.

Not very precise, but that’s okay – I’m not going for rigour here. Suppose now we have a discrete set of nodes, what could this mean? First of all, we let a node be at a distance of 1 from any of its neighbours, and allow no closer distances. To each of these nodes we assign a value, representing the concentration of some substance at that node. (Technically, since we’re working in a network now, there are better concepts than concentration, but I want to stick close to the original intuition.) Remembering our definition of the (unweighted) Laplacian as

L=D−AL = D – A

with D the diagonal degree matrix and A the incidence matrix, suppose that we have values \mathbf{x} = (x_1, x_2, \dots ,x_n) assigned to vertices v_1,v_2,\dots ,v_n. Looking at just the first entry of the matrix L\mathbf{x}, we get

\text{deg}(v_1)x_1 - A_{12}x_2 - \cdots - A_{1n}x_n .

Supposing that x_1 is connected to k vertices v_{i_1} ,\dots ,v_{i_k}, this gives us

(x_1 - x_{i_1}) + (x_1 - x_{i_2}) + \dots + (x_1 - x_{i_k}).

This is exactly what we want to describe diffusion-like phenomena, since it encodes the differences between the values at v_1 and all the nodes connected to it. Compared with the earlier approximation of the second derivative however, we notice a sign difference. This is easily fixed by multiplying with a negative, and we get the graph diffusion equation

\frac{dx}{dt} = -Lx.

This is all very nice, but have we not just in effect written a system of differential equations in a neat matrix form? Where does this get us? The point of formulating this system as a Laplacian is that we will be able to say things without solving the system, by only analyzing the algebraic properties of the operator L. These properties will tell us a lot about the topology of the graph itself, which is where we’ll go next.

Leave a Reply