New paper tightens spectral bounds and recovery guarantees for sparse random graphs

A new arXiv paper by Manuel Fernandez and Yizhe Zhu (arXiv:2607.14304) tackles spectral concentration and recovery in sparse high-dimensional random geometric graphs. These graphs connect pairs of high-dimensional vectors when their inner product exceeds a threshold, with edges appearing with probability p but dependent due to shared latent vectors. The authors prove that for the spherical model at the connectivity scale np = Ω(log n), the deviation between the adjacency matrix A and its expectation E[A] is bounded by O(sqrt(np log n) + npτ) with high probability, where τ is the cap threshold. This sharpens previous bounds from Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions. An analogous result holds for the Gaussian model after removing vector norm fluctuations, yielding improved synchronization guarantees for the homogeneous Kuramoto model.

Beyond concentration, the paper provides recovery guarantees for the underlying latent geometry from the leading eigenspace. When np >> log n, both the latent vector and relative Gram matrix errors vanish provided d << np log(1/p) / log n. The required lower dimension is only d >> log(1/p) for the spherical model and d >> log^2(1/p) log n for the Gaussian model, improving on Li and Schramm (2023). Notably, the authors prove the first exact recovery result for the Gaussian mixture block model: at the optimal connectivity scale np = Ω(log n), a polynomial-time semidefinite program exactly recovers all labels in a moderate-separation regime, with larger separation making recovery impossible due to isolated vertices. The proofs combine orthogonal polynomial expansions, decoupling, and matrix concentration, avoiding previous trace-moment arguments.