Hierarchical Clustering for Euclidean Data

Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev

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 measures. In this paper we take the first step and give novel scalable algorithms for this problem tailored to Euclidean data in $R^d$ and under vector-based similarity measures, a prevalent model in several typical machine learning applications. We focus primarily on the popular Gaussian kernel and other related measures, presenting our results through the lens of the objective introduced recently by Moseley and Wang [2017]. We show that the approximation factor in Moseley and Wang [2017] can be improved for Euclidean data. We further demonstrate both theoretically and experimentally that our algorithms scale to very high dimension $d$, while outperforming average-linkage and showing competitive results against other less scalable approaches.

Introduction

Hierarchical clustering (HC) is a cornerstone of exploratory data analysis, yet theoretical advancements have often treated it as a generic graph problem, ignoring the underlying geometry of the data. This paper, presented by researchers from Stanford and Indiana University, shifts the focus toward Euclidean data—where points are vectors in $\mathbb{R}^d$. By exploiting the geometric properties of Euclidean space, the authors develop algorithms that are both faster and theoretically superior to general-purpose methods.

The $F^+$ Objective and the 1/3 Barrier

A significant challenge in HC has been the lack of a formal objective function to evaluate the quality of a hierarchy. This work utilizes the $F^+$ objective, which measures the quality of a tree by rewarding hierarchies that keep similar pairs of points together as long as possible before they are partitioned into separate clusters.

For arbitrary similarity measures, the best known algorithms only achieve a 1/3-approximation of the optimal tree. Furthermore, traditional agglomerative methods like Average-Linkage (AL) suffer from $O(n^2)$ computational complexity, making them impractical for modern large-scale datasets. This paper addresses both the theoretical "1/3-approximation barrier" and the computational bottleneck by leveraging the structure of Euclidean data.

The Projected Random Cut (PRC) Algorithm

The authors propose a top-down, divisive approach called Projected Random Cut (PRC). The algorithm operates in two main stages:

  1. 1D Random Cut (RC): For data points distributed along a single line, the algorithm selects a random point within the data's range and splits the set into two. This process is repeated recursively. In the 1D case, this simple strategy is proven to achieve a 1/2-approximation.
  2. High-Dimensional Projection: To handle high-dimensional vectors, PRC first projects all points onto a single, randomly chosen Gaussian vector. This reduces the complex $d$-dimensional problem into the more manageable 1D case while preserving enough geometric structure to maintain high-quality clustering.
Illustration of cluster partitioning on a 1D line, showing how proximity (like between A and B) influences the similarity weight $w_{AB}$.

Key Insights and Results

Breaking the Approximation Barrier

The study focuses on the Gaussian kernel similarity, a standard measure in machine learning. The authors prove that PRC provides a constant improvement over the general 1/3-approximation, specifically achieving a factor of $(1+\delta)/3$, where $\delta$ depends on the kernel's bandwidth. This demonstrates that geometry is a powerful "cheat code" for improving theoretical bounds.

Scalability to Millions of Points

Because PRC relies on 1D projections and sorting, its complexity is $O(n(d + \log n))$. This efficiency was demonstrated on the SIFT10M dataset, containing 10 million 128-dimensional vectors. PRC processed the entire dataset in approximately 26 minutes on standard consumer hardware—a task that would be computationally infeasible for methods requiring the full similarity matrix.

Empirical Quality

On smaller benchmarks like the Zoo dataset, PRC achieved approximation factors between 0.73 and 0.92 relative to the upper bound. It consistently outperformed Average-Linkage in quality while remaining significantly more scalable.

Conclusion and Future Directions

By tailoring hierarchical clustering to the Euclidean setting, the authors have provided a scalable and theoretically grounded alternative to traditional methods. The success of 1D projections suggests that future work exploring projections onto low-dimensional subspaces (e.g., 2D or 3D) could yield even tighter approximation ratios. Additionally, the conjecture that Average-Linkage might achieve a 3/4-approximation in 1D remains an intriguing open question for the field.

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 measures. In this paper we take the first step and give novel scalable algorithms for this problem tailored to Euclidean data in R^d and under vector-based similarity measures, a prevalent model in several typical machine learning applications. We focus primarily on the popular Gaussian kernel and other related measures, presenting our results through the lens of the objective introduced recently by Moseley and Wang [2017]. We show that the approximation factor in Moseley and Wang [2017] can be improved for Euclidean data. We further demonstrate both theoretically and experimentally that our algorithms scale to very high dimension d, while outperforming average-linkage and showing competitive results against other less scalable approaches.
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