Fast adaptively balanced min-cut clustering

Feiping Nie, Fangyuan Xie, Jingyu Wang, Xuelong Li

Research output: Contribution to journalArticlepeer-review

Abstract

Min-cut clustering is a typical graph clustering method, which has been extensively applied for pattern recognition, data analysis and image processing. However, min-cut has trivial solutions, which leads to skewed clustering performance. Spectral clustering (SC) alleviates this by relaxing indicator matrix into continuous embedding and then discretizes the embedding. However, there are two primary challenges in SC, which are high computational complexity and two-stage process. To resolve these issues, a fast adaptively balanced min-cut clustering model (FBMC) is proposed, which directly solves the discrete indicator matrix without any post-processing. We utilize the bipartite graph to accelerate the construction of affinity graph and process of optimization. Besides, the balance factors are added in the model, which could alleviate skewed clustering results. Two specific methods are proposed, in which one adds a balance factor to all clusters while the other assigns balance factors to each cluster separately, referred to as FBMC1 and FBMC2. What is more, a one-step optimization is proposed to solve FBMC1 and FBMC2, the complexity of which is linear of time. Finally, comprehensive experiments results highlight the superior performance of our proposed method.

Original languageEnglish
Article number111027
JournalPattern Recognition
Volume158
DOIs
StatePublished - Feb 2025

Keywords

  • Balanced min-cut clustering
  • Bipartite graph
  • Coordinate descent method
  • Fast clustering

Fingerprint

Dive into the research topics of 'Fast adaptively balanced min-cut clustering'. Together they form a unique fingerprint.

Cite this