Hierarchical Clustering: a 0.585 Revenue Approximation

Noga Alon, Yossi Azar, Danny Vainstein

Introduction

Hierarchical clustering (HC) is a fundamental tool in data science, organizing data into a nested sequence of partitions represented as a tree structure. While heuristic methods like average linkage are widely used in practice, theoretical computer science seeks to establish mathematical guarantees for these algorithms. In 2016, Sanjoy Dasgupta introduced a formal cost function for HC, which was followed by the "Revenue" objective proposed by Moseley and Wang. This paper advances the state-of-the-art for revenue approximation, significantly improving the guarantee from 0.4246 to 0.585.

The Revenue Objective

In the revenue model, the goal is to maximize the similarity of points that remain in the same cluster for as long as possible as one moves down the tree. For any two points $i$ and $j$ with a similarity weight $w_{ij}$, the revenue contributed is proportional to the size of the subtree rooted at their least common ancestor (LCA). Specifically, if $T_{ij}$ is the subtree containing both $i$ and $j$ before they are split into different branches, the objective is to maximize $\sum_{i,j} w_{ij} |T_{ij}|$. This encourages keeping highly similar points together in large subtrees throughout the hierarchy.

The "Bisect-then-Randomize" Strategy

The authors propose a two-step algorithm that balances complex combinatorial optimization with intentional simplicity:

  1. Max-Uncut Bisection (MUB): The first cut of the tree is determined by solving the MUB problem. This seeks to partition the dataset into two equal halves while maximizing the weight of edges that remain inside the two halves. This step utilizes a semidefinite programming approach known to yield an 0.8776 approximation for MUB.
  2. Random Splitting: For every subsequent split in the tree, the algorithm simply partitions the remaining data points randomly.

Theoretical Insights: The Line Embedding Trick

A core contribution of this work is the proof that a single, well-chosen bisection can capture at least 50% of the total revenue of an optimal, infinitely deep tree. To prove this, the authors employ a "Line Embedding Trick," where they embed the leaves of an optimal tree onto a 1D line such that no edges cross.

Figure 1: An illustration of the tree structure and leaf ordering used in the line embedding proof technique.

By ensuring no edges cross in this embedding, the researchers create a way to relate the distance between points on the line to the size of the subtrees in the hierarchical structure. They show that a random cut on this line performs surprisingly well, capturing at least half of the optimal revenue. This existence proof, combined with the MUB approximation, leads to the final 0.585 ratio (derived from the formula $\frac{2}{3} \times 0.8776$).

Key Results and Implications

  • New State-of-the-Art: The paper establishes a 0.585 approximation ratio, a major improvement over the previous best of 0.4246.
  • The Power of the First Cut: The most surprising insight is that the "first cut" is the most critical decision. A single bisection can do 50% of the work of an optimal tree that might have hundreds of levels.
  • Computational Efficiency: Because the algorithm only requires solving one difficult optimization problem (the first bisection) and then uses randomization, it is more computationally efficient than methods requiring complex optimization at every level of the tree.

Conclusion

This research demonstrates that simple strategies can be remarkably effective for complex hierarchical clustering problems. While the 0.585 figure is currently tied to the best-known approximation for Max-Uncut Bisection, the underlying proof techniques provide a new foundation for future improvements. Whether more sophisticated strategies for lower levels of the tree can further improve this bound remains an open and intriguing question for the field.

Summary updated

BibTeX
@inproceedings{alon2020hierarchical,
  author = {Noga Alon and Yossi Azar and Danny Vainstein},
  title = {{Hierarchical Clustering: a 0.585 Revenue Approximation}},
  booktitle = {Conference on Learning Theory},
  year = {2020},
}
Figure