Detecting Random Geometric Graphs with General Kernel
Abstract
We study testing a random geometric graph with a fixed kernel against an Erdős-Rényi graph with the same edge density. Under the null hypothesis, the graph has n vertices and independent edges with probability p. Under the alternative hypothesis, latent points X1,…,Xn are independent and uniform on 𝕊d−1, and edges are conditionally independent with probabilities K(⟨ Xi,Xj⟩), where p=𝔼[K(⟨ X1,X2⟩)]. The goal is to determine a critical dimension d⋆ = d⋆(n,K): the total variation distance between the two graph laws tends to one for d≪ d⋆ and to zero for d≫ d⋆. For dense graphs, [BDER16] established d⋆asymp n3 for hard threshold kernels, whereas [MWX26] proved d⋆asymp n3/4 for smooth kernels with K'(0)≠0. We connect these results by characterizing the detection thresholds for kernels that need not be differentiable at zero. We also determine the thresholds for smooth kernels whose first nonzero derivative at zero has finite order greater than one. Throughout these classes, signed triangle or quadrilateral counts attain the optimal detection threshold. For certain nondifferentiable kernels, quadrilateral counts are optimal while triangle counts are suboptimal.
Related
- Planarity and number of crossings in general models of random geometric graphs
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Heat Kernel Estimates for Random Walks with Killing on Transient Graphs
- Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
- Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs
BibTeX
@misc{huang2026detecting,
title = {{Detecting Random Geometric Graphs with General Kernel}},
author = {Dong Huang and Shuangping Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12765},
eprint = {2610.12765},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12765},
}
RIS
TY - UNPB
TI - Detecting Random Geometric Graphs with General Kernel
AU - Dong Huang
AU - Shuangping Li
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12765
UR - https://arxiv.org/abs/2610.12765
AB - We study testing a random geometric graph with a fixed kernel against an Erdős-Rényi graph with the same edge density. Under the null hypothesis, the graph has n vertices and independent edges with probability p. Under the alternative hypothesis, latent points X_1,…,X_n are independent and uniform on 𝕊^d−1, and edges are conditionally independent with probabilities K(⟨ X_i,X_j⟩), where p=𝔼[K(⟨ X_1,X_2⟩)]. The goal is to determine a critical dimension d_⋆ = d_⋆(n,K): the total variation distance between the two graph laws tends to one for d≪ d_⋆ and to zero for d≫ d_⋆. For dense graphs, [BDER16] established d_⋆asymp n^3 for hard threshold kernels, whereas [MWX26] proved d_⋆asymp n^3/4 for smooth kernels with K'(0)≠0. We connect these results by characterizing the detection thresholds for kernels that need not be differentiable at zero. We also determine the thresholds for smooth kernels whose first nonzero derivative at zero has finite order greater than one. Throughout these classes, signed triangle or quadrilateral counts attain the optimal detection threshold. For certain nondifferentiable kernels, quadrilateral counts are optimal while triangle counts are suboptimal.
ER -