GraphHDBSCAN*: Graph-based Hierarchical Clustering on High-dimensional Spaces with Applications to Single-cell RNA Sequencing Data

Single-cell RNA sequencing (scRNA-seq) is widely used to resolve cellular heterogeneity across thousands to millions of cells. A major challenge is identifying biologically meaningful cell populations while preserving their hierarchical organization, because broad cell types often split into more specialized subtypes. However, state-of-the-art approaches mostly focus on flat partitions and ignore the hierarchical nature of single-cell data. Here we introduce GraphHDBSCAN*, a graph-based extension of HDBSCAN* with an effectively hyperparameter-free hierarchical clustering stage that operates on a graph representation of the data, enabling robust recovery of both hierarchical and non-hierarchical (flat) relationships in very high-dimensional, noisy datasets. We evaluate GraphHDBSCAN* across multiple scRNA-seq datasets and show that it recovers biologically meaningful hierarchies that agree more closely with curated biological references than alternative hierarchical clustering methods, while revealing fine-grained structure, including monocyte subpopulations. In addition, the method yields high-quality flat partitions that outperform widely used community-detection methods.