Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs
Abstract
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,…,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.
Related
- Parametrized Power-Iteration Clustering for Directed Graphs
- Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs
- Hierarchical clustering of X-Ray Fluorescence images using a dissimilarity based on the likelihood ratio statistic
- Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
- Spectral properties of the resistance Laplacian with applications to data clustering and anomaly detection
BibTeX
@misc{marinho2026roundtrip,
title = {{Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs}},
author = {Eraldo Pereira Marinho and Caetano Mazzoni Ranieri and Fabricio Aparecido Breve},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06795},
eprint = {2610.06795},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06795},
}
RIS
TY - UNPB
TI - Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs
AU - Eraldo Pereira Marinho
AU - Caetano Mazzoni Ranieri
AU - Fabricio Aparecido Breve
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06795
UR - https://arxiv.org/abs/2610.06795
AB - 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,…,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.
ER -