Adversarial Nonnegative Matrix Factorization

Lei Luo, Yanfu Zhang, Heng HuangICML 2020 · OpenReview

TL;DR

Standard Nonnegative Matrix Factorization (NMF) is notoriously fragile when faced with outliers or adversarial perturbations. This paper introduces Adversarial NMF (ANMF), a bilevel optimization framework that treats data corruption as a strategic "attacker." This approach allows the model to learn feature matrices that are mathematically guaranteed to be more robust against a wide variety of real-world noises.

What Problem Does This Paper Address?

Nonnegative Matrix Factorization (NMF) is a cornerstone of dimensionality reduction, used for everything from document clustering to facial recognition. By decomposing a data matrix $Y$ into two nonnegative matrices $A$ (features) and $X$ (weights), it finds parts-based representations that are easy for humans to interpret.

However, NMF has a "glass jaw." Most versions rely on the $L_2$-norm (Euclidean distance), which assumes noise is nicely distributed (Gaussian). While "Robust NMF" variants exist to handle specific issues like outliers (using $L_{2,1}$-norms), they often fail when noise is structured, complex, or intentionally designed to mislead the model—what we call adversarial perturbations. The authors identify a critical gap: we need an NMF model that doesn't just react to noise but proactively anticipates worst-case scenarios.

Methods

The core innovation is formulating NMF as a bilevel optimization problem, essentially a game between two players:

  1. The Attacker (Lower Level): Given the current feature matrix, the attacker tries to find a perturbation that moves the data toward a specific "target" (e.g., making a face look like a different person or adding structured occlusion).
  2. The Learner (Upper Level): The learner tries to find a feature matrix $A$ and weight matrix $X$ that minimize reconstruction error on both the original data and the attacker's perturbed data.

Key Technical Highlights:

  • Stackelberg Equilibrium: The authors model this interaction as a leader-follower game. They derive a closed-form solution for the attacker's "best response," which allows them to simplify a seemingly impossible optimization problem.
  • ADMM Solver: To solve the resulting complex objective, they employ the Alternating Direction Method of Multipliers (ADMM). They introduce several auxiliary variables to split the problem into smaller, solvable sub-problems with closed-form updates.
  • Theoretical Guarantees: The paper provides a rigorous robustness analysis, proving that ANMF provides asymptotically unbiased predictions under mild conditions.

Datasets and Experimental Setup

The authors evaluated ANMF across a diverse range of benchmarks to prove its versatility, including image datasets (MNIST, Yale, ORL, UMIST, COIL-20, USPS) and text datasets (BBCsports, BBCNews, WebKB, Reuters, RCV, TDT2).

To rigorously test robustness, they didn't just use "clean" data. They subjected these datasets to four types of corruption:

  1. Salt & Pepper (SP) Noise: Random white/black pixels.
  2. Pixel Noise: Random Gaussian-like perturbations.
  3. Regular Patch Noise: Blocking out a consistent square area (simulating occlusion).
  4. Irregular Patch Noise: Blocking out random, non-contiguous shapes.
Examples of the four types of noise applied to face datasets: Salt & Pepper, pixel, regular patch, and irregular patch.

Key Insights and Results

ANMF consistently outperformed standard NMF and existing robust variants (like $L_{2,1}$-NMF and CNMF) across almost every metric.

  • Robustness via Anticipation: Unlike previous methods that change the loss function (e.g., using $L_1$ instead of $L_2$), ANMF changes the training process. By baking the "attacker" into the loop, the model learns features that are inherently less sensitive to change.
  • Beyond Gaussian Assumptions: Most robust models assume noise is independent and identically distributed (i.i.d.). ANMF breaks this by handling structured noise (like patches), which is much more common in real-world applications like video surveillance or sensor data.
  • Clustering Accuracy (ACC): On the ORL face dataset with "Regular Patch" noise, ANMF achieved an accuracy of 0.5680, significantly higher than standard NMF (0.5465) and specialized robust models like CNMF (0.4695).
  • Visual Stability: T-SNE visualizations showed that the features learned by ANMF ($A$) and the perturbed features ($\tilde{A}$) remain well-separated and distinct, whereas other models see their feature clusters "collapse" under noise.
t-SNE visualization showing well-separated feature clusters even under perturbation.

Limitations and Future Work

While powerful, ANMF comes with a few trade-offs:

  • Computational Complexity: Using ADMM for a bilevel problem is more computationally expensive than the simple "Multiplicative Update" rules used in basic NMF. Scaling this to massive matrices might require further optimization.
  • Manual Perturbation Priors: The current model requires some manual setting of the "target" $Z$ for the attacker. Future work could involve automatically learning these priors to make the model even more autonomous.
  • Additive Focus: The framework primarily focuses on additive noise. Exploring how this handles multiplicative noise or geometric transformations (rotations/scaling) remains an open question.

Summary updated

Abstract

Nonnegative Matrix Factorization (NMF) has become an increasingly important research topic in machine learning. Despite all the practical success, most of existing NMF models are still vulnerable t...
BibTeX
@inproceedings{luo2020adversarial,
  author = {Lei Luo and Yanfu Zhang and Heng Huang},
  title = {{Adversarial Nonnegative Matrix Factorization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=SopByrVHQy8},
}
Figure