Threshold for detecting high dimensional geometry in anisotropic random geometric graphs

DOI10.1002/RSA.21178zbMATH Open1529.05139arXiv2206.14896MaRDI QIDQ6185052FDOQ6185052

Authors: Matthew D. Brennan, Guy Bresler, Brice Huang 

Publication date: 5 January 2024

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: 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 ErdH{o}s-R'enyi graph with the same edge probability. If $n$ is the number of vertices and $alpha$ is the vector of eigenvalues, Eldan and Mikulincer show that detection is possible when $n^{3}gg(|alpha{|}_2/|alpha{|}_3{)}^6$ and impossible when $n^{3}ll(|alpha{|}_2/|alpha{|}_4{)}^4$. We show detection is impossible when $n^{3}ll(|alpha{|}_2/|alpha{|}_3{)}^6$, closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer.

Full work available at URL: https://arxiv.org/abs/2206.14896

Recommendations

• Information and dimensionality of anisotropic random geometric graphs
• Testing for high-dimensional geometry in random graphs
• Phase transition in noisy high-dimensional random geometric graphs
• High-dimensional random geometric graphs and their clique number
• Phase transitions for detecting latent geometry in random graphs

zbMATH Keywords

hypothesis testinghigh-dimensional geometryrandom geometric graphWishart matrixErdős-Rényi graph

Mathematics Subject Classification ID

Hypothesis testing in multivariate analysis (62H15) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Geometric probability and stochastic geometry (60D05) Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Random Geometric Graphs
• Testing for high-dimensional geometry in random graphs
• Analysis of Boolean Functions
• Title not available (Why is that?)
• Approximation of rectangular beta-Laguerre ensembles and large deviations
• Multivariate normal approximation using exchangeable pairs
• High-dimensional random geometric graphs and their clique number
• Testing thresholds for high-dimensional sparse random geometric graphs
• A smooth transition from Wishart to GOE
• Entropic CLT and phase transition in high-dimensional Wishart matrices
• Information and dimensionality of anisotropic random geometric graphs
• Asymptotic behavior of large Gaussian correlated Wishart matrices
• Phase transitions for detecting latent geometry in random graphs
• The middle-scale asymptotics of Wishart matrices
• A CLT in Stein's distance for generalized Wishart matrices and higher-order tensors

Cited In (1)

• Phase transition in noisy high-dimensional random geometric graphs

This page was built for publication: Threshold for detecting high dimensional geometry in anisotropic random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185052)