Can round-trip KNN clustering find hierarchical clusters without a preset cluster count?

Directed KNN links become weighted votes

Most graph clustering pipelines make a k-nearest-neighbour (KNN) graph undirected before clustering. RTKNNC keeps both directions of the neighbour relation: which points a given point selects, and which points select it. The paper treats incoming selections as weighted votes that help decide which local connections stay visible during a recursive forward-and-reverse traversal.

That traversal is the core mechanism. Starting from a seed, the method follows visible links forward to selected neighbours and backward to points that selected the current point, repeating until no further points can be added. The paper calls this a round trip and the final set a saturated round-trip closure. Clusters therefore come from local graph connectivity rather than a prescribed geometric shape, and the number of clusters is never supplied to the algorithm.

Neighbourhood size K replaces a preset cluster count

K sets the propagation scale. Small values describe very local structure and may fragment the graph; larger values let information spread over broader neighbourhoods. Running the method independently for increasing K produces a sequence of cluster layers, so persistent groups and mergers become directly visible.

In this paper, hierarchical means this organisation across neighbourhood scales, not a conventional linkage-based agglomerative procedure. On the variable-density blobs dataset, the unpruned reference inverse-square model drops from 595 microclusters at K=2 to 277 at K=3, 99 at K=4, 18 at K=5, 6 at K=6, 5 at K=7, and 4 at K=8, where the partition then stays unchanged through K=16. All N=2000 points are represented exactly once and the unclustered count is zero, so these layers are proper partitions.

Unrefined layers merge but do not split

For the reference inverse-square voting rule, before the optional structural refinement is applied, the paper proves a merge-only property for successive proper partitions: as K increases, a cluster may persist or merge with another one, but it does not split. Figure 2 illustrates this on the variable-density blobs over K=5,6,7,8, where every cluster at one scale is wholly contained in a unique cluster at the next scale, so the transition forest contains preservation and merger events but no split.

This property belongs to the unrefined reference model, not to every vote kernel or to the refined output. It is also a statement about layer structure, not about correctness: the merge-only forest describes how clusters correspond across scales, which is a different diagnostic from whether a single reported layer is a proper partition.

Stable cluster counts do not guarantee correct classes

The variable-density blobs make the distinction concrete. At K=7 the cluster count already equals the five reference classes, but the adjusted Rand index (ARI) is only 0.7805. At the tested-range saturation beginning at K=8, four components remain and ARI is 0.7817. The equality between the reported count and the reference count, and the stable plateau, both fail to indicate recovery of the latent classes.

ARI and NMI compare each partition with the known reference labels and are invariant under permutation of cluster identifiers. The paper uses them only for evaluation; the label column is never included among the clustering features. This is why the authors describe the stable four-component plateau as a stable merger that needs a separate correction rather than as a solution.

Label-free refinement splits supported components only

Connectivity-based clustering can join distinct groups through a sparse bridge or a small region of overlap. RTKNNC adds an optional refinement applied only after a connected component has already formed. It tests whether that 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.

The paper is explicit that this stage does not replace the round-trip method with a Gaussian-mixture clustering algorithm. The mixture model is used locally as a test of internal structure, with a minimum BIC gain of 10, size checks, graph-coherence checks, and a four-component veto. Refinement is disabled throughout the 840-run kernel comparison, so the ablation isolates vote allocation from structural pruning.

Refinement raises ARI on the two hard benchmarks

On the variable-density benchmark, refinement increased ARI from 0.7817 to 0.9627 and changed the reported count from four to five clusters. On the sparse-bridge benchmark, ARI rose from 0.8083 to 0.9853, reaching three clusters at K=6 and 0.9865 at K=10. On three already correct preservation controls, the refinement accepted no split and ARI remained 1.

The gains are specific to the two connectivity failures the refinement targets. The variable-density case is a stable merger of four components; the bridge case is a sparse chain joining dense cores. The preservation controls show the acceptance rules do not force subdivisions where the component is already correct.

Two implementations agree across 120 reference runs

Across eight synthetic datasets and K=2 through 16, independent C and Python implementations produced identical partitions in all 120 reference runs, up to permutation of cluster identifiers and including the unclustered masks. Six additional C-Python comparisons covered the three weighted kernels on the variable-density blobs at K=8 and the bridge at K=6.

The independent-run convention matters for this agreement. Each reported scale is run with K0=K, so the graph, radius, popularity, and visibility all refer to the same stated neighbourhood scale; a run with K0 below Kmax could otherwise leave a construction-time radius tied to Kmax at smaller intermediate layers.

Vote kernels matter less than visible connectivity

The 840-run kernel sweep compared uniform, inverse-distance, inverse-square, and sigmoid allocation under the same per-source vote budget. Vote allocation often changed visibility and sometimes the induced partition. On the two difficult reference scales, inverse-distance, inverse-square, and sigmoid voting all preserved the corrected cluster counts with essentially identical scores, and their six unpruned native partitions passed pointwise C-Python agreement.

For the variable-density blobs, the three kernels produced pointwise-identical final partitions even though their native mean visible-neighbour counts differ and the audit finds hundreds of kernel-dependent directed edges. For the bridge, stability is only approximate: inverse-distance voting changes four assignments relative to the pointwise-identical inverse-square and sigmoid results, a distinction hidden by three-decimal ARI and NMI.

A label-selected best-of-grid comparison covered 10,344 external fits and 90 RTKNNC fits across seven external methods. RTKNNC with structural refinement enabled matched ARI 1 on four benchmark datasets, obtained ARI 0.9627 on the variable-density dataset versus 0.9639 for a full-covariance GMM, and attained the highest sparse-bridge ARI, 0.9865 versus 0.9831 for the GMM. Because reference labels select the best candidate within each grid, the paper does not propose ARI as an unsupervised deployment rule.

Where the label-free claim holds and stops

The label-free claim is strongest for cluster construction: the number of clusters is never supplied, and refinement accepts subdivisions only after size and graph-coherence checks. The merge-only property, by contrast, is proved for the unrefined reference inverse-square model whenever layers are proper partitions, not for every kernel or for the refined output.

The evidence base is eight synthetic datasets with K=2 through 16, and the external comparison uses the six datasets with nontrivial discrete references. The uniform cloud has no nontrivial reference partition, and the Swiss-roll labels are an artificial discretisation of a continuous manifold, so its external scores are interpreted descriptively. The paper lists repeated stochastic realisations, higher-dimensional data, alternative covariance models, label-free scale selection, and additional graph-based baselines as future work.

The practical priority follows from the two hard cases rather than from the stable plateaus. A reader evaluating RTKNNC should look first at whether a component is a stable merger or a sparse-bridge join, because those are the conditions where the optional refinement changes ARI from 0.7817 to 0.9627 and from 0.8083 to 0.9853, while a matching cluster count or an unchanged partition across K does not by itself indicate that the latent classes were recovered.

Sources used in this answer