Communicability-Inspired Positional Encoding (CIPE)

Yipeng Zhang, Zhongtian Sun, Pietro Liò, Kelin XiaarXiv 2026 · arXiv

TL;DR

The paper introduces Communicability-Inspired Positional Encoding (CIPE), a novel graph positional encoding framework that aligns graph structural representations with the inner-product similarity mechanism of self-attention. By deriving node encodings from diffusion-based network communicability, CIPE ensures that the similarity scores computed by a Transformer directly reflect global, multi-path structural relatedness. This approach yields massive performance boosts, improving structure-agnostic Transformers by an average of 35.5% across seven benchmarks.

What Problem Does This Paper Address?

Transformers have revolutionized sequence modeling, but adapting them to graphs remains a major challenge. Because self-attention is inherently permutation-invariant (it treats inputs as an unordered set), models require Positional Encodings (PEs) to understand graph topology.

While many graph PEs exist (e.g., Laplacian eigenvectors, random walk statistics, heat kernels), most are descriptor-oriented. They focus on capturing structural features of individual nodes but ignore how those features interact within the Transformer's self-attention mechanism. Self-attention relies on the inner product to compute similarity between nodes. If the inner product of two positional encodings doesn't map to a meaningful graph-theoretic relationship, a critical geometric mismatch occurs.

The authors address this gap by proposing the Attention-Compatible Geometry condition: a graph PE's geometry should be designed such that its inner products directly recover a principled measure of structural relatedness.

Methods

CIPE achieves an attention-compatible geometry by leveraging the concept of network communicability, which measures how easily information flows between two nodes by accounting for all possible connecting paths (weighted by length).

The core pipeline of CIPE is illustrated below:

Overview of the CIPE framework, showing graph diffusion, encoding construction, inner-product recovery, and dimensionality alignment.
  1. Diffusion-Based Encodings: Instead of using the full diffusion process at time $t$, CIPE simulates a discrete heat diffusion process up to time $t/2$. The encoding for node $i$ is the diffusion state vector at this halfway point.
  2. Inner Product Recovery: Crucially, due to the properties of the graph exponential, the inner product of two halfway encodings exactly recovers the full diffusion-based communicability between them at time $t$: $$\langle \text{CIPE}_i, \text{CIPE}_j \rangle = (e^{-tL})_{ij}$$
  3. Normalization: The raw encodings are symmetrically normalized to transform absolute diffusion responses into a scale-independent communicability cosine similarity.
  4. Dimensionality Alignment: Because raw CIPE dimensions depend on the number of nodes in a graph ($n$), the authors introduce an optimization procedure using Singular Value Decomposition (SVD) to project the encodings into a fixed target dimension ($d$) while minimizing distortion to the inner-product geometry.
  5. Scalable Approximation: To avoid the expensive $O(n^3)$ eigendecomposition on large graphs, they implement a fast Chebyshev polynomial approximation, dropping the time complexity to a scalable $O(nd + Kmd)$ for a graph with $m$ edges.

Datasets

The authors evaluated CIPE across 14 diverse graph benchmarks:

  • TUDataset (Graph Classification): IMDB-B, IMDB-M (social networks without node attributes), PROTEINS, and ENZYMES (bioinformatics).
  • MoleculeNet (Molecular Classification): BACE, BBBP, ClinTox, SIDER, Tox21, HIV, and MUV.
  • Quantum-Chemistry Regression: QM7, QM8, and QM9.

Key Insights and Ideas

  • Geometry-First Design: CIPE shifts the paradigm from "what structural features should we encode?" to "how can we make the encoding's geometry match the attention mechanism?".
  • Complementarity to Message Passing: Traditional PEs often provide redundant information when paired with Message-Passing Neural Networks (MPNNs). CIPE captures global, multi-path connectivity that local neighborhood aggregation misses, leading to consistent performance gains even on structure-biased backbones.
  • The 1D Sequence Connection: When specialized to cycle graphs (periodic 1D sequences), CIPE's inner products depend solely on relative positional offsets. This mirrors the behavior of Rotary Positional Embedding (RoPE) used in large language models, hinting at CIPE's potential for periodic sequence data like polymer SMILES strings.

Key Results

The authors tested CIPE on two backbones: a structure-agnostic Vanilla Transformer (VTr) and a structure-biased Message-Passing Transformer (MPTr).

  • Vanilla Transformer (VTr) Boosts: On the four TUDataset benchmarks, CIPE improved accuracy over the baseline VTr by an average of 49.0%, with a 75.5% relative improvement on the ENZYMES dataset. On the QM7/8/9 regression tasks, it reduced Mean Absolute Error (MAE) by an average of 17.5%.
  • Outperforming Existing PEs: CIPE consistently beat established encodings like LapPE, RWSE, CycleSE, and HKSE. This was especially clear on the node-attributeless IMDB datasets, proving that CIPE injects a highly effective structural geometry.
  • State-of-the-Art Competitiveness: When integrated into the structure-biased MPTr backbone, CIPE achieved the top performance across all seven MoleculeNet datasets, outperforming complex self-supervised pre-training paradigms (like GraphMAE and GraphCL) and specialized graph Transformers (like GraphGPS).

Limitations and Future Work

While the authors introduced a Chebyshev approximation to handle larger graphs, the initial setup still requires computing the graph Laplacian and handling matrix operations that scale with the target embedding dimension.

For future work, the authors suggest exploring CIPE's application to intrinsically periodic sequence representations (such as polymers). Additionally, the operator-driven paradigm established here could inspire new positional encodings based on other domain-specific graph operators beyond the standard Laplacian diffusion.

Summary updated

Abstract

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.
BibTeX
@misc{zhang2026communicability,
  author = {Yipeng Zhang and Zhongtian Sun and Pietro Liò and Kelin Xia},
  title = {{Communicability-Inspired Positional Encoding (CIPE)}},
  year = {2026},
  eprint = {2606.25293},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.25293},
}
Figure