Testing for high-dimensional geometry in random graphs

DOI10.1002/RSA.20633zbMATH Open1349.05315arXiv1411.5713OpenAlexW2963421284MaRDI QIDQ2830237FDOQ2830237

Authors: Sébastien Bubeck, Jian Ding, Ronen Eldan, Miklós Z. Rácz 

Publication date: 9 November 2016

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

Abstract: We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an ErdH{o}s-R'enyi random graph $G(n,p)$. Under the alternative, the graph is generated from the $G(n,p,d)$ model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere $mathbb{S}^{d-1}$, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., $p$ is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in $G(n,p,d)$.

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

Recommendations

• A probabilistic view of latent space graphs and phase transitions
• Phase transitions for detecting latent geometry in random graphs
• Information and dimensionality of anisotropic random geometric graphs
• A nonparametric two-sample hypothesis testing problem for random graphs
• High-dimensional random geometric graphs and their clique number

zbMATH Keywords

hypothesis testingrandom graphsrandom geometric graphshigh-dimensional geometric structuresigned triangles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• On the distribution of the largest eigenvalue in principal components analysis
• Reconstruction and estimation in the planted partition model
• The method of moments and degree distributions for network models
• Latent Space Approaches to Social Network Analysis
• Detecting positive correlations in a multivariate sample
• Community detection in dense random networks
• Exact Recovery in the Stochastic Block Model
• Collective dynamics of `small-world' networks
• Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
• An introduction to random matrices
• Unit disk graph recognition is NP-hard
• Approximation of rectangular beta-Laguerre ensembles and large deviations
• High-dimensional random geometric graphs and their clique number
• Title not available (Why is that?)
• An efficiency upper bound for inverse covariance estimation

Cited In (43)

• Limit behavior in high-dimensional regime for the Wishart tensors in Wiener chaos
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Asymptotic behavior of large Gaussian correlated Wishart matrices
• The middle-scale asymptotics of Wishart matrices
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• Limit theory of sparse random geometric graphs in high dimensions
• A smooth transition from Wishart to GOE
• Random geometric graph: some recent developments and perspectives
• New error bounds in multivariate normal approximations via exchangeable pairs with applications to Wishart matrices and fourth moment theorems
• Information and dimensionality of anisotropic random geometric graphs
• Permutation Tests for Infection Graphs
• Adaptive estimation of nonparametric geometric graphs
• High-dimensional random geometric graphs and their clique number
• Optimal adaptivity of signed-polygon statistics for network testing
• A probabilistic view of latent space graphs and phase transitions
• Markov random geometric graph, MRGG: a growth model for temporal dynamic networks
• A high-dimensional CLT in \(\mathcal {W}_2\) distance with near optimal convergence rate
• High-dimensional regimes of non-stationary Gaussian correlated Wishart matrices
• Title not available (Why is that?)
• Detecting a botnet in a network
• Community detection and percolation of information in a geometric setting
• Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
• Local and global expansion in random geometric graphs
• Title not available (Why is that?)
• Phase transition in noisy high-dimensional random geometric graphs
• Threshold for detecting high dimensional geometry in anisotropic random geometric graphs
• High-dimensional regime for Wishart matrices based on the increments of the solution to the stochastic heat equation
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Limiting behavior of large correlated Wishart matrices with chaotic entries
• Guarantees for Spontaneous Synchronization on Random Geometric Graphs
• Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
• Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
• Phase transitions for detecting latent geometry in random graphs
• Maximal persistence in random clique complexes
• Testing multivariate uniformity based on random geometric graphs
• Limit behavior in high-dimensional regime for Wishart tensors with Rosenblatt entries
• Searching for (sharp) thresholds in random structures: where are we now?
• Gaussian fluctuation for Gaussian Wishart matrices of overall correlation
• A nonparametric two-sample hypothesis testing problem for random graphs
• Two-sample hypothesis testing for inhomogeneous random graphs
• Higher-order fluctuations in dense random graph models
• Gaussian fluctuations for edge counts in high-dimensional random geometric graphs
• Graph-theoretic multisample tests of equality in distribution for high dimensional data

This page was built for publication: Testing for high-dimensional geometry in random graphs

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