LEMD: Latent Environment Extrapolation and Message Disentanglement for Dynamic Graph Under Distribution Shift

Abstract

Dynamic graph neural networks (DyGNNs) are widely used to model evolving interactions, but may fail under data distribution shift. Due to limited and unreliable interventions and insufficient disentanglement, the existing dynamic graph domain generalization approaches lead to suboptimal results. We formalize a message sufficiency causal view: a node representation is fully mediated by its received message multiset. Building on this perspective, we propose Latent environment Extrapolation and Message Disentanglement (LEMD), a novel robust representation learning framework for dynamic graph domain generalization. A message extrapolation mechanism under soft uncertainty constraints is proposed to obtain the diverse counterfactual message distributions. Causal information is disentangled fully from the messages to suppress shortcuts via a recoverable evolving disentanglement module. We further provide rigorous theoretical analysis and proofs to ensure the effectiveness of LEMD. Across all six datasets and two tasks, LEMD consistently improves over state-of-the-art dynamic graph generalization baselines under distribution shift, and achieves the best performance increase of 7.7% relative compared to the suboptimal baseline. The code of LEMD for reviewer is available at https://github.com/W-WuJi/LEMD.