Nonnegative Factorization and The Maximum Edge Biclique Problem

Nicolas Gillis, François Glineur

Abstract Nonnegative Matrix Factorization (NMF) is a cornerstone of modern data analysis, enabling the compression and interpretation of nonnegative data through parts-based representations. This paper investigates a broader class of problems termed Nonnegative Factorization (NF), where a not necessarily nonnegative matrix is approximated by the product of two nonnegative matrices. We prove that NF is NP-hard for any fixed factorization rank $r \ge 1$ by establishing a reduction to the Maximum Edge Biclique Problem (MBP). This theoretical framework provides a mathematical explanation for the superior performance of Hierarchical Alternating Least Squares (HALS) over Multiplicative Updates (MU) and introduces a novel, efficient $O(|E|)$ algorithm for biclique detection in large-scale graphs.

Introduction

Since the seminal work of Lee and Seung in 1999, NMF has been widely adopted for its ability to decompose data into intuitive, additive components. However, many practical implementations, such as HALS, iteratively solve subproblems involving "residual" matrices that contain negative entries. This paper formalizes these subproblems as Nonnegative Factorization (NF). By analyzing the complexity of NF, we bridge the gap between continuous matrix factorization and discrete graph theory.

The Complexity of Nonnegative Factorization

A significant finding of this work is the "hardness jump" associated with NF. In standard NMF, rank-1 and rank-2 problems can be solved in polynomial time using techniques like Singular Value Decomposition (SVD) or the Perron-Frobenius theorem. In contrast, we demonstrate that for NF, even the rank-1 case is NP-hard.

This hardness stems from the negative values in the target matrix, which introduce combinatorial choices absent in purely nonnegative data. We prove this by reducing the Maximum Edge Biclique Problem—a known hard problem in graph theory—to a rank-1 NF problem. This connection reveals that finding the optimal rank-1 NF approximation is equivalent to identifying the largest biclique in a corresponding bipartite graph.

Algorithmic Insights: MU vs. HALS

The paper provides a mathematical "post-mortem" on the performance disparity between the two most popular NMF algorithms:

  1. Multiplicative Updates (MU): Originally proposed by Lee and Seung, MU is essentially a gradient-descent approach. We generalize MU to handle NF by splitting the target matrix into positive and negative components ($M = P - N$).
  2. Hierarchical Alternating Least Squares (HALS): HALS is shown to be significantly more efficient because it effectively solves the rank-1 NF subproblem optimally at each iteration, whereas MU takes "lazy," suboptimal steps.

Geometric Interpretation

The geometry of NF can be visualized as finding a low-rank subspace and a nonnegative cone within that subspace that best approximates the data points.

Geometric interpretation of rank-2 nonnegative factorization, where data points are approximated within a cone defined by two nonnegative basis vectors on a 2D plane.

As shown in the figure above, the factorization seeks to project data points onto a plane (for rank-2) where they are bounded by rays representing the nonnegative basis vectors. The presence of negative values in the original matrix $M$ means that points may lie outside the first quadrant, complicating the search for the optimal cone.

Finding Bicliques in Large Graphs

By linking NF stationary points with feasible solutions of the biclique problem, we developed a new algorithm for graph mining. By employing a homotopy-like approach—starting with a low penalty for negative approximations and gradually increasing it—we force the NF stationary points to converge toward maximal bicliques.

Experimental Results

  • Convergence: On the CBCL face database (2,429 images), HALS reached lower error rates significantly faster than generalized MU rules.
  • Biclique Performance: On DIMACS benchmark graphs and synthetic random graphs, our $O(|E|)$ algorithm consistently identified larger bicliques than the established Motzkin-Strauss formalism.
  • Biclustering: On a 'Classic' text mining dataset (7,094 texts, 41,681 words), the algorithm demonstrated robust biclustering capabilities, identifying dense submatrices even when perfect bicliques were not present.

Conclusion

This research establishes NF as a powerful framework that unites matrix factorization and graph theory. While the NP-hardness of NF implies that global optima are difficult to guarantee, the proposed NF-based algorithms offer a scalable and robust alternative to existing methods for both data compression and discrete graph analysis. Future work will explore more sophisticated penalty update schedules to further mitigate the risk of local optima.

Summary updated

Abstract

Nonnegative Matrix Factorization (NMF) is a data analysis technique which allows compression and interpretation of nonnegative data. NMF became widely studied after the publication of the seminal paper by Lee and Seung (Learning the Parts of Objects by Nonnegative Matrix Factorization, Nature, 1999, vol. 401, pp. 788--791), which introduced an algorithm based on Multiplicative Updates (MU). More recently, another class of methods called Hierarchical Alternating Least Squares (HALS) was introduced that seems to be much more efficient in practice. In this paper, we consider the problem of approximating a not necessarily nonnegative matrix with the product of two nonnegative matrices, which we refer to as Nonnegative Factorization (NF); this is the subproblem that HALS methods implicitly try to solve at each iteration. We prove that NF is NP-hard for any fixed factorization rank, using a reduction to the maximum edge biclique problem. We also generalize the multiplicative updates to NF, which allows us to shed some light on the differences between the MU and HALS algorithms for NMF and give an explanation for the better performance of HALS. Finally, we link stationary points of NF with feasible solutions of the biclique problem to obtain a new type of biclique finding algorithm (based on MU) whose iterations have an algorithmic complexity proportional to the number of edges in the graph, and show that it performs better than comparable existing methods.
BibTeX
@misc{gillis2008nonnegative,
  author = {Nicolas Gillis and François Glineur},
  title = {{Nonnegative Factorization and The Maximum Edge Biclique Problem}},
  year = {2008},
  eprint = {0810.4225},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0810.4225},
}

Loading related content...

Figure