SPORE: Skeleton Propagation Over Recalibrating Expansions

View PDF HTML (experimental)

Abstract:Clustering is a foundational task in data analysis, yet most algorithms impose rigid assumptions on cluster geometry: centroid-based methods favor convex structures, while density-based approaches break down under variable local density or moderate dimensionality. This paper introduces SPORE (Skeleton Propagation Over Recalibrating Expansions), a classical clustering algorithm built to handle arbitrary geometry without relying on global density parameters. SPORE grows clusters through a nearest-neighbor graph, admitting new points based on each cluster's own evolving distance statistics, with density-ordered seeding enabling recovery of nested and asymmetrically separated structures. A refinement stage exploits initial over-segmentation, propagating high-confidence cluster skeletons outward to resolve ambiguous boundaries in low-contrast regions. Across 28 diverse benchmark datasets, SPORE achieves a statistically significant improvement in ARI-based recovery capacity over all evaluated baselines, with strong performance accessible within ten evaluations of a fixed hyperparameter grid.

Comments: Renamed the algorithm to SPORE; added random-grid baseline to ablations

Subjects:

Machine Learning (cs.LG)

Cite as: arXiv:2511.00064 [cs.LG]

(or arXiv:2511.00064v4 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2511.00064

arXiv-issued DOI via DataCite

Submission history

From: Randolph Wiredu-Aidoo [view email] [v1] Wed, 29 Oct 2025 03:44:05 UTC (3,110 KB) [v2] Wed, 5 Nov 2025 07:06:55 UTC (3,110 KB) [v3] Mon, 9 Feb 2026 03:34:51 UTC (376 KB) [v4] Mon, 30 Mar 2026 01:48:43 UTC (1,329 KB)