Uncertainty-Aware Disentangled Dynamic Graph Attention Network for Out-of-Distribution Generalization

Dynamic graph neural networks, i.e., DyGNNs, have been extensively explored in literature to handle structural and temporal properties in graphs. On the one hand, there naturally exist distribution shifts in real-world scenarios relevant to dynamic graphs. On the other hand, the dynamics may further bring extra uncertainties to patterns in dynamic graphs. However, existing DyGNNs merely exploit variant patterns with respect to labels under distribution shifts, failing to accurately make predictions when there exist distribution shifts together with uncertain patterns from training data to test data. To deal with this issue, in this paper we propose to handle spatio-temporal distribution shifts in dynamic graphs via the discovery and utilization of invariant patterns, taking uncertainties in patterns into account, where the invariant patterns include structures and features whose predictive abilities are stable across distribution shifts. Nevertheless, we face the following key challenges: i) How to discover the complex invariant and variant spatio-temporal patterns involving time-varying topological structures and node-level features; ii) How to utilize the invariant and variant patterns to deal with the spatio-temporal distribution shifts in dynamic graphs; iii) How to handle the pattern uncertainties upon capturing the hidden invariance and variance with a theoretical guarantee. To tackle these challenges, we propose the Information Bottleneck guided Disentangled Dynamic Graph ATtention network (IB-D$^{2}$2 GAT). Our proposed IB-D$^{2}$2 GAT model is able to effectively handle spatio-temporal distribution shifts with uncertainties in dynamic graphs through discovering variant and invariant spatio-temporal patterns via information bottleneck. Specifically, we propose a disentangled spatio-temporal attention network to capture the invariant and variant patterns. Next, guided by the information bottleneck principle, we propose the distribution-based invariance optimization strategy which injects stochasticity into the invariant pattern identification so as to prevent the variant information from influencing the prediction, thus eliminating the spurious impacts of variant patterns. We further theoretically show that our proposed tailored invariance optimization strategy can lead to accurately capturing the invariant patterns with stable predictive abilities and therefore is capable of handling distribution shifts. Experiments on multiple real-world datasets and one synthetic dataset demonstrate the superiority of our method over state-of-the-art baselines under distribution shifts.