Communicability-Inspired Positional Encoding (CIPE)
For graph Transformer practitioners, CIPE provides a principled PE that consistently boosts performance, even on structure-biased models where other PEs fail, addressing the need for effective non-Euclidean positional encodings.
CIPE introduces a positional encoding for graph Transformers that uses communicability to define an attention-compatible geometry, improving structure-agnostic Transformers by 35.5% on average across seven benchmarks and outperforming existing PEs.
Positional encodings (PEs) are essential for Transformers. Yet designing effective PEs for non-Euclidean graphs remains challenging. Such encodings should ideally induce an Attention-Compatible Geometry for self-attention: not merely describing graph structure, but defining a geometry whose inner products reflect meaningful structural relatedness. To realize this geometry, we propose Communicability-Inspired Positional Encoding (CIPE), built from communicability, a measure between pairs of nodes that aggregates contributions from paths of all lengths. By construction, CIPE inner products recover communicability, converting global multi-path connectivity into an attention-ready similarity geometry. For practical Transformer training, we introduce dimensionality alignment, mapping graph-size-dependent CIPE representations to prescribed dimensions while faithfully preserving the induced geometry. Empirically, CIPE improves structure-agnostic Transformers by 35.5% on average across seven benchmarks, outperforming representative PEs; it also consistently improves structure-biased graph Transformers, where competing PEs often yield only marginal benefits. These results position CIPE as a principled framework for attention-compatible graph positional encodings.