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:
- 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.
- 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.
- Flexible Sampling Strategies: The algorithm supports three sampling modes:
- Mini-batch: Processes small, fresh data samples.
- Aggregate: Averages all historical samples equally.
- 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.
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.
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