# Learnable Spatial-Temporal Positional Encoding for Link Prediction

arXiv: https://arxiv.org/abs/2506.08309 · HTML: https://mlsanity.com/paper/2506.08309/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 56 references that are in the map.
- First posted on arXiv 10 Jun 2025.

## Builds on (most cited first, 30 of 30)

- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Towards Better Dynamic Graph Learning: New Architecture and Unified Library](https://mlsanity.com/paper/2303.13047/) (2023)
- [NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs](https://mlsanity.com/paper/2206.04910/) (2022)
- [Towards Better Evaluation for Dynamic Link Prediction](https://mlsanity.com/paper/2207.10128/) (2022)
- [Transformer for Graphs: An Overview from Architecture Perspective](https://mlsanity.com/paper/2202.08455/) (2022)
- [TCL: Transformer-based Dynamic Graph Modelling via Contrastive Learning](https://mlsanity.com/paper/2105.07944/) (2021)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Relational Attention: Generalizing Transformers for Graph-Structured Tasks](https://mlsanity.com/paper/2210.05062/) (2022)
- [Language in the Flow of Time: Time-Series-Paired Texts Weaved into a Unified Temporal Narrative](https://mlsanity.com/paper/2502.08942/) (2025)
- [TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphs](https://mlsanity.com/paper/2406.09639/) (2024)
- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [Class-Imbalanced Graph Learning without Class Rebalancing](https://mlsanity.com/paper/2308.14181/) (2023)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [MentorGNN: Deriving Curriculum for Pre-Training GNNs](https://mlsanity.com/paper/2208.09905/) (2022)
- [BACKTIME: Backdoor Attacks on Multivariate Time Series Forecasting](https://mlsanity.com/paper/2410.02195/) (2024)
- [RAG over Tables: Hierarchical Memory Index, Multi-Stage Retrieval, and Benchmarking](https://mlsanity.com/paper/2504.01346/) (2025)
- [DPPIN: A Biological Repository of Dynamic Protein-Protein Interaction Network Data](https://mlsanity.com/paper/2107.02168/) (2021)
- [PageRank Bandits for Link Prediction](https://mlsanity.com/paper/2411.01410/) (2024)
- [PyG-SSL: A Graph Self-Supervised Learning Toolkit](https://mlsanity.com/paper/2412.21151/) (2024)
- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [APEX2: Adaptive and Extreme Summarization for Personalized Knowledge Graphs](https://mlsanity.com/paper/2412.17336/) (2024)
- [Invariant Link Selector for Spatial-Temporal Out-of-Distribution Problem](https://mlsanity.com/paper/2505.24178/) (2025)

## Built on by (most cited first, 3 of 3)

- [Harnessing Generalist Agents for Contextualized Time Series](https://mlsanity.com/paper/2606.05404/) (2026)
- [OWLEYE: Zero-Shot Learner for Cross-Domain Graph Data Anomaly Detection](https://mlsanity.com/paper/2601.19102/) (2026)
- [Dynamic Link Prediction with Temporally Enhanced Signed Graph Neural Networks](https://mlsanity.com/paper/2605.26290/) (2026)

## Abstract (arXiv)

Accurate predictions rely on the expressiveness power of graph deep learning frameworks like graph neural networks and graph transformers, where a positional encoding mechanism has become much more indispensable in recent state-of-the-art works to record the canonical position information. However, the current positional encoding is limited in three aspects: (1) most positional encoding methods use pre-defined, and fixed functions, which are inadequate to adapt to the complex attributed graphs; (2) a few pioneering works proposed the learnable positional encoding but are still limited to the structural information, not considering the real-world time-evolving topological and feature information; (3) most positional encoding methods are equipped with transformers' attention mechanism to fully leverage their capabilities, where the dense or relational attention is often unaffordable on large-scale structured data. Hence, we aim to develop Learnable Spatial-Temporal Positional Encoding in an effective and efficient manner and propose a simple temporal link prediction model named L-STEP. Briefly, for L-STEP, we (1) prove the proposed positional learning scheme can preserve the graph property from the spatial-temporal spectral viewpoint, (2) verify that MLPs can fully exploit the expressiveness and reach transformers' performance on that encoding, (3) change different initial positional encoding inputs to show robustness, (4) analyze the theoretical complexity and obtain less empirical running time than SOTA, and (5) demonstrate its temporal link prediction out-performance on 13 classic datasets and with 10 algorithms in both transductive and inductive settings using 3 different sampling strategies. Also, L-STEP obtains the leading performance in the newest large-scale TGB benchmark. Our code is available at https://github.com/kthrn22/L-STEP.