Self-supervised Symmetric Nonnegative Matrix Factorization

Yuheng Jia, Hui Liu, Junhui Hou, Sam Kwong, Qingfu Zhang

Abstract

Symmetric nonnegative matrix factorization (SNMF) is a powerful method for data clustering but is mathematically formulated as a non-convex optimization problem, making it highly sensitive to variable initialization. We propose Self-supervised Symmetric SNMF ($S^3NMF$), a method that leverages this sensitivity to boost clustering performance progressively. By performing SNMF repeatedly with random initializations, ranking the results with adaptive weights, and iteratively reconstructing a more discriminative similarity matrix, $S^3NMF$ achieves superior results without external labels. Extensive experiments on 10 benchmark datasets demonstrate that $S^3NMF$ significantly outperforms 12 state-of-the-art methods across multiple metrics.

Introduction

Clustering is a fundamental task in machine learning aimed at grouping data points based on similarity. SNMF is a popular approach that decomposes an affinity matrix into lower-dimensional representations. However, the non-convex nature of the optimization problem means the algorithm often gets trapped in local minima, leading to inconsistent results depending on the starting point.

Traditionally, researchers mitigate this by using multiple runs and selecting the best one or employing complex pre-seeding strategies. $S^3NMF$ takes a different approach: it treats the diversity of results from different initializations as a source of information. Inspired by ensemble clustering, it aggregates these results to learn a more robust and accurate representation of the data's underlying structure.

The $S^3NMF$ Methodology

The core of $S^3NMF$ is an iterative, self-supervised loop designed to refine the similarity matrix used for clustering. The process consists of several key steps:

  1. Multiple Initializations: The algorithm runs SNMF multiple times (an ensemble) using different random starting points, producing a diverse set of clustering results.
  2. Adaptive Weighting: Instead of treating all runs equally, the model learns a weight ($\alpha$) for each run. Results that better fit the data receive higher weights. A hyper-parameter ($\tau$) is used to maintain diversity and prevent the weights from collapsing onto a single run.
  3. Affinity Reconstruction: The weighted results are used to build a new similarity matrix ($S$). The authors found that reconstructing this matrix from "binarized" (hard) clustering assignments is more effective than using continuous values, as it sharpens the boundaries between clusters.
  4. Self-Supervised Stopping: To determine when the process has converged, the algorithm monitors the Average Normalized Mutual Information (ANMI), which measures the consensus among the ensemble. The process stops when peak stability is reached.
Evolution of Clustering Accuracy (ACC) and Average Normalized Mutual Information (ANMI) over iterations. The red circle indicates the self-supervised stopping point.

Experimental Evaluation

The authors evaluated $S^3NMF$ on 10 diverse benchmark datasets, including image data (MNIST, COIL20, MSRA) and general datasets (IRIS, SEEDS). The method was compared against 12 state-of-the-art clustering algorithms using five quantitative metrics: Accuracy (ACC), NMI, Purity, ARI, and F1-score.

Key Results

  • Superior Performance: $S^3NMF$ achieved the best performance in 44 out of 50 test cases.
  • Significant Gains: On the COIL20 dataset, $S^3NMF$ improved Clustering Accuracy (ACC) by 31% compared to standard SNMF.
  • Robustness: The method showed significantly lower standard deviation in results, indicating that the ensemble approach successfully mitigates the risks of poor initialization.
Comparison of Clustering Accuracy (ACC) between standard SNMF (dashed line) and the proposed S$^3$NMF (red line) across different initialization set sizes.

Discussion and Conclusion

$S^3NMF$ effectively turns the primary weakness of SNMF—its sensitivity to initialization—into a strength. By iteratively refining the affinity matrix through a self-supervised ensemble process, it reaches a consensus that is more accurate than any single run.

While the iterative nature of the algorithm increases computational cost, it typically converges within five iterations. Future work may focus on scaling this approach to larger datasets through stochastic approximations. The source code for $S^3NMF$ is available at https://github.com/jyh-learning/SSSNMF.

Summary updated

Abstract

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.
BibTeX
@article{jia2022self,
  author = {Yuheng Jia and Hui Liu and Junhui Hou and Sam Kwong and Qingfu Zhang},
  title = {{Self-supervised Symmetric Nonnegative Matrix Factorization}},
  journal = {IEEE Trans. Circuits Syst. Video Technol.},
  year = {2022},
  doi = {10.1109/tcsvt.2021.3129365},
}
Figure