Information and dimensionality of anisotropic random geometric graphs

DOI10.1007/978-3-030-36020-7_13zbMATH Open1453.05118arXiv1609.02490OpenAlexW2520379570MaRDI QIDQ5115958FDOQ5115958

Ronen Eldan, Dan Mikulincer

Publication date: 21 August 2020

Published in: Lecture Notes in Mathematics (Search for Journal in Brave)

Abstract: This paper deals with the problem of detecting non-isotropic high-dimensional geometric structure in random graphs. Namely, we study a model of a random geometric graph in which vertices correspond to points generated randomly and independently from a non-isotropic $d$-dimensional Gaussian distribution, and two vertices are connected if the distance between them is smaller than some pre-specified threshold. We derive new notions of dimensionality which depend upon the eigenvalues of the covariance of the Gaussian distribution. If $alpha$ denotes the vector of eigenvalues, and $n$ is the number of vertices, then the quantities $left(frac||alpha|{|}_2||alpha|{|}_{3}ight{)}^6/n^3$ and $left(frac||alpha|{|}_2||alpha|{|}_{4}ight{)}^4/n^3$ determine upper and lower bounds for the possibility of detection. This generalizes a recent result by Bubeck, Ding, R'acz and the first named author from [BDER14] which shows that the quantity $d/n^3$ determines the boundary of detection for isotropic geometry. Our methods involve Fourier analysis and the theory of characteristic functions to investigate the underlying probabilities of the model. The proof of the lower bound uses information theoretic tools, based on the method presented in [BG15].

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

Recommendations

• Testing for high-dimensional geometry in random graphs
• A probabilistic view of latent space graphs and phase transitions
• High-dimensional random geometric graphs and their clique number
• Phase transitions for detecting latent geometry in random graphs
• Gaussian fluctuations for edge counts in high-dimensional random geometric graphs

zbMATH Keywords

geometric graphsRandom graphsErdős-Rényi modeldimensionality of embeddings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Inequalities; stochastic orderings (60E15) Central limit and other weak theorems (60F05)

Cites Work

• Elements of Information Theory
• A Lyapunov-type Bound in R^d
• Probability
• Testing for high-dimensional geometry in random graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Normal approximations with Malliavin calculus. From Stein's method to universality
• The analysis of linear partial differential operators. I: Distribution theory and Fourier analysis.
• Banach-Mazur distances and projections on random subgaussian polytopes
• Entropic CLT and Phase Transition in High-dimensional Wishart Matrices

Cited In (7)

• A smooth transition from Wishart to GOE
• Random geometric graph: some recent developments and perspectives
• A probabilistic view of latent space graphs and phase transitions
• Phase transition in noisy high-dimensional random geometric graphs
• Threshold for detecting high dimensional geometry in anisotropic random geometric graphs
• The CLT in high dimensions: quantitative bounds via martingale embedding
• Phase transitions for detecting latent geometry in random graphs

This page was built for publication: Information and dimensionality of anisotropic random geometric graphs

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