Abstract
Symmetric Nonnegative Matrix Factorization (symNMF) is a widely used technique for clustering tasks, where a similarity matrix $A$ is approximated by $HH^T$. However, standard symNMF faces challenges including mathematical complexity (quartic subproblems), theoretical existence issues, and the "diagonal distraction"—the unnecessary effort spent fitting uninformative self-similarity values. We propose Off-diagonal Symmetric Nonnegative Matrix Factorization (ODsymNMF), which ignores diagonal entries to streamline optimization and enhance robustness. Our approach utilizes Coordinate Descent (CD) algorithms for $\ell_2$ and $\ell_1$ norms. Experimental results on synthetic and real-world document datasets show that ODsymNMF significantly outperforms standard symNMF, particularly in noisy and adversarial settings.
Introduction
Clustering via symmetric Nonnegative Matrix Factorization (symNMF) involves finding a low-rank nonnegative matrix $H \in \mathbb{R}^{n \times r}_+$ such that $A \approx HH^T$ for a given similarity matrix $A \in \mathbb{R}^{n \times n}$. While effective, the standard formulation has several drawbacks. First, it attempts to approximate the diagonal entries $A_{ii}$, which often contain arbitrary or irrelevant information, distracting the algorithm from the more important off-diagonal similarity relationships. Second, the optimization problem typically involves solving fourth-degree polynomials, leading to high computational costs and a propensity for local minima. Finally, for some matrices, an exact symmetric NMF may not even exist, creating a theoretical gap in the model's applicability.
Methodology
The core innovation of ODsymNMF is the modification of the objective function to minimize error exclusively on off-diagonal entries. This shift simplifies the underlying mathematics and ensures that an exact factorization always exists for any $n$-dimensional matrix with a rank of at most $n(n-1)/2$.
Coordinate Descent Algorithms
We developed two Coordinate Descent (CD) schemes to solve the ODsymNMF problem. For the standard $\ell_2$ (Frobenius) norm, the univariate subproblems are reduced from quartic equations to simple quadratic ones, which can be solved efficiently. For the $\ell_1$ norm, which is more robust to outliers and noise in binary data, we formulated the subproblem as a "constrained weighted median" problem.
To handle large-scale datasets, we implemented a version of the algorithm that avoids the explicit calculation of large residual matrices. Additionally, we introduced a greedy initialization strategy for the $\ell_1$ norm to mitigate its sensitivity to starting conditions, outperforming traditional random or zero-start methods.
Theoretical Justification
A key theoretical contribution is the proof that for rank-one binary matrices, minimizing the $\ell_1$ norm is equivalent to minimizing the $\ell_0$ norm. This justifies the use of $\ell_1$ as a robust proxy for counting mismatches in binary similarity data.
Experiments and Results
The performance of ODsymNMF was evaluated using both synthetic binary matrices and real-world document datasets.
Synthetic Data Performance
In tests involving block-diagonal matrices with 10% random binary noise, ODsymNMF with the $\ell_1$ norm achieved 98% clustering accuracy. In contrast, standard symNMF and the $\ell_2$ variant of ODsymNMF only reached approximately 90-91%. Under adversarial noise conditions—where noise is specifically structured to mislead clustering—the $\ell_1$ model maintained high accuracy long after standard models failed.
Real-World Document Clustering
We tested the models on 12 document datasets from the CLUTO collection, using cosine similarity matrices. On the "reviews" dataset, ODsymNMF-$\ell_1$ achieved 70.07% accuracy, a significant improvement over the 49.37% accuracy of standard symNMF. Across all datasets, the off-diagonal models generally matched or exceeded the performance of standard symNMF, confirming that diagonal entries often act as "dead weight" in clustering tasks.
Conclusion
ODsymNMF offers a mathematically simpler and more robust alternative to standard symNMF for clustering. By ignoring diagonal entries, the method avoids unnecessary computational overhead and theoretical pitfalls. The $\ell_1$ variant, in particular, demonstrates exceptional resilience to noise in binary data. Future research will explore hybrid $\ell_1/\ell_2$ models and distributionally robust optimization to further enhance the stability and versatility of the ODsymNMF framework.
Summary updated