On the Fourier Coefficients of High-Dimensional Random Geometric Graphs

The random geometric graph RGG(n, S d-1 , p) is formed by sampling n i.i.d. vectors V i n i=1 uniformly on S d-1 and placing an edge between pairs of vertices i and j for which ⟨V i , V j ⟩ ≥ τ p d , where τ p d is such that the expected density is p. We study the low-degree Fourier coefficients of the distribution RGG(n, S d-1 , p) and its Gaussian analogue.

Our main conceptual contribution is a novel two-step strategy for bounding Fourier coefficients which we believe is more widely applicable to studying latent space distributions. First, we localize the dependence among edges to few fragile edges. Second, we partition the space of latent vector configurations (S d-1 ) ⊗n based on the set of fragile edges and on each subset of configurations, we define a noise operator acting independently on edges not incident (in an appropriate sense) to fragile edges.

We apply the resulting bounds to: 1) Settle the low-degree polynomial complexity of distinguishing spherical and Gaussian random geometric graphs from Erdős-Rényi both in the case of observing a complete set of edges and in the non-adaptively chosen mask M model recently introduced by [MVW24]; 2) Exhibit a statistical-computational gap for distinguishing RGG and the planted coloring model [KVWX23] in a regime when RGG is distinguishable from Erdős-Rényi; 3) Reprove known bounds on the second eigenvalue of random geometric graphs.