On Statistical-Computational Gaps in Graph Combinatorial Testing Problems
math.ST, stat.ML, stat.TH
Submitted: 2026-10-30
Updated: 2026-10-30
Comments: 106 pages, 6 figures, 1 table
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
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.
Sources
- The statistical threshold for planted matchings and spanning trees
- Planted clique detection and recovery from the hypergraph adjacency matrix
- Community Detection in Random Networks
- Searching for a trail of evidence in a maze
- Detection of an anomalous cluster in a network
- Distribution-Free Detection of Structured Anomalies: Permutation and Rank-Based Scans
- The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
- The Quasi-Polynomial Low-Degree Conjecture is False
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Low-degree lower bounds via almost orthonormal bases
- Detecting weighted hidden cliques
- An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Detecting Arbitrary Planted Subgraphs in Random Graphs
- Sharp minimax risks and phase transitions in sparse submatrix detection
- Bayesian estimation from few samples: community detection and related problems
- The power of sum-of-squares for detecting hidden structures
- Recovery thresholds for hidden weighted sparse graphs
- Rigorous Implications of the Low-Degree Heuristic
- Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Related papers
- Sigmoid-FTRL: Design-Based Adaptive Neyman Allocation for AIPW Estimators
- Conformal Prediction for Dyadic Regression Under Complex Missingness
- Sharp Asymptotic Theory of Maximum Likelihood Estimation for Gaussian Processes with an RBF Kernel
- Bentkus-type asymptotic e-values
- Canonical Layer Inference for Deep Gaussian Processes via Symmetry-Breaking Augmentation
- High-Dimensional Asymptotics of Differentially Private PCA