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

Eraldo Pereira Marinho; Caetano Mazzoni Ranieri; Fabricio Aparecido Breve

cs.LGOct 5, 2026

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

Authors: Eraldo Pereira Marinho, Caetano Mazzoni Ranieri, Fabricio Aparecido Breve

Organizations: Department of Statistics, Applied Mathematics and Computing, S˜ao Paulo State University (UNESP), Institute of Geosciences and Exact Sciences, Av. 24-A, 1515, Rio Claro, S˜ao Paulo, Brazil.

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,\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.

Figures & tables

Figure 1: Example of a directed KNN graph with $K=2$ , used to illustrate the proposed mechanism. Arrows represent directed nearest-neighbour choices. The graph encodes neighbourhood connectivity, but its abstract layout does not reproduce the spatial morphology of the original point distribution. Metric distances are stored as edge attributes and are not represented by the drawn edge lengths. The same graph supports reverse-neighbour retrieval and visibility-filtered round-trip expansion.

$K$	clusters	ARI	NMI
2	595	0.0116	0.3991
3	277	0.0403	0.4491
4	99	0.2809	0.5716
5	18	0.6661	0.8017
6	6	0.7774	0.8941
7	5	0.7805	0.8981

Table 1: Unpruned inverse-square regression results for the variable-density blobs dataset. Each

K

was run independently with

K_{0}=K

Figure 2: Multiscale evolution of the unpruned reference inverse-square model on the variable-density blobs. Every layer is generated independently with

K_{0}=K

. (a) The cluster count decreases from 595 microclusters at

K=2

to four components at

K=8

and is plotted on a logarithmic scale; the dashed line is the reference count

C^{*}=5

, used only for evaluation. (b) ARI and NMI against the withheld reference labels. The shaded interval marks the exactly unchanged partition from

K=8

through the largest tested value,

K=16

. (c) The merge-only transition forest over

K=5,6,7,8

. Node and ribbon thicknesses encode point population and overlap count

W_{ab}^{(K,K^{\prime})}

, respectively. Colours identify the four lineages ending at

K=8

and do not encode reference labels. The equality

m_{7}=C^{*}

without high ARI and the stable

m_{K}=4

plateau demonstrate that cluster-count or partition stability alone does not guarantee recovery of latent classes.

Figure 3: Number of clusters as a function of

K

for every primary dataset in the controlled, unpruned four-kernel benchmark. Each point is obtained from an independent execution with

K_{0}=K

, and the ordinate is logarithmic. Lines are evaluated at the integer

K

values; markers have small horizontal offsets only to expose coincident counts from different kernels. Dashed lines show the reference count

C^{*}

for evaluation only. The Swiss-roll reference comprises artificial bands, and the uniform cloud has no reference partition. Matching

C^{*}

is therefore neither an execution-time selection rule nor evidence of pointwise partition correctness.

Figure 4: Reference labels and the four predicted partitions for the two-moons dataset at the common representative scale

K=10

: budget-matched uniform

h(u)=1

, inverse-distance

h(u)=1/u

, reference inverse-square

h(u)=1/u^{2}

, and local sigmoid

S_{\alpha}(u)

with

\alpha=8

. Every source casts the common budget in Eq. ( 20 ); the panels differ only in its allocation among outgoing neighbours. Every vote model recovers the two non-convex components exactly (ARI

{}={}

NMI

{}={}

1). Cluster colours are local to each panel and do not encode a cross-panel label correspondence.

bridge fraction	$h(u)=1$	$h(u)=1/u$	$h(u)=1/u^{2}$	$S_{\alpha}(u)$
0.00	$>16$	$>16$	$>16$	$>16$
0.10	5	5	6	5
0.25	6	6	6	6
0.50	6	6	6	6
0.75	7	7	7	7
1.00	7	7	7	7

Table 2: First

K

producing a merger of the two dense bridge cores for each of the four vote kernels. A value

>16

means that no merger occurred in the tested range.

Figure 5: Native structural pruning of the complete sparse bridge at

K=6

under the three weighted allocation shapes. The panels show budget-matched

h(u)=1/u

, reference

h(u)=1/u^{2}

, and budget-matched local sigmoid

S_{\alpha}(u)

with

\alpha=8

, respectively. Every model produces three clusters. Inverse-square and sigmoid allocation coincide pointwise (ARI

0.98535

, NMI

0.96212

), while inverse-distance differs from them at four points after label alignment (ARI

0.98532

, NMI

0.96244

). The accepted subdivisions have 6, 10, and 11 crossing visible connections, and their annotated native unpruned visible-edge counts are 6940, 6928, and 6972, respectively. The distinct unpruned visible graphs yield identical final partitions under inverse-square and sigmoid allocation. Reference labels are used only for external evaluation and colour alignment.

dataset	$K$	$C^{*}$	$C_{0}$	ARI 0	$C_{p}$	ARI p	$\|E^{\mathrm{cut}}\|$
Variable-density blobs	8	5	4	0.7817	5	0.9627	12
Sparse bridge	6	3	2	0.8083	3	0.9853	10
Sparse bridge	10	3	1	0.0000	3	0.9865	32
Circles	7	2	2	1.0000	2	1.0000	0
Two moons	10	2	2	1.0000	2	1.0000	0
Anisotropic blobs	8	3	3	1.0000	3	1.0000	0

Table 3: Native inverse-square results before and after structural pruning.

C^{*}

is the number of reference classes,

C_{0}

and

C_{p}

are the unpruned and pruned cluster counts, and

|E^{\mathrm{cut}}|

is the number of crossing visible connections in the accepted subdivision (zero when no split is accepted). Labels are used only for the reported ARI and

C^{*}

Figure 6: Native structural pruning of the variable-density blobs at

K=8

under the three weighted allocation shapes. The three panels show, from left to right, budget-matched

h(u)=1/u

, reference

h(u)=1/u^{2}

, and budget-matched local sigmoid

S_{\alpha}(u)

with

\alpha=8

. All produce the same pointwise five-cluster partition (ARI

0.96265

, NMI

0.96141

) after structural refinement; each accepted subdivision has 12 crossing visible connections. The panel annotations expose the distinct native unpruned graphs:

|E^{\mathrm{vis}}|=9402

, 9365, and 9470 directed edges, respectively. Reference labels are omitted from the mosaic and are used only for colour alignment and external scores; each unpruned C partition was first verified pointwise against its Python kernel definition.

Method	Anisotropic	Equal-density blobs	Variable-density blobs	Sparse bridge	Circles	Two moons
$C^{*}$	3	4	5	3	2	2
RTKNNC	1.0000/1.0000	1.0000/1.0000	0.9627/0.9614	0.9865/0.9632	1.0000/1.0000	1.0000/1.0000
Agglom. †	1.0000/1.0000	1.0000/1.0000	0.9306/0.9444	0.9153/0.8580	1.0000/1.0000	1.0000/1.0000
K-means †	1.0000/1.0000	1.0000/1.0000	0.9189/0.9338	0.9342/0.8780	-0.0004/0.0001	0.4800/0.3815
GMM †	1.0000/1.0000	1.0000/1.0000	0.9639/0.9636	0.9831/0.9552	-0.0004/0.0001	0.5096/0.4080
DBSCAN	1.0000/1.0000	1.0000/1.0000	0.7916/0.8044	0.8140/0.7422	1.0000/1.0000	1.0000/1.0000

Table 4: Best label-selected grid result for RTKNNC with structural refinement enabled and external clustering methods. Each cell reports ARI/NMI; bold denotes the highest ARI in the column, including ties. Methods marked

\dagger

receive the reference cluster count

C^{*}

; the others do not. Reference labels are used only for scoring and best-of-grid selection, never as clustering features.

Explore similar work

Selective Hypergraph Refinement for Frozen Graph Clustering
Sep 3, 2026Zimo SiClustering Graph Clustering
Department of Mathematics, Faculty of Science, University of Macau · Macao SAR, China
AdaGraph: A Graph-Native Clustering Algorithm That Overcomes the Curse of Dimensionality and Enables Scientific Discovery
May 5, 2026Ahmed ElmahdiClustering Graph Clustering
Independent Researcher
G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation
Sep 21, 2026Keith Miller, Tristan CrawfordGraph Neural Networks Unsupervised Clustering

Sep 3, 2026, cs.LGJ/K move · Enter open · S save

Selective Hypergraph Refinement for Frozen Graph Clustering

Zimo Si

Department of Mathematics, Faculty of Science, University of Macau · Macao SAR, China

Clustering Graph Clustering

Open paper AskPDF arXiv

Existing graph-clustering methods typically improve clustering performance by optimizing model parameters and node representations. Effective means of further improving the clustering results of an already trained and frozen model, however, remain limited. We study post-processing for frozen graph clustering. After checkpoint fixation, the procedure uses no labels and updates neither model parameters, node representations, nor the original graph structure. Instead, it exploits an attribute hypergraph to supplement higher-order relations that ordinary graphs cannot readily express, thereby refining existing cluster assignments. Because global hypergraph refinement can yield both performance gains and erroneous updates, we propose Selective Hypergraph Refinement (SHR). The method generates candidate residual directions from the hypergraph and evaluates their reliability using graph structure, node attributes, and matched-null evidence. It updates only nodes with sufficient support and otherwise retains their original assignments. Further analysis shows that whether a node changes cluster is jointly governed by its native assignment gap and the directional strength of the refinement. In a controlled common-suite evaluation, 13 of 15 backbone-dataset cells had a positive mean macro gain, one produced exact no-action, and one was negative. The cell-equal macro gain was 0.066 pp (95% bootstrap CI, [0.030, 0.107] pp), while only 0.209% of hard assignments changed on average. A broader 15-combination native-interface evaluation yielded a macro gain of 0.137 pp at a mean change ratio of 0.375%. These results indicate that frozen clustering outputs retain a limited but measurable refinement space after training. The effect is heterogeneous across backbone-dataset pairs, and broader coverage also increases exposure to negative transfer.

Abstract

Explore similar work

Selective Hypergraph Refinement for Frozen Graph Clustering

AdaGraph: A Graph-Native Clustering Algorithm That Overcomes the Curse of Dimensionality and Enables Scientific Discovery

G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation