Robust Adaptive Graph Regularized Non-Negative Matrix Factorization

Xiang He, Qi Wang, Xuelong LiIEEE Access 2019 · OpenReview

Abstract

Data clustering, which aims to divide the given samples into several different groups, has drawn much attention in recent years. As a powerful tool, non-negative matrix factorization (NMF) has been applied successfully in clustering tasks. However, there are still two main limitations. First, the original NMF treats equally both noisy and clean data, which leads to high sensitivity to noises and outliers. Second, the performance of graph-based NMFs highly depends on the input graph, that is, if a low-quality graph is constructed to regularize NMF, the clustering results will be bad. To address the above-mentioned problems, we propose a novel robust adaptive graph regularized non-negative matrix factorization (RAGNMF) for data clustering. To be specific, we develop a robust weighted NMF (RWNMF) that can assign small weights to noises and outliers and large weights to clean data. Thus, the robustness of NMF is improved. Moreover, in the process of matrix factorization, metric learning is combined to choose some discriminative features and compute more appropriate distances of samples. Then, an adaptive graph is learned to well regularize the NMF. The experimental results demonstrate that the proposed RAGNMF can achieve better clustering performance then most of the state-of-the-art methods.

Introduction

Non-Negative Matrix Factorization (NMF) is a staple in machine learning for finding "parts-based" representations of data, making it incredibly useful for clustering. However, traditional NMF approaches suffer from two primary weaknesses. First, they are highly sensitive to noise; standard NMF uses the Frobenius norm (squared error), meaning a few massive outliers can dominate the loss function and skew results. Second, many advanced NMF variants rely on a static "graph regularizer" to preserve local data structures. These graphs are typically pre-computed using simple Euclidean distance. If the data is noisy or contains irrelevant features, the initial graph will be low-quality, leading to poor clustering performance—a classic "garbage in, garbage out" scenario.

The RAGNMF Framework

To solve these issues, we propose Robust Adaptive Graph Regularized NMF (RAGNMF), a unified framework that simultaneously filters out outliers, selects relevant features, and builds an adaptive graph. The framework consists of three main components:

  • Robust Weighted NMF (RWNMF): Instead of treating every data point equally, the algorithm learns a weight for each sample. It automatically assigns near-zero weights to outliers and high weights to clean data, effectively "muting" the noise.
  • Unsupervised Metric Learning: The model learns a diagonal metric matrix ($M$) that weights features based on their importance. This acts as an integrated feature selection mechanism, ensuring that noisy or irrelevant dimensions don't interfere with distance calculations.
  • Adaptive Graph Learning: Rather than relying on a static, pre-defined graph, RAGNMF learns the graph structure dynamically. It uses the learned feature weights to compute more accurate similarities between samples, which in turn regularizes the matrix factorization.

By integrating graph construction into the factorization process, the model creates a virtuous cycle: better factorization leads to a better graph, and a better graph leads to a more accurate factorization.

Experimental Evaluation

The researchers evaluated RAGNMF against eight benchmark datasets, including image datasets (ORL, Yale, JAFFE, and USPS) and UCI benchmarks (Iris, Ecoli, Vote, and Control). RAGNMF was compared against eight state-of-the-art methods, including k-means, standard NMF, and Graph-regularized NMF (GNMF).

Sample images from the ORL dataset with 8x8 block occlusions used to test robustness.

RAGNMF achieved the highest Clustering Accuracy (ACC) and Normalized Mutual Information (NMI) across all eight datasets. A key highlight was the model's performance under extreme noise. In tests on the ORL dataset polluted with $8 \times 8$ block occlusions (as seen in the figure above), RAGNMF maintained an accuracy of 42.98%, while standard NMF plummeted to 38.88%.

Conclusion

RAGNMF provides a robust and adaptive approach to data clustering by addressing the inherent weaknesses of traditional NMF. By explicitly weighting samples and features while dynamically learning the data's underlying graph structure, the model achieves superior performance even in the presence of significant noise and outliers. Future work may explore extending this modular framework to deep architectures or multi-view clustering scenarios.

Summary updated

Abstract

Data clustering, which aims to divide the given samples into several different groups, has drawn much attention in recent years. As a powerful tool, non-negative matrix factorization (NMF) has been applied successfully in clustering tasks. However, there are still two main limitations. First, the original NMF treats equally both noisy and clean data, which leads to high sensitivity to noises and outliers. Second, the performance of graph-based NMFs highly depends on the input graph, that is, if a low-quality graph is constructed to regularize NMF, the clustering results will be bad. To address the above-mentioned problems, we propose a novel robust adaptive graph regularized non-negative matrix factorization (RAGNMF) for data clustering. To be specific, we develop a robust weighted NMF (RWNMF) that can assign small weights to noises and outliers and large weights to clean data. Thus, the robustness of NMF is improved. Moreover, in the process of matrix factorization, metric learning is combined to choose some discriminative features and compute more appropriate distances of samples. Then, an adaptive graph is learned to well regularize the NMF. The experimental results demonstrate that the proposed RAGNMF can achieve better clustering performance then most of the state-of-the-art methods.
BibTeX
@inproceedings{he2019robust,
  author = {Xiang He and Qi Wang and Xuelong Li},
  title = {{Robust Adaptive Graph Regularized Non-Negative Matrix Factorization}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=ocSC4bRTc_A},
}
Figure