Off-diagonal symmetric nonnegative matrix factorization

François Moutier, Arnaud Vandaele, Nicolas Gillis

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.

Algorithm 1: Coordinate Descent for ODsymNMF.

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

Abstract

Symmetric nonnegative matrix factorization (symNMF) is a variant of nonnegative matrix factorization (NMF) that allows handling symmetric input matrices and has been shown to be particularly well suited for clustering tasks. In this paper, we present a new model, dubbed off-diagonal symNMF (ODsymNMF), that does not take into account the diagonal entries of the input matrix in the objective function. ODsymNMF has three key advantages compared to symNMF. First, ODsymNMF is theoretically much more sound as there always exists an exact factorization of size at most n(n − 1)/2 where n is the dimension of the input matrix. Second, it makes more sense in practice as diagonal entries of the input matrix typically correspond to the similarity between an item and itself, not bringing much information. Third, it makes the optimization problem much easier to solve. In particular, it will allow us to design an algorithm based on coordinate descent that minimizes the component-wise ℓ1 norm between the input matrix and its approximation. We prove that this norm is much better suited for binary input matrices often encountered in practice. We also derive a coordinate descent method for the component-wise ℓ2 norm, and compare the two approaches with symNMF on synthetic and document datasets.
BibTeX
@article{moutier2021off,
  author = {François Moutier and Arnaud Vandaele and Nicolas Gillis},
  title = {{Off-diagonal symmetric nonnegative matrix factorization}},
  journal = {Numer. Algorithms},
  year = {2021},
  doi = {10.1007/s11075-020-01063-9},
}
Figure