Communicability-Inspired Positional Encoding (CIPE)

How can we design positional encodings for graph-based Transformers that move beyond simple structural descriptors to create a geometry naturally compatible with the self-attention mechanism? The authors aim to bridge the gap between graph topology and the inner-product similarity used by Transformers.

The authors propose Communicability-Inspired Positional Encoding (CIPE). They leverage the concept of graph communicability—a measure that aggregates the influence of all possible paths between two nodes—to define a positional geometry. By utilizing the graph heat kernel (the solution to the diffusion equation on a graph), they construct node embeddings such that the inner product between any two nodes corresponds to their pairwise communicability. To ensure these encodings are usable in standard Transformer architectures, the authors introduce a dimensionality alignment procedure that maps these graph-size-dependent representations into a fixed-dimensional space while minimizing geometric distortion.

CIPE consistently outperforms existing positional encoding methods across 14 benchmarks, including molecular property prediction and social network analysis. It provides a 35.5% average improvement on structure-agnostic Transformer backbones and continues to offer performance gains even when integrated into graph Transformers that already incorporate structural biases. The results suggest that aligning positional geometry with the attention mechanism is a powerful, principled strategy for graph representation learning.

Most existing graph positional encodings focus on describing local or spectral features without considering how those features interact with the attention mechanism's inner-product similarity. CIPE provides a unified framework that translates global, multi-path graph connectivity into a format that Transformers can directly exploit, offering a more mathematically grounded approach to graph-based attention.