Rooted Motif Positional Encoding

Integrate this at the input positional-encoding stage of a message-passing GNN or graph transformer. For a graph with adjacency matrix A and n nodes, compute K short rooted-walk channels without constructing dense matrix powers. Initialize q to an all-ones vector. For k from 1 through K, replace q by (A multiplied by q) divided by n, and append q as the k-th node feature channel. Compute a rooted triangle channel as the diagonal of A multiplied by A multiplied by A, divided by n cubed. With sparse graphs, use sparse matrix-vector products for walks and sparse matrix-matrix products or a triangle-counting kernel for triangles. Concatenate the original node features with all motif channels, standardize each channel across nodes, then apply LayerNorm and a learned linear projection before the first GNN or attention layer. Pseudocode is: q = ones(n); channels = []; for k in 1,...,K: q = sparse_matvec(A,q)/n; channels.append(q); triangle = diag(A @ A @ A)/n^3; z = Linear(LayerNorm(concat(x, channels, triangle))); output = GNN(z,A). Use K equal to 3 or 4 initially. The exact mathematical computation is the rooted-walk recursion and the finite-rank Vandermonde identifiability argument; eigenvalues do not need to be estimated in the first implementation. For a conditioning-aware variant, estimate the leading eigenvalues of A/n with Lanczos and reduce the weight of channels when eigenvalue gaps are small or when the empirical feature variance is near zero. First experiment: use a two-layer GCN and a graph transformer for node classification on four-block stochastic block model graphs whose blocks have equal expected degrees but different within-block connectivity patterns. Compare raw features, degree features, Laplacian positional encodings, and the proposed features at similar parameter counts. Use graphs with 500 to 2000 nodes and sparse matrix operations. The main success signal is higher test accuracy and better accuracy with fewer labeled nodes, while also reporting feature-computation time and robustness under edge noise.