Fast Clustering by Directly Solving Bipartite Graph Clustering Problem

Spectral clustering (SC) has been widely used in many applications and shows excellent performance. Its high computational cost limits its applications; many strategies including the anchor technique can partly alleviate the high computational cost problem. However, early methods ignore the fact that SC usually involves two stages: relaxation and postprocessing, i.e., it relaxes the discrete constraints to continuous constraints, and then conducts the postprocessing to get the discrete solution, which is time-consuming and deviates from directly solving the primal problem. In this article, we first adopt the bipartite graph strategy to reduce the time complexity of SC, and then an improved coordinate descent (CD) method is proposed to solve the primal problem directly without singular value decomposition (SVD) and postprocessing, i.e., directly solving the primal problem not approximately solving. Experiments on various real-world benchmark datasets show that the proposed method can get better solutions faster with better clustering performance than traditional optimization methods. Furthermore, it can jump out of local minima of traditional methods and continue to obtain better local solutions. Moreover, compared with other clustering methods, it also shows its superiority.