Cayley-Residual Graph Convolution

(1) Integration point: replace a standard GCN message-passing layer on a fixed graph by a two-branch layer. The structured branch uses Gamma=Z_n and one shift operator per inverse pair {s,-s}; the residual branch uses only original edges absent from the selected Cayley host. For variable-size graph batches, construct a separate cyclic host per graph or pad to a common n.

(2) MVP pseudocode:

input node features X and adjacency A_G
compute n, m, Delta; set d=max(Delta, smallest d with n*d even)
initialize permutation logits P and generator scores a[1:n//2]
for each training step:
    Pi = Sinkhorn(P/tau)                 # soft vertex labeling
    for s in 1,...,floor((n-1)/2):
        A_s = cyclic_shift(s)
        score[s] = sum_u A_G[u, Pi_inverse(Pi[u]+s)]
    S = top_k(score[s]+a[s], k=d//2)
    A_H = sum_{s in S}(A_s + A_{-s})
    A_res = relu(A_G-A_H)
    Y = activation(sum_{s in S} A_s @ X @ W_s + lambda*A_res @ X @ W_res)
    loss = task_loss(Y) + eta*edge_count(A_res)
update P, a, W with Adam; use straight-through top-k at inference

Use a sigmoid relaxation for generator selection during early training and anneal the Sinkhorn temperature tau. Normalize each shift and the residual adjacency by their respective degrees. Initialize lambda=1 so training begins near ordinary message passing.

(3) The paper supplies the inverse-pair decomposition and degree lower bound. The permutation, generator scores, and residual coefficient are learned empirically. Compute Delta* directly from n and Delta by incrementing Delta until n*Delta* is even. Measure the actual residual density |E_res|/m; the theorem is only a lower-bound diagnostic and need not be tight.

(4) First cheap experiment: train on Cora and on synthetic randomly permuted cycle, grid, and SBM graphs. Compare a 2-layer GCN, a full-edge graph transformer, a Cayley-only layer, and this residual layer at matched hidden width. Record validation accuracy, peak edge-memory, edge operations, and wall-clock time. A positive result is at least 30% fewer edge operations or lower memory at matched accuracy; on graphs generated from known Cayley structures, the Cayley-only model should nearly match full message passing while using substantially fewer distinct operators.