Chapter 136. Spectral Graph Theory

136.1 Introduction

Spectral graph theory studies graphs using matrices and their eigenvalues.

A graph is a combinatorial object made of vertices and edges. Linear algebra enters through matrices associated with the graph, such as adjacency matrices and Laplacian matrices. The eigenvalues and eigenvectors of these matrices encode structural information about connectivity, expansion, clustering, random walks, and dynamics on the graph.

The subject lies at the intersection of:

Area	Connection
Linear algebra	Eigenvalues and eigenvectors
Graph theory	Combinatorial structure
Probability	Random walks and Markov chains
Computer science	Networks and algorithms
Geometry	Discrete analogues of manifolds
Physics	Diffusion and vibration
Data science	Spectral clustering

Spectral graph theory translates combinatorial problems into matrix problems.

136.2 Graphs

A graph $G$ consists of:

A set of vertices $V$ ,
A set of edges $E$ .

If the graph has $n$ vertices, one often labels them

1,2,\ldots,n.

An edge between vertices $i$ and $j$ is written

(i,j).

A graph is undirected if:

(i,j)\in E \quad\Longrightarrow\quad (j,i)\in E.

Otherwise it is directed.

Throughout most of spectral graph theory, graphs are undirected unless stated otherwise.

136.3 Adjacency Matrix

The adjacency matrix of a graph with $n$ vertices is the matrix

A=(a_{ij}),

where

a_{ij} = \begin{cases} 1, & \text{if } i \text{ and } j \text{ are adjacent},\\ 0, & \text{otherwise}. \end{cases}

For an undirected graph,

A=A^T.

Thus the adjacency matrix is symmetric, so its eigenvalues are real.

Example:

If the graph has edges

(1,2),\quad (2,3),

then

A = \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0 \end{bmatrix}.

The adjacency matrix converts graph structure into linear algebra.

136.4 Degree Matrix

The degree of a vertex is the number of edges incident to it.

If vertex $i$ has degree $d_i$ , then the degree matrix is

D = \operatorname{diag}(d_1,\ldots,d_n).

This is a diagonal matrix.

For the graph

1-2-3,

the degrees are:

Vertex	Degree
$1$	$1$
$2$	$2$
$3$	$1$

Thus

D = \begin{bmatrix} 1 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & 1 \end{bmatrix}.

The degree matrix records local connectivity information.

136.5 Graph Laplacian

The Laplacian matrix of a graph is

L=D-A.

Explicitly:

L_{ij} = \begin{cases} d_i, & i=j,\\ -1, & i\ne j \text{ and adjacent},\\ 0, & \text{otherwise}. \end{cases}

For the path graph

1-2-3,

the Laplacian is

L = \begin{bmatrix} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{bmatrix}.

The Laplacian is one of the central matrices of spectral graph theory.

It acts as a discrete analogue of the continuous Laplacian operator from differential equations.

136.6 Basic Properties of the Laplacian

The graph Laplacian has several important properties.

Symmetry

For undirected graphs:

L=L^T.

Therefore all eigenvalues are real.

Positive Semidefiniteness

For every vector $x\in\mathbb{R}^n$ ,

x^TLx = \sum_{(i,j)\in E}(x_i-x_j)^2.

x^TLx=\sum_{(i,j)\in E}(x_i-x_j)^2

Thus:

x^TLx\ge0.

So the Laplacian is positive semidefinite.

Zero Eigenvalue

The vector

\mathbf{1} = \begin{bmatrix} 1\\ 1\\ \vdots\\ 1 \end{bmatrix}

satisfies

L\mathbf{1}=0.

Thus $0$ is always an eigenvalue.

136.7 Connectivity and Eigenvalues

The Laplacian eigenvalues encode connectivity.

Order the eigenvalues as:

0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n.

The multiplicity of the eigenvalue $0$ equals the number of connected components of the graph.

Thus:

Multiplicity of $0$	Graph property
$1$	Connected
$k$	$k$ connected components

This result is fundamental because it translates connectivity into a linear-algebraic statement.

136.8 Algebraic Connectivity

The second-smallest Laplacian eigenvalue

\lambda_2

is called the algebraic connectivity or Fiedler value.

It measures how well connected the graph is.

Properties include:

Value of $\lambda_2$	Interpretation
$0$	Graph disconnected
Small positive	Weakly connected
Large	Strongly connected

The corresponding eigenvector is called the Fiedler vector.

It is important in graph partitioning and clustering.

136.9 Spectral Clustering

Spectral clustering uses eigenvectors of graph matrices to partition data.

The basic idea is:

Construct a similarity graph,
Form a Laplacian matrix,
Compute eigenvectors,
Embed the data into a low-dimensional spectral space,
Cluster in that space.

The Fiedler vector often separates the graph into two weakly connected regions.

Spectral clustering is widely used in:

Application	Use
Image segmentation	Pixel grouping
Social networks	Community detection
Machine learning	Unsupervised clustering
Data analysis	Dimensional reduction

Linear algebra provides the embedding coordinates.

136.10 Normalized Laplacian

The normalized Laplacian is:

\mathcal{L} = I-D^{-1/2}AD^{-1/2}.

It adjusts for varying vertex degrees.

Another form is the random-walk Laplacian:

L_{\mathrm{rw}} = I-D^{-1}A.

Normalized Laplacians are useful when degree variation is large.

Their eigenvalues lie in the interval

[0,2].

Normalized forms are common in probability and machine learning.

136.11 Random Walks on Graphs

A random walk moves from vertex to adjacent vertex randomly.

The transition matrix is

P=D^{-1}A.

The entry

P_{ij}

gives the probability of moving from vertex $i$ to vertex $j$ .

Properties of the random walk are closely related to spectral properties of $P$ and the Laplacian.

Examples include:

Spectral quantity	Probabilistic meaning
Largest eigenvalue	Stationary behavior
Spectral gap	Mixing speed
Eigenvectors	Long-term structure

Random walks connect graph theory with Markov chains.

136.12 Expansion

An expander graph is a sparse graph with strong connectivity properties.

Informally, every subset of vertices has many edges leaving it.

Expansion is related to the spectral gap:

\lambda_2.

Large spectral gap implies strong expansion.

Expanders are important in:

Area	Application
Computer science	Network design
Complexity theory	Derandomization
Coding theory	Error correction
Distributed systems	Communication efficiency

Spectral graph theory provides quantitative measures of expansion.

136.13 Cheeger’s Inequality

Cheeger’s inequality relates graph expansion to Laplacian eigenvalues.

The conductance of a graph measures how difficult it is to disconnect the graph.

Cheeger’s inequality states, roughly:

\lambda_2

controls conductance up to multiplicative constants.

Thus spectral information determines combinatorial bottlenecks.

This theorem is fundamental in spectral partitioning.

136.14 Eigenvectors and Geometry

Eigenvectors of graph matrices often reveal geometric structure.

For example:

Eigenvector	Interpretation
Constant eigenvector	Global uniform mode
Fiedler vector	Weakest separation direction
Higher eigenvectors	Finer structural modes

This resembles Fourier analysis.

Low-frequency eigenvectors vary slowly across edges.

High-frequency eigenvectors oscillate rapidly.

Thus graph eigenvectors act like discrete harmonic modes.

136.15 Discrete Laplacian and PDE Analogy

The graph Laplacian is analogous to the continuous Laplace operator

\Delta.

Continuous Laplacian:

\Delta f = \sum_i \frac{\partial^2 f}{\partial x_i^2}.

Discrete Laplacian:

(Lf)(i) = \sum_{j\sim i}(f(i)-f(j)).

Both measure local variation.

This analogy explains why spectral graph theory resembles harmonic analysis and differential geometry.

136.16 Heat Diffusion on Graphs

Heat flow on a graph satisfies the differential equation:

\frac{du}{dt} = -Lu.

The solution is:

u(t) = e^{-tL}u(0).

The matrix exponential

e^{-tL}

acts as a diffusion operator.

Eigenvalues determine diffusion rates:

Eigenvalue	Effect
Small	Slow decay
Large	Fast decay

Heat diffusion smooths functions on graphs.

136.17 Graph Fourier Transform

The eigenvectors of the Laplacian define a graph Fourier basis.

If:

L=U\Lambda U^T,

then the columns of $U$ are orthonormal eigenvectors.

For a graph signal $f$ , the graph Fourier transform is:

\widehat{f}=U^Tf.

Low-frequency components correspond to small eigenvalues.

Graph signal processing extends Fourier analysis to irregular discrete structures.

Applications include:

Application	Goal
Sensor networks	Signal smoothing
Recommendation systems	Graph filtering
Image processing	Structured denoising

136.18 Directed Graphs

Directed graphs lead to nonsymmetric matrices.

If:

A\ne A^T,

then eigenvalues may become complex.

Many properties of symmetric spectral theory fail or become more complicated.

Directed spectral theory often uses:

Matrix	Purpose
Transition matrix	Markov chains
Directed Laplacian	Flow analysis
PageRank matrix	Web ranking

Nonsymmetric spectral theory is generally harder than symmetric theory.

136.19 Random Graphs

Random graphs produce random matrices.

For example, in the Erdős-Rényi model:

G(n,p),

each edge appears independently with probability $p$ .

The adjacency matrix becomes a random symmetric matrix.

Spectral graph theory and random matrix theory interact strongly in this setting.

Important questions include:

Question	Meaning
Largest eigenvalue	Connectivity strength
Spectral distribution	Global randomness
Eigenvector localization	Structural concentration

Random graph spectra reveal hidden structure in networks.

136.20 Applications

Spectral graph theory has many applications.

Computer Science

Problem	Spectral tool
Graph partitioning	Fiedler vector
Web search	Eigenvector ranking
Recommendation systems	Spectral embeddings

Machine Learning

Task	Spectral method
Clustering	Laplacian eigenvectors
Manifold learning	Spectral embeddings
Semi-supervised learning	Graph diffusion

Physics

Phenomenon	Graph interpretation
Diffusion	Heat equation
Vibrations	Laplacian eigenmodes
Quantum transport	Spectral propagation

Network Science

Structure	Spectral indicator
Communities	Eigenvector structure
Robustness	Spectral gap
Synchronization	Laplacian eigenvalues

136.21 Summary

Spectral graph theory studies graphs using eigenvalues and eigenvectors of associated matrices.

The main ideas are:

Concept	Meaning
Adjacency matrix	Encodes edges
Degree matrix	Encodes vertex degrees
Laplacian	Discrete differential operator
Spectral gap	Connectivity strength
Fiedler vector	Graph partition direction
Random walk matrix	Probabilistic dynamics
Expansion	Sparse but highly connected structure
Graph Fourier basis	Laplacian eigenvectors
Heat diffusion	Dynamics generated by Laplacian
Spectral clustering	Eigenvector-based partitioning

Spectral graph theory converts combinatorial structure into linear algebra. Eigenvalues and eigenvectors reveal connectivity, geometry, diffusion, clustering, and randomness in discrete networks.