Mitigating Dynamic Graph Distribution Shifts via Spectral Augmentation

Abstract

Dynamic Graph Neural Networks (DyGNNs) are facing challenges with distribution shifts between training and test data that are similar but not identical. Existing DyGNNs for out-of-distribution scenarios primarily focus on discovering invariant patterns in the spatial domain, overlooking its impact on the structural properties in the spectral domain. In this paper, we propose a spectral-based graph augmentation framework designed to investigate and improve generalization behavior in dynamic graphs under distribution shifts. Specifically, we augment the input graph spectra into a mixture of shift components by maximizing the variance of spectral distance and propose an efficient approximation to reduce the computational cost brought by eigen-decomposition. Building on this, we develop a multi-encoder architecture in which each encoder targets a specific spectral shift component to generate referential representations. Our method adopts a new learning objective to encourage the model to rely on robust spectral properties for better generalization under distribution shifts. Extensive experiments on both real-world and synthetic datasets demonstrate that our proposed method significantly outperforms state-of-the-art approaches in node classification and link prediction tasks. Source codes are available at https://github.com/SSQiana/DSPA.