A Stochastic Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization

Songtao Lu, Mingyi Hong, Zhengdao WangAISTATS 2017 · OpenReview

Abstract

Symmetric nonnegative matrix factorization (SymNMF) plays an important role in applications of many data analytics problems such as community detection, document clustering and image segmentation. However, traditional SymNMF algorithms are often computationally intensive and designed for "offline" settings where the entire dataset is available upfront. This paper introduces SNS-SymNMF, a stochastic nonconvex splitting method designed to handle large-scale, streaming data with convergence guarantees even in non-convex settings.

Introduction

SymNMF is a powerful tool for finding latent structures in similarity matrices $Z$. The goal is to find a lower-rank factor matrix $X$ such that $XX^T \approx Z$. Despite its utility, SymNMF faces significant challenges: it is NP-hard, non-convex, and typically requires the full data matrix to be stored in memory. Standard stochastic methods often fail to provide convergence guarantees for SymNMF because the objective function's gradient lacks global Lipschitz continuity.

The SNS-SymNMF Framework

The proposed Stochastic Nonconvex Splitting (SNS-SymNMF) method overcomes these hurdles through three primary innovations:

  1. Variable Splitting: By introducing an auxiliary variable $Y$, the problem is reformulated to minimize the difference between $XY^T$ and $Z$, subject to the constraint $X = Y$. This decoupling simplifies the optimization steps.
  2. Augmented Lagrangian with Proximal Stabilization: The framework employs an iteration-dependent penalty term $\beta^{(t)}$. This proximal term acts as a stabilizer, ensuring that sub-problems remain strongly convex and preventing the algorithm from diverging in the absence of a smooth gradient.
  3. Flexible Sampling Strategies: The algorithm supports three sampling modes:
  4. Mini-batch: Processes small, fresh data samples.
  5. Aggregate: Averages all historical samples equally.
  6. Weighted Aggregate: Prioritizes recent samples, enabling the model to adapt to changing data distributions.

Experimental Evaluation

The researchers evaluated SNS-SymNMF using both synthetic and real-world datasets:

  • Synthetic Random Graphs: Used to test performance on static and dynamic community structures. In dynamic tests, the community structure was abruptly shifted mid-stream to test adaptability.
  • TDT2 (Topic Detection and Tracking): A real-world document dataset used to assess clustering accuracy in a sequential processing environment.

Results and Discussion

Experimental results demonstrate that SNS-SymNMF offers a superior balance of speed and accuracy compared to existing methods.

Performance comparison on static and dynamic networks. Figure (a) and (b) show static convergence, while (c) and (d) illustrate tracking performance after a structural change at sample 400.

Convergence and Adaptability

In static network environments, the aggregate version of SNS-SymNMF converged significantly faster than standard Mini-Batch Stochastic Projected Gradient Descent (SPGD). More importantly, in dynamic scenarios where the underlying data structure changed at the 400th sample, the Weighted-SNS-SymNMF variant demonstrated unique adaptability, successfully tracking the change and rapidly lowering the error rate again, whereas other methods struggled to adjust as effectively.

Offline Quality at Online Speeds

A key finding is that SNS-SymNMF achieves the accuracy of "offline" deterministic algorithms while maintaining the efficiency of a sequential, stochastic approach. On the TDT2 dataset, the clustering accuracy was nearly identical to the deterministic version that processes all data at once.

Comparison of stochastic methods against the deterministic SymNMF baseline. The inset highlights how SNS-SymNMF variants closely approach the offline solution's error levels.

Conclusion

SNS-SymNMF represents a significant advancement for Symmetric Nonnegative Matrix Factorization in big data contexts. By combining variable splitting with proximal stabilization, it provides robust convergence guarantees and the ability to track dynamic changes in real-time. Future work may explore hyperparameter optimization and the integration of more advanced mini-batching techniques to further enhance performance.

Summary updated

Abstract

Symmetric nonnegative matrix factorization (SymNMF) plays an important role in applications of many data analytics problems such as community detection, document clustering and image segmentation. ...
BibTeX
@inproceedings{lu2017stochastic,
  author = {Songtao Lu and Mingyi Hong and Zhengdao Wang},
  title = {{A Stochastic Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=i7KW-OKuEdQ},
}
Figure