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 \say{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_\infty$-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 \say{AND} of their 1-dimensional counterparts, as is the case for $L_\infty$ 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\ll n^3p^3$ for the whole regime of edge probabilities $\frac{c}{n} Cite this Paper BibTeX @InProceedings{pmlr-v291-baguley25a, title = {Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions}, author = {Baguley, Samuel and G{\"o}bel, Andreas and Pappik, Marcus and Schiller, Leon}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {200--201}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/baguley25a/baguley25a.pdf}, url = {https://proceedings.mlr.press/v291/bagul