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 x1,ldots,xn independently and uniformly from the d-dimensional unit sphere, then connecting each pair (i,j) with probability K(langle xi,xjrangle). We study the sharp detection threshold, namely the highest dimension at which an RGG can be distinguished from its ErdHos--R'enyi counterpart with the same edge density. For dense graphs, we show that for smooth kernels the critical scaling is d = n3/4, substantially lower than the threshold d = n3 known for the hard RGG with step-function kernels citebubeck2016testing. 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 n3 mathoprm tr2(kappa3) = 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=√n is the critical dimension for non-trivial estimation of the latent vectors up to a global rotation.