Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
Round-Trip KNN Clustering (RTKNNC) is a novel graph-based method that detects multiscale hierarchical cluster structure in directed nearest-neighbour graphs by leveraging both outgoing and incoming neighbour relations. By treating incoming selections as weighted votes during a recursive traversal and repeating for increasing neighbourhood scales ($K$), RTKNNC reveals how clusters merge but not split, offering a robust approach to cluster discovery without pre-specifying the number of clusters. An optional label-free refinement step further enhances cluster purity by subdividing components based on Gaussian subpopulations, significantly improving performance on challenging benchmarks.
Discover hierarchical cluster structure across multiple scales in directed graphs without knowing the number of clusters beforehand, even across sparse bridges.
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.