Clustering research on graph regularization nonnegative matrix factorization based on auxiliary variables under orthogonal conditions

Caiping Wang; Wen Li; Junjian Zhao; Yasong Chen; Caiping Wang; Wen Li; Junjian Zhao; Yasong Chen

doi:10.3934/math.2025529

AIMS Mathematics

2025, Volume 10, Issue 5: 11676-11707. doi: 10.3934/math.2025529

Previous Article Next Article

Research article Special Issues

Clustering research on graph regularization nonnegative matrix factorization based on auxiliary variables under orthogonal conditions

1.
Information Center, Zhangjiakou Cigarette Factory Co., Ltd., Zhangjiakou 075000, China
2.
School of Mathematical Sciences, Tiangong University, Tianjin 300387, China

Received: 19 March 2025 Revised: 11 May 2025 Accepted: 16 May 2025 Published: 21 May 2025
MSC : 62H30, 62H35, 68Q32, 68T10, 90C26

This paper addressed the challenge of image clustering by integrating graph and orthogonality mechanisms into the nonnegative matrix factorization algorithm. It presented a novel model named graph regularized nonnegative matrix factorization with auxiliary variable orthogonal subspace (GNMFOSV). This innovative approach not only provided a rigorous proof of algorithm convergence using auxiliary variables, thereby filling a significant gap in the theoretical validation of similar algorithms under orthogonal conditions, but also effectively captured the nonlinear relationships in the reconstructed data. Additionally, it enhanced the sparsity of the decomposition results, leading to a notable improvement in clustering performance. To verify the effectiveness of the proposed method, comprehensive clustering tests were conducted on diverse datasets. The experimental results clearly demonstrated that the GNMFOSV algorithm outperformed existing methods in terms of clustering performance, indicating its great potential for practical applications.
- NMF,
- graph Laplacian,
- orthogonality,
- clusterting,
- auxiliary variables
Citation: Caiping Wang, Wen Li, Junjian Zhao, Yasong Chen. Clustering research on graph regularization nonnegative matrix factorization based on auxiliary variables under orthogonal conditions[J]. AIMS Mathematics, 2025, 10(5): 11676-11707. doi: 10.3934/math.2025529

Related Papers:

Abstract

This paper addressed the challenge of image clustering by integrating graph and orthogonality mechanisms into the nonnegative matrix factorization algorithm. It presented a novel model named graph regularized nonnegative matrix factorization with auxiliary variable orthogonal subspace (GNMFOSV). This innovative approach not only provided a rigorous proof of algorithm convergence using auxiliary variables, thereby filling a significant gap in the theoretical validation of similar algorithms under orthogonal conditions, but also effectively captured the nonlinear relationships in the reconstructed data. Additionally, it enhanced the sparsity of the decomposition results, leading to a notable improvement in clustering performance. To verify the effectiveness of the proposed method, comprehensive clustering tests were conducted on diverse datasets. The experimental results clearly demonstrated that the GNMFOSV algorithm outperformed existing methods in terms of clustering performance, indicating its great potential for practical applications.

References

[1]	A. Jain, Data clustering: 50 years beyond k-means, Pattern Recogn. Lett., 31 (2010), 651–666. https://doi.org/10.1016/j.patrec.2009.09.011 doi: 10.1016/j.patrec.2009.09.011
[2]	S. Renaud-Deputter, T. Xiong, S. Wang, Combining collaborative filtering and clustering for implicit recommender system, Proceedings of IEEE 27th International Conference on Advanced Information Networking and Applications (AINA), 2013,748–755. https://doi.org/10.1109/AINA.2013.65
[3]	J. Das, P. Mukherjee, S. Majumder, P. Gupta, Clustering-based recommender system using principles of voting theory, Proceedings of International Conference on Contemporary Computing and Informatics (IC3I), 2014,230–235. https://doi.org/10.1109/IC3I.2014.7019655
[4]	C. Zheng, D. Huang, L. Zhang, X. Kong, Tumor clustering using nonnegative matrix factorization with gene selection, IEEE Trans. Inf. Technol. Bio., 13 (2009), 599–607. https://doi.org/10.1109/TITB.2009.2018115 doi: 10.1109/TITB.2009.2018115
[5]	J. Brunet, P. Tamayo, T. Golub, J. Mesirov, Metagenes and molecular pattern discovery using matrix factorization, Proc. Natl. Acad. Sci. USA, 101 (2004), 4164–4169. https://doi.org/10.1073/pnas.0308531101 doi: 10.1073/pnas.0308531101
[6]	S. Wang, P. Wu, M. Zhou, T. Chang, S. Wu, Cell subclass identification in single-cell rna-sequencing data using orthogonal nonnegative matrix factorization, Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018,876–880. https://doi.org/10.1109/ICASSP.2018.8462055
[7]	P. Paatero, U. Tapper, Positive matrix factorization: a nonnegative factor model with optimal utilization of error estimates of data values, Environmetrics, 5 (1994), 111–126. https://doi.org/10.1002/env.3170050203 doi: 10.1002/env.3170050203
[8]	P. Anttila, P. Paatero, U. Tapper, O. Järvinen, Source identification of bulk wet deposition in finland by positive matrix factorization, Atmos. Environ., 29 (1995), 1705–1718. https://doi.org/10.1016/1352-2310(94)00367-T doi: 10.1016/1352-2310(94)00367-T
[9]	D. D. Lee, H. S. Seung, Learning the parts of objects by nonnegative matrix factorization, Nature, 401 (1999), 788–791. https://doi.org/10.1038/44565 doi: 10.1038/44565
[10]	F. Shahnaz, M. W. Berry, V. P. Pauca, R. J. Plemmons, Document clustering using nonnegative matrix factorization, Inform. Process. Manag., 42 (2006), 373–386. https://doi.org/10.1016/j.ipm.2004.11.005 doi: 10.1016/j.ipm.2004.11.005
[11]	W. Xu, X. Liu, Y. Gong, Document clustering based on nonnegative matrix factorization, Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, 2003,267–273. https://doi.org/10.1145/860435.860485
[12]	H. Kim, H. Park, Sparse nonnegative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis, Bioinformatics, 23 (2007), 1495–1502. https://doi.org/10.1093/bioinformatics/btm134 doi: 10.1093/bioinformatics/btm134
[13]	P. O. Hoyer, Non-negative matrix factorization with sparseness constraints, J. Mach. Learn. Res., 5 (2004), 1457–1469.
[14]	D. Wang, H. Lu, On-line learning parts-based representation via incremental orthogonal projective nonnegative matrix factorization, Signal Process., 93 (2013), 1608–1623. https://doi.org/10.1016/j.sigpro.2012.07.015 doi: 10.1016/j.sigpro.2012.07.015
[15]	N. Gillis, F. Glineur, A multilevel approach for nonnegative matrix factorization, J. Comput. Appl. Math., 236 (2012), 1708–1723. https://doi.org/10.1016/j.cam.2011.10.002 doi: 10.1016/j.cam.2011.10.002
[16]	V. P. Pauca, J. Piper, R. J. Plemmons, Nonnegative matrix factorization for spectral data analysis, Linear Algebra Appl., 416 (2006), 29–47. https://doi.org/10.1016/j.laa.2005.06.025 doi: 10.1016/j.laa.2005.06.025
[17]	M. W. Berry, M. Browne, A. N. Langville, V. P. Pauca, R. J. Plemmons, Algorithms and applications for approximate nonnegative matrix factorization, Comput. Stat. Data Anal., 52 (2007), 155–173. https://doi.org/10.1016/j.csda.2006.11.006 doi: 10.1016/j.csda.2006.11.006
[18]	N. Bertin, R. Badeau, E. Vincent, Enforcing harmonicity and smoothness in bayesian nonnegative matrix factorization applied to polyphonic music transcription, IEEE Trans. Audio Speech, 18 (2010), 538–549. https://doi.org/10.1109/TASL.2010.2041381 doi: 10.1109/TASL.2010.2041381
[19]	G. Zhou, Z. Yang, S. Xie, J. Yang, Online blind source separation using incremental nonnegative matrix factorization with volume constraint, IEEE Trans. Neural Networ., 22 (2011), 550–560. https://doi.org/10.1109/TNN.2011.2109396 doi: 10.1109/TNN.2011.2109396
[20]	S. Z. Li, X. W. Hou, H. J. Zhang, Q. S. Cheng, Learning spatially localized, parts-based representation, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001, I–I. https://doi.org/10.1109/CVPR.2001.990477
[21]	Y. Gao, G. Church, Improving molecular cancer class discovery through sparse nonnegative matrix factorization, Bioinformatics, 21 (2005), 3970–3975. https://doi.org/10.1093/bioinformatics/bti653 doi: 10.1093/bioinformatics/bti653
[22]	S. Jia, Y. Qian, Constrained nonnegative matrix factorization for hyperspectral unmixing, IEEE Trans. Geosci. Remote, 47 (2009), 161–173. https://doi.org/10.1109/TGRS.2008.2002882 doi: 10.1109/TGRS.2008.2002882
[23]	J. Tang, Z. Wan, Orthogonal dual graph-regularized nonnegative matrix factorization for co-clustering, J. Sci. Comput., 87 (2021), 66. https://doi.org/10.1007/s10915-021-01489-w doi: 10.1007/s10915-021-01489-w
[24]	C. Ding, T. Li, W. Peng, H. Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006,126–135. https://doi.org/10.1145/1150402.1150420
[25]	J. Yoo, S. Choi, Orthogonal nonnegative matrix tri-factorization for co-clustering: multiplicative updates on stiefel manifolds, Inform. Process. Manag., 46 (2010), 559–570. https://doi.org/10.1016/j.ipm.2009.12.007 doi: 10.1016/j.ipm.2009.12.007
[26]	B. Li, G. Zhou, A. Cichocki, Two efficient algorithms for approximately orthogonal nonnegative matrix factorization, IEEE Signal Process. Lett., 22 (2014), 843–846. https://doi.org/10.1109/LSP.2014.2371895 doi: 10.1109/LSP.2014.2371895
[27]	Y. Liu, X. Li, C. Liu, H. Liu, Structure-constrained low-rank and partial sparse representation with sample selection for image classification, Pattern Recogn., 59 (2016), 5–13. https://doi.org/10.1016/j.patcog.2016.01.026 doi: 10.1016/j.patcog.2016.01.026
[28]	F. R. Bach, M. I. Jordan, Spectral clustering for speech separation, In: Automatic speech and speaker recognition: large margin and kernel methods, Hoboken: John Wiley & Sons, Ltd., 2009,221–250. https://doi.org/10.1002/9780470742044.ch13
[29]	D. Cai, X. He, J. Han, T. Huang, Graph regularized nonnegative matrix factorization for data representation, IEEE Trans. Pattern Anal., 33 (2011), 1548–1560. https://doi.org/10.1109/TPAMI.2010.231 doi: 10.1109/TPAMI.2010.231
[30]	P. Li, J. Bu, L. Zhang, C. Chen, Graph-based local concept coordinate factorization, Knowl. Inf. Syst., 43 (2015), 103–126. https://doi.org/10.1007/s10115-013-0715-x doi: 10.1007/s10115-013-0715-x
[31]	W. Hu, K. Choi, P. Wang, Y. Jiang, S. Wang, Convex nonnegative matrix factorization with manifold regularization, Neural Networks, 63 (2015), 94–103. https://doi.org/10.1016/j.neunet.2014.11.007 doi: 10.1016/j.neunet.2014.11.007
[32]	Y. Meng, R. Shang, L. Jiao, W. Zhang, Y. Yuan, S. Yang, Feature selection based dual-graph sparse nonnegative matrix factorization for local discriminative clustering, Neurocomputing, 290 (2018), 87–99. https://doi.org/10.1016/j.neucom.2018.02.044 doi: 10.1016/j.neucom.2018.02.044
[33]	X. Long, H. Lu, Y. Peng, W. Li, Graph regularized discriminative nonnegative matrix factorization for face recognition, Multimed. Tools Appl., 72 (2014), 2679–2699. https://doi.org/10.1007/s11042-013-1572-z doi: 10.1007/s11042-013-1572-z
[34]	F. Shang, L. Jiao, F. Wang, Graph dual regularization nonnegative matrix factorization for co-clustering, Pattern Recogn., 45 (2012), 2237–2250. https://doi.org/10.1016/j.patcog.2011.12.015 doi: 10.1016/j.patcog.2011.12.015
[35]	C. Liu, S. Wu, R. Li, D. Jiang, H. Wong, Self-supervised graph completion for incomplete multi-view clustering, IEEE Trans. Knowl. Data Eng., 35 (2023), 9394–9406. https://doi.org/10.1109/TKDE.2023.3238416 doi: 10.1109/TKDE.2023.3238416
[36]	C. Liu, R. Li, H. Che, M. Leung, S. Wu, Z. Yu, et al., Beyond euclidean structures: collaborative topological graph learning for multiview clustering, IEEE Trans. Neur. Net. Lear., in press. https://doi.org/10.1109/TNNLS.2024.3489585
[37]	X. Yang, H. Che, M. Leung, C. Liu, S. Wen, Auto-weighted multi-view deep nonnegative matrix factorization with multi-kernel learning, IEEE Trans. Signal Inf. Pr., 11 (2024), 23–34. https://doi.org/10.1109/TSIPN.2024.3511262 doi: 10.1109/TSIPN.2024.3511262
[38]	H. Che, C. Li, M. Leung, D. Ouyang, X. Dai, S. Wen, Robust hypergraph regularized deep nonnegative matrix factorization for multi-view clustering, IEEE Transactions on Emerging Topics in Computational Intelligence, 9 (2025), 1817–1829. https://doi.org/10.1109/TETCI.2024.3451352 doi: 10.1109/TETCI.2024.3451352
[39]	G. Li, X. Zhang, S. Zheng, D. Li, Semi-supervised convex nonnegative matrix factorizations with graph regularized for image representation, Neurocomputing, 237 (2017), 1–11. https://doi.org/10.1016/j.neucom.2016.04.028 doi: 10.1016/j.neucom.2016.04.028
[40]	W. Zhang, M. Tan, Q. Sheng, L. Yao, Q. Shi, Efficient orthogonal nonnegative matrix factorization over stiefel manifold, Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 2016, 1743–1752. https://doi.org/10.1145/2983323.2983761
[41]	S. Wang, T. Chang, Y. Cui, J. Pang, Clustering by orthogonal nonnegative matrix factorization: a sequential non-convex penalty approach, Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019, 5576–5580. https://doi.org/10.1109/ICASSP.2019.8683466
[42]	Y. Qin, C. Jia, Y. Li, Community detection using nonnegative matrix factorization with orthogonal constraint, Proceedings of Eighth International Conference on Advanced Computational Intelligence (ICACI), 2016, 49–54. https://doi.org/10.1109/ICACI.2016.7449802
[43]	P. He, X. Xu, J. Ding, B. Fan, Low-rank nonnegative matrix factorization on stiefel manifold, Inform. Sciences, 514 (2020), 131–148. https://doi.org/10.1016/j.ins.2019.12.004 doi: 10.1016/j.ins.2019.12.004
[44]	H. Abe, H. Yadohisa, Orthogonal nonnegative matrix tri-factorization based on Tweedie distributions, Adv. Data Anal. Classif., 13 (2019), 825–853. https://doi.org/10.1007/s11634-018-0348-8 doi: 10.1007/s11634-018-0348-8
[45]	P. Li, J. Bu, C. Chen, C. Wang, D. Cai, Subspace learning via locally constrained A-optimal nonnegative projection, Neurocomputing, 115 (2013), 49–62. https://doi.org/10.1016/j.neucom.2012.12.029 doi: 10.1016/j.neucom.2012.12.029
[46]	P. Li, J. Bu, B. Xu, B. Wang, C. Chen, Locally discriminative spectral clustering with composite manifold, Neurocomputing, 119 (2013), 243–252. https://doi.org/10.1016/j.neucom.2013.03.034 doi: 10.1016/j.neucom.2013.03.034
[47]	P. Li, J. Bu, Y. Yang, R. Ji, C. Chen, D. Cai, Discriminative orthogonal nonnegative matrix factorization with flexibility for data representation, Expert Syst. Appl., 41 (2014), 1283–1293. https://doi.org/10.1016/j.eswa.2013.08.026 doi: 10.1016/j.eswa.2013.08.026
[48]	Z. Li, X. Wu, H. Peng, Nonnegative matrix factorization on orthogonal subspace, Pattern Recogn. Lett., 31 (2010), 905–911. https://doi.org/10.1016/j.patrec.2009.12.023 doi: 10.1016/j.patrec.2009.12.023
[49]	A. Tosyali, J. Kim, J. Choi, M. Jeong, Regularized asymmetric nonnegative matrix factorization for clustering in directed networks, Pattern Recogn. Lett., 125 (2019), 750–757. https://doi.org/10.1016/j.patrec.2019.07.005 doi: 10.1016/j.patrec.2019.07.005
[50]	D. Lee, H. S. Seung, Algorithms for nonnegative matrix factorization, Proceedings of the 14th International Conference on Neural Information Processing Systems, 2000,535–541.
[51]	A. Mirzal, A convergent algorithm for orthogonal nonnegative matrix factorization, J. Comput. Appl. Math., 260 (2014), 149–166. https://doi.org/10.1016/j.cam.2013.09.022 doi: 10.1016/j.cam.2013.09.022
[52]	S. Peng, W. Ser, B. Chen, L. Sun, Z. Lin, Robust nonnegative matrix factorization with local coordinate constraint for image clustering, Eng. Appl. Artif. Intel., 88 (2020), 103354. https://doi.org/10.1016/j.engappai.2019.103354 doi: 10.1016/j.engappai.2019.103354
[53]	G. Chen, C. Xu, J. Wang, J. W. Feng, J. Q. Feng, Graph regularization weighted nonnegative matrix factorization for link prediction in weighted complex network, Neurocomputing, 369 (2019), 50–60. https://doi.org/10.1016/j.neucom.2019.08.068 doi: 10.1016/j.neucom.2019.08.068
[54]	Q. Gu, J. Zhou, Co-clustering on manifolds, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009,359–368. https://doi.org/10.1145/1557019.1557063
[55]	Q. Wang, M. Chen, F. Nie, X. Li, Detecting coherent groups in crowd scenes by multiview clustering, IEEE Trans. Pattern Anal., 42 (2020), 46–58. https://doi.org/10.1109/TPAMI.2018.2875002 doi: 10.1109/TPAMI.2018.2875002
[56]	J. Guo, Z. Wan, A modified spectral prp conjugate gradient projection method for solving large-scale monotone equations and its application in compressed sensing, Math. Probl. Eng., 2019 (2019), 5261830. https://doi.org/10.1155/2019/5261830 doi: 10.1155/2019/5261830
[57]	T. Li, Z. Wan, New adaptive Barzilai-Borwein step size and its application in solving large-scale optimization problems, ANZIAM J., 61 (2019), 76–98. https://doi.org/10.1017/S1446181118000263 doi: 10.1017/S1446181118000263
[58]	J. Lv, S. Deng, Z. Wan, An efficient single-parameter scaling memoryless broyden-fletcher-goldfarb-shanno algorithm for solving large scale unconstrained optimization problems, IEEE Access, 8 (2020), 85664–85674. https://doi.org/10.1109/ACCESS.2020.2992340 doi: 10.1109/ACCESS.2020.2992340
[59]	A. Martinez, R. Benavente, The AR face database: Cvc technical report, 24, Commissioned report, 1998.
[60]	F. Li, R. Fergus, P. Perona, Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories, Proceedings of Conference on Computer Vision and Pattern Recognition Workshop, 2004,178–178. https://doi.org/10.1109/CVPR.2004.383
[61]	J. D. Wang, J. Wang, Q. Ke, G. Zeng, S. Li, Fast approximate k-means via cluster closures, In: Multimedia data mining and analytics: disruptive innovation, Cham: Springer, 2015,373–395. https://doi.org/10.1007/978-3-319-14998-1_17
[62]	P. O. Hoyer, Non-negative sparse coding, Proceedings of the 12th IEEE Workshop on Neural Networks for Signal Processing, 2002,557–565. https://doi.org/10.1109/NNSP.2002.1030067
[63]	J. Huang, F. Nie, H. Huang, C. Ding, Robust manifold nonnegative matrix factorization, ACM Trans. Knowl. Discov. D., 8 (2014), 11. https://doi.org/10.1145/2601434 doi: 10.1145/2601434
[64]	D. Tolić, N. Antulov-Fantulin, I. Kopriva, A nonlinear orthogonal nonnegative matrix factorization approach to subspace clustering, Pattern Recogn., 82 (2018), 40–55. https://doi.org/10.1016/j.patcog.2018.04.029 doi: 10.1016/j.patcog.2018.04.029
[65]	V. Leplat, A. Ang, N. Gillis, Minimum-volume rank-deficient nonnegative matrix factorizations, Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019, 3402–3406. https://doi.org/10.1109/ICASSP.2019.8682280
[66]	C. Peng, Z. Kang, Y. Hu, J. Cheng, Q. Cheng, Nonnegative matrix factorization with integrated graph and feature learning, ACM Trans. Intel. Syst. Tec., 8 (2017), 42. https://doi.org/10.1145/2987378 doi: 10.1145/2987378
[67]	S. Boyd, L. Vandenberghe, Convex optimization, Cambridge: Cambridge University Press, 2004. https://doi.org/10.1017/CBO9780511804441

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)