Structured Doubly Stochastic Graph-Based Clustering

Graph-based clustering is a hot topic in machine learning, whose effectiveness highly relies on the quality of the learned graph. Recent researches preferred to learn the nearest doubly stochastic approximation of a graph to suppress intercluster connections and enhance intracluster connections and thus improve clustering performance. While current paradigm is limited by three key problems: 1) it is restricted by a predefined graph; 2) the separated stages of spectral decomposition-based way (graph learning, spectral embedding learning, and cluster assignment by k-means) cause mismatched problems and randomness; and 3) the optimization of doubly stochastic conditions is generally achieved by von Neumann successive projection (VNSP) lemma, which separates the conditions to form two subproblems for alternative optimization, converging only to a feasible solution. To solve these problems, in this article, a novel structured doubly stochastic graph-based clustering model termed SDSGC is proposed, which learns a structured doubly stochastic graph from data to directly provide cluster indicators. For optimization, a simple but effective augmented Lagrangian multiplier (ALM)-based method is proposed, which optimizes all the doubly stochastic conditions simultaneously to obtain the optimal solution. Experiments on one toy dataset and eight ad hoc noised face datasets have demonstrated that the proposed SDSGC is more robust to noise. Furthermore, a quantitative comparison of ten benchmarks has verified our SDSGC achieves better clustering performance when compared with SOTA methods. The code is available at <uri>https://github.com/NianWang-HJJGCDX/SDSGC.git</uri>.