Phase transition in noisy high-dimensional random geometric

We study the problem of detecting latent geometric structure in random graphs. To this end, we consider the soft high-dimensional ran -dom geometric graph g(n, p, d, q), where each of the n vertices corresponds to an independent random point distributed uniformly on the sphere Sd-1, 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 q E [0, 1], 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 Erdos-Renyi 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 nq -0 or d >> n3q2, then geometry is lost: g(n, p, d, q) is asymptotically indistinguishable from g(n, p). On the other hand, if d ⠅ n3q6, then the signed triangle statistic provides an asymptotically powerful test for detecting geometry. These results generalize those of Bubeck, Ding, Eldan, and Racz (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.