PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonnegative Factorization and The Maximum Edge Biclique Problem

Nicolas Gillis, François Glineur

arXiv:0810.4225v1math.NAcs.NAmath.OC

TL;DR

NMF supports compression and interpretation of nonnegative data, while its joint-factor generalization, NF, raises a fixed-rank complexity question. The paper proves NF NP-hardness through a biclique reduction, generalizes multiplicative updates, and links NF stationary points to a biclique heuristic. The heuristic uses O(|E|) operations per iteration, while the paper notes that its convergence is unproved.

  • Problem

    The paper asks whether the joint nonnegative-factor approximation problem remains tractable when the matrix being approximated need not be nonnegative.

    Source: §3 · p. 6

  • Method

    The paper reduces NF to the maximum edge biclique problem, generalizes multiplicative updates to NF, and uses stationary points of a rank-one NF instance to construct a biclique heuristic.

    Source: The Maximum Edge Biclique Problem in… · pp. 8, 10, §5.1 · p. 20, §6 · p. 22

  • Results

    NF is NP-hard for any fixed rank, and the biclique heuristic requires O(|E|) operations per iteration and performs well compared with existing methods.

    Source: §6 · p. 22

  • Takeaways & Limitations

    The stationary-point connection supplies a multiplicative-updates-based heuristic for finding large bicliques, with per-iteration work proportional to graph edges.

    Source: §5.1 · p. 20, §6 · p. 22

    No convergence proof is provided for the biclique-finding algorithm, and the paper gives no guarantee that its algorithms reach globally optimal solutions.

    Source: §6 · p. 23

Abstract

from arXiv · show

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.

1 Introduction

NMF approximates nonnegative data with low-rank nonnegative factors, supporting compression and interpretation. The paper studies the broader Nonnegative Factorization problem and connects its complexity, multiplicative updates, and biclique algorithms.

1 Introduction

  • NMF represents each data column as a nonnegative combination of nonnegative basis elements, enabling part-based interpretation.Nonnegative weights make reconstruction essentially additive; sparsity can further improve compression and part-based representation.Source: §1 · p. 2
  • The paper generalizes NMF to Nonnegative Factorization, where the matrix being approximated need not be nonnegative, and proves fixed-rank NP-hardness via maximum edge biclique.It also generalizes multiplicative updates, studies stationary points, and uses the NF–biclique connection to develop a biclique-finding algorithm with O(|E|) operations per iteration.Source: §1 · p. 2

2 Nonnegative Matrix Factorization (NMF)

This section reviews NMF optimization and its complexity, then describes multiplicative updates and HALS, including convergence modifications and practical trade-offs.

2 Nonnegative Matrix Factorization (NMF)

  • NMF seeks a low-rank nonnegative-factor approximation of a nonnegative matrix, commonly using alternating minimization because the objective is separately convex in each factor.Optimizing a corresponding column of V and row of W simultaneously loses that convexity.Source: §2 · p. 3

2.1 Complexity

  • Exact NMF and NMF optimization are NP-hard in general, but the cited results establish exact factorization for ranks one and two and polynomial-time optimization for rank one.The complexity of exact NMF and NMF optimization for fixed ranks above three remains unknown in the reviewed results.Source: §2.1 · pp. 3–4

2.2 Multiplicative Updates (MU)

  • Lee and Seung’s multiplicative updates make the Frobenius reconstruction error nonincreasing, but alternating updates are not guaranteed to reach a first-order stationary point.The paper proposes a slight update modification to guarantee convergence to such a point.Source: §2.2 · p. 5

2.3 Hierarchical Alternating Least Squares (HALS)

  • HALS alternates over each rank-one factor using closed-form subproblems; it has the same per-iteration computational cost as MU and is reported to converge significantly faster.The positive-bound variant prevents zero factors and is shown to converge to a stationary point; zero factors otherwise can cause undefined updates and rank-deficient approximations.Source: §2.3 · p. 6

3 Nonnegative Factorization (NF)

This section studies nonnegative factorization of arbitrary real matrices through its complexity and its connections to the maximum edge biclique problem. It also generalizes multiplicative updates to this setting, establishing properties of the updates and examining the role of the matrix decomposition.

3 Nonnegative Factorization (NF)

  • NF extends NMF to arbitrary real input matrices, and jointly optimizing both nonnegative factors is not polynomial-time solvable unless P=NP.The paper presents NF as the problem of approximating an arbitrary real matrix by a product of two nonnegative matrices.Source: §3 · p. 7, The Maximum Edge Biclique Problem in… · p. 9

3.1 Complexity

The Maximum Edge Biclique Problem in Bipartite Graphs

  • For d ≥ |E|, optimal rank-one NF solutions coincide with maximum edge bicliques, making NF-1d NP-hard.The correspondence means vw is binary and vw ≤ Mb; the reduction uses the NP-completeness of the biclique decision problem.Source: The Maximum Edge Biclique Problem in… · pp. 7–9

3.2 Stationary points of (NF-1d) √

  • The section studies NF-1d stationary points and relates them to feasible maximum edge biclique solutions as a basis for a biclique-finding algorithm.The stationary points are defined by the same KKT conditions as for NMF.Source: §3.2 · p. 10, §3.2.1 · p. 10

3.2.2 Stationarity of Maximal Bicliques

  • For d > max(m, n) − 1, the only nontrivial feasible solutions of (MBP) that are stationary points of (NF-1d) are the maximal bicliques.Not every stationary point of (NF-1d) corresponds to a maximal biclique.Source: §3.2.2 · p. 11

3.2.3 Limit points of Sd

  • As d grows, NF-1d stationary points get arbitrarily close to feasible maximum edge biclique solutions.The result establishes closeness for sufficiently large d, rather than asserting that every stationary point is itself feasible.Source: §3.2.3 · pp. 11–13
  • An illustrated positive stationary point approaches a biclique as d increases, showing how stationary points can converge toward feasible solutions without being bicliques at finite d.The example tracks a positive singular vector of Md as d varies.Source: §3.2.3 · p. 13, Figure 2 · p. 13

3.3 Multiplicative Updates for Nonnegative Factorization

  • The generalized multiplicative updates make the NF cost ||M − VW||F nonincreasing when M = P − N with P, N ≥ 0.The proof uses a quadratic upper approximation whose nonnegative global minimum supplies the next iterate and guarantees monotonicity.Source: §3.3 · p. 14
  • With every factor constrained to be at least epsilon > 0, the modified updates keep the cost nonincreasing and every limit point is stationary for the optimization problem.The guarantee holds for any constant epsilon > 0.Source: §3.3 · p. 15
  • For rank r = 1, choosing C = 0 in P = M+ + C and N = M− + C is optimal among decompositions M = P − N.The paper says this optimal-choice result does not extend to r > 1.Source: §3.3 · p. 16
  • For r > 1, a suitable nonzero C can improve an update even for nonnegative matrices, but choosing C is nontrivial and does not seem to significantly accelerate convergence.An example shows lower reconstruction error with one C-based update than with the update using P = M and N = 0.Source: §3.3 · p. 16

4 How good are the Multiplicative Updates (MU) of Lee and Seung?

The paper explains the limits of Lee and Seung’s multiplicative updates and proposes improved updates. In the example, the original MU converges more slowly than the improved MU and HALS, whose subproblems have closed-form solutions.

4.1 An Improved Version of the MU

  • MU updates are nonincreasing in the objective when applied to any column of V or row of W, and cycle through columns before rows.This interpretation motivates improvements to the update scheme.Source: §4.1 · p. 17
  • The MU uses old values for already-updated columns or rows, and its subproblems are not optimal despite having closed-form solutions.The improved updates (4.2) perform better than (4.1) but worse than the optimal HALS updates (2.12–2.13).Source: §4.1 · p. 17

4.2 An example

  • In the CBCL-face example, the original MU converges significantly less rapidly than the improved MU and HALS; HALS subproblems have closed-form solutions.Figure 3 compares the three methods on the same database; the paper says there is little reason to use either MU variant when HALS provides a closed-form solution for the corresponding subproblems.Source: Figure 3 · p. 18, §4.2 · p. 18
  • HALS has the same computational complexity as MU and performs provably better, but the paper gives no guarantee it will reach a better local optimum.Because NMF is NP-hard and has numerous locally optimal solutions, more efficient iterations do not guarantee a better final solution.Source: §4.2 · p. 18
  • For rank one, the three algorithms are equivalent to the power method, which reaches the optimal rank-one solution if initialized nonperpendicularly to the top singular vector.The paper also states that any stationary point is scaled.Source: §4.2 · p. 18

5 Biclique Finding Algorithm

The paper presents an O(|E|)-per-iteration biclique heuristic based on NF multiplicative updates and compares it with other algorithms. It reports generally better solutions for its method, especially on dense random graphs, while outlining settings where it instead yields biclusters.

5 Biclique Finding Algorithm

  • The proposed biclique-finding algorithm uses O(|E|) operations per main iteration and is based on NF multiplicative updates and links between NF stationary points and feasible bicliques.The paper compares it with other algorithms whose iterations also require O(|E|) operations.Source: §5 · p. 19

5.1 Description

  • For sufficiently large d, stationary points of NF-1d are close to bicliques, and NF-1d shares the MBP cost function.The algorithm uses multiplicative updates and increases d from a small initial value until it converges to a biclique.Source: §5.1 · p. 20

5.2 Other Algorithms in O(|E|) operations

  • The paper also presents two alternative maximal-biclique algorithms with O(|E|) operations per iteration.These alternatives are introduced for comparison with the proposed method.Source: §5.2 · p. 20

5.2.1 Motzkin-Strauss Formalism

  • The Motzkin–Strauss approach may yield a dense bipartite subgraph rather than a biclique when its parameters are not sufficiently small.With α = β = 2, it converges to an optimal rank-one solution of the unconstrained problem; the paper uses equal α and β.Source: §5.2.1 · p. 21

5.2.2 Greedy Heuristic

  • The greedy heuristic repeatedly adds a vertex connected to the most vertices on the opposite side, deleting non-neighbors to ensure a biclique.The paper states that this procedure produces a maximal biclique.Source: §5.2.2 · p. 21

5.3 Results

  • The multiplicative-update method generally finds better bicliques than the Motzkin–Strauss method, especially on dense random graphs.The evaluation uses DIMACS graphs and random graphs; Table 1 reports edge counts for DIMACS solutions and Table 2 reports average biclique edges for random graphs.Source: §5.3 · p. 21, Table 1 · p. 21, Table 2 · p. 22
  • The algorithm also applies to weighted graphs and can favor one side; keeping d sufficiently small may instead produce a bicluster whose density depends on the chosen cap.The paper describes a capped d update and illustrates biclusters on a sparse text-mining dataset.Source: §5.3 · p. 22, Table 3 · p. 22

6 Conclusion

The paper introduces NF, proves it NP-hard for any fixed rank, and generalizes multiplicative updates to NF. It also develops an O(|E|)-per-iteration biclique heuristic, while noting that its algorithms lack guarantees of global optimality.

6 Conclusion

  • NF is NP-hard for any fixed factorization rank, by reduction to the maximum edge biclique problem.The paper presents NF as a variant of NMF in which the approximated matrix need not be nonnegative.Source: §6 · p. 22
  • Generalized NF multiplicative updates provide a new interpretation of Lee and Seung’s algorithm and explain its weaker practical performance relative to HALS.Source: §6 · p. 22
  • The biclique heuristic uses O(|E|) operations per iteration and draws on stationary-point results for rank-one NF-1d.Source: §6 · p. 22
  • None of the presented algorithms is guaranteed to reach a global optimum, and no convergence proof is provided for the biclique heuristic.For the NMF and NF algorithms, only convergence to a stationary point is proved; the biclique algorithm uses dynamic updates of d.Source: §6 · p. 23

Related papers

Loading 0810.4225v1…