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.