Random geometric graphs detection thresholds vary by kernel smoothness
Detecting Random Geometric Graphs with General Kernel
Information Theory
Summary
This work looks at how to tell apart two types of random graphs: one where edges appear completely randomly and another where edges depend on hidden points relating to each other. The authors focus on how the difficulty of detection changes with the dimension of the space and the shape of the function (kernel) that determines edge probabilities. They find exact thresholds that describe when it's possible to distinguish these graphs, depending on whether the kernel is smooth or not. They also identify which simple graph statistics work best for detection under different conditions.
What this means in practice
- •For network analysts: Improve methods for detecting structure in complex networks by identifying critical dimension thresholds for different edge-generation models.
- •For data scientists: Use graph motif counts to optimize detection of latent geometric structure in high-dimensional data representations.
A theory result. No direct application yet.
Authors
Dong Huang, Shuangping Li
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 $X_1,\ldots,X_n$ are independent and uniform on $\mathbb{S}^{d-1}$, and edges are conditionally independent with probabilities $K(\langle X_i,X_j\rangle)$, where $p=\mathbb{E}[K(\langle X_1,X_2\rangle)]$. The goal is to determine a critical dimension $d_\star = d_\star(n,K)$: the total variation distance between the two graph laws tends to one for $d\ll d_\star$ and to zero for $d\gg d_\star$. For dense graphs, [BDER16] established $d_\star\asymp n^3$ for hard threshold kernels, whereas [MWX26] proved $d_\star\asymp n^{3/4}$ for smooth kernels with $K'(0)\ne0$. 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.