Phase transition in noisy high-dimensional random geometric graphs

We study the problem of detecting latent geometric structure in random graphs. To this end, we consider the soft high-dimensional random geometric graph G(n, p, d, q), where each of the n vertices corresponds to an independent random point distributed uniformly on the sphere (Formula Presented), and the probability that two vertices are connected by an edge is a decreas-ing function of the Euclidean distance between the points. The probability of connection is parametrized by (Formula Presented), with smaller q corresponding to weaker dependence on the geometry; this can also be interpreted as the level of noise in the geometric graph. In particular, the model smoothly interpolates between the hard spherical random geometric graph G(n, p, d) (corresponding to q = 1) and the Erdős–Rényi model G(n, p) (correspond-ing to q = 0). We focus on the dense regime (i.e., p is a constant). We show that if (Formula Presented), then geometry is lost: G(n, p, d, q) is asymptotically indistinguishable from G(n, p). On the other hand, if (Formula Presented), then the signed triangle statistic provides an asymptotically powerful test for detecting geometry. These results generalize those of Bubeck, Ding, Eldan, and Rácz (2016) for G(n, p, d), and give quantitative bounds on how the noise level affects the dimension threshold for losing geometry. We also prove analogous results under a related but different distributional assumption which corresponds to the random dot product graph.