Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

Steinar Laenen, Bogdan-Adrian Manghiuc, He Sun
6/16/2023
cs.DScs.LG

No confident code implementation found for this paper. 2 possible matches can be shown below.

Abstract

This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function. For any input graph $G$ with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of $G$, and return an $O(1)$-approximate HC tree with respect to Dasgupta's cost function. We compare the performance of our algorithm against the previous state-of-the-art on synthetic and real-world datasets and show that our designed algorithm produces comparable or better HC trees with much lower running time.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 2 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Ultrametric Cluster Hierarchies: I Want 'em All!

86% match2025

Hierarchical Clustering via Local Search

83% match2024

Average Sensitivity of Hierarchical k-Median Clustering

81% match2025

Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees

80% match2023

High-Performance Hybrid Algorithm for Minimum Sum-of-Squares Clustering of Infinitely Tall Data

80% match1 repo2023

Graph Probability Aggregation Clustering

79% match2025

Cite this paper

@article{laenen2023nearlyoptimal,
  title  = {Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs},
  author = {Steinar Laenen and Bogdan-Adrian Manghiuc and He Sun},
  year   = {2023},
  eprint = {2306.09950},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.09950v1},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.09950.svg)](https://codeofpaper.com/paper/2306.09950)

Discussion