Simple Path Structural Encoding for Graph Transformers
University of Trento, Trento, Italy
Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) · Vancouver, Canada · PMLR 267:857–873
In one sentence. SPSE replaces random-walk probabilities with approximate simple-path counts so graph transformers can encode cyclic and local structures that RRWP may treat identically.
Problem
Graph transformers require positional and structural encodings because global self-attention does not inherently represent graph topology. Relative Random Walk Probabilities (RRWP) encode pairwise structure efficiently, but can assign identical edge encodings to distinct local patterns—including edges in paths and even cycles—limiting the model’s ability to recognize cyclic or higher-order structure.
Main contributions
- Theoretical results identify graph pairs and edges that RRWP cannot distinguish and connect simple-path counts to cycle information.
- Simple Path Structural Encoding (SPSE) represents node pairs through counts of simple paths at multiple lengths.
- A DFS/BFS-based sequence of directed acyclic graph decompositions approximates otherwise expensive path counts.
- Controlled cycle counting and eight real benchmarks compare SPSE with RRWP in CSA, GRIT, and GraphGPS.
Method
SPSE constructs a matrix for each path length whose entries count self-avoiding paths between node pairs, normalizes the potentially large counts through repeated logarithmic transforms, and feeds the resulting tensor to the transformer’s edge-encoding network. Exact enumeration is avoided: repeated graph decompositions combine depth-first and breadth-first search to discover long and alternative paths. SPSE can replace RRWP without changing the number of trainable parameters.
Experimental setting
- Tasks
- Synthetic cycle counting; graph regression, graph classification, and node classification.
- Datasets
- ZINC, Peptides-functional, Peptides-structural, PCQM4Mv2, PATTERN, CLUSTER, MNIST, CIFAR10, plus 12,000 synthetic cycle graphs.
- Metrics
- MAE, average precision (AP), classification accuracy, and cycle-counting accuracy.
- Models
- CSA, GRIT, and GraphGPS with RRWP or SPSE; additional GNN and graph-transformer baselines.
- Protocol
- Ten seeds except one run for PCQM4Mv2; no task-specific hyperparameter tuning; two-sided t-tests at p ≤ 0.05.
Key results
Replacing RRWP with SPSE improves 21 of 24 paired benchmark results. For CSA and GRIT on molecular tasks, five of six comparisons improve significantly. Gains are smaller or absent where approximate path counting is difficult, notably the dense CLUSTER graphs. The synthetic experiment also shows higher cycle-counting accuracy for SPSE in all but one model/configuration pair.
| Model / dataset | Metric | SPSE | RRWP | Difference |
|---|---|---|---|---|
| CSA / ZINC | MAE ↓ | 0.061 ± 0.003 | 0.069 ± 0.003 | −0.008 |
| GRIT / Peptides-functional | AP ↑ | 0.6945 ± 0.0113 | 0.6803 ± 0.0085 | +0.0142 |
| GRIT / Peptides-structural | MAE ↓ | 0.2449 ± 0.0018 | 0.2480 ± 0.0025 | −0.0031 |
| GRIT / CIFAR10 | Accuracy ↑ | 77.022 ± 0.430 | 76.246 ± 0.954 | +0.776 |
When this work is relevant
This work is relevant for graph-transformer structural encodings, alternatives to random-walk positional encodings, learning cyclic molecular patterns, simple-path or self-avoiding-walk features, long-range graph learning, and drop-in edge encodings for CSA, GRIT, or GraphGPS.
Limitations
The approximate algorithm returns lower bounds rather than exact path counts and can miss paths in dense graphs, which may hurt performance. Precomputation ranges from about one to 80 hours on the reported datasets. Extremely large graphs, broader domains, and interactions with other transformer architectures require further study.
Citation
Persistent identifiers: PMLR: pmlr-v267-airale25a · arXiv:2502.09365 · https://doi.org/10.48550/arXiv.2502.09365