A (1+?)-Approximation for Ultrametric Embedding in Subquadratic Time

Gabriel Bathie, Guillaume LagardeAAAI 2025 · DOI

Introduction

Hierarchical clustering is a fundamental tool in data analysis, allowing researchers to represent complex datasets as tree-like structures known as dendrograms. Mathematically, these structures are formalized as ultrametrics. A central challenge in this field is the "best ultrametric fit" ($BUF_\infty$) problem, which seeks an ultrametric that minimizes the maximum distortion of original pairwise distances.

Historically, solving $BUF_\infty$ exactly has been constrained by a "quadratic barrier," requiring $O(n^2)$ time. While recent advancements achieved subquadratic runtimes, they were limited to coarse approximations (e.g., factors around 4.90). This research introduces FASTULT, the first subquadratic-time algorithm capable of achieving arbitrarily precise $(1 + \epsilon)$-approximations.

Methodology

The FASTULT framework overcomes traditional geometric bottlenecks through two primary innovations:

  1. LSH-Guided Tree Construction: Previous subquadratic attempts relied on spanners (sparse graphs preserving distances), which are computationally expensive to build for high-precision requirements. FASTULT instead utilizes Locality-Sensitive Hashing (LSH) and a breadth-first traversal to construct a $\gamma$-Kruskal Tree ($\gamma$-KT) directly, decoupling the tree structure from spanner limitations.
  2. Dynamic Approximate Farthest Neighbor (AFN): To assign weights to the tree edges (cut weights), the authors developed a dynamic data structure that treats the task as a series of farthest-neighbor queries. By employing a "smallest-to-largest" query trick—iterating over the smaller cluster to query the larger one during merges—the algorithm maintains a total query count of $O(n \log n)$.

Combined, these techniques allow for a $c$-approximation in $\tilde{O}(n^{1+1/c})$ time, providing a continuous trade-off between computational speed and approximation accuracy.

Experimental Evaluation

The authors evaluated FASTULT using diverse real-world benchmarks (IRIS, DIABETES, MICE, PENDIGITS, and SHUTTLE) and large-scale synthetic datasets containing up to one million points in 10 to 100 dimensions.

Key Results: Accuracy and Scalability

Experiments demonstrate that FASTULT significantly outperforms existing subquadratic methods in precision while maintaining massive scalability. On real-world datasets, FASTULT (with $c=4$) consistently achieved lower distortion than the previous state-of-the-art subquadratic algorithm, CVL, often approaching the optimal exact solution (FKW).

Performance comparison of FASTULT against exact (FKW) and previous subquadratic (CVL) methods on real-world datasets.

In terms of scalability, the algorithm's performance is even more pronounced. While traditional Single Linkage clustering failed to process a dataset of one million points within a 10-hour limit, FASTULT (with $c=16$) completed the task in approximately 2.5 minutes.

Scalability of FASTULT on large-scale synthetic datasets compared to Single Linkage.

Limitations and Future Work

While FASTULT represents a theoretical and practical breakthrough, its runtime is partially dependent on the "spread" of the dataset (the ratio between maximum and minimum distances). Extremely stretched datasets may see performance impacts. Additionally, the algorithm is randomized, though it maintains mathematically bounded failure probabilities. Future research may focus on extending these high-precision subquadratic results to non-Euclidean metric spaces, such as Manhattan distance or Cosine similarity.

Reference: Bathie, G., & Lagarde, G. (2025). A (1 + ϵ)-Approximation for Ultrametric Embedding in Subquadratic Time. Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI-25).

Summary updated

BibTeX
@inproceedings{bathie2025approximation,
  author = {Gabriel Bathie and Guillaume Lagarde},
  title = {{A (1+?)-Approximation for Ultrametric Embedding in Subquadratic Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i15.33703},
}
Figure