How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class $\mathcal{F}$. We call this problem Hierarchical $\mathcal{F}$-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of $\mathcal{F}$: trees and graphs of bounded diameter. We present the first polynomial time $\mathcal{O}(\log n\cdot\log\log n)$ and $\mathcal{O}(\log n)$-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes $\mathcal{F}$ for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call $p_{\mathcal{F}}$-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Clustering is a cornerstone of modern data analysis. Detecting clusters in exploratory data analyses (EDA) requires algorithms that make few assumptions about the data. Density-based clustering algorithms are particularly well-suited for EDA because they describe high-density regions, assuming only that a density exists. Applying density-based clustering algorithms in practice, however, requires selecting appropriate hyperparameters, which is difficult without prior knowledge of the data distribution. For example, DBSCAN requires selecting a density threshold, and HDBSCAN* relies on a minimum cluster size parameter. In this work, we propose Persistent Leaves Spatial Clustering for Applications with Noise (PLSCAN), a multiscale density-based clustering algorithm that replaces HDBSCAN*'s fixed minimum cluster size pruning of a mutual-reachability linkage hierarchy with a persistence-based cluster selection procedure. Effectively, PLSCAN identifies all minimum cluster sizes for which HDBSCAN* produces stable (leaf) clusters. In concept, PLSCAN applies scale-space clustering principles and is equivalent to persistent homology on a novel metric space. We compare its performance to HDBSCAN* on several real-world datasets, demonstrating that it achieves a higher median ARI, is less sensitive to changes in the number of mutual reachability neighbours, and has higher stability under resampling. Additionally, we compare PLSCAN's computational costs to $k$-Means++, demonstrating competitive run-times on low-dimensional datasets. At higher dimensions, run times scale more similarly to HDBSCAN*.

Recovering the underlying $k$-clustering of a set $U$ of $n$ points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query $S \subset U$, $|S|=2$, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be $Θ(nk)$, while non-adaptive algorithms are extremely limited: even for $k=3$, such algorithms require $Ω(n^2)$ queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for $|S|>2$, where the oracle returns the number of clusters intersecting $S$. Previous work obtained an $O(n)$ query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making $O(n \log k \cdot (\log k + \log\log n)^2)$ queries, improving to $O(n \log \log n)$ when $k$ is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound, $s$, on the query size. We show $Ω(\max(n^2/s^2,n))$ queries are necessary and obtain algorithms making $\smash{\widetilde{O}(n^2k/s^2)}$ queries for any $s \leq \sqrt{n}$ and $\smash{\widetilde{O}(n^2/s)}$ queries for any $s \leq n$. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.