Evolving graphs are prevalent in real-world systems where nodes and edges continuously expand over time, resulting in persistent topological changes across temporal snapshots. As the graph expands, the increasing structural discrepancy between earlier and later timesteps often leads to poor generalization-a phenomenon widely recognized as Temporal out-of-distribution (TOOD) generalization. This issue has spurred growing research interest in generalized graph learning. Existing approaches often rely on modeling latent environments or incorporating structural causal reasoning, but they frequently face scalability limitations when applied to rapidly expanding graphs. In this work, we carry out a detailed analysis of temporal drift in evolving graphs and identify two complementary forms: structural role drift reflected by changes in degree proportions, and semantic drift measured by embedding divergence. To capture this graph evolution, we propose PromptEG, a scalable prompt-based framework that generates node-specific prompts using degree signals and KL-divergence between representations. These prompts are optimized via consistency and contrastive objectives, and injected into GNNs to enhance temporal generalization. Experiments on largescale evolving graphs-containing up to 500 K edges and tens of thousands of nodes-demonstrate that PromptEG achieves strong long-horizon generalization while maintaining high computational efficiency.

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.