# Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs

arXiv: https://arxiv.org/abs/2610.06795 · HTML: https://mlsanity.com/paper/2610.06795/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 29 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Builds on (most cited first, 1 of 1)

- [Efficient Coreset Selection via K-Nearest Neighbor Graphs](https://mlsanity.com/paper/2608.16270/) (2026)

## Abstract (arXiv)

We introduce Round-Trip KNN Clustering (RTKNNC), a graph-based method for finding cluster structure at several neighbourhood scales without requiring the number of clusters in advance. Unlike approaches that first make a k-nearest-neighbour (KNN) graph undirected, RTKNNC keeps both directions of the neighbour relation: which points a given point selects and which points select it. Incoming selections are treated as weighted votes that help decide which local connections remain visible during a recursive forward-and-reverse traversal. Repeating the procedure for increasing K reveals how groups persist or merge as the neighbourhood scale grows; for the reference inverse-square model before structural refinement, clusters can merge but do not split. Because graph connectivity can occasionally join distinct groups through a sparse bridge or a small region of overlap, we add an optional label-free refinement. It first tests whether an already formed component is better described by two or three Gaussian subpopulations, and accepts a subdivision only when the proposed groups are large enough and consistent with the visible KNN graph. Across eight synthetic datasets and K=2,ldots,16, independent C and Python implementations produced identical partitions in all 120 reference runs. Refinement increased adjusted Rand index from 0.7817 to 0.9627 on a variable-density benchmark and from 0.8083 to 0.9853 on a sparse-bridge benchmark. Comparisons with seven external clustering methods show competitive performance while preserving a label-free cluster-construction process.