Research map / Graph learning / Knowledge and temporal graphs
Improving Temporal Link Prediction via Temporal Walk Matrix Projection
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.
Unifies relative encodings for temporal link prediction as functions of temporal walk matrices and proposes TPNet, which uses time-decayed walk matrices maintained via random feature propagation with JL-style guarantees.
Problem
Temporal link prediction relies on relative encodings that are computationally expensive to build (graph queries/sampling per link) and ignore temporal information.
Approach
Shows that existing relative encodings (DyGFormer, PINT, NAT, CAWN) are functions of temporal walk matrices with different score functions; proposes a time-decayed temporal walk matrix and maintains it implicitly via random projection of node representations updated incrementally at each interaction, which preserves inner products with theoretical guarantees.
Key results
- TPNet achieves the best average rank on transductive random-negative AP (1.08) across 13 datasets, outperforming DyGFormer (3.15).
- TPNet reaches up to 33.3x speedup over DyGFormer (SOTA baseline) on LastFM, and 71.5x over CAWN.
- On MOOC, TPNet AP improves from 89.15 (TGN, second best) to 96.39 under transductive random negative sampling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TPNet instead of the strongest baseline | Temporal link prediction · Most of the 13 benchmark datasets, transductive random-negative setting | AP | Helped |
| Use TPNet instead of DyGFormer | Temporal link prediction on LastFM · LastFM | inference speed: 33$\times$ speedups | Helped |
| Add pairwise node representations and decoded pairwise features (ablation) | TPNet · Temporal link prediction | performance | Helped |
| Add time-decay weighting to temporal walk matrix construction (ablation) | TPNet · Temporal link prediction | performance | Helped |
| Apply ReLU and log scaling to decoded pairwise features (ablation) | TPNet · Temporal link prediction | training stability | Helped |
| Vary node representation dimension (ablation) | TPNet · MOOC and LastFM | performance | Mixed |
Surprising findings
- Existing link-wise methods (except CAWN) ignore temporal information, with score functions always equal to 1, so entries reduce to walk counts.
- Removing the log/ReLU scaling of pairwise features causes unstable training and sometimes numerical overflow.
Limitations
- Matrix construction (time decay score) requires manually predefined settings and may not suit long-term dependency networks.
- Time decay hyperparameter lambda must be grid-searched per dataset.
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 AUC-ROC running time GPU memory
Baselines: JODIE DyRep TGAT TGN CAWN EdgeBank TCL GraphMixer NAT PINT DyGFormer
Builds on: DyGFormer CAWN NAT PINT DyGLib
Closest papers by meaning
- TAMI: Taming Heterogeneity in Temporal Interactions for Temporal Graph Link Prediction (NeurIPS 2025 · similarity 0.90)
- Future Link Prediction Without Memory or Aggregation (NeurIPS 2025 · similarity 0.89)
- Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs (NeurIPS 2024 · similarity 0.87)
- TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphs (NeurIPS 2024 · similarity 0.87)
- TGB-Seq Benchmark: Challenging Temporal GNNs with Complex Sequential Dynamics (ICLR 2025 · similarity 0.87)
- Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Models (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.