Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions

摘要

We study high-dimensional random geometric graphs (RGGs) of edge-density p with vertices uniformly distributed on the d-dimensional torus and edges inserted between sufficiently close vertices with respect to an L_q-norm. In this setting, we focus on distinguishing an RGG from an Erdős–Rényi graph if both models have the same marginal edge probability p. So far, most results in the literature considered either spherical RGGs with L_2-distance or toroidal RGGs under L_∞-distance. However, for general L_q-distances, many questions remain open, especially if p is allowed to depend on n. The main reason for this is that RGGs under L_q-distances can not easily be represented as the logical AND of their 1-dimensional counterparts, as is the case for L_∞ geometries. To overcome this difficulty, we devise a novel technique for quantifying the dependence between edges based on a modified version of Edgeworth expansions. Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general L_q norms from Erdős–Rényi graphs for any fixed p and q. We achieve this by showing that the signed triangle statistic can distinguish the two models when d≪ n^3p^3 for the whole regime of edge probabilities c/n<p<1. Additionally, our technique yields an improved information-theoretic lower bound for this task, showing that the two distributions converge in total variation whenever d=Ω̃(n^3p^2), which is just as strong as the currently best known lower bound for spherical RGGs in case of general p from Liu et al. [STOC’22]. Finally, our expansions allow us to tightly characterize the spectral properties of toroidal RGGs both under L_q-distances for fixed 1 ≤ q < ∞, and L_∞-distance. We find that these are quite different for q<∞ vs. q=∞. Our results partially resolve a conjecture of Bangachev and Bressler [COLT ’24] and prove that the distance metric, rather than the underlying space, is responsible for the observed differences in the behavior of high-dimensional spherical and toroidal RGGs.