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

University of Michigan - Ann Arbor

Google

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

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

Learn Before

Related