A probabilistic view of latent space graphs and phase transitions. (English) Zbl 1515.05160
Summary: We study random graphs with latent geometric structure, where the probability of each edge depends on the underlying random positions corresponding to the two endpoints. We consider the setting where this conditional probability is a general monotone increasing function of the inner product of two vectors; such a function can naturally be viewed as the cumulative distribution function of some independent random variable. A one-parameter family of random graphs, characterized by the variance of this random variable, that smoothly interpolates between a random dot product graph and an Erdős-Rényi random graph, is investigated. Focusing on the dense regime, we prove phase transitions of detecting geometry in these graphs, in terms of the dimension of the underlying geometric space and the variance parameter: When the dimension is high or the variance is large, the graph is similar to an Erdős-Rényi graph with the same edge density; in other parameter regimes, there is a computationally efficient signed triangle statistic that can distinguish them. The proofs make use of information-theoretic inequalities and concentration of measure phenomena.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62F15 | Bayesian inference |
| 60C05 | Combinatorial probability |
Keywords:
high-dimensional geometric structure; random dot product graph; random graph; signed triangleReferences:
| [1] | Athreya, A., Fishkind, D.E., Tang, M., Priebe, C.E., Park, Y., Vogelstein, J.T., Levin, K., Lyzinski, V., Qin, Y. and Sussman, D.L. (2017). Statistical inference on random dot product graphs: A survey. J. Mach. Learn. Res. 18 Paper No. 226, 92. · Zbl 1473.05279 |
| [2] | Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford: Oxford Univ. Press. With a foreword by Michel Ledoux. 10.1093/acprof:oso/9780199535255.001.0001 · Zbl 1279.60005 |
| [3] | Brennan, M., Bresler, G. and Huang, B. (2021). De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions. arXiv preprint arXiv:2103.14011. |
| [4] | Brennan, M., Bresler, G. and Nagaraj, D. (2020). Phase transitions for detecting latent geometry in random graphs. Probab. Theory Related Fields 178 1215-1289. 10.1007/s00440-020-00998-3 · Zbl 1468.60011 |
| [5] | Bubeck, S., Ding, J., Eldan, R. and Rácz, M.Z. (2016). Testing for high-dimensional geometry in random graphs. Random Structures Algorithms 49 503-532. 10.1002/rsa.20633 · Zbl 1349.05315 |
| [6] | Bubeck, S. and Ganguly, S. (2018). Entropic CLT and phase transition in high-dimensional Wishart matrices. Int. Math. Res. Not. IMRN 2 588-606. 10.1093/imrn/rnw243 · Zbl 1407.82024 |
| [7] | Chen, L.H.Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method. Probability and Its Applications (New York). Heidelberg: Springer. 10.1007/978-3-642-15007-4 · Zbl 1213.62027 |
| [8] | Devroye, L., György, A., Lugosi, G. and Udina, F. (2011). High-dimensional random geometric graphs and their clique number. Electron. J. Probab. 16 2481-2508. 10.1214/EJP.v16-967 · Zbl 1244.05200 |
| [9] | Duchemin, Q. and De Castro, Y. (2021). Random Geometric Graph: Some recent developments and perspectives. Preprint. |
| [10] | Eldan, R. and Mikulincer, D. (2020). Information and dimensionality of anisotropic random geometric graphs. In Geometric Aspects of Functional Analysis. Vol. I. Lecture Notes in Math. 2256 273-324. Cham: Springer. 10.1007/978-3-030-36020-7_13 · Zbl 1453.05118 |
| [11] | Gibbs, A.L. and Su, F.E. (2002). On choosing and bounding probability metrics. Int. Stat. Rev. 70 419-435. · Zbl 1217.62014 |
| [12] | Gilbert, E.N. (1961). Random plane networks. J. Soc. Indust. Appl. Math. 9 533-543. · Zbl 0112.09403 |
| [13] | Hoff, P.D., Raftery, A.E. and Handcock, M.S. (2002). Latent space approaches to social network analysis. J. Amer. Statist. Assoc. 97 1090-1098. 10.1198/016214502388618906 · Zbl 1041.62098 |
| [14] | Janson, S. (1997). Gaussian Hilbert Spaces. Cambridge Tracts in Mathematics 129. Cambridge: Cambridge Univ. Press. 10.1017/CBO9780511526169 · Zbl 0887.60009 |
| [15] | Jiang, T. and Li, D. (2015). Approximation of rectangular beta-Laguerre ensembles and large deviations. J. Theoret. Probab. 28 804-847. 10.1007/s10959-013-0519-7 · Zbl 1333.15032 |
| [16] | Liu, S. and Rácz, M.Z. (2021). Phase transition in noisy high-dimensional random geometric graphs. arXiv preprint arXiv:2103.15249. |
| [17] | Liu, S. and Rácz, M.Z. (2023). Supplement to “A probabilistic view of latent space graphs and phase transitions.” 10.3150/22-BEJ1547SUPP |
| [18] | Ma, Z., Ma, Z. and Yuan, H. (2020). Universal latent space model fitting for large networks with edge covariates. J. Mach. Learn. Res. 21 Paper No. 4, 67. 10.1109/tnnls.2020.3010690 · Zbl 1497.68432 |
| [19] | Marchal, O. and Arbel, J. (2017). On the sub-Gaussianity of the beta and Dirichlet distributions. Electron. Commun. Probab. 22 Paper No. 54, 14. 10.1214/17-ECP92 · Zbl 1395.60016 |
| [20] | Penrose, M. (2003). Random Geometric Graphs. Oxford Studies in Probability 5. Oxford: Oxford Univ. Press. 10.1093/acprof:oso/9780198506263.001.0001 · Zbl 1029.60007 |
| [21] | Penrose, M.D. (2016). Connectivity of soft random geometric graphs. Ann. Appl. Probab. 26 986-1028. 10.1214/15-AAP1110 · Zbl 1339.05369 |
| [22] | Polyanskiy, Y. and Wu, Y. (2012-2017). Lecture notes on Information Theory. |
| [23] | Rácz, M.Z. and Bubeck, S. (2017). Basic models and questions in statistical network analysis. Stat. Surv. 11 1-47. 10.1214/17-SS117 · Zbl 1388.62199 |
| [24] | Rácz, M.Z. and Richey, J. (2019). A smooth transition from Wishart to GOE. J. Theoret. Probab. 32 898-906. 10.1007/s10959-018-0808-2 · Zbl 1447.60027 |
| [25] | Stein, C.M. (1981). Estimation of the mean of a multivariate normal distribution. Ann. Statist. 9 1135-1151. · Zbl 0476.62035 · doi:10.1214/aos/1176345632 |
| [26] | Tang, M., Sussman, D.L. and Priebe, C.E. (2013). Universally consistent vertex classification for latent positions graphs. Ann. Statist. 41 1406-1430. 10.1214/13-AOS1112 · Zbl 1273.62147 |
| [27] | van Handel, R. (2016). Probability in High Dimension. APC 550 Lecture Notes (Princeton University). |
| [28] | Wainwright, M.J. (2019). High-Dimensional Statistics: A Non-asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics 48. Cambridge: Cambridge Univ. Press. 10.1017/9781108627771 · Zbl 1457.62011 |
| [29] | Wendel, J.G. (1948). Note on the gamma function. Amer. Math. Monthly 55 563-564. 10.2307/2304460 |
| [30] | Young, S.J. and Scheinerman, E.R. (2007). Random dot product graph models for social networks. In Algorithms and Models for the Web-Graph. Lecture Notes in Computer Science 4863 138-149. Berlin: Springer. 10.1007/978-3-540-77004-6_11 · Zbl 1136.05322 |
| [31] | Zhang, A.R. and Zhou, Y. (2020). On the non-asymptotic and sharp lower tail bounds of random variables. Stat 9 e314, 11. 10.1002/sta4 · Zbl 07851200 |
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.
