  Symmetric nonnegative matrix factorization (SNMF) has demonstrated to be a
powerful method for data clustering. However, SNMF is mathematically formulated
as a non-convex optimization problem, making it sensitive to the initialization
of variables. Inspired by ensemble clustering that aims to seek a better
clustering result from a set of clustering results, we propose self-supervised
SNMF (S$^3$NMF), which is capable of boosting clustering performance
progressively by taking advantage of the sensitivity to initialization
characteristic of SNMF, without relying on any additional information.
Specifically, we first perform SNMF repeatedly with a random nonnegative matrix
for initialization each time, leading to multiple decomposed matrices. Then, we
rank the quality of the resulting matrices with adaptively learned weights,
from which a new similarity matrix that is expected to be more discriminative
is reconstructed for SNMF again. These two steps are iterated until the
stopping criterion/maximum number of iterations is achieved. We mathematically
formulate S$^3$NMF as a constraint optimization problem, and provide an
alternative optimization algorithm to solve it with the theoretical convergence
guaranteed. Extensive experimental results on $10$ commonly used benchmark
datasets demonstrate the significant advantage of our S$^3$NMF over $12$
state-of-the-art methods in terms of $5$ quantitative metrics. The source code
is publicly available at https://github.com/jyh-learning/SSSNMF.
