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

University of Michigan - Ann Arbor

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.

K nearest neighbours graph

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.

Learn Before

Related