Spectral Clustering

PUBLISHED: MAY 2, 2026•1 MIN READ

Spectral Clustering16 Oct 2025Spectral Clustering is a graph-based clustering technique that uses the eigenvalues and eigenvectors of the graph Laplacian to fin

Ashutosh KumarAuthor

gyarados

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 :

Adjacency Matrix:
Degree Matrix:

Both are , where = number of nodes.

Step 2: Compute the Graph Laplacian

Step 3: Compute the Normalized Laplacian

L_{N}=D^{-1/2}\,L\,D^{-1/2}

$

Step 4: Compute Eigenvectors

Find the eigenvectors corresponding to the K smallest eigenvalues:

Step 5: Normalize the Rows

Form matrix by normalizing each row of .

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

Step 6: Apply K-Means

Cluster the nnn points (rows of ) into clusters:

c=(c_1,c_2,\cdot\cdot\cdot,c_{K})

Step 7: Output the Clusters

A_{i}=\{\,j\mid j\in c_{i}\,\},\quad i=1,\cdot\cdot\cdot,K