Only join nodes that are symmetrically in each other's k nearest neighbours.

Mutual K nearest neighbours graph

To resolve the asymmetry of the directed k nearest neighbours relation, we drop edge direction: nodes $$i$$ and $$j$$ are connected by an undirected edge whenever $$i$$ is among $$j$$'s k nearest neighbours OR $$j$$ is among $$i$$'s k nearest neighbours. This 'OR' rule is what is usually meant by the k nearest neighbours graph, and it is looser than the mutual k nearest neighbours graph, which requires the relation to hold in both directions.

Undirected K nearest neighbours graph

We connect each node to its k nearest neighbours based on the similarity measure. However, this relation is NOT always symmetric, i.e. A's kth nearest neighbour may be B, but A is B's (k+1)th nearest neighbour. This causes the graph to be directed, which is a problem. The child nodes describe two ways to deal with this: the undirected k nearest neighbours graph and the mutual k nearest neighbours graph.

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

Learn Before

Related

Learn After