Normalized and unnormalized spectral clustering involve a tradeoff between predictive performance and computational cost. The cited 2015 discussion by Sarkar and Bickel reports improved prediction accuracy from normalization in applications such as image segmentation and stochastic block models, while describing unnormalized spectral clustering as less computationally intensive. These reported advantages should be treated as application-dependent rather than universal.

University of Michigan - Ann Arbor

Google

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 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.

Unnormalized Spectral Clustering

This variant of spectral clustering (Shi and Malik, 2000) modifies the base algorithm by replacing the step that finds eigenvectors of the unnormalized Laplacian alone. Instead, it solves the generalized eigenproblem $$Lv = \lambda Dv$$, where $$L$$ is the unnormalized Laplacian and $$D$$ is the degree matrix. The resulting eigenvectors are then used for clustering in place of the unnormalized Laplacian's eigenvectors.

Learn Before

Related