Skip to main content

Testing for high-dimensional geometry in random graphs

Author(s): Bubeck, Sébastien; Ding, Jian; Eldan, Ronen; Rácz, Miklós Z

To refer to this page use:
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 Erdős-Rényi 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 Sd−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).
Publication Date: Oct-2016
Electronic Publication Date: 6-Jan-2016
Citation: Bubeck, Sébastien, Ding, Jian, Eldan, Ronen, Rácz, Miklós Z. (2016). Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49 (3), 503 - 532. doi:10.1002/rsa.20633
DOI: doi:10.1002/rsa.20633
ISSN: 1042-9832
Pages: 503 - 532
Type of Material: Journal Article
Journal/Proceeding Title: Random Structures & Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.