We connect nodes to their k nearest neighbours. However there are times when this relation is NOT symmetric i.e. A's kth nearest neighbour is B, but A is B's k+1th nearest neighbour. This causes the graph to be directed which is a problem. 
This can be dealt with in two ways described in the child nodes.

K nearest neighbours graph

We connect all nodes that have a non-zero similarity value ($$s_{i,j}$$) in the similarity matrix and weigh their edges by the value of $$s_{i,j}$$.

Fully Connected Similarity Graph

An $$\epsilon$$ neighbourhood graph is formed by connecting all nodes that are at most a distance of $$\epsilon$$ away from each other.

$$\epsilon$$ Neighbourhood Graph

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

University of Michigan - Ann Arbor

Google

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

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

The K Means Clustering run on the distinct $a_i$ data points, assigns them to different clusters. The question then arises, how does this allow us to assign cluster assigments to the original data points?

Well, matrix M has dimensionality n x k, i.e. it has n separate points that are classified by the K Means algorithm. Each of these n points is in a one-to-one correspondence with each of the n points in the original similarity matrix i.e. each node of the graph which directly encodes every data point. Thus the assignment of the ith row in M is the same as the cluster assignment of the ith data point.

Thus spectral clustering helps us be more *efficient* with assigning clusters to points of high dimensionality, by mapping them to a lower dimension and *then* running K means on them.

Interpreting output of Spectral Clustering Assignments

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

Each data point in the matrix denotes the similarity between two data points i.e. $w_{i,j}$ denotes the similarity between points $i$ and $j$ calculated by some specific function. Eg : Gaussian similarity function : 

$$w_{i,j} = exp(- \frac{||x_i - x_j||^2}{2\sigma^2})$$
Here $||$ denotes the L2 norm, and $\sigma$ is just a parameter.
W is symmetric and all $w_{i,j} >= 0$ 


Definition : Adjacency Matrix W

A degree matrix D is a diagonal matrix where

$$d_{i,i} = \Sigma_j w_{i,j}$$
$$d_{i,k} = 0$$
where k != i, $w_{i,j}$ are elements in W, $d_{i,k}$ are elements of D.

Definition : Degree Matrix

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.

Learn Before

Related

Learn After