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:
- Multiple Initializations: The algorithm runs SNMF multiple times (an ensemble) using different random starting points, producing a diverse set of clustering results.
- 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.
- 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.
- 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.
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.
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