# Constrained Hierarchical Clustering via Graph Coarsening and Optimal Cuts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 7 Dec 2023.

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

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Semi-supervised clustering methods](https://mlsanity.com/paper/1307.0252/) (2013)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Hierarchical Clustering of Asymmetric Networks](https://mlsanity.com/paper/1607.06294/) (2016)
- [A novel brain partition highlights the modular skeleton shared by structure and function](https://mlsanity.com/paper/1410.7959/) (2014)
- [Order preserving hierarchical agglomerative clustering](https://mlsanity.com/paper/2004.12488/) (2020)
- [Hierarchical Clustering Given Confidence Intervals of Metric Distances](https://mlsanity.com/paper/1610.04274/) (2016)

## Abstract (arXiv)

Motivated by extracting and summarizing relevant information in short sentence settings, such as satisfaction questionnaires, hotel reviews, and X/Twitter, we study the problem of clustering words in a hierarchical fashion. In particular, we focus on the problem of clustering with horizontal and vertical structural constraints. Horizontal constraints are typically cannot-link and must-link among words, while vertical constraints are precedence constraints among cluster levels. We overcome state-of-the-art bottlenecks by formulating the problem in two steps: first, as a soft-constrained regularized least-squares which guides the result of a sequential graph coarsening algorithm towards the horizontal feasible set. Then, flat clusters are extracted from the resulting hierarchical tree by computing optimal cut heights based on the available constraints. We show that the resulting approach compares very well with respect to existing algorithms and is computationally light.