Parity-Constrained Signed Propagation

Integrate the method at the graph-convolution propagation matrix, before the feature matrix H is multiplied by W_t. For an undirected graph, construct a binary edge-cycle matrix C over \mathbb F_2: each row is the edge-incidence vector of a selected short even cycle, such as all simple even cycles of length 4 and 6 found by bounded-depth enumeration. Set b=1 for every row, so Cs=b means each selected cycle has odd edge-sign parity and is therefore unbalanced. Compute one feasible solution s_0 and a nullspace basis B of C using Gaussian elimination over \mathbb F_2; every candidate signing is s=s_0+Bq for q uniformly sampled from \mathbb F_2^r. For each candidate, form A_sigma by multiplying each undirected edge weight by (-1)^{s_e}, then estimate J_K(s)=\sum_{k=1}^{K}\alpha_k\operatorname{tr}(A_\sigma^{2k}) using Hutchinson probes: draw Rademacher vectors v_j and use \operatorname{tr}(A^{2k})\approx R^{-1}\sum_j v_j^T A^{2k}v_j. Select the candidate minimizing J_K, optionally with normalized adjacency \widetilde A_\sigma and coefficients \alpha_k=\beta^k. The paper supplies the parity trace identity and cancellation rule; the engineer estimates the trace empirically and does not need to enumerate walk classes. First test on Cora, PubMed, and a synthetic d-regular graph with 20-40 message-passing layers. Compare unsigned GCN, one unconstrained random signing, and parity-constrained selected signing at matched parameters and FLOPs. Measure validation accuracy, gradient norm growth, activation norm versus depth, estimated spectral radius, and training loss. Success means substantially slower activation and gradient explosion and equal-or-better accuracy at depth 20 or more, with no meaningful inference-time overhead.