acceptodds
Under review as a conference paper at ICLR 2027

The Missing Link: Certifying And Repairing Approximate Density-based Clustering

Abstract

Density-based clustering identifies clusters of arbitrary shape and of different sizes. Its clusterings are derived from a minimum spanning tree (MST) over all pairwise distances: cutting the tree at a distance threshold gives a clustering, as in DBSCAN, and the whole tree defines a hierarchy of clusterings, as in HDBSCAN. For large datasets, scalable methods approximate the MST and build it only from the distances between nearest neighbors. Such an approximate MST can miss connections between points, and the returned clustering can then differ from the exact one without any indication. We show how to certify that a clustering obtained from an approximate MST equals the exact one, and how to repair it if it does not, with a search that examines no pair of points inside a cluster and skips pairs of clusters that lie further apart than the threshold. The key observation is that every edge of an approximate MST is a true connection between two points, so the approximation can omit connections but never invent them: a missing link can split an exact cluster into parts, but can never merge two exact clusters. Thus, it is sufficient to check for missing edges: pairs of close points that lie in different clusters but belong to the same exact cluster. If this check finds no such pair, the clustering is proven correct. Otherwise, we add the missing edges, merge the clusters they join, and check again; the number of such rounds grows only logarithmically with the number of parts into which a cluster was split. The check works on the output of any method that uses an approximate MST. On approximate trees of image embeddings, all failed clusterings are repaired in a single round. At million iNaturalist images, the whole pipeline takes seconds on six CPU threads, less than an exact library needs for its tree alone; the check and the repair account for of them. Finally, we extend the check from a single clustering to the whole hierarchy of clusterings that the MST defines.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
density-based clustering, HDBSCAN, minimum spanning tree, approximate nearest neighbors, mutual-reachability distance, certification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_uNVyOpenReview ↗
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

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:

  • The clustering covers the complete point set.
  • Every tree edge joins two points of that set and carries their exact MR distance or an upper bound. Under these conditions, the approximate tree can only split exact clusters at a fixed threshold, never merge them (Theorem 1(a)). This covers sparse neighbor graphs and sampled candidate pairs that retain all points.

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.

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 clusteringCore distancesRemaining workTotal
Approximate tree, check and repair (ours)60 s28 s87 s
Direct computation from all pairs within the threshold61 s48 s109 s
Exact tree of fast_hdbscan, without a checkincluded135 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:

  1. The exact result is unique. Data and parameters determine the clustering at a threshold, so exactness can be proven.
  2. 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.
  3. 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).

Reviewer_QXofOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses silent failures in density-based clustering from approximate MSTs. Firstly, a check at a fixed threshold that decides whether an approximate clustering equals the exact clustering without enumerating all pairs, by searching only inter-cluster missing edges; Secondly, a repair with a logarithmic round bound; Finally, a hierarchy check covering thresholds selected from the tree. Validation spans 336 trees on STL-10, CIFAR-100, iNaturalist-500k, up to 2.7M images, 300 damaged graphs, and comparisons with exact libraries. The check agrees with independent exact computation in every case; 32 failed clusterings are repaired in one round; at 2.7M points, the pipeline takes 87 s, of which check and repair take 4s.

Critical strengths

S1. Novel perspective. Rather than proposing another approximate method, the paper certifies and repairs the output of existing approximate MST-based clustering back to the exact result, exploiting the fact that approximation can only split—never merge—exact clusters. S2. Solid proofs and extensive experiments. Complete proofs support the theory, and the validation is extensive: 336 trees, case-by-case agreement with exact computation, 32/32 repairs in one round, 300 damaged graphs, and runs on up to 2.7M images against multiple exact baselines.

Critical weaknesses

W1. Overclaimed contribution statement. The title presents checking and repairing as a pair, and the task statement in the introduction also says, “decide whether it is the exact one, and repair it if it is not.” However, repair is provided only for the fixed-threshold case; there is no repair for non-fixed-threshold methods. W2. Insufficient experimental validation. At 2.7M points, the experiment only performs the fixed-threshold check and reports no hierarchy-check results. Since automatic threshold selection is precisely the paper’s motivating scenario, the strongest claim of contribution 3 is not delivered at scale. For k and m, the paper provides only sensitivity experiments, but lacks parameter selection guidance. There is no end-to-end narrative case analysis based on real data, nor any visualization of real cases and data. Moreover, there is no ablation of key components—such as bounding-box pruning and the hierarchy index—to isolate their contribution.

Questions for authors

Q1. Can the fixed-threshold repair be reused for approximate results under a non-fixed threshold? If not, why not? Q2. Does density-based clustering use only the density definition adopted in this paper? “Density” can also mean the average distance between a point and other points, i.e., Σ w(x,y)/|V|. The introduction should briefly define density to avoid ambiguity. Are there works that use average edge weights as a density definition? If so, they should be discussed. Q3. Could you add a pipeline overview and conceptual diagrams for the core mechanisms? Q4. In large-scale datasets, only the fixed-threshold check is reported; is contribution 3 intended to address this scale, and if not, why not, and does this contradict your claim to certify results where the threshold is selected automatically from the tree? Q5. Section 3.1 says “we first select the core points, group them by cluster,” which reads as if core points must be filtered inside each cluster, without saying how. Q6. What does “the tree” on line 256 refer to—the approximate tree or the exact tree? Q7. How to set k and m? Since these are user-supplied parameters, a practical setting guide should be provided. Q8. Could you add an end-to-end case study with a figure showing a real split cluster and its missing edges? Q9. There is no ablation isolating the contribution of key algorithmic components, including but not limited to bounding-box pruning and the hierarchy index. Could you report the check time and candidate-pair count with and without bounding-box pruning, and the hierarchy check time with and without the hierarchical index, to show each component's contribution?

3 comments

Thank you for the detailed review. We have completed the additional experiments and prepared the two requested figures. We will include them in the revised paper and notify you when it is available.

Q1 / W1

Yes. We select a threshold t from the approximate tree, keep it fixed, and repair the clustering at t. The result is the exact clustering at that threshold, even when t was selected from the data. The logarithmic bound on the number of repair rounds still applies.

A passed hierarchy check over the required range of thresholds additionally certifies agreement with the exact tree’s selection. We will make the two contributions explicit: check and repair at a given or automatically selected threshold, and hierarchy certification of the selection itself.

Q2

We use the DBSCAN*/mutual-reachability formulation. A point’s core distance is its distance to the μ-th nearest other point. At threshold ε, it is a core point if this distance is at most ε, meaning that at least μ other points lie within ε. We will give this definition in the introduction.

Other density definitions exist. For example, LOF (Breunig et al., SIGMOD 2000) uses the inverse of the average reachability distance within a local neighborhood to define local reachability density. It is an outlier-detection method; its local average differs from averaging distances to every point in the dataset. We will cite it and state that our guarantees concern the mutual-reachability formulation.

Q3

We have prepared the overview. It shows the steps in order: exact core distances and candidate pairs from approximate search, exact MR weights, the tree, threshold selection, and the loop of check and repair. The hierarchy check appears as a separate branch for certifying the selection. We will include this figure and the real-data illustration described in Q8.

Q4 / W2

At 2.7 million points, the fixed-threshold check and repair take about 4 s within the 87.5 s pipeline and return the exact clustering at the supplied threshold. This also applies when the threshold is selected from the approximate tree and then held fixed (Q1).

The hierarchy check can additionally certify the selection when it passes over the required range of thresholds. Its guarantee has no dataset-size restriction. In the paper, it passes for 130 of 336 trees, on datasets of up to 60,000 points. We have now tested 15 iNaturalist trees at five sizes from 100,000 to 2.7 million points, with three runs per tree.

With 10 neighbors, it finds a verified hierarchy error at every size. Median check times are 0.16 to 3.95 s on one CPU, including the index and excluding core-distance and tree construction.

With 30 neighbors and with the tree returned by fast_hdbscan, the search reaches its limit of 50 million node-pair visits. At 2.7 million points, it also reaches a tenfold larger limit, including for trees with 60 or 100 neighbors. These runs are reported as inconclusive. Both larger neighborhoods correct a verified error in the 30-neighbor hierarchy and pass the fixed-threshold check. The new experiments thus demonstrate detection of hierarchy errors at full scale, alongside the certified check and repair at a fixed threshold. We will state the measured range of the hierarchy results in the contribution list and add the complete tables to the appendix.

Q5

Core distances are computed on the whole dataset. At threshold ε, we take all points whose core distance is at most ε and group them by their cluster in the given clustering. We will rewrite the sentence to make these two steps explicit.

Q6

It is the approximate tree T̂. The threshold is selected from T̂, while the exact MST T defines the reference hierarchy. We will use these symbols consistently in the selection discussion.

Q7

k is the number of clusters expected by the application. In our benchmarks, we use the known class counts as fixed targets. When the application does not supply a count, several plausible values can be examined while reusing the same tree and core distances.

m is the size of the smallest group that should count as a cluster. Choose it according to the application; our default is m = 10. Both k and m are separate from the density parameter μ and the number of neighbors used to build the graph.

In Appendix E.5, we vary k by ±20% and m over 5, 10 and 20. All 90 checks pass, and mean ARI exceeds that of k-means in all 18 settings. If no threshold gives exactly k clusters, the rule selects the closest count that occurs. We recommend reporting the attained count and the fraction of points assigned a label afterwards, and will add this guidance to Section 3.3.

Q8/W2

We have prepared a figure for 13,000 STL-10 images, their 10D DINOv2/AE embeddings, and an NN-Descent tree with 10 neighbors. It shows an exact cluster of 4,150 images split into two parts of 1,910 and 2,240. The check finds an edge between them with MR weight 0.339, below the selected threshold of 0.358. Adding that edge reconnects the two parts.

Across the full dataset, two missing edges repair the clustering in one round. An independent enumeration of all pairs within the threshold confirms the result. The figure shows the images at the ends of the missing edge and representatives of both parts. PCA is used only for display; all clustering decisions use the original 10D distances.

The case study illustrates recovery of the exact clustering defined by mutual-reachability distances. Section 4.4 reports how repair affects agreement with the given class labels across all 32 repaired cases.

Q9/W2

We ran both ablations, with 228 measurements and three separate runs per setting on one CPU. The bounding-box comparison covers 27 trees with the same inputs, thresholds and stopping conditions. These times measure the Python implementation on one CPU; the paper’s optimized pipeline uses six CPU threads.

Bounding boxes let the check skip pairs of clusters that are too far apart to have a missing connection. In the two iNaturalist cases below, they remove more than 99% of the cluster pairs that would otherwise be searched. The result of the check is identical with and without them.

Dataset (points)Time with boxesTime without boxesCluster pairs searched (with / without)
STL-10 (13,000)0.09 s0.09 s45 / 55
CIFAR-100 (60,000)0.06 s0.14 s296 / 10,585
iNaturalist (500,000)0.82 s1.98 s1,361 / 158,766
iNaturalist (2.7 million)15.1 s20.3 s5,230 / 1,056,331

All rows use AE embeddings and NN-Descent with 30 neighbors. Times are medians of three runs, and all four checks pass. Bounding boxes skip more than 99% of cluster-pair searches in the two iNaturalist cases while preserving the reported missing edges. On the small STL-10 example, both versions take about 0.09 s.

Both parts of the hierarchy index contribute to the successful checks. Without traversal of merged groups, the STL-10 check takes 9.0 s instead of 2.0 s. On CIFAR-100, it reaches the limit of 100 million point-pair tests and reports inconclusive, while the full index passes in 4.0 s. Removing only binary lifting for path queries increases the CIFAR-100 time from 4.0 to 18.4 s.

We will include the complete paired tables, timing ranges, numbers of tested pairs and check results in the appendix.

Thank you to the authors for their response. However, repair at an automatically selected threshold is exact only at that threshold: if the threshold selected on the approximate tree differs from the one the exact tree would select, the repaired clustering is exact at the former, not the one the exact tree would give. It remains unclear how the authors return the clustering the exact method would produce. I will therefore retain my original scores.

Reviewer_U1YHOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies the DBSCAN clustering algorithm, from the perspective of the problem of constructing an MST of the mutual-reachability graph of the dataset. The paper proposes a method to 'fix' an approximate MST in order to return clusters equivalent to those extracted from an exact MST.

The proposed method is to look for edges which have been missed in the approximate MST and repair them.

Critical strengths

The problem of finding a good density-based clustering reduces to constructing an MST on the dataset, under the mutual reachability distance. This paper proposes a method for doing this which appears to have good empirical performance.

A fast algorithm for constructing an exact MST from geometric data is certainly of interest to the community.

Critical weaknesses

The algorithm proposed in this paper begins with an MST built using an approximate nearest neighbour algorithm. The justification for the proposed 'fix' method is that

"The edges of the approximate MST therefore carry their true mutual-reachability distances, ... The only possible error is therefore a missing edge" (lines 110-113)

Moreover, the paper claims that the algorithm proceeds by first constructing an approximate MST T^\hat{T}, and then setting the exact weights of the edges:

"the weight ... of each proposed pair is computed from the exact distances, which we compute separately from the graph" (lines 190-193)

Weakness 1. Computing the exact mutual reachability distances requires computing κμ(x)\kappa_\mu(x) for each vertex - this is the distance to the μ\mu-th nearest neighbour of xx. This seems to require an exact nearest neighbour algorithm, and thus defeats the point of using an approximate nearest neighbour algorithm.

On investigation of the supplied code, it appears that the weights of the MST are set on lines 181-193 of src/dc_graph.py. If I have understood this correctly, the code in fact does not compute the exact weights, but rather uses an approximation only. (As an aside, the codebase is overly complex and difficult to understand. It also appears to include code from a different research project, such as model.py).

Weakness 2. The experiments do not correctly implement the proposed algorithm, rather they use approximate weights in the MST.

It may be that, despite these weaknesses the algorithm is a fast DBSCAN algorithm in practice. However if that is the case, then I suspect we might as well use the approximate MST without fixing it. The value of this proposed algorithm is that it is equivalent to an exact method, but I am not convinced that this has been correctly evaluated.

Questions for authors
  1. Does computing the exact weights of the edges of the MST require using an exact nearest neighbour algorithm? Does this not defeat the benefit of using an approximate NN algorithm to construct the MST?
  2. Where in the supplied code are the weights of the MST calculated?
  3. How does the clustering performance of the fixed clustering compare to that of the approximate clustering before the fix?
7 comments

Thank you for reading both the paper and the code. We clarify below how exact core distances, approximate tree construction, and the check and repair work together.

Q1/W1

No. Exact core-distance queries do not eliminate the measured benefit of approximate tree construction. We compute core distances exactly, with a nearest-neighbor query for each point, and include this cost in all end-to-end timings. We build the tree from a sparse ANN candidate graph instead of computing the MST of the complete mutual-reachability graph. Every candidate edge receives its exact MR weight. We use NN-Descent and HNSW to study certification and repair of approximate graph constructions from related work. On 2.7 million points, our pipeline returns the certified clustering at the fixed threshold in 87.5 s on six CPU threads: 59.6 s for the exact core distances, about 24 s for the approximate tree, and 3.8 s for the check and repair. The fast_hdbscan library takes 135.3 s to build its tree, including its own core-distance computation.

Exact core distances alone do not give the exact clustering: all 32 clusterings that failed the check already used exact core distances and exact edge weights. The exact neighbors could also be reused, but even their sparse graph may omit connections between dense groups when each point’s retained neighbors lie within its own group. Our check applies to either construction.

For a fixed threshold, the check need not compute every exact core distance. ANN candidates can already prove that a point has at least μ neighbors within the threshold; only unresolved points need bounded exact queries. We evaluate this variant in the appendix D.6.

Q2/W2

The check and repair experiments reported in the paper use exact MR weights. The relevant functions in reproduce/extended/common.py are:

  • core_distances computes exact core distances on the full dataset with a kd-tree query.
  • mr_weights computes the MR weight of every candidate pair from those cores and its pairwise distance in float64.
  • tree_from_edges builds the MST from these weights.

You read compute_dc_graph_approx correctly: it estimated core distances from NN-Descent lists. It was used only by the separate diagnostic script verify_exact.py, not by the reported check and repair experiments. We have removed both from the revised release: https://anonymous.4open.science/r/SLICE-8406/

The remaining compute_dc_graph_connected is used by reproduce/scaling.py for the trained-pipeline comparison with SHADE. The autoencoder in src/model.py produces embeddings used in Section 4.

Theorem 1(a) also covers trees built with estimated core distances. Using the same distance calculation for both sets, the μ-th nearest point among a subset of distinct other points cannot be closer than the μ-th nearest among all points. The estimated core distance is therefore an upper bound. With all points retained and MR weights computed from these bounds and the exact pairwise distances, such a tree can only split exact clusters at a fixed threshold, never merge them. It is therefore a valid input to the check, which tests core points and cross-cluster connections exactly.

Q3

Section 4.4 and the corresponding appendix table report the comparison for all 32 clusterings that failed the check. After repair, all 32 equal the exact reference at the same threshold. Before repair, up to 49% of the points lie in exact clusters that the approximate tree splits, and the ARI between the approximate and repaired clusterings is as low as 0.77.

Class-label scores do not reliably reveal these errors: in 24 of the 32 cases, ARI with respect to the given class labels changes by less than 0.001 when noise points count as singletons. Repair establishes that the result is the clustering defined by the density criterion. Section 4.4 reports the complete before-and-after class-label scores, including the scores after noise points are assigned.

These results show why checking is useful even when quality scores look similar. With only 10 neighbors, 26 of 48 trees in our study give incorrect clusterings. The check detects these errors, and repair recovers the exact clustering at the chosen threshold.

We will make the exact and approximate steps explicit at the start of Section 3 and add the pipeline figure.

Thanks for your response.

Weakness 2

I am willing to believe that my original weakness 2 was incorrect, and that the experiment does implement the algorithm with exact MR distances on the edges in the MST, although it is near-impossible for me to verify this due to the complexity and structure of the supplied code. It seems to me that the code is substantially AI generated, to the extent that it is no longer human-verifiable.

Weakness 1

I still have a concern about the use of both an approximate ANN method (NN-descent or HNSW), followed by an exact method (kd-tree). As I understand it, the algorithm is:

  1. Build an approximate kNN graph with NN-descent or HNSW.
  2. Build an MST of this graph.
  3. Compute the exact k-nearest neighbours of all nodes using a KDTree.
  4. Use the distances to these exact neighbours to set the MR weights on the MST edges.

Would the following be an equivalent, and faster algorithm?

  1. Build an exact kNN graph using a KDTree.
  2. Build an MST of this graph.
  3. Set the MR weights on the MST edges.

Overall, I am still struggling to place this paper as either a primarily theoretical result, or as a primarily empirical one. It seems that the empirical benefit of the algorithm, viewed simply as a clustering algorithm, is somewhat limited. On the other hand, as a theoretical result it is an algorithm for builing an exact MR MST, but it does not have rigorous complexity results.

Thank you for the follow up and for the concrete proposal. We also appreciate your quick response!

W1

Your first list (steps 1 to 4) describes how we build the tree. Two steps follow them, the check and the repair. They are the contribution of the paper, and they would be needed here as well.

Your variant alone is not exact. The MST of a kNN graph is not the MST over all pairs of points, even if every neighbor is exact: a kNN graph contains only pairs of near neighbors, so the edges between non neighbors would be missing. The errors come from the step from all pairs to a sparse graph, whether the neighbors in this graph are exact or approximate.

We built your variant (exact neighbors from a kd-tree, MST of this graph) for the 120 settings of Section 4.1.

Neighbors per pointExact neighborsApproximate neighbors
1056 of 120 clusterings wrong26 of 48 wrong
302 of 120 wrong6 of 240 wrong

This table can and will be extended for the paper.

Exact neighbors lead to almost the same share of wrong clusterings as approximate ones. With 10 exact neighbors, up to 58% of the points lie in a cluster that the tree had split. On the complete iNaturalist data (2.7 million points), this tree splits one exact cluster into 20 parts. The check does not depend on how a tree was built. Its result is the same as the exact reference for all 240 trees above, and one round of repairs corrects each of the 58 wrong clusterings. At 2.7 million points, construction, check and repair together take about 86 s, so runtime wise it would be faster, thank you for this suggestion. We will add it to the paper. But the main reason for the approximation was simply that scalable methods and libraries build their trees using ANN graphs, and these are the trees that users need to verify. We hope that clarifies the motivation behind it.

W2

Thank you for reconsidering this point and yes as the AI use statement of the paper says, llms helped to write and refactor the experiment code under our direction. We reviewed every change and audited it. Every result of the check and of the repair is compared with an exact computation by independent code e.g. the hdbscan library, fast_hdbscan, etc. They produce the same results. Please ask if anything is unclear.

Overall/What kind of paper is this?

The paper proposes neither a new clustering algorithm nor a new algorithm for the exact MST. It solves a verification problem: given the clustering from an approximate tree, prove that it is exact, or repair it. It never builds the exact MST. For this reason the check and the repair take 4 s at 2.7 million points, where the exact library takes 135 s for its tree.

On the empirical side, the paper grew out of a failure in practice. In deep clustering experiments on one million points, an ANN graph reproducibly fell apart into 253 parts, and the extracted clustering had 260 clusters instead of 10. We then found that the problem is general. It occurs with both ANN indexes that we tested (32 of 336 trees), in the default setting of the hdbscan library on three of six datasets (Table 19) and, as your proposal shows, with exact neighbors as well. Quality scores do not show it (Section 4.4). This finding is the reason for the paper: with the check, a reported clustering depends only on the data and on the definition of the algorithm.

On the theoretical side, the guarantees hold without assumptions on the data, which is another main benefit. The concrete theorems are stated in the paper (Theorem 1, Propositions 1 and 2, Lemma 1). For the running time we state the worst case, which is quadratic. The exact parallel algorithm of Wang et al. (2021) has the same worst case, O(n2)O(n^2) work. But our experiments stay far below the worst case, with 0.09 s for the check on 500,000 points.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.