Harmonic cut: An efficient and directly solved balanced graph clustering

Yu Duan, Feiping Nie, Rong Wang, Xuelong Li

科研成果: 期刊稿件文章同行评审

3 引用 (Scopus)

摘要

In recent years, balanced clustering has garnered significant attention within its research domain. Previous studies have often employed various regularization terms to achieve balanced clustering. However, they inevitably bring extra hyper-parameters and suffer from high computational complexity. In this paper, we propose an efficient balanced graph cut model called Harmonic Cut. Harmonic cut is inspired by two key factors: harmonic mean and anchors’ labels are instances’ labels. The former elegantly derives a balance constraint. And the latter efficiently provides an idea for obtaining clustering labels. Unlike conventional spectral clustering methods, Harmonic cut directly acquires all cluster assignments, eliminating the need for additional k-means steps and significantly enhancing efficiency. We tackle the optimization problem associated with the Harmonic cut model using an efficient and heuristic algorithm, whose computational complexity scales linearly with the data size, denoted as n. Finally, extensive experiments conducted on various real-world datasets demonstrate that Harmonic cut not only achieves comparable or even superior results, but also ensures both balance and efficiency. The code is available at https://github.com/DuannYu/HarmonicCut.

源语言英语
文章编号127381
期刊Neurocomputing
578
DOI
出版状态已出版 - 14 4月 2024

指纹

探究 'Harmonic cut: An efficient and directly solved balanced graph clustering' 的科研主题。它们共同构成独一无二的指纹。

引用此