Graph Structural Encodings from $k$-FWL Algebra: Operations, Budgets, and Readouts

Structural encodings supply graph statistics to learning models, yet the field lacks a common language for comparing them: a new channel family is proposed, a gain is reported, and it is rarely clear whether the gain reflects new structural information or only better access to information already present. This paper supplies that language for $k$-dimensional folklore Weisfeiler–Leman refinement ($k$-FWL). On a fixed finite graph we show that each refinement round is generated exactly by pointwise operations and contractions whose replacement branches share a single pivot, and we build three dictionary families on this operation: polynomial, endpoint, and joint channels. Each family carries an explicit budget (degree $Q$, tuple order $k$, retained objects $m$, moment $P$) with sufficient refinement-round membership bounds, so constructions are compared in a common currency rather than by channel count. We then separate what an encoding contains from what a readout can see: channelwise powers are injective on exact vectors and multisets, adding no raw distinction, yet the same expansion changes what mean pooling observes, and every joint triple first moment collapses to $n^{-2}$ on equal-size regular graphs of minimum degree at least one. Graph-pair experiments on BREC and within-graph experiments on ZINC, QM9, OGB, LRGB, and TU graphs evaluate nodes, edges, and vertex pairs against automorphism orbits at matched width; endpoints combined with powers improve pair discrimination on four TU datasets with 95% intervals above zero, while node and edge changes are smaller and can reverse. We report unresolved comparisons alongside averages so that high capacity is not mistaken for full recovery. Operations, budgets, readouts, and object domains jointly determine the distinctions an encoding exposes, and greater discrimination alone does not establish a downstream benefit.