# An objective function for order preserving hierarchical clustering

arXiv: https://arxiv.org/abs/2109.04266 · HTML: https://mlsanity.com/paper/2109.04266/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 40 references that are in the map.
- First posted on arXiv 9 Sep 2021.

## Builds on (most cited first, 8 of 8)

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [The Impact of Random Models on Clustering Similarity](https://mlsanity.com/paper/1701.06508/) (2017)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Foundations of Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/1811.00928/) (2018)
- [Hierarchical Quasi-Clustering Methods for Asymmetric Networks](https://mlsanity.com/paper/1404.4655/) (2014)
- [Order preserving hierarchical agglomerative clustering](https://mlsanity.com/paper/2004.12488/) (2020)

## Abstract (arXiv)

We present a theory and an objective function for similarity-based hierarchical clustering of probabilistic partial orders and directed acyclic graphs (DAGs). Specifically, given elements x ≤ y in the partial order, and their respective clusters [x] and [y], the theory yields an order relation ≤' on the clusters such that [x]≤'[y]. The theory provides a concise definition of order-preserving hierarchical clustering, and offers a classification theorem identifying the order-preserving trees (dendrograms). To determine the optimal order-preserving trees, we develop an objective function that frames the problem as a bi-objective optimisation, aiming to satisfy both the order relation and the similarity measure. We prove that the optimal trees under the objective are both order-preserving and exhibit high-quality hierarchical clustering. Since finding an optimal solution is NP-hard, we introduce a polynomial-time approximation algorithm and demonstrate that the method outperforms existing methods for order-preserving hierarchical clustering by a significant margin.