Approximate hierarchical density-based clustering using graph-based search indexes

Current exact hierarchical density-based clustering algorithms for high-dimensional data have asymptotically quadratic complexity. We present algorithms for approximate hierarchical density-based clustering, namely for single-linkage clustering and for HDBSCAN, with empirically near-linear time scalability. We explore both graph index-based incremental nearest neighbor search and an iterative exploration scheme on the graph index approximating the MST of the reachability graph similar to Kruskal. As graph index, we use both the bottom layer and a combination of all layers of an HNSW as a stand-in for connected search graphs. We provide experiments comparing the clusterings to baselines such as exact implementation and an algorithm using metric tree-based searchers. We explore the impact of the HNSW hyperparameters on the performance in terms of running time and clustering quality. For both single-linkage clustering and HDBSCAN, our algorithms yield highly accurate clusterings while being up to two orders of magnitude faster than industry-standard baselines such as scikit-learn’s hdbscan .