Fast linkage algorithm for $k$-medians hierarchical clustering

Hierarchical linkage methods are widely used due to their simplicity, interpretability, and ability to produce full clusterings across all values of $k$. The $k$-medians objective is a fundamental measure of cluster compactness, capturing average distances to representative points. Despite its importance, existing hierarchical linkage methods that align with this objective are either computationally expensive or lack scalability. We introduce two simple hierarchical linkage algorithms, r-msi and f-msi, which, to the best of our knowledge, are the first linkage methods aligned with the $k$-medians objective to achieve subcubic time complexity. Our methods can be seen as efficient variations of msi, a linkage method that runs in cubic time. r-msi runs in $O(n^2\log n)$ time while f-msi runs in $O(n^2)$ time and produces inversion-free dendrograms. Notably, f-msi admits an implementation for datasets represented as weighted graphs that runs in $O((m+n\sqrt{m})\log m)$ time, where $n$ and $m$ are the number of vertices and edges of the graph, as well as a subquadratic-time implementation in which the merge rule is $\gamma$-approximated. Experiments on several datasets from different domains show that our algorithms present strong empirical performance, achieving clustering quality close to msi while being up to 75 times faster. Moreover, f-msi scales to graph datasets with over $10^7$ edges.