# Hierarchical Clustering with Structural Constraints

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2018.

## Built on by (most cited first, 15 of 15)

- [A Framework for Deep Constrained Clustering](https://mlsanity.com/paper/2101.02792/) (2021)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds](https://mlsanity.com/paper/2211.03674/) (2022)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Exact and Approximate Hierarchical Clustering Using A*](https://mlsanity.com/paper/2104.07061/) (2021)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [Tree Learning: Optimal Algorithms and Sample Complexity](https://mlsanity.com/paper/2302.04492/) (2023)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [An objective function for order preserving hierarchical clustering](https://mlsanity.com/paper/2109.04266/) (2021)
- [Expanding the class of global objective functions for dissimilarity-based hierarchical clustering](https://mlsanity.com/paper/2207.14375/) (2022)
- [Constrained Hierarchical Clustering via Graph Coarsening and Optimal Cuts](https://mlsanity.com/paper/2312.04209/) (2023)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)

## Abstract (arXiv)

Hierarchical clustering is a popular unsupervised data analysis method. For many real-world applications, we would like to exploit prior information about the data that imposes constraints on the clustering hierarchy, and is not captured by the set of features available to the algorithm. This gives rise to the problem of "hierarchical clustering with structural constraints". Structural constraints pose major challenges for bottom-up approaches like average/single linkage and even though they can be naturally incorporated into top-down divisive algorithms, no formal guarantees exist on the quality of their output. In this paper, we provide provable approximation guarantees for two simple top-down algorithms, using a recently introduced optimization viewpoint of hierarchical clustering with pairwise similarity information [Dasgupta, 2016]. We show how to find good solutions even in the presence of conflicting prior information, by formulating a constraint-based regularization of the objective. We further explore a variation of this objective for dissimilarity information [Cohen-Addad et al., 2018] and improve upon current techniques. Finally, we demonstrate our approach on a real dataset for the taxonomy application.