Mitigating Dynamic Graph Distribution Shifts via Spectral Augmentation

1 Introduction

Dynamic graphs can represent complex relationships in the real world, where nodes correspond to entities and edges indicate their interactions. Dynamic graph neural networks (DyGNNs) have been proposed to tackle complex structural and temporal information over dynamic graphs, and have demonstrated significant advancements in various domains, including social networks [Zhu et al., 2024; Jiang et al., 2024], recommendation systems [Zhang and Gan, 2024; Abolghasemi et al., 2024], and transportation networks [Xia et al., 2024; Chen et al., 2024; Zhou et al., 2020].

∗Corresponding Author

Despite their great success, most DyGNNs are trained and evaluated under the assumption that dynamic graph data are independent and identically distributed. However, this assumption does not always hold because distribution shifts naturally emerge as graphs evolve. For instance, in social networks, user interaction patterns may change significantly in response to trending topics, making past data less representative of current behaviors. If a classifier relies heavily on such spurious patterns from the training set, it inevitably fails to generalize to unseen test sets under distributions.

Invariant learning [Arjovsky et al., 2019; Wu et al., 2022] addresses the out-of-distribution (OOD) problem by identifying correlations that remain stable across training and testing environments. A prominent strategy within this paradigm is to create multiple training environments via data augmentation to develop robust predictors. For example, prior works have investigated distribution shifts caused by modifications to graph structure [Zhu et al., 2021; Buffelli et al., 2022], node features [Liu et al., 2023; Wu et al., 2024b], or graph sizes [Liu et al., 2022b; Li et al., 2022], under the assumption that target data conform to a specific shift type. The effectiveness of these methods makes the augmentation strategy a critical component for model generalization. However, the real-world distribution shifts and graph dynamics are unknown, which could be any combination of multiple distribution shift components. Fixed combinations of uniform augmentations, fail to comprehensively cover the potential shift configurations in practical scenarios, resulting in undesirable generalization on new unseen nodes.

To validate this insight, Figure 1 presents a preliminary analysis comparing augmentation strategies. We employ the EERM [Wu et al., 2022] framework on the COLLAB dataset, which minimizes mean and variance risks across multiple augmentation branches. Specifically, we conduct a comparative analysis of two topology augmentation heuristics: 1) uniform augmentation, which perturbs edges uniformly at random; and 2) spectral augmentation, which flips edges within and across node clusters to induce principled changes in graph properties [Lin et al., 2023; Lin et al., 2022]. The results demonstrate that, under an equivalent perturbation budget, the spectral-based strategy consistently outperforms uniform augmentation across varying perturbation rates and numbers of branches. The performance gap between these two strategies motivates us to improve common uniform augmentations and explore effective graph augmentation strategies that better preserve graph invariance.

In this paper, we propose spectral augmentation as a surrogate for structural graph augmentation to enhance out-ofdistribution generalization. Specifically, we define the spectral distance between an original graph and its perturbed counterpart measured by their Laplacian eigenvalues. The key idea of our approach is to decompose the input graph into multiple shift components by maximizing the variance of spectral distance and learn predictors that focus on robust spectral components. However, calculating the spectral distance requires the eigendecomposition of the graph Laplacian, which results in a prohibitive time complexity of O(N 3 ) with N nodes in a graph. We introduce an approximate solution based on the Rayleigh quotient, reducing the computational complexity from O(N 3 ) to O(m2 ) with m non-isolated nodes in the graph. On top of this, we propose a novel objective that minimizes both the variance and the constructive risk across multiple spectral components. This objective encourages the classifier to focus on robust spectral components that remain stable under small edge perturbations (i.e., environment-insensitive) while reducing dependency on unstable components susceptible to perturbations (i.e., environment-sensitive). The main contributions of this work are summarized as follows:

• A Novel Framework: We propose a new approach to migrate dynamic graph distribution shifts by decomposing and mitigating complex distributional shifts on the spectral domain.
• A Novel View: We propose to extrapolate distribution shifts into a mixture of spectral components and encourage the model to encode crucial topological information that remains invariant under such shifts.
• Superior Performance: We conduct comprehensive experiments on both real-world and synthetic datasets to evaluate the performance of the proposed method. DSPA outperforms state-of-the-art methods on both link prediction and node classification tasks.

2 RelatedWorks

OOD Generalization on Graphs. Out-of-distribution generalization on graphs often relies on invariant learning, which assumes that invariant factors related to the label remain stable across environments, while variant patterns may still be predictive. As a widely adopted framework, IRM [Arjovsky et al., 2019] aims to learn a representation function that enables a shared classifier to perform optimally across multiple environments. Based on these principles, existing approaches for graph OOD generalization can be broadly categorized into two types: (i) Graph data augmentation [Liu et al., 2023; Liu et al., 2022a; Wu et al., 2024b], which perturbs the graph structure in a rule-based manner; and (ii) Disentangled representation learning [Yu et al., 2024; Zhang et al., 2022; Zhang et al., 2023], which attempts to separate feature representations into domain-invariant and domain-specific components. In this work, we focus on graph data augmentation to enhance the generalization capability of DyGNNs.

3 Preliminaries

Dynamic Graph. Let G be a dynamic graph defined over a global node set V with |V| = N, which captures the temporal evolution of node interactions and attributes. The dynamic graph is represented as a sequence of discrete-time snapshots G = {Gt}Tt=1 , where each snapshot is defined as a tuple Gt = (Vt, Et,Xt,At), comprising a node set Vt ⊆ V, an edge set Et, a node feature matrix Xt ∈ R|Vt|×dN , and an adjacency matrix At. Here, dN denotes the dimension of node features.

Graph Spectrum. For a given graph snapshot Gt = (Vt, Et), the normalized Laplacian matrix is defined as: Lnorm,t = I -D-1/2 t AtD-1/2 t , where I is the identity matrix, At is the adjacency matrix, and Dt is the diagonal degree matrix. Since this matrix is real and symmetric, it admits the eigendecomposition Lnorm,t =UtΛtU⊤t . In this decomposition, Λt = diag(λ1,t, . . . , λN,t) is the diagonal matrix of real eigenvalues; the set of these eigenvalues constitutes the graph spectrum. The corresponding matrix Ut = [u1,t, . . . , uN,t] is an orthogonal matrix whose columns are the orthonormal eigenvectors, also known as the spectral bases.

OOD Generalization on Dynamic Graphs. In the context of dynamic graphs, we use the random variables G1:t and Yt to indicate the sequence of ego-graphs up to time t and their true labels, while G1:t and yt refer to their specific empirical observations. We aim to learn a parameterized DyGNN mapping, fθ : G1:t → ˆ Yt, designed to generalize label predictions to unseen testing data.Aligning with standard practices in dynamic graph analysis [Gui et al., 2022; Yang et al., 2024], our research concentrates on node-level predictions. For any given node v associated with a temporal ego-graph Gv,1:t, the training loss for the sample (Gv,1:t, yt) is computed as ℓ(yt, fθ(Gv,1:t)). The core pursuit of OOD generalization is to ensure the model maintains stable performance across diverse testing environments, motivating the optimization objective below:

4 Methodology

The framework of the proposed DSPA is illustrated in Figure 2. We formulate the generalization problem as a twostage framework: (i) Surrogate estimation: Decomposing the graph into a mixture of spectral components that serve as surrogates for target shifts, explicitly designed to capture the heterogeneity of the graph structure; and (ii) Mitigation: Neutralizing individual shift components via invariant learning to prioritize robust spectral component. We next present the specific methodology designed to realize this framework.

4.1 Spectral Augmentation for Shift Extrapolation

This section introduces our dynamic graph spectral augmentation strategy, which focuses on perturbing edges that induce significant changes in structural properties. We first formulate the augmentation principle as a spectral perturbation. Subsequently, we derive an approximation method to alleviate the computational overhead associated with large graphs.

Probabilistic Edge Flipping Mechanism

Instead of relying on fixed heuristic rules, we draw inspiration from SPAN [Lin et al., 2023] and formulate topology augmentation as a learnable probabilistic process. We introduce a set of K learnable probability matrices, denoted as {Φ1, Φ2, . . . , ΦK}, where each Φk ∈ [0, 1]N×N governs the generation of the k-th augmented view.

For a specific view k, each entry (Φk)uv represents the probability of flipping the edge status between node u and v. To physically realize this augmentation, we first determine the permissible direction of modification using a structural direction matrix D ∈ {-1, 1}N×N :

where ¯A represents the adjacency of the complement graph (without self-loops). Consequently, Duv = 1 implies that the edge (u, v) does not exist and can be added, whereas Duv = -1 indicates an existing edge that can be removed.

To generate the augmented adjacency matrix ˜A(k) , we sample a binary perturbation mask B(k) from the Bernoulli distribution parameterized by Φk:

Here, ◦ denotes the Hadamard product. If B(k) uv = 1, the operation defined in Duv is applied (adding or removing the edge); otherwise, the connection remains unchanged. The expectation of this stochastic augmentation is given by E[ ˜A(k) ] = A + D ◦ Φk, making the topology shift differentiable with respect to the probability parameters.

Optimizing for Spectral Diversity

To ensure the augmented views cover a wide range of spectral shifts, we optimize the probability matrices {Φk}Kk=1 to maximize the diversity of their resulting spectral properties. Specifically, we focus on the graph spectral distance variance.

Let Dspec(Φk) be the spectral distance of the expected augmented graph for the k-th view:

The optimization objective is then formulated to maximize the variance of these distances across all K views:

where Ω constrains the perturbation budget. By maximizing this variance, the model is incentivized to generate views that exhibit distinct spectral characteristics.

Scalability

Directly optimizing the spectral distance in Eqn.4 requires performing eigendecomposition of O(N 3 ), which is computationally prohibitive for large graphs. To mitigate this, we employ a first-order spectral approximation based on matrix perturbation theory.

Proposition 1 (Spectral Approximation via Rayleigh Quotient). Let L be the Laplacian of the original graph and {(λj, uj)} be its eigenpairs. Consider the perturbed Laplacian for the k-th view as ˜L(k) = L + ∆L(Φk), where ∆L(Φk) represents the Laplacian change induced by the probabilistic edge perturbation D ◦ Φk.

Assuming the perturbation magnitude is bounded, the perturbed eigenvalues ˜λ(k) j can be approximated using the Rayleigh Quotient of ˜L(k) evaluated on the original eigenvectors uj. Since the original eigenvectors are normalized, this simplifies to:

Proof. The Rayleigh Quotient R(M, x) = x⊤Mx x⊤x is stationary at the eigenvectors of M. Specifically, the gradient ∇xR(M, x) vanishes when x is an eigenvector. According to matrix perturbation theory, the perturbed eigenvector ˜uj can be expressed as ˜uj = uj +O(∥∆L∥). Substituting uj into the Rayleigh Quotient of the perturbed matrix, we obtain:

Proposition 1 essentially states that utilizing the fixed basis uj provides a robust first-order estimation of the spectral shift. Accordingly, we pre-compute the eigenvectors U = [u1, . . . , uN] of the original Laplacian L once. During the optimization of the probability matrices Φk, we treat U as a fixed basis and backpropagate gradients solely through the perturbation term ∆L(Φk). This approximation avoids computationally expensive repetitive eigendecompositions.

Furthermore, in the context of dynamic graphs, isolated nodes in each snapshot are excluded from the spectral analysis, as they do not convey structural shift information. Restricting the analysis to the subgraph of m active nodes reduces the per-iteration complexity from O(N 3 ) to O(m2 ), resulting in an overall training complexity of O(T ·L·K·m2 ), where T, L, and K denote the number of time steps, optimization iterations, and augmented views, respectively.

4.2 Mitigating Shift Components by Invariant Learning

Having estimated the spectral surrogates via learnable probabilistic flipping, we propose an invariant spectral filtering to capture stable patterns in the spectral domain. We treat the original graph as a reference anchor and apply contrastive learning to align each augmented view with the original graph, thereby eliminating the effects of the induced spectral shift components.

The DSPA Workflow

We process the original graph and its augmentations through a shared encoder to capture both invariant and variant features. Formally, let Gt denote the ego-graph instance at snapshot t with adjacency matrix At. The encoder is denoted as h : Gt → Rd , which projects graph snapshots into a latent embedding space. h assumes two conceptual roles: the Reference Encoder serves as an in-distribution module that processes the original graph to extract the invariant component, whereas the Shift Encoder processes augmented graphs to generate variant components as illustrated in Figure 2. We refer to the scenario where h produces referentially invariant representations w.r.t. spectral surrogates while allowing heterogeneity across different spectral instances. The objective function ensures that h generalizes under multiple shifts.

Invariant Component (ZI): The encoder processes the original (in-distribution) graph Gt, serving as a reference to produce a stable and distribution-invariant representation:

Variant Components ({ZV,k}Kk=1 ): To capture potential distributional shifts, the encoder processes the K augmented views. Let G (k) t be the graph instance associated with the augmented adjacency ˜A(k) t (from Eqn. 3). The variant representations are obtained as:

These generated representations are then propagated to a classifier µ. Consequently, the overall model is defined as f = µ ◦ h, with the prediction function articulated as:

Unlike most DyGNNs that process all temporal snapshots simultaneously-which is both memory-consuming for large dynamic graphs and infeasible for true inductive learning. Instead, our approach processes snapshots sequentially. We leverage snapshot from the current timestep t to predict edges at the subsequent timestep t + 1. This strategy is suited for inductive learning and aligns with the evolutionary nature of dynamic graphs. We use GCN as the encoder h and train the model using stochastic gradient descent.

Training Objective

To learn representations that are robust to distributional shifts, we propose an objective that trains the model on both the original graph and its spectrally diverse augmentations.

• Task Loss (L1). The task loss guides the model to utilize invariant representations ZI for downstream prediction. It is defined as:

where µ is the prediction head, and ℓ is the task loss function.

• Invariance Loss (L2). To encourage consistency across spectrally shifted views, we minimize the variance of the task losses computed from the K augmented components. The invariance loss is defined as:

where ℓk denotes the prediction logit corresponding to the kth augmented view, and ¯ ℓ = 1K ∑Kk=1 ℓk represents the mean logit across all augmented views.

• Contrastive Loss (L3). Note that the augmentation strategy specifically targets edge perturbations that cause substantial

variations in the graph's structural characteristics. Drawing inspiration from the InfoMin principle [Zhao et al., 2021; Lin et al., 2023; Meng and Liu, 2023], we propose a contrastive learning objective that maximizes the correspondence between ZI and ZV,k. This encourages the model to focus on sensitive edges, while edges that introduce structural instability are treated as noise and disregarded by the encoder. This ensures that the model's representations remain consistent across different augmented views.

Specifically, let Di denote the denominator in the contrastive loss for sample i, computed as:

Then, the contrastive loss L3 is formulated as:

where s(·, ·) denotes the similarity function between two latent vectors, and τ is the temperature hyperparameter.

· Total Loss. Following recent advances in adversarial training on graphs [Wu et al., 2022; Feng et al., 2019], we optimize the network's parameters independently. We maximize the spectral diversity of perturbations via Φ while simultaneously minimizing the overall objective with respect to the model parameters θ:

where α is a hyperparameter balancing the contributions, and Laug is the spectral distance variance defined in Eqn. (5).

5 Experiments

5.1 Experimental Setup

Datasets. We conduct experiments on four node property prediction datasets: COLLAB [Tang et al., 2012], Yelp [Sankar et al., 2020], ACT [Kumar et al., 2019], and Aminer [Zhang et al., 2023]. Following [Yuan et al., 2023; Zhang et al., 2023], we construct distinct in-distribution (ID) and outof-distribution (OOD) partitions for each dataset. For COLLAB, Yelp, and ACT, we adopt the challenging inductive future link prediction task, where the model is evaluated on a dynamic graph containing nodes that are unseen during training. For Aminer, we perform a node classification task on a citation network; here, nodes represent papers, and a timestamped edge from u to v indicates that paper u (published at time t) cites paper v.

Baselines. We compare DSPA with ERM and twelve baseline methods in four categories: (1) Invariant Learning methods: EERM [Wu et al., 2022], IRM [Arjovsky et al., 2019], CaNet [Wu et al., 2024a]. (2) Dynamic Graph Learning methods: VGAE [Chen et al., 2024], EGCN [Pareja et al., 2020], DySAT [Sankar et al., 2020]. (3) Dynamic Graph OOD methods: DIDA [Zhang et al., 2022], I-DIDA [Zhang et al., 2024], EAGLE [Yuan et al., 2023], DyCIL [Zhang et al., 2026]. (4) Spectral Learning methods: SPAN [Lin et al., 2023], SILD [Zhang et al., 2023].

Training Settings. All experiments are repeated five times with different random seeds. Validation set performance determines both model checkpoint selection and early stopping. While we present results for ID and OOD test sets, we focus primarily on OOD metrics to assess generalization. Models are optimized via Adam with weight decay for up to 200 epochs, and we report the test performance corresponding to the optimal validation epoch.

5.2 Distribution Shift on Real World Datasets

Settings. We use 3 real-world dynamic graph datasets: YELP, ACT, and Aminer. Following the setup in [Zhang et al., 2023], we adopt the challenging inductive link prediction task on the COLLAB, YELP, and ACT datasets, where testing is performed on dynamic graphs from domains that are unseen during training. For the node classification task, we train on the Aminer dataset using a temporal split, where papers published between 2009 and 2014 are used for training, and those published after 2015 are used for testing.

Results. The results are presented in Table 1. Here, ID and OOD indicate whether distribution shifts are present in the test set. We have the following observations: (i) Although the baselines perform well on the training data, their effectiveness declines significantly during testing. These empirical results support our hypothesis that DyGNNs tend to overfit spurious correlations or non-causal features, leading to suboptimal generalization. (ii) When integrated into our framework, invariant methods such as EERM and IRM exhibit improvements over state-of-the-art baselines. This demonstrates that our training paradigm is more effective for handling distribution shifts in inductive settings. (iii) DSPA consistently outperforms the baselines under distribution shifts. We attribute this improvement to the training objective, which encourages invariance to distributional changes by leveraging diverse augmented views.

5.3 Distribution Shift on Synthetic Datasets

Settings. We follow [Zhang et al., 2022] to generate additional node features that simulate distribution shifts. Specifically, we sample a mix of positive and negative links from the next time step's edges, At+1. A time-dependent sampling probability p(t) is used to select p(t)|At+1| positive links and (1 - p(t))|At+1| negative links, where p(t) = ¯ p + σ cos(t). The original node features and the synthesized features are concatenated as [Xt∥X′t ] and fed into the model. A larger p(t) introduces stronger spurious correlations between the perturbed features X′ t and future environments. To achieve better generalization, the model should avoid relying on variant patterns that exploit spurious correlations introduced by the additional features. In our experiments, we manipulate the level of spurious correlation by varying ¯ p during training. Specifically, we set ¯ p to 0.4, 0.6, and 0.8 during training, and fix it to 0.1 during the testing stage.

Results. The results are shown in Table 2. We have the following observations: (i) Our method better handles distribution shifts than the baselines, especially when the shifts are strong. In the link prediction task, DSPA surpasses DyCIL by an average of 1.17%. (ii) Our method exploits invariant patterns across different levels of distribution shift. As the shift intensity increases, almost all baselines exhibit a significant performance drop. In contrast, the performance of DSPA degrades slightly. This demonstrates that DSPA learns robust structures and alleviates reliance on variant patterns, enabling the encoder to maintain stable outputs across varying shifts.

5.4 Ablation Study

We validate the effectiveness of various components in DSPA by individually removing these modules. The ablated version 'w/o Const' removes contrastive loss L3, and 'w/o Aug' is trained without the spectral augmentation only on the origin input graph. From Figure 3, we have the following observations. First, our proposed method consistently outperforms all its variants. This demonstrates the effectiveness of each component within our methodology. Second, the performance of both 'w/o Const' and 'w/o Aug' degrades significantly. This decline indicates that our spectral augmentation scheme and contrastive loss help the model focusing on invariant patterns under distribution shifts.

5.5 Hyperparameter Sensitivity Analysis

Impact of Parameter α. Figure 4(a) illustrates the performance of DSPA under different values of the hyperparameter α. As the weight of the contrastive loss L3 increases, the AUC improves across all datasets. This trend suggests that enhancing the alignment between invariant and perturbed representations by contrastive learning strengthens the model's robustness to structural perturbations, particularly in graphs with high sensitivity to edge modifications.

Impact of Parameter K. The hyperparameter K controls the number of augmentation branches. As shown in Figure 4(b), the model's OOD performance is generally insensitive to the choice of K on the YELP and ACT datasets, while exhibiting a moderate dependency on K for COLLAB. This discrepancy can be attributed to the more pronounced distribution shifts in COLLAB, which make generalization inherently more challenging. Moreover, the proposed spectral augmentation strategy consistently outperforms uniformly random edge perturbation, as the latter ignores the unequal influence of different edges on graph structural properties.

Table 3: Empirical running time (s) on four datasets.

Impact of perturbation ratio. As shown in Figure 4(c), increasing the perturbation ratio slightly degrades performance on YELP and ACT, while generally improving performance on COLLAB. This difference is likely due to variations in graph density and structural redundancy across datasets. In particular, COLLAB is a dense network with abundant redundant structures, where a higher perturbation ratio helps generate more informative augmented views.

5.6 Spectral Approximation Analysis

To empirically validate the approximation bound in Proposition 1, we compare the Rayleigh quotient approximation (Approx) with exact eigendecomposition (Full) under different perturbation ratios on the COLLAB dataset. As shown in Table 4, the Spectral Approximation Error (SAE) increases monotonically with the ratio, empirically confirming that the error is dominated by higher-order terms O(∥∆L∥2 ). Despite this, the performance of Approx remains robust and consistently outperforms Full. This suggests that the first-order approximation acts as a spectral regularizer, effectively filtering out high-frequency structural noise captured by the exact decomposition while retaining semantically relevant shifts.

5.7 Visualization of Spectral Augmentation

To illustrate structural changes induced by spectral augmentation, we visualize a random geometric graph. Figure 5(a) shows the original topology, Figure 5(b) the graph maximizing Dspec, and Figure 5(c) the graph minimizing Dspec. Maximizing the spectral norm tends to remove inter-cluster edges, while minimizing it promotes cross-cluster connections. This augmentation mainly targets spurious edges affecting structural properties. Similar observations were reported in previous works [Lin et al., 2023; Lin et al., 2022]: smaller eigenvalues capture smooth intra-cluster similarities, whereas larger eigenvalues reflect sharp inter-cluster differences.

6 Conclusion

In this paper, we propose DSPA, a novel framework to migrate complex distribution shifts on dynamic graphs in the spectral domain. DSPA distinguishes itself from traditional invariant learning methods, which primarily rely on augmenting the training data to cover the test distribution shifts. Instead, our approach guides the encoder to identify sensitive edges, whose perturbations cause significant spectral variations. This encourages the model to focus on robust spectral components for improved generalization. Experimental results demonstrate that DSPA consistently outperforms baseline methods on both real-world and synthetic datasets.

Acknowledgements

This research is supported by the National Natural Science Foundation of China (Grant No. 62472263, 62072288), Humanities and Social Science Research Project of the Ministry of Education, China (Grant No. 24YJAZH058), the Natural Science Foundation of Shandong Province, China (Grant No. ZR2024MF034), the CAHE 2024 Higher Education Scientific Research Planning Project (Grant No. 24XX0101).