arXiv preprint ·
On Statistical-Computational Gaps in Graph Combinatorial Testing Problems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study high-dimensional graph combinatorial hypothesis testing problems in which a signal is supported on the edge set of an unknown subgraph drawn from a class invariant under vertex relabeling. For Gaussian observations, we characterize sharp statistical and computational thresholds (at polynomial order) for the signal magnitude required for strong detection across various combinatorial graph alternatives. Our analysis is based on bounding the second moments of the full and low-degree likelihood ratios in terms of the overlap of two independent latent structures and comparing the resulting lower bounds with scan, average, and coordinatewise maximum tests. Under an appropriate low-degree conjecture for computational hardness, we obtain planted-clique thresholds matching those known for Gaussian submatrix detection and identify new statistical-computational gaps for multiple planted cliques and hypercliques, thick cycles and thick paths. We also establish a novel transfer principle across natural exponential family observation models: matching the one-coordinate chi-square divergence preserves full likelihood-ratio second moments exactly and makes low-degree second moments equivalent up to constant factors under a degree condition. Under local regularity, we obtain corresponding testing upper bounds in terms of an effective signal strength. When these upper and lower bounds match, they yield universal threshold scales in the local alternative regime. As a consequence, statistical-computational gaps for planted-clique detection in Erdős--Rényi settings can be deduced from the Gaussian model.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistics Theory
Bethe Hessian Recovery through the Kesten-Stigum Regime
Non-asymptotic analysis of SGLD with discontinuous stochastic gradients: a new route to portfolio CVaR minimization
The Statistical Geometry of Latent Recovery in Hidden Markov Models
Instance-dependent sequential limits as an exact information ledger
Estimating Average Treatment Effects with Projected Instrumental Variables
Get the few papers worth your time in Statistics Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.