Spectral Clustering

Spectral Clustering

16 Oct 2025

Spectral Clustering is a graph-based clustering technique that uses the eigenvalues and eigenvectors of the graph Laplacian to find clusters.

1. Approaches to Find More Than Two Clusters

(A) Recursive Partitioning

• First split the data into 2 clusters.

• Then apply the same partitioning recursively on each cluster.

• Disadvantage:

  • Inefficient

  • Unstable

  • Errors propagate as recursion goes deeper

(B) Multiple Cluster Spectral Clustering (Standard Method)

This is the commonly used method.

2. Steps of Spectral Clustering (Multi-Cluster Method)

Step 1: Construct Matrices

Given a graph $G(V,E)$:

• Adjacency Matrix: $A$

• Degree Matrix: $D$

Both are $n\times n$, where $n$ = number of nodes.

Step 2: Compute the Graph Laplacian

$L=D-AL=D-A$

Step 3: Compute the Normalized Laplacian

$=D^{-1/2}\left(D-A\right)D^{-1/2}$$

Step 4: Compute Eigenvectors

Find the eigenvectors corresponding to the K smallest eigenvalues:

$X=(x_1,x_2,\cdot \cdot \cdot ,x_K)$

Step 5: Normalize the Rows

Form matrix $Y$ by normalizing each row of $X$.

Each row of $Y$ can be treated as a point in $K$-dimensional space.

Step 6: Apply K-Means

Cluster the nnn points (rows of $Y$) into $K$ clusters:

Step 7: Output the Clusters