The shrinking cluster
HDBSCAN* can change its answer when you raise min_samples by one small step. This page explains why, how to spot the cluster at risk, and how to prove that a step is safe.
A biologist clusters 20,000 cells and finds five cell types. A data team groups customer reviews into topics with BERTopic. An astronomer searches a star catalogue for new star clusters. All three use HDBSCAN*, and all three set its density parameter, min_samples, once, or leave it at the default.
A small change to that parameter, say from 30 to 35, usually changes little. In the benchmarks of my preprint, with min_cluster_size moving together with min_samples as in the default, about one step in six (16.9% on 47 datasets) changed the result a lot: a cluster vanished, two clusters merged, or a fifth of the points changed label.
This is not a hidden flaw. Any rule with a size threshold behaves this way: when a parameter changes, a cluster close to min_cluster_size can drop out or merge with another. The documentation says as much. The hdbscan guide shows that min_samples “clearly has a dramatic effect on clustering” and makes the clustering more conservative as it grows. The scikit-learn user guide says that min_samples “tends to be a more robust hyperparameter” than the eps of DBSCAN, a comparison with eps and not a claim that the partition stays the same. The docstrings of scikit-learn and hdbscan, and BERTopic’s guide, state that min_samples takes the value of min_cluster_size when it is left unset. Campello et al. (2015) describe it as a classic smoothing factor in density estimates, to which methods with an analogous parameter are typically robust, and fix it at a single non-critical value in their experiments. They also report that runs with other values did not change their main conclusions. What was missing is a measurement of how often a small step changes the flat partition, and a way to see it coming without refitting.
Trying the nearby values by brute force shows whether a step changes the result, but it is slow: on 100,000 points, a sweep over 24 values takes 24 to 80 minutes. The preprint proposes a cheaper check that uses the run you already have. It explains why a step changes the result, flags the cluster at risk and proves when a step is safe, at about 1% of the cost of a new run. These results come from a single preprint that has not yet been peer reviewed. To try the check on your own data, with scikit-learn or the hdbscan library:
pip install git+https://github.com/provezano/minpts-check
from minpts_check import check_min_samples
check_min_samples(X, min_samples=30, min_cluster_size=30).summary()
The demo below runs HDBSCAN* in your browser, so you can watch a cluster vanish.
Three Gaussian clouds (60, 60 and 40 points) and 20 scattered points, as in the paper’s example, drawn at random here. The numbers differ from the paper’s; the behaviour is the same.
What the paper found
A higher min_samples changes the cluster tree. A selected cluster can shrink below the minimum cluster size, drop out of the selection and change the output.
A count from the current run flags the cluster at risk. On new tables, 82% of flagged clusters were lost, against 10% of unflagged clusters of the same size.
A theorem gives conditions, checked on one run, under which the next value keeps the same clusters. No certified step was fragile.
How HDBSCAN* finds clusters
Picture the data as a landscape in which altitude is point density. As the water level drops, the densest peaks appear first as islands, and neighbouring islands later join. HDBSCAN* records this history as a tree and then picks one set of islands as the clusters.
Two parameters steer the process. min_samples (mpts in the paper) sets how many neighbours a point needs to count as dense. min_cluster_size (mclSize) sets the smallest island that counts as a cluster. In scikit-learn, the hdbscan library and BERTopic, min_samples takes the value of min_cluster_size when it is left unset, so by default the two move together. Click the five stages to see each one on the example.
The last stage, excess of mass (EOM), gives each branch a stability score: roughly, how long its points stay together as the density level rises. It then picks the branches with the highest total score, never a branch together with one of its descendants. Only branches with at least min_cluster_size points can be picked, and this rule is behind everything that follows.
A small step, a big change
With the method in place, we can measure how often a small step changes its answer. Neto et al. (2018) describe HDBSCAN* as robust to min_samples, in that a small change “typically leads to only a small or no change in the clustering structure”, a statement about the hierarchy rather than the flat clusters. Users work with the final flat partition, so the measurement has to be made on the partition.
The paper calls a step fragile when the outputs at two neighbouring values agree poorly, with an adjusted Rand index (ARI) below 0.8 and noise counted as one label. The neighbouring values come from a grid of 24 values between 5 and 120, each 11% to 20% above the previous one.
The real pipelines were single-cell analysis with scanpy and UMAP, topic modelling with BERTopic, and the search for star clusters in data from the Gaia satellite. When a step was fragile, a cluster almost always appeared, disappeared, split or merged.
The tree is to blame, not the threshold
To predict such changes, we first need to know which stage of the method causes them. When min_cluster_size follows min_samples, one step changes two things: the tree, because core distances grow, and the size threshold. A 2 × 2 design separates them by changing only the tree, only the threshold, or both. Pick a step in the lab and compare the four panels.
The lab shows one dataset. On 47 new datasets, the fragile steps split as follows.
EOM picks only among branches with at least min_cluster_size points. A new threshold on the old tree can remove only clusters that were already below it, which is rare. A new tree can shrink any branch. When a selected cluster drops below the threshold, it is no longer a candidate, and EOM re-decides the branch above it: the cluster becomes noise, joins a neighbour, or the branch is reorganised.
To test this directly, the paper fixed the threshold and planted clusters of known size. Clusters just above the threshold (1.2 to 1.35 times) were often lost, and clusters two to three times larger never were. Every shape tested behaved this way.
On real data, steps near the threshold were more fragile than steps far from it, after adjusting for the number of clusters, the noise share and the threshold itself (odds ratio 6.6). Some steps far from the threshold are fragile too, so size explains most cases but not all.
A predictor that uses a single run
If a cluster is lost because it shrinks in the new tree, we can ask how many of its points remain at the level where it is born. This needs no new tree: compute the core distances at the next value with one nearest-neighbour query, and count.
If ŝ falls below the next min_cluster_size, the cluster cannot reappear unchanged. In the paper’s example, the 41-point cluster has ŝ = 38 at the step to 40, and it is lost. At the step from 8 to 9, every cluster has ŝ ≥ 43, well above the threshold.
The predictor was then tested on 25 OpenML tables that the work had never used, with the analysis fixed before the data were downloaded.
The predictor ranks well both the clusters absorbed by a larger one (AUC 0.80) and those that dissolve into noise (0.94). It does not predict splits, which are rare here (40 of 1,620 losses) and follow a different mechanism. Splits dominate when min_samples goes down, a case the paper does not cover.
Used as an alarm, the rule “flag the step if any cluster has ŝ below the next threshold” flagged 48% of the steps and caught 89% of the fragile ones. Only 4.4% of the unflagged steps were fragile. This analysis is exploratory and has not been replicated.
Resampling the data shows the same size effect. Clusters just above the threshold disappeared in 52% of resamples, against 17% to 26% for larger ones.
A certificate that nothing changes
Predicting risk is useful, but proving safety is stronger. The paper’s theorem uses the current run and the neighbour distances at the next value. If its three conditions hold, the next value selects the same clusters, and every point outside a small tolerance set U keeps its label. The new tree is never built.
A core that holds
Every selected cluster keeps a certified core of at least the next min_cluster_size points over all density levels the step can affect.
Stability to spare
Each selected cluster’s certified stability beats the most its descendants could reach.
Comfortable decisions
Every EOM decision in the current run won by more than the step can change it.
The size condition is where the shrinking mechanism returns. If a selected cluster can fall below the threshold during the step, the certificate does not claim safety. Of the fragile steps, 82.7% fail this condition first.
The certificate covers a minority of steps. With U capped at 1% of the points, it certified 9.5% of the steps on the exploratory data and 26.2% on a new benchmark set. It was built as a diagnostic that shows where stability can be proved and why it fails elsewhere. A large U still allows an ARI below 0.8, so U should be capped.
min_samples therefore has to use the observed growth of the core distances.Why not simply rerun?
Both tools may seem unnecessary, since one could simply rerun HDBSCAN* at the next value. A rerun shows what changed but not why, and it costs a full fit per value. The predictor and the certificate need the current run plus one nearest-neighbour query for the whole grid.
| 100,000 points, 1 thread | covertype | Higgs |
|---|---|---|
| One HDBSCAN* fit | 63 s | 208 s |
| Sweep over the 24-value grid | 24 min | 80 min |
| Certificate check (after the neighbour query) | 1.5 s | 1.2 s |
What to do with this
The quickest route is minpts-check, which runs the whole check from one fit and one neighbour query: it flags the clusters at risk, proves the safe steps and handles the counting convention.
pip install git+https://github.com/provezano/minpts-check
from minpts_check import check_min_samples
check_min_samples(X, min_samples=30, min_cluster_size=30).summary()
To check by hand, whether you use HDBSCAN* directly, in scikit-learn or inside BERTopic:
- Run a few values of
min_samplesaround your choice and check that the clusters hold. - Treat a selected cluster close to
min_cluster_size, or with ŝ below the next threshold, as a warning. Computing ŝ costs one neighbour query and no refit. - When stability matters, report the agreement between neighbouring values, with and without noise, and the certified steps.
- Mind the counting convention: scikit-learn’s
min_samplescounts the point itself and thehdbscanlibrary’s does not, so scikit-learn’s m + 1 equalshdbscan’s m.
If you compare methods that use HDBSCAN*, report min_samples, min_cluster_size, the extraction method and the tree algorithm. Prefer exact trees when stability matters: the default approximate tree was more fragile (29.3% of steps against 23.4% on the exploratory data).
Computing ŝ step by step
- Run HDBSCAN* at the current value m and keep the condensed tree and the selected clusters.
- For each selected cluster C, take the level λ at which it is born in the condensed tree; its birth radius is 1/λ.
- Compute, for every point, the distance to the neighbour that defines its core at the next value m′ (one k-NN query; mind the counting convention above).
- ŝ(C) is the number of points of C whose new core distance is at most the birth radius.
- If ŝ(C) < m′ (the next
min_cluster_size), flag C as at risk.
The paper’s supplementary material includes a reference implementation of the stability report and of the certificate checker; minpts-check packages both for everyday use.
One exploratory study and six replications
The numbers on this page come from seven studies. The tools were developed on 61 datasets. Each later study used data that no earlier study had touched, tested a few hypotheses with Holm’s correction, and followed an analysis plan written before the runs. Every planned hypothesis is reported, confirmed or not.
| Data | Question | Confirmed |
|---|---|---|
| 61 benchmark and OpenML datasets | exploration: first form of every tool | – |
| 47 new datasets, 3 seeds | how often; which stage causes it | 1 of 5 |
| planted Gaussians; 51 datasets | mechanism, with the threshold fixed | 3 of 4 |
| five planted shapes; 19 tables | robustness to shape and confounders | 8 of 8 |
| 10 OpenML tables, up to 20,000 points | larger tables: rate, mechanism, certificate | 3 of 5 |
| 17 datasets: single-cell, BERTopic, Gaia | real pipelines | 3 of 4 |
| 25 new OpenML tables | predictor ŝ; resampling | 3 of 4 |
Some hypotheses were not confirmed, and they are informative too:
- In the real pipelines, the fragile rate (13.6%) was not significantly above 10%, and it varied by pipeline.
- In BERTopic, two UMAP seeds at the same
min_samplesdisagreed in 98.1% of cases, so the embedding seed moves the output far more than the parameter. - On the larger tables, the size ratio as a single pooled score ranked steps only moderately (AUC 0.71, below the planned bar), though it ranked them well within each table.
- Decreases of
min_samples, leaf extraction and approximate trees are outside the main claims.
What was already known
HDBSCAN* was proposed by Campello, Moulavi and Sander (2013, 2015), and McInnes and colleagues (2017) wrote the popular implementation. The stability of the hierarchy is well studied, from the statistical theory of density cluster trees to ToMATo (Chazal and colleagues, 2013) and the work of Rolle and Scoccola (2024), who also show that the hierarchy can change arbitrarily after a one-unit change of the parameter.
Earlier work had also seen sensitivity in the final partition. PLSCAN (Bot and colleagues, 2025) notes on one example that HDBSCAN*’s clusterings vary considerably with the parameter and chooses the minimum cluster size by persistence. FOSC-X (Simpson and Campello, 2026) lists near-optimal EOM solutions on a fixed tree. Malzer and Baum (2020) documented over-splitting into micro-clusters at small values. Neto and colleagues (2018, 2021, 2022) compute the hierarchies for all values at once and describe them as robust to small changes. Hunt and Reffert (2021) found, on Gaia data, that the recovery rate of known star clusters ranges from 0.42 to 0.82 with the minimum cluster size.
That a cluster near the size threshold can drop out when a parameter changes is expected of any threshold rule. The paper adds a label-free measure of agreement between neighbouring values, the stage of the method that causes each change, a prediction of which cluster will be lost, and a proof of when a step is harmless. These results come from one preprint and still need independent replication.
Glossary
- min_samples (mpts)
- How many neighbours define a point’s core distance. Controls the smoothing of the density.
- min_cluster_size (mclSize)
- Minimum size of a branch for it to count as a cluster in the condensed tree.
- core distance
- Distance from a point to its m-th nearest neighbour. Small in dense regions.
- mutual reachability
- max(core(p), core(q), distance(p, q)). The distance used to build the tree.
- λ (lambda)
- Density level, equal to 1 / radius. The larger, the denser.
- condensed tree
- The hierarchy after discarding branches smaller than min_cluster_size.
- EOM
- Excess of mass: the rule that selects the final clusters by maximising total stability.
- fragile step
- Two neighbouring values of min_samples whose outputs have ARI < 0.8 (noise counted as one label).
- ARI
- Adjusted Rand index: 1 = identical partitions; near 0 = agreement by chance.
- lost cluster
- No cluster of the other output has a Jaccard index of at least 1/2 with it.
- ŝ
- Number of the cluster’s points whose new core distance fits within the radius at which the cluster is born (its birth radius).
- tolerance set U
- The only points the certificate does not cover; all others provably keep their label.