Graph Laplacian Matrix

Introduction

The graph Laplacian matrix is a matrix representation of a graph. It is very useful for graph analysis and graph machine learning.

In this blog post, we will take a look at the definition of the graph Laplacian matrix and the relationship between the graph Laplacian matrix and the Laplace operator.

Graph Laplacian Matrix

The Laplacian matrix of a graph is defined as follows:

$$
L = D - A
$$

where $D$ is the degree matrix of the graph and $A$ is the adjacency matrix of the graph.

For example, given an undirected graph with five nodes and the following adjacency matrix:

$$
A = \begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0
\end{bmatrix}
$$

The degree matrix is:

$$
D = \begin{bmatrix}
2 & 0 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 & 0 \\
0 & 0 & 3 & 0 & 0 \\
0 & 0 & 0 & 3 & 0 \\
0 & 0 & 0 & 0 & 2
\end{bmatrix}
$$

The Laplacian matrix is, by definition, the difference between the degree matrix and the adjacency matrix:

$$
L = \begin{bmatrix}
2 & -1 & -1 & 0 & 0 \\
-1 & 2 & 0 & -1 & 0 \\
-1 & 0 & 3 & -1 & -1 \\
0 & -1 & -1 & 3 & -1 \\
0 & 0 & -1 & -1 & 2
\end{bmatrix}
$$

The matrix is called Laplacian matrix because it is the discrete analog of the Laplace operator in continuous space.

We will take a look at the relationship between the Laplacian matrix and the Laplace operator in the following sections.

Laplace Operator

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a function on Euclidean space.

In vector calculus, divergence is a vector operator that operates on a vector field, producing a scalar field giving the quantity of the vector field’s source at each point. More technically, the divergence represents the volume density of the outward flux of a vector field from an infinitesimal volume around a given point.

In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable.

$$
\Delta f = \nabla \cdot \nabla f = \sum_{i=1}^{n} \frac{\partial^2 f}{\partial x_i^2}
$$

where $f$ is a function of $n$ variables $x_1, x_2, \cdots, x_n$.

Graph Laplacian

For each pair of the neighboring nodes in the graph, we could also define the “gradient” as the difference between the values of the node and its neighbors. For example, for the node $i$ and its neighbor $j$, the directional “gradient” is:

$$
\begin{align}
\frac{\partial f}{\partial x_{i,j}} &= f_i - f_j \\
\frac{\partial f}{\partial x_{j,i}} &= f_j - f_i \\
\end{align}
$$

where $f_i$ is the value of the node $i$ and $f_j$ is the value of the node $j$.

The “divergence” of the node is the sum of the directional “gradients” from the node. For example, for the node $i$, the “divergence” is:

$$
\begin{align}
\Delta f_i &= \sum_{j} \frac{\partial f}{\partial x_{i,j}} \\
&= \sum_{j} (f_i - f_j) \\
&= \sum_{j} f_i - \sum_{j} f_j \\
&= f_i \sum_{j} 1 - \sum_{j} f_j \\
&= f_i d_i - \sum_{j} f_j \\
\end{align}
$$

where $d_i$ is the degree of the node $i$.

Using the Laplacian matrix, we could write the above equation as:

$$
\Delta f_i = (D f)_i - (A f)_i = (D - A) f_i = (L f)_i
$$

where $L$ is the Laplacian matrix of the graph and $f$ is the vector of the values of the nodes.

The divergence field of the graph is the dot product of the Laplacian matrix and the the vector of the values of the nodes.

$$
\Delta f = L f
$$

That’s why the Laplacian matrix is the discrete analog of the Laplace operator in continuous space.

References

• Laplacian Matrix
• The graph Laplacian