Laplacian

The graph Laplacian and the normalized Laplacian is defined here.

Laplacian as a GSO $(Lx)_i$

Inspecting the elements of the result of the Laplacian operator on a graph signal $x \in \mathbb{R^n}$

$$\begin{aligned} (Lx)_i &= ((D - A)x)_i \\ &= (Dx)_i - (Ax)_i \\ &= D_{ii} x_i - \sum_{j=1}^{n} A_{ij} x_j \\ &= d_i x_i - \sum_{j=1}^{n} A_{ij} x_j \end{aligned}$$

Now it's clear that the Laplacian operator results in each element being the weighted deviation of the corresponding node from the weighted average of it's neighbours, showing a clear analogue of the Laplacian operator in standard calculus. In fact, if the graph is unweighted since $d_i = |\mathcal{N}(i)|$,

$$\begin{aligned} (Lx)_i &= \sum_{j \in \mathcal{N}(i)} x_i - \sum_{j \in \mathcal{N}(i)} x_j \\ &= \sum_{j \in \mathcal{N}(i)} (x_i - x_j) \end{aligned}$$

Here, the Laplacian as a measure of deviation of a node from it's neighbours is very clear.

Laplacian and Total Variation

In DSP, the total variation of a signal $x$ is defined as

$$\mathrm{TV}(x) = \sum_i \left| x_i - x_{i-1} \right|^2$$

Now, consider the quadratic form of the Laplacian of an undirected graph, hence a symmetric Laplacian.

$$\begin{aligned} x^T L x &= x^T (D - A) x \\ &= x^T D x - x^T A x \\ &= \sum_{i=1}^{n} \sum_{j=1}^{n} x_i D_{ij} x_j - \sum_{i=1}^{n} \sum_{j=1}^{n} x_i A_{ij} x_j \\ &= \sum_{i=1}^{n} d_i x_i^2 - 2\sum_{(i,j) \in \mathcal{E}} x_i x_j &= \sum_{(i,j) \in \mathcal{E}} (x_i^2 + x_j^2) - 2\sum_{(i,j) \in \mathcal{E}} x_i x_j &= \sum_{(i,j) \in \mathcal{E}} (x_i^2 - 2x_i x_j + x_j^2) \\ &= \sum_{(i,j) \in \mathcal{E}} (x_i - x_j)^2 \end{aligned}$$

Hence, the quadratic form of the Laplacian operator generalizes the concept of total variation in graphs. It is a proxy for the concept of frequency in a graph. This results also shows the symmetric Laplacian is PSD. In fact, let $\lambda_1, \ldots, \lambda_n$ be the eigenvalues of $L$, ordered by increasing value. Since $L \cdot \mathbf{1} = 0$ and $L$ is PSD, using the facts about the Rayleigh quotient we can see that,

$$\begin{cases} \displaystyle \max_{\|x\|=1} \text{TV}(x) = \lambda_n \\[2ex] \displaystyle \min_{\|x\|=1} \text{TV}(x) = 0 \end{cases}$$

So for a given set of graph signals of same energy, the maximum total variation is the highest eigenvalue of the Laplacian and the total variation is bounded below by 0. The Laplacian eigenvalues are the canonical frequencies of the graph, and the corresponding eigenvectors are the oscillation modes.

The 0 Eigenvalue of the Laplacian

The fact that the symmetric Laplacian is PSD was shown through the total variation argument above. Hence all eigenvalues of the Laplacian are non-negative. Indeed, an eigenvalue of value 0 always exist as $L \cdot \mathbf{1} = 0$. Moreover, the multiplicity of this 0 eigenvalue corresponds to the connected components of the graph.