Constrained Hierarchical Clustering via Graph Coarsening and Optimal Cuts
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSentenceMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transport
Hierarchical abstractions are a methodology for solving large-scale graph problems in various disciplines. Coarsening is one such approach: it generates a pyramid of graphs whereby the one in the next level is a structur…
Graph ClassificationGromov-Wasserstein Graph Coarsening
We study the problem of graph coarsening within the Gromov-Wasserstein geometry. Specifically, we propose two algorithms that leverage a novel representation of the distortion induced by merging pairs of nodes. The first…
PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms
Clustering the nodes of a graph is a cornerstone of graph analysis and has been extensively studied. However, some popular methods are not suitable for very large graphs: e.g., spectral clustering requires the computatio…
ClusteringComputational EfficiencyGraph ClusteringHierarchical Sparse Circuit Extraction from Billion-Parameter Language Models through Scalable Attribution Graph Decomposition
Extracting sparse circuits from billion-parameter transformers is constrained by $O(2^n)$ search cost and pervasive feature reuse across co-active pathways. Hierarchical Attribution Graph Decomposition (HAGD) addresses t…
Coreference ResolutionHyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
Hypergraphs allow modeling problems with multi-way high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To addre…
Clusteringhypergraph partitioning