# Poisson Non-Backtracking Fingerprint

- ID: 2945
- Canonical URL: https://synthcore.org/idea/2945/poisson-non-backtracking-fingerprint
- API JSON: https://synthcore.org/api/idea/2945.json
- API Markdown: https://synthcore.org/api/idea/2945.md
- Verification status: unverified
- Source: [arXiv:2608.28539](https://arxiv.org/abs/2608.28539)
- Category: architecture
- Solves: accuracy, sample-efficiency, scalability
- ML areas: graph-nn, embedding, loss
- Math tags: graph-theory, spectral-theory, probability, statistics
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Add a fixed or lightly parameterized graph-level feature extractor based on short non-backtracking cycle counts, and concatenate its Poisson log-likelihood-ratio features with the output of a graph neural network. The feature scaling uses the paper's explicit means, so the network receives statistics that are approximately independent and correctly normalized rather than raw, highly correlated cycle counts.

## Mathematical statement

Theorem 1.3 states that for a base d-regular graph H on k vertices, the cycle counts C_t of a noisy random lift are close in total variation to independent Poisson variables with means mu_t. Here t is the cycle length, r is the number of rematched edges, n is the lift size, delta=2r/(nd) is the rematching fraction, B is the weighted non-backtracking matrix of the base graph, and nu_t=tr(B^t)/(2t) is its base-cycle contribution. The theorem gives mu_t=(1-delta)^t(nu_t-(d-1)^t/(2t))+(d-1)^t/(2t), with null random-regular mean mu_t^(0)=(d-1)^t/(2t). For independent Poisson counts, the log likelihood ratio is sum_t [C_t log(mu_t^(1)/mu_t^(0))-(mu_t^(1)-mu_t^(0))], where mu_t^(1)=mu_t. The total-variation approximation is asserted for lengths up to D=Omega(log n), motivating a short-cycle feature extractor. The implementation uses exact or stochastic estimates of C_t from powers of the observed graph's non-backtracking matrix.

## Key formulas

- $$\mu_t=(1-\delta)^t\left(\nu_t-\frac{(d-1)^t}{2t}\right)+\frac{(d-1)^t}{2t},\qquad \delta=\frac{2r}{nd},\qquad \nu_t=\frac{\operatorname{tr}(B^t)}{2t}.$$
- $$C_1,\ldots,C_D\ \approx\ \bigotimes_{t=1}^{D}\operatorname{Pois}(\mu_t),\qquad D=\Omega(\log n).$$
- $$\mu_t^{(0)}=\frac{(d-1)^t}{2t},\qquad \mu_t^{(1)}=(1-\delta)^t\left(\nu_t-\mu_t^{(0)}\right)+\mu_t^{(0)}.$$
- $$\phi(G)=\sum_{t=1}^{D}\left[C_t(G)\log\frac{\mu_t^{(1)}+\varepsilon}{\mu_t^{(0)}+\varepsilon}-\left(\mu_t^{(1)}-\mu_t^{(0)}\right)\right],\qquad z_t=\frac{C_t-\mu_t^{(0)}}{\sqrt{\mu_t^{(0)}+\varepsilon}}.$$

## Implementation notes

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.

## Disclaimer

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