✗ Failed on benchmark 2026

Cross-Degree Certificate Against Recurrent Oscillation

Implementation & benchmark of arXiv:2608.00340 — Extinction thresholds in a graph-based model of HIV infection dynamics

Usefulness7/10

Difficulty5/10

Novelty7/10

Dynamics Stability Accuracy Graph nn Rnn Ssm Regularization Graph theory Dynamical systems Combinatorics Control theory

Source paper: Extinction thresholds in a graph-based model of HIV infection dynamics arXiv:2608.00340 ⓘ · analyzed Aug 31, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Add a graph-structural anti-oscillation constraint to binary or thresholded recurrent message-passing networks. The paper shows that a partition with sufficiently many cross-partition neighbors creates an exact period-two orbit, so training can explicitly penalize such high cross-degree bipartite cores or choose the threshold above their strength.

Formulas

$$r_*(G)=\max_{V=U_0\cup U_1}\min\left\{\min_{v\in U_0}|N(v)\cap U_1|,\min_{v\in U_1}|N(v)\cap U_0|\right\}.$$

$$\min_{v\in U_0}|N(v)\cap U_1|\ge R,\quad \min_{v\in U_1}|N(v)\cap U_0|\ge R\ \Longrightarrow\ x_{t+2}=x_t.$$

$$c_*(W)=\max_{V=U_0\cup U_1}\min\left\{\min_{v\in U_0}\sum_{u\in U_1}|W_{vu}|,\min_{v\in U_1}\sum_{u\in U_0}|W_{vu}|\right\};\quad R>c_*(W)\ \text{blocks this certificate}.$$

Mathematical statement

Let G=(V,E) be the recurrent communication graph and let R be the integer activation threshold. For a partition V=U_0\cup U_1, define the cross-degree d_{U_1}(v)=|N(v)\cap U_1| for v\in U_0 and d_{U_0}(v)=|N(v)\cap U_0| for v\in U_1. If every vertex in both parts has cross-degree at least R, initializing U_0 as healthy and U_1 as infected produces alternating infected/dead sets: I_t=U_1,D_t=U_0 for odd t and I_t=U_0,D_t=U_1 for even t. Thus the recurrent state has period two. Define r_*(G)=\max_{V=U_0\cup U_1}\min\{\min_{v\in U_0}d_{U_1}(v),\min_{v\in U_1}d_{U_0}(v)\}. A sufficient and, for the paper's state-transition model, necessary condition for existence of a 2-cycle is R\le r_*(G). In a weighted neural graph, replace cross-degree by cross-gain c_{U_1}(v)=\sum_{u\in U_1}|W_{vu}| and use the same minimum-cross-gain certificate.

Implementation notes

Integrate this at the recurrent message-passing layer, especially for binary-state GNNs, spiking networks, hard-concrete gates, or quantized state-space models. Use the update h_{t+1}=Threshold_R(W h_t+b), or the paper's three-state rule, where h_t is the node-state vector and W is the signed or nonnegative message matrix. At each training checkpoint, approximately find a dangerous partition with a spectral bipartition followed by local Kernighan-Lin swaps; compute its minimum cross-degree for an unweighted graph or minimum cross-gain for weighted W. Add L_cycle=lambda_cycle sum_v ReLU(R-c_U(v))^2 over the candidate partition, or reject or rewire edges that increase the estimated certificate. Pseudocode: partition V; repeat local swaps maximizing the minimum cross-gain; calculate c_min; loss += lambda_cycle*ReLU(R-c_min)^2; perform the normal gradient step. The exact mechanism imported from the paper is the alternating-state proof and the R <= r_* boundary. The maximizing partition and r_* are estimated heuristically because exact optimization is combinatorial. First experiment: train a 2-layer binary recurrent GNN on synthetic node-labeling tasks over random regular, bipartite, and expander graphs, comparing baseline training with the penalty. Sweep R and measure whether a random initialization enters x_{t+2}=x_t. The predicted signature is a sharp increase in period-two trajectories when R crosses the estimated r_*(G), and suppression when R exceeds the certificate by 10 to 20 percent; the measured transition should track the estimated boundary within one threshold unit.

Verification

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Significantly worse ✗

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built a deterministic weighted threshold-dynamics verifier for the cross-degree certificate, including exact partition search and a baseline-versus-safe-threshold comparison. All three mechanism predictions were confirmed: the nontrivial period-two boundary matched 1 <= R <= c* exactly, weight scaling produced the predicted linear boundary, and setting R=1.1c* suppressed the certified orbit in every sweep. This demonstrates the mechanism, but not improved trained-GNN accuracy.

Agent confidence: 9/10

Baseline: R=1.0; period-two rate from 300 random initial states = 0.0833
Idea: R=1.1c*=2.2; period-two rate from 300 random initial states = 0.0000; exact c*=2.0
Prediction checks: Boundary confirmed; scaling boundary errors were 0 at scales 0.5, 1.0, 1.5, and 2.0; 10% threshold suppression confirmed at all scales

Limitations: Only a small 8-node bipartite weighted threshold system was tested. The experiment used exact partition enumeration rather than the proposed spectral/local-swap approximation, and did not train or evaluate a recurrent GNN, node-labeling task, learned penalty, signed weights, non-bipartite graphs, or accuracy/runtime tradeoffs.

How to run: python3 certificate_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.00340) Sep 2, 2026

Significantly WORSE than the tuned baseline (+127.4%, p=0.0152, wins 1 / 8 paired seeds).

Benchmark: Dynamics forecasting
Model: rnn_small
Paired seeds: 8
Baseline mean: 0.0024
Idea mean: 0.0055
Effect (Δ): 0.0031 (+127.4%; negative = idea better)
Wins: 1 / 8 paired seeds
p-value: 0.0152 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±73.7%
Mechanism: Not confirmed ✗
Practical effect: Hurts
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in actuated-pendulum dynamics task and rnn_small GRU were tested; no binary/thresholded message-passing GNN, explicit graph rewiring, signed-weight certificate, spectral/local-swap partition approximation, longer rollouts, or threshold-state recurrent architecture was evaluated. The differentiable hidden-state penalty is a proxy for the graph certificate rather than an exact cross-degree constraint.

How to run: python3 bench_cross_degree.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

The recurrent anti-oscillation penalty was tested on the registered dynamics/rnn_small benchmark with matched systems and eight paired seeds. The tuned baseline had mean test MSE 0.0024029803, while the best idea setting had 0.0054648099; paired delta was +0.0030618296 with permutation p=0.0152, so the idea was significantly worse. The trained-model mechanism signature was also not confirmed: the two-step/adjacent hidden-state ratio increased from 2.1946 to 2.8453.

Baseline: mean test MSE 0.0024029802589211613 over 8 seeds; best lr=0.006, weight_decay=0.0
Comparison: delta_mean=0.0030618296150350943, idea_wins=1/8, permutation p_value=0.0152, verdict=idea worse (significant)
Idea: mean test MSE 0.005464809873956256 over 8 seeds; best lr=0.006, weight_decay=0.0, lambda_cycle=0.1

Benchmark result