Sublinear Algorithms for Estimating Single-Linkage Clustering Costs

Abstract

Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a $k$-clustering produced by SLC can be obtained by computing a minimum spanning tree (MST) and deleting its $k-1$ heaviest edges. This naturally induces a cost profile for the SLC hierarchy: for each $k\in [n]$, we define ${\mathrm{cost}}_k$ to be the weight of the resulting $k$-component spanning forest, equivalently, the minimum total weight of any spanning forest with exactly $k$ connected components. The corresponding \emph{SLC cost profile} is $({\mathrm{cost}}_1,\dots ,{\mathrm{cost}}_n)$, and the scalar quantity $\mathrm{cost}(G)={\sum }_{k=1}^n{\mathrm{cost}}_k$ is the area under this profile. We study the problem of approximating these quantities in sublinear time. We assume that the input is a weighted graph $G$ of average degree $d$ with edge weights in $\{1,\dots ,W\}$, accessed through adjacency-list queries; missing edges are treated as having infinite distance. Our main result is a sampling-based algorithm that outputs a succinct sketch of the entire SLC cost profile in the distance setting. The algorithm runs in $\tilde{O}(d\sqrt{W}/{\epsilon }^3)$ time and returns a sketch from which one can derive estimates $({\widehat{\mathrm{cost}}}_1,\dots ,{\widehat{\mathrm{cost}}}_n)$ satisfying ${\sum }_{k=1}^n|{\widehat{\mathrm{cost}}}_k-{\mathrm{cost}}_k|\le \epsilon \mathrm{cost}(G)$. Thus, we obtain an ${\ell }_1$ approximation to the full profile whose error is at most an $\epsilon$-fraction of the area under the true profile. In particular, this yields a $(1\pm \epsilon )$-approximation to $\mathrm{cost}(G)$ within the same running time. We also prove a nearly matching lower bound of $\Omega (d\sqrt{W}/{\epsilon }^2)$ queries for estimating $\mathrm{cost}(G)$.

arXiv commentAccepted by ESA 2026