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

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 $336$ approximate trees of image embeddings, all $32$ failed clusterings are repaired in a single round. At $2.7$ million iNaturalist images, the whole pipeline takes $87$ seconds on six CPU threads, less than an exact library needs for its tree alone; the check and the repair account for $4$ of them. Finally, we extend the check from a single clustering to the whole hierarchy of clusterings that the MST defines.