logo

Graph Laplacian 📂Graph Theory

Graph Laplacian

Definition

Let the degree matrix of a graph be DD and the adjacency matrix be AA. Then, the graph Laplacian LL of GG is defined as follows:

L:=DA L := D - A

Explanation

Unlike the Laplacian Δ=i2xi2\Delta = \sum\limits_{i} \frac{\partial^{2}}{\partial x_{i}^{2}} defined for functions over Euclidean space, it depends on the given graph.

For the graph G=(V,E)G = (V, E), denote f:VRf : V \to \mathbb{R} as the node signal and represent it as f=[f(v1)f(vn)]T\mathbf{f} = \begin{bmatrix} f(v_{1}) & \cdots & f(v_{n}) \end{bmatrix}^{\mathsf{T}}. Then, each component of LfL\mathbf{f} indicates how much the value at each vertex differs from the values at adjacent vertices.

Derivation

For a multivariable function g:RnRg : \mathbb{R}^{n} \to \mathbb{R}, the Laplacian is defined as follows:

2g=Δg=2gx12++2gxn2 \nabla^{2} g = \Delta g = \dfrac{\partial^{2} g}{\partial x_{1}^{2}} + \cdots + \dfrac{\partial^{2} g}{\partial x_{n}^{2}}

The differential of a function f:RRf : \mathbb{R} \to \mathbb{R} defined over real space can be numerically approximated as follows:

f(x)=f(x+h)f(x)h f^{\prime}(x) = \dfrac{f(x+h) - f(x)}{h}

f(x)=f(x+h)2f(x)+f(xh)h2(1) f^{\prime \prime}(x) = \dfrac{f(x+h) - 2f(x) + f(x-h)}{h^{2}} \tag{1}

Let’s consider the above equation for a graph. If we see xx as a vertex, x+hx+h and xhx-h can be viewed as vertices connected to xx. f(x)f(x) preceding 22 indicates that there are two adjacent points to xx. Therefore, from the graph perspective, (1)(1) represents subtracting the value of the reference vertex from the values at adjacent vertices by the degree. Expressing it mathematically yields ADA - D, but reversing the sign yields a positive definite matrix, thus defined as follows:

L:=DA L := D - A

Properties

  1. The graph Laplacian LL is a positive definite matrix.

Proof

1.

Let D=[Dij]D = [D_{ij}] and A=[Aij]A = [A_{ij}] be the degree matrix and adjacency matrix, respectively. Let xRn\mathbf{x} \in \mathbb{R}^{n} be as follows:

xTLx=xT(DA)x=xTDxxTAx=i=1nDiixi2i,j=1nAijxixj=i=1n(j=1nAij)xi2i,j=1nAijxixj \begin{align*} \mathbf{x}^{\mathsf{T}} L \mathbf{x} &= \mathbf{x}^{\mathsf{T}} (D - A) \mathbf{x} \\ &= \mathbf{x}^{\mathsf{T}} D \mathbf{x} - \mathbf{x}^{\mathsf{T}} A \mathbf{x} \\ &= \sum\limits_{i=1}^{n} D_{ii} x_{i}^{2} - \sum\limits_{i,j = 1}^{n} A_{ij} x_{i} x_{j} \\ &= \sum\limits_{i=1}^{n} \left( \sum\limits_{j=1}^{n} A_{ij} \right) x_{i}^{2} - \sum\limits_{i,j = 1}^{n} A_{ij} x_{i} x_{j} \\ \end{align*}

Here, i,ji, j is a dummy index and since AA is a symmetric matrix, i,jAijxi=i,jAijxj\sum_{i,j}A_{ij}x_{i} = \sum_{i,j}A_{ij}x_{j} holds true. Therefore, we obtain the following:

xTLx=i,j=1nAij(xi2xixj)=12i,j=1nAij(2xi22xixj)=12i,j=1nAij(xi2+xj22xixj)=12i,j=1nAij(xixj)2 \begin{align*} \mathbf{x}^{\mathsf{T}} L \mathbf{x} &= \sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i}^{2} - x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( 2x_{i}^{2} - 2x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i}^{2} + x_{j}^{2} - 2x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i} - x_{j} \right)^{2} \end{align*}

Since Aij0A_{ij} \ge 0, LL is a positive definite matrix.