- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper addresses a real gap in approximate density-based clustering: users cannot verify whether an approximate MST yields the exact clustering at a given threshold.
Its key observation is that approximation only affects which pairs are found, not their distances, so errors are missing edges that can only split exact clusters, never merge them. The authors propose a check, a repair for a fixed threshold, and a hierarchy check.
Critical strengths
Core insight is simple, correct. Approximation only affects which pairs are found, not their exact MR weights; so errors are missing edges that can only split clusters, never merge them. This guarantee holds only under the authors’ assumptions: a complete point set, exact core distances, and the MR/MST framework.
Validation is thorough and transparent. Checked against exact references on 336 trees up to 2.7M points, with failures, inconclusive cases, and floating-point caveats reported honestly.
Critical weaknesses
The guarantee fails for sampling-based approximations, but the paper never states this boundary. “Only split, never merge” requires a complete point set and exact core distances. Under sampling, both split and merge errors are possible. Since sampling is common in scalable clustering, this omission is misleading.
The algorithmic scope is never made explicit. The check relies on MR distance and MST structure specific to DBSCAN*/HDBSCAN, so it does not apply to Density Peak, Mean Shift, or k-means approximations. The paper neither states this restriction nor excludes these methods, inviting overgeneralization.
Questions for authors
NA
3 comments
I appreciate the clarification, but I am not convinced that stating the boundaries resolves my concern.
The response acknowledges the boundaries and promises to declare them, but does not argue that the contribution remains sufficient once they are declared. Specifically:
(1) the estimated-core-distance relaxation widens the scope but does not address the tension between exact core-distance cost (59.6 s of 87.5 s at 2.7M points) and the scalability claim;
(2) declaring a boundary is not evidence that the contribution holds within it;
(3) asserting that MR/MST is mainstream does not justify why this restricted scope warrants separate certification. I would need the revision to substantively address (1)–(3), not merely state the boundaries, before I can revise my assessment.
Thank you for the follow up. The revision is uploaded and contains the same arguments as below.
1. Exact core distances and scalability
Every exact method computes the core distances, because they are part of the definition of the clustering. At 2.7 million points (Table 7):
| Route to the exact clustering | Core distances | Remaining work | Total |
|---|---|---|---|
| Approximate tree, check and repair (ours) | 60 s | 28 s | 87 s |
| Direct computation from all pairs within the threshold | 61 s | 48 s | 109 s |
| Exact tree of fast_hdbscan, without a check | included | 135 s |
Our scalability claim is relative to exact computation, the only other way to obtain the same guarantee. We reduce the work that remains after the core distances, and of our 28 s the check and the repair take 4 s. At every size from 100,000 to 2.7 million points, our total is 26 to 35 percent below the time that the exact library needs for its tree alone.
At a fixed threshold, the check needs less than the core distances. It only has to decide which points are core points, and a query with a distance bound does that. At 500,000 points this lowers the time for core points and check from 5.5 s to 2.3 s (Table 4).
2. Evidence within the boundary
Within the boundary, Theorem 1 and Proposition 1 hold for every dataset, with no assumption on the data or on the quality of the approximate graph.
Every tree in Section 4 lies within the boundary, so stating it removes no result. The check agrees with an independent exact computation for all 336 trees. It finds 32 wrong clusterings, and one round of repair corrects each of them. The final clusterings also equal the exact reference in all runs at 2.7 million points, on ImageNet-1k, in up to 384 dimensions and on 300 deliberately damaged graphs.
We also enforce the conditions on every input. The check runs on all points, and the weight of every tree edge is computed from the exact core distances, also for trees from other libraries (0.4 s at 2.7 million points). A passed check is therefore a proof for this run, whichever method built the tree.
3. Why this scope warrants its own certificate
A certificate proves that an output equals one uniquely defined result, so it always belongs to one definition (McConnell et al., 2011). Density Peaks, Mean Shift and k-means define different results, and no single certificate can cover them.
For the MR/MST definition, a certificate is both possible and needed:
- The exact result is unique. Data and parameters determine the clustering at a threshold, so exactness can be proven.
- The errors are frequent and silent. No approximate method of this family gives a guarantee for an individual run (Table 20). We find wrong clusterings in 32 of 336 approximate trees and in the default setting of the hdbscan library on three of six datasets (Table 19). Up to 49% of the points lie in a split cluster. In 24 of the 32 cases the ARI with respect to the classes changes by less than 0.001, so quality scores do not show the error.
- The structure makes the certificate cheap. Approximation can only split clusters, so the tree edges already prove each cluster, and only pairs between clusters remain to be searched. The check and the repair therefore take 4 s where the exact tree takes 135 s.
The scope also covers a family of methods: DBSCAN* at any threshold, the upper part of the HDBSCAN* hierarchy, and the output of every method that builds such a tree.
In the revision, the abstract, the introduction and the limitations state the scope. Section 3 contains the argument of (2) and Section 4.2 the comparison of (1).
Thank you for your review and for recognizing the paper’s core insight. Our guarantees apply independently of the graph-construction method under the conditions below. We will state these conditions and the algorithmic scope explicitly in the abstract, introduction and limitations.
W1
The guarantee rests on two conditions:
Estimated core distances are covered too when they use distinct other candidate points and the same distance calculation as for the full dataset: the μ-th nearest candidate cannot be closer than the μ-th nearest point in the full dataset. With MR weights computed from these upper bounds and exact pairwise distances, the tree is a valid input to the check. The check tests core points and cross-cluster connections exactly.
It does not cover clustering a subsample and then assigning the remaining points. That procedure can both split and merge exact clusters, and a check on the subsample does not certify the full-data clustering. We will state this boundary explicitly.
W2
This scope is already specified in Section 2: “Exact clustering” defines the DBSCAN* clustering through mutual-reachability distances, and “Cluster extraction” identifies the threshold cut as the clustering we certify. For HDBSCAN*, the hierarchy check establishes agreement over the range of thresholds it verifies; certifying EOM selection requires the corresponding hierarchy information. These guarantees concern the MR/MST formulation, while Density Peaks, Mean Shift and k-means optimize different objectives.
Within this scope, the check is independent of the tree constructor. After reweighting hdbscan’s default trees and applying our threshold-selection rule, it finds errors on three of six datasets; repair recovers the exact clusterings. This comparison tests cuts of those trees at our selected thresholds. We will highlight this scope earlier in the abstract and introduction.