Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lift

What the math gives to ML

The paper provides a constructive low-degree statistical representation of noisy random lifts: short cycle counts are approximately independent Poisson variables whose means are explicit functions of the base graph's weighted non-backtracking spectrum. This suggests a graph-neural-network front end that computes non-backtracking cycle statistics and feeds a Poisson likelihood-ratio embedding into a graph classifier, anomaly detector, or routing module. The transferable asset is not the random-lift application itself, but the principled conversion of many correlated local subgraph observations into approximately independent, variance-calibrated features with an explicit signal-to-noise scale. A clean test is whether these features improve detection of planted graph structure at matched parameters and whether performance follows the predicted dependence on rematching rate and cycle length.