# Understanding and Improving Laplacian Positional Encodings For Temporal GNNs

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [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)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Rotary Position Embedding for Vision Transformer](https://mlsanity.com/paper/2403.13298/) (2024)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Towards Better Dynamic Graph Learning: New Architecture and Unified Library](https://mlsanity.com/paper/2303.13047/) (2023)
- [Do We Really Need Complicated Model Architectures For Temporal Networks?](https://mlsanity.com/paper/2302.11636/) (2023)
- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey](https://mlsanity.com/paper/2005.07496/) (2020)
- [Discrete-time Temporal Network Embedding via Implicit Hierarchical Learning in Hyperbolic Space](https://mlsanity.com/paper/2107.03767/) (2021)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Generalized Laplacian Positional Encoding for Graph Representation Learning](https://mlsanity.com/paper/2210.15956/) (2022)
- [Temporal Link Prediction: A Unified Framework, Taxonomy, and Review](https://mlsanity.com/paper/2210.08765/) (2022)
- [Efficient Neural Common Neighbor for Temporal Graph Link Prediction](https://mlsanity.com/paper/2406.07926/) (2024)
- [Dynamic Graph Representation Learning with Neural Networks: A Survey](https://mlsanity.com/paper/2304.05729/) (2023)
- [UTG: Towards a Unified View of Snapshot and Event Based Models for Temporal Graphs](https://mlsanity.com/paper/2407.12269/) (2024)
- [Spectral properties of the Laplacian of multiplex networks](https://mlsanity.com/paper/1307.2090/) (2013)
- [DyANE: Dynamics-aware node embedding for temporal networks](https://mlsanity.com/paper/1909.05976/) (2019)
- [Dynamic Graph Transformer with Correlated Spatial-Temporal Positional Encoding](https://mlsanity.com/paper/2407.16959/) (2024)

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

- [Revisiting Node Affinity Prediction in Temporal Graphs](https://mlsanity.com/paper/2510.06940/) (2025)
- [Invariant-Stratified Propagation for Expressive Graph Neural Networks](https://mlsanity.com/paper/2603.01388/) (2026)
- [RAPNet: Accelerating Algebraic Multigrid with Learned Sparse Corrections](https://mlsanity.com/paper/2605.26854/) (2026)

## Abstract (arXiv)

Temporal graph learning has applications in recommendation systems, traffic forecasting, and social network analysis. Although multiple architectures have been introduced, progress in positional encoding for temporal graphs remains limited. Extending static Laplacian eigenvector approaches to temporal graphs through the supra-Laplacian has shown promise, but also poses key challenges: high eigendecomposition costs, limited theoretical understanding, and ambiguity about when and how to apply these encodings. In this paper, we address these issues by (1) offering a theoretical framework that connects supra-Laplacian encodings to per-time-slice encodings, highlighting the benefits of leveraging additional temporal connectivity, (2) introducing novel methods to reduce the computational overhead, achieving up to 56x faster runtimes while scaling to graphs with 50,000 active nodes, and (3) conducting an extensive experimental study to identify which models, tasks, and datasets benefit most from these encodings. Our findings reveal that while positional encodings can significantly boost performance in certain scenarios, their effectiveness varies across different models.