Approximation Scheme for Weighted Metric Clustering via Sherali-Adams

Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory YaroslavtsevAAAI 2024 · OpenReview

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.

  1. Relaxation: The hierarchy generates local probability distributions for small subsets of points, ensuring local consistency across the dataset.
  2. 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.
  3. Two-Stage Rounding:
    • Primary Assignment: Most points are assigned to clusters via independent rounding based on the processed LP values.
  4. 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).

Comparison of Depth-HC and Dasgupta objectives in terms of dendrogram purity and running time across different subsample sizes.

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

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 x k symmetric matrix A with non-negative entries, the goal is to find a k-partition of these points into clusters C1,...,Ck, while minimizing the sum of A[i,j] * d(u,v) over all pairs of clusters Ci and Cj and all pairs of points u from Ci and v from Cj. 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.
BibTeX
@inproceedings{avdiukhin2024approximation,
  author = {Dmitrii Avdiukhin and Vaggos Chatziafratis and Konstantin Makarychev and Grigory Yaroslavtsev},
  title = {{Approximation Scheme for Weighted Metric Clustering via Sherali-Adams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=iRg1qpQlv6},
}
Figure