Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture

A random geometric graph (RGG) with kernel $K$ is constructed by first sampling latent points $x_1,\dots ,x_n$ independently and uniformly from the $d$-dimensional unit sphere, then connecting each pair $(i,j)$ with probability $K(⟨x_i,x_j⟩)$. 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\mathrm{/}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{}^2({\kappa }^3)=1$, where $\kappa$ 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.