Discrete Optimal Graph Clustering.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Graph-based clustering is a prevalent method, typically involving separate steps for graph construction, label relaxation, and k-means discretization.
• Existing methods suffer from fixed similarity graphs, information loss during label relaxation, and sensitivity to k-means initialization.

Purpose of the Study:

• To propose an effective discrete optimal graph clustering framework that addresses the limitations of conventional methods.
• To enhance clustering performance through adaptive graph learning and robust prediction for unseen data.

Main Methods:

• Adaptively learning a structured similarity graph with rank constraints for optimal clustering.
• Enforcing discrete transformation on intermediate labels to derive a tractable optimization problem with discrete solutions.
• Developing an adaptive robust module for learning prediction functions on unseen data.
• Employing an iterative optimization strategy with guaranteed convergence.

Main Results:

• The proposed framework demonstrates superior performance compared to state-of-the-art clustering approaches.
• Experiments on real and synthetic datasets validate the effectiveness of the discrete optimal graph clustering method.
• The adaptive learning and discrete transformation successfully mitigate information loss and improve accuracy.

Conclusions:

• The discrete optimal graph clustering framework offers a significant advancement over traditional methods.
• The adaptive and robust design leads to more reliable and accurate clustering results.
• This approach provides a robust solution for various clustering tasks.