Understanding and Improving Laplacian Positional Encodings For Temporal GNNs
This work addresses a key bottleneck in temporal graph learning for applications like recommendation systems and traffic forecasting, offering incremental improvements in efficiency and understanding.
The paper tackled the challenges of extending Laplacian positional encodings to temporal graphs, such as high computational costs and unclear applicability, by providing a theoretical framework, reducing runtime by up to 56x, and identifying scenarios where these encodings improve performance.
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.