Fast adaptively balanced min-cut clustering

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.