Self-Supervised Symmetric Nonnegative Matrix Factorization

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

TL;DR

Symmetric Nonnegative Matrix Factorization (SNMF) is a powerful tool for data clustering, but it suffers from a major flaw: it is highly sensitive to how you initialize its variables, often getting stuck in poor local minima. This paper introduces Self-supervised Symmetric NMF ($S^3NMF$), which turns this "bug" into a feature by running multiple random initializations, ranking their quality, and iteratively reconstructing a superior similarity matrix to boost clustering performance without any external labels.

What Problem Does This Paper Address?

Clustering is the task of grouping data points so that items in the same group are more similar to each other than to those in other groups. SNMF is a popular way to do this by decomposing an "affinity matrix" (which describes how similar every pair of points is) into a lower-dimensional representation.

However, SNMF involves solving a non-convex optimization problem. In plain English, this means the mathematical "landscape" the algorithm explores is full of traps (local minima). If you start the algorithm in the wrong place (initialization), you end up with a mediocre clustering result. Most researchers just try a few times and pick the best one, or use complex "pre-seeding" strategies. The authors of this paper wanted to find a way for the algorithm to learn from its own various attempts to produce a result that is better than any single run could achieve.

Methods

The core of $S^3NMF$ is an iterative, self-supervised loop inspired by "ensemble clustering." Here is how it works:

  1. Multiple Initializations: The algorithm performs SNMF several times (let's say 20) using different random starting points. This produces a set of diverse clustering results.
  2. Adaptive Weighting: Instead of treating all results equally, the model learns a weight ($\alpha$) for each run. Results that fit the data better get higher weights. They use a hyper-parameter ($\tau$) to ensure the weights don't just collapse onto a single "best" run, maintaining diversity.
  3. Affinity Reconstruction: It takes these weighted results and builds a new similarity matrix ($S$). Because clustering partitions are generally cleaner and more discriminative than raw similarity data, this new matrix is "sharper" and more accurate than the original.
  4. Iteration: The process repeats. The new, better matrix is used as the input for the next round of SNMF runs.
  5. Self-Supervised Stopping: To decide when to stop, the authors use Average Normalized Mutual Information (ANMI). This measures the consensus among the different runs. When the consensus starts to drop, the algorithm stops, as it has reached peak stability.

Datasets

The authors evaluated their method on 10 diverse benchmark datasets commonly used in machine learning research:

  • Image Data: MNIST (digits), USPS (digits), COIL20 (objects), MSRA (faces), SEMEION (handwritten digits), PALM (palmprints).
  • General Data: IRIS (flowers), SEEDS (wheat), CHART (synthesized shapes), USPST (a variant of USPS).

These datasets range from simple low-dimensional data (Iris) to high-dimensional image data (COIL20), providing a robust test of the algorithm's versatility.

Key Insights and Ideas

  • Turning Sensitivity into Strength: Usually, sensitivity to initialization is a weakness. Here, the authors realize that different initializations explore different parts of the data's structure. By aggregating them, they capture a more holistic view of the clusters.
  • The "Hard" vs. "Soft" Reconstruction: The paper finds that reconstructing the affinity matrix from "binarized" clustering partitions (hard assignments) is more effective than using the raw continuous values. This "sharpens" the boundaries between clusters.
  • Mathematical Convergence: Despite the complexity of the iterative loop, the authors provide a theoretical proof using an "auxiliary function" to guarantee that their optimization algorithm will actually converge to a stable solution.

Key Results

The $S^3NMF$ method was compared against 12 state-of-the-art methods, including standard Spectral Clustering and advanced SNMF variants.

  • Superior Accuracy: $S^3NMF$ achieved the best performance in 44 out of 50 test cases across 5 different metrics (Accuracy, NMI, Purity, ARI, and F1-score).
  • Massive Gains: On the COIL20 dataset, $S^3NMF$ improved the Clustering Accuracy (ACC) by a staggering 31% compared to standard SNMF.
  • Robustness: The standard deviation of the results was significantly lower than other methods, meaning $S^3NMF$ isn't just better on average—it's much more reliable and less likely to give a "bad" result on any given run.

Limitations and Future Work

While the paper demonstrates impressive results, a few areas remain for future exploration:

  • Computational Cost: Running SNMF multiple times per iteration is computationally more expensive than a single run. While the authors note that it usually converges within 5 iterations, the "ensemble" nature inherently requires more memory and processing power.
  • Hyper-parameter Tuning: Although the authors suggest an empirical value of $\tau = 2$ works well, the optimal balance between "consensus" and "diversity" might vary for extremely noisy or overlapping datasets.
  • Scalability: The paper tests on datasets with up to 2,000 samples. Scaling this iterative ensemble approach to "Big Data" (millions of samples) would likely require further optimization or stochastic approximations.

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 positive 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 constrained 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 14 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},
}

Loading related content...

Figure