mlsanityData to 13 Oct 2026

Temporal Generalization Estimation in Evolving Graphs

arXiv 2404.04969 ↗First posted 7 Apr 2024cs.LG cs.AIcited by 2

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) are widely deployed in vast fields, but they often struggle to maintain accurate representations as graphs evolve. We theoretically establish a lower bound, proving that under mild conditions, representation distortion inevitably occurs over time. To estimate the temporal distortion without human annotation after deployment, one naive approach is to pre-train a recurrent model (e.g., RNN) before deployment and use this model afterwards, but the estimation is far from satisfactory. In this paper, we analyze the representation distortion from an information theory perspective, and attribute it primarily to inaccurate feature extraction during evolution. Consequently, we introduce Smart, a straightforward and effective baseline enhanced by an adaptive feature extractor through self-supervised graph reconstruction. In synthetic random graphs, we further refine the former lower bound to show the inevitable distortion over time and empirically observe that Smart achieves good estimation performance. Moreover, we observe that Smart consistently shows outstanding generalization estimation on four real-world evolving graphs. The ablation studies underscore the necessity of graph reconstruction. For example, on OGB-arXiv dataset, the estimation metric MAPE deteriorates from 2.19% to 8.00% without reconstruction.

Key facts. Cited by 2 papers in the map (data through 13 Oct 2026). Builds on 31 of its 45 references that are in the map. First posted on arXiv 7 Apr 2024.

Builds on

31 of 45 references.

References · 31

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
  2. 2017Graph Attention Networkscited by 8,888
  3. 2017Inductive Representation Learning on Large Graphscited by 6,303
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,157
  5. 2014DeepWalk: Online Learning of Social Representationscited by 1,544
  6. 2017Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networkscited by 1,327
  7. 2020Graph Contrastive Learning with Augmentationscited by 1,207
  8. 2019Strategies for Pre-training Graph Neural Networkscited by 965
  9. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  10. 2016Temporal Convolutional Networks for Action Segmentation and Detectioncited by 504
  11. 2020Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classificationcited by 503
  12. 2019EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphscited by 445
19 more
  1. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  2. 2021Graph Self-Supervised Learning: A Surveycited by 289
  3. 2018Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shiftcited by 241
  4. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 192
  5. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 187
  6. 2023Geometric Latent Diffusion Models for 3D Molecule Generationcited by 185
  7. 2022ROLAND: Graph Learning Framework for Dynamic Graphscited by 131
  8. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  9. 2021Predicting with Confidence on Unseen Distributionscited by 116
  10. 2020Are Labels Always Necessary for Classifier Accuracy Evaluation?cited by 104
  11. 2021What Does Rotation Prediction Tell Us about Classifier Accuracy under Varying Testing Environments?cited by 63
  12. 2019Temporal Network Embedding with Micro- and Macro-dynamicscited by 51
  13. 2022TREND: TempoRal Event and Node Dynamics for Graph Representation Learningcited by 50
  14. 2022Spatio-Temporal Graph Few-Shot Learning with Cross-City Knowledge Transfercited by 43
  15. 2021Retrain or not retrain: Conformal test martingales for change-point detectioncited by 29
  16. 2022On the Strong Correlation Between Model Invariance and Generalizationcited by 23
  17. 2020Lifelong Learning of Graph Neural Networks for Open-World Node Classificationcited by 22
  18. 2023Graph Out-of-Distribution Generalization with Controllable Data Augmentationcited by 9
  19. 2022Interpretable Distribution Shift Detection using Optimal Transportcited by 2

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Confidence and Dispersity as Signals: Unsupervised Model Evaluation and Rankingcited by 1
  2. 2025Constraint Multi-class Positive and Unlabeled Learning for Distantly Supervised Named Entity Recognitioncited by 0