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


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

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.

Unnormalized Spectral Clustering

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.

Learn Before

Related