×

Latent space model for higher-order networks and generalized tensor decomposition. (English) Zbl 07792618

Summary: We introduce a unified framework, formulated as general latent space models, to study complex higher-order network interactions among multiple entities. Our framework covers several popular models in recent network analysis literature, including mixture multi-layer latent space model and hypergraph latent space model. We formulate the relationship between the latent positions and the observed data via a generalized multilinear kernel as the link function. While our model enjoys decent generality, its maximum likelihood parameter estimation is also convenient via a generalized tensor decomposition procedure. We propose a novel algorithm using projected gradient descent on Grassmannians. We also develop original theoretical guarantees for our algorithm. First, we show its linear convergence under mild conditions. Second, we establish finite-sample statistical error rates of latent position estimation, determined by the signal strength, degrees of freedom and the smoothness of link function, for both general and specific latent space models. We demonstrate the effectiveness of our method on synthetic data. We also showcase the merit of our method on two real-world datasets that are conventionally described by different specific models in producing meaningful and interpretable parameter estimations and accurate link prediction. for this article are available online.

MSC:

62-XX Statistics

References:

[1] Arroyo, J.; Athreya, A.; Cape, J.; Chen, G.; Priebe, C. E.; Vogelstein, J. T., “Inference for Multiple Heterogeneous Networks with a Common Invariant Subspace,”, Journal of Machine Learning Research, 22, 1-49 (2021) · Zbl 07415085
[2] Athreya, A.; Fishkind, D. E.; Tang, M.; Priebe, C. E.; Park, Y.; Vogelstein, J. T.; Levin, K.; Lyzinski, V.; Qin, Y., “Statistical Inference on Random Dot Product Graphs: A Survey,”, The Journal of Machine Learning Research, 18, 8393-8484 (2017) · Zbl 1473.05279
[3] Balasubramanian, K., Nonparametric Modeling of Higher-Order Interactions via Hypergraphons, arXiv preprint arXiv:2105.2105.08678 (2021) · Zbl 07415089
[4] Benson, A. R.; Gleich, D. F.; Leskovec, J., “Higher-Order Organization of Complex Networks,”, Science, 353, 163-166 (2016) · doi:10.1126/science.aad9029
[5] Bhattacharjee, M.; Banerjee, M.; Michailidis, G., Change Point Estimation in a Dynamic Stochastic Block Model, arXiv preprint arXiv:1812.03090 (2018)
[6] Bick, C.; Gross, E.; Harrington, H. A.; Schaub, M. T., What are Higher-Order Networks?, arXiv preprint arXiv:2104.11329 (2021)
[7] Cai, J.-F.; Li, J.; Xia, D., “Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization,”, arXiv preprint (2021) · Zbl 07784931 · doi:10.1080/01621459.2022.2063131
[8] Cai, T. T.; Zhang, A., “Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics,”, The Annals of Statistics, 46, 60-89 (2018) · Zbl 1395.62122 · doi:10.1214/17-AOS1541
[9] Cardillo, A.; Gómez-Gardenes, J.; Zanin, M.; Romance, M.; Papo, D.; Del Pozo, F.; Boccaletti, S., “Emergence of Network Features from Multiplexity,”, Scientific Reports, 3, 1-6 (2013) · doi:10.1038/srep01344
[10] Cardillo, A.; Zanin, M.; Gómez-Gardenes, J.; Romance, M.; del Amo, A. J. G.; Boccaletti, S., “Modeling the Multi-Layer Nature of the European Air Transport Network: Resilience and Passengers Re-Scheduling Under Random Failures,”, The European Physical Journal Special Topics, 215, 23-33 (2013) · doi:10.1140/epjst/e2013-01712-8
[11] Chen, H.; Zhang, N., “Graph-based Change-Point Detection,”, Annals of Statistics, 43, 139-176 (2015) · Zbl 1308.62090
[12] Chen, Y.; Li, C.; Xu, G., A Note on Statistical Inference for Noisy Incomplete 1-bit Matrix, arXiv preprint arXiv:2105.01769 (2021)
[13] Chien, I.; Lin, C.-Y.; Wang, I.-H., “Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms,”, 871-879 (2018)
[14] Davenport, M. A.; Plan, Y.; Van Den Berg, E.; Wootters, M., “1-Bit Matrix Completion,”, Information and Inference: A Journal of the IMA, 3, 189-223 (2014) · Zbl 1309.62124 · doi:10.1093/imaiai/iau006
[15] Dickison, M. E.; Magnani, M.; Rossi, L., Multilayer Social Networks (2016), Cambridge: Cambridge University Press, Cambridge
[16] Edelman, A.; Arias, T. A.; Smith, S. T., “The Geometry of Algorithms with Orthogonality Constraints,”, SIAM journal on Matrix Analysis and Applications, 20, 303-353 (1998) · Zbl 0928.65050 · doi:10.1137/S0895479895290954
[17] Ghoshal, G.; Zlatić, V.; Caldarelli, G.; Newman, M. E., “Random Hypergraphs and their Applications,”, Physical Review E, 79, 066118 (2009) · doi:10.1103/PhysRevE.79.066118
[18] Ghoshdastidar, D.; Dukkipati, A., “Consistency of Spectral Partitioning of Uniform Hypergraphs Under Planted Partition Model, Advances in Neural Information Processing Systems, 27, 397-405 (2014)
[19] Ghoshdastidar, D.; Dukkipati, A., “A Provable Generalized Tensor Spectral Method for Uniform Hypergraph Partitioning,”, 400-409 (2015)
[20] Ghoshdastidar, D.; Dukkipati, A., “Consistency of Spectral Hypergraph Partitioning Under Planted Partition Model,”, Annals of Statistics, 45, 289-315 (2017) · Zbl 1360.62330
[21] Goldenberg, A.; Zheng, A. X.; Fienberg, S. E.; Airoldi, E. M., “A Survey of Statistical Network Models.”, Foundations and Trends® in Machine Learning, 2, 129-233 (2010) · Zbl 1184.68030 · doi:10.1561/2200000005
[22] Han, R.; Willett, R.; Zhang, A., An Optimal Statistical and Computational Framework for Generalized Tensor Estimation, arXiv preprint arXiv:2002.11255 (2020)
[23] Hoff, P. D.; Raftery, A. E.; Handcock, M. S., “Latent Space Approaches to Social Network Analysis,”, Journal of the American Statistical Association, 97, 1090-1098 (2002) · Zbl 1041.62098 · doi:10.1198/016214502388618906
[24] Holland, P. W.; Laskey, K. B.; Leinhardt, S., “Stochastic Blockmodels: First Steps,”, Social Networks, 5, 109-137 (1983) · doi:10.1016/0378-8733(83)90021-7
[25] Hore, V.; Viñuela, A.; Buil, A.; Knight, J.; McCarthy, M. I.; Small, K.; Marchini, J., “Tensor Decomposition for Multiple-Tissue Gene Expression Experiments,”, Nature Genetics, 48, 1094-1100 (2016) · doi:10.1038/ng.3624
[26] Hu, J.; Lee, C.; Wang, M., “Supervised Tensor Decomposition with Features on Multiple Modes,”, arXiv e-prints, arXiv-1910 (2019)
[27] Ji, P.; Jin, J., “Coauthorship and Citation Networks for Statisticians,”, The Annals of Applied Statistics, 10, 1779-1812 (2016) · Zbl 1454.62541 · doi:10.1214/15-AOAS896
[28] Jing, B.-Y.; Li, T.; Lyu, Z.; Xia, D., “Community Detection on Mixture Multi-Layer Networks via Regularized Tensor Decomposition, The Annals of Statistics, 49, 3181-3205 (2021) · Zbl 1486.62185 · doi:10.1214/21-AOS2079
[29] Ke, Z. T.; Shi, F.; Xia, D., Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration, arXiv preprint arXiv:1909.06503 (2019)
[30] Keshavan, R. H.; Montanari, A.; Oh, S., “Matrix Completion from a Few Entries,”, IEEE Transactions on Information Theory, 56, 2980-2998 (2010) · Zbl 1366.62111 · doi:10.1109/TIT.2010.2046205
[31] Kim, C.; Bandeira, A. S.; Goemans, M. X., Stochastic Block Model for Hypergraphs: Statistical Limits and a Semidefinite Programming Approach, arXiv preprint arXiv:1807.02884 (2018)
[32] Kivelä, M.; Arenas, A.; Barthelemy, M.; Gleeson, J. P.; Moreno, Y.; Porter, M. A., “Multilayer Networks,”, Journal of Complex Networks, 2, 203-271 (2014) · doi:10.1093/comnet/cnu016
[33] Kolda, T. G., Multilinear Operators for Higher-Order Decompositions (2006)
[34] Kolda, T. G.; Bader, B. W., “Tensor Decompositions and Applications,”, SIAM Review, 51, 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X
[35] Larremore, D. B.; Clauset, A.; Buckee, C. O., “A Network Approach to Analyzing Highly Recombinant Malaria Parasite Genes,”, PLOS Computational Biology, 9, e1003268 (2013) · doi:10.1371/journal.pcbi.1003268
[36] Le, C. M.; Levin, K.; Levina, E., “Estimating a Network from Multiple Noisy Realizations,”, Electronic Journal of Statistics, 12, 4697-4740 (2018) · Zbl 1409.62115 · doi:10.1214/18-EJS1521
[37] Lee, S. H.; Magallanes, J. M.; Porter, M. A., “Time-Dependent Community Structure in Legislation Cosponsorship Networks in the Congress of the Republic of Peru,”, Journal of Complex Networks, 5, 127-144 (2017) · doi:10.1093/comnet/cnw004
[38] Lei, J.; Chen, K.; Lynch, B., “Consistent Community Detection in Multi-Layer Network Data,”, Biometrika, 107, 61-73 (2020) · Zbl 1435.62235 · doi:10.1093/biomet/asz068
[39] Lei, J.; Rinaldo, A., “Consistency of Spectral Clustering in Stochastic Block Models,”, Annals of Statistics, 43, 215-237 (2015) · Zbl 1308.62041
[40] Levin, K.; Athreya, A.; Tang, M.; Lyzinski, V.; Park, Y.; Priebe, C. E., A Central Limit Theorem for An Omnibus Embedding of Multiple Random Graphs and Implications for Multiscale Network Inference, arXiv preprint arXiv:1705.09355 (2017)
[41] Ma, Z.; Ma, Z.; Yuan, H., Universal latent space model fitting for large networks with edge covariates, Journal of Machine Learning Research, 21, 4, 1-67 (2020) · Zbl 1497.68432
[42] MacDonald, P. W.; Levina, E.; Zhu, J., Latent Space Models for Multiplex Networks with Shared Structure, arXiv preprint arXiv:2012.14409 (2020) · Zbl 07582646
[43] Matias, C.; Miele, V., “Statistical Clustering of Temporal Networks through a Dynamic Stochastic Block Model,”, Journal of the Royal Statistical Society, Series B, 79, 1119-1141 (2017) · Zbl 1373.62312 · doi:10.1111/rssb.12200
[44] Newman, M., Networks (2018), Oxford: Oxford University Press, Oxford · Zbl 1391.94006
[45] Newman, M. E., The Structure and Dynamics of Networks, The Structure of Scientific Collaboration Networks, 221-226 (2011), Princeton: Princeton University Press, Princeton
[46] Pal, S.; Zhu, Y., Community Detection in the Sparse Hypergraph Stochastic Block Model, arXiv preprint arXiv:1904.05981 (2019)
[47] Park, Y.; Priebe, C. E.; Youssef, A., “Anomaly Detection in Time Series of Graphs Using Fusion of Graph Invariants,”, IEEE Journal of Selected Topics in Signal Processing, 7, 67-75 (2012) · doi:10.1109/JSTSP.2012.2233712
[48] Paul, S.; Chen, Y., “A Random Effects Stochastic Block Model for Joint Community Detection in Multiple Networks with Applications to Neuroimaging,”, Annals of Applied Statistics, 14, 993-1029 (2020) · Zbl 1446.62287
[49] Paul, S.; Chen, Y., “Spectral and Matrix Factorization Methods for Consistent Community Detection in Multi-Layer Networks,”, The Annals of Statistics, 48, 230-250 (2020) · Zbl 1440.62091
[50] Pensky, M., “Dynamic Network Models and Graphon Estimation,”, Annals of Statistics, 47, 2378-2403 (2019) · Zbl 1466.62337
[51] Pensky, M.; Zhang, T., “Spectral Clustering in the Dynamic Stochastic Block Model,”, Electronic Journal of Statistics, 13, 678-709 (2019) · Zbl 1415.62046 · doi:10.1214/19-EJS1533
[52] Rohe, K.; Chatterjee, S.; Yu, B., Spectral clustering and the high-dimensional stochastic blockmodel, Annals of Statistics, 39, 4, 1878-1915 (2011) · Zbl 1227.62042
[53] Sarkar, P.; Moore, A. W., “Dynamic Social Network Analysis using Latent Space Models,”, Acm Sigkdd Explorations Newsletter, 7, 31-40 (2005) · doi:10.1145/1117454.1117459
[54] Sewell, D. K.; Chen, Y., “Latent Space Models for Dynamic Networks,”, Journal of the American Statistical Association, 110, 1646-1657 (2015) · Zbl 1373.62580 · doi:10.1080/01621459.2014.988214
[55] Tang, R.; Tang, M.; Vogelstein, J. T.; Priebe, C. E., Robust Estimation from Multiple Graphs Under Gross Error Contamination, arXiv preprint arXiv:1707.03487 (2017)
[56] Wang, D.; Yu, Y.; Rinaldo, A., Optimal Change Point Detection and Localization in Sparse Dynamic Networks, arXiv preprint arXiv:1809.09602 (2018)
[57] Wang, H.; Tang, M.; Park, Y.; Priebe, C. E., “Locality Statistics for Anomaly Detection in Time Series of Graphs,”, IEEE Transactions on Signal Processing, 62, 703-717 (2013) · Zbl 1394.94790 · doi:10.1109/TSP.2013.2294594
[58] Wang, L.; Zhang, Z.; Dunson, D., “Common and Individual Structure of Brain Networks,”, The Annals of Applied Statistics, 13, 85-112 (2019) · Zbl 1417.62332 · doi:10.1214/18-AOAS1193
[59] Wang, M.; Li, L., “Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality,”, Journal of Machine Learning Research, 21, 1-38 (2020) · Zbl 1525.68127
[60] Wang, Y.; Chakrabarti, A.; Sivakoff, D.; Parthasarathy, S., Fast Change Point Detection on Dynamic Social Networks, arXiv preprint arXiv:1705.07325 (2017)
[61] Wilson, J. D.; Stevens, N. T.; Woodall, W. H., “Modeling and Detecting Change in Temporal Networks via the Degree Corrected Stochastic Block Model,”, Quality and Reliability Engineering International, 35, 1363-1378 (2019) · doi:10.1002/qre.2520
[62] Xia, D., Normal Approximation and Confidence Region of Singular Subspaces, arXiv preprint arXiv:1901.00304 (2019)
[63] Xia, D.; Yuan, M., “On Polynomial Time Methods for Exact Low-Rank Tensor Completion,”, Foundations of Computational Mathematics, 19, 1265-1313 (2019) · Zbl 1436.15031 · doi:10.1007/s10208-018-09408-6
[64] Xu, K., Artificial Intelligence and Statistics, Stochastic Block Transition Models for Dynamic Networks, 1079-1087, (2015), PMLR
[65] Yuan, M.; Liu, R.; Feng, Y.; Shang, Z., Testing Community Structures for Hypergraphs, arXiv preprint arXiv:1810.04617 (2018)
[66] Zhang, A.; Xia, D., “Tensor SVD: Statistical and Computational Limits,”, IEEE Transactions on Information Theory, 64, 7311-7338 (2018) · Zbl 1432.62176 · doi:10.1109/TIT.2018.2841377
[67] Zhang, J.; Cao, J., “Finding Common Modules in a Time-Varying Network with Application to the Drosophila Melanogaster Gene Regulation Network, Journal of the American Statistical Association, 112, 994-1008 (2017) · doi:10.1080/01621459.2016.1260465
[68] Zhang, X.; Xu, G.; Zhu, J., “Joint Latent Space Models for Network Data with High-Dimensional Node Variables,”, Biometrika, 109, 707-720 (2021) · Zbl 07582647 · doi:10.1093/biomet/asab063
[69] Zhang, X.; Xue, S.; Zhu, J., “A Flexible Latent Space Model for Multilayer Networks,”, 11288-11297 (2020), PMLR
[70] Zhang, Y.; Levina, E.; Zhu, J., “Community Detection in Networks with Node Features,”, Electronic Journal of Statistics, 10, 3153-3178 (2016) · Zbl 1359.62271 · doi:10.1214/16-EJS1206
[71] Zhang, Y.; Levina, E.; Zhu, J., “Detecting Overlapping Communities in Networks using Spectral Methods,”, SIAM Journal on Mathematics of Data Science, 2, 265-283 (2020) · Zbl 1484.62073
[72] Zhao, Y.; Wu, Y.-J.; Levina, E.; Zhu, J., “Link Prediction for Partially Observed Networks,”, Journal of Computational and Graphical Statistics, 26, 725-733 (2017) · doi:10.1080/10618600.2017.1286243
[73] Zhao, Z.; Chen, L.; Lin, L., Change-Point Detection in Dynamic Networks via Graphon Estimation, arXiv preprint arXiv:1908.01823 (2019)
[74] Zhen, Y.; Wang, J., “Community Detection in General Hypergraph via Graph Embedding,”, arXiv preprint arXiv:2103.15035 (2021) · Zbl 07751795 · doi:10.1080/01621459.2021.2002157
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.