MagResPE: Forest-Normalized Magnitude Residual Positional Encoding for Graph Transformers

Graph Transformers rely on positional encodings (PEs) to expose graph structure to attention, yet practical positional encodings provide only a finite structural interface. We introduce MagResPE, a deterministic multi-scale node PE derived from graph magnitude by measuring the ridge-regularized residual from an exact forest reference. This forest normalization gives every forest an explicit zero baseline while retaining non-forest structure across metric scales. We derive an all-orders BFS-shell expansion of the forest-prediction defect, whose coefficients are determined by same-shell edges and redundant shortest-path parents. Its second-order coefficient captures triangles and redundant two-hop geodesics, and the expansion yields a girth-controlled first nonzero order for the positive-ridge residual. We further prove a regular-subdivision separation: for arbitrarily prescribed finite horizons, connected graphs can share identical RRWP rooted row-profile multisets while exhibiting distinct small-q MagResPE onset orders. An exact cycle folding law further gives the sharp RRWP separation horizon. Empirically, on ZINC-12K, augmenting RRWP with MagResPE reduces test MAE from 0.0638 ± 0.0036 to 0.0600 ± 0.0021. Matched formulation controls and a SignNet spectral-node control do not reproduce this gain, indicating that it is not explained by raw magnitude or by the tested spectral-node augmentation. Using the same fixed MagResPE configuration, the hybrid also improves mean RRWP performance on Peptides-struct and PascalVOC-SP. Standalone replacement is not consistently competitive, supporting MagResPE as a complementary rather than universal PE. Together, these results suggest that forest-normalized graph magnitude is a promising basis for complementary positional encoding in Graph Transformers.