Research map / Graph learning / Knowledge and temporal graphs
Learnable Spatial-Temporal Positional Encoding for Link Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes L-STEP, a simple temporal link prediction model that uses a learnable DFT-based positional encoding module plus MLP node-link-positional encoder instead of attention, evaluated on 13 datasets and TGB.
Problem
Temporal link prediction on time-evolving graphs needs positional encodings that are learnable, track time-evolving topology and features, and remain efficient without costly attention mechanisms.
Approach
A learnable positional encoding module applies a learnable complex-valued Fourier filter to the sequence of a node's past positional encodings to approximate the current encoding, which is then combined with node/link features via MLPs only (no attention), giving linear complexity in number of nodes.
Key results
- Transductive random-NSS AP: ranks first on average (avg rank 1.85) across 13 datasets, e.g., UN Vote AP 73.40 vs 55.55 for DyGFormer.
- On TGB, ranks 2nd on tgbl-review (test MRR 0.411) and 3rd on tgbl-coin (test MRR 0.711) per the open leaderboard.
- Outperforms PINT on Enron and UCI in transductive and inductive settings with random NSS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use L-STEP instead of the strongest baseline | Temporal link prediction · 13 classic datasets, transductive, random negative sampling | AP | Mixed |
| Use L-STEP instead of PINT | Temporal link prediction · Enron and UCI, transductive and inductive, random negative sampling | AP and ROC-AUC: Enron transductive AP: 81.60 ± 0.67 -> 93.96 ± 0.36; UCI transductive ROC-AUC: 94.89 ± 0.15 -> 97.62 ± 0.23 | Helped |
| Use L-STEP instead of the leaderboard method | Temporal link prediction · tgbl-review | Test MRR: 0.521 ± 0.015 vs 0.411 ± 0.011 | Hurt |
| Use L-STEP instead of the leaderboard method | Temporal link prediction · tgbl-coin | Test MRR: 0.762 ± 0.004 vs 0.711 ± 0.0185 | Hurt |
Surprising findings
- On several datasets (e.g., MOOC, Social Evo., Reddit inductive) L-STEP is not the best, with FreeDyG or DyGFormer leading.
Limitations
- On some datasets (e.g., Social Evo., MOOC) it trails the best baseline.
- Theoretical slow-change bound assumes eigenvectors vary little across timestamps.
- Relies on hand-picked hyperparameters such as L, K and t_gap.
Experimental setup
Datasets: Wikipedia Reddit MOOC LastFM Enron Social Evo. UCI Flights Can. Parl. US Legis. UN Trade UN Vote
Benchmarks: Wikipedia Reddit MOOC LastFM Enron Social Evo. UCI Flights Can. Parl. US Legis. UN Trade UN Vote
Metrics: AP ROC-AUC MRR average rank
Baselines: JODIE DyRep TGAT TGN CAWN TCL GraphMixer DyGFormer FreeDyG PINT TNCN NAT
Builds on: DyGFormer TGAT TGN Laplacian positional encoding
Closest papers by meaning
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.89)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.88)
- Supra-Laplacian Encoding for Transformer on Dynamic Graphs (NeurIPS 2024 · similarity 0.88)
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.87)
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.87)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.