Research map / Graph learning / Knowledge and temporal graphs
Beyond Spatio-Temporal Representations: Evolving Fourier Transform for Temporal 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.
Proposes the Evolving Graph Fourier Transform (EFT), an invertible spectral transform for temporal graphs with evolving structure that approximates the joint-Laplacian eigendecomposition via a Kronecker product of time DFT and per-timestep GFT, and instantiates it in a transformer (EFT-T).
Problem
Spectral GNN transforms exist for static graphs but cannot capture spectra of temporal graphs whose structure evolves over time; naive joint eigendecomposition is computationally prohibitive (O(T^3) overhead).
Approach
Relax the variational form of the joint Laplacian of the dynamic graph to its pseudospectrum, giving a transform that is the Kronecker product of the DFT along time and per-timestep graph Fourier bases, enabling efficient, interpretable time-vertex spectral filtering inside a transformer.
Key results
- On Amazon Games, EFT-T reports Recall@10 of 77.78 vs 75.57 for the best baseline DGSR; NDCG@10 58.65 vs 55.70.
- On discrete datasets, EFT-T reaches MAP 0.672 on AS vs 0.233 for the best baseline LED-GAT, and F1 0.616 on Elliptic vs 0.575 for GCN-GRU.
- EFT yields lower reconstruction error than DFT and GFT in compaction experiments on temporal mesh graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EFT-T instead of DGSR | Sequential recommendation models · Beauty | Recall@10: 52.40 -> 53.23 | Helped |
| Use EFT-T instead of DGSR | Sequential recommendation models · Games | Recall@10: 75.57 -> 77.78 | Helped |
| Use EFT-T instead of DGSR | Sequential recommendation models · CDs | Recall@10: 72.43 -> 75.42 | Helped |
| Use EFT-T instead of DGSR | Sequential recommendation models · Beauty | NDCG@10: 35.90 -> 37.10 | Helped |
| Use EFT-T instead of DGSR | Sequential recommendation models · Games | NDCG@10: 55.70 -> 58.65 | Helped |
| Use EFT-T instead of DGSR | Sequential recommendation models · CDs | NDCG@10: 51.22 -> 54.99 | Helped |
| Use EFT-T instead of the strongest baseline | Dynamic graph link prediction · SBM | MAP: 0.200 -> 0.250 | Helped |
| Use EFT-T instead of the strongest baseline | Dynamic graph link prediction · SBM | MRR: 0.015 -> 0.024 | Helped |
| Use EFT-T instead of the strongest baseline | Dynamic graph link prediction · UCI | MAP: 0.032 -> 0.055 | Helped |
| Use EFT-T instead of the strongest baseline | Dynamic graph link prediction · UCI | MRR: 0.163 -> 0.181 | Helped |
| Use EFT-T instead of the strongest baseline | Dynamic graph link prediction · AS | MAP: 0.233 -> 0.672 | Helped |
| Use EFT-T instead of the strongest baseline | Dynamic graph link prediction · AS | MRR: 0.469 -> 0.689 | Helped |
Surprising findings
- The paper's own counterexample shows the proposed EFT matrix generally differs from the exact eigendecomposition of the joint Laplacian (Psi_D != Psi_AD).
Limitations
- Theory assumes bounded graph change rate and eigenvalue multiplicity of 1; the bound is loose and approximate.
- Only undirected/unsigned graphs are considered; signed and directed graphs are out of scope.
- EFT is not exactly equal to the eigendecomposition of the joint Laplacian in general.
Experimental setup
Datasets: Amazon Beauty Amazon Games Amazon CDs UCI AS SBM Elliptic Brain temporal mesh (dancer)
Benchmarks: Amazon Beauty Amazon Games Amazon CDs UCI AS SBM Elliptic Brain
Metrics: Recall@10 NDCG@10 MAP MRR F1 reconstruction error
Baselines: GRU4Rec+ Caser SASRec HGN TiSASRec FMLPRec SRGNN HyperRec DGSR GCN GAT DynGEM
Builds on: FMLPRec Graph Fourier Transform Discrete Fourier Transform Joint Fourier Transform
Closest papers by meaning
- Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.87)
- Supra-Laplacian Encoding for Transformer on Dynamic Graphs (NeurIPS 2024 · similarity 0.87)
- Generating Graphs via Spectral Diffusion (ICLR 2025 · similarity 0.87)
- GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2025 · similarity 0.87)
- HoloNets: Spectral Convolutions do extend to Directed Graphs (ICLR 2024 · similarity 0.87)
- Designing Specialized Two-Dimensional Graph Spectral Filters for Spatial-Temporal Graph Modeling (AAAI 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.