Normalized spectral clustering is more accurate for prediction in applications like image segmentation, stochastic blockmodels etc. (Role of Normalization in Spectral Clustering for Stochastic Blockmodels, Sarkar, Bickel [2015]). Unnormalized spectral clustering however is less computationally intensive.

University of Michigan - Ann Arbor

1. Normalized Spectral Clustering 1 by Shi and Malik [2000]
2. Normalized Spectral Clustering 2 by Ng, Jordan, Weiss [2002]
3. Unnormalized Spectral Clustering

Variations of Spectral Clustering Algorithm

We insert a mini step between steps 3 and 4 of the algorithm so that instead of calculating the eigenvectors of the unnormalized Laplacian, we calculate the eigenvectors of the generalized eigenproblem
$$Lv = \lambda Dv$$


Normalized Spectral Clustering 1

We calculate the eigenvectors of the matrix generated by :
$$D^\frac{-1}{2} L D^\frac{-1}{2} = I - D^\frac{-1}{2} W D^\frac{-1}{2}$$
Where W is the adjacency matrix (weighted), D is the degree matrix and L is the unnormalized Laplacian.

Normalized Spectral Clustering 2

We just follow the same algorithm and find the eigenvectors of the unnormalized Laplacian.

Learn Before

Related