Research map / Graph learning / Knowledge and temporal graphs
Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in 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.
Applies time-aware De Bruijn Graph Neural Networks (DBGNN) to predict temporal betweenness and closeness centralities in 13 temporal graphs, outperforming GCN, EVO, TGN and the sampling-based ONBRA while being much faster than exact computation.
Problem
Exact computation of temporal betweenness and closeness centralities based on shortest time-respecting paths is computationally expensive for large temporal graphs, and static centralities can misrepresent node importance in temporal networks.
Approach
Use a static but time-aware higher-order De Bruijn graph representation of time-respecting paths as input to a DBGNN, trained end-to-end as a node-level regression model on ground-truth temporal centralities from a training window and applied to a future test window with possibly unseen nodes.
Key results
- DBGNN achieves temporal closeness Spearman correlations of 0.893 to 0.992 across datasets, versus 0.285 to 0.861 for GCN, and outperforms GCN on all 13 datasets for closeness.
- For temporal betweenness, DBGNN outperforms GCN on 12 of 13 datasets, and outperforms TGN in all but one dataset (ants-2-1), with relative Spearman gains up to 151% over GCN (ants-2-2).
- Speed-up of fitting plus inference over exact centrality computation ranges from about 3.5x to 43.7x for closeness and 6.4x to 1077x for betweenness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DBGNN instead of static GCN | temporal closeness prediction · 13 temporal graphs | Spearmanr: 13 % for ants-2-1; 241 % for eu-email-dept4 | Helped |
| use DBGNN instead of static GCN | temporal betweenness prediction · 12 of 13 temporal graphs | Spearmanr: 3 % (sp-hospital) to 151 % (ants-2-2) | Helped |
| use DBGNN instead of static GCN | temporal betweenness prediction · haggle | Spearmanr: 8 % | Hurt |
| use DBGNN instead of EVO | temporal closeness prediction · 13 temporal graphs | Spearmanr: 35 % (ants-2-2) to 732 % (ants-2-1) | Helped |
| use DBGNN instead of EVO | temporal betweenness prediction · nine temporal graphs | Spearmanr: up to 139 % (sp-highschool-2013) | Helped |
| use DBGNN instead of TGN | temporal closeness prediction · 13 temporal graphs | Spearmanr | Helped |
| use DBGNN instead of TGN | temporal betweenness prediction · ants-2-1 | Spearmanr | Hurt |
| use DBGNN instead of ONBRA | temporal betweenness estimation · large temporal graphs | Spearmanr | Helped |
| use DBGNN instead of exact centrality calculation | temporal centrality prediction · 13 temporal graphs | speed-up: 3.5 to 43.7 for temporal closeness; 6.4 to 1077 for temporal betweenness | Helped |
| add dropout layers (ablation) | DBGNN and GCN · temporal centrality prediction | prediction performance | Hurt |
Surprising findings
- EVO outperforms DBGNN on betweenness for four datasets (ants-2-2, eu-email-dept4, eu-email-dept2, haggle), and GCN outperforms DBGNN on haggle betweenness.
- ONBRA failed to return results on three datasets (sp-hypertext, sp-hospital, and eu-email-dept2 for Spearman) where DBGNN performs well.
Limitations
- Hyperparameters such as delta, maximum order k, and layer sizes were not systematically optimized.
- Models are trained and tested within the same graph (transductive forecasting on a split), not in an inductive cross-graph setting.
- Betweenness prediction is substantially harder than closeness prediction, with lower absolute rank correlations.
Experimental setup
Datasets: ants-1-1 ants-1-2 ants-2-1 ants-2-2 company-emails eu-email-dept2 eu-email-dept3 eu-email-dept4 sp-hospital sp-hypertext sp-workplace sp-highschool-2013
Benchmarks: ants-1-1 ants-1-2 ants-2-1 ants-2-2 eu-email-dept4 eu-email-dept2 eu-email-dept3 sp-workplace sp-hypertext sp-hospital haggle manufacturing-email
Metrics: Spearman rank correlation hitsIn10 MAE speed-up
Baselines: GCN EVO TGN ONBRA
Builds on: DBGNN EVO TGN GCN ONBRA
Closest papers by meaning
- Temporal-Aware Evaluation and Learning for Temporal Graph Neural Networks (AAAI 2025 · similarity 0.88)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.87)
- Improving Temporal Link Prediction via Temporal Walk Matrix Projection (NeurIPS 2024 · similarity 0.87)
- TAMI: Taming Heterogeneity in Temporal Interactions for Temporal Graph Link Prediction (NeurIPS 2025 · similarity 0.87)
- TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphs (NeurIPS 2024 · similarity 0.87)
- Future Link Prediction Without Memory or Aggregation (NeurIPS 2025 · 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.