Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs
For researchers in high-dimensional statistics and network analysis, the work advances theoretical understanding of spectral methods in dependent-edge random graphs.
The paper provides sharp spectral norm bounds for sparse high-dimensional random geometric graphs and improves latent geometry recovery guarantees, showing that exact recovery in a Gaussian mixture block model is possible at optimal connectivity with polynomial-time algorithms.
We study sparse random geometric graphs generated by connecting pairs of high-dimensional vectors whose inner product exceeds a threshold. The latent vectors are sampled either uniformly from the sphere or from a standard Gaussian distribution. Although every edge appears with probability $p$, the edges are dependent through their shared latent vectors. For the spherical model, at the connectivity scale $np=Ω(\log n)$, we prove $\|A-\mathbb E A\|=O\left(\sqrt{np\log n}+npτ\right)$, with high probability, where $τ$ is the cap threshold. This sharpens the spectral norm bound of Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions. An analogous result holds for the Gaussian model after removing the fluctuations of the vector norms, yielding improved global synchronization guarantees for the homogeneous Kuramoto model. We then recover the latent geometry from the leading eigenspace. When $np\gg\log n$, both the latent vector and relative Gram matrix errors vanish provided $d\ll np\log(1/p)/\log n$. The required lower dimension is only $d\gg\log(1/p)$ for the spherical model and $d\gg\log^2(1/p)\log n$ for the Gaussian model, improving the recovery guarantees of Li and Schramm (2023). Finally, we prove the first exact recovery result for the Gaussian mixture block model of Li and Schramm (2023). At the optimal connectivity scale $np=Ω(\log n)$, a polynomial-time semidefinite program exactly recovers all labels in a moderate-separation regime, whereas larger separation makes exact recovery impossible because isolated vertices appear with high probability. Our proofs combine orthogonal polynomial expansions, decoupling, and matrix concentration, avoiding the trace-moment arguments used in previous work.