Abstract
Motivated by applications to classification problems on metric data, we study Weighted Metric Clustering problem: given a metric $d$ over $n$ points and a $k \times k$ symmetric matrix $A$ with non-negative entries, the goal is to find a $k$-partition of these points into clusters $C_1, \dots, C_k$, while minimizing the sum of $A_{i,j} \cdot d(u,v)$ over all pairs of clusters $C_i$ and $C_j$ and all pairs of points $u \in C_i$ and $v \in C_j$. Specific choices of $A$ lead to Weighted Metric Clustering capturing well-studied graph partitioning problems in metric spaces, such as Min-Uncut, Min-k-Sum, Min-k-Cut, and more. Our main result is that Weighted Metric Clustering admits a polynomial-time approximation scheme (PTAS). Our algorithm handles all the above problems using the Sherali-Adams linear programming relaxation. This subsumes several prior works, unifies many of the techniques for various metric clustering objectives, and yields a PTAS for several new problems, including metric clustering on manifolds and a new family of hierarchical clustering objectives. Our experiments on the hierarchical clustering objective show that it better captures the ground-truth structural information compared to the popular Dasgupta's objective.
Introduction
Clustering is a fundamental task in data science, yet different applications require distinct optimization objectives. The Weighted Metric Clustering (WMC) framework provides a unified approach to these varied goals. Given $n$ points in a metric space and a target number of clusters $k$, the objective is defined by a $k \times k$ cost matrix $A$. For any two points $u$ and $v$ assigned to clusters $i$ and $j$ respectively, a penalty of $A_{ij} \cdot \text{dist}(u, v)$ is incurred.
This formulation is remarkably versatile. By adjusting the matrix $A$, one can recover classic problems:
- Min-k-Sum: Minimizing intra-cluster distances.
- Multiway Cut: Minimizing inter-cluster distances.
- Manifold Clustering: Capturing specific topologies like rings or chains.
While maximization variants are well-understood, minimization in metric spaces is challenging. This work demonstrates that the triangle inequality is a critical property that enables the development of a Polynomial-Time Approximation Scheme (PTAS) for WMC when $k$ is fixed.
Algorithmic Framework: Sherali-Adams Hierarchy
The core of the proposed PTAS is the Sherali-Adams linear programming hierarchy, a "lift-and-project" method that enhances standard LP relaxations.
- Relaxation: The hierarchy generates local probability distributions for small subsets of points, ensuring local consistency across the dataset.
- MakeIndependent Procedure: To handle potential correlations between these local distributions, the authors employ a randomized conditioning technique. This transforms the LP solution into a set of "nearly independent" distributions.
- Two-Stage Rounding:
- Primary Assignment: Most points are assigned to clusters via independent rounding based on the processed LP values.
- Outlier Handling: Points that remain poorly assigned are treated as outliers. Given their small number, a simpler 3-approximation algorithm can assign them without compromising the overall $(1+\epsilon)$ guarantee.
Hierarchical Clustering and Depth-HC
The authors extend this framework to hierarchical clustering by introducing a new objective: Depth-HC. Unlike the widely used Dasgupta’s objective, which penalizes pairs based on the number of leaves in their shared subtree, Depth-HC penalizes based on the depth of their Lowest Common Ancestor (LCA). This shift reflects the intuition that early splits in a hierarchy are more significant than the eventual size of the subtrees.
Experimental Evaluation
The Depth-HC objective was evaluated against Dasgupta’s objective using real-world datasets including 20 NEWSGROUPS (text), ZEBRAFISH (gene expression), and CIFAR-10 (images).
As shown in the figure above, Depth-HC consistently outperforms Dasgupta’s objective in terms of Dendrogram Purity, a metric measuring alignment with ground-truth labels. On the 20 Newsgroups dataset, the purity achieved by Depth-HC was nearly double that of the benchmark. While the full PTAS is computationally intensive, a practical implementation using a simplified LP relaxation ($LP_{II}$) and local search proved scalable for datasets up to 10,000 points.
Conclusion
This research provides a powerful theoretical unification for metric clustering problems. By leveraging the Sherali-Adams hierarchy, the authors establish the existence of a PTAS for a broad class of objectives. Furthermore, the introduction of the Depth-HC objective demonstrates that theoretical insights into metric structures can lead to significant practical improvements in recovering hierarchical data relationships. Future work remains in optimizing the computational overhead of the Sherali-Adams rounds and extending the framework to scenarios where $k$ scales with $n$.
Summary updated