Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Shortest-Path Encodings for Graph Transformers

2 minute read

Published:

TL;DR: For Graph Transformers, the shortest path distance dist(i,j) between every node pair can be used as an attention bias — biasing attention scores to decrease with distance, encoding the graph's metric structure without message passing.

Why Shortest Paths?

In Graphormer (Ying et al., 2021), every pair of nodes can attend to each other. But without structural information, the model has no way to know that nodes 1 hop apart should interact more strongly than nodes 10 hops apart.

Shortest-path distance (SPD) encoding injects this directly as an attention bias:

A_{ij} = softmax_j( QᵢKⱼᵀ / √d + φ_SPD(dist(i,j)) )

Where φ_SPD is a learned embedding: one scalar per distance value (0, 1, 2, 3, …, max_dist, ∞).

What It Captures

  • Immediate neighbours (dist=1): strongest attention bias
  • 2-hop neighbours (dist=2): moderate bias
  • Distant nodes (dist=10): small or negative bias
  • Disconnected (dist=∞): special “no path” embedding

The model learns how distance should affect attention strength — this is not fixed (e.g., always decaying); the learned φ_SPD can assign different weights to each distance bucket.

All-Pairs Shortest Paths: Computation Cost

Computing all-pairs shortest paths (APSP) costs O(N · (N +E)) with BFS from every node. For small graphs (N < 1000): cheap, precomputable. For large graphs (N > 100,000): prohibitive.

This is why SPD encoding is primarily used for small-graph tasks (molecules with N < 100, protein structure graphs with N < 500).

SPD vs LapPE vs RWPE

EncodingTypeCapturesCost  
LapPENode PEGlobal positionO(k·E·T)
RWPENode PELocal structural roleO(K·E)
SPDEdge/pair PEGraph metric distancesO(N·(N+E))

SPD is a pairwise encoding — it’s not a node property but a pair property. It cannot be used as a standard node embedding; it must be injected into the attention mechanism as a bias.

Beyond SPD: Distance Encoding (DE)

Distance Encoding (Li et al., 2020) uses SPD from each node to a set of landmark nodes as a node-level encoding. With landmark set S:

pe_v = [dist(v, s₁), dist(v, s₂), ..., dist(v, s_k)]

This converts pairwise distances into node features (by fixing anchor nodes), making it usable as standard node PE. With random landmark selection, it approximates SPD information efficiently.

Summary

SPD encoding directly injects graph metric structure into Graph Transformer attention. It is simple, interpretable, and effective for small graphs. For large graphs, it is too expensive — use RWPE or LapPE instead, which capture distance information implicitly through local structure.

References

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic — atoms of different types bonded together — and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win — and when don’t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.