Threshold for detecting high dimensional geometry in anisotropic random geometric graphs. (English) Zbl 1529.05139
Summary: In the anisotropic random geometric graph model, vertices correspond to points drawn from a high-dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to hypothesis test between such a graph and an Erdős-Rényi graph with the same edge probability. If \(n\) is the number of vertices and \(\alpha\) is the vector of eigenvalues, R. Eldan and D. Mikulincer [Lect. Notes Math. 2256, 273–324 (2020; Zbl 1453.05118)] shows that detection is possible when \(n^3 \gg\left(\left\Vert \alpha \right\Vert_2 /\left\Vert \alpha \right\Vert_3 \right)^6\) and impossible when \(n^3 \ll \left(\left\Vert \alpha \right\Vert_2 /\left\Vert \alpha \right\Vert_4 \right)^4\). We show detection is impossible when \(n^3 \ll \left(\left\Vert \alpha \right\Vert_2 /\left\Vert \alpha \right\Vert_3 \right)^6\), closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer [loc. cit.].
© 2023 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.
© 2023 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
| 60B20 | Random matrices (probabilistic aspects) |
| 60F05 | Central limit and other weak theorems |
| 15B52 | Random matrices (algebraic aspects) |
| 60C05 | Combinatorial probability |
| 60D05 | Geometric probability and stochastic geometry |
| 62H15 | Hypothesis testing in multivariate analysis |
Keywords:
Erdős-Rényi graph; high-dimensional geometry; hypothesis testing; random geometric graph; Wishart matrixCitations:
Zbl 1453.05118References:
| [1] | M.Brennan, G.Bresler, and B.Huang. De Finetti‐style results for Wishart matrices: Combinatorial structure and phase transitions. arXiv preprint arXiv:2103.14011. 2021. |
| [2] | M.Brennan, G.Bresler, and D.Nagaraj, Phase transitions for detecting latent geometry in random graphs, Probab. Theory Rel. Fields178 (2020), no. 3, 1215-1289. · Zbl 1468.60011 |
| [3] | S.Bubeck, J.Ding, R.Eldan, and M. Z.Rácz, Testing for high‐dimensional geometry in random graphs, Rand. Struct. Alg.49 (2016), no. 3, 503-532. · Zbl 1349.05315 |
| [4] | S.Bubeck and S.Ganguly, Entropic CLT and phase transition in high‐dimensional Wishart matrices, Int. Math. Res. Not.2018 (2018), no. 2, 588-606. · Zbl 1407.82024 |
| [5] | S.Chatterjee and E.Meckes, Multivariate normal approximation using exchange‐able pairs, Alea4 (2008), 257-283. · Zbl 1162.60310 |
| [6] | D.Chételat and M. T.Wells, The middle‐scale asymptotics of Wishart matrices, Ann. Stat.47 (2019), no. 5, 2639-2670. · Zbl 1436.60019 |
| [7] | L.Devroye, A.György, G.Lugosi, and F.Udina, High‐dimensional random geometric graphs and their clique number, Elec. J. Probab.16 (2011), 2481-2508. · Zbl 1244.05200 |
| [8] | R.Eldan and D.Mikulincer, “Information and dimensionality of anisotropic random geometric graphs,” Geo. Aspects Func. Analysis: Israel seminar, Cham, Switzerland: Springer, 2017, pp. 273-324. · Zbl 1453.05118 |
| [9] | T.Jiang and D.Li, Approximation of rectangular beta‐Laguerre ensembles and large deviations, J. Theor. Probab.28 (2015), no. 3, 804-847. · Zbl 1333.15032 |
| [10] | I. M.Johnstone. High dimensional statistical inference and random matrices. Paper presented at: Proc. 2006 ICM. 2007307-333. · Zbl 1120.62033 |
| [11] | S.Liu, S.Mohanty, T.Schramm, and E.Yang. Testing thresholds for high‐dimensional sparse random geometric graphs. Paper presented at: Proc. 54th STOC. 2022672-677. · Zbl 07774369 |
| [12] | S.Liu and M. Z.Rácz. Phase transition in noisy high‐dimensional random geometric graphs. arXiv preprint arXiv:2103.15249. 2021. |
| [13] | D.Mikulincer, A CLT in Stein’s distance for generalized Wishart matrices and higher‐order tensors, Int. Math. Res. Not.2022 (2022), no. 10, 7839-7872. · Zbl 1491.60041 |
| [14] | I.Nourdin and G.Zheng, Asymptotic behavior of large Gaussian correlated Wishart matrices, J. Theor. Probab. (2021), 35, 2239-2268. · Zbl 1502.60008 |
| [15] | R.O’Donnell, Analysis of Boolean functions, Cambridge, UK: Cambridge University Press, 2014. · Zbl 1336.94096 |
| [16] | M.Penrose, Random geometric graphs, Vol 5, Oxford, UK: Oxford University Press, 2003. · Zbl 1029.60007 |
| [17] | M. Z.Rácz and J.Richey, A smooth transition from Wishart to GOE, J. Theor. Probab.32 (2019), no. 2, 898-906. · Zbl 1447.60027 |
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.
