Testing for a Hidden Geometry in Random Graphs
Amit Silber, Mor Oren-Loberman, Wasim Huleihel
Abstract
We study the problem of detecting a faint geometric signal hidden in an otherwise random graph. Formally, we consider a hypothesis testing problem in which, under the null, the observed graph is an Erdős--Rényi random graph , while under the alternative a random geometric graph is planted on vertices. The planted subgraph is generated from independent random points on the unit sphere , with edges determined by latent geometric proximity and calibrated to have edge density . Our goal is to characterize the statistical and computational limits of detecting this hidden geometry. We derive sharp information-theoretic lower bounds that identify regimes where detection is impossible and provide algorithms that achieve these limits whenever detection is feasible. We further investigate the computational complexity of the problem and determine when efficient polynomial-time tests exist. The model exhibits an \emph{easy--hard--impossible} phase transition: some regimes allow efficient detection, others permit detection only with computationally intractable procedures, and still others render detection impossible even with unlimited computational power. As evidence for the computational barrier, we prove that all low-degree polynomial algorithms fail throughout the conjecturally hard regime, demonstrating a sharp gap between statistical and computational feasibility.
AI Impact Assessments
(1 models)Scientific Impact Assessment
Core Contribution
This paper addresses the fundamental problem of detecting a planted random geometric subgraph hidden within an Erdős–Rényi random graph G(n,q). The key distinguishing feature is that the planted subgraph has the *same* marginal edge probability q as the background, so detection must rely entirely on geometric correlations (higher-order edge dependencies) rather than density contrast. The authors characterize a complete easy–hard–impossible phase transition in the (α, β) plane where d = Θ(n^α) and k = Θ(n^β):
This is, to the authors' knowledge, the first sharp detection theory for a planted structure whose defining feature is latent high-dimensional geometry rather than density.
Methodological Rigor
The paper demonstrates strong technical sophistication across multiple fronts:
Information-theoretic lower bounds: The naive second-moment method fails due to rare tail events in the likelihood ratio. The authors develop a truncated second-moment analysis (following Ingster and Arias-Castro/Verzelen), carefully defining truncation sets based on Frobenius and operator norm constraints on the Wishart matrix. The analysis involves bounding D_m divergences through a chain of Cauchy–Schwarz decompositions and data processing inequalities, ultimately reducing to controlling moments of the overlap Z = |K ∩ K̄| via hypergeometric tail bounds. This is technically demanding but appears sound.
Upper bounds: Three algorithms are analyzed: (1) a vanilla signed-triangle test for the easy regime, (2) a scan signed-triangle test achieving the information-theoretic threshold, and (3) a geometry-agnostic densest subgraph scan. The scan test analysis is a genuine technical contribution — it requires exponential tail bounds for signed triangle counts rather than mere moment estimates. The authors develop new tools via decoupling inequalities for canonical U-statistics (de la Peña–Giné), combined with operator norm concentration and a McShane–Whitney extension argument for the log-Sobolev/Lipschitz machinery. This is novel territory, as prior work on signed triangles relied solely on first/second moment methods.
Computational lower bounds: The low-degree polynomial framework is applied with D ≤ C log n / log log n. A critical ingredient is the recent result of Bangachev–Bresler (STOC 2024) bounding Fourier coefficients of spherical random geometric graphs. The argument that leaf-containing subgraphs contribute zero to the low-degree likelihood, combined with the polynomial decay of cyclic contributions, yields the computational barrier. The matching lower bound on ||L_{n,≤D}|| via the triangle contribution provides the sharp computational threshold.
Potential Impact
Theoretical: This work sits at the intersection of planted subgraph detection and random geometric graph theory, two individually mature areas. By connecting them, it opens a new class of problems where the planted signal is *structural* (geometric correlations) rather than parametric (density change). The phase diagram Figure 1 provides a clean and complete picture that will likely become a reference point.
Methodological: The exponential tail bounds for signed triangle statistics via U-statistic decoupling are likely reusable in other scan-type testing problems involving dependent graph statistics. The truncated second-moment technique with geometric constraints may also find applications in related latent space models.
Applied: The motivation from detecting coordinated accounts, collusion networks, or botnets where the subgroup matches background statistics but has latent geometric coherence is compelling and timely. However, the current results are for fixed (constant) edge density, limiting immediate practical applicability.
Timeliness & Relevance
The paper addresses a current need at the intersection of high-dimensional statistics and network inference. The concurrent independent work by Bok, Li, and Yu (2026) on the same problem confirms this is a timely question. The use of the low-degree polynomial framework for computational hardness evidence is well-aligned with the current state of the art in average-case complexity.
Strengths
1. Complete phase diagram: All three regimes (easy/hard/impossible) are characterized, with matching bounds up to logarithmic factors.
2. Novel technical tools: The decoupling-based exponential tail bounds for signed triangles and the truncated second-moment analysis with geometric truncation sets are substantial contributions.
3. Clean presentation: Despite the technical complexity, the phase diagram and main results are stated clearly with explicit dependence on parameters.
4. Multiple evidence sources: The computational barrier is supported by low-degree polynomial hardness, consistent with the broader planted problem literature.
Limitations
1. Dense regime only: Edge probability q is a fixed constant. The sparse regime where q → 0 (arguably more realistic) is left open, though the concurrent work [BLY26] addresses this partially.
2. Logarithmic gaps: The information-theoretic bounds have log²k gaps, and the computational threshold has log³d factors. While common in the literature, closing these would strengthen the results.
3. Low-degree hardness only: The computational hardness evidence is based on the low-degree conjecture rather than formal reductions from established hard problems (e.g., planted clique). This is standard but remains conjectural.
4. Specific geometric model: Results are for the unit sphere with hard-threshold connections. Extensions to soft geometric graphs, other manifolds, or anisotropic settings are discussed only as future work.
5. No experiments: Numerical simulations illustrating the phase transitions would strengthen the presentation, particularly for practitioners.
Overall Assessment
This is a strong theoretical contribution that provides the first comprehensive detection theory for planted geometric structure in random graphs. The technical machinery is sophisticated and the results are sharp. The paper makes a meaningful advance at the intersection of planted subgraph detection and high-dimensional geometric graph theory.
Generated Jun 16, 2026
Comparison History (17)
Paper 2 has higher likely impact due to a timely, broadly relevant contribution to statistical/computational phase transitions in planted-structure random graph testing, with sharp information-theoretic limits, matching algorithms, and low-degree lower bounds supporting computational hardness. This fits a central line of work in high-dimensional inference, complexity, and network science, with clear downstream applications (community detection, anomaly/structure detection, latent space models). Paper 1 is innovative and methodologically rich, but its impact is likely more specialized to information contraction/Markov kernels and niche applications, with narrower cross-field uptake.
Paper 2 addresses a fundamental problem in random graph theory and computational complexity, establishing sharp information-theoretic bounds and an easy-hard-impossible phase transition for detecting hidden geometry. This connects to broad areas including community detection, average-case complexity, and geometric inference, with deep theoretical implications. The low-degree polynomial hardness evidence contributes to the growing computational-statistical gaps literature. Paper 1, while technically rigorous and practically relevant for LLM efficiency, is more narrowly focused on KV cache compression and its impact is primarily within the LLM systems community. Paper 2's contributions to foundational theory give it broader and more lasting impact.
Paper 1 offers a highly novel privacy mechanism—using correlated local noise to match central-DP optimal accuracy—directly addressing a major known limitation of local DP. This has clear, near-term real-world applicability in federated analytics and privacy-preserving data collection, with potential to influence both theory (tight utility bounds under LDP) and system design. Paper 2 is methodologically rigorous and timely for average-case complexity, but its impact is more specialized to theoretical random graph detection and complexity. Overall, Paper 1 likely has broader practical and cross-disciplinary uptake.
Paper 2 likely has higher impact: it reports exponential and even unbounded capacity gains from entanglement assistance in classical multiple access channels with causal CSIT—far beyond previously known modest improvements—suggesting a major conceptual shift with direct implications for quantum-enhanced networking and information theory. The claims are timely (quantum networks) and potentially broad (multiuser communications, coding, network information theory, quantum resources under noise). Paper 1 is rigorous and important for statistical/computational phase transitions in planted geometry, but its applications are more indirect and its conceptual leap is less dramatic than exponential/unbounded capacity advantages.
Paper 2 has higher potential impact due to broader relevance and timeliness: it advances the statistical–computational tradeoff literature with sharp information-theoretic limits, achievable algorithms, and low-degree lower bounds in a planted geometric subgraph model. The easy–hard–impossible phase transition framework is broadly transferable across random graphs, inference, and theoretical CS, with likely downstream influence on detection, community/structure testing, and complexity conjectures. Paper 1 is rigorous and practically relevant to federated learning security, but is more specialized to secure aggregation and key-distribution tradeoffs, likely yielding narrower cross-field impact.
Paper 2 targets a timely, high-visibility problem—scaling multi-agent AI—and offers an information-theoretic limitation tied to task-constraint connectivity with empirical validation (including SWE-bench), making it directly actionable for system design. Its potential real-world applications span agent architectures, software engineering automation, and task decomposition, with broad cross-field relevance (AI, information theory, complex systems). Paper 1 is methodologically rigorous and novel in statistical/computational phase transitions for planted geometric structure, but its impact is likely more specialized within random graphs and theoretical CS/statistics, with less immediate applied uptake.
Paper 2 addresses a fundamental problem in random graph theory and computational complexity with broad implications across statistics, computer science, and network science. Its characterization of easy-hard-impossible phase transitions with sharp information-theoretic bounds and computational hardness evidence (low-degree polynomial lower bounds) represents a significant contribution to the growing literature on statistical-computational gaps. Paper 1, while technically strong and timely given low-precision training trends, addresses a more specialized optimization theory question with narrower audience. Paper 2's methodology and results are likely to influence multiple research communities and inspire follow-up work on planted structure detection problems.
Paper 1 likely has higher scientific impact due to strong novelty in formalizing and sharply characterizing statistical–computational phase transitions for hidden geometric structure, with rigorous information-theoretic limits and low-degree lower bounds—results that can generalize across random graph inference, high-dimensional statistics, and complexity theory. Its methodological rigor and breadth (theory spanning statistics and computation) are high and timely given interest in computational barriers. Paper 2 is timely and application-relevant for generative communications, but appears more model/engineering-specific and may have narrower theoretical generality.
Paper 2 addresses a fundamental problem at the intersection of random graph theory, statistical hypothesis testing, and computational complexity. Its identification of an easy-hard-impossible phase transition with sharp information-theoretic bounds and computational hardness evidence (via low-degree polynomials) has broad impact across theoretical computer science, statistics, and network science. The geometric signal detection framework is widely applicable. Paper 1 makes strong technical contributions to stochastic approximation theory but addresses a more specialized topic with a narrower audience, primarily in optimization and reinforcement learning theory.
Paper 1 addresses a fundamental problem in random graph theory and computational complexity, establishing sharp information-theoretic limits and revealing an easy-hard-impossible phase transition for detecting hidden geometry. This contributes broadly to statistics, theoretical computer science, and network science, with deep methodological rigor and novelty. Paper 2, while practically relevant for 5G massive MIMO, proposes an incremental iterative receiver solution for phase noise—a narrower contribution with less theoretical depth and more limited cross-disciplinary impact.