Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910023958921216 |
|---|---|
| author | Mao, Cheng Wu, Yihong Xu, Jiaming |
| author_facet | Mao, Cheng Wu, Yihong Xu, Jiaming |
| contents | A random geometric graph (RGG) with kernel $K$ is constructed by first sampling latent points $x_1,\ldots,x_n$ independently and uniformly from the $d$-dimensional unit sphere, then connecting each pair $(i,j)$ with probability $K(\langle x_i,x_j\rangle)$. We study the sharp detection threshold, namely the highest dimension at which an RGG can be distinguished from its Erdős--Rényi counterpart with the same edge density.
For dense graphs, we show that for smooth kernels the critical scaling is $d = n^{3/4}$, substantially lower than the threshold $d = n^3$ known for the hard RGG with step-function kernels \cite{bubeck2016testing}. We further extend our results to kernels whose signal-to-noise ratio scales with $n$, and formulate a unifying conjecture that the critical dimension is determined by $n^3 \mathop{\rm tr}^2(κ^3) = 1$, where $κ$ is the standardized kernel operator on the sphere.
Departing from the prevailing approach of bounding the Kullback-Leibler divergence by successively exposing latent points, which breaks down in the sublinear regime of $d=o(n)$, our key technical contribution is a careful analysis of the posterior distribution of the latent points given the observed graph, in particular, the overlap between two independent posterior samples. As a by-product, we establish that $d=\sqrt{n}$ is the critical dimension for non-trivial estimation of the latent vectors up to a global rotation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14998 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture Mao, Cheng Wu, Yihong Xu, Jiaming Probability Information Theory Social and Information Networks Statistics Theory A random geometric graph (RGG) with kernel $K$ is constructed by first sampling latent points $x_1,\ldots,x_n$ independently and uniformly from the $d$-dimensional unit sphere, then connecting each pair $(i,j)$ with probability $K(\langle x_i,x_j\rangle)$. We study the sharp detection threshold, namely the highest dimension at which an RGG can be distinguished from its Erdős--Rényi counterpart with the same edge density. For dense graphs, we show that for smooth kernels the critical scaling is $d = n^{3/4}$, substantially lower than the threshold $d = n^3$ known for the hard RGG with step-function kernels \cite{bubeck2016testing}. We further extend our results to kernels whose signal-to-noise ratio scales with $n$, and formulate a unifying conjecture that the critical dimension is determined by $n^3 \mathop{\rm tr}^2(κ^3) = 1$, where $κ$ is the standardized kernel operator on the sphere. Departing from the prevailing approach of bounding the Kullback-Leibler divergence by successively exposing latent points, which breaks down in the sublinear regime of $d=o(n)$, our key technical contribution is a careful analysis of the posterior distribution of the latent points given the observed graph, in particular, the overlap between two independent posterior samples. As a by-product, we establish that $d=\sqrt{n}$ is the critical dimension for non-trivial estimation of the latent vectors up to a global rotation. |
| title | Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture |
| topic | Probability Information Theory Social and Information Networks Statistics Theory |
| url | https://arxiv.org/abs/2602.14998 |