Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
Abstract
Detection of geometry in random graphs and matrices has been extensively studied in recent years. For testing a dense random geometric graph on n vertices with latent points in dimension d against an Erdős--Rényi graph, the detection threshold dasymp n3 is well known since Bubeck, Ding, Eldan, and Rácz (2016). We sharpen this result by establishing the optimal asymptotic testing error in the critical regime d/n3→λ∈(0,∞). The log-likelihood ratio is shown to be asymptotically normal and dominated by the signed triangle count. Moreover, we consider testing the rank statistics of inner products between latent points against uniformly random ranks. We show that ranks preserve all asymptotic testing information available in the full matrix models, and a cubic statistic based on rank statistics attains the optimal asymptotic error. This then yields an asymptotically optimal test for random kernel matrices with a possibly unknown, strictly monotone kernel. The proofs combine the classical framework of Davies (1985) and Le Cam and Yang (1988) for asymptotic normality under information loss with conditional limit theorems for the models in consideration.
Related
- Critical soil moisture thresholds reveal contrasting ecosystem responses across the tropics
- Asymptotic Rounding Laws for Optimal Thresholds in Secretary Problems
- Critical thresholds for the damped wave system with mixed product-type nonlinearities
- Eigenvector distributions and optimal shrinkage estimators for large covariance and precision matrices
- Sharp Critical Minimax Laws and No-Learning Thresholds in Continuous-Time Adaptive Control
BibTeX
@misc{mao2026optimal,
title = {{Optimal detection of geometry in random graphs and kernel matrices at critical thresholds}},
author = {Cheng Mao and Timothy L. H. Wee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15272},
eprint = {2610.15272},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15272},
}
RIS
TY - UNPB
TI - Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
AU - Cheng Mao
AU - Timothy L. H. Wee
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15272
UR - https://arxiv.org/abs/2610.15272
AB - Detection of geometry in random graphs and matrices has been extensively studied in recent years. For testing a dense random geometric graph on n vertices with latent points in dimension d against an Erdős--Rényi graph, the detection threshold dasymp n^3 is well known since Bubeck, Ding, Eldan, and Rácz (2016). We sharpen this result by establishing the optimal asymptotic testing error in the critical regime d/n^3→λ∈(0,∞). The log-likelihood ratio is shown to be asymptotically normal and dominated by the signed triangle count. Moreover, we consider testing the rank statistics of inner products between latent points against uniformly random ranks. We show that ranks preserve all asymptotic testing information available in the full matrix models, and a cubic statistic based on rank statistics attains the optimal asymptotic error. This then yields an asymptotically optimal test for random kernel matrices with a possibly unknown, strictly monotone kernel. The proofs combine the classical framework of Davies (1985) and Le Cam and Yang (1988) for asymptotic normality under information loss with conditional limit theorems for the models in consideration.
ER -