Approximate hierarchical clustering via sparsest cut and spreading metrics

DOI10.1137/1.9781611974782.53zbMATH Open1409.68328arXiv1609.09548OpenAlexW2529851164MaRDI QIDQ4575792FDOQ4575792

Authors: Vaggos Chatziafratis, Moses Charikar 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Dasgupta recently introduced a cost function for the hierarchical clustering of a set of points given pairwise similarities between them. He showed that this function is NP-hard to optimize, but a top-down recursive partitioning heuristic based on an alpha_n-approximation algorithm for uniform sparsest cut gives an approximation of O(alpha_n log n) (the current best algorithm has alpha_n=O(sqrt{log n})). We show that the aforementioned sparsest cut heuristic in fact obtains an O(alpha_n)-approximation for hierarchical clustering. The algorithm also applies to a generalized cost function studied by Dasgupta. Moreover, we obtain a strong inapproximability result, showing that the hierarchical clustering objective is hard to approximate to within any constant factor assuming the Small-Set Expansion (SSE) Hypothesis. Finally, we discuss approximation algorithms based on convex relaxations. We present a spreading metric SDP relaxation for the problem and show that it has integrality gap at most O(sqrt{log n}). The advantage of the SDP relative to the sparsest cut heuristic is that it provides an explicit lower bound on the optimal solution and could potentially yield an even better approximation for hierarchical clustering. In fact our analysis of this SDP served as the inspiration for our improved analysis of the sparsest cut heuristic. We also show that a spreading metric LP relaxation gives an O(log n)-approximation.

Full work available at URL: https://arxiv.org/abs/1609.09548

Recommendations

• Hierarchical clustering via spreading metrics
• scientific article; zbMATH DE number 2089373
• Performance guarantees for hierarchical clustering
• Approximation algorithms for hierarchical location problems
• Hierarchical clustering: objective functions and algorithms

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (11)

• Title not available (Why is that?)
• Hierarchical clustering via spreading metrics
• A two-level graph partitioning problem arising in mobile wireless communications
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• Ultrametric fitting by gradient descent ^*
• On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
• Optimal hierarchical clustering on a graph
• Expanding the class of global objective functions for dissimilarity-based hierarchical clustering
• Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints
• Fitting metrics and ultrametrics with minimum disagreements
• Title not available (Why is that?)

This page was built for publication: Approximate hierarchical clustering via sparsest cut and spreading metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575792)