Spectra of high-dimensional sparse random geometric graphs

Abstract

We determine the limiting empirical spectral distribution of sparse high-dimensional random geometric graphs. The vertices are independent uniform points on the unit sphere $S^{d-1}$, and two vertices are joined when their inner product exceeds a threshold chosen to give edge density $p$. The edges therefore have the same marginal probabilities as in an Erdős--Rényi graph, but the latent geometry introduces dependence among them. We show that these correlations are asymptotically invisible to the global spectrum in two sparse regimes. If $p\to 0$, $np\to \infty$, and $d=\Omega (np\log (1/p))$, then the empirical spectral distribution of $A/\sqrt{np}$ converges in probability to the semicircle law. If $p=\alpha /n$ for a fixed $\alpha >0$ and $d=\omega (\log n)$, then the empirical spectral distribution of $A/\sqrt{\alpha }$ converges in probability to the limiting spectral distribution of $\mathcal{G}(n,\alpha /n)$. The proof combines the moment method with a cluster expansion that decomposes geometric dependence into weak local interactions, allowing us to control every fixed walk pattern in the moment calculation.

arXiv comment39 pages, 1 figure. Major revision. The proof of the global law has been substantially revised using a new argument, leading to an improved result