Introduction: The Challenge of Concept Shift
In spatio-temporal graph modeling—critical for applications like traffic forecasting and social link prediction—models typically rely on historical patterns to predict future states. However, these models often encounter concept shift. Unlike standard distribution shift, where data distributions change, concept shift occurs when the underlying relationship between history and the future is altered by hidden environmental variables.
For instance, a specific traffic pattern on a sunny day may lead to smooth flow, while the identical pattern during a snowstorm results in gridlock. If a model cannot infer these latent factors (like weather), its predictive accuracy suffers significantly when the environment shifts. This phenomenon is an intra-sample issue, where the evolution of a single sequence is disrupted by unobserved variables.
The Samen Framework
To address this, the authors introduce Samen (State-driven environment inference framework). Samen treats environment inference as a state-space problem, aiming to uncover the latent variables that drive concept shift. The architecture is built upon three primary components:
- Prefix-Suffix Collaborative State Learning: Traditional models are causal, looking only at the past (the prefix). Samen recognizes the "duality" of states: continuity (accumulated from history) and hysteresis (information retroactively inferable from future evolution). By employing a bidirectional approach, the model captures a holistic view of the environment.
- Hierarchical State Compressor: This module identifies "activatable" states—variables that may be dormant during historical observations but become pivotal in the future. It partitions data to isolate these specific triggers of concept shift.
- Skip-Connection Spatio-Temporal Predictor: The inferred environment states are integrated into the prediction process via skip-connections, allowing the model to adjust its output based on the uncovered latent context.
Experimental Evaluation
Samen was evaluated across seven real-world datasets, including social link forecasting (COLLAB, Yelp, ACT) and traffic flow prediction (PEMS04, PEMS08, SD-2019, GBA-2019). To rigorously test robustness, the researchers developed "Selective Samples" subsets—data specifically filtered for high levels of concept shift.
Key Results
- State-of-the-Art Performance: Samen outperformed leading baselines such as DGIB, DIDA, and CaST. Notably, it achieved a top AUC of 79.96% on the Yelp dataset.
- Resilience to Concept Shift: While baseline models showed sharp performance drops on the "Selective Samples," Samen remained stable, demonstrating superior generalization in the face of environmental changes.
- Efficiency: Despite its bidirectional modeling, the framework maintains linear time complexity $O(T \cdot L \cdot N)$, ensuring it remains computationally competitive.
- Ablation Studies: Results confirmed that the prefix-suffix module is the most critical component; its removal led to the most significant performance degradation.
Conclusion and Future Directions
Samen effectively mitigates the performance discount caused by concept shift in dynamic graphs by inferring latent environmental states. Future research may focus on making these latent states more interpretable by mapping them to explicit real-world factors and optimizing the framework for extremely long-term dependencies where state activation may be delayed.
Summary updated