Graph Laplacian Fundamentals
Throughout our linear-algebra section, we have built up the vocabulary of linear algebra, from
vector spaces,
linear transformations,
eigendecompositions, and
symmetric matrices with their
spectral theorem to more
specialized tools like the trace and matrix norms, the
Kronecker product, and
stochastic matrices. These tools were developed in the abstract, on
\(\mathbb{R}^n\) or \(M_n(\mathbb{R})\) with no particular geometric context. The question now becomes: what
happens when we apply them to a space that carries genuine combinatorial structure?
Graphs are the simplest such structure, a finite set of nodes equipped with pairwise relations. To apply the
spectral machinery we have built, we need a matrix that faithfully encodes a graph's connectivity. The
graph Laplacian is exactly this matrix. It captures how "different" adjacent vertices are from
each other, making it the natural bridge between
graph theory and the spectral methods developed on the
preceding pages. The bridge turns out to be rich. A single matrix, defined in two lines, will give us connectivity,
clustering, frequency analysis, and diffusion, all from its eigenstructure.
Definition: Unnormalized Graph Laplacian
For a graph \(G\) with \(n\) vertices \(v_1, \ldots, v_n\),
adjacency matrix
\(\boldsymbol{A}\), and degree matrix \(\boldsymbol{D} = \operatorname{diag}(\deg(v_1), \ldots, \deg(v_n))\),
the unnormalized graph Laplacian is the matrix
\[
\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}.
\]
Its entries are given by
\[
L_{ij} = \begin{cases} \deg(v_i) & \text{if } i = j \\ -1 & \text{if } i \neq j \text{ and } v_i \sim v_j \\ 0 & \text{otherwise} \end{cases}
\]
where \(v_i \sim v_j\) means vertices \(v_i\) and \(v_j\) are adjacent.
Example:
\[
\underbrace{
\begin{bmatrix} 2 & 0 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 & 0 \\
0 & 0 & 4 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}
}_{\boldsymbol{D}}
-
\underbrace{
\begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0
\end{bmatrix}
}_{\boldsymbol{A}}
=
\underbrace{
\begin{bmatrix} 2 & -1 & -1 & 0 & 0 \\
-1 & 2 & -1 & 0 & 0 \\
-1 & -1 & 4 & -1 & -1 \\
0 & 0 & -1 & 1 & 0 \\
0 & 0 & -1 & 0 & 1
\end{bmatrix}
}_{\boldsymbol{L}}
\]
The Laplacian Quadratic Form (Measuring Smoothness)
The definition \(\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}\) may appear
arbitrary, but the Laplacian has a natural interpretation through its quadratic form,
which measures how much a signal varies across the edges of the graph.
From here on we allow edge weights. A weighted graph carries a symmetric weight matrix
\(\boldsymbol{A} = (w_{ij})\) with \(w_{ij} = w_{ji} \geq 0\) and \(w_{ii} = 0\), and the vertices \(v_i\)
and \(v_j\) are adjacent, \(v_i \sim v_j\), exactly when \(w_{ij} \gt 0\). The weighted degree is
\(d_i = \sum_j w_{ij}\), the degree matrix is \(\boldsymbol{D} = \operatorname{diag}(d_1, \ldots, d_n)\),
and the Laplacian is \(\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}\) as before. The unweighted case
is \(w_{ij} \in \{0, 1\}\), which recovers the definition above. Unless a statement says otherwise, every
result below holds in the weighted setting.
Theorem: Dirichlet Energy
For any signal \(\boldsymbol{f} \in \mathbb{R}^n\) defined on the vertices of a
graph with Laplacian \(\boldsymbol{L}\), the quadratic form satisfies
\[
\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = \sum_{(i,j) \in E} w_{ij}(f_i - f_j)^2
\]
where \(w_{ij}\) is the weight of edge \((i,j)\) (equal to 1 for unweighted graphs).
This quantity is called the Dirichlet energy of \(\boldsymbol{f}\).
Proof:
Recall that \(d_i = \sum_{j} w_{ij}\) and \(\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}\). Split
the quadratic form:
\[
\begin{align*}
\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f}
&= \boldsymbol{f}^\top \boldsymbol{D} \boldsymbol{f} - \boldsymbol{f}^\top \boldsymbol{A} \boldsymbol{f} \\\\
&= \sum_{i} d_i f_i^2 - \sum_{i,j} w_{ij} f_i f_j.
\end{align*}
\]
Rewrite the degree term using \(d_i = \sum_{j} w_{ij}\), then symmetrize via \(w_{ij} = w_{ji}\):
\[
\begin{align*}
\sum_{i} d_i f_i^2
&= \sum_{i,j} w_{ij} f_i^2 \\\\
&= \tfrac{1}{2}\sum_{i,j} w_{ij} f_i^2 + \tfrac{1}{2}\sum_{i,j} w_{ij} f_j^2 \\\\
&= \tfrac{1}{2}\sum_{i,j} w_{ij} (f_i^2 + f_j^2),
\end{align*}
\]
where the second sum in the middle expression is obtained from the first by swapping the dummy indices
\(i \leftrightarrow j\) (which is free to do) and then using \(w_{ji} = w_{ij}\).
Now substitute into the split, writing the second term as
\(\sum_{i,j} w_{ij} f_i f_j = \tfrac{1}{2}\sum_{i,j} w_{ij}(2 f_i f_j)\) so that both terms share
the prefactor \(\tfrac{1}{2}\):
\[
\begin{align*}
\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f}
&= \tfrac{1}{2}\sum_{i,j} w_{ij}(f_i^2 + f_j^2) - \tfrac{1}{2}\sum_{i,j} w_{ij}(2 f_i f_j) \\\\
&= \tfrac{1}{2}\sum_{i,j} w_{ij}(f_i - f_j)^2.
\end{align*}
\]
The remaining sum ranges over all ordered pairs \((i, j)\). Since the summand \(w_{ij}(f_i - f_j)^2\)
is symmetric in \((i, j)\) and each undirected edge \(\{v_i, v_j\}\) contributes once as \((i, j)\) and
once as \((j, i)\), the prefactor \(\tfrac{1}{2}\) exactly converts the ordered-pair sum into a sum
over undirected edges:
\[
\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = \sum_{(i,j) \in E} w_{ij}(f_i - f_j)^2.
\]
The Dirichlet energy is small when adjacent vertices have similar signal values (the signal
is "smooth") and large when adjacent vertices differ significantly. The quadratic form of the Laplacian thus
measures the total squared variation of a signal across the graph's edges.
The nonnegativity of every summand also gives an immediate structural consequence.
Corollary: The Graph Laplacian is Positive Semidefinite
For any graph \(G\) (with nonnegative edge weights), the Laplacian
\(\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}\) is positive semidefinite.
In particular, every eigenvalue of \(\boldsymbol{L}\) is nonnegative.
Proof:
By Dirichlet Energy, for every
\(\boldsymbol{f} \in \mathbb{R}^n\),
\[
\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = \sum_{(i,j) \in E} w_{ij}(f_i - f_j)^2 \geq 0,
\]
since each summand has \(w_{ij} \geq 0\) and \((f_i - f_j)^2 \geq 0\). Thus \(\boldsymbol{L} \succeq 0\). By
the spectral characterization of definiteness,
all eigenvalues of \(\boldsymbol{L}\) are nonnegative.
Insight: Dirichlet Energy as a Regularizer in ML
The Dirichlet energy \(\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f}\) is widely used as a graph
regularization term in semi-supervised learning. The objective
\[
\min_{\boldsymbol{f}} \|\boldsymbol{f} - \boldsymbol{y}\|^2 + \alpha \, \boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f}
\]
penalizes label assignments where connected nodes receive different labels, encoding the smoothness
assumption that nearby nodes in a graph are likely to share the same label. This principle underlies
label propagation and graph-based semi-supervised learning, and it motivates the smoothing bias of message
passing in Graph Neural Networks.
Normalized Laplacians
The unnormalized Laplacian \(\boldsymbol{L}\) can be biased by vertices with
large degrees, since high-degree vertices contribute disproportionately to the
Dirichlet energy. To account for varying degrees, two normalized Laplacians
are commonly used.
Definition: Symmetric Normalized Laplacian
For a graph without isolated vertices (so that \(\boldsymbol{D}\) is invertible), the symmetric
normalized Laplacian is
\[
\mathcal{L}_{sym} = \boldsymbol{D}^{-1/2} \boldsymbol{L} \boldsymbol{D}^{-1/2} = \boldsymbol{I} - \boldsymbol{D}^{-1/2} \boldsymbol{A} \boldsymbol{D}^{-1/2}.
\]
As a symmetric congruence transform of \(\boldsymbol{L}\), it is itself symmetric and admits
an orthonormal eigenbasis.
Definition: Random Walk Normalized Laplacian
For a graph without isolated vertices, the random walk normalized Laplacian is
\[
\begin{align*}
\mathcal{L}_{rw} &= \boldsymbol{D}^{-1} \boldsymbol{L} \\\\
&= \boldsymbol{I} - \boldsymbol{D}^{-1} \boldsymbol{A} = \boldsymbol{I} - \boldsymbol{P}.
\end{align*}
\]
Here \(\boldsymbol{P} = \boldsymbol{D}^{-1}\boldsymbol{A}\), with entries \(P_{ij} = w_{ij}/d_i\), is the
transition matrix of the random walk on \(G\) that steps from \(v_i\) to \(v_j\) with probability \(P_{ij}\).
It is written row-wise, with each row summing to one, which is the transpose of the column convention used for
stochastic matrices on the previous page. Consequently \(\lambda\) is an eigenvalue of \(\mathcal{L}_{rw}\)
exactly when \(1 - \lambda\) is an eigenvalue of \(\boldsymbol{P}\).
Theorem: Spectrum of the Normalized Laplacians
For a graph without isolated vertices, the symmetric and random-walk normalized Laplacians share the same
spectrum, and all eigenvalues lie in the interval \([0, 2]\):
\[
\sigma(\mathcal{L}_{sym}) = \sigma(\mathcal{L}_{rw}) \subset [0, 2].
\]
Proof:
(i) Same spectrum.
A direct computation gives
\[
\begin{align*}
\mathcal{L}_{rw}
&= \boldsymbol{D}^{-1} \boldsymbol{L} \\\\
&= \boldsymbol{D}^{-1/2} \bigl(\boldsymbol{D}^{-1/2} \boldsymbol{L} \boldsymbol{D}^{-1/2}\bigr) \boldsymbol{D}^{1/2} \\\\
&= \boldsymbol{D}^{-1/2} \mathcal{L}_{sym} \boldsymbol{D}^{1/2}.
\end{align*}
\]
Thus \(\mathcal{L}_{rw}\) is similar to \(\mathcal{L}_{sym}\) via the invertible transform
\(\boldsymbol{D}^{1/2}\).
Similar matrices have identical eigenvalues,
so \(\sigma(\mathcal{L}_{rw}) = \sigma(\mathcal{L}_{sym})\).
(ii) Lower bound \(\lambda \geq 0\).
For any \(\boldsymbol{g} \in \mathbb{R}^n\), set
\(\boldsymbol{f} = \boldsymbol{D}^{-1/2}\boldsymbol{g}\). Then
\[
\begin{align*}
\boldsymbol{g}^\top \mathcal{L}_{sym} \boldsymbol{g}
&= \boldsymbol{g}^\top \boldsymbol{D}^{-1/2} \boldsymbol{L} \boldsymbol{D}^{-1/2} \boldsymbol{g} \\\\
&= \boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} \\\\
&\geq 0
\end{align*}
\]
since \(\boldsymbol{L}\) is
positive semidefinite. Hence
\(\mathcal{L}_{sym} \succeq 0\), giving \(\lambda \geq 0\) for every eigenvalue.
(iii) Upper bound \(\lambda \leq 2\).
Equivalently, we show
\(2\boldsymbol{I} - \mathcal{L}_{sym}\) is positive semidefinite. Using
\(\mathcal{L}_{sym} = \boldsymbol{I} - \boldsymbol{D}^{-1/2}\boldsymbol{A}\boldsymbol{D}^{-1/2}\),
\[
2\boldsymbol{I} - \mathcal{L}_{sym} = \boldsymbol{I} + \boldsymbol{D}^{-1/2}\boldsymbol{A}\boldsymbol{D}^{-1/2}.
\]
A direct edge-sum expansion analogous to the Dirichlet energy calculation gives, for any
\(\boldsymbol{g} \in \mathbb{R}^n\) (with \(g_i\) the \(i\)-th entry),
\[
\begin{align*}
\boldsymbol{g}^\top (2\boldsymbol{I} - \mathcal{L}_{sym}) \boldsymbol{g}
&= \sum_{(i,j) \in E} w_{ij} \left(\frac{g_i}{\sqrt{d_i}} + \frac{g_j}{\sqrt{d_j}}\right)^2 \\\\
&\geq 0,
\end{align*}
\]
where \(d_i = \sum_j w_{ij}\). (The identity is verified by expanding the square and matching the diagonal term
\(\sum_i g_i^2\) with the contributions \(\sum_j w_{ij} \cdot (1/d_i) = 1\) from the edges incident to \(v_i\),
and the cross term with the off-diagonal entries of
\(\boldsymbol{D}^{-1/2}\boldsymbol{A}\boldsymbol{D}^{-1/2}\).) Thus
\(2\boldsymbol{I} - \mathcal{L}_{sym} \succeq 0\), giving \(\lambda \leq 2\).
The choice between the two normalized forms depends on the application. The symmetric form \(\mathcal{L}_{sym}\) is
preferred when symmetry is needed (for example, for invoking the spectral theorem directly, or for GCN-style
architectures), while \(\mathcal{L}_{rw}\) connects directly to random walk analysis.
Spectral Properties
The Graph Laplacian is Positive Semidefinite (a
direct corollary of Dirichlet energy) immediately constrains \(\boldsymbol{L}\)'s eigenvalue structure. Since
\(\boldsymbol{L}\) is also real and symmetric, the
spectral theorem guarantees a
complete set of real, nonnegative eigenvalues and orthonormal eigenvectors. These eigenvalues and eigenvectors
encode detailed information about the graph's connectivity.
The eigendecomposition of the unnormalized Laplacian \(\boldsymbol{L}\) is:
\[
\boldsymbol{L} = \boldsymbol{V}\,\boldsymbol{\Lambda}\,\boldsymbol{V}^\top,
\quad
\boldsymbol{\Lambda} = \operatorname{diag}(\lambda_0, \lambda_1, \ldots, \lambda_{n-1}),
\]
with ordered eigenvalues
\[
0 = \lambda_0 \leq \lambda_1 \leq \cdots \leq \lambda_{n-1},
\]
and orthonormal eigenvectors \(\boldsymbol{v}_0, \ldots, \boldsymbol{v}_{n-1}\) (which form a basis for
\(\mathbb{R}^n\)).
The Smallest Eigenvalue (\(\lambda_0 = 0\))
A direct computation shows that the constant vector \(\boldsymbol{1} \in \mathbb{R}^n\) (all entries equal to one)
is always in the kernel of \(\boldsymbol{L}\):
\[
\boldsymbol{L}\boldsymbol{1} = (\boldsymbol{D} - \boldsymbol{A})\boldsymbol{1} = \boldsymbol{D}\boldsymbol{1} - \boldsymbol{A}\boldsymbol{1} = \boldsymbol{d} - \boldsymbol{d} = \boldsymbol{0}
\]
(where \(\boldsymbol{d}\) is the vector of degrees). So \(\lambda_0 = 0\) is always an eigenvalue. But is
it the only zero eigenvalue, and does \(\boldsymbol{1}\) span the entire zero eigenspace? The
answer depends on whether the graph is connected. More generally, the zero eigenspace encodes the graph's
component structure exactly.
Theorem: Kernel of \(\boldsymbol{L}\) and Connected Components
Let \(G\) be a graph with \(c\) connected components \(C_1, \ldots, C_c\), and let
\(\boldsymbol{1}_{C_k} \in \mathbb{R}^n\) denote the indicator vector of \(C_k\) (entry \(1\) on vertices in
\(C_k\), zero elsewhere). Then
\[
\ker \boldsymbol{L} = \operatorname{span}\{\boldsymbol{1}_{C_1}, \ldots, \boldsymbol{1}_{C_c}\},
\]
so the multiplicity of the zero eigenvalue equals the number of connected components:
\(\dim \ker \boldsymbol{L} = c\). In particular, \(G\) is connected if and only if \(\lambda_0 = 0\) is a
simple eigenvalue. When \(n \geq 2\), this is equivalent to \(\lambda_1 \gt 0\).
Proof:
Step 1: \(\boldsymbol{f} \in \ker \boldsymbol{L}\) if and only if \(\boldsymbol{f}\) is constant on each connected component.
(\(\Rightarrow\))
If \(\boldsymbol{L}\boldsymbol{f} = \boldsymbol{0}\), then
\(\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = \boldsymbol{f}^\top \boldsymbol{0} = 0\). By
Dirichlet Energy,
\[
0 = \boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = \sum_{(i,j) \in E} w_{ij}(f_i - f_j)^2.
\]
Each summand is nonnegative (weights \(w_{ij} \gt 0\) on edges), so every edge term vanishes: \(f_i = f_j\)
whenever \(v_i \sim v_j\). By transitivity along paths within each connected component, \(\boldsymbol{f}\) is
constant on each component.
(\(\Leftarrow\))
Conversely, suppose \(\boldsymbol{f}\) is constant on each component. Then \(f_i = f_j\)
for every edge \((i, j) \in E\), so \(\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = 0\) by the same
Dirichlet formula. Since \(\boldsymbol{L}\) is real symmetric, the
spectral theorem gives an
orthonormal eigenbasis \(\boldsymbol{v}_0, \ldots, \boldsymbol{v}_{n-1}\) with eigenvalues
\(0 \leq \lambda_0 \leq \cdots \leq \lambda_{n-1}\) (nonnegativity by
positive semidefiniteness). Expanding
\(\boldsymbol{f} = \sum_k b_k \boldsymbol{v}_k\) in this basis,
\[
0 = \boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f} = \sum_k \lambda_k b_k^2,
\]
and since each \(\lambda_k b_k^2 \geq 0\), every summand must vanish. Thus \(b_k = 0\) whenever
\(\lambda_k \gt 0\), so \(\boldsymbol{f}\) lies in the span of eigenvectors with eigenvalue zero, that is,
\(\boldsymbol{f} \in \ker \boldsymbol{L}\).
Step 2: \(\{\boldsymbol{1}_{C_1}, \ldots, \boldsymbol{1}_{C_c}\}\) is a basis of \(\ker \boldsymbol{L}\).
Each \(\boldsymbol{1}_{C_k}\) is constant on its own component (value \(1\)) and constant on every other
component (value \(0\)), so by Step 1, \(\boldsymbol{1}_{C_k} \in \ker \boldsymbol{L}\). They are linearly
independent because their supports \(C_1, \ldots, C_c\) are pairwise disjoint. Any nontrivial combination
\(\sum_k a_k \boldsymbol{1}_{C_k}\) with some \(a_k \neq 0\) is nonzero on \(C_k\). Conversely, any
\(\boldsymbol{f} \in \ker \boldsymbol{L}\) is, by Step 1, constant on each component, say with value \(a_k\) on
\(C_k\), and thus \(\boldsymbol{f} = \sum_k a_k \boldsymbol{1}_{C_k}\) lies in the span. Therefore
\(\dim \ker \boldsymbol{L} = c\).
Step 3: Connected case.
If \(G\) is connected, \(c = 1\) and \(\ker \boldsymbol{L} = \operatorname{span}\{\boldsymbol{1}\}\) is
one-dimensional. Hence \(\lambda_0 = 0\) is simple. When \(n \geq 2\), the next eigenvalue
therefore satisfies \(\lambda_1 \gt 0\).
The Fiedler Vector and Algebraic Connectivity
While the multiplicity of the eigenvalue \(\lambda_0 = 0\) tells us whether the graph is connected (and how many
components it has), the second-smallest eigenvalue \(\lambda_1\) quantifies how well the graph is connected.
It is arguably the single most informative spectral quantity of a graph.
Definition: Algebraic Connectivity
The second-smallest eigenvalue \(\lambda_1\) of the Laplacian \(\boldsymbol{L}\) is called the
algebraic connectivity (or Fiedler value) of the graph.
Definition: Fiedler Vector
An eigenvector \(\boldsymbol{v}_1\) corresponding to the algebraic connectivity
\(\lambda_1\) is called a Fiedler vector.
The sign pattern of a Fiedler vector splits the vertices into two sets, and this split often exposes the graph's
sparsest cut. That observation is the seed of spectral clustering, taken up below.
Theorem: Algebraic Connectivity and Graph Connectedness
For a graph \(G\) with \(n \geq 2\) vertices, \(\lambda_1 \gt 0\) if and only if \(G\) is connected.
This is an immediate corollary of
Theorem: Kernel of \(\boldsymbol{L}\) and Connected Components:
\(G\) is connected if and only if \(c = 1\), and by the theorem this holds if and only if
\(\dim \ker \boldsymbol{L} = 1\), that is, if and only if \(\lambda_1 \gt 0\).
Heuristically, a larger \(\lambda_1\) indicates a more "well-connected" graph, one with less of a "bottleneck". The
next subsection turns this heuristic into an inequality for the normalized Laplacian.
The Spectral Gap and Cheeger's Inequality
The Fiedler value \(\lambda_1\) provides a spectral measure of connectivity, but
one might ask: does it correspond to a genuine combinatorial notion of "bottleneck"?
Cheeger's inequality makes this connection precise, relating the spectral gap of the normalized
Laplacian to the Cheeger constant, a minimum cut normalized by volume, defined below.
Theorem: Cheeger's Inequality
Let \(G\) have no isolated vertices and vertex set \(V\). For \(\varnothing \neq S \subsetneq V\), write
\(|\partial S|\) for the total weight of the edges with exactly one endpoint in \(S\) (their number, in the
unweighted case) and \(\operatorname{Vol}(S) = \sum_{v_i \in S} d_i\) for the total degree of \(S\). The
Cheeger constant (or conductance) \(h(G)\) measures the "bottleneck" of the graph by finding
the minimum cut normalized by the volume of the smaller set:
\[
h(G) = \min_{\varnothing \neq S \subsetneq V} \frac{|\partial S|}{\min(\operatorname{Vol}(S), \operatorname{Vol}(V \setminus S))}.
\]
Let \(\lambda_1^{\mathrm{norm}}\) denote the second smallest eigenvalue of the
normalized Laplacian \(\mathcal{L}_{sym}\) (equivalently \(\mathcal{L}_{rw}\), since the two
share the same spectrum by
Spectrum of the Normalized Laplacians).
Cheeger's inequality states
\[
\frac{h(G)^2}{2} \leq \lambda_1^{\mathrm{norm}} \leq 2 h(G).
\]
This fundamental result links the spectral gap directly to the graph's geometric structure. A small
\(\lambda_1^{\mathrm{norm}}\) guarantees the existence of a "bottleneck" (a sparse cut), while a large
\(\lambda_1^{\mathrm{norm}}\) certifies that the graph is well-connected (an expander graph).
Note that this \(\lambda_1^{\mathrm{norm}}\) is for the normalized Laplacian and is distinct
from the unnormalized Fiedler value \(\lambda_1\) of \(\boldsymbol{L}\) discussed above. The two are
generally different numerically, though they agree qualitatively on connectivity (both are zero if and
only if \(G\) is disconnected).
The proof is nontrivial. The lower bound in particular requires a careful analysis of the level sets of an
eigenvector of \(\mathcal{L}_{rw}\) for \(\lambda_1^{\mathrm{norm}}\). We omit it here.
Insight: The Spectral Gap in Network Science and ML
The spectral gap, \(\lambda_1\) or its normalized counterpart \(\lambda_1^{\mathrm{norm}}\), has direct
practical significance. In graph-based semi-supervised learning, a large spectral gap means
that label information propagates quickly through the graph, which is generally associated with better
generalization from few labeled examples. In network robustness, \(\lambda_1\) measures how
resilient a network is to partitioning. Networks with small algebraic connectivity are vulnerable to targeted
edge removal. The Cheeger inequality thus provides a principled criterion for evaluating graph quality in
applications from social network analysis to mesh generation in computational geometry.
Graph Signal Processing (GSP)
The GSP framework provides a crucial link between graph theory and classical signal analysis. It
re-interprets the Laplacian's eigenvectors as a Fourier basis for signals on the graph,
making it the natural generalization of the classical
Fourier transform to irregular domains.
The eigenvalues \(\lambda_k\) represent frequencies:
- Small \(\lambda_k\) (for example, \(\lambda_0, \lambda_1\)) \(\leftrightarrow\) Low Frequencies.
The corresponding eigenvectors \(\boldsymbol{v}_k\) vary slowly across edges (they are "smooth").
- Large \(\lambda_k\) \(\leftrightarrow\) High Frequencies. The eigenvectors
\(\boldsymbol{v}_k\) oscillate rapidly, with adjacent nodes having very different values.
This frequency interpretation connects back to the Dirichlet energy. By expanding
\(\boldsymbol{f}\) in the eigenbasis, we obtain a spectral decomposition of the Laplacian quadratic form:
Theorem: Spectral Expression of Dirichlet Energy
For any graph signal \(\boldsymbol{f}\) with Graph Fourier Transform
\(\hat{\boldsymbol{f}} = \boldsymbol{V}^\top \boldsymbol{f}\),
\[
\begin{align*}
\boldsymbol{f}^\top \boldsymbol{L} \boldsymbol{f}
&= \boldsymbol{f}^\top (\boldsymbol{V} \boldsymbol{\Lambda} \boldsymbol{V}^\top) \boldsymbol{f} \\\\
&= (\boldsymbol{V}^\top \boldsymbol{f})^\top \boldsymbol{\Lambda} (\boldsymbol{V}^\top \boldsymbol{f}) \\\\
&= \hat{\boldsymbol{f}}^\top \boldsymbol{\Lambda} \hat{\boldsymbol{f}} \\\\
&= \sum_{k=0}^{n-1} \lambda_k \hat{f}_k^2.
\end{align*}
\]
Terminology note. The GSP literature often calls this identity
Parseval's theorem on graphs, by loose analogy with the classical
Parseval identity.
Strictly, classical Parseval is a norm-preservation statement. Its graph analogue is
\(\|\boldsymbol{f}\|^2 = \|\hat{\boldsymbol{f}}\|^2\), which follows directly from the orthogonality of
\(\boldsymbol{V}\). The identity above is a weighted spectral sum with eigenvalues as weights, so it is more
accurately a spectral decomposition of the Dirichlet quadratic form. We adopt the descriptive name here to
avoid conflating the two, while recognizing the Parseval naming is widespread in practice.
This identity shows that the Dirichlet energy of a signal equals the weighted sum of its
spectral components, where each frequency \(\lambda_k\) weights the corresponding
coefficient \(\hat{f}_k^2\). High-frequency components (large \(\lambda_k\)) contribute
more to the energy, which is why smooth signals have small Dirichlet energy.
Practical Computations
The spectral theory above assumes access to the full eigendecomposition of \(\boldsymbol{L}\), but computing all
\(n\) eigenvalues and eigenvectors requires \(O(n^3)\) operations, which is prohibitive for graphs with millions of
vertices. In practice, many applications, such as spectral clustering and graph partitioning, require only the few
smallest eigenvalues and their eigenvectors, which can be computed efficiently using iterative methods.
- Power Iteration: A simple method to find the dominant eigenvector (corresponding to
\(\lambda_{\max}\)). It can be adapted (as "inverse iteration") to find the smallest eigenvalues.
-
Lanczos Algorithm: A powerful iterative method for
finding the \(k\) smallest (or largest) eigenvalues and eigenvectors
of a symmetric matrix. It is far more efficient than full decomposition
when \(k \ll n\).
Modern Applications
The properties of the graph Laplacian are fundamental to many
algorithms in machine learning and data science.
Spectral Clustering
One of the most powerful applications of the Laplacian is spectral clustering.
The challenge with many real-world datasets is that clusters are not
"spherical" or easily separated by distance, which is a key assumption of
algorithms like K-means.
Spectral clustering re-frames this problem. Instead of clustering points by distance, it clusters them by
connectivity. The Fiedler vector (\(\boldsymbol{v}_1\)) and the subsequent eigenvectors
(\(\boldsymbol{v}_2, \ldots, \boldsymbol{v}_{r-1}\)) provide a new, low-dimensional "spectral embedding" of the
data. In this new space, complex cluster structures (like intertwined moons or spirals) are "unrolled" and often
become linearly separable.
The general algorithm involves using the first \(r\) eigenvectors of the Laplacian (often \(\mathcal{L}_{sym}\))
to create an \(n \times r\) embedding matrix, and then running a simple algorithm like K-means on the
rows of that matrix.
We cover this topic in full detail, including the formal algorithm and
its comparison to K-means, on our dedicated page.
→ See: Clustering Algorithms
Graph Neural Networks (GNNs)
Many GNNs, like Graph Convolutional Networks (GCNs), are based on
spectral filtering. The idea is to apply a filter
\(g(\boldsymbol{\Lambda})\) to the graph signal's "frequencies."
\[
\boldsymbol{f}_{out} = g(\boldsymbol{L}) \boldsymbol{f}_{in} =
\boldsymbol{V} g(\boldsymbol{\Lambda}) \boldsymbol{V}^\top \boldsymbol{f}_{in}.
\]
This is a "convolution" in the graph spectral domain.
Directly computing this is too expensive. Instead, methods like ChebNet approximate the filter
\(g(\cdot)\), here applied to \(\mathcal{L}_{sym}\), using a \(K\)-th order polynomial:
\[
g_\theta(\mathcal{L}_{sym}) \approx \sum_{k=0}^K \theta_k T_k(\tilde{\boldsymbol{L}})
\]
where \(T_k\) are Chebyshev polynomials. Crucially, \(\tilde{\boldsymbol{L}}\) is the rescaled
Laplacian, which rescales the spectrum of \(\mathcal{L}_{sym}\) from \([0, \lambda_{\max}]\) onto
\([-1, 1]\), where \(\lambda_{\max}\) is its largest eigenvalue:
\[
\tilde{\boldsymbol{L}} = \frac{2}{\lambda_{\max}}\mathcal{L}_{sym} - \boldsymbol{I}.
\]
This approximation allows for localized and efficient computations (a
\(K\)-hop neighborhood) without ever computing eigenvectors. The standard GCN is a first-order approximation
(\(K=1\)) of this process.
Diffusion, Label Propagation, and GNNs
The Laplacian is the canonical "generator" of diffusion processes, whether as the continuous operator \(\Delta\) or
as its graph counterpart \(\boldsymbol{L}\). On a continuous domain, the heat equation
\(\partial u/\partial t = \kappa\,\Delta u\) (with diffusivity \(\kappa \gt 0\)) describes how temperature spreads
through space. On a graph, the same role
is played by \(\boldsymbol{L}\), and the resulting discrete diffusion is the mathematical foundation for many GNN
architectures and semi-supervised learning algorithms.
For example, the classic Label Propagation algorithm for semi-supervised learning is a direct
application of this. Imagine "clamping" the "heat" of labeled nodes (for example, 1 for class A and 0 for
class B) and letting that heat diffuse through the graph to unlabeled nodes. The final "temperature" of a node
is its classification.
Formalizing this intuition gives the graph heat equation. It is the direct discrete analogue of
the classical heat equation on a continuous domain, in which the negative Laplacian \(-\Delta\) is replaced by the
graph Laplacian \(\boldsymbol{L}\) itself (both are positive semidefinite, so the sign of the equation matches):
Theorem: Heat Diffusion on Graphs
Let \(\boldsymbol{L}\) be the Laplacian of a graph on \(n\) vertices. The graph heat equation
is the linear system
\[
\frac{d\boldsymbol{u}}{dt} = -\boldsymbol{L} \boldsymbol{u}
\]
for a differentiable \(\boldsymbol{u} : [0, \infty) \to \mathbb{R}^n\). For every initial heat distribution
\(\boldsymbol{u}(0) \in \mathbb{R}^n\) it has exactly one solution, which describes how that distribution
spreads over the graph:
\[
\boldsymbol{u}(t) = e^{-t\boldsymbol{L}} \boldsymbol{u}(0),
\]
where
\(e^{-t\boldsymbol{L}} = \sum_{k=0}^{\infty} \frac{(-t\boldsymbol{L})^k}{k!} = \boldsymbol{V} e^{-t\boldsymbol{\Lambda}} \boldsymbol{V}^\top\)
and \(e^{-t\boldsymbol{\Lambda}} = \operatorname{diag}(e^{-t\lambda_0}, \ldots, e^{-t\lambda_{n-1}})\).
Proof:
Write \(\boldsymbol{L} = \boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^\top\) with \(\boldsymbol{V}\)
orthogonal and \(\boldsymbol{\Lambda} = \operatorname{diag}(\lambda_0, \ldots, \lambda_{n-1})\), as the
spectral theorem permits.
Since \(\boldsymbol{V}^\top \boldsymbol{V} = \boldsymbol{I}\), induction gives
\(\boldsymbol{L}^k = \boldsymbol{V}\boldsymbol{\Lambda}^k\boldsymbol{V}^\top\) for every \(k \geq 0\), so the
partial sums of the series satisfy
\[
\sum_{k=0}^{N} \frac{(-t\boldsymbol{L})^k}{k!}
= \boldsymbol{V} \left( \sum_{k=0}^{N} \frac{(-t\boldsymbol{\Lambda})^k}{k!} \right) \boldsymbol{V}^\top.
\]
The matrix in parentheses is diagonal, with \(j\)-th entry \(\sum_{k=0}^{N} (-t\lambda_j)^k/k!\), which
converges to \(e^{-t\lambda_j}\) as \(N \to \infty\) by the scalar exponential series. Hence the matrix series
converges entrywise to \(\boldsymbol{V} e^{-t\boldsymbol{\Lambda}} \boldsymbol{V}^\top\), which justifies the
two expressions for \(e^{-t\boldsymbol{L}}\).
Existence. Set
\(\boldsymbol{u}(t) = \boldsymbol{V} e^{-t\boldsymbol{\Lambda}} \boldsymbol{V}^\top \boldsymbol{u}(0)\).
Differentiating the diagonal entries gives
\(\frac{d}{dt} e^{-t\boldsymbol{\Lambda}} = -\boldsymbol{\Lambda} e^{-t\boldsymbol{\Lambda}}\), and
multiplication by the constant matrices \(\boldsymbol{V}\) and \(\boldsymbol{V}^\top \boldsymbol{u}(0)\)
commutes with differentiation, so
\[
\begin{align*}
\frac{d\boldsymbol{u}}{dt}
&= \boldsymbol{V} (-\boldsymbol{\Lambda}) e^{-t\boldsymbol{\Lambda}} \boldsymbol{V}^\top \boldsymbol{u}(0) \\\\
&= -(\boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^\top)(\boldsymbol{V} e^{-t\boldsymbol{\Lambda}} \boldsymbol{V}^\top \boldsymbol{u}(0)) \\\\
&= -\boldsymbol{L}\boldsymbol{u}(t),
\end{align*}
\]
where the middle step inserts \(\boldsymbol{V}^\top \boldsymbol{V} = \boldsymbol{I}\).
Uniqueness. Let \(\boldsymbol{u}\) be any differentiable solution and set
\(\boldsymbol{y}(t) = \boldsymbol{V}^\top \boldsymbol{u}(t)\). Then
\[
\begin{align*}
\boldsymbol{y}'
&= \boldsymbol{V}^\top \boldsymbol{u}' \\\\
&= -\boldsymbol{V}^\top \boldsymbol{L} \boldsymbol{u} \\\\
&= -\boldsymbol{\Lambda} \boldsymbol{V}^\top \boldsymbol{u} \\\\
&= -\boldsymbol{\Lambda}\boldsymbol{y},
\end{align*}
\]
that is, \(y_j' = -\lambda_j y_j\) for each coordinate \(j\). For each \(j\), the product rule gives
\[
\begin{align*}
\frac{d}{dt}\bigl(e^{\lambda_j t} y_j(t)\bigr)
&= e^{\lambda_j t}\bigl(\lambda_j y_j(t) + y_j'(t)\bigr) \\\\
&= 0,
\end{align*}
\]
so, by the
mean value theorem
(applied with \(n = 1\) on the open interval \((0, \infty)\), and extended to the endpoint \(0\)
by continuity), \(e^{\lambda_j t} y_j(t)\) is constant on \([0, \infty)\) and equals its value
\(y_j(0)\) at \(t = 0\). Thus
\(\boldsymbol{y}(t) = e^{-t\boldsymbol{\Lambda}} \boldsymbol{y}(0)\), and
\(\boldsymbol{u}(t) = \boldsymbol{V}\boldsymbol{y}(t)\) equals
\(\boldsymbol{V} e^{-t\boldsymbol{\Lambda}} \boldsymbol{V}^\top \boldsymbol{u}(0)\), the
solution constructed above.
The matrix \(e^{-t\boldsymbol{L}}\) is known as the graph heat kernel. It acts as a low-pass
filter, since high-frequency components \(e^{-t\lambda_k}\) with large \(\lambda_k\) decay fastest. That decay is
the discrete counterpart of the instantaneous-smoothing phenomenon of the continuous heat equation, where high
spatial frequencies are damped by a Gaussian factor \(e^{-\kappa\xi^2 t}\) in the Fourier domain. The continuous
version, including the eigenvalue scaling \((j\pi/\ell)^2\) of the \(j\)-th mode on a bounded interval of length
\(\ell\) and the Gaussian heat kernel that solves the problem on \(\mathbb{R}\), is treated in
The Heat Equation.
The same diffusive process is also the formal explanation for the over-smoothing problem in deep
GNNs. Repeated application of a smoothing operator such as \(e^{-t\boldsymbol{L}}\), or of the GCN propagation
matrix introduced below, drives features toward the eigenspace for the eigenvalue \(1\) of that operator. For
\(e^{-t\boldsymbol{L}}\), this eigenspace is \(\ker \boldsymbol{L}\), the signals that are constant on every connected
component. Within each connected component, node representations therefore become indistinguishable (for the
GCN matrix, up to a degree-dependent scale).
More advanced models take this connection to its logical conclusion, explicitly modeling GNNs as continuous-time
graph differential equations. This links the abstract mathematics of differential equations directly to the design
of modern ML models.
Insight: From Spectral Filtering to Message Passing
The spectral viewpoint (filtering via \(\boldsymbol{V} g(\boldsymbol{\Lambda}) \boldsymbol{V}^\top\)) and the
spatial viewpoint (aggregating information from neighbors) are unified in GCNs. Kipf & Welling (2017) proposed
the renormalization trick:
\[
\tilde{\boldsymbol{A}} = \boldsymbol{A} + \boldsymbol{I}, \quad \tilde{\boldsymbol{D}}_{ii} = \sum_j \tilde{\boldsymbol{A}}_{ij}.
\]
Replacing \(\boldsymbol{A}\) with \(\tilde{\boldsymbol{A}}\) (adding self-loops) serves two mathematical
purposes. It preserves a node's own features during aggregation, and, critically, it controls the
spectral radius. Without this, the operation
\(\boldsymbol{I} + \boldsymbol{D}^{-1/2}\boldsymbol{A}\boldsymbol{D}^{-1/2}\) has eigenvalues in \([0, 2]\),
so repeated application can amplify some components, which can lead to numerical instability (exploding or
vanishing gradients) in deep networks. After renormalization, the operator
\(\tilde{\boldsymbol{D}}^{-1/2}\tilde{\boldsymbol{A}}\tilde{\boldsymbol{D}}^{-1/2}\) has all eigenvalues in
\([-1, 1]\), with largest eigenvalue exactly \(1\) (the range follows from the same edge-sum arguments run on
the graph with a self-loop at every vertex, and the eigenvector
\(\tilde{\boldsymbol{D}}^{1/2}\boldsymbol{1}\) attains \(1\)), so repeated application never amplifies a
component while the low-pass filtering effect is maintained.
Other Applications
- Recommender Systems:
Used extensively in industry to model user-item interactions as a graph, often leveraging Laplacian-regularized
matrix factorization or graph-based diffusion models to predict preferences.
- Protein Structure:
Foundational to structural bioinformatics, where graph neural networks represent a protein as a residue graph
(amino acids as nodes, spatial contacts as edges) and learn from its geometry with Laplacian-based or
message-passing convolutions.
- Electrical Networks & Effective Resistance:
Treating each edge as a unit resistor, the
pseudoinverse
\(\boldsymbol{L}^\dagger\) encodes effective resistance between vertex pairs. Effective resistance is
a geometric distance on the graph induced by random-walk commute times, with applications in chip design,
network tomography, and graph embeddings.
- Matrix-Tree Theorem (Kirchhoff):
For an unweighted graph, any cofactor of \(\boldsymbol{L}\) equals the number of spanning trees
of \(G\). This combinatorial identity connects Laplacian spectra to graph enumeration and is foundational in
statistical physics and random graph theory.
- Computer Vision:
Historically used for image segmentation and denoising via graph cuts (minimum cut problems, which are directly
related to the Laplacian quadratic form).
Looking Ahead
The graph Laplacian closes the matrix-theoretic arc of our linear-algebra section. We began with linear systems, linear maps,
and vector spaces, then developed the spectral theory of symmetric matrices. Now we have deployed that theory on
a concrete combinatorial object, a graph, to recover connectivity, clustering, frequency, and diffusion, all
from a single eigendecomposition. The static algebraic tools developed so far have come together into a
dynamical, geometric picture.
Connection to the Incidence Matrix
Our definition \(\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}\) is combinatorial, in that it starts from
adjacency counts. A second, deeper construction is available. Orient each edge arbitrarily and form the
oriented incidence matrix \(\boldsymbol{B} \in \mathbb{R}^{n \times m}\), where \(m\) is the number
of edges. It places \(+1\) at the tail and \(-1\) at the head of each edge. For an unweighted graph, the
Laplacian admits the factorization
\[
\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top.
\]
This factorization is the graph-theoretic analogue of the continuous identity \(\Delta = \nabla \cdot \nabla\)
(with the sign flip \(\boldsymbol{L} \leftrightarrow -\Delta\) noted above), the operator at the heart of
the Laplace equation. The Laplacian is the
composition of a discrete gradient (\(\boldsymbol{B}^\top\), mapping vertex potentials to edge
differences) with a discrete divergence (\(\boldsymbol{B}\), mapping edge flows to vertex net outflows).
The factorization makes positive semidefiniteness immediate, since
\(\boldsymbol{x}^\top\boldsymbol{L}\boldsymbol{x} = \|\boldsymbol{B}^\top\boldsymbol{x}\|^2\). It also opens the
door to cycle/cut space decompositions, Kirchhoff's current law, and the cohomological picture of graphs.
This perspective is developed in full in
Incidence Structure & Cycle/Cut Spaces,
where the Laplacian reappears as the degree-zero case of a much larger object: the Hodge Laplacian on
a simplicial complex.
Toward Continuous Symmetry: Lie Theory
The symmetric matrices that dominated the linear-algebra pages came with a natural symmetry group, the orthogonal
group, acting by conjugation \(A \mapsto Q A Q^\top\). We have treated this group primarily as a collection of
matrices, useful for diagonalizing operators and preserving inner products, without developing the group's own
geometric or infinitesimal structure. The pages ahead upgrade this picture. Lie groups and their
associated Lie algebras treat \(O(n)\), \(SO(n)\), and their cousins as smooth manifolds, with
tangent structure and exponential maps connecting the two.
We will find that the matrix exponential \(e^{tX}\) plays, in this continuous setting, exactly the role that the
power \(P^t\) played for the stochastic matrices of the
previous page, and that the heat-diffusion kernel
\(e^{-t\boldsymbol{L}}\) we derived above is the graph-theoretic shadow of the same construction. Lie theory will
give us the vocabulary for rotation, rigid motion, and gauge symmetry. These are the geometric counterparts of the
structures on which spectral clustering and the Fiedler vector are built.
Toward Geometric Deep Learning
The most immediate destination beyond this page is Graph Neural Networks and, more broadly,
Geometric Deep Learning. Many architectural ideas in the spectral GNN family draw on the
properties of the graph Laplacians developed on this page. These ideas include spectral filtering, Chebyshev polynomial
approximations, the GCN renormalization trick, and heat-kernel diffusion. The same properties also explain
over-smoothing and motivate graph differential equations. Spectral GNNs are, at their core, linear algebraic
operators designed to act diagonally in the eigenbasis of a graph Laplacian (\(\boldsymbol{L}\), \(\mathcal{L}_{sym}\),
or the renormalized \(\boldsymbol{I} - \tilde{\boldsymbol{D}}^{-1/2}\tilde{\boldsymbol{A}}\tilde{\boldsymbol{D}}^{-1/2}\)). Spatial or
message-passing GNNs with a permutation-invariant aggregation (GAT, for example, whose aggregation weights depend on
the features) are in general not filters of this form, but they still respect the graph's permutation symmetries,
as spectral filters \(g(\boldsymbol{L})\) do.
The same principle generalizes. On a smooth manifold, the relevant operator is the Laplace-Beltrami operator. On a
Lie group, it is the Casimir element. On a simplicial complex, it is the
Hodge Laplacian. The graph Laplacian is the
simplest, cleanest instance of a pattern that will recur throughout the geometric tracks of this curriculum.
