Temporal Generalization Estimation in Evolving Graphs
Bin Lu Tingyan Ma Xiaoying Gan Xinbing Wang Yunqiang Zhu Chenghu Zhou Shiyu Liang
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.