Revealing Concept Shift in Spatio-Temporal Graphs via State Learning

Kuo Yang, Yunhe Guo, Qihe Huang, Zhengyang Zhou, Yang Wang

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.

Illustration of concept shift where hidden environmental factors (e.g., weather) change the relationship between historical patterns and future outcomes.

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:

  1. 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.
  2. 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.
  3. 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.
Overview of the Samen framework, featuring prefix-suffix collaborative state learning and a hierarchical state compressor.

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

Abstract

Dynamic graphs are ubiquitous in the real world, presenting the temporal evolution of individuals within spatial associations. Recently, dynamic graph learning research is flourishing, striving to more effectively capture evolutionary patterns and spatial correlations. However, existing methods still fail to address the issue of concept shift in dynamic graphs. Concept shift manifests as a distribution shift in the mapping pattern between historical observations and future evolution. The reason is that some environment variables in dynamic graphs exert varying effects on evolution patterns, but these variables are not effectively captured by the models, leading to the intractable concept shift issue. To tackle this issue, we propose a State-driven environment inference framework (Samen) to achieve a dynamic graph learning framework equipped with concept generalization ability. Firstly, we propose a two-stage environment inference and compression strategy. From the perspective of state space, we introduce a prefix-suffix collaborative state learning mechanism to bidirectionally model the spatio-temporal states. A hierarchical state compressor is further designed to refine the state information resulting in concept shift. Secondly, we propose a skip-connection spatio-temporal prediction module, which effectively utilizes the inferred environments to improve the model's generalization capability. Finally, we select seven datasets from different domains to validate the effectiveness of our model. By comparing the performance of different models on samples with concept shift, we verify that our Samen gains generalization capacity that existing methods fail to capture.
BibTeX
@inproceedings{yang2025revealing,
  author = {Kuo Yang and Yunhe Guo and Qihe Huang and Zhengyang Zhou and Yang Wang},
  title = {{Revealing Concept Shift in Spatio-Temporal Graphs via State Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/392},
}
Figure