Testing for high‐dimensional geometry in random graphs1. Issue 3 (6th January 2016)

• Record Type: Journal Article
• Authors: Bubeck, Sébastien; Ding, Jian; Eldan, Ronen; Rácz, Miklós Z.
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 503
• Page End: 532
• Publication Date: 2016-01-06
• Subjects: random graphs -- random geometric graphs -- hypothesis testing -- high‐dimensional geometric structure -- signed triangles; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20633
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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 ) . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 503–532, 2016