Research map / Graph learning / Knowledge and temporal graphs
Temporal Graph Neural Tangent Kernel with Graphon-Guaranteed
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 Temp-G3NTK, a temporal extension of the graph neural tangent kernel with generalization bounds and graphon convergence, evaluated on temporal graph classification (TUDataset temporal graphs) and temporal node property prediction (tgbn-trade).
Problem
Extending graph neural tangent kernels (GNTK) to temporal graphs whose topology and node features evolve over time, with rigorous guarantees on generalization and limit behavior.
Approach
Defines a temporal NTK by aggregating temporal neighborhoods with time encoding and applying the closed-form ReLU GNTK recursion at each snapshot time t; proves symmetry, PSD, a sequential-Rademacher generalization bound, and convergence of the kernel to a graphon NTK as graphs grow.
Key results
- Temp-G3NTK reaches 0.740 accuracy on INFECTIOUS and 0.700 on FACEBOOK, best among all listed baselines on all four temporal graph classification datasets (5-fold CV).
- On tgbn-trade node property prediction, Temp-G3NTK obtains test NDCG 0.380, above TGN (0.374) and DyRep (0.374), slightly below DyGFormer (0.388).
- Runtime on INFECTIOUS is 23.04 s for Temp-G3NTK versus 254.59 s for TGN and 217.70 s for GraphMixer, though Graph2Vec is faster (3.43 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Temp-G3NTK instead of the strongest reported baseline | Temporal graph classification · INFECTIOUS | accuracy: 0.670 ± 0.075 -> 0.740 ± 0.058 | Helped |
| Use Temp-G3NTK instead of TGN | Temporal graph classification · DBLP | accuracy: 0.580 ± 0.003 -> 0.600 ± 0.063 | Helped |
| Use Temp-G3NTK instead of WL-Subtree | Temporal graph classification · FACEBOOK | accuracy: 0.650 ± 0.075 -> 0.700 ± 0.138 | Helped |
| Use Temp-G3NTK instead of Shortest Path | Temporal graph classification · TUMBLR | accuracy: 0.580 ± 0.143 -> 0.630 ± 0.068 | Helped |
| Use Temp-G3NTK instead of DyGFormer | Temporal node property prediction · tgbn-trade validation | NDCG: 0.408 ± 0.006 -> 0.397 ± 0.039 | Hurt |
| Use Temp-G3NTK instead of DyGFormer | Temporal node property prediction · tgbn-trade test | NDCG: 0.388 ± 0.006 -> 0.380 ± 0.008 | Hurt |
| Set the number of BLOCK operations to 1 rather than selecting from {1, 2, 3} (ablation) | Temp-G3NTK · tgbn-trade | NDCG | Helped |
Surprising findings
- Temporal GNN baselines such as EvolveGCN score near or below chance on several datasets (e.g., 0.395 on TUMBLR), while simple kernels are competitive.
- Baseline accuracies are reported at their best timestamp over the temporal graph, which favors the baselines' highest score.
Limitations
- Generalization bound is data-dependent and relies on kernel regression with a Lipschitz loss; empirical gains are modest on node-level tasks (below DyGFormer).
- Node-level experiments use only tgbn-trade and a single hyperparameter choice (L=1) selected by search.
- Graph-level datasets are small (TUDataset temporal graphs with few hundred graphs), limiting scale evidence.
Experimental setup
Datasets: INFECTIOUS DBLP FACEBOOK TUMBLR REDDIT WIKIPEDIA LASTFM MOOC tgbn-trade
Benchmarks: INFECTIOUS DBLP FACEBOOK TUMBLR tgbn-trade
Metrics: classification accuracy NDCG runtime in seconds
Baselines: WL-Subtree kernel Shortest-Path kernel Random Walk kernel Graph2Vec NetLSD GL2Vec GraphMixer TGN EvolveGCN DyRep DyGFormer
Builds on: Graph Neural Tangent Kernel Graphon Neural Tangent Kernel TGN GraphMixer
Closest papers by meaning
- Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels (NeurIPS 2019 · similarity 0.93)
- Neural Tangent Kernels Motivate Cross-Covariance Graphs in Neural Networks (ICML 2024 · similarity 0.89)
- Efficient Graph Continual Learning via Lightweight Graph Neural Tangent Kernels-based Dataset Distillation (ICML 2025 · similarity 0.89)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.88)
- Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · 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.