Randomized Algorithms for Symmetric Nonnegative Matrix Factorization
This work addresses scalability issues in SymNMF for data analysis and machine learning practitioners, though it is incremental as it builds on existing methods with randomized enhancements.
The authors tackled the problem of speeding up Symmetric Nonnegative Matrix Factorization (SymNMF) by developing two randomized algorithms using matrix sketching and leverage score sampling, which achieved significant speed-ups while approximately maintaining solution quality on large real-world graph clustering datasets.
Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning that approximates a symmetric matrix with a product of a nonnegative, low-rank matrix and its transpose. To design faster and more scalable algorithms for SymNMF we develop two randomized algorithms for its computation. The first algorithm uses randomized matrix sketching to compute an initial low-rank approximation to the input matrix and proceeds to rapidly compute a SymNMF of the approximation. The second algorithm uses randomized leverage score sampling to approximately solve constrained least squares problems. Many successful methods for SymNMF rely on (approximately) solving sequences of constrained least squares problems. We prove theoretically that leverage score sampling can approximately solve nonnegative least squares problems to a chosen accuracy with high probability. Additionally, we prove sampling complexity results for previously proposed hybrid sampling techniques which deterministically include high leverage score rows. This hybrid scheme is crucial for obtaining speeds ups in practice. Finally we demonstrate that both methods work well in practice by applying them to graph clustering tasks on large real world data sets. These experiments show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.