Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs
Round-Trip KNN Clustering finds multiscale clusters on directed neighbour graphs without a preset count.
Round-Trip KNN Clustering (RTKNNC) finds clusters at multiple neighbourhood scales on directed k-nearest-neighbour graphs without a preset cluster count. Incoming neighbour selections act as weighted votes during a recursive forward-and-reverse traversal, and an optional label-free step splits a component into two or three Gaussian subpopulations only when the groups are large and consistent with the visible graph. Across eight synthetic datasets and K from 2 to 16, independent C and Python implementations produced identical partitions in all 120 reference runs. Refinement raised 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, remaining competitive with seven external methods.
- RTKNNC keeps directed KNN edges and treats incoming selections as weighted votes.
- Repeating for increasing K shows which groups persist or merge.
- Optional Gaussian refinement splits bridged or overlapping components only when consistent.
- C and Python implementations matched on all 120 reference runs.
- Refinement raised adjusted Rand index to 0.9627 and 0.9853 on two benchmarks.
From the original article
1 min read at arxiv.orgWe 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.
By Eraldo Pereira Marinho · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.