Block-Diagonal Guided Symmetric Nonnegative Matrix Factorization

Symmetric nonnegative matrix factorization (SNMF) is effective to cluster nonlinearly separable data, which uses the constructed graph to capture the structure of inherent clusters. Nevertheless, many SNMF-based clustering approaches implicitly enforce either the sparseness constraint or the smoothness constraint with the limited supervised information in the form of cannot-link or must-link in a semi-supervised manner, which may not be quite satisfactory in many applications where sparseness and smoothness are demanded explicitly and simultaneously. In this paper, we propose a new semi-supervised SNMF-based approach termed Semi-supervised Structured SNMF-based clustering (S3NMF). The method flexibly enforces the block-diagonal structure to the similarity matrix, where the sparseness and smoothness are simultaneously considered, so that we can obtain the desirable assignment matrix by simultaneously learning similarity and assignment matrices in a constrained optimization problem. We formulate S3NMF with a semi-supervised manner and utilize the indirect constraints of sparseness and smoothness by cannot-link and must-link. To effectively solve S3NMF, we present an alternating iterative algorithm with theoretically proved convergence to seek for the solution of the optimization problem. Experiments on five benchmark data sets show better performance and satisfactory stability of the proposed method.