Testing for high-dimensional geometry in random graphs

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

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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).

Original languageEnglish (US)
Pages (from-to)503-532
Number of pages30
JournalRandom Structures and Algorithms
Volume49
Issue number3
DOIs
StatePublished - Oct 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • high-dimensional geometric structure
  • hypothesis testing
  • random geometric graphs
  • random graphs
  • signed triangles

Fingerprint Dive into the research topics of 'Testing for high-dimensional geometry in random graphs'. Together they form a unique fingerprint.

Cite this