Poisson Non-Backtracking Fingerprint

Integrate this at the graph-level readout of a message-passing GNN, before the final MLP classifier. The input is a sparse d-regular or approximately regular graph G with N vertices; choose D=4, 6, or min(12, floor(log(N)/2)) for the first experiment. Construct the directed-edge non-backtracking matrix B_G: its rows and columns are directed edges e=(u->v), and B_G[e,f]=1 when f=(v->w) with w != u. Estimate C_t(G)=tr(B_G^t)/(2t). For small graphs compute sparse matrix-vector products and the trace exactly; for larger graphs use q Rademacher Hutchinson probes g_j, with C_t approximately equal to (1/(2tq)) times the sum of g_j^T B_G^t g_j, followed by clamping to nonnegative values. Obtain d from the graph and set mu0[t]=(d-1)^t/(2t). If the base H and rematching rate r are known, calculate B_H, nu[t]=tr(B_H^t)/(2t), delta=2r/(Nd), and mu1[t]=(1-delta)^t*(nu[t]-mu0[t])+mu0[t]. If they are unknown, estimate mu1[t] from positive training graphs using a shrinkage mean, while retaining mu0 from matched random-regular null graphs. Form z_t and phi, concatenate [z_1,...,z_D,phi] to the GNN pooled embedding, and train the final classifier normally. Pseudocode: counts=zeros(D); for probe in probes: v=g; for t in 1..D: v=B_G@v; counts[t]+=g.T@v/(2*t*q); z=(counts-mu0)/sqrt(mu0+eps); phi=sum(counts[t]*log((mu1[t]+eps)/(mu0[t]+eps))-(mu1[t]-mu0[t])); h=concat(GNN_pool(G),z,phi); logits=MLP(h). The paper supplies the Poisson means and likelihood; Hutchinson variance, the base spectrum, and unknown rematching rates are estimated empirically. First test on synthetic 2- or 3-regular graphs with N=128, 256, and 512, comparing noisy lifts against uniformly random regular graphs. Use a 3-layer GIN baseline with identical hidden width and matched training FLOPs. Pre-register three mechanism tests: first, at fixed N, fingerprint advantage should decrease as delta increases and become negligible when (1-delta)^t*(nu[t]-mu0[t]) is below sqrt(mu0[t]); second, adding lengths up to D should improve log-likelihood in the ordering predicted by the sum of Poisson KL terms sum_t[mu1[t]log(mu1[t]/mu0[t])-mu1[t]+mu0[t]], with observed AUC ordering matching predictions within 20%; third, replacing non-backtracking counts with ordinary closed-walk traces should lose advantage at larger t because of backtracking noise. Remove only the fingerprint features for the ablation. Falsify the transfer if the fingerprint does not improve over the matched GNN at delta=0.1 or if its advantage fails to decline with the predicted signal gap.