Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem. (English) Zbl 1486.90156
Summary: In this paper, we consider the symmetric multi-type non-negative matrix tri-factorization problem (SNMTF), which attempts to factorize several symmetric non-negative matrices simultaneously. This can be considered as a generalization of the classical non-negative matrix tri-factorization problem and includes a non-convex objective function which is a multivariate sixth degree polynomial and a has convex feasibility set. It has a special importance in data science, since it serves as a mathematical model for the fusion of different data sources in data clustering. We develop four methods to solve the SNMTF. They are based on four theoretical approaches known from the literature: the fixed point method (FPM), the block-coordinate descent with projected gradient (BCD), the gradient method with exact line search (GM-ELS) and the adaptive moment estimation method (ADAM). For each of these methods we offer a software implementation: for the former two methods we use Matlab and for the latter Python with the TensorFlow library. We test these methods on three data-sets: the synthetic data-set we generated, while the others represent real-life similarities between different objects. Extensive numerical results show that with sufficient computing time all four methods perform satisfactorily and ADAM most often yields the best mean square error (MSE). However, if the computation time is limited, FPM gives the best MSE because it shows the fastest convergence at the beginning. All data-sets and codes are publicly available on our GitLab profile.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C90 | Applications of mathematical programming |
Keywords:
non-negative matrix factorization; fixed point method; block coordinate descent; projected gradient method; ADAMReferences:
| [1] | Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G.S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., Zheng, X.: TensorFlow: Large-scale machine learning on heterogeneous systems (2015). http://tensorflow.org/. Software available from tensorflow.org |
| [2] | Altschul, SF; Gish, W.; Miller, W.; Myers, EW; Lipman, DJ, Basic local alignment search tool, J. Mol. Biol., 215, 3, 403-410 (1990) · doi:10.1016/S0022-2836(05)80360-2 |
| [3] | Asadi, S.; Povh, J., A block coordinate descent-based projected gradient algorithm for orthogonal non-negative matrix factorization, Mathematics, 9, 5, 540 (2021) · doi:10.3390/math9050540 |
| [4] | Atwood, GR; Foster, WW, Transformation of bounded variables in simplex optimization techniques, Ind. Eng. Chem. Process Des. Dev., 12, 4, 485-486 (1973) · doi:10.1021/i260048a019 |
| [5] | Bergstra, J.; Bengio, Y., Random search for hyper-parameter optimization, J. Mach. Learn. Res., 13, 281-305 (2012) · Zbl 1283.68282 |
| [6] | Bertsekas, D.: Nonlinear Programming. Athena scientific optimization and computation series. Athena Scientific (2016). https://books.google.si/books?id=TwOujgEACAAJ |
| [7] | Boutsidis, C.; Gallopoulos, E., Svd based initialization: a head start for nonnegative matrix factorization, Pattern Recogn., 41, 4, 1350-1362 (2008) · Zbl 1131.68084 · doi:10.1016/j.patcog.2007.09.010 |
| [8] | Cichocki, A.; Zdunek, R.; Phan, AH; Amari, SI, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-Way Data Analysis and Blind Source Separation (2009), London: Wiley, London · doi:10.1002/9780470747278 |
| [9] | Davis, D.; Drusvyatskiy, D.; Kakade, S.; Lee, JD, Stochastic subgradient method converges on tame functions, Found. Comput. Math., 20, 1, 119-154 (2020) · Zbl 1433.65141 · doi:10.1007/s10208-018-09409-5 |
| [10] | Del Buono, N.; Pio, G., Non-negative matrix tri-factorization for co-clustering: an analysis of the block matrix, Inf. Sci., 301, 13-26 (2015) · doi:10.1016/j.ins.2014.12.058 |
| [11] | Dickinson, PJ; Gijben, L., On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57, 2, 403-415 (2014) · Zbl 1330.90103 · doi:10.1007/s10589-013-9594-z |
| [12] | Ding, C., Li, T., Peng, W., Park, H.: Orthogonal nonnegative matrix t-factorizations for clustering. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 126-135. ACM (2006) |
| [13] | Feng, S., Krim, H., Kogan, I.: 3D face recognition using euclidean integral invariants signature. In: IEEE/SP 14th Workshop on Statistical Signal Processing, 2007. SSP ’07, pp. 156-160 (2007) |
| [14] | Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, A.; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, H., Qplib: a library of quadratic programming instances, Math. Program. Comput., 11, 2, 237-265 (2019) · Zbl 1435.90099 · doi:10.1007/s12532-018-0147-4 |
| [15] | Gillis, N.; Suykens, J.; Signoretto, M.; Argyriou, A., The why and how of nonnegative matrix factorization, Regularization, Optimization, Kernels, and Support Vector Machines, 257-291 (2015), New York: Chapman & Hall/CRC, New York |
| [16] | Gligorijević, V.; Janjić, V.; Pržulj, N., Integration of molecular network data reconstructs gene ontology, Bioinformatics, 30, 17, i594-i600 (2014) · doi:10.1093/bioinformatics/btu470 |
| [17] | Gligorijević, V.; Malod-Dognin, N.; Pržulj, N., Fuse: multiple network alignment via data fusion, Bioinformatics, 32, 8, 1195-1203 (2015) · doi:10.1093/bioinformatics/btv731 |
| [18] | Gligorijević, V.; Malod-Dognin, N.; Pržulj, N., Integrative methods for analyzing big data in precision medicine, Proteomics, 16, 5, 741-758 (2016) · doi:10.1002/pmic.201500396 |
| [19] | Gligorijević, V., Malod-Dognin, N., Pržulj, N.: Patient-specific data fusion for cancer stratification and personalised treatment. In: Proceedings of the Pacific Symposium Biocomputing, pp. 321-332. World Scientific (2016) |
| [20] | Ho, N.D.: Nonnegative matrix factorization algorithms and applications. Ph.D. thesis, Université catholique de Louvain (2008) |
| [21] | Hofmann, T.; Buhmann, JM, Pairwise data clustering by deterministic annealing, IEEE Trans. Pattern Anal. Mach. Intell., 19, 1, 1-14 (1997) · doi:10.1109/34.566806 |
| [22] | Hrga, T., Hribar, R., Povh, J.: Symmetric NMTF (2020). https://repo.ijs.si/hribarr/symmetric-nmtf |
| [23] | Huang, K.; Sidiropoulos, ND; Swami, A., Non-negative matrix factorization revisited: uniqueness and algorithm for symmetric decomposition, IEEE Trans. Signal Process., 62, 1, 211-224 (2013) · Zbl 1393.15016 · doi:10.1109/TSP.2013.2285514 |
| [24] | Jain, AK; Zongker, D., Representation and recognition of handwritten digits using deformable templates, IEEE Trans. Pattern Anal. Mach. Intell., 19, 12, 1386-1391 (1997) · doi:10.1109/34.643899 |
| [25] | Kim, H.; Park, H., Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method, SIAM J. Matrix Anal. Appl., 30, 2, 713-730 (2008) · Zbl 1162.65354 · doi:10.1137/07069239X |
| [26] | Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014) |
| [27] | Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: Advances in Neural Information Processing Systems, pp. 556-562 (2001) |
| [28] | Lin, CJ, Projected gradient methods for nonnegative matrix factorization, Neural Comput., 19, 10, 2756-2779 (2007) · Zbl 1173.90583 · doi:10.1162/neco.2007.19.10.2756 |
| [29] | Liu, K., Wang, H.: High-order co-clustering via strictly orthogonal and symmetric l1-norm nonnegative matrix tri-factorization. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 2454-2460. International Joint Conferences on Artificial Intelligence Organization (2018). doi:10.24963/ijcai.2018/340 |
| [30] | Lu, S.; Hong, M.; Wang, Z., A nonconvex splitting method for symmetric nonnegative matrix factorization: convergence analysis and optimality, IEEE Trans. Signal Process., 65, 12, 3120-3135 (2017) · Zbl 1414.94392 · doi:10.1109/TSP.2017.2679687 |
| [31] | Ma, X.; Dong, D., Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks, IEEE Trans. Knowl. Data Eng., 29, 5, 1045-1058 (2017) · doi:10.1109/TKDE.2017.2657752 |
| [32] | Malick, J.; Povh, J.; Rendl, F.; Wiegele, A., Regularization methods for semidefinite programming, SIAM J. Optim., 20, 1, 336-356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575 |
| [33] | Malod-Dognin, N.; Petschnigg, J.; Windels, SF; Povh, J.; Hemingway, H.; Ketteler, R.; Pržulj, N., Towards a data-integrated cell, Nat. Commun., 10, 1, 1-13 (2019) · doi:10.1038/s41467-018-07882-8 |
| [34] | MATLAB: 9.6.0.1072779 (R2019a). The MathWorks Inc., Natick, Massachusetts (2019) |
| [35] | Mirzal, A., A convergent algorithm for orthogonal nonnegative matrix factorization, J. Comput. Appl. Math., 260, 149-166 (2014) · Zbl 1293.65066 · doi:10.1016/j.cam.2013.09.022 |
| [36] | Mirzal, A.: A convergent algorithm for bi-orthogonal nonnegative matrix tri-factorization. arXiv preprint arXiv:1710.11478 (2017) · Zbl 1293.65066 |
| [37] | Obayashi, T.; Kagaya, Y.; Aoki, Y.; Tadaka, S.; Kinoshita, K., Coxpresdb v7: a gene coexpression database for 11 animal species supported by 23 coexpression platforms for technical evaluation and evolutionary inference, Nucleic Acids Res., 47, D1, D55-D62 (2019) · doi:10.1093/nar/gky1155 |
| [38] | Oughtred, R.; Stark, C.; Breitkreutz, BJ; Rust, J.; Boucher, L.; Chang, C.; Kolas, N.; Odonnell, L.; Leung, G.; McAdam, R., The biogrid interaction database: 2019 update, Nucleic Acids Res., 47, D1, D529-D541 (2019) · doi:10.1093/nar/gky1079 |
| [39] | Park, S., Hwang, T.H.: Bayesian semi-nonnegative tri-matrix factorization to identify pathways associated with cancer types. arXiv preprint arXiv:1712.00520 (2017) |
| [40] | Park, S.; Kar, N.; Cheong, JH; Hwang, TH, Bayesian semi-nonnegative matrix tri-factorization to identify pathways associated with cancer phenotypes, Pacific Symp. Biocomput., 2020, 427-438 (2020) · doi:10.1142/9789811215636_0038 |
| [41] | Philips, S.; Pitton, J.; Atlas, L., Perceptual feature identification for active sonar echoes, Oceans, 2006, 1-6 (2006) |
| [42] | Povh, J.; Rendl, F.; Wiegele, A., A boundary point method to solve semidefinite programs, Computing, 78, 3, 277-286 (2006) · Zbl 1275.90055 · doi:10.1007/s00607-006-0182-2 |
| [43] | Pržulj, N.; Malod-Dognin, N., Network analytics in the age of big data, Science, 353, 6295, 123-124 (2016) · doi:10.1126/science.aah3449 |
| [44] | Reddi, S.J., Kale, S., Kumar, S.: On the convergence of Adam and beyond. arXiv preprint arXiv:1904.09237 (2019) |
| [45] | Rumelhart, DE; Hinton, GE; Williams, RJ, Learning representations by back-propagating errors, Nature, 323, 6088, 533-536 (1986) · Zbl 1369.68284 · doi:10.1038/323533a0 |
| [46] | Saito, S.; Hirata, Y.; Sasahara, K.; Suzuki, H., Tracking time evolution of collective attention clusters in twitter: time evolving nonnegative matrix factorisation, PLOS ONE, 10, 9, 1-17 (2015) · doi:10.1371/journal.pone.0139085 |
| [47] | Schleif, F., Gisbrecht, A.: Data analysis of (non-)metric proximities at linear costs. In: E.R. Hancock, M. Pelillo (eds.) Similarity-Based Pattern Recognition-Second International Workshop, SIMBAD 2013, York, UK, July 3-5, 2013. Proceedings, Lecture Notes in Computer Science, vol. 7953, pp. 59-74. Springer (2013). doi:10.1007/978-3-642-39140-8_4 · Zbl 1277.68012 |
| [48] | Someya, H.; Yamamura, M., A robust real-coded evolutionary algorithm with toroidal search space conversion, Soft. Comput., 9, 4, 254-269 (2005) · Zbl 1066.68033 · doi:10.1007/s00500-004-0378-3 |
| [49] | Stanfill, C.; Waltz, D., Toward memory-based reasoning, ACM Commun., 29, 12, 1213-1228 (1986) · doi:10.1145/7902.7906 |
| [50] | Szklarczyk, D.; Gable, AL; Lyon, D.; Junge, A.; Wyder, S.; Huerta-Cepas, J.; Simonovic, M.; Doncheva, NT; Morris, JH; Bork, P., String v11: protein-protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets, Nucleic Acids Res., 47, D1, D607-D613 (2019) · doi:10.1093/nar/gky1131 |
| [51] | Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl., 109, 3, 475-494 (2001) · Zbl 1006.65062 · doi:10.1023/A:1017501703105 |
| [52] | Tsutsui, S.: Multi-parent recombination in genetic algorithms with search space boundary extension by mirroring. In: International Conference on Parallel Problem Solving from Nature, pp. 428-437. Springer (1998) |
| [53] | Vavasis, SA, On the complexity of nonnegative matrix factorization, SIAM J. Optim., 20, 3, 1364-1377 (2009) · Zbl 1206.65130 · doi:10.1137/070709967 |
| [54] | Čopar, A.; Zupan, B.; Žitnik, M., Fast optimization of non-negative matrix tri-factorization, PLoS ONE, 14, 6, 1-15 (2019) · doi:10.1371/journal.pone.0217994 |
| [55] | Wang, F., Li, T., Zhang, C.: Semi-supervised clustering via matrix factorization. In: Proceedings of the 2008 SIAM International Conference on Data Mining, pp. 1-12. SIAM (2008) |
| [56] | Wang, F., Tong, H., Lin, C.: Towards evolutionary nonnegative matrix factorization. In: AAAI-11 / IAAI-11-Proceedings of the 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, pp. 501-506 (2011) |
| [57] | Wang, H., Huang, H., Ding, C.: Simultaneous clustering of multi-type relational data via symmetric nonnegative matrix tri-factorization. In: Proceedings of the 20th ACM international conference on Information and knowledge management, pp. 279-284. ACM (2011) |
| [58] | Wang, H.; Huang, H.; Ding, C.; Nie, F., Predicting protein-protein interactions from multimodal biological data sources via nonnegative matrix tri-factorization, J. Comput. Biol., 20, 4, 344-358 (2013) · doi:10.1089/cmb.2012.0273 |
| [59] | Wright, SJ, Coordinate descent algorithms, Math. Program., 151, 1, 3-34 (2015) · Zbl 1317.49038 · doi:10.1007/s10107-015-0892-3 |
| [60] | Yu, W.; Wang, W.; Jiao, P.; Li, X., Evolutionary clustering via graph regularized nonnegative matrix factorization for exploring temporal networks, Knowl.-Based Syst., 167, 1-10 (2019) · doi:10.1016/j.knosys.2019.01.024 |
| [61] | Žitnik, M.; Janjić, V.; Larminie, C.; Zupan, B.; Pržulj, N., Discovering disease-disease associations by fusing systems-level molecular data, Sci. Rep., 3, 3202 (2013) · doi:10.1038/srep03202 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
