Spectral Graph Theory

This node assumes you already know basic eigenvalues/eigenvectors ($A\mathbf{v}=\lambda\mathbf{v}$) and graph representations. For spectral graph theory, a few extra prerequisites matter a lot; this section makes them explicit and flags where each appears.

Linear algebra prerequisites

1) Symmetric eigendecomposition (for real symmetric matrices)

• •Fact: If $M$ is real symmetric, it has real eigenvalues and an orthonormal eigenbasis. You can write $M = Q\Lambda Q^\top$.
• •Where used: All core matrices for undirected graphs (adjacency $A$, Laplacian $L$, normalized Laplacian $\mathcal{L}$) are symmetric, so we can order eigenvalues and reason variationally.

2) Quadratic forms and positive semidefinite (PSD) matrices

• •Fact: $M$ is PSD iff $\mathbf{x}^\top M\mathbf{x} \ge 0$ for all x.
• •Where used: $L$ and $\mathcal{L}$ are PSD; this underpins why eigenvalues are nonnegative and why minimization problems make sense.

3) Rayleigh quotient and the min–max principle

• •Rayleigh quotient: $R_M(\mathbf{x}) = \frac{\mathbf{x}^\top M\mathbf{x}}{\mathbf{x}^\top \mathbf{x}}$.
• •Min–max (informal): eigenvalues can be characterized as constrained minima/maxima of Rayleigh quotients.
• •Where used: We interpret eigenvalues as “best possible” values of energy objectives, and connect $\lambda₂$ to cuts/partitions.

Graph theory prerequisites

1) Undirected vs directed, unweighted vs weighted graphs

• •Many results here assume undirected graphs. Weighted edges are allowed but must be symmetric: $w_{ij}=w_{ji}$.
• •Where used: Definitions of $A$, $D$, $L$, and properties like symmetry/PSD depend on undirectedness.

2) Connected components

• •You should know what it means for a graph to have $k$ connected components.
• •Where used: Multiplicity of the eigenvalue 0 of the Laplacian equals the number of components.

3) Cuts and volumes

• •Cut: edges crossing between $S$ and $\bar S$.
• •Volume: $\mathrm{vol}(S)=\sum_{i\in S} d_i$.
• •Where used: Conductance/expansion, Cheeger inequalities, and spectral partitioning.

Probability / Markov chain prerequisites (for the random-walk parts)

1) Markov chains on graphs: transition matrix $P$

• •Standard random walk: from node $i$, move to neighbor $j$ with probability $w_{ij}/d_i$.
• •Where used: The random-walk Laplacian and mixing relate to eigenvalues.

2) Stationary distribution

• •For an undirected connected graph, stationary distribution is $\pi_i = d_i/\mathrm{vol}(V)$.
• •Where used: Normalization choices and conductance definitions rely on this measure.

If any of these are shaky, it’s worth a quick review before continuing—spectral graph theory is powerful, but it’s also picky about definitions (especially which Laplacian and which conductance).

Spectral graph theory studies graphs through the eigenvalues and eigenvectors (the spectrum) of matrices that encode graph structure.

At a high level, the workflow is:

1) Start with a graph $G=(V,E)$ (possibly weighted).

2) Build a matrix representation like the adjacency matrix $A$ or a Laplacian.

3) Analyze eigenvalues/eigenvectors of that matrix.

4) Translate spectral facts back into graph properties: connectivity, clustering, expansion, random-walk behavior, and more.

Why this is even plausible: eigenvectors provide “global coordinates” on the vertices. If a graph has two clusters with sparse connections between them, there tends to exist a vector x that is roughly constant on each cluster but differs between clusters. When you apply a graph matrix to x, the result changes little if edges mostly connect equal values. This idea becomes a quadratic form: edges penalize differences.

The main matrices

Adjacency matrix $A$

For a graph with $n$ vertices (labeled 1…n),

• •Unweighted: $A_{ij}=1$ if $(i,j)\in E$, else 0.
• •Weighted: $A_{ij}=w_{ij}$.

For undirected graphs, $A$ is symmetric.

Adjacency spectra are great for: regular graphs, counting walks, and global “density/structure” signals. But for cuts, flows, and random walks, Laplacians are often more natural.

Degree matrix $D$

$D$ is diagonal with $D_{ii}=d_i=\sum_j A_{ij}$ (weighted degree if weighted).

Combinatorial Laplacian $L$

This is the central object for many connectivity and cut problems.

Normalized Laplacian $\mathcal{L}$ (important!)

There are two common Laplacians beyond $L$:

1) Symmetric normalized Laplacian

This is symmetric (for undirected graphs with positive degrees).

2) Random-walk Laplacian

where $P=D^{-1}A$ is the random-walk transition matrix. $L_{\text{rw}}$ is generally not symmetric, but it is similar to $\mathcal{L}$ and thus shares eigenvalues.

What “spectrum” means

The spectrum of a matrix is the multiset of its eigenvalues:

• •For $L$, we typically order them: $0=\lambda_1 \le \lambda_2 \le \cdots \le \lambda_n$.
• •For $\mathcal{L}$: $0=\nu_1 \le \nu_2 \le \cdots \le \nu_n \le 2$.

Eigenvectors matter too, especially for algorithms: the eigenvector associated with $\lambda_2$ (or $\nu_2$) often reveals a good partition.

A key mindset shift: spectral information is not just a “summary.” Many graph optimization problems (like finding a minimum cut under balance constraints) are hard combinatorial problems. Spectral methods relax them into continuous problems solvable by eigenvectors.

The combinatorial Laplacian $L=D-A$ is more than a definition—it encodes a geometry on the graph.

Laplacian as an “edge difference” operator

Take any vector x ∈ ℝⁿ assigning a scalar $x_i$ to each vertex $i$. Consider the quadratic form:

Expand it step by step (undirected, weighted case; assume $A_{ij}=w_{ij}=w_{ji}$):

\begin{align*}

\mathbf{x}^\top L\mathbf{x}

&= \mathbf{x}^\top (D-A)\mathbf{x}\\

&= \mathbf{x}^\top D\mathbf{x} - \mathbf{x}^\top A\mathbf{x}\\

&= \sum_i d_i x_i^2 - \sum_{i,j} w_{ij} x_i x_j.

\end{align*}

Now rewrite the second term using symmetry:

\begin{align*}

\sum_{i,j} w_{ij} x_i x_j

&= \sum_{i<j} w_{ij}(x_i x_j + x_j x_i) + \sum_i w_{ii}x_i^2\\

&= 2\sum_{i<j} w_{ij}x_i x_j \quad (\text{usually } w_{ii}=0).

\end{align*}

Also note:

So

\begin{align*}

\mathbf{x}^\top L\mathbf{x}

&= \sum_{i,j} w_{ij} x_i^2 - \sum_{i,j} w_{ij} x_i x_j\\

&= \frac{1}{2}\sum_{i,j} w_{ij}(x_i^2 - 2x_i x_j + x_j^2)\\

&= \frac{1}{2}\sum_{i,j} w_{ij}(x_i - x_j)^2.

\end{align*}

Interpretation: $\mathbf{x}^\top L\mathbf{x}$ is the total “edge disagreement energy.” It’s small when neighboring vertices have similar values.

PSD and nonnegative eigenvalues

From

we immediately get: $L$ is PSD, hence all eigenvalues satisfy $\lambda_i\ge 0$.

Why the smallest eigenvalue is 0

If x is constant, say $x_i=c$ for all $i$, then every difference $x_i-x_j=0$, so

Thus 0 is always an eigenvalue with eigenvector 1.

Connected components and multiplicity of 0

If the graph has $k$ connected components, you can build $k$ linearly independent vectors that are constant on one component and 0 elsewhere. Each has zero energy, so each lies in the nullspace of $L$.

Theorem: The multiplicity of eigenvalue 0 of $L$ equals the number of connected components.

This is one of the cleanest examples of “graph property ↔ eigenvalues.”

Algebraic connectivity and the Fiedler value

The second-smallest eigenvalue $\lambda_2$ (for a connected graph) is called the algebraic connectivity.

• •If $\lambda_2$ is tiny, the graph is “almost disconnected”: there exists a vector x orthogonal to 1 that changes little across edges, suggesting a sparse cut.
• •If $\lambda_2$ is large, every non-constant assignment must pay energy across many edges, suggesting strong connectivity.

Variationally,

This is where Rayleigh quotient/min–max enters: $\lambda_2$ is the best (smallest) achievable energy among vectors orthogonal to constants.

Normalized Laplacian energy (why normalization matters)

Combinatorial $L$ treats every vertex value equally in the denominator $\mathbf{x}^\top \mathbf{x}$. But for irregular graphs, high-degree vertices can dominate behavior.

The symmetric normalized Laplacian $\mathcal{L}=D^{-1/2}LD^{-1/2}$ has quadratic form

This makes “differences” comparable relative to degrees. Many expansion and random-walk results (including Cheeger-type inequalities) are stated for $\mathcal{L}$.

A practical rule:

• •Use $L$ for physics-style diffusion on uniformly weighted nodes, some cut relaxations, and when degrees are comparable.
• •Use $\mathcal{L}$ (or $L_{\text{rw}}$) when degrees vary a lot, or when your objective is tied to random walks / conductance.

A central algorithmic use of spectral graph theory is to find a “good” partition of the vertices: two groups with few edges between them but each group not too small.

From cuts to an optimization problem

For a subset $S \subset V$ (nonempty, not all vertices), define:

• •Cut weight:

• •Volume:

A widely used balanced-separation score is conductance:

And the graph conductance is

This definition is the one that matches the standard Cheeger inequality for the normalized Laplacian.

Why normalization appears

If you use a raw cut size $\mathrm{cut}(S,\bar S)$ alone, you can get trivial answers: isolate a single low-degree vertex. Conductance normalizes by volume, which corresponds to probability mass under the random-walk stationary distribution $\pi_i=d_i/\mathrm{vol}(V)$.

Indicator vectors and the relaxation idea

Suppose you want a cut. A discrete way is an indicator vector f where

• •$f_i = 1$ if $i\in S$
• •$f_i = 0$ if $i\notin S$.

But optimizing over such discrete vectors is hard. Spectral methods relax the problem: allow f to be real-valued, solve a continuous minimization, then “round” back to a set by thresholding.

This is where eigenvectors enter: the minimizing relaxed vector is an eigenvector.

The normalized Laplacian and the second eigenvalue

Let $0=\nu_1\le \nu_2\le\cdots\le\nu_n$ be eigenvalues of $\mathcal{L}$.

• •$\nu_2$ is small when there exists a set with small conductance.
• •$\nu_2$ is large when every set has large conductance (graph is an expander-like object).

Cheeger inequality (normalized Laplacian version)

For the conductance definition above and $\mathcal{L}$:

Important clarifications:

• •This statement is for the normalized Laplacian $\mathcal{L}$ (equivalently the random-walk matrix $P$).
• •There are variants with slightly different constants depending on conventions.
• •The left inequality says: if $\nu_2$ is small, the graph must have a sparse cut.
• •The right inequality says: from the eigenvector of $\nu_2$, you can find a cut with conductance at most about $\sqrt{\nu_2}$ (via a sweep/thresholding procedure).

The Fiedler vector and sweep cuts

Let u₂ be an eigenvector for $\nu_2$ of $\mathcal{L}$ (or equivalently for the second-largest eigenvalue of $P$). The spectral partitioning recipe:

1) Compute u₂.

2) Sort vertices by their coordinate in u₂ (or by $u_{2,i}/\sqrt{d_i}$ depending on implementation).

3) Consider prefix sets $S_k$ consisting of the first $k$ vertices in that order.

4) Compute conductance $\phi(S_k)$ for each; choose the best.

This “sweep” is the rounding step that turns a continuous eigenvector into a discrete cut.

Intuition: why the second eigenvector separates clusters

If the graph has two clusters weakly connected:

• •Values of u₂ tend to be nearly constant inside each cluster (low internal disagreement).
• •Values differ between clusters (to satisfy orthogonality constraints).

Thresholding separates the two sign/level regions.

Adjacency spectrum vs Laplacian spectrum for clustering

Adjacency eigenvectors can also show community structure, especially in stochastic block models. But Laplacians are generally more robust for irregular degrees because they directly encode “difference across edges” and integrate naturally with random-walk normalization.

A useful comparison:

Takeaway: when you see conductance/Markov chains, think normalized objects.

Spectral graph theory isn’t just about partitions. The same matrices govern diffusion, random walks, and learning algorithms.

Random walks and the transition matrix

For an undirected weighted graph, define

Then $P_{ij}=w_{ij}/d_i$ is the probability of moving from $i$ to $j$ in one step.

• •$P$ is row-stochastic (rows sum to 1).
• •If the graph is connected and non-bipartite (aperiodic), powers $P^t$ converge to a rank-1 stationary behavior.

The stationary distribution is

This is why volumes (sums of degrees) appear in conductance: they’re the natural “mass” under the walk.

Spectral connection: $P$ and $\mathcal{L}$ share eigenvalues

Even though $P$ is not symmetric, it is similar to a symmetric matrix:

So $P$ has real eigenvalues (for undirected graphs) and they match those of $D^{-1/2}AD^{-1/2}$.

Also,

So if $\mu_i$ are eigenvalues of $D^{-1/2}AD^{-1/2}$, then eigenvalues of $\mathcal{L}$ are $\nu_i = 1 - \mu_i$.

Mixing time and spectral gap (high-level)

Let $1=\mu_1 \ge \mu_2 \ge \cdots \ge \mu_n \ge -1$ be eigenvalues of $P$ (for connected graphs, $\mu_1=1$).

The spectral gap is often $1-\mu_2$ (for lazy walks you avoid negative eigenvalues issues). Since $\nu_2 = 1-\mu_2$, the second normalized Laplacian eigenvalue is exactly that gap.

Intuition:

• •If $\mu_2$ is close to 1 (small gap), the walk mixes slowly—there’s a bottleneck set with low conductance.
• •If $\mu_2$ is much smaller than 1 (large gap), mixing is fast—no severe bottlenecks.

This is the random-walk mirror of Cheeger: bottlenecks ↔ small $\nu_2$ ↔ slow mixing.

Diffusion and Laplacian dynamics

In continuous-time diffusion on graphs, a common model is

Solution uses the matrix exponential:

Eigenvectors of $L$ are the diffusion “modes”:

• •Small eigenvalues correspond to slow-decaying modes (large-scale structure).
• •Large eigenvalues decay quickly (fine-scale oscillations).

This perspective explains why low-frequency eigenvectors are used for embedding and clustering: they capture coarse geometry.

A small “map” of related spectral objects

You’ll see several related matrices in practice:

Where this shows up in ML and systems

• •Spectral clustering: compute a few eigenvectors of $\mathcal{L}$, embed nodes, run k-means.
• •Graph embeddings: Laplacian eigenmaps (manifold learning viewpoint).
• •Network science: expansion, robustness, community structure.
• •Numerical methods: solving linear systems in $L$ (graph-based preconditioners), effective resistance.

Spectral graph theory is a hub: once you can move between graphs ↔ matrices ↔ eigen-objects, many results become variations on the same theme—energy minimization under constraints.