Warm-Started Perron Positional Encoding

Integrate this at the input of a graph transformer, sparse-attention layer, or MoE router whose examples already provide a weighted graph. Construct a symmetric nonnegative adjacency matrix from the existing edge list: set $A_{ij}=C_{ij}$ when $C_{ij}>C_{\min}$ and zero otherwise; for unweighted edges, use $C_{ij}=1$. Maintain one vector $p\in\mathbb{R}^N$ per graph or per connected batch component. At every graph refresh, initialize $p^{(0)}$ from the previous step's normalized vector, add a small positive constant if some entries are zero, and run $R=2$--$8$ iterations: compute $z_i=\sum_{j\in\mathcal N(i)}A_{ij}p_j$, normalize $p_i\leftarrow z_i/(\sqrt{\sum_k z_k^2}+\epsilon)$, and stop early if $\|p^{(r+1)}-p^{(r)}\|_2<\tau$. This is a local sparse matrix-vector multiply and can use the model's existing edge-aggregation kernel. Feed the result to the network by concatenating $\alpha p_i$ to each node feature, adding $\beta p_i p_j$ to attention logits, or providing it as a router feature before top-k gating. Estimate the empirical contraction ratio from successive residuals, $\widehat\rho=\|p^{(r+1)}-p^{(r)}\|_2/\max(\|p^{(r)}-p^{(r-1)}\|_2,\epsilon)$, and use it for diagnostics or adaptive iteration counts; the paper-derived component is the power iteration and its dependence on the dominant spectral gap, while $\alpha$, $\beta$, $R$, and $\tau$ are tuned empirically. The first cheap experiment should use a 4--8 layer graph transformer on a molecular or citation benchmark with fixed sparse edges, comparing no positional encoding, Laplacian eigenvectors, and this encoding at equal aggregation FLOPs. Then apply dynamic edge-drop or node-motion perturbations while reusing the previous $p$. Record validation accuracy, wall-clock time, spectral-update rounds, and sensitivity to disconnected or nearly disconnected graphs. Success means matching or exceeding Laplacian positional-encoding accuracy with at least 2x fewer spectral-update iterations, faster loss descent at equal total FLOPs, and less degradation after graph changes.