GBSK: Skeleton Clustering via Granular-ball Computing and Multi-Sampling for Large-Scale Data.

Abstract

To overcome the computational bottlenecks of traditional density-based clustering, we propose Granular-Ball SKeleton clustering (GBSK), a scalable algorithm that achieves near-linear time complexity while preserving topological accuracy. GBSK introduces a strategic shift from full density estimation to the sketching of geometric density skeleton-recover a graph connecting high-density modes that captures essential cluster connectivity. Theoretically, we find that granular-ball density statistics can serve as a computationally efficient, asymptotically approximate local proxy for kernel density estimation (KDE), providing a statistical support for discrete mode extraction within the well-established KDE framework. Methodologically, GBSK integrates three key components: adaptive granular-ball construction for efficient local data approximation, multi-stage sampling for rapid density estimation, and a secondary refinement process that aggregates candidate modes from all sample sets to produce a robust final density skeleton. To enhance usability, we introduce an adaptive variant, AGBSK, which reduces hyperparameters to just the cluster count. Extensive experiments on datasets scaling up to 100 million instances and 3072 dimensions demonstrate that GBSK and AGBSK maintain competitive accuracy while achieving orders-of-magnitude speedup over state-of-the-art methods.