One-step bipartite graph cut: A normalized formulation and its application to scalable subspace clustering.

Area of Science:

• Machine Learning
• Graph Theory
• Data Mining

Background:

• Bipartite graphs are effective for subspace and spectral clustering in large datasets.
• Existing methods like constrained Laplacian rank (CLR) can yield imbalanced clusters due to neglecting component distribution.
• Normalized Cut (Ncut) is successful for general graphs, but a one-step normalized cut for bipartite graphs with linear complexity is lacking.

Purpose of the Study:

• To develop a novel one-step bipartite graph cut (OBCut) criterion with normalized constraints.
• To address the limitations of existing methods in achieving balanced and well-defined clusters.
• To propose a scalable subspace clustering approach with linear-time complexity.

Main Methods:

• Characterized a novel one-step bipartite graph cut (OBCut) criterion with normalized constraints.
• Theoretically proved the equivalence of OBCut to a trace maximization problem.
• Developed a scalable subspace clustering approach integrating adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning within a unified objective function.
• Designed an alternating optimization algorithm for linear-time computation.

Main Results:

• The proposed OBCut criterion effectively constrains connected components in bipartite graphs.
• The unified objective function and alternating optimization algorithm achieve simultaneous adaptive anchor learning, bipartite graph learning, and normalized partitioning.
• Experimental results on diverse datasets demonstrate the effectiveness and scalability of the proposed approach.
• The method achieves linear-time complexity.

Conclusions:

• The novel OBCut criterion provides a robust solution for normalized bipartite graph partitioning in clustering.
• The integrated subspace clustering approach offers an effective and scalable method for large-scale datasets.
• The linear-time complexity makes the approach suitable for real-world applications.