Traversal-Invariant Positional Encoding for Serialized Graphs

Many systems represent graphs as sequences by visiting nodes one at a time, for example, a molecule written as a SMILES string or a program written as a token stream from an AST traversal. The same graph can be traversed in many ways, producing different sequences for the same underlying object. Sequence Transformers treat these as distinct inputs and produce distinct embeddings, even though the graph remains unchanged. Existing graph-native Transformers address this by operating directly on the graph, but many practical pipelines receive serialized inputs and cannot be redesigned. We provide a theoretical characterization in three parts. Tree-positional encoding achieves structural invariance for acyclic graphs under canonical-root serialization but is insufficient for cyclic graphs due to spanning-tree non-uniqueness. Augmenting with cycle-membership encoding derived from the canonical cycle basis introduces a traversal-invariant anchor on cycle vertices. The resulting Tree+Cycle Positional Encoding is a drop-in replacement for sinusoidal PE within graph-aware serialization pipelines (those preserving token-to-atom alignment for structural tokens), requiring no architectural changes to the sequence model. It applies to any domain where labeled graphs are given as sequences with this alignment property. We validate the approach on two testbeds. On synthetic cycle counting and ring membership tasks, it outperforms the GIN baseline by $2\times$ on cycle counting and matches it on ring membership, demonstrating that pre-computed cycle structure encoded as PE matches message-passing GNNs at end-task performance. On molecular property prediction, it achieves $0.977 \pm 0.029$ mean cosine similarity across re-rootings ($n = 24{,}960$), outperforms a parameter-matched graph-native Transformer (Graphormer) on BACE and BBBP, and enables fragment-level interpretability with $+5$ points on alert alignment over a methodologically matched sinusoidal baseline.