Fast Clustering by Directly Solving Bipartite Graph Clustering Problem.

Area of Science:

• Data Science
• Machine Learning
• Computational Science

Background:

• Spectral clustering (SC) is a powerful technique for data analysis but suffers from high computational costs.
• Existing methods often involve time-consuming relaxation and postprocessing stages, deviating from direct problem-solving.

Purpose of the Study:

• To develop a computationally efficient spectral clustering algorithm.
• To directly solve the primal problem of SC without approximation.
• To enhance clustering performance and escape local minima.

Main Methods:

• Utilized a bipartite graph strategy to reduce the time complexity of spectral clustering.
• Proposed an improved coordinate descent (CD) method for direct primal problem optimization.
• Avoided singular value decomposition (SVD) and postprocessing steps.

Main Results:

• The proposed method significantly reduces computational time compared to traditional optimization methods.
• Achieved superior clustering performance on benchmark datasets.
• Demonstrated the ability to escape local minima and find better solutions.

Conclusions:

• The novel SC approach offers a faster and more effective solution for clustering tasks.
• Directly solving the primal problem leads to improved accuracy and robustness.
• The method shows significant advantages over existing spectral clustering and other clustering techniques.