Spectral Graph Theory

Eigenvalues, the Laplacian, and spectral clustering

Spectral Graph Theory

Spectral graph theory studies the relationship between graph structure and the eigenvalues of associated matrices. By encoding a graph as a matrix, we can use powerful tools from linear algebra to uncover hidden properties!

In this section, you'll explore the adjacency and Laplacian matrices, learn how eigenvalues reveal connectivity, and see how spectral methods enable graph clustering.

What You'll Learn

📊
Graph Matrices
Adjacency, degree, and Laplacian matrices
🔢
Eigenvalues
λ₂ and algebraic connectivity
🎯
Clustering
Partitioning via the Fiedler vector

Graph Matrices Explorer

Every graph has associated matrices that encode its structure. The Adjacency matrix A, Degree matrix D, and Laplacian L = D - A reveal deep properties of the graph.

Click a vertex to select, click two vertices to toggle edge

Adjacency Matrix A
1
2
3
4
1
0
1
0
0
2
1
0
1
0
3
0
1
0
1
4
0
0
1
0
4
Vertices (n)
3
Edges (m)
4×4
Matrix Size

About Graph Matrices

  • Adjacency (A): A[i,j] = 1 if vertices i,j are connected
  • Degree (D): Diagonal matrix with D[i,i] = degree of vertex i
  • Laplacian (L): L = D - A, encodes graph connectivity
  • All three matrices are symmetric for undirected graphs

Eigenvalue Properties

The eigenvalues of the Laplacian matrix reveal graph structure. The second-smallest eigenvalue λ₂ (algebraic connectivity) tells us if the graph is connected!

Laplacian Spectrum
0
1
2
3
4
5
Zero (λ = 0)
λ₂ (Fiedler)
Other
Eigenvalues of L:
λ1 = 0.000
λ2 = 0.586
λ3 = 2.000
λ4 = 3.414
λ₂ = 0.586
Algebraic Connectivity
Graph is CONNECTED
1
Zero Eigenvalues
= 1 Connected Component
✓ λ₂ > 0 confirms the graph is connected!
The larger λ₂ is, the more "well-connected" the graph. K₄ has λ₂ = 4!

Key Spectral Properties

  • λ₁ = 0 always (constant vector is an eigenvector)
  • λ₂ > 0 if and only if the graph is connected
  • Number of zero eigenvalues = number of connected components
  • λ₂ is called the Fiedler value or algebraic connectivity

Spectral Clustering

Spectral clustering uses the Fiedler vector (eigenvector of λ₂) to partition graphs. Vertices are assigned to clusters based on the sign of their Fiedler vector component!

Fiedler Vector (eigenvector of λ₂)
v1
-0.41
v2
-0.41
v3
-0.41
v4
+0.41
v5
+0.41
v6
+0.41
Cluster assignment: negative → Cluster A (blue), positive → Cluster B (red)
Cluster A (negative)
Cluster B (positive)
Unclustered

How Spectral Clustering Works

  1. Compute the Laplacian matrix L = D - A
  2. Find the eigenvector for λ₂ (the Fiedler vector)
  3. Partition vertices by the sign of their component
  4. This minimizes the ratio cut of the graph!

What We've Learned

1. Graph Matrices: Every graph has associated matrices — the adjacency matrix A, degree matrix D, and Laplacian L = D - A. These encode the graph structure in a form amenable to linear algebra.

2. Laplacian Eigenvalues: The eigenvalues of L reveal graph properties. The number of zero eigenvalues equals the number of connected components. The second-smallest eigenvalue λ₂ (algebraic connectivity) is positive iff the graph is connected.

3. Spectral Clustering: The eigenvector of λ₂ (Fiedler vector) provides a natural way to partition the graph. Vertices with the same sign in the Fiedler vector tend to form clusters, minimizing edges cut.

Next Up: In the next section, you'll explore random graphs and networks — Erdős-Rényi models, small-world phenomena, and scale-free networks!