On Trivial Solution and Scale Transfer Problems in Graph Regularized NMF
Quanquan Gu, Chris H. Q. Ding, Jiawei Han · 2011
Combining graph regularization with nonnegative matrix (tri-)factorization (NMF) has shown great performance improvement compared with tradi-tional nonnegativematrix (tri-)factorizationmodels due to its ability to utilize the geometric structure of the documents and words. In this paper, we show that these models are not well-defined and suffer-ing from trivial solution and scale transfer prob-lems. In order to solve these common problems, we propose two models for graph regularized non-negativematrix (tri-)factorization,which can be ap-plied for document clustering and co-clustering re-spectively. In the proposed models, a Normalized Cut-like constraint is imposed on the cluster as-signment matrix to make the optimization problem well-defined. We derive a multiplicative updating algorithm for the proposed models, and prove its convergence. Experiments of clustering and co-clustering on benchmark text data sets demonstrate that the proposed models outperform the original models as well as many other state-of-the-art clus-tering methods. 1