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.

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

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

The degree matrix $$D$$ of a similarity graph is a diagonal matrix where its diagonal elements are $$d_{i,i} = \sum_j w_{i,j}$$ and its off-diagonal elements are $$d_{i,k} = 0$$ for $$k \neq i$$. Here, $$w_{i,j}$$ are the elements of the weighted adjacency matrix $$W$$, and $$d_{i,k}$$ are the elements of $$D$$.

Degree Matrix of a Similarity Graph

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

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

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

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