Testing for high-dimensional geometry in random graphs

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