Graph Laplacians & Spectrum

Overview & Motivation

A graph encodes pairwise relationships: who knows whom, which proteins interact, which cities are connected by flights. The adjacency matrix $A$ records these relationships, but it is the Laplacian $L = D - A$ that reveals the graph’s deeper structure.

Why the Laplacian and not the adjacency matrix? Because the Laplacian is a real symmetric positive semidefinite matrix, and the Spectral Theorem guarantees it has a complete orthonormal eigenbasis with non-negative eigenvalues. These eigenvalues encode global properties that are invisible to local inspection:

• How many pieces? The multiplicity of the zero eigenvalue equals the number of connected components.
• How well-connected? The second-smallest eigenvalue $\lambda_2$ — the Fiedler value or algebraic connectivity — quantifies the graph’s bottleneck.
• Where to cut? The eigenvector corresponding to $\lambda_2$ — the Fiedler vector — identifies the optimal bipartition.
• How regular? The entropy of the random walk’s stationary distribution, connected to the spectrum via Shannon Entropy, measures how uniformly the graph distributes flow.

Cheeger’s inequality makes the connection between algebra and combinatorics precise: $\frac{h(G)^2}{2} \leq \lambda_2 \leq 2h(G)$, where $h(G)$ is the Cheeger constant measuring the graph’s combinatorial bottleneck.

Spectral clustering exploits this theory: embed vertices into the eigenspace of the Laplacian, then cluster in the embedding. Points that are non-linearly separable in the original space become linearly separable in the spectral embedding — the same idea as PCA, but with the Laplacian replacing the covariance matrix.

What we cover:

1. Graphs and matrices — adjacency, degree, and Laplacian matrices for named graph families.
2. The graph Laplacian — definition, quadratic form, positive semidefiniteness, and the zero eigenvalue.
3. Spectral properties — eigenvalue ordering, connectivity, the Fiedler value and vector.
4. The normalized Laplacian — connection to random walks and transition matrices.
5. Cheeger’s inequality — the spectral gap bounds the combinatorial bottleneck.
6. Spectral clustering — from similarity graphs to Laplacian eigenmaps to $k$-means.
7. Connections to ML — GNNs as Laplacian smoothing, graph signal processing.
8. Computational notes — practical implementations in Python.

---

Graphs, Adjacency Matrices, and the Degree Matrix

We work with undirected, weighted graphs throughout. An undirected graph is the natural setting for the Laplacian: the resulting matrix is symmetric, which is exactly what the Spectral Theorem requires.

Concrete examples. The topology of a graph shapes its matrix representations. Here are the standard families we will use throughout:

• Path $P_n$: $n$ vertices in a line. $A$ is tridiagonal. Each interior vertex has degree 2; endpoints have degree 1.
• Cycle $C_n$: $P_n$ with the endpoints connected. $A$ is tridiagonal plus corner entries. Every vertex has degree 2 (a $2$-regular graph).
• Complete graph $K_n$: every pair connected. $A = \mathbf{1}\mathbf{1}^T - I$. Every vertex has degree $n - 1$.
• Star $S_n$: one hub connected to $n - 1$ leaves. The hub has degree $n - 1$; every leaf has degree 1.
• Barbell: two $K_k$ cliques joined by a single bridge edge. This is the canonical bottleneck graph.
• Grid $m \times m$: vertices on a lattice. Interior vertices have degree 4; edges have degree 3; corners have degree 2.

---

The Graph Laplacian

The Laplacian looks like a minor rearrangement of $A$, but the sign flip on the off-diagonal entries is what makes it positive semidefinite. The key insight is the quadratic form.

import numpy as np

# Laplacian construction from an adjacency matrix
A = np.array([[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]], dtype=float)
D = np.diag(A.sum(axis=1))
L = D - A

print(f"L = D - A =\n{L}")
# [[ 2. -1. -1.  0.]
#  [-1.  3. -1. -1.]
#  [-1. -1.  2.  0.]
#  [ 0. -1.  0.  1.]]

Preset:Path(6)Cycle(6)Complete(6)Star(6)Barbell(3-3)PetersenGrid(3×3)Color:Fiedler vectorDegreeNoneHide matrices

Click empty space: add nodeClick node: select for edge toggleClick second node: toggle edgeDouble-click node: deleteDrag node: reposition

---

Spectral Properties of the Laplacian

Since $L$ is real symmetric and PSD, the Spectral Theorem guarantees that its eigenvalues are real and non-negative. We order them:

$0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$

The first eigenvalue is always $\lambda_1 = 0$ (with eigenvector $\mathbf{1}$). The central question is: what does the rest of the spectrum tell us about the graph?

The Fiedler value is a spectral measure of “how connected” the graph is. A large $\lambda_2$ means the graph is well-connected with no bottleneck; a small $\lambda_2$ means there is a narrow bridge that nearly disconnects the graph.

# Eigendecomposition of the Laplacian
eigenvalues, eigenvectors = np.linalg.eigh(L)
print(f"Eigenvalues: {eigenvalues.round(4)}")
print(f"Fiedler value λ₂ = {eigenvalues[1]:.4f}")
print(f"Fiedler vector v₂ = {eigenvectors[:, 1].round(4)}")

Family:Path(n)Cycle(n)Complete(n)Barbell(k–k)Grid(m×m)Erdős–Rényi(n,p)n:6

+ Add edge− Remove edge

---

The Normalized Laplacian

The unnormalized Laplacian $L$ treats all vertices equally, regardless of degree. For graphs with heterogeneous degree distributions, the normalized Laplacian accounts for the local connectivity of each vertex.

The three Laplacians are closely related. If $\mathcal{L}\mathbf{u} = \lambda \mathbf{u}$, then $L_{\text{rw}}(D^{1/2}\mathbf{u}) = \lambda (D^{1/2}\mathbf{u})$, so $\mathcal{L}$ and $L_{\text{rw}}$ share eigenvalues. The eigenvectors differ by the transformation $D^{1/2}$.

Connection to entropy. The random walk on $G$ has stationary distribution $\pi_i = d_i / (2m)$ where $m = \sum_{\{i,j\} \in E} w_{ij}$ is the total edge weight. The Shannon entropy of $\boldsymbol{\pi}$ is $H(\boldsymbol{\pi}) = -\sum_i \pi_i \log_2 \pi_i$. For a $d$-regular graph, $\boldsymbol{\pi}$ is uniform and $H(\boldsymbol{\pi}) = \log_2 n$ — the maximum possible entropy. The spectral gap $1 - \lambda_2(P) = \lambda_2(\mathcal{L})$ governs how quickly the walk’s distribution converges to $\boldsymbol{\pi}$, i.e., how fast entropy increases toward equilibrium.

# Normalized Laplacian construction
D_inv_sqrt = np.diag(1.0 / np.sqrt(np.where(d > 0, d, 1)))
L_norm = D_inv_sqrt @ L @ D_inv_sqrt  # = I - D^{-1/2} A D^{-1/2}

eigenvalues_norm = np.linalg.eigh(L_norm)[0]
print(f"Normalized eigenvalues: {eigenvalues_norm.round(4)}")
print(f"All in [0, 2]: {np.all(eigenvalues_norm >= -1e-10) and np.all(eigenvalues_norm <= 2 + 1e-10)}")

---

Cheeger’s Inequality

The Fiedler value $\lambda_2$ is an algebraic quantity. The Cheeger constant $h(G)$ is a combinatorial quantity. Cheeger’s inequality links them, providing a bridge between linear algebra and graph theory.

The Cheeger constant measures the graph’s worst bottleneck: the smallest ratio of “edges crossing a cut” to “the smaller side’s connectivity.” A large $h(G)$ means every cut has many crossing edges relative to the smaller side — the graph is well-connected everywhere. A small $h(G)$ means there is a narrow bridge.

Interpretation. Cheeger’s inequality says that the spectral gap is a faithful proxy for the combinatorial bottleneck:

• Large $\lambda_2$ $\Rightarrow$ large $h(G)$ $\Rightarrow$ every cut crosses many edges $\Rightarrow$ the graph is an expander (the subject of Expander Graphs).
• Small $\lambda_2$ $\Rightarrow$ small $h(G)$ $\Rightarrow$ there exists a narrow bottleneck $\Rightarrow$ the graph is nearly disconnected.

Graph:Barbell (5+5)Path (10)Cycle (10)Grid (4×4)Two cliques (5+5)Random 3-regular (10)

Cut:Minimum cutFiedler partition

h(G) = 0.0476

λ₂ = 0.0726

Bounds: 0.0011 ≤ 0.0726 ≤ 0.0952✓

---

Spectral Clustering

Spectral clustering is the most celebrated application of graph Laplacian theory in machine learning. The idea: transform data using the eigenvectors of a graph Laplacian, then cluster in the transformed space. Points that are non-linearly separable in the original space become linearly separable in the spectral embedding — a phenomenon that standard $k$-means cannot achieve.

The Algorithm

Unnormalized spectral clustering (Laplacian eigenmaps + $k$-means):

1. Build a similarity graph. Given data points $\mathbf{x}_1, \ldots, \mathbf{x}_n \in \mathbb{R}^d$, construct a $k$-nearest-neighbor graph or $\varepsilon$-ball graph. Weight edges with the Gaussian kernel:

$w_{ij} = \exp\!\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma^2}\right)$

where $\sigma$ is typically set to the median pairwise distance.

2. Compute the Laplacian. Form $L = D - A$ (unnormalized) or $\mathcal{L} = I - D^{-1/2}AD^{-1/2}$ (normalized).

3. Embed. Compute the $k$ smallest eigenvectors $\mathbf{v}_1, \ldots, \mathbf{v}_k$ of $L$ (or $\mathcal{L}$). Form the embedding matrix $U \in \mathbb{R}^{n \times k}$ whose columns are these eigenvectors. Each row of $U$ is a point in $\mathbb{R}^k$.

4. Cluster. Run $k$-means on the rows of $U$.

Normalized variants (preferred in practice):

• Shi–Malik (2000): Use $L_{\text{rw}}$ eigenvectors. Equivalent to normalizing the rows of $U$ before $k$-means.
• Ng–Jordan–Weiss (2001): Use $\mathcal{L}$ eigenvectors, then normalize each row to unit length before $k$-means.

Why It Works

Consider a graph with $k$ ideal clusters — $k$ cliques with no edges between them. The Laplacian is block diagonal:

$L = \begin{pmatrix} L_1 & & \\ & \ddots & \\ & & L_k \end{pmatrix}$

Each block $L_i$ has a zero eigenvalue with eigenvector $\mathbf{1}_{C_i}$. The bottom $k$ eigenvectors of $L$ are exactly the indicator vectors of the clusters. The rows of $U$ are one-hot vectors, so $k$-means trivially separates them.

When the clusters are not perfectly separated — when there are a few edges between them — the eigenvectors are perturbed versions of the ideal indicators. The perturbation is small when the inter-cluster edges are few (relative to intra-cluster edges), and $k$-means still succeeds.

This is why spectral clustering handles non-convex clusters that $k$-means in the original space cannot: the Laplacian embedding transforms the data from Euclidean proximity (which fails for non-convex shapes) to graph connectivity (which captures the manifold structure).

from sklearn.cluster import SpectralClustering
from sklearn.datasets import make_moons

# Two moons: non-convex clusters that k-means cannot separate
X, y = make_moons(200, noise=0.06, random_state=42)

sc = SpectralClustering(
    n_clusters=2,
    affinity='nearest_neighbors',
    n_neighbors=10,
    random_state=42
)
labels = sc.fit_predict(X)
accuracy = max(np.mean(labels == y), np.mean(1 - labels == y))
print(f"Spectral clustering accuracy: {accuracy:.1%}")  # ~100%

DatasetTwo MoonsTwo CirclesThree BlobsSpiralClusters k

234

Graph

k-NNε-ball

Noise 1.0

---

Connections to Machine Learning

Graph Signal Processing

A graph signal is a function $\mathbf{f} \in \mathbb{R}^n$ that assigns a real value to each vertex. The eigenvectors of the Laplacian form an orthonormal basis — the graph Fourier basis — and the graph Fourier transform of $\mathbf{f}$ is:

$\hat{\mathbf{f}} = U^T \mathbf{f}$

where $U = [\mathbf{v}_1 \mid \cdots \mid \mathbf{v}_n]$ is the matrix of Laplacian eigenvectors. Low-eigenvalue components correspond to smooth signals (slowly varying across edges); high-eigenvalue components correspond to rough signals (rapidly varying). Filtering in the spectral domain — zeroing out high-frequency components — amounts to smoothing the signal on the graph.

GCNs as Laplacian Smoothing

The Graph Convolutional Network (GCN) of Kipf & Welling (2017) performs the update:

$H^{(\ell+1)} = \sigma\!\left(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(\ell)} W^{(\ell)}\right)$

where $\tilde{A} = A + I$ is the adjacency matrix with added self-loops and $\tilde{D}$ is its degree matrix. The matrix $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} = I - \tilde{\mathcal{L}}$ is one minus the normalized Laplacian of the self-loop-augmented graph. This means each GCN layer smooths the node features: every node’s representation is replaced by a weighted average of itself and its neighbors.

Message Passing & GNNs develops this connection further, showing how message-passing neural networks generalize GCNs and how the Laplacian spectrum determines what a GNN can and cannot learn.

import torch

# Single GCN layer: H' = σ(D̃^{-1/2} Ã D̃^{-1/2} H W)
A_tilde = A + torch.eye(n)                  # Add self-loops
D_tilde = torch.diag(A_tilde.sum(dim=1))
D_inv_sqrt = torch.diag(1.0 / torch.sqrt(D_tilde.diagonal()))
S = D_inv_sqrt @ A_tilde @ D_inv_sqrt       # Normalized adjacency

H = torch.randn(n, 16)                      # Node features
W = torch.randn(16, 8)                       # Learnable weights
H_next = torch.relu(S @ H @ W)              # One GCN layer

---

Computational Notes

NumPy / SciPy

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import laplacian

# Dense Laplacian
A = np.array([[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]], dtype=float)
D = np.diag(A.sum(axis=1))
L = D - A

# Eigendecomposition (use eigh for symmetric matrices — faster and more stable)
eigenvalues, eigenvectors = np.linalg.eigh(L)
fiedler_value = eigenvalues[1]
fiedler_vector = eigenvectors[:, 1]

# Sparse Laplacian (for large graphs)
A_sp = csr_matrix(A)
L_sp = laplacian(A_sp)

NetworkX

import networkx as nx

G = nx.from_numpy_array(A)
print(f"Spectrum: {np.sort(nx.laplacian_spectrum(G)).round(4)}")
print(f"Algebraic connectivity: {nx.algebraic_connectivity(G):.4f}")
print(f"Fiedler vector: {nx.fiedler_vector(G).round(4)}")

scikit-learn

from sklearn.cluster import SpectralClustering

sc = SpectralClustering(
    n_clusters=2,
    affinity='nearest_neighbors',
    n_neighbors=10,
    random_state=42
)
labels = sc.fit_predict(X)

Practical tips:

• Always use np.linalg.eigh (not eig) for symmetric matrices — it is faster, more numerically stable, and guarantees real eigenvalues.
• Threshold near-zero eigenvalues: treat $|\lambda| < 10^{-10}$ as zero when counting connected components.
• For large sparse graphs, use scipy.sparse.linalg.eigsh(L, k=3, which='SM') to compute only the smallest $k$ eigenvalues.
• Set the Gaussian kernel bandwidth $\sigma$ to the median pairwise distance — a robust default.

---

Connections & Further Reading

Topic	Connection
The Spectral Theorem	The graph Laplacian is real symmetric. The Spectral Theorem guarantees a complete orthonormal eigenbasis — the foundation of spectral graph theory. The Courant–Fischer theorem underlies the Fiedler value characterization and Cheeger’s inequality.
Shannon Entropy & Mutual Information	The entropy of the random walk stationary distribution $H(\boldsymbol{\pi})$ measures graph regularity. Regular graphs have uniform $\boldsymbol{\pi}$ and maximum entropy $\log_2 n$. The spectral gap governs the mixing rate.
PCA & Low-Rank Approximation	Spectral clustering uses the bottom eigenvectors of the Laplacian as an embedding, analogous to PCA using the top eigenvectors of the covariance matrix. Both are eigenmap embeddings: PCA preserves variance, spectral clustering preserves graph connectivity.
Convex Analysis	The quadratic form $\mathbf{x}^T L \mathbf{x}$ is convex. Spectral clustering relaxes the NP-hard normalized cut to a continuous eigenvalue problem — a convex relaxation.
Random Walks & Mixing	The transition matrix $P = D^{-1}A$ has eigenvalues $\mu_i = 1 - \lambda_i(\mathcal{L})$, and the spectral gap $\gamma = \lambda_2(\mathcal{L})$ controls mixing time — how quickly the walk’s distribution converges to the stationary distribution.
Expander Graphs	Expander Graphs studies the graphs that maximize connectivity at fixed sparsity. The spectral gap — bounded below by Cheeger’s inequality — is the defining quantity: expanders have spectral gap bounded away from zero.
Message Passing & GNNs	GCN message passing is Laplacian smoothing. Over-smoothing occurs when too many layers act as a low-pass filter, collapsing all node features toward the dominant eigenvector.

Key Notation

Symbol	Meaning
$L = D - A$	Unnormalized graph Laplacian
$\mathcal{L} = D^{-1/2}LD^{-1/2}$	Normalized Laplacian
$L_{\text{rw}} = I - D^{-1}A$	Random walk Laplacian
$P = D^{-1}A$	Random walk transition matrix
$\lambda_2$	Fiedler value (algebraic connectivity)
$\mathbf{v}_2$	Fiedler vector
$h(G)$	Cheeger constant
$\mathrm{vol}(S) = \sum_{i \in S} d_i$	Volume of vertex set