Detecting geometric structure in random graphs

Detecting geometric structure in random graphs

-
Ronan Eldan, Weizmann Institute
Fine Hall 214

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 Erdos-Renyi random graph. Under the alternative, the graph is a geometric random graph, where each vertex corresponds to a latent independent random vector uniformly distributed on the d-dimensional sphere (the isotropic case) or a Gaussian distribution with an arbitrary covariance matrix (the non isotropic case), 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. Based joint works with Sebastien Bubeck, Jian Ding, Dan Mikulincer and Miklos Racz.