## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 3512-3574 |

Number of pages | 63 |

Journal | Electronic Journal of Statistics |

Volume | 17 |

Issue number | 2 |

DOIs | |

State | Published - 2023 |

### Funding

S. L. thanks Cong Ma, Kaizheng Wang, and Jiacheng Zhang for numerous insightful discussions throughout the years. We thank the editors and anonymous referees for their valuable comments and help to improve the manuscript. The authors acknowledge the generous support from NSF grant DMS-1811724.

## Keywords

- Random graph
- high-dimensional geometric structure
- hypothesis testing
- random geometric graph
- signed triangle

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty