Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

The Graph Laplacian: Spectral Graph Theory Explained Simply

6 minute read

Published:

TL;DR: The Graph Laplacian \(L = D - A\) encodes the structure of a graph in a matrix. Its eigenvectors form the "Fourier basis" of the graph; its eigenvalues measure "frequencies". Spectral GNNs like GCN are simplifications of graph convolution in this Laplacian eigenvector space.

What Is the Laplacian?

Given a graph on \(N\) nodes with adjacency matrix \(A\) (where \(A_{ij} = 1\) if \((i,j)\) is an edge) and degree matrix \(D = \mathrm{diag}(d_1,\dots,d_N)\) with \(d_i = \sum_j A_{ij}\), the Graph Laplacian is:

\[ L = D - A . \]

That’s it. For a 4-node graph where node 1 has degree 3, node 2 has degree 2, node 3 has degree 3, node 4 has degree 2:

     [3  0  0  0]   [0  1  1  1]   [ 3 -1 -1 -1]
L  = [0  2  0  0] - [1  0  1  0] = [-1  2 -1  0]
     [0  0  3  0]   [1  1  0  1]   [-1 -1  3 -1]
     [0  0  0  2]   [1  0  1  0]   [-1  0 -1  2]

That is, \(L_{ij} = d_i\) if \(i = j\), \(-1\) if \((i,j)\) is an edge, and \(0\) otherwise.

Why Does This Matter?

The Laplacian is the discrete analogue of the second derivative (or more precisely, the negative of the Laplace operator \(\nabla^2\)). In continuous space, the Laplacian of a function \(f\) measures how much \(f\) at a point differs from \(f\) at nearby points.

On a graph, for a signal \(f \in \mathbb{R}^N\),

\[ (Lf)[i] \;=\; \sum_{j \in \mathcal{N}(i)} \bigl(f[i] - f[j]\bigr), \]

where \(\mathcal{N}(i)\) is the set of neighbours of node \(i\). It measures how much node \(i\)’s value differs from its neighbours’ values. If all neighbours have the same value as \(i\), then \((Lf)[i] = 0\).

Intuition: Think of \(f\) as heat temperature at each node. The Laplacian measures how much heat wants to flow out of each node — the local "imbalance". The heat diffusion equation is \(df/dt = -Lf\), meaning heat flows from hot nodes to cold neighbours.
Low-freq signal (smooth) 0.9 0.8 0.7 0.6 Neighbouring nodes have similar values → small eigenvalue λ ≈ 0 High-freq signal (oscillating) +1 −1 +1 −1 Neighbours have opposite signs → large eigenvalue λ ≈ 4
Figure 1: Low-eigenvalue eigenvectors correspond to smooth signals (similar values in connected nodes). High-eigenvalue eigenvectors oscillate rapidly between neighbours. This is the "frequency" interpretation.

Concrete Numerical Example

For the 4-node graph above, let’s verify the Laplacian formula entry by entry:

L[1][1] = deg(1) = 3,   L[1][2] = -A[1][2] = -1  (edge exists)
L[1][3] = -A[1][3] = -1 (edge exists),  L[1][4] = -A[1][4] = -1 (edge exists)

Check the "row sum = 0" property:
Row 1: 3 + (-1) + (-1) + (-1) = 0  ✓

This zero row-sum is crucial: it means the all-ones vector \(\mathbf{1} = [1,1,1,1]^{\top}\) satisfies \(L\mathbf{1} = 0\) — confirming \(\lambda_1 = 0\).

Key Insight: The Laplacian always has at least one zero eigenvalue, because the all-ones vector is always in its null space — connected or not. The multiplicity of the eigenvalue \(0\) equals the number of connected components: the null space is spanned by the indicator vectors of the components. So the graph is connected exactly when \(\lambda_2 > 0\). This is how you detect disconnected clusters with pure linear algebra, no search algorithm needed.

The Eigendecomposition: Graph Fourier Transform

The Laplacian \(L\) is symmetric — hence orthogonally diagonalisable — and positive semi-definite, since \(f^{\top} L f = \sum_{(u,v)\in E}(f[u]-f[v])^2 \ge 0\) for every \(f\). It can therefore be decomposed as:

\[ L = U \Lambda U^{\top}, \qquad U^{\top}U = I, \]

where \(U = [u_1, u_2, \ldots, u_N]\) holds the orthonormal eigenvectors and \(\Lambda = \mathrm{diag}(\lambda_1 \le \lambda_2 \le \cdots \le \lambda_N)\) the eigenvalues.

This is exactly analogous to the Fourier transform:

  • Eigenvectors \(u_k\): the “basis functions” — the graph’s Fourier modes.
  • Eigenvalues \(\lambda_k\): the “frequencies”. Indeed \(\lambda_k = u_k^{\top} L u_k = \sum_{(u,v)\in E}(u_k[u]-u_k[v])^2\), so a small \(\lambda_k\) literally means a smooth, slowly varying mode and a large \(\lambda_k\) a rapidly oscillating one.

Projecting a signal \(f\) onto \(U\) gives its frequency content, \(\hat{f} = U^{\top}f\) — the Graph Fourier Transform.

What Eigenvalues Tell You

  • \(\lambda_1 = 0\) always, with eigenvector \(\mathbf{1}\) (this holds for any graph, connected or not).
  • The multiplicity of eigenvalue \(0\) = the number of connected components. A graph with 3 disconnected clusters has exactly 3 zero eigenvalues.
  • \(\lambda_2\) (the algebraic connectivity or Fiedler value): zero when the graph is disconnected; close to \(0\) means barely connected; large means well-connected and hard to cut.
  • The eigenvector \(u_2\) for \(\lambda_2\) (the Fiedler vector) suggests a partition of the graph into two communities by the sign of its entries — the basis of spectral clustering. It is a relaxation of the NP-hard minimum-ratio-cut problem, so it is a good heuristic rather than a guaranteed optimum.

Animated Heat Diffusion

Heat diffusion on a graph (df/dt = −Lf): hot node cools, cold node warms v₁ hot v₂ medium v₃ cold heat flows out heat flows in Lf at v₁ = large positive (hot, loses heat) · Lf at v₃ = large negative (cold, gains heat)
Figure 2: Animated heat diffusion governed by \(df/dt = -Lf\). The Laplacian \(L\) measures local imbalance — hot nodes (large \(Lf\)) lose heat to cooler neighbours; cold nodes gain it. At equilibrium, \(Lf = 0\) everywhere, which by the null-space argument above means \(f\) is constant on each connected component.

From Laplacian to GCN

Spectral graph convolution convolves a signal with a filter in the Laplacian eigenspace:

\[ h *_G g_\theta \;=\; U\, g_\theta(\Lambda)\, U^{\top} h , \]

where \(g_\theta(\Lambda) = \mathrm{diag}\bigl(g_\theta(\lambda_1),\ldots,g_\theta(\lambda_N)\bigr)\) reweights each frequency.

This is computationally expensive (the eigendecomposition costs \(O(N^3)\)). GCN (Kipf & Welling, 2017) made two simplifications:

  1. Restrict \(g_\theta\) to a low-order polynomial in \(L_{\mathrm{sym}}\), so that \(U g_\theta(\Lambda) U^{\top} = g_\theta(L_{\mathrm{sym}})\) and no eigendecomposition is needed. Truncating the Chebyshev expansion at first order gives \(g_\theta(L_{\mathrm{sym}}) \approx \theta_0 I + \theta_1 L_{\mathrm{sym}}\).
  2. Tie the two coefficients (\(\theta = \theta_0 = -\theta_1\)) and apply the renormalisation trick: replace \(I + D^{-1/2}AD^{-1/2}\), whose spectrum lies in \([0,2]\), with
\[ \hat{A} \;=\; \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}, \qquad \tilde{A} = A + I, \quad \tilde{D}_{ii} = \sum_j \tilde{A}_{ij}, \]

whose spectrum lies in \((-1, 1]\) — bounded, so repeated application does not blow up.

Result: the GCN layer \(H^{(k+1)} = \sigma\bigl(\hat{A} H^{(k)} W^{(k)}\bigr)\) — neighbourhood averaging with symmetric normalisation. (See the GCN post for details.)

The Normalised Laplacian

For a graph with no isolated vertices, the symmetric normalised Laplacian is:

\[ L_{\mathrm{sym}} \;=\; D^{-1/2} L D^{-1/2} \;=\; I - D^{-1/2} A D^{-1/2}. \]

Its eigenvalues lie in \([0, 2]\) — bounded regardless of graph size or degree, which is what makes it convenient for filter design. The upper bound \(\lambda_N = 2\) is attained if and only if at least one connected component is bipartite; adding self-loops (as GCN does) destroys bipartiteness and pushes \(\lambda_N\) strictly below \(2\).

Note that the \(\lambda = 0\) eigenvector of \(L_{\mathrm{sym}}\) is \(D^{1/2}\mathbf{1}\), not \(\mathbf{1}\): the two agree only when every node has the same degree. Its multiplicity still equals the number of connected components.

✅ Key Takeaways

  • \(L = D - A\) is the Graph Laplacian: it measures local "imbalance" at each node.
  • Eigenvalues \(\lambda_i\) = graph frequencies; eigenvectors \(u_i\) = graph Fourier modes. Small eigenvalues = smooth signals.
  • The multiplicity of eigenvalue \(0\) = the number of connected components; \(\lambda_2\) measures overall connectivity.
  • \(L_{\mathrm{sym}} = I - D^{-1/2}AD^{-1/2}\) has spectrum in \([0,2]\), with \(2\) attained only for bipartite components.
  • GCN is a simplified spectral convolution: truncate the Laplacian filter to first order and renormalise, giving \(\hat{A}H\) with \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\).

References

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed — most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually — but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first — which is faster, shorter, and free of race conditions.