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.

Normalized Spectral Clustering via Generalized Eigenproblem (Shi–Malik)

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.

Normalized vs Unnormalized Spectral Clustering

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

University of Michigan - Ann Arbor

Algorithm: Input: Similarity Matrix and number of clusters $$k$$. 1. Represent all data points as nodes in a graph. 2. Build the similarity graph given a similarity matrix. Calculate its weighted adjacency matrix $$W$$. Let it have dimensionality $$n 	imes n$$. 3. Build the unnormalized Laplacian $$L$$ ($$n 	imes n$$). 4. If we wish to cluster the data into $$k$$ clusters (user-defined), then we consider the first $$k$$ eigenvectors of the matrix $$L$$. 5. Build an $$n 	imes k$$ matrix with each of the first $$k$$ eigenvectors as its columns. Let us call this matrix $$M$$. 6. Interpret each ROW of the matrix $$M$$ as a separate data point $$a_i$$. 7. Run the k-means clustering algorithm to put these distinct $$a_i$$ data points into clusters.

Spectral Clustering Algorithm

Resources referred to : 
1. [towardsdatascience.com/spectral-clustering-82d3cff3d3b7](https://towardsdatascience.com/spectral-clustering-82d3cff3d3b7)
2. [en.wikipedia.org/wiki/Spectral_clustering](https://en.wikipedia.org/wiki/Spectral_clustering) 

Reference : spectral clustering

Papers and class slides referred to : 
1. [www.cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf](https://www.cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf)
2. [www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf](https://www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf)
3. [people.cs.pitt.edu/~milos/courses/cs3750-Fall2011/lectures/class17.pdf](https://people.cs.pitt.edu/~milos/courses/cs3750-Fall2011/lectures/class17.pdf)
4. [projecteuclid.org/download/pdfview_1/euclid.aos/1431695635](https://projecteuclid.org/download/pdfview_1/euclid.aos/1431695635) 

Paper References : spectral clustering

The Unnormalized Laplacian is constructed as : 
$$L = D - W$$
Where D is the degree matrix, W is the adjacency matrix, and L is the unnormalized laplacian.

Definition : Unnormalized Laplacian

In the spectral clustering algorithm, the first step is to build a similarity graph from the similarity matrix. There are three common types of similarity graphs that can be generated:
1. $$\epsilon$$-neighbourhood graph
2. k-nearest neighbours graph
3. Fully connected graph

Similarity Graphs in Spectral Clustering

In spectral clustering, the weighted adjacency matrix $$W$$ represents the similarity graph of the data points. Each entry $$w_{i,j}$$ denotes the non-negative similarity between points $$i$$ and $$j$$, calculated by a specific function. For example, using the Gaussian similarity function:

$$w_{i,j} = \exp(- \frac{||x_i - x_j||^2}{2\sigma^2})$$

Here, $$||\cdot||$$ denotes the L2 norm, and $$\sigma$$ is a scaling parameter. The matrix $$W$$ is symmetric, and all weights satisfy $$w_{i,j} \geq 0$$.

Weighted Adjacency Matrix in Spectral Clustering

In the spectral clustering algorithm, k-means clustering is applied to the distinct rows, denoted as $$a_i$$, of the $$n \times k$$ matrix $$M$$. Since matrix $$M$$ contains exactly $$n$$ rows, each row has a one-to-one correspondence with one of the $$n$$ original data points represented in the similarity graph. Consequently, the cluster assigned to the $$i$$-th row of $$M$$ is directly assigned to the $$i$$-th original data point. This process demonstrates how spectral clustering efficiently handles high-dimensional data by first mapping it to a lower-dimensional representation before performing k-means.

Learn Before

Related

Learn After

Learn After

Related