Structured Doubly Stochastic Graph-Based Clustering.

Area of Science:

• Machine Learning
• Data Mining
• Computer Vision

Background:

• Graph-based clustering effectiveness depends on graph quality.
• Current methods use doubly stochastic approximations but face limitations like predefined graphs and suboptimal optimization.
• Separated stages in spectral decomposition methods lead to mismatched problems and randomness.

Purpose of the Study:

• To propose a novel Structured Doubly Stochastic Graph-based Clustering (SDSGC) model.
• To address limitations of existing graph-based clustering paradigms.
• To directly learn a structured doubly stochastic graph from data for improved cluster indicators.

Main Methods:

• Developed the SDSGC model for direct graph learning from data.
• Employed an Augmented Lagrangian Multiplier (ALM)-based optimization method.
• Optimized all doubly stochastic conditions simultaneously for optimal solutions.

Main Results:

• SDSGC demonstrates robustness to noise, particularly on face datasets.
• Quantitative comparisons show SDSGC outperforms state-of-the-art (SOTA) methods on benchmark datasets.
• The proposed ALM-based optimization achieves optimal solutions, unlike feasible solutions from VNSP lemma.

Conclusions:

• The proposed SDSGC model offers a significant advancement in graph-based clustering.
• Simultaneous optimization of doubly stochastic conditions leads to superior performance.
• SDSGC provides a robust and effective solution for clustering tasks, especially in noisy environments.