Research map / Graph learning / GNN architectures
Temporal Generalization Estimation in Evolving 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.
Proves that GNN representation distortion over evolving graphs is unavoidable and proposes SMART, a self-supervised (graph reconstruction) RNN-based estimator of post-deployment generalization error that requires no new labels.
Problem
Estimating how a pre-trained GNN's generalization error degrades over time on evolving graphs after deployment, without human annotation, given representation distortion as the graph grows.
Approach
Attribute estimation failure to inaccurate feature extraction under evolution and fix it by adapting a feature extractor post-deployment with self-supervised augmented graph reconstruction (structure via link prediction and feature reconstruction), feeding an RNN generalization-loss predictor.
Key results
- On OGB-arXiv with GCN, SMART achieves MAPE 2.1897 vs 10.5224 for linear regression and 9.5277 for DoC.
- On synthetic BA graphs (N0=1000, m=5), SMART reaches MAPE 4.2602% vs 74.1083% for linear regression.
- On DBLP with GCN, SMART MAPE is 3.4992 vs 16.4991 for linear regression; on Pharmabio, 1.3405 vs 32.3653.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SMART instead of linear regression for estimation | Generalization estimation · BA random graphs (six BA and Dual BA settings) | MAPE: 79.2431 -> 7.1817; 74.1083 -> 4.2602; 82.1677 -> 9.1173; 61.8048 -> 7.9038; 67.6442 -> 3.8288; 38.4884 -> 1.9947 | Helped |
| Use SMART instead of Linear with GCN backbone | Generalization estimation · OGB-arXiv | MAPE: 10.5224 -> 2.1897 | Helped |
| Use SMART instead of DoC with GCN backbone | Generalization estimation · OGB-arXiv | MAPE: 9.5277 -> 2.1897 | Helped |
| Use SMART instead of Supervised with GCN backbone | Generalization estimation · OGB-arXiv | MAPE: 2.1354 -> 2.1897 | No clear effect |
| Use SMART instead of Linear with GCN backbone | Generalization estimation · DBLP | MAPE: 16.4991 -> 3.4992 | Helped |
| Use SMART instead of Linear with GCN backbone | Generalization estimation · Pharmabio | MAPE: 32.3653 -> 1.3405 | Helped |
| Remove augmented graph reconstruction (M1) (ablation) | SMART · OGB-arXiv and Pharmabio | MAPE: null | Hurt |
| Replace RNN with an MLP (M2) (ablation) | SMART · Cornell | standard error: null | Hurt |
| Remove structure reconstruction loss (M3) (ablation) | SMART · Four evolving graph datasets | MAPE: null | Hurt |
| Remove feature reconstruction loss (M3) (ablation) | SMART · Four evolving graph datasets | MAPE: null | Hurt |
| Use graph reconstruction instead of omitting reconstruction (ablation) | SMART · OGB-arXiv | MAPE: 8.00% -> 2.19% | Helped |
| Continue post-deployment reconstruction fine-tuning | SMART · BA random graph | prediction performance improvement: 10% | Helped |
Surprising findings
- Naive RNN/linear estimators with a static feature extractor perform very poorly, with MAPE often exceeding 30% on real graphs.
- On GraphSAGE backbone on OGB-arXiv, SMART (5.27) is worse than supervised retraining (1.69) and more variable than on GCN.
Limitations
- Theory is for a single-layer GCN with Leaky ReLU and relies on assumptions like continuous features and ever-growing graphs with zero-mean features.
- Assumes labels are unchanged over evolution; future work targets changing labels, heterogeneous and spatio-temporal graphs.
- Requires a small fraction of labeled nodes (10%) before deployment for training the estimator.
Experimental setup
Datasets: OGB-arXiv DBLP Pharmabio Facebook 100 Barabási-Albert synthetic graphs Dual Barabási-Albert synthetic graphs
Benchmarks: OGB-arXiv DBLP Pharmabio Facebook 100 Barabási-Albert synthetic graphs
Metrics: MAPE standard error RMSE MAE
Baselines: Linear regression DoC Supervised retraining
Builds on: Barabási-Albert graph graph attention network DoC EvolveGCN
Closest papers by meaning
- EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs (AAAI 2020 · similarity 0.90)
- Quality Measures for Dynamic Graph Generative Models (ICLR 2025 · similarity 0.88)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.87)
- EvoluNet: Advancing Dynamic Non-IID Transfer Learning on Graphs (ICML 2024 · similarity 0.87)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.86)
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (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.