Hierarchical Clustering for Euclidean Data

Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev

Abstract

Recent work in Hierarchical Clustering (HC) has focused on optimizing objective functions like $\mathcal{F}^+$ for arbitrary similarity graphs. However, most real-world data is Euclidean, possessing geometric structures that general-purpose algorithms fail to exploit. This paper introduces the Projected Random Cut (PRC) algorithm, which leverages Euclidean geometry to achieve approximation guarantees that surpass the $1/3$ worst-case bound of standard methods. PRC operates in near-linear time, enabling high-quality hierarchical clustering on massive datasets with millions of points.

Introduction

Hierarchical clustering is a cornerstone of exploratory data analysis, yet it was long evaluated purely through heuristics. Recent formalizations use the $\mathcal{F}^+$ objective, which rewards trees that keep similar points together deeper in the hierarchy. For arbitrary similarity matrices, the popular Average-Linkage algorithm provides a $1/3$-approximation, a bound that is theoretically difficult to beat in the general case.

This paper asks whether we can do better by assuming data lives in Euclidean space ($\mathbb{R}^d$) with similarities defined by kernels like the Gaussian kernel. The authors prove that geometry indeed allows for better approximations and significantly faster algorithms.

The Projected Random Cut (PRC) Algorithm

The authors propose a randomized approach designed for high-dimensional efficiency. The PRC algorithm works as follows:

  1. Projection: Pick a random Gaussian vector and project all $d$-dimensional points onto this 1D line.
  2. Random Cut: In 1D, choose a split point uniformly at random within the range of the data to divide points into left and right subtrees.
  3. Recursion: Repeat the process recursively to build the full hierarchical tree.

This method is a computational breakthrough. Traditional agglomerative methods like Average-Linkage require $O(dn^2)$ time and $O(n^2)$ memory to compute and store a similarity matrix. In contrast, PRC requires only $O(n(d + \log n))$ time and $O(n)$ memory, effectively scaling to the size of the raw data.

Empirical Performance and Scalability

Approximation Quality

On the Zoo dataset (UCI ML), PRC was compared against Average-Linkage (AL) and Spectral Clustering. As shown in the table below, PRC consistently achieves approximation ratios between $0.74$ and $0.92$, significantly outperforming AL across various kernel bandwidths ($\sigma$).

Approximation ratios on the Zoo dataset across varying kernel bandwidths (sigma).

Large-Scale Efficiency

To test scalability, the authors used the SIFT10M dataset, containing 10 million 128-dimensional vectors. PRC clustered the entire dataset in approximately 26 minutes on a standard laptop. Its runtime scales almost perfectly linearly, tracking closely with the time required for a single pass over the data.

Runtime scalability of PRC compared to a single data pass on massive datasets.

Key Insights

  • Geometry Beats Arbitrary Graphs: By assuming Euclidean structure, PRC breaks the $1/3$ approximation barrier that limits general similarity graph algorithms.
  • Average-Linkage Limitations: The authors prove that Average-Linkage cannot beat the $1/3$ factor in high dimensions, even for Euclidean data, making PRC a superior choice for high-dimensional tasks.
  • Simplicity Scales: Projecting onto a single random 1D line preserves enough structural integrity to build highly competitive trees in a fraction of the time required by traditional methods.

Conclusion

This work demonstrates that exploiting the geometric nature of data leads to both better theoretical guarantees and practical, high-performance algorithms. PRC offers a scalable solution for hierarchical clustering that is both faster and more accurate than traditional heuristics on Euclidean data. Future research may investigate whether projecting onto low-dimensional subspaces (e.g., 2D or 3D) can further improve approximation ratios without sacrificing linear-time performance.

Summary updated

Abstract

Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arbitrary similarity...
BibTeX
@inproceedings{charikar2019hierarchical,
  author = {Moses Charikar and Vaggos Chatziafratis and Rad Niazadeh and Grigory Yaroslavtsev},
  title = {{Hierarchical Clustering for Euclidean Data}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=FLffJVrXiXj},
}
Figure