Alessio Borgi

Alessio Borgi

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

The Graph Laplacian: Spectral Graph Theory Explained Simply

4 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 with adjacency matrix A and degree matrix D, 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]

L[i][j] = deg(i) if i=j, and -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 Laplace operator ∇²). 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, (Lf)[i] = Σⱼ (f[i] - f[j]) for all neighbours j — it measures how much node i’s value differs from its neighbours’ values. If all neighbours have the same value, (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.

The Eigendecomposition: Graph Fourier Transform

The Laplacian L is symmetric and positive semi-definite. It can be decomposed as:

L = U · Λ · Uᵀ

where U = [u₁, u₂, …, uₙ] are the eigenvectors and Λ = diag(λ₁ ≤ λ₂ ≤ … ≤ λₙ) are the eigenvalues.

This is exactly analogous to the Fourier transform:

  • Eigenvectors uₖ: the “basis functions” — the graph’s Fourier modes.
  • Eigenvalues λₖ: the “frequencies”. Small λ = smooth, slowly-varying mode. Large λ = rapidly oscillating mode.

Projecting a signal f onto U gives its frequency content — the Graph Fourier Transform.

What Eigenvalues Tell You

  • λ₁ = 0 always (the all-ones vector is an eigenvector with eigenvalue 0 for connected graphs).
  • Number of zero eigenvalues = number of connected components. A graph with 3 disconnected clusters has 3 zero eigenvalues.
  • λ₂ (the algebraic connectivity or Fiedler value): close to 0 means the graph is barely connected; large means it’s well-connected and hard to cut.
  • The eigenvector for λ₂ (Fiedler vector) reveals the best way to partition the graph into two communities — directly usable for spectral clustering.

From Laplacian to GCN

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

h * g_θ = U · g_θ(Λ) · Uᵀ · h

This is computationally expensive (eigendecomposition is O(N³)). GCN (Kipf & Welling 2016) made two simplifications:

  1. Approximate the filter as a polynomial of L: g_θ(L) ≈ θ₀ + θ₁L.
  2. Truncate and normalise: use à = D̃^(-1/2)(A+I)D̃^(-1/2).

Result: the GCN layer H' = σ(Ã · H · W) — neighbourhood averaging with normalisation. (See the GCN post for details.)

The Normalised Laplacian

The normalised Laplacian is:

L_norm = D^(-1/2) · L · D^(-1/2) = I − D^(-1/2) · A · D^(-1/2)

Its eigenvalues lie in [0, 2], making it more numerically stable for filter design. GCN uses this normalised version.

✅ Key Takeaways

  • L = D − A is the Graph Laplacian: it measures local "imbalance" at each node.
  • Eigenvalues = graph frequencies; eigenvectors = graph Fourier modes. Small eigenvalues = smooth signals.
  • The number of zero eigenvalues = number of connected components; λ₂ measures overall connectivity.
  • GCN is a simplified spectral convolution: approximate the Laplacian filter as first-order polynomial, normalise → get ÃH.

You May Also Enjoy

GraphSAGE: Inductive Learning on Large Graphs

3 minute read

Published:

GCN and GAT learn embeddings for fixed graphs — add a new node and you’re stuck. GraphSAGE (Hamilton et al., 2017) learns an aggregation function instead, so it can generate embeddings for entirely new nodes at inference time.

GAT: Graph Attention Networks

3 minute read

Published:

GCN assigns the same (degree-based) weight to every neighbour. GAT learns which neighbours actually matter — using attention coefficients on edges. More expressive, more interpretable.

GCN: Graph Convolutional Networks

3 minute read

Published:

GCN (Kipf & Welling, 2016) is the ‘hello world’ of GNNs. It simplifies spectral graph convolution into a single elegant layer: normalised neighbourhood averaging with a learned linear transformation.