Fast Nonnegative Matrix Tri-Factorization for Large-Scale Data Co-Clustering

Hua Wang, Feiping Nie, Heng Huang, Fillia MakedonIJCAI 2011 · OpenReview

Abstract

Nonnegative Matrix Factorization (NMF) based coclustering methods have attracted increasing attention in recent years because of their mathematical elegance and encouraging empirical results. However, the algorithms to solve NMF problems usually involve intensive matrix multiplications, which make them computationally inefficient. In this paper, instead of constraining the factor matrices of NMF to be nonnegative as existing methods, we propose a novel Fast Nonnegative Matrix Trifactorization (FNMTF) approach to constrain them to be cluster indicator matrices, a special type of nonnegative matrices. As a result, the optimization problem of our approach can be decoupled, which results in much smaller size subproblems requiring much less matrix multiplications, such that our approach works well for large-scale input data. Moreover, the resulted factor matrices can directly assign cluster labels to data points and features due to the nature of indicator matrices. In addition, through exploiting the manifold structures in both data and feature spaces, we further introduce the Locality Preserved FNMTF (LP-FNMTF) approach, by which the clustering performance is improved. The promising results in extensive experimental evaluations validate the effectiveness of the proposed methods.

Introduction

Clustering is a fundamental task in machine learning, typically focused on grouping one dimension of a dataset, such as documents in a corpus. Co-clustering extends this by simultaneously grouping both data points and features (e.g., documents and words), providing a more holistic view of the data structure. While Nonnegative Matrix Tri-Factorization (NMTF) offers an elegant framework for co-clustering, it is often computationally prohibitive for large-scale datasets due to the iterative nature of intensive matrix multiplications. Furthermore, standard NMTF yields continuous "soft" assignments, necessitating additional post-processing to obtain discrete cluster labels.

Methodology

The authors introduce two primary algorithms to address these efficiency and usability challenges:

FNMTF (Fast Nonnegative Matrix Tri-Factorization)

The core innovation of FNMTF lies in constraining the factor matrices $F$ and $G$ to be discrete cluster indicator matrices. In these matrices, each row contains exactly one "1" (indicating cluster membership) and zeros elsewhere. This structural constraint allows the global optimization problem to be decoupled into independent subproblems. Instead of heavy matrix-matrix multiplications, the algorithm performs vector norm calculations to find the nearest cluster centers. This approach significantly reduces computational overhead and provides direct cluster assignments without post-processing.

LP-FNMTF (Locality Preserved FNMTF)

Recognizing that real-world data often resides on non-linear manifolds, the authors developed LP-FNMTF. This variant incorporates manifold regularization using graph Laplacians to preserve the local geometric structure of both data and feature spaces. By ensuring that nearby points in the original space remain close in the clustered space, LP-FNMTF enhances clustering accuracy while maintaining the computational efficiency of the base FNMTF model through clever mathematical transformations (Proposition 1).

Experimental Evaluation

The proposed methods were tested against five benchmark datasets: Coil20 (images), WebKB (web pages), WebACE (news), CSTR (technical reports), and RCV1 (a large-scale news dataset with 193,844 samples).

Performance and Accuracy

Experimental results demonstrate that LP-FNMTF consistently outperforms state-of-the-art methods like GNMF and DRCC across multiple metrics, including Accuracy, Normalized Mutual Information (NMI), and Purity.

Table 3: Performance comparison of different clustering methods across five datasets.

Efficiency and Scalability

A key advantage of FNMTF is its scalability. On the large-scale RCV1 dataset, FNMTF and LP-FNMTF demonstrated significantly lower computational costs compared to traditional NMF variants.

Figure 1(b): Computational cost comparison on the large-scale RCV1 dataset.

The speedup is attributed to both fewer iterations required for convergence and the reduced complexity of each iteration. For instance, on RCV1, standard NMF required approximately 92 iterations, whereas FNMTF converged in roughly 45.

Conclusion

By shifting from continuous non-negative constraints to discrete indicator matrices, FNMTF transforms the co-clustering problem into a highly efficient, decoupled optimization task. The inclusion of manifold regularization in LP-FNMTF further boosts performance without sacrificing speed. While the method is subject to local minima common in NMF approaches, its ability to handle hundreds of thousands of samples makes it a powerful tool for modern large-scale data analysis.

Summary updated

Abstract

Nonnegative Matrix Factorization (NMF) based coclustering methods have attracted increasing attention in recent years because of their mathematical elegance and encouraging empirical results. However, the algorithms to solve NMF problems usually involve intensive matrix multiplications, which make them computationally inefficient. In this paper, instead of constraining the factor matrices of NMF to be nonnegative as existing methods, we propose a novel Fast Nonnegative Matrix Trifactorization (FNMTF) approach to constrain them to be cluster indicator matrices, a special type of nonnegative matrices. As a result, the optimization problem of our approach can be decoupled, which results in much smaller size subproblems requiring much less matrix multiplications, such that our approach works well for large-scale input data. Moreover, the resulted factor matrices can directly assign cluster labels to data points and features due to the nature of indicator matrices. In addition, through exploiting the manifold structures in both data and feature spaces, we further introduce the Locality Preserved FNMTF (LP-FNMTF) approach, by which the clustering performance is improved. The promising results in extensive experimental evaluations validate the effectiveness of the proposed methods.
BibTeX
@inproceedings{wang2011fast,
  author = {Hua Wang and Feiping Nie and Heng Huang and Fillia Makedon},
  title = {{Fast Nonnegative Matrix Tri-Factorization for Large-Scale Data Co-Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=H1bjyNM_WH},
}
Figure