# Cross-Degree Certificate Against Recurrent Oscillation - ID: 1629 - Canonical URL: https://synthcore.org/idea/1629/cross-degree-certificate-against-recurrent-oscillation - API JSON: https://synthcore.org/api/idea/1629.json - API Markdown: https://synthcore.org/api/idea/1629.md - Verification status: failed_benchmark - Source: [arXiv:2608.00340](https://arxiv.org/abs/2608.00340) - Category: dynamics - Solves: stability, accuracy - ML areas: graph-nn, rnn, ssm, regularization - Math tags: graph-theory, dynamical-systems, combinatorics, control-theory - Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10 ## 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. ## 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. ## Key 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}.$$ ## 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 - Status: failed_benchmark - Mechanism evidence: yes - Mechanism confirmed: no - Practical verdict: harms - Verdict: 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. ### Mechanism check - Verdict: 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. - Confidence: 9/10 - 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. ### Practical benchmark - Paired seeds: 8 - Baseline mean: 0 - Idea mean: 0 - p-value: 0.0152 - Paired wins: 1/8 - Benchmark verdict: idea worse (significant) ## Artifacts - [bench_cross_degree.py](https://synthcore.org/code/608/bench_cross_degree.py) - [bench_report.json](https://synthcore.org/code/608/bench_report.json) - [certificate_experiment.py](https://synthcore.org/code/608/certificate_experiment.py) - [report.md](https://synthcore.org/code/608/report.md) - [report_bench_2026-08-31T194422.md](https://synthcore.org/code/608/report_bench_2026-08-31T194422.md) - [results.json](https://synthcore.org/code/608/results.json) - [Download all files as ZIP](https://synthcore.org/download/608) ## Disclaimer AI-generated research hypothesis, automatically tested. Not peer-reviewed.