Convex Nonnegative Matrix Factorization on Bipartite Graph
DOI:
https://doi.org/10.63313/CS.8008Keywords:
Nonnegative Matrix Factorization, Clustering, Bipartite GraphAbstract
In this paper, we propose a novel convex nonnegative matrix factorization (CNMF) method to learn a bipartite graph with exactly k connected components, where k is the number of clusters. The new bipartite graph learned in our model approximates the original graph but maintains an explicit cluster structure, from which we can immediately get the clustering results. Besides, inspired by self-expressive assumption of the data and subspace clustering, we added additional constraints to further recover global structural information of the data. Multiplicative updating rules are developed. The superiority of our method over the effectiveness and efficiency is demonstrated by extensive experiments.
References
[1] A. Sotiras, S. M. Resnick, and C. Davatzikos, “Finding imaging patterns of structural covari-ance via non-negative matrix factorization,” NeuroImage, p. 1–16, Mar 2015. [Online]. Available: http://dx.doi.org/ 10.1016/j.neuroimage.2014.11.045
[2] D. Behnia, K. Ahangari, and S. R. Moeinossadat, “Modeling of shear wave ve-locity in lime-stone by soft computing methods,” International Journal of Mining Science and Technolo-gy, vol. 27, no. 3, p. 423–430, May 2017. [Online]. Available: http://dx.doi.org/10.1016/j.ijmst.2017. 03.006
[3] H. Liu, Z. Wu, D. Cai, and T. S. Huang, “Constrained nonnegative matrix fac-torization for image representation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, p. 1299–1311, Jul 2012. [Online]. Available: http://dx.doi.org/10.1109/tpami.2011.217
[4] Y. Akashi and T. Okatani, “Separation of reflection components by sparse non-negative matrix factorization,” Computer Vision and Image Understanding, p. 77–85, May 2016. [Online]. Available: http://dx.doi.org/10.1016/j.cviu.2015.09.001
[5] C. Ding, T. Li, W. Peng, and H. Park, “Orthogonal nonnegative matrix t-factorizations for clustering,” in Proceedings of the 12th ACM SIGKDD interna-tional conference on Knowledge discovery and data mining, Aug 2006. [Online]. Available: http://dx.doi.org/10.1145/1150402.1150420
[6] D. Cai, X. He, J. Han, and T. Huang, “Graph regularized nonnegative matrix factorization for data representation.” IEEE transactions on pattern analysis and machine intelligence, vol. 33, no. 8, pp. 1548–60, 2011.
[7] X. Li, G. Cui, and Y. Dong, “Graph regularized non-negative low-rank matrix factorization for image clustering,” IEEE Transactions on Cybernetics, p. 3840–3853, Nov 2017. [Online]. Available: http://dx.doi.org/10.1109/tcyb.2016.2585355
[8] C. Peng, Y. Zhang, Y. Chen, Z. Kang, C. Chen, and Q. Cheng, “Log-based sparse nonnegative matrix factorization for data representation,” Apr 2022.
[9] Z. Li, J. Tang, and X. He, “Robust structured nonnegative matrix factorization for image representation,” IEEE Transactions on Neural Networks and Learning Systems, vol. 29, no. 5, p. 1947–1960, May 2018. [Online]. Available: http://dx.doi.org/10.1109/tnnls.2017.2691725
[10] Q. Huang, X. Yin, S. Chen, Y. Wang, and B. Chen, “Robust nonnegative matrix factorization with structure regularization,” Neurocomputing, vol. 412, p. 72–90, Oct 2020. [Online]. Available: http://dx.doi.org/10. 1016/j.neucom.2020.06.049
[11] C. Peng, Z. Zhang, Z. Kang, C. Chen, and Q. Cheng, “Nonnegative matrix fac-torization with local similarity learning,” Information Sciences, p. 325–346, Jul 2021. [Online]. Available: http://dx.doi.org/ 10.1016/j.ins.2021.01.087
[12] P. Deng, H. Wang, T. Li, H. Zhao, and Y. Wu, “Graph regularized sparse non-negative matrix factorization for clustering,” in Developments of Artificial Intelligence Technologies in Computation and Robotics, Oct 2020. [Online]. Available: http://dx.doi.org/10.1142/9789811223334 0119
[13] D. Kong, C. Ding, and H. Huang, “Robust nonnegative matrix factorization using l21-norm,” in Proceedings of the 20th ACM international conference on In-formation and knowledge management, Oct 2011. [Online]. Available: http://dx.doi.org/10.1145/2063576. 2063676
[14] F. Nie, H. Huang, X. Cai, and C. Ding, “Efficient and robust feature selection via joint l2,1-norms minimization,” Neural Information Processing Sys-tems,Neural Information Processing Systems, Dec 2010.
[15] F. Nie, X. Wang, C. Deng, and H. Huang, “Learning a structured optimal bi-partite graph for co-clustering,” Neural Information Processing Systems,Neural Information Processing Systems, Jan 2017.
[16] C. Peng and Q. Cheng, “Discriminative ridge machine: A classifier for high-dimensional data or imbalanced data,” IEEE Transactions on Neural Net-works and Learning Systems, p. 2595–2609, Jun 2021. [Online]. Available: http://dx.doi.org/10.1109/tnnls.2020.3006877
[17] C. H. Q. Ding, T. Li, and M. I. Jordan, “Convex and semi-nonnegative matrix factorizations.” in Machine Learning & Knowledge Discovery in Databases, Euro-pean Conference, Ecml Pkdd, Bled, Slovenia, September, 2009.
[18] C. Peng, Z. Kang, H. Li, and Q. Cheng, “Subspace clustering using log-determinant rank ap-proximation,” in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug 2015. [Online]. Available: http://dx.doi.org/10.1145/ 2783258.2783303
[19] C. Peng, Q. Zhang, Z. Kang, C. Chen, and Q. Cheng, “Kernel two-dimensional ridge regression for subspace clustering,” Cornell University - arXiv,Cornell Uni-versity - arXiv, Nov 2020.
[20] G. Liu, Z. Lin, and Y. Yu, “Robust subspace segmentation by low-rank repre-sentation,” In-ternational Conference on Machine Learning,International Confer-ence on Machine Learn-ing, Jun 2010.
[21] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, “Robust recovery of subspace structures by low-rank representation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, p. 171–184, Jan 2013. [Online]. Available: http://dx.doi.org/10.1109/tpami.2012.88
[22] Yong-Deok Kim and Seungjin Choi. Weighted non-negative matrix factoriza-tion. In Acous-tics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE Interna-tional Conference on, pages 1541–1544. IEEE, 2009.
[23] J. Huang, F. Nie, H. Huang, and C. Ding, “Robust manifold nonnegative matrix factorization,” ACM Transactions on Knowledge Discovery from Data, p. 1–21, Jun 2014. [Online]. Availa-ble: http://dx.doi.org/10.1145/2601434
[24] J. Liu, X. Liu, Y. Yang, L. Liu, S. Wang, W. Liang, and J. Shi, “Onepass mul-ti-view clustering for large-scale data,” in 2021 IEEE/CVF International Confer-ence on Computer Vision (ICCV), Oct 2021. [Online]. Available: http://dx.doi.org/10.1109/iccv48922.2021.01212
[25] J. Lu, Y. Lu, R. Wang, F. Nie, and X. Li, “Multiple kernel k-means clustering with simultane-ous spectral rotation,” in ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2022. [Online]. Available: http://dx.doi.org/10.1109/icassp43922.2022.9746905
[26] J. Wei, C. Tong, B. Wu, Q. He, S. Qi, Y. Yao, and Y. Teng, “An entropy weighted nonnegative matrix factorization algorithm for feature representation.”
Downloads
Published
Issue
Section
License
Copyright (c) 2025 by author(s) and Erytis Publishing Limited.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
How to Cite
