Research map / Graph learning / Knowledge and temporal graphs
Supra-Laplacian Encoding for Transformer on Dynamic Graphs
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.
Introduces SLATE, a fully-connected spatio-temporal graph transformer whose positional encoding is the spectrum of a supra-Laplacian built from a multi-layer transformation of discrete-time dynamic graphs, plus a cross-attention edge module for dynamic link prediction.
Problem
Graph transformers on discrete-time dynamic graphs lose structural and temporal information when all nodes at multiple snapshots are connected by self-attention, and existing dynamic GTs encode space and time separately and rely on sub-graph sampling.
Approach
Cast a DTDG as a multi-layer graph, clean it (remove isolated nodes, add virtual nodes, add temporal self-connections) so the supra-Laplacian is connected, use its first k eigenvectors as a unified spatio-temporal positional encoding for a single-layer fully-connected transformer, and predict links with a cross-attention edge module over node pairs' historical embeddings.
Key results
- Average AUC of 95.12 on five DTDG datasets versus 93.62 for the best prior DTDG model HTGN.
- Average AUC of 96.88 on six CTDG-protocol datasets versus 83.41 for DyGFormer.
- Ablation on Enron, CanParl, USLegis, UNtrade shows the SLATE encoding and Edge module each improve AUC over a LapPE + sinusoidal baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SLATE encoding instead of separate LapPE and sinusoidal time encoding (ablation) | SLATE without Edge module · CanParl | AUC: +6.47 points | Helped |
| use SLATE encoding instead of separate LapPE and sinusoidal time encoding (ablation) | SLATE without Edge module · USLegis | AUC: +8.08 points | Helped |
| use SLATE encoding instead of separate LapPE and sinusoidal time encoding (ablation) | SLATE without Edge module · UNtrade | AUC: +3.77 points | Helped |
| add the Edge module (ablation) | SLATE with LapPE + sinusoidal encoding · CanParl | AUC: +7.25 points | Helped |
| add the Edge module (ablation) | SLATE with LapPE + sinusoidal encoding · Enron | AUC: +1.57 points | Helped |
| add the Edge module (ablation) | SLATE · Enron, USLegis, UNVote | AUC: +5.8 points on Enron; +2.6 points on USLegis; +6.4 points on UNVote | Helped |
| remove isolated nodes before supra-Laplacian computation (ablation) | SLATE · Colab | AUC: 86.73 -> 90.84 | Helped |
| remove isolated nodes before supra-Laplacian computation (ablation) | SLATE · USLegis | AUC: 66.57 -> 95.80 | Helped |
| add a virtual node to connect snapshot clusters (ablation) | SLATE · Enron | AP | Helped |
| use a smaller time window instead of all snapshots (ablation) | SLATE · most datasets | AP | Helped |
| use average pooling instead of max pooling (ablation) | SLATE edge representation · USLegis, UNVote, Trade | AUC: 93.03 -> 94.50; 87.92 -> 99.72; 93.37 -> 96.71 | Helped |
| use mean pooling with k=2 rather than k=3 (ablation) | SLATE edge representation · USLegis | AUC: 94.50 -> 95.35 | Helped |
Surprising findings
- Keeping isolated nodes in the supra-graph drops Colab AUC from 90.84 to 86.73 and USLegis AUC from 95.80 to 66.57.
- Considering all temporal snapshots did not yield better results than a small time window (w=3 or 4).
Limitations
- Transductive setting; cannot generalize to unseen nodes.
- Scaling to very large graphs remains challenging for transformers.
Experimental setup
Datasets: CanParl USLegis Flights Trade UNVote Contact HepPh AS733 Enron Colab SBM
Benchmarks: CanParl USLegis Flights Trade UNVote Contact HepPh AS733 Enron Colab SBM
Metrics: AUC AP
Baselines: GCN GIN EvolveGCN GRUGCN DySat VGRNN HTGN ROLAND-GT JODIE DyRep TGAT TGN
Builds on: ROLAND Laplacian positional encoding Performer FlashAttention TCL
Closest papers by meaning
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.88)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.88)
- Learnable Spatial-Temporal Positional Encoding for Link Prediction (ICML 2025 · similarity 0.88)
- Spatio-Spectral Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.87)
- Beyond Spatio-Temporal Representations: Evolving Fourier Transform for Temporal Graphs (ICLR 2024 · similarity 0.87)
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.