HAL-x is a hierarchical density-clustering algorithm that uses supervised linkage to build a tunable cluster hierarchy from raw single-cell data. It scales to tens of millions of cells on an ordinary laptop, outperforms Parc, Phenograph and HDBSCAN on standard cytometry benchmarks, and its clusters classify clinical status from single-cell profiles with near-perfect F1 scores.
The problem
Technologies like flow and mass cytometry measure dozens of markers across tens of millions of cells per study. Grouping those cells into biologically meaningful populations is the first step of almost every analysis, and at this scale it is computationally hard: several popular clustering methods run out of memory somewhere around a million points, and the ones that survive give little control over how fine the resulting populations should be.
The approach
HAL-x separates the problem into a fast, unsupervised step and a supervised, self-consistent one. First, a subsample of the data is embedded and a density map is built; local density maxima become candidate clusters and every point is assigned to its nearest mode. Then, instead of merging neighbouring clusters with a geometric distance, HAL-x trains a classifier to tell them apart and merges the pair that is hardest to distinguish out of sample. Repeating this yields a full hierarchy of clusters, and a single cross-validation score lets the user pick the resolution at which clusters are still statistically meaningful. Because the merging is driven by a classifier, the same model labels the complete dataset, including the cells that were never embedded.
Results
On the Levine flow-cytometry (81,747 cells, 13 markers) and mass-cytometry (104,184 cells, 32 markers) benchmarks, HAL-x achieves higher F1 scores than Parc, Phenograph and HDBSCAN. On synthetic data from 103 to 107 points, several competing methods exceed available memory at 106 points while HAL-x keeps running. Applied to a 38-marker lupus cohort, it surfaces a mature neutrophil subpopulation that separates patients from healthy controls.
Why it matters
The supervised-linkage idea gives clustering something it usually lacks: a self-consistent notion of which clusters are real at a given resolution, learned from the data rather than set by a distance threshold. That is what makes the hierarchy tunable, and it is why the same approach transfers to other large, high-dimensional datasets beyond single-cell biology.