Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Rigorous Low-Degree Implications for Planted Subgraph Detection".
Jane: Here's the gist of the paper. The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems.
Tom: This work rigorously investigates the consequences of this low-degree assumption for planted subgraph detection in sparse random graphs, showing that vanishing low-degree advantage forces the noisy planted distribution to be asymptotically indistinguishable from the null.
Jane: Core Results on Indistinguishability The main result establishes that if a planted graph's low-degree likelihood ratio vanishes, then a noisy version of the planted model is asymptotically indistinguishable from the null distribution.
Tom: Specifically, in the supercritical regime where the average degree is greater than one, if tw(Γn) = o(Dn/ log n), then a noisy version of Pn is asymptotically indistinguishable from Qn.
Title and authors: Tom: So this paper is basically taking that low degree idea we talked about and putting it through some serious stress tests with noise to see what actually happens Hop18.
Jane: Right so they're showing that if the low degree advantage you have doesn't vanish in a certain way then even when you add random noise to your planted structure you still know how to tell it apart from pure random chance Hop18.
Lu: Specifically they tie this to the treewidth of your graph. If the graph is too complex if it has high treewidth that low degree advantage might still be there enough to distinguish it from noise Hop18.
Meng: So what's the practical implication here? If I'm building a system that looks for a hidden pattern does this mean I need to keep my graphs simple like keeping the treewidth low if I want to rely on this low degree test?
Tom: Exactly. The paper proves that in the supercritical regime where your average degree is high if you have a graph with small treewidth then the noise won't destroy your ability to detect it unless the low degree advantage itself completely disappears Hop18.
Jane: That’s a relief for people trying to build robust detection methods. It means that for those structured graphs with low treewidth the low degree heuristic still has teeth against noise.
Lu: But they also show the opposite in critical and subcritical regimes in those cases even without a small treewidth the noise actually helps you out by destroying any remaining long cycles in your structure Hop18.
Meng: Wait so it depends entirely on which regime you're in supercritical versus critical to know if the treewidth assumption is even necessary for the result to hold? That makes deploying this a bit tricky.
Tom: It does. The paper gives you two different conditions depending on whether your average degree is above one or not Hop18. It’s a big difference between those two settings.
Jane: And they also showed how to build a scan test that proves distinguishability using all possible subsets of vertices and that the total error of that test goes to zero if the low degree advantage disappears <ref:2608.06279#pg5>.
Lu: That scan test is powerful because it doesn't rely on assumptions about treewidth or cycles it just checks every possible configuration Hop18. It’s a very general proof.
Meng: It really shows that the structural properties like treewidth are what make the difference between having a tool that works well and having one that actually works against noise.
Tom: And they also connect this to Gaussian vectors showing that for more complex math problems too the same idea holds with a certain bound on how big your degree is log n over log log n Hop18.
Jane: So for more complex math problems too the same idea holds with a certain bound on how big your degree is log n over log log log n Hop18.
Lu: It’s a strong extension of the idea it suggests that low degree constraints are fundamental across different types of mathematical structures.
Meng: So for me what this means is that if I'm deploying an AI system I need to really look at the underlying structure of my data is it sparse does it have bounded treewidth because if not this test might fail you fast when noise gets in.
Tom: That’s right. It moves the discussion from just does this work to under what structural constraints does this work reliably against noise.
Jane: And that's where the real research is going next figure out how to build these tests efficiently enough for actual deployment not just theoretically prove they exist <ref:2608.06279#pg1>.
The paper's summary: Tom: So we just talked about how this paper shows that low degree advantage vanishes if you add noise Hop18 and that treewidth matters a lot for that to be true Hop18.
Jane: Right but what are they suggesting we do now? What’s the next step in making this detection method better or more reliable hop18.
Lu: They suggest a few things First they're focusing on making those structural decompositions more refined Hop18 specifically refining the tree decomposition to be subcubic Hop18.
Meng: Refined how? Like if the original structure is a tree decomposition but it's too big or messy for us to use in production models hop18.
Lu: Exactly. They are partitioning that weighted tree into smaller clusters making sure each cluster has a total weight between one and three times that small value Hop18. This controls how much information flows across the boundaries of the decomposition hop18.
Tom: That sounds like they’re trying to control the complexity of the data flow so we don't have to deal with a massive amount of connections all at once hop18.
Jane: And they are also looking at how noise behaves in those specific structural constraints Hop18. They found that in the critical and subcritical regimes the noise actually helps by destroying long cycles very quickly hop18.
Meng: That’s interesting because it means for certain graph types we don't even need to worry about keeping treewidth low if we are in those regimes hop18.
Lu: Right. The paper provides a clear roadmap for what structural properties like that subcubic refinement are actually necessary to achieve the bounds they are proving Hop18 It moves the idea from maybe it works to it works if you do this.
Tom: And they also look at the mathematical generalizations like those Gaussian vectors we mentioned earlier Hop18. They show that this low degree noise effect extends beyond just Boolean vectors hop18.
Jane: So the main improvement is giving us a concrete way to handle those complex structural assumptions using these decomposition techniques hop18 It’s turning a theoretical result into a practical guide for graph analysis hop18.
Meng: I'm still worried about the computational cost of these refinements Hop18 If refining the decomposition takes too long then it doesn't help us deploy anything in real time at scale hop18.
Lu: That’s a valid concern, Meng. But they are aiming for bounds that show the complexity remains manageable enough for subexponential time algorithms hop18 It’s about finding those sweet spots where the structure helps without making the computation impossible hop18.
The paper's improvements: Tom: So to wrap up this paper on "Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth" shows that if you have low degree advantage in a planted graph you need low treewidth to keep that advantage against noise Hop18.
Jane: And they’ve given us a concrete way to build those tests using scan tests over all vertex subsets proving the error goes to zero when the low degree vanishes <ref:2608.06279#pg5>.
Lu: It really formalizes how the structural properties like treewidth and cycle control are essential for these statistical results hop18 It's about proving what is necessary versus what is just convenient Hop18.
Meng: I still wonder if we can actually make those refined decomposition algorithms fast enough for real-world deployment at scale hop18 The refinement steps sound complicated and could introduce a lot of overhead hop18.
Lalam: I'm confident in the result the logic connecting the Fourier expansion to those subgraph counts is very solid <ref:2608.06279#pg2> It’s a strong connection between graph structure and statistical moments <ref:2608.06279#pg1>.
Tom: Yeah it connects the math to something real like whether an AI can actually tell a planted signal apart from noise in a noisy world <ref:2608.06279#pg1>.
Jane: This means that for any AI system looking for hidden structures understanding the underlying geometry—the treewidth and cycle structure—is just as important as knowing the degree distribution <ref:2608.06279#pg1>.
Lu: It opens up avenues to apply these ideas to other problems where we need to detect hidden patterns in noisy data like those Gaussian vector settings Hop18.
Meng: So if I'm building a detection system my first move is probably going to be checking the treewidth of the expected data structure before I even start training anything hop18
Conclusion: Tom: So we've been looking at "Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth" by Xuan Chen and Shuangping Li, and the main thing is that you need low treewidth to keep that low degree advantage against noise hop18.
Jane: Right, so if you're trying to find a hidden pattern in a random graph, using a low degree test won't work against noise unless the graph itself is pretty simple and has low treewidth hop18.
Lu: They show that they have to refine the tree decomposition into subcubic pieces and cluster them carefully so each piece keeps its total weight small, between one and three times that value hop18.
Meng: I still have my doubts about how much computational overhead this refinement adds when we try to run this on a massive graph at scale hop18
Tom: Yeah, Meng, they are aiming for bounds that show the complexity stays manageable enough for subexponential time algorithms hop18 It's about finding those sweet spots where the structure helps without making it impossible to compute hop18
Jane: And they proved this using a scan test over every possible subset of vertices—a test that proves the error goes to zero if that low degree advantage disappears hop18
Lu: That scan test is powerful because it doesn't rely on assumptions about treewidth or cycles; it just checks every configuration hop18 It’s a very general proof about the statistical moments linking subgraph counts to automorphism factors hop18
Meng: So, for me, my takeaway is that I need to check the treewidth of the data structure before I even start training anything because if it's not low, this test might fail you fast when noise gets in hop18
Tom: Right. The point here is that the low degree heuristic isn't just a guess; it has rigorous structural consequences when you factor in noise and specific graph constraints like treewidth hop18
Jane: It’s a powerful tool for understanding the fundamental limits of what we can detect in these kinds of random graphs hop18
Lu: We’re going to look at how this idea of structural constraints impacts the next set of problems we tackle in representation learning hop18
Peking University · Yale University
cs.CC, cs.DS, math.PR
Submitted: 2026-08-06
Updated: 2026-11-03
Comments: 41 pages, 4 figures
Code: https://github.com/fifalsp/lean
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 95/100
The gist: The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems.
Key concepts
- Low-Degree Heuristic
- This heuristic assumes that a graph's properties can be well-approximated by polynomials of low degree. The paper uses this assumption to analyze how much information about the planted structure is retained after adding noise, specifically focusing on the likelihood ratio's projection onto these low-degree polynomials.
- Statistical Indistinguishability
- This means that no statistical test, no matter how clever or efficient, can reliably tell the difference between a graph that has been planted with a specific structure and a random null graph when noise is present. The paper proves this happens when the low-degree advantage disappears.
- Treewidth
- Treewidth is a measure of how 'tree-like' or simple a graph structure is. It helps control the complexity of subgraphs by allowing the graph to be decomposed into pieces that overlap minimally at boundary vertices. This property is crucial for bounding Fourier mass and controlling subgraph counts.
- Fourier Analysis
- Fourier analysis involves breaking down complex functions, like those describing graph distributions, into a sum of simpler waves (basis functions). The paper uses this tool to relate the squared low-degree norm—which measures the planted structure's strength—to counts of specific subgraphs and their relationship to graph automorphisms.
Terminology
Summary
The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems. p. 0 This work rigorously investigates the consequences of this low-degree assumption for planted subgraph detection in sparse random graphs, showing that vanishing low-degree advantage forces the noisy planted distribution to be asymptotically indistinguishable from the null. p. 3
Core Results on Indistinguishability
The main result establishes that if a planted graph's low-degree likelihood ratio vanishes, then a noisy version of the planted model is asymptotically indistinguishable from the null distribution. Specifically, in the supercritical regime where the average degree is greater than one, if tw(Γn) = o(Dn/ log n), then a noisy version of Pn is asymptotically indistinguishable from Qn. p. 0 In the critical and subcritical regimes, the same conclusion holds whenever Dn = ω(log n), without any treewidth assumption. p. 0
Fourier Analysis and Subgraph Counts
The proof relies on uncovering a correspondence between subgraph counts and automorphism factors in the Fourier expansion and counts of isomorphism triples. The squared low-degree norm is expressed as a sum over isomorphism classes of subgraphs F, where the weight is related to the number of isomorphism triples. p. 7 The exact expression for the low-degree second moment is given by equation (3. p. 65) and its noised counterpart in equation (3. p. 96).
Role of Treewidth and Cycles
Treewidth plays a crucial role in controlling the Fourier mass of large subgraphs by allowing the decomposition tree to be cut into pieces that meet at only a few interface vertices. In the supercritical regime, this treewidth condition is necessary for Theorem 1. p. 51 to hold. At and below criticality, the treewidth assumption is removed in Theorem 1. p. 42. Furthermore, at and below criticality, the low-degree assumption rules out short cycles. p. 0
Construction of Counterexamples
The paper provides a deterministic supercritical example in Theorem A.3 that demonstrates a gap between low-degree and statistical distinguishability. p. 1 This construction involves selecting a simple realization from the D-regular configuration model and pruning short cycles to ensure the resulting graph satisfies the required local sparsity and girth conditions.
Statistical Distinguishability
The statistical distinguishability is proven using a scan test over all mn-vertex subsets. The test distinguishes the noised planted distribution from the null by thresholding the maximum induced edge count among these subsets. p. 3 This leads to a vanishing total error for the test, proving (A. p. 37).
Implications and Connections
The findings extend beyond Boolean vectors to Gaussian vectors, showing that after noise the joint distributions of symmetric polynomials of degree up to O(log n/ log log n) are statistically indistinguishable. This provides an important starting point for understanding rigorous consequences of low degree in planted-subgraph models and naturally raises the question for random graphs. p. 3
Technical Details of Decomposition
The proof of Lemma 4.4 involves refining a tree decomposition to be subcubic and then partitioning the resulting weighted tree into clusters whose total weight is between l and 3l. p. 9 This process ensures that the vertex-overlap count is bounded by (k + 1)(m − 1). p. 9 The final bound on the sum over connected graphs is shown to be o(1). p. 2
Cycle Control in Critical Regimes
In the critical and subcritical regimes (c ≤ 1), Theorem 1.2 proves that TεΓn is asymptotically acyclic with high probability. p. 7 This is achieved by showing that the expected number of cycles in TεΓn tends to zero. p. 2 This result shows that the noise destroys the remaining long cycles with high probability. p. 7
References
[ABAL+26] Louigi Addario-Berry, Omer Angel, Gabor Lugosi, Mikl os Z. R acz, and Tselil Schramm. The statistical threshold for planted matchings and spanning trees. p. 6
[AKS98] Noga Alon, Michael Krivelevich, and Benny Sudakov. p. 6 Finding a large hidden clique in a random graph. p. 3
[BBH+21] Matthew S. p. 2 Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, and Tselil Schramm. p. 2 Statistical query algorithms and low degree tests are almost equivalent. p. 2
[BBK+21] Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein. p. 3 Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. p. 2
[BEAH+22] Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. The franz-parisi criterion and computational trade-offs in high dimensional statistics. p. 2
[BH22] Guy Bresler and Brice Huang. p. 3 The algorithmic phase transition of random k-sat for low degree polynomials. p. 3
[BHJK25] Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, and Pravesh K. p. 3 Kothari. The quasipolynomial low-degree conjecture is false. p. 3
[BHK+19] Boaz Barak, Samuel B Hopkins, Jonathan A Kelner, Pravesh K. p. 2 Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. p. 2
[BLY26] Jinho Bok, Shuangping Li, and Sophie H Yu. p. 3 Detection of local geometry in random graphs: information-theoretic and computational limits. p. 3
[Bod93] Hans L Bodlaender. p. 5 A tourist guide through treewidth. p. 0
[Bod98] Hans L Bodlaender. p. 5 A partial k-arboretum of graphs with bounded treewidth. p. 1
[Bol80] Bela Bollob as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. p. 7
[BR13a] Quentin Berthet and Philippe Rigollet. p. 2 Complexity theoretic lower bounds for sparse principal component detection. p. 6 p. 6
[BR13b] Quentin Berthet and Philippe Rigollet. p. 2 Complexity theoretic lower bounds for sparse principal component detection.
[COGHK+22] Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik. Statistical and computational phase transitions in group testing. p. 3
[DDL25] Jian Ding, Hang Du, and Zhangsong Li. p. 3 Low-degree hardness of detection for correlated Erdos–R enyi graphs. p. 3
[DKWB24] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. p. 3 Subexponential-time algorithms for sparse PCA. p. 3
[EH25] Dor Elimelech and Wasim Huleihel. p. 6 Detecting arbitrary planted subgraphs in random graphs. p. 6
[EH26] Dor Elimelech and Wasim Huleihel. p. 6 Robust detection of planted subgraphs in semi-random models. p. 6
[Gam21] David Gamarnik. p. 2 The overlap gap property: A topological barrier to optimizing over random structures. p. 2
[HKK+26] Jun-Ting Hsieh, Daniel M. p. 3 Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel. Rigorous implications of the low-degree heuristic
[HKP+17] Samuel B Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures
[Hop18] Samuel B Hopkins. Statistical Inference and the Sum of Squares Method. p. 2
[HS17] Samuel B Hopkins and David Steurer. p. 2 Efficient bayesian estimation from few samples: Community detection and related problems. p. 3
[Hul26a] Wasim Huleihel. p. 6 Fundamental limits of query-based subgraph detection. p. 3
[Hul26b] Wasim Huleihel. p. 6 Recovery of planted subgraphs. p. 6
[HW21] Justin Holmgren and Alexander S Wein. p. 3 Counterexamples to the Low-Degree Conjecture. p. 3
[Jer92] Mark Jerrum. p. 2 Large cliques elude the metropolis process. p. 0
[KWB22] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. p. 3 Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. p. 0
[LG24] Yuetian Luo and Chao Gao. p. 3 Computational lower bounds for graphon estimation via low-degree polynomials. p. 6
[LPRZ25] Daniel Z Lee, Francisco Pernice, Amit Rajaraman, and Ilias Zadik. p. 6 The fundamental limits of recovering planted subgraphs (extended abstract). p. 7
[Mao26] Songtao Mao. p. 3 The polynomial-time low-degree conjecture is false. p. 0
[MNWS+23] Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, and Ilias Zadik. Sharp thresholds in inference of planted subgraphs. p. 6
[MST19] Laurent Massoulie, Ludovic Stephan, and Don Towsley. p. 6 Planting trees in graphs, ´ and finding them back. p. 5
[O’D14] Ryan O’Donnell. p. 2 Analysis of Boolean functions. p. 3
[RS86] Neil Robertson and P. p. 5D Seymour. Graph minors. p. 0 ii. algorithmic aspects of tree-width. p. 5
[SW22] Tselil Schramm and Alexander S Wein. p. 3 Computational barriers to estimation from low-degree polynomials. p. 3
[SW25] Youngtak Sohn and Alexander S Wein. p. 3 Sharp phase transitions in estimation with low-degree polynomials. p. 3
[Wei22] Alexander S Wein. p. 3 Optimal low-degree hardness of maximum independent set. p. 6
[Wei23] Alexander S Wein. p. 3 Average-case complexity of tensor decomposition for lowdegree polynomials. p. 2
[Wei25] Alexander S Wein. p. 3 Computational complexity of statistics: New insights from low-degree polynomials. p. 2
[YZZ25] Xifan Yu, Ilias Zadik, and Peiyuan Zhang. p. 3 Counting stars is constant-degree optimal for detecting any planted subgraph. p. 4
Pruning redundant reasoning tokens
The paper's primary contribution is showing that vanishing low-degree advantage forces the noisy planted distribution to be asymptotically indistinguishable from the null. This conclusion is information-theoretic, meaning no test, efficient or otherwise, can distinguish TεPn from Qn with nonvanishing advantage. p. 5
How the training signal is built
The low-degree likelihood ratio L≤D denotes the orthogonal projection of the likelihood ratio onto polynomials of degree at most D in the observed coordinates. The squared norm is given by equation (3. p. 42) as a sum over isomorphism classes of subgraphs F, where the summand is related to NΓn(F) and automorphism factors. p. 0 This structure allows the proof to relate large-support contributions to low-degree pieces via an exact combinatorial representation involving isomorphism triples. p. 7
Where the gains come from
The gains stem from using treewidth to cut the decomposition tree into subtrees, breaking each large Fourier support into low-degree pieces that meet at only a few interface vertices. At and below criticality, noise destroys the remaining long cycles while the low-degree assumption rules out short cycles. p. 0 The final result is that for broad classes of planted graphs, vanishing low-degree advantage forces indistinguishability of the entire noised graph for any fixed positive amount of noise. p. 4
Model and Notation
The model involves a null distribution Qn = G(n, c/n) and a planted distribution Pn obtained by planting a uniformly random copy of a deterministic graph Γn into an independent sample from Qn. The noise operator Tε independently resamples every edge indicator with probability ε. p. 4 The Fourier basis is defined using the re(ω) function and the collection of orthonormal functions χS(ω). p. 3 The calculation of coefficients cLn(F•) involves relating containment probability to NΓn(F)Aut(F) (n)v(F). p. 7
Conclusion
The paper concludes that the low-degree heuristic, when combined with noise, provides a rigorous tool for establishing computational hardness results against concrete algorithms. The study shows that the structural assumptions in related conjectures are essential. p. 3 The program is carried to planted-subgraph models in sparse random graphs. p. 4
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI system for planted-subgraph detection can rigorously determine if a noisy version of a deterministic graph is asymptotically indistinguishable from a null distribution based on low-degree likelihood ratio bounds. This allows for the prediction of computational hardness against efficient noise tolerant distinguishers in the supercritical regime, as shown by Theorem 1.1 and Theorem 1.2.
-
The system can detect if a planted distribution converges to the null after noise by using a scan test over all possible subsets of vertices, which is proven to have vanishing total error when low-degree advantage vanishes (Lemma A.7). This provides a method for distinguishing distributions that are hard to separate via low-degree tests alone.
-
AI systems can be trained to identify structural properties of planted graphs, such as treewidth and girth, which dictate the behavior of the low-degree heuristic under noise. The system can use these properties to determine whether a graph is (l, C, a)-divisible (Lemma 4.4), leading to information-theoretic lower bounds on statistical distinguishability.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
- Interactive Proofs of Proximity for Model Evaluation