Invariant Graph Representations for Continuous-Time Dynamic Graphs Under Distribution Shifts

1 Introduction

Many real-world systems exhibit continuously evolving relational structures, which are naturally modeled as dynamic graphs [Zhang et al., 2025]. Existing dynamic graph models can be broadly categorized into Discrete-Time Dynamic Graphs (DTDGs) [Ahmed and Chen, 2016; Ma et al., 2019], which represent evolution as a sequence of temporal snapshots, and Continuous-Time Dynamic Graphs (CTDGs) [Peng et al., 2025; Yuan et al., 2025a; Li et al., 2017; De Winter et al., 2018], which capture fine-grained structural changes via continuous node and edge updates. Although existing methods have achieved significant success in modeling temporal dynamics, they predominantly overlook robustness under out-of-distribution (OOD) scenarios.

∗ Shanshan Feng is the corresponding author.

Therefore, this paper focuses on invariant representation learning for CTDGs under OOD scenarios. While techniques such as subgraph extraction [Deng and Shen, 2024; Li et al., 2024a] and attention mechanisms [Ranjan et al., 2020] can partially alleviate distribution shifts, they remain vulnerable to exploiting spurious correlations [Chang et al., 2020]. For example, in the link prediction setting illustrated in Figure 1, a triadic closure pattern (highlighted in red) constitutes the invariant subgraph underlying the formation of the target link (u, v). However, because a bridging link (x, u) (highlighted in blue), also appears before (u, v) in most training graphs, the model may incorrectly treat (x, u) as the invariant subgraph for (u, v). As a result, at test time, the model may falsely predict the existence of (u, v) based solely on (x, u), ignoring the absent of the triadic closure pattern.

Recent structural causal model (SCM) based methods [Li et al., 2025a; Sui et al., 2022; Wang et al., 2025; Fan et al., 2022] have been proposed to mitigate spurious correlations by identifying and intervening on invariant subgraphs, either across multiple environments or through sampling-based interventions. However, these approaches implicitly assume a fixed or bounded graph structure, where the set of nodes and candidate edges remains stable over time, as in static graphs or DTDGs. Under this assumption, causal invariance can be meaningfully defined and estimated over a shared structural support. In contrast, CTDGs allow nodes and edges to be added or removed at arbitrary time points, resulting in a non-stationary and exponentially expanding space of graph topologies. This fundamentally challenges existing SCMbased intervention mechanisms.

In this paper, we propose Continuous-time Invariant Representation (CIR), a novel method that captures invariant representation and mitigates OOD effects from a new SCM perspective. To effectively address OOD generalization in CTDGs, CIR is designed to satisfy three essential properties: (1) robust mitigation of OOD distribution shifts, which is fundamental for generalization across unseen environments; (2) simultaneous capture of invariant subgraphs across both structural and temporal dimensions, which is crucial in CTDGs where graph topology and event timing evolve continuously; and (3) computationally efficient causal interventions, necessitated by the exponentially large space of possible structural-temporal subgraphs.

CIR is theoretically grounded in a structural causal model termed the Independent and Confounded Causal Model (ICCM), which explicitly models both in-distribution and OOD environments. Directly intervening on all possible structural and temporal subgraphs is computationally infeasible. To address this challenge, we leverage the Normalized Weighted Geometric Mean (NWGM) [Xu et al., 2015] to efficiently approximate the expected interventional outcome, substantially reducing computational cost. We instantiate ICCM within a practical deep learning framework. The architecture first employs dual subgraph extractors to capture causal structural and temporal patterns. An environment memory bank is then maintained to learn environment-specific representations, which are used to condition the prediction process. To approximate the expected outcome of causal interventions defined in ICCM, we aggregate environment-conditioned predictions using the NWGM. Finally, the causal structural and temporal patterns are encoded into invariant representations, and the model performs predictions based on the learned invariant representations together with the environment representations. The main contributions of this paper are summarized as follows:

• To the best of our knowledge, we are the first to investigate invariant representation learning problem for CTDGs under OOD shifts.
• We introduce ICCM, a novel structural causal model that characterizes invariant causal subgraphs in CTDGs, and develop an efficient intervention strategy based on the NWGM to approximate interventional predictions, avoiding exhaustive enumeration of structural and temporal subgraphs.
• We design a framework named CIR that instantialize ICCM, enabling the joint learning of invariant structural and temporal representations along with environmentspecific features.

2 RelatedWork

In this section, we review two areas closely related to our study: dynamic graph neural networks and invariant graph representation.

DynamicGraphNeural Networks. Dynamic graph neural networks encompass two primary classifications: DiscreteTime Dynamic Graphs (DTDGs) [Ma et al., 2019; Qin et al., 2023] and Continuous-Time Dynamic Graphs (CTDGs) [Li et al., 2017; De Winter et al., 2018; Li et al., 2023]. DTDGs comprise a sequence of static graph snapshots captured at regular time intervals [Sankar et al., 2020; Yu et al., 2018; Mahdavi et al., 2018]. CTDGs capture the evolution of graphs by considering modifications on the graph that occur continuously rather than discretely at predefined time steps [Xu et al., 2020; Trivedi et al., 2019; Feng et al., 2023]. However, these GNNs focus primarily on modeling graph dynamics while overlooking robustness to OOD scenarios.

Invariant Graph Representation. Invariant learning enhances the robustness of GNNs by identifying stable, environment-invariant patterns. Existing approaches fall broadly into two categories: disentangled learning and causal learning. Disentangled learning [Yuan et al., 2025b; Ning et al., 2025; Li et al., 2024b] aims to learn representations in which latent factors are separated and interpretable, capturing distinct variations in the data. Such representations have been shown to improve robustness to adversarial attacks and enhance generalization. However, these methods are limited in their ability to identify causal variables that remain invariant in the presence of shortcuts or spurious correlations. Causal inference methods [Li et al., 2025b; Wu et al., 2022] focus on unveiling and comprehending the true causal variables that drive observed phenomena. On realworld graphs, uncovering these causal variables becomes an act of explanation, revealing the "why" behind intricate relationships. However, most of these methods are largely restricted to static settings. To extend causal inference into dynamic scenarios, DIDA [Zhang et al., 2022] has been proposed as an invariant rational discovery framework for DTDGs. However, DIDA requires constructing an intervention set for each snapshot, making it computationally intensive when applied to CTDGs. EAGLE [Yuan et al., 2023] employs a VAE-based model as an environment sample generation network. However, when the number of environments is large and the available sample size is limited, the generated samples may not adequately represent the underlying environments, thereby impairing generalization performance. In this work, we focus on the more realistic and challenging setting of CTDGs, where interactions evolve continuously rather than at discrete time intervals. Existing causal inference methods are generally inapplicable to this setting because they predominantly rely on snapshot-based assumptions, which fail to capture the fine-grained temporal dynamics inherent in CTDGs.

3 ProblemFormulation

Definition 1 (CTDG) A Continuous Time Dynamic Graph (CTDG) G = (V, E, T ) consists of a set of vertices V, a set of edges E, and a continuous time domain T . The graph evolves over t ∈ T through edge additions, removals, or changing characteristics. We represent G as a sequence of time-stamped edges G = ⟨eij(tk)⟩, where eij(tk) denotes an interaction between node vi and vj at time tk with feature vector xeij (tk). Each node vi has a feature vector xni .

Given a CTDG G = (V, E), the task is to predict whether an interaction eij(t) will occur at a future time t, based on the historical sequence of nodes, edges, and their features. To evaluate OOD robustness, the model is trained on one environment and tested on CTDGs from other environments, where structural and temporal distributions may differ.

4 Independent and Confounded Causal Model

In this section, we introduce a novel structural causal model framework, termed Independent and Confounded Causal Model (ICCM).

In dynamic graphs, the existence of an edge can be influenced by both the structural topology (e.g., triadic closure) and temporal dynamics (e.g., temporal burst) [Cong et al., 2023]. These mechanisms may act independently or become entangled through latent confounders, and their influence can vary across environments. Existing causal formulations typically conflate structural and temporal effects, limiting their ability to disentangle spurious correlations under distribution shifts.

To explicitly capture both independent causal effects and environment-dependent confounding, ICCM models structural and temporal causal processes as distinct but potentially confounded components. We formalize ICCM by inspecting the causalities among nine variables: the structural causal subgraph Cs ⊆ G, the temporal causal subgraph Ct ⊆ G, the hidden representations HT and HS , the structural confounder Ds, the temporal confounder Dt, the edge existence probability in the in-distribution environment Y I , the edge existence probability in OOD environments Y O , and the final prediction result Y . Assumption 4.1 summarizes the core principles underlying ICCM:

Assumption 4.1 (ICCM)

In this assumption, Cs and Ct are causal structural and temporal subgraph. These subgraphs are encoded into latent representations HS and HT via fs(·) and ft(·). The indistribution prediction Y I is determined by the outcome function f I o (HS , HT ):

In OOD environments, however, structural and temporal confounders introduce spurious correlations that degrade model generalization. Specifically, structural confounders establish backdoor paths Cs ← C s b → Y and Cs ← Us → Y , where C s b = G \ Cs, and Us represent unobserved variables. These paths induce spurious correlations between Cs and Y C . Temporal confounders exert a similar influence. To mitigate these spurious correlations, we employ the do-operation introduced by Pearl [Pearl et al., 2016]. The do-operation allows us to block backdoor paths, thereby eliminating spurious correlations and isolating the invariant causal effect. Using the do-operation, the prediction Y C can be formulated as:

where Ds = {C s b , Us} and Dt = {C t b ,Ut}, respectively, f C o is output network network:

where W ∗ ∗ denotes the model parameters, f ∗ y (·) denotes linear network, σ denotes the activation function. However, we observe Equation 2 is computationally intractable. It necessitates enumerating all possible pairs of invariant causal subgraphs across the space of structural confounders Ds and temporal confounders Dt. In the context of large-scale CTDGs, this combinatorial explosion of potential subgraph configurations leads to prohibitive computational costs, making exhaustive intervention infeasible.

To address this issue, we propose an efficient intervention process by leveraging the NWGM approximation [Xu et al., 2015]. The NWGM provides a computationally efficient way to estimate the expectation of a softmax or sigmoid output by moving the expectation inside the non-linearity:

By applying the NWGM approximation, the interventional prediction in Equation 2 can be reformulated as:

Note that Ds and Dt denote abstract latent confounders, which may themselves correspond to complex subgraph patterns. While the confounder space can be large, Equation 5 does not require explicit enumeration of all possible confounders. Instead, it only requires expectation over a representative set of confounding modes, which can be approximated via confounder prototypes (Explained in Section 5.2.

5 Neural Instantiation of ICCM

In this section, we describe how the proposed ICCM is instantiated within a neural architecture by mapping latent causal variables to learnable components. The complete architecture is illustrated in Figure 2.

While the theoretical ICCM assumes access to causal subgraphs Cs and Ct, these variables are typically latent and unobserved in real-world scenarios. To address this, we employ causal subgraph extractors to infer structural and temporal subgraphs directly from the input data. The extractors identify invariant structural and temporal patterns and produce hidden representations HS and HT .

For the in-distribution perspective, these representations are passed to the outcome function f I o to predict the label yI . For the out-of-distribution (OOD) perspective, as described in Equation 5, the interventional prediction requires the expected representations of structural and temporal confounders: Eu∼DS [f u y (u)] and Ev∼DT [f v y (v)].

To estimate these expectations without exhaustive enumeration, we maintain structural and temporal memory banks that approximate the latent confounder distributions Ds and Dt. A multi-head attention-based fusion module then aggregates the memory entries to compute the expected environmental context, which approximates the expectation over latent confounder effects. Finally, the invariant representations HS and HT are integrated with the computed expectations from the memory banks and fed into the outcome function f C o to produce the OOD prediction yC . We term this framework Continuous Invariant Representation (CIR).

5.1 Extracting and Encoding Causal/Non-causal Subgraphs

Temporal extraction and encoding. Given a dynamic graph G and a target node pair (u, v) for prediction, our goal is to identify historical temporal interactions that causally contribute to the potential existence of an edge between u and v. Unlike heuristic time-window approaches, we aim to extract temporally relevant evidence that is both time-aware and pair-specific, aligning with the causal assumptions in ICCM. we first extract the temporal edges associated with nodes u and v denoted by SuG and SvG, respectively. Each edge eui(tk) ∈ SuG is encoded using a continuous-time representation following [Cong et al., 2023]: cos((t0 -tk)ω), where t0 is the prediction timestamp, ω = {α-(i-1)/β }di=1 defines a set of multi-scale temporal frequencies, with α and β representing hyperparameters. This encoding is combined with its corresponding edge features as [cos((t0 - tk) ω)∥xeui (tk)].

A 1-layer MLP-mixer [Tolstikhin et al., 2021] is employed to encode the edge features,

where stack(SuG) indicates the stacking of the edge features in sequence SuG. The MLP-Mixer enables global mixing across temporal edges, allowing the representation of higher-order temporal dependencies that are crucial for causal reasoning.

Intuitively, a historical interaction of v is considered temporally causal for predicting (u, v) only if it helps explain u's behavior, and vice versa. Therefore, we introduce a crossnode attention mechanism. The subgraph is generated by:

Here, d denotes a specific hyperparameter, and M e ∗ [k] represents the importance score assigned to the k-th edge within S∗. This attention mechanism filters temporal evidence based on mutual relevance, rather than local frequency or recency alone. Consequently, the highest top-k scores inM e v andM e u are selected to construct the temporal causal subgraphs Ct, while the remaining edges form the temporal non-causal subgraphs ˆBt. Finally, the temporal representations of the causal and non-causal graphs are encoded by:

The final representations are obtained by concatenation:

Causal temporal evidence is disentangled from confounding effects, supporting intervention-based learning.

Structural extraction and encoding. Our objective is to identify structural neighbors that causally support the interaction between u and v, while filtering out background nodes that may introduce spurious correlations. We first encode each node based on its n-hop neighborhood within a recent time window ]t0 - T, t0]: zu = xnu + Mean({xnv | v ∈ N n (u; t0 - T, t0)}). Here, N n (u; t0 - T, t0) denotes the nhop neighbors of node u with valid temporal edges, where T controls the structural temporal scope. The node mask matrices are computed through the equations:

Here, Zu and Zv is the stack of the encoded node features of all nodes in N n (u; t0 -T, t0) and N n (v; t0 -T, t0), respectively. The nodes with the highest top-k scores in M n u and M n v are chosen to form the structural causal subgraph, while the remaining edges form the temporal non-causal subgraphs ˆBs. The final structural representation HS is computed by:

where xnv represents the node feature of v, N n S (u) represents the n-hop neighbors of u in Cs. The final structural representation XS for the non-causal subgraph ˆBs is obtained using the same encoding method applied to Cs.

5.2 Memory Banks

The memory bank is designed to capture all confounders, including both non-causal subgraphs and unobserved factors. Since unobserved factors are not directly observable, we approximate them using the representations of observable noncausal subgraphs, based on the insight that unobserved influences are often implicitly reflected in the structure of these subgraphs.

As the dynamic graph evolves, the number of non-causal subgraphs can grow exponentially, making it infeasible to consider each instance individually. To address this, each entry in the memory bank approximates a cluster of noncausal subgraphs, capturing the shared influence of similar confounders. Specifically, the memory bank consists of K prototype vectors stored in the ˆD∗ ∈ RK×d , where K denotes the number of prototypes and d represents the feature dimensionality. Each element of ˆD∗ is initialized by sampling from a standard normal distribution, after which each prototype is normalized to ensure that they lie on a unit hypersphere. The memory bank is updated during training via gradient descent, guided by two self-supervised loss functions: the alignment loss and the diversity loss.

Given non-causal graphs XT and XS , the alignment loss is defined as:

Here, zT and zS are encoded features of XT and XS , respectively. The term z∗ ˆD⊤ ∗ [k∗] (with ∗ representing either T or S) measures the similarity between the encoded feature z∗ and the k∗-th prototype in ˆD∗. Each sample is assigned to the prototype with the highest similarity. When z∗ is well aligned with ˆD∗[k], the loss contribution for that sample is minimal.

To prevent redundancy among the prototypes, we impose a diversity loss:

Minimizing this loss encourages the prototypes to be as orthogonal as possible, ensuring that each captures a distinct cluster of non-causal subgraphs.

The overall regularization loss is the sum of the alignment and diversity losses:Lreg = Lalign + Ldiv. (14)

This loss is backpropagated during training to update both the encoder parameters and the memory bank, thereby refining the prototypes to more accurately represent distinct clusters of non-causal subgraphs.

5.3 Fusion

As shown in Equations 5, the fusion module combines the causal graph representations (HS and HT ) with the expected contributions of confounders, as approximated by the memory banks ( ˆDS and ˆDT ). This step implements the ICCMinspired interventional reasoning, where the model accounts for potential spurious effects from non-causal subgraphs and unobserved factors. We approximate the expected effect of confounders as:

The attention output is then fused with the original query using a residual connection, followed by dropout and layer normalization:

The fused features HS c and HT c are subsequently processed by a feedforward network and output the final prediction yC .

5.4 Optimization

We define the overall learning objective as:

where λi, λc, and λr are hyperparameters, E denotes the training dataset, which comprises pairs of positive and negative samples. Positive samples are derived from the original edge sets, while negative samples are generated by replacing the destination nodes with randomly sampled nodes from the vocabulary, ensuring a balanced ratio. The variable ye indicates the ground-truth label for edge e, with ye = 1 for positive samples and ye = 0 for negative samples.

The model underwent training for 300 epochs using the Adam optimizer with a learning rate set at 0.0001 and a weight decay of 1e-6. We set the batch size to 600, and the hidden layer dimension to 100. For the extraction of the causal subgraph, we specified the number of recent edges (N) as 50 and employed 1-hop neighbors. All MLP layers were configured to 2. Regarding the link prediction task, negative samples were set at a ratio of 1:5 in the training set and adjusted to 1:1 in both the validation and test sets.

Baselines. Given the limited research on invariant GNNs for CTDGs, we consider three categories of baselines: (1) CTDG GNN Models:TGN [Rossi et al., 2020], TGAT [Xu et al., 2020], and GraphMixer [Cong et al., 2023]. These models are specifically designed for CTDGs but lack the ability to produce explainable and invariant results. Therefore, our comparison primarily focuses on link prediction. (2) Robust DTDG models:DIDA [Zhang et al., 2022], EAGLE [Yuan et al., 2023], and Ada-DyGNN [Li et al., 2024a].

6.2 Link Prediction results (RQ1)

Table 1 reports the AUC results under varying shortcut ratios (0.2, 0.4, 0.6), while Table 2 presents the corresponding AP scores. Higher values indicate better performance. We summarize the key observations below: (1) CTDG models degrade sharply under stronger shortcuts. TGN suffers a substantial performance drop, with AUC decreasing by 31.4% on MOOC and by 23.8% on REDDIT. GraphMixer achieves competitive performance at 0.2 with CIR, but suffering drastic declines, particularly on MOOC (AUC decrease of 50.3%) and WIKI (AUC decrease of 33.3%). TGAT demonstrates relatively better stability but still degrades at higher shortcut ratios. (2) Robust DTDG models perform relatively well but do not generalize as effectively as CIR. Since DTDG models operate on discrete time steps, their effectiveness on CTDGs may be constrained, as they are not explicitly designed to handle fine-grained temporal dependencies. The relatively competitive performance of Ada-DyGNN and EAGLE sug-

6 Experiments

We conduct extensive experiments on four benchmark continuous-time dynamic-graph datasets to answer the following research questions:

• RQ1: How well does CIR mitigate distribution shift?
• RQ2: How efficient is CIR compared to existing baselines?
• RQ3: What is the contribution of each component?

All the experiments are conducted on a computer with Intel(R) Core(TM)2 Duo CPU @2.40 GHz processor, 128 GB RAM, and Tesla T4.

6.1 Experimental Settings

Datasets We conducted experiments on four real-world datasets: Wikipedia 1 , Reddit 2 MOOC 3 , UCI 4 . Following prior work [Zhang et al., 2022], we introduce structural perturbations to the graphs to simulate distributional shifts.

Evaluation Metrics. We partitioned the datasets based on the edge occurrence time: the initial 70% of edges were designated as the training set, the subsequent 15%were allocated to the validation set, and the remaining 15% formed the test set. We employ the average precision (AP) and area under the curve (AUC) as the evaluation metrics for link prediction. AP and AUC are two common metrics used to evaluate the performance of binary classification models. AP is a measure of the average precision across all possible recall thresholds. AUC is a measure of the area under the receiver operating characteristic (ROC) curve.

Training Protocols. An early-stopping mechanism was employed, terminating training when the Average Precision (AP) metric showed no improvement for five consecutive epochs.

1 http://snap.stanford.edu/jodie/wikipedia.csv

2 http://snap.stanford.edu/jodie/reddit.csv

3 http://snap.stanford.edu/jodie/mooc.csv

4 https://zenodo.org/records/7213796#.Y1cO6y8r30o

gests that their robustness mechanisms still provide advantages, but their full potential might be underestimated due to the CTDG evaluation setting. (3) CIR achieves the best AUC score across all datasets and shortcut ratios. Even at the highest shortcut ratio (0.6), CIR maintains strong performance, significantly outperforming other models, demonstrating superior generalization under distributional shifts. (4) CIR maintains low variance across datasets and shortcut ratios, indicating consistent performance. In contrast, CTDG models, particularly GraphMixer and TGN, exhibit higher variance at larger shortcut ratios, suggesting instability when shortcut dependencies are removed. TGAT shows moderate variance but still struggles with higher shift levels. Among DTDG models, Ada-DyGNN demonstrates lower variance than CTDG models, reflecting its robustness in link prediction, while EAGLE's variance remains moderate, indicating some inconsistency in handling shifts.

In conclusion, the results demonstrate that CIR achieves SOTA performance in link prediction across varying levels of distribution shift. Unlike existing CTDG and DTDG models, which either suffer from severe performance degradation or exhibit low AUC and AP scores, CIR consistently identifies stable causal structures and maintains high predictive performance with low variance. These results highlight CIR's strong generalization ability and robustness to spurious correlations in CTDGs.

6.3 Efficiency (RQ2)

Figure 3 reports the average inference time per edge for each method. CIR demonstrates high efficiency, with average running times per edge of 5.4 × 10-4 seconds on Reddit and 5.8 × 10-4 seconds on MOOC. In contrast, TGAT and TGN are slower due to their more complex encoding networks, while DIDA is also slower because it must construct a confounder dictionary for each snapshot. GraphMixer is slightly more efficient than CIR, primarily because it does not output an explainable subgraph. Despite some differences in absolute running times between the Reddit and MOOC datasets, the relative performance across models is consistent, indicating that these efficiency measurements are reproducible across diverse dynamic graph scenarios.

6.4 Ablation Study (RQ3)

Table 3 depicts the ablation study by reporting the AP and AUC across datasets with a fixed shortcut ratio of 0.4. The results reveal that each component contributes significantly to the overall performance. Removing either the structural encoder or the temporal encoder leads to substantial performance drops, particularly on the WIKI and UCI datasets.

Moreover, excluding the Y C causes a marked decline in performance. In contrast, the removal of the Y I has a more modest impact, with performance decreases ranging from about 2% to 8.9%. This suggests that while the ICM plays a supportive role in enhancing performance, the CCM is critical for capturing the essential patterns in the data. In summary, the full CIR model, which integrates all these components, consistently outperforms the ablated versions, highlighting the necessity of each module in achieving optimal performance across diverse datasets.

7 Conclusion

This paper addresses the challenge of developing invariant and self-interpretable GNNs for continuous-time dynamic graphs. By analyzing this problem from a causal effect perspective, we introduce the ICCM, a novel causal inference model meticulously designed to address both IID and OOD scenarios for CTDGs. Building upon the theoretical foundations of ICCM, we propose a novel deep learning architecture, which translates theoretically established causal models into a practical solution for dynamic graphs. Experiments show that CIR outperforms prior methods in link prediction, and robustness under OOD scenarios.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No.62472091, 62394333, 62572361)