Constrained Hierarchical Clustering via Graph Coarsening and Optimal
  Cuts
Eliabelle Mauduit Andrea Simonetto
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.