Rationalizing and Augmenting Dynamic Graph Neural Networks
Authors: Guibin Zhang
Yiyan Qi
Ziyang Cheng
Yanwei Yue
Dawei Cheng
Jian Guo
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Data Augmentation
Dynamic Graph Neural Networks
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph data augmentation (GDA) has shown significant promise in enhancing the performance, generalization, and robustness of graph neural networks (GNNs). However, contemporary methodologies are often limited to static graphs, whose applicability on dynamic graphs—more prevalent in real-world applications—remains unexamined. In this paper, we empirically highlight the challenges faced by static GDA methods when applied to dynamic graphs, particularly their inability to maintain temporal consistency. In light of this limitation, we propose a dedicated augmentation framework for dynamic graphs, termed $\texttt{DyAug}$, which adaptively augments the evolving graph structure with temporal consistency awareness. Specifically, we introduce the paradigm of graph rationalization for dynamic GNNs, progressively distinguishing between causal subgraphs (\textit{rationale}) and the non-causal complement (\textit{environment}) across snapshots. We develop three types of environment replacement, including, spatial, temporal, and spatial-temporal, to facilitate data augmentation in the latent representation space, thereby improving the performance, generalization, and robustness of dynamic GNNs. Extensive experiments on six benchmarks and three GNN backbones demonstrate that $\texttt{DyAug}$ can \textbf{(I)} improve the performance of dynamic GNNs by $0.89\\%\sim3.13\\%\uparrow$; \textbf{(II)} effectively counter targeted and non-targeted adversarial attacks with $6.2\\%\sim12.2\\%\\uparrow$ performance boost; \textbf{(III)} make stable predictions under temporal distribution shifts.

Published as a conference paper at ICLR 2025
RATIONALIZING AND AUGMENTING DYNAMIC GRAPH NEURAL NETWORKS
Guibin Zhang 2., Yiyan 0 Ziyang Cheng', Yanwei Yue', Dawei Cheng 104 Jian Guo 204]
'Tongii University IInternational Digital Economy Academy (IDEA) Corresponding:
dcheng@tong www.nnngii.....ooooooooooo en, guojiant idna. enu.en
ABSTRACT
Graph data augmentation (GDA) has shown significant promise in enhane- ing the performance, generalization, and robustness of graph neural networks (GNNs). However, contemporary methodologies are often limited to static graphs, whose applicability dynamic graphs-mort prevalent in real-world applica- tions remains unexamined. In this paper. we empirically highlight the chal- lenges faced by static GDA methods when applied to dynamic graphs, particu- larly their inability to maintain temporal consistency. In light of this limitation, we propose dedicated augmentation framework for dynamic graphs, termed DyAug, which adaptively augments the evolving graph structure with temporal consistency awareness. Specifically, we introduce the paradigm of graph ratio- nalization for dynamic GNNs, progressively distinguishing between causal sub- graphs (rationale) and the non-causal complement (environment) across snap- shots. We develop three types of environment replacement, including, spatial, temporal, and spatial-temporal, to facilitate data augmentation in the latent repre- sentation space, thereby improving the performance, generalization, and robust- ness of dynamic GNNs. Extensive experiments on six benchmarks and three GNN backbones demonstrate that DyAug can (I) improve the performance of dynamic GNNs by 0.89% ~ 3.13% 1: (II) effectively counter targeted and non-targeted adversarial attacks with 6.2% 12.2% 1 performance boost; (III) make sta- ble predictions under temporal distribution shifts. The source code is available at https: / /tt///gtttuttt cow wwm./binggreeeyy///yg..
INTRODUCTION
Data-driven inference has greatly enhanced generalization capabilities and improved model perfor- mance, particularly through data augmentation, across wide range of domains, including computer vision (CV) (Yang et al., 2022; Alomar et al., 2023; Zheng et al., 2023), natural language process- ing (NLP) (Shorten et al., 2021; Dai et al., 2023), and graph-based tasks (Rong al., 2019; Feng et al., 2020; Fang et al., 2022; Wang et al., 2021b; Liu et al., 2022c; Sui et al., 2024). Among these domains, graph-tailored augmentation strategies are notably distinct due the irregular and non- Euclidean nature of graph data, unlike the other two domains, where data is typically structured in regular, Euclidean forms such as grids (i.e., images) and sequences (i.e., sentences). Drawing upon these unique characteristics, current graph data augmentation (GDA) techniques have demonstrated significant effectiveness in enhancing the performance (Zhao et al., 2022c; Wang et al., 2024; Li et al., 2023d), robustness (Jin et al., 2020; Kong et al., 2022; Zhang et al., 2024c;b), and general- ization ability (Wu et al., 2022b; Liu et al., 2022a) on graph neural networks (GNNs), applicable to various levels of graph tasks, including node-level (Rong et al., 2019; Wang et al., bb; Zhang et al., 2024d; Li et al., 2025), edge-level (Dai et al., 2019; Zhao et al., 2022b), and graph-level (Feng et al., 2020; You et al., 2021; Liu et al., 2022a).
Despite their success, previous graph data augmentation methods have been largely constrained to a specific class of graphs, namely static graphs. In contrast, dynamic graphs, which evolve over time, and are widely recognized as more prevalent in real-world applications such as so- cial networks (Berger-Wo Wolf & Saia, 2006; Greene et al., 2010; Li et al., 2023c), financial trans- actions (Nascimento et al., 2021; Zhang et al., 2021), and traffic networks (Peng et al., 2021; 2020),
Equal contributions.

---

Published as a conference paper at ICLR 2025
Lo
0.8
Vanill
Deroddas
DyAAg
1U50 CULLAS (a) Performance
0.0
Vanilla
DropEEgge
+NeuniSpuree
(b) Duration CDF
(c) Duration distribution
Figure 1: (Left) (a) illustrates the AUC (%) comparison among vanilla DySAT, DropEdge (Rong et al., 2019), GraphMixup (Wang et al., 2021b). RGDA (Liu et al., 2024a) and DyAug on the Yelp dataset; (Middle) (b) analyzed the time span of each edge, i.e. its longest consecutive existence period across snapshots, and compared the cumulative distribution function (CDF) for the vanilla dataset and after applying NpuralSparse and DropEdge; (Right) (c) visualizes the distribution of edge time spans under different methods, with colors ranging from light dark representing [1, 2, 3, 4, 5, others].
notably lack effective and tailored data augmentation designs. In light of this dilemma, an intuitive approach would be to directly apply static graph augmentation techniques to dynamic graphs. But is this truly feasible? In the remainder of this section, we will (I) first review key advancements in GDA, (2) highlight the critical challenges in their extension to dynamic graphs, (3) present our proposal for dynamic graph augmentation, and (4) summarize the contributions of this paper.
Look-back on GDA. Existing graph augmentation techniques can be broadly categorized into the following two types: 1 rule-based augmenters, which manipulate data through predefined strategies such as edge dropping (Rong et al., 2019), node dropping (Feng et al., 2020), message dropping (Fang et al., 2022), and mixup (Wang et al., 2021b; Han et al., 2022; Ling et al., 2023; Kim et al., 2023; Ma et al., 2024); and @ learning-based augmenters, which incorporate learnable parameters in the generation of augmented examples, including graph structure learning (Jin et al., 2020; Wu et al., 2022a; Zou et al., 2023; Huang et al., 2023; Wan et al., 2024b), graph rationaliza- tion (Liu et al., 2022a; Wu al., 2022b; Yue et al., 2024a), adversarial training (Zhu et al., 2019; Li et al., 2023a), and contrastive learning (You et al., 2020; 2021; Shen et al., 2023). Although these methods have made significant strides empowering generalizing. and robustifying GNNs on static graphs (Zhao et al., 2022a; Ding et al., 2022: Adjeisah et al., 2023), their performance on dynamic graphs along with the potential challenges, remains largely unexplored and unassessed.
Emperical Observation. To investigate the potential issues of transferring static GDA methods to dynamic settings, we select three representative methods from both rule- and learning-based aug- menters and apply them on Yelp (Sankar et al., 2020) with DySAT (Sankar et al., 2020) as the GNN backbone As shown in Figure 1 (Left), not all methods contribute positively: though effec- tive on static graphs, DropEdge (Rong et al., 2019) and GraphMixup (Wang et al., 2021b), lead to a performance drop of 0.2% 0.6%. Nevertheless, RGDA (Liu et al., 2024a) achieves a modest im- provement (0.6% in AUC). This raises the question: what caused such a discrepancy? To explore this further, we examine how graph augmentation affects dynamic graph sequences. We investigate the edge timespan (Yang et al., 2023), namely the maximum number of consecutive graph snapshots an edge spans. As illustrated in Figure (Middle), DropEdge significantly alters the cumulative distribution function (CDF) of edge timespans, while RGDA has comparatively minor effect.
Challenges. Based on the above observations, we conclude that static GDA methods not fully applicable to dynamic graphs, due to their unawareness of temporal consistency. More concretely, existing methods primarily focus on augmenting individual graphs, while overlooking the strong temporal dependencies across different graph snapshots. Imagine a scenario where existing GDA techniques are applied independently to each graph snapshot. Since topological augmentations often involve removing/deleting edges (Zhao et al., 2022a; Ding et al., 2022), this can lead to surge in edges with a timespan of only 1, while many tingttimsspan edges may suddenly disappear at one timestamp and reappear at the next-such behavior does not align with the natural evolution patterns observed in real-world dynamic graphs (Beck et al., 2017). This issue is clearly illustrated in Figure (Right): DropEdge disrupted many originally long-spanned edges, causing the proportion of edges with a timespan of 1 to increase sharply from 43.57% to 69.25%. We call this the disruption of the temporal consistency (Qian et al., 2021) between different graph frames, which significantly undermines the continuity and temporal dependencies inherent in dynamic graphs. Therefore, a
We place detailed explanations of their adaption dynamic graphs in Appendix A.I.
2

---

Published as a conference paper at ICLR 2025
natural question arises: how can we design a data augmentation method for dynamic graphs that effectively enhances dynamic GNNs via well-maintaining temporal consistency?
Proposal. To address the aforementioned challenges, we propose remporal-consisten dynamic graph augmentation framework (dubbed DyAug), which can efficiently integrate into mainstream dynamic GNN backbones, and adaptively manipulates and augments evolving graph structures with temporal consistency awareness. Technically, DyAug pioneers the exploration of graph rational- ization (Liu al., 2022a; Si et al., 2023; Yue al., 2024a) in dynamic graphs by dynamically pinpointing the rational features (rationales) that support a model's predictions during the training phase, while the contrasting elements are referred to the environment. Through temporally condi- tioned graph sequence for the dynamic graphs, effectively preserving the temporal consistency. By employing three types of augmentation techniques, i.e. temporal, spatial, and spatial-tempot environment replacement, DyAug efficiently expands the data distribution for dynamic GNNs, achieving a triple win in terms of performance, robustness, and generalization capacity.
environmenni separation. DyAug learns a highly correlated rationale subgraph
Our contributions are summarized as follows:
Problem Identification. We pioneer the exploration of graph data augmentation (GDA) within dynamic graphs. Through empirical evaluation, we demonstrate the poor transferability of tra- ditional static GDA methods to dynamic graphs, identifying the root cause as the disruption of temporal consistency inherent to dynamic graph structures.
Pratical Solution. We propose a semporal-consistenn dynamic graph augmentation framework, termed DyAug, which makes the first step to explore graph rationalization within dynamic GNNs. By extracting rationale subgraphs in a temporally conditioned manner, DyAug effectively preserves the temporal consistency of dynamic graph sequences while efficiently augmenting training data through temporal, spatial, and spatial-temporal environment replacement.
Experimental Validation. Extensive experiments on six benchmarks and four dynamic GNN backbones demonstrate that DyAug can (I) improve the performance of dynamic GNNs by 0.89% 3.13% 1, surpassing state-of-the-ar GDA methods by up to 2.8%; (II) effectively counter targeted and non-targeted adversarial attacks with 6.20% ~ 12.22% 1 performance boost; (III) make stable predictions under temporal distribution shifts.
RELATED WORK
Dynamic Graph Neural Networks. Dynamic Graphs find applications in a wide variety of dis- ciplines, including social networks (Berger-Wolf & Saia, 2006; Greene al., 2010), recommender systems (Li et al., 2020; Zhang et al., 2022a; Gong et al., 2024), epidemiology (Wan et al., 2024a; Tan et al., 2024; Liu al., 2024c), etc. According to data types, current dynamic graphs can be pri- marily classified into discrete-time dynamic graphs (DTDG) and continuous- dynamic graphs (CTDG) (Barros al., 2021: Feng et 2024). This paper's main research scope focuses on DTDG, which consists of multiple discrete graph snapshots arranged in chronological order. Contemporary dynamic GNNs (DyGNNs) typically follow a framework where spatial module processes different snapshots, and temporal module aggregates information from various timestamps. Common cate- gories include: (1) Typical GNN-RNN DyGNNs, which utilize a GNN module to handle individ- ual snapshots and employ recurrent neural network (RNN) style modules to aggregate information across time, including STGCN (Yu et al., 2017), DySAT (Sankar et al., 2020), EvolveGCN (Pareja et al., 2020). TeMP (Wu et al., 2020), TFE-GNN (Zhang et al., 2023a), and SEIGN (Qin et al., 2023); (2) Temporallenhaneed DyGNNs where specific design are adopted to better capture temporal de- pendencies, such as generative adversarial networks (GAN) in SGNN-GR (Wang al., 2022) and spiking neural networks (SNN) in SpikeNet (Li et al., 2023b); (3) Spatial-enhanced DyGNNs, improving spatial modeling, such as GCRN (Sco al., 2018) and TTGCN (Li al., 2024a).
Graph Data Augmentation As discussed in Section existing graph data augmentation (GDA) techniques can be broadly categorized into two types. (1) Rule-based augmentors employ heuristic rules for enhancing graph data across various dimensions, including topological-level (Rong et al., 2019; You et al., 2020; Wang et al., 2020; Sun et al., 2021; Yue et al., 2024b), feature-level (Zhao et al., 2021a; Sun et al., 2021), 1), and label-level (Park et al., 2021; 1; Han et al., 2022). (2) Learning- based augmenters employ various automated learning paradigms to expand graph data. For in- stance, graph structure learning (Zhu et al., 2021; Li et al., 2024b; Zhiyao et al., 2024) has been leveraged for enhancing graph topology by adding or removing edges (Jin et al., 2020; Liu al.,
3

---

Published as a conference paper at ICLR 2025
cimppora-conditionned rationale generation
Consistency Regularization: (o 93 ,
gf A @ M
of [x2, A2 M))
G (XT, APt M
t=
1=1
Progressive sparsifiaaiin
Dynamic Graph
Gur (g
(M A1, Ag, M
Ps P& Ar, Ar M
Optimization
Rationale subgraph (X1r, Air + BMP) 1:T)
DyGNN: (a A1a)
Environment subgraph
Cieat Ld Ler
9
(X177 A ① M,T
DTDG
DyGNN
Geseraliaaata
Environmentt-oae based
forward
Subgraph Augmentation
RTANDD
H TRNND
Spatial Aug: Comb th
tm
envirocment embeedinng
tmp
Temporal Comb (h
Spa-temp Aug: (b.
emboddiings
Ui US
Figure 2: The overview of our proposed DyAug.
2022b; Zhao et al., 2023; Wu et al., 2023). Techniques such as contrastive learning (Velickovic al., 2019; You et al., 2020; 2021; Zhang et al., 2023b; 2024e) and reinforcement learning (Zhao et al., 2022c; Zhou & Gong, 2023) are also commonly used for graph augmentation. In contrast the aforementioned methods, graph rationalization focuses on identifying intrinsically learned subgraphs as the rationale graph (Zhao et al., 2022a), with the opposing context referred to as the environment, which augments data by perturbing the rationale-environmerr pair. Due its robust- ness to data noise (Sun et al., 2022; Yuan et al., 2024) and distribution shifts (Wu et al., 2022b; Liu et al.. 2024a), graph rationalization has garnered increasing attention, and our proposed method falls within this category. However, all these GDA methods are confined to static graphs and do not take into account the temporal correlations present in dynamic graph sequences, which significantly limits their performance when extended to dynamic graphs. Regarding GDA for dynamic graphs, although there are few attempts for CTDG (Wang et al., 202 la; Chen et al., 2023), to the best of knowledge, there currently GDA methods specifically designed for DTDG.
3 METHODOLOGGY
3.1 NOTATIONS AND PRELIMINARY
Notations Consider a graph 9 with the node set V and the edge set E. (discrete-time) dynamic graph can be defined G1.T (G1, G2, Gr), where T is the number of time stamps, G. (Ve: & is the graph slice time stamp E [1, V = U V,, E = - & Alternatively, 91-r can be represented as (XI.T, Air], }, where each snapshot G. = {X,, At) consists of node attributes X, N and adjacency matrices A, E {0, 1) NNN with N [V] denoting the number of nodes and D denoting the dimensionality of the node attributes.
DyGNN Paradigm We take the classical link prediction in dynamic graph modeling as an ex- ample. The objective is to train a dynamic GNN fe (X1:r, A ب {0. 1) NXN which leverages information from the past snapshots to predict edge existence at time step T + Fur- thermore, can express fe fe fa ft fa. where f. (X1.7, A1T7) H.. parameter- ized by +., is tasked with capturing spatial patterns to derive representations for timestamps T, fi H. + H4. parameterized by θ,, captures temporal dependencies and retrieves representations for the T + time step, and fa H, ++ y, parameterized by θ,, denotes the downstream task function, which predicts the connectivity AT- 1 time step T + in the context of link prediction.

---

Published as a conference paper at ICLR 2025
3.2 FRAMEWORK OVERVIEW
In this study, present the first efficient data augmentation framework tailored for dynamic graphs, termed DyAug, as depicted in Figure 2. Given dynamic graph sequence Gı.r, DyAug progressively performs national--nvvioomment separation for each snapshot, constrained by consistency regulariza- tion to preserve temporal consistency across snapshots. The underlying DyGNN backbone is then employed to generate both rationale and environment representations. Subsequently, three types of augmentations, including spatial, temporal, and spatial-temporal, are applied to prevent fe from learning spurious correlations from environment representations, thus enhancing the performance, robustness, and generalizability of DyGNNs. In the following sections, we will first give causal analysis in Section 3.3, introduce how DyAug performs temporal-conditioned rationale-enviromment separation in Section 3.4, present the data augmentation strategies in Section 3.5, and showcase the overall optimization objective and complexity analysis in Section 3.6.
3.3 A CAUSAL VIEW ON DYGNNS
To clarify the goal and implementation of graph rationaliza- tion in dynamic graphs, we first take a step back to ana- lyze the DyGNN modeling through Structural Causal Model (SCM) (Pearl et al., 2000; Pearl, 2016), as illustrated in Fig- 3. We depict the causal relationships among seven key variables in the DyGNN setting: the dynamic graph Gırr, the unobservable causal variable C, the unobservable non- causal (environmental) variable S. the observable node at- tributes XI.T, the observable topology AI.T, representations H. and predictions y. Solid arrows indicate causal relation- ships, while dashed lines represent spurious correlations. Be- low are some critical insights about the SCM:
9
X
Sportous tactor
Ruri Thramir graph A Adjanenay matrion X. Nods cttiibutes
Cuasal
Represmntiion
Prediction
Figure 3: Structural Causal Model (SCM) for DyGNNs.
S - GiT + C: The dynamic graph G1rr consists of two disjoint parts: the causal part C and the non-causal/cnviromennaa part S.
A < and S - X1:T + two variables (causal variable C and non-causal variable S) construct two components of observable contextual subgraphs (node attributes X1:7 and topology Ai:)), which is different from i.i.d. data only consider attributes.
Air + X1:7 and H. >> y:: DyGNN backbones are leveraged generate future represen- tations based on observable contextual subgraphs, which are then utilized for making predictions.
C S: the spurious probabilistic dependencies between S and C.
Based on this SCM, we can identify two backdoor paths between and Y: (i) < G1.T + S AI:T > H + V, and (ūi) C + G1.T - S X i: - H + y. In both cases, the environmental variable S acts as a confounder between 91-r and y, potentially causing a misleading correlation between C and D, if there no direct causal link C + y. Therefore, severing
S is crucial. In the following sections, we will elaborate on how DyAug effectively severs these spurious correlations through the rationale-envirommen separation and augmentation.
3.4 TEMPORAI-CONDITIONE EXTIONALF-EVVROOMEEN SEPARATION
Given a graph snapshot Gr, we model its unobservable causal part as soft mask M. E [0, NxN where each entry represents the probability score of the corresponding edge belong- ing to the rationale subgraph. Naturally, the rationale for snapshot G. can be expressed as (() A, MR), }, and the causal part of the entire dynamic graph sequence is denoted as R [X1:r A + M Traditional static graph rationalization methods (Zhang et al., 2024a; Liu al., 2024a) typically follow the paradigm below extract rationales:
(1) where the causal mask is generated conditioned on the current features X, and topology A,, and the generator is parameterized by Φ. However, this overlooks the temporal dependencies between snapshots, often negatively disrupting the spatial- distribution of the augmented data. To address this issue, design temporal-conditioned graph rationalization, which progressively
M ~ Po (M. A,,X,),
5

---

Published as a conference paper at ICLR 2025
uncovers the causal subgraph along the temporal dimension. At each step. it depends solely the previous timestamp and current status, thereby maintaining the Markov property:
M po (M A,, X, M
where the generation of M additionally depends on the causal mask from the (t 1)-th timestamp. In practice, model the rationale as follows:
(M, A. X,
Po (M,)) A., X,,
(3)
where M is the element at the i-th row and j-th column of M representing the probability that edge eij belongs to the rationale at timestamp t. We compute M f,i as follows:
pa (M A,, X1, M /1 2tj, M 1.1j);
(4)
=LA - log(1 e) ww)/TT)
where 1()) an indicator function, wij = ( æ²j, M,,,)) parameterized by 4; e ~ Uniform(0, 1). a(.) represents the sigmoid function, and T is the temperature coefficient. When approaches zero, Equation (4) effectively returns the Bernoulli sampling result for edge eij. The gradient ///w/// remains well-defined long r 0. Through this temporally progressive rationale discovery, we ultimately obtain the rationale subgraph set 9 and the corresponding en- vironmental subgraph set G.. defined as follows:
Gh (XITT, 1 MET), f = (XIT, ALT @ M.T..
(5)
where M, = A, M. To further ensure temporal consistency, i.e, the rationales across different snapshots remain coherent even as the graph structure evolves, we propose the following consistency regularization loss:
Cep(sim(g) ()
Ler
log exp (sim (R) + Σ Exetomme4 exp )
where Ge represents the rationale within a w-step temporal window surrounding the central ra- tionale GR, while G. refers rationales that are further away. sim(...) measures the similarity between graphs, and we implement it as sim G sum[M M2 I). Equation (6) draws inspiration from the practices in Tonekaboni et al. (2021); Wang et al. (2023), where closely situated subsequences regarded positive pairs and those with larger distance Exhibiting a similar idca, Equation (6) aims to maintain higher consistency around the current ra- tionale. Upon disentangling the causal and non-causal components in dynamic graphs well as maintaining the temporal consistency, we proceed to the next step of data augmentation.
treated negatives.
3.5
DATA AUGMENTATION WITH ENVIRONMENT SUBGRAPHS
With the rationale subgraph set G. and the environmental subgraph set G available, explic- itly separate the message passing from the rationale and environmental subgraphs during the spatial and temporal modeling processes of the vanilla DyGNN:
H IT f- ALT @ MR Ox), H = fx(X A @ MET: Ox):
(7)
where HR, E R and H 1 RXXND represent the aggregated rationale and environment
embeddings for timestamps and environment for predictions, leading spurious correlations between G and y, resulting in potentially accurate but unjustified predictions. Therefore, DyAug enhances the training samples by simulating various eeniioneee combinations within the node embedding space. To be more concrete, considering the rationale embedding h, [i. for node oi at timestamp t, we propose three environment replacement augmentation paradigms.
The standard fe without rationalization tends to merge rationale

---

Published as a conference paper at ICLR 2025
Spatial Replacement Augmentation Data augmentation with environment replacement replaces the environment variable of the current node of with any other environment variable from a different sample. Given that the rationable embedding h, is considered to the dominant factor of predic- tions of 24, the environment embedding can be interpreted as natural noise. Hence, combining of's rationale embedding with environment embeddings from other nodes at the same snapshot enhances the model's robustness against the noise signal brought by the environment subgraphs. This pro- cess can be accomplished using any pooling function, such concatenation, sum pooling, max pooling. Taking sum pooling for example, the spatial replacement is executed as follows:
t, f
Combi (embin (h,,,; D = h,,, h j Uniform(1, N) \4,
(8)
where h,, represents the augmented node embedding, and b L..
Temporal Replacement Augmentation In contrast to spatial replacement, temporal enhancement focuses augmenting the temporal dimension. As the dynamic graph structure evolves, AI.T t MP. remains a stable causal factor; however, fe may inadvertently learn spurious patterns from the complementary non-causal components. Therefore, for each node 24, we replace its environment embedding with one from a historical snapshot to avoid reliance on temporal trivial information:
b f Combine. [h, hy,)), ~ Uniform [1 1).
(9)
Spatial-temporal Replacement Augmentation Combining the above two, spatial- envi- ronment replacement augments data simultaneously across both spatial and temporal dimensions:
hr.5 + Combi i ne (h, hn.)), (p.j) (Uniform(1, ( - 1), Uniform(1, N) N) \i).
(10)
After applying the three types of environment replacement, we obtain the augmented representa- H.l. where H, [h,2,, h..2..... h..v). These representations are then further transformed by the DyGNN backhone into future node embeddings XT+1, which are subsequently converted into predictions í as follows:
tions H1T- [H, H....., Hr..
X f(H ALT @ Mf::;; 5 fa(ST+1;0.).
(1I)
3.6 OPTIMIZATION AND ANALYSIS
Optimization Objective In addition to the original task-specific loss associated with DyGNN training. denoted as Lpred. DyAug introduces two supplementary losses: the consistency regulariza- tion loss defined in Equation (6), and the contrastive loss aimed at differentiating between causal and non-causal representations while ensuring semantic similarity between causal and augmented representations, which is expressed mathematically as follows:
T
exp(sim(h,.. h(,)/T))))
La 4a= MΣΣNN log
(12)
exp(sim(he,. h exp(sim h/)
where T represents the temperature coefficient and sim (im -) is computed using the dot product. The overall training objective for DyAug is formulated as: min L θ) Fpedd + Lar + Las,
(13)
4.6
where & pertains to rationale-enviromment separation, θ parameterizes the vanilla DyGNN back- bone, and 01, 02 are scaling factors.
Complexity Analysis The additional complexity coming with DyAug arises primarily from three sources: (I) causal mask estimation, which contributes O [g(0] D); (2) the contrastive loss, adding OTND);; and (3) the consistency loss, contributing O OT 1t= [g(1)), which is negligi- ble. summary, the overall extra complexity introduced by DyAug is O |001 NDT*).
EXPERIMENTS
In this section, we conduct extensive experiments to answer the following research questions (RQ): (RQ1) Can DyAug augment dynamic GNNs?
(RQ2) Can DyAug better preserve the temporal consistency of dynamic graphs?
(RQ3) Does DyAug improve the robustness of DyGNNs against adversarial attacks?
(RQ4) Does DyAug enhance the outoof-distributin generalization of DyGNNs?
(RQ5) How sensitive is DyAug to its key components and parameters?
7

---

Published as a conference paper at ICLR 2025
Table 1: AUC score (# standard deviation) of future link prediction task five real-world datasets. The best results are in bold, and the runner-ups are underlined.
Method
COLLAB
Yelp
Bitcoin
UCI
ACT
Vanilla
0.8278=0000522
0.6645=0.0187
0.8766=00.0034
0.7682=0.0074
0.7963-=000041
+DropFEdee
0.8285++0.0059
0.6472=0.0205
0.8732=000051
0.7693=0.0105
0.7928+0.0042
+DropNode
0.8297+00.007
0.6448=0.01%6
0.8749=0.0064
0.7664=0.0068
0.7942+0.0500
GRCN
+DropMessage
0.8326++000097
0.6669+0.0240
0.8780+0.0057
0.7690+0.0119
0.7968+0.0044
+GraphMixup
0.8258++0.0000 +000
0.6697=000180
0.8641+0.0033
0.7613=0.0133
0.7902++0.00 0045
+NNeuralSparse
0.83944:0.0076
0.6705=0.0233
0.8792=00.006
0.7710=0.0062
0.7959=000044
+SUBLIME
0.8312++0.005.
0.6685=0.0273
0.8770=0.0055
0.7735=0.0081
0.7989+000044
+RGDA
0.8374+0.0031
0.6692+0.0194
0.8812+000031
0.7698+00 00.0046
0.8066+000008
+DyAug (ours)
0.8495 0.0070
0.0000
0.9079+ 0.0029
0.7783
0.0054
0.8147 0.0049
Vanilla
0.88074:00018
0.7962=000045
0.8896=000027
0.7502=0.0056
0.7790=10.003.
+DropEdge
0.8760=+0000099
0.7185
0.8843=0.0048
0.7516=0.0077
0.7689- 0.067
+DropNode
0.8783-10.001
0.7980=000077
0.882610.0039
0.7519 0.0055
0.7705 0044
DySAT
+DropMessage
0.8815:10.0069
0.8915=0.0070 0.7964=0.0082
0.0102
0.7689
+GraphMixup
0.8085:1:.0112 0.7814=0.0029
0.8726=000031
0.0000
0.7653+000012
+NeuralSparre
0.8862::000053
0.8074=000050
0.8916=000044
0.7579=0.0064
0.7796=+0.006
+SUBLIME
0.8871+000034
0.8037=000041
0.8927=000043
0.7552==00004
0.7772++ 0.054
+RGDA
0.8897+000000
0.8049
0.8065
0.7560-0.0051
0.7805+000004
+DyAug (ours)
+.8925+0.0034
0.8233 0.0023
0.9032+ 0.0040
0.7698
0.0063
0.7860 0.0054
Vanilla
0.0029
0,8072+1.0033
0.0013
1,79321000033
0.84571100001
+DropEdge
0,923511.0002
0.801510.0041
0.0884
0.798510.000
0.83661 0.0355
+DropNode
0.921510.0039 0.803910.000 0.044
0.892810.0035
0.7913
18382.10.0030
SEIGN
+DropMessage
0.9259+10.0032 0.812010.0032
0.89611000071
0.789610.0024
0.842910.0011
+GruphMixup
0.9187+10.002 0.7942=000043
0.8005=000057
0.7903=000019
0.8311
+NNuralSparsee
0.9279++0.002 0.8038=000046
0.8994=0.0028
0.8012=0.0030
0.8491
+SUBLIME
0.9310=+0.0027 0.8144=000015
0.8069=000020 0.09
0.8465+000013
+RGDA
0.92455+-000022
0.8131=000020
0,9013=0.0018
0.7985=0.0039
0.8472+000013
+DyAug (ours)
0.9362:10.0022
0.828410.0015
0.9067=0.0017
0.0092
0.854610.0029
4.1 EXPERIMENTAL SETUP
Datasets and Splits To thoroughly evaluate our proposed method, we select five real-world datasets. COLLAB (Tang et al., 2012) is an academic collaboration network spanning 16 years. Yelp (Sankar et al., 2020) is a business review dataset containing customer feedback on various businesses. Bitcoin (Kumar et al., 2018) is trust network dataset representing users who engage in trading on the Bitcoin OTC platform. UCI (Panzarasa et al., 2009) is an online communication network from the University of California, Irvine, capturing student interactions. Lastly, ACT (Ku- mar et al., 2019) describes the actions taken by users on a popular MOOC website within 30 days. Backbones and Baselines For DyGNN backbones, we select three classical baselines: (1) GCRN (Sco et al., 2018), which combines GCNs and GRU (Chung et al., 2014); (2) DySAT (Sankar et al., 2020), which models spatial and temporal dependencies via self-attention; and (3) SEIGN (Qin et al., 2023), which leverages GCN for message passing, GRU for parameter up- dates, and transformer for learning the final node representations. For baselines, compre- hensively choose seven GDA techniques for comparison. Regarding rule-based augmenters, we adopt DropEdge (Rong et al., 2019), DropNode (Feng et al., 2020), DropMessage (Fang et al., 2022), and Graph Mixup (Wang et al., 2021b). Regarding rule-based augmenters, we opt for Neu- ralSparse (Zheng et al., 2020) and SUBLIME (Liu et al., 2022d) for the graph structure learning branch, RGDA (Liu et al., 2024a) for the graph rationalization branch. Notably. we acknowledge that some classical or highly related GDA methods, such as DIR (Wu et al., 2022b), GREA (Liu et al., 2022a), JOAO (You et al., 2021), and AIA (Sui et al., 2024), are not included in our eval- uation. This exclusion is either due to data format limitations (e.g., methods focused solely on graph classification) or incompatibility issues (e.g., inability to adapt to dynamic graphs). Detailed explanations and the full baseline setup can be found in Appendix A.
Hyperparameter Configurations We set the number of layers to two for all baselines, with a hidden dimension of 128. Specifically, for DyAug, we fix 7 = le 2 and w = 2 across all datasets. For each node, we assign equal probability of selecting one of the following strategies: (I) no replacement, using only the rationale embedding: (2) spatial replacement; (3) temporal replacement; or (4) spatial-temper replacement strategies in Appendix B.2. For the parameters ai and ag in Equation (13), we vary
replacement. We provide an ablation study on the effectiveness of these
on E (le 2, 5e 2, le 1) and 02 E (le 4, 5e 4, le 3, 5e - 3).
8

---

Published as a conference paper at ICLR 2025
1.0
Yelp
COLLAB
0.8
0.75
Vanilla
DropEdge
Vanilla
0.0
0.4
GraphMioup
DropNode
Dreptidoy
Drephodee
0.4
Deopädgee
Deephtedo
Graphhlispp
Gespholiurp
0.2
RGDA
RUDA
0.3
DyAug
Dybag
0.0
0
3 Edge Timespan
8.0
0.5
1.0
1.5
2,0
2.5
3-5
+00
0.0
Edge Timespan
Edge Timespan
Figure 4: The cumulative distribution function (CDF) of edge timespan for the vanilla dataset and after apply- ing different GDA methods YELP, COLLAB and ACT. We opt for GRCN for all the datasets. The faster the curve converges to 1, greater proportion edges with shorter timespans.
90
before topology attack
after topology attack
85
Rrv7
80.3
81.4
AUC (%)
80
78.1
75
70
68.3
69.6
65
$5.2
644.3
60
Vanílla
DroppEdge
+DropNode
+GraphMixup +DropAlesagge
+NeuralSparse
+SUBLIME
+RGDA
+DyAug (Ours)
Figure The performance comparison various GDA methods under structure attack on DYSAT+YELP.
4.2 COMPARISON WITH EXISTING GDA METHODS (RQ1 & RQ2)
We compare the performance of DyAug against seven GDA baselines across five datasets on GRCN, DySAT, and SEIGN, summarized in Table 1. We draw the following observations (Obs.):
Obs. Temporal consistency counts for dynamic graphs. DropEdge, DropNode, DropMessage, and GraphMixup belong to rule-based augmenters, and many of them consistently result in perfor- mance drops rather than improvements. For example, GraphMixup shows 1.25% & decrease on GRCN+Bitco ini, and DropNode shows a O. 0.85% drop on DySAT+ACT. We attribute the under- lying cause the disruption of temporal consistency. As shown in Figure 4, both DropNode and GraphMixup lead to rapid convergence of the edge timespan CDF to 1, which indicates that these methods cause many long-spanning edges disappear, replacing them with numerous short-lived edges that quickly appear and vanish. In contrast, RGDA and our DyAug closely approximate the vanilla CDF, resulting in far more stable and significant performance improvements.
Obs. DyAug continuously enhances dynamic graph modeling. DyAug demonstrates a stable performance improvement across all datasets and DyGNN backbones. Nevertheless, the magnitude of this improvement tied to the complexity of the DyGNN backbone. For simpler backbones like GRCN, DyAug yields notable gains, such as a 1.77% increase COLLAB and a 3. 3.13% boost on Bitcoin. While the AUC improvements on more advanced backbones like SEIGN are relatively marginal, DyAug still achieves 2.14% 1 increase on YELP.
4.3 AGAINST ADVERSARIAL ATTACKS (RQ3)
In this section, we aim to empirically validate that DyAug can effectively defend against both non- targeted and targeted attacks answer RQ3. We employ three types of attacks: (1) structure attack, which randomly perturbs 20% of edges; (2) feature attack, where Gaussian noise is added to the node features; and (3) Nettack (poisoning mode), where Nettack (Zügner et al., 2018) 8) is applied to perturb the training set twice. The results are visualized in Figures 5, 7 and 8. We observe:
Obs. AyAug outperform all baselines under various attack modes. Among the three types of attacks, Nettack, a targeted attack, poses the greatest challenge the robustness of DyGNNs. As shown in Figure 8, the vanilla DySAT suffers from a significant drop of 12.7% in AUC, and even when combined with RGDA, it only recovers 2.1% of the loss. However, DyAug, through its tailored data augmentation design, effectively mitigates the impact of noise and perturbations during training, resulting an 8.2% improvement in the attacked model's performance.

---

Published as a conference paper at ICLR 2025
Table 2: AUC score (%) of different methods real-world datasets. The best results in bold and the second-best results are underlined. "w/o DS' and 'w/ DS' denote test data with and without distribution shift.
Model
COLLAB (ROC-AUCT)
YELP (ROC-AUCT)
Test Data
w/o DS
w/ DDS
w/o DS
w/ DS
GRCN (Seo al., 2018)
82.78 0.52
67.49 1: 0.73
66.45 1: 1.87
61.82 1 3.39
DyAug
84,95 0.70
73.22 1: 0.56
67.95 1 0.24
61.78 1 2.76
DySAT (Sankar ct al., 2020)
88.07= 0.18
75.59 + 0.29
79.62 + 0.65
65.80 + 1.22
DyAuug
89.25 0.74
82.56 + 0.68
82.33 1.13
73.15 + 0.92
SEIGN (Qin et al., 2023)
92,19= 0.21
80.68 + 0.72
80.72 + 0.39
67.19 + 0.84
DyAug
93.62=: 0.42
83.11 = 0.56
82.84 + 0.35
76.50 - 0.65
IRM (Rosenfeld et al., 2021)
87.96 0.90
75.42 + 0.87
66.49 + 0.78
56.02 + 6.08
DIDA (Zhang et al., 2022b)
91.97= 0,05
81.87 + 0,40
78.22 + 0,40
75.92 + 0.90
DGIB-Bemn (Yuan et al., 2024)
92.17= 0.20
83.09 + 0.56
76.88 + 0.20
72.56 + 0.74
4.4 AGAINST DISTRIBUTION SHIFT (RQ4)
Graph rationalization was originally introduced to address the out-of-distribution (OOD) challenge by capturing invariant patterns in evolving data (Wu et al., 2021; 2024). To evaluate whether DyAug can defend against distribution shifts in dynamic graphs, we use COLLAB and Yelp, and explicitly construct distribution shifts. Specifically, for COLLAB, we transfer all edges belonging to "data mining" category to the test set, ensuring that DyGNN has never been exposed to this category during training. For Yelp, we select "Pizza" edges the out-of-distribution data. We observe that:
Obs. 2 DyAug elfectively enhances the robustness of DyGNNs. As demonstrated in Table 2, SEIGN+DyAug consistently achieves the best performance on both Yelp and COLLAB, regard- less of the presence of distribution shifts. This improvement can be attributed not only SEIGN's strong baseline performance but also to DyAug's ability to sever spurious correlations. For example, on YELP, DyAug boosts SEIGN's OOD performance from 67.19% to 76.50%.
85
DyArg
w/lo
Cl.
0g//1
le 2
5e-
le
$1.40
(3)) (8)
80
70.30
79.90
$o.10
77-40
76.70
75.60
Ge-
le
78.17
77.
77.60.0.4
14.0.
78.601n2
78. 20.2
78.45
78.5
78.30
77.9210.
75
74:50
5e
3
77.81 77.52
77.0610-4
70
Clean
Structure attack
Table 3: Sensitivity study on scaling fac-
Figure Ablation study on DyAug and its four variants, tested ACT and that after structure attack. We use GRCN the backbone.
on and a2. The results reported DySAT backbone and ACT dataset.
4.5
ABLATION STUDY AND SENSITIVITY ANALYSIS (RQ5)
Ablation Study We evaluate four variants: (1) DyAug w/o TC, where graph rationalization is snapshot-independent rather than temporally conditioned; (2) DyAug w/o RA, where all data aug- mentations are discarded; (3) DyAug w/o CR, where Ler is omitted; and (4) DyAug w/o CL, where La discarded. It can observed from Figure that the removal of each module results AUC decay, among which DyAug w/o RA is the most detrimental, leading to 2.9% J drop under the structure attack. This demonstrates each component's 'ss importance in dynamic graph augmentation.
We evaluate DyAug under different ai and a2. As shown Table 3, Dy is relatively insensitive to changes in a1 However, when 02 becomes too large, a performance drop is observed. For instance, with 0 = 1e - 2. the performance with 02 = 1e is 0.75% higher than that with 0g = 5e 3. Nevertheless, AyAug demonstrates overall robustness parameter variations.
Sensitivity Analysis
5 CONCLUSION
In this work, we present the first graph data augmentation (GDA) method specifically designed for (discrete-time) dynamic graphs, termed DyAug. DyAug addresses the limitations of previous static GDA methods, i.e., the unawareness of temporal consistency, by employing temporal-condition rationale discovery to disentangle the antional--envioomen further propose three augmentation strategies to enrich the data distribution. Experimental results demonstrate that DyAug excels in empowering, robustifying, and generalizing dynamic GNNs.
within dynamic graph sequences. We
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
Dawei Cheng is supported by the National Natural Science Foundation of China (62472317). Yiyan Qi supported in part by the National Natural Science Foundation of China (62372362).
REFERENCES
Michael Adjeisah, Xinzhong Zhu, Huiying Xu, and Tewodros Alemu Ayall. Towards data aug- mentation in graph neural network: An overview and evaluation. Computer Science Review, 47: 100527, 2023.
Khaled Alomar, Halil Ibrahim Aysel, and Xiaohao Cai. Data augmentation in classification and segmentation: A survey and new strategies. Journal of Imaging. 9(2):46, 2023.
Claudio DT Barros, Matheus RF Mendonça, Alex Vieira, and Artur Ziviani. survey on embed- ding dynamic graphs. ACM Compuling Surveys (CSUR), 5311):137,,
Fabian Beck. Michael Burch, Stephan Diehl, and Daniel Weiskopf. A taxonomy and survey of dynamic graph visualization. In Computer graphics forum, volume 36, pp. 133-159. Wiley Online Library, 2017.
Tanya Y Berger- Berger-Wolf and Jared Saia. A framework for analysis of dynamic social networks. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 523-528. 2006.
Hongjiang Chen, Pengfei Jiao, Huijun Tang, and Huaming Wu. Temporal graph representation learning with adaptive augmentation contrastive. In Joint European conference machine learn- ing and knowledge discovery in databases, pp. 683-699. Springer, 2023.
Junyoung Chung. Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: 141..354 2014.
Haixing Dai, Zhengliang Liu, Wenxiong Liao, Xiaoke Huang, Yihan Cao, Zihao Wu, Lin Zhao, Shaochen Xu, Wei Liu, Ninghao Liu, et al. Auggpt: Leveraging chatgpt for text data augmenta- tion. arXiv preprint arXiv:2302.13007 2023.
Quanyu Dai, Xiao Shen, Liang Zhang, Qiang Li, and Dan Wang. Adversarial training methods for network embedding. The World Wide Web Conference, pp. 329-339, 2019.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey, ACM SIGKDD Explorations Newsletter, 24(2).61-77, 2022.
Taoran Fang, Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. Dropmes- sage: Unifying random dropping for graph neural networks. arXiv preprint arXiv:2204. 10037, 2022.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092-22103, 2020.
ZhengZhao Feng, Rui Wang, TianXing Wang, Mingli Song. Sai Wu, and Shuibing He. A com- prehensive survey of dynamic graph neural networks: Models, frameworks, benchmarks, experi- ments and challenges. arXiv preprint arxXv:2405. 404600077.. 2024.
Jibing Gong, Yi Zhao, Jinye Zhao, Jin Zhang, Guixiang Ma. Shaojie Zheng, Shuying Du, and Jie Tang. Personalized recommendation via inductive spatiotemporal graph neural network. Pattern Recognition, 145:109884, 2024.
Derek Greene, Donal Doyle, and Padraig Cunningham. Tracking the evolution of communities in dynamic social networks. In 2010 international conference on advances in social networks analysis and mining, pp. 176-183. IEEE, 2010.

---

Published as a conference paper at ICLR 2025
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, 2022.
Wenke Huang, Guancheng Wan, Mang Ye, and Bo Du Federated graph semantic and structural learning. In Proceedings of the Thirty-Secone International Joint Conference on Artificial Intel- 2023.
ligence, pp.
Xuanwen Huang, Yang Yang. Yang Wang, Chunping Wang, Zhisheng Zhang, Jiarong Xu, Lei Chen, and Michalis Vazirgiannis. Dgraph: A large-scale financial dataset for graph anomaly detection. Advances in Neural Information Processing Systems, 35:22765 227777,, 2022.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 66-74, 2020.
Yannis Karmim, Mare Lafon, Raphaël Fournier S' S'nichotta, and Nicolas Thome. Supra-laplacian encoding for transformer on dynamic graphs. arXiv preprint 1xXi::2499.19886 2024.
Junghurn Kim, Sukwon Yun, and Chanyoung Park. S-mixup: Structural mixup for graph neural net- works. In Proceedings the 32nd ACM International Conference on Information and Knowledge Management, pp. 4003-4007, 2023.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein, Robust optimization as data augmentation for large-scale graphs. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 60-69, 2022.
Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and VS Subrahma- nian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 333-341, 2018
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1269-1278, 2019.
Hongxi Li, Zuxuan Zhang, Dengzhe Liang, and Yuncheng Jiang. K-truss based temporal graph convolutional network for dynamic graphs In Asian Conference on Machine Learning, pp. 739- 754. PMLR, 2024a.
Jianxin Li, Xingcheng Fu, Shijie Zhu, Hao Peng, Senzhang Wang, Qingyun Sun, S Yu Philip, and Lifang He. A robust and generalized framework for adversarial graph embedding. IEEE Trans- actions Knowledge and Data Engineering, 35(11): 11011-100011111111 2023a.
Jintang Li, Zhouxin Yu, Zulun Zhu, Liang Chen, Qi Yu, Zibin Zheng, Sheng Tian, Ruofan Wu, and Changhua Meng. Scaling up dynamic graph representation learning via spiking neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 3588-8596 2023b.
Xiaohan Li, Mengqi Zhang, Shu Wu, Zheng Liu, Liang Wang, and S Yu Philip. Dynamic graph collaborative filtering. In 2020 IEEE international conference data mining (ICDM), pp. 322- 331. IEEE, 2020.
Yuhan Li, Zhixun Li, Peisong Wang. Jia Li, Xiangguo Sun, Hong Cheng, and Jeffrey Xu Yu. A survey of graph meets large language model: Progress and future directions. arXiv preprint 1xXiv:3311.12333 2023c.
Zhixun Li, Liang Wang, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, et al. Gslb: The graph structure learning benchmark. Advances in Neural Information Processing Systems, 36:30306-30318 2023d.
Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, et al. Gslb: the graph structure learning benchmark. Advances in Neural Information Processing Systems, 36, 2024b.
12

---

Published as a conference paper at ICLR 2025
Zhixun Li, Dingshuo Chen, Tong Zhao, Daixin Wang, Hongrui Liu, Zhiqiang Zhang, Jun Zhou, and Jeffrey Xu Yu. Iceberg: Debiased self-training for cass-imbalanced node classification, arXiv preprint arXhv:2502..662 06280, 2025.
Zhigiang
Hongyi Ling, Zhimeng Jiang, Meng Liu, Shuiwang Ji, and Na Zou. Graph mixup with soft align- ments. In International Conference on Machine Learning, pp. 21335-21349, PMLR, 2023.
Gang Liu, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Graph rationalization with environment-based augmentations. In Proceedings of the 28th ACM SIGKDD International Con- ference Knowledge Discovery & Data Mining, 2022a.
Gang Liu, Eric Inae, Tengfei Luo, and Meng Jiang. Rationalizing graph neural networks with data augmentation. ACM Transactions Knowledge Discovery from Data, 18(4):1-23, 2024a.
Gang Liu, Eric Inae, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Data-centric learning from unlabeled graphs with diffusion model. Advances in neural information processing systems, 36, 2024b.
Nian Liu, Xiao Wang. Lingfei Wu, Yu Chen, Xiaojie Guo, and Chuan Shi. Compact graph structure learning via mutual information compression. In Proceedings of the ACM web conference 2022, pp. 1601-1610, 2022b.
Songtao Liu, Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu. Local augmentation for graph neural networks. arXiv preprint Sitv:2109.03856 2022c.
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsu- pervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, pp. 1392-1403 2022d.
Zewen Liu, Guancheng Wan, Aditya Prakash, Max SY Lau, and Wei Jin. A review of graph neural networks in epidemic modeling. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 6577-6587 2024c.
Youzhi Luo, Michael Curtis McThrow, Wing Yee Au, Tao Komikado, Kanji Uchino, Koji Maruhashi, and Shuiwang Ji. Automated data augmentations for graph classification. In The Eleventh International Conference Learning Representations, 2023.
Xinyu Ma, Xu Chu, Yasha Wang, Yang Lin, Junfeng Zhao, Liantao Ma, and Wenwu Zhu. Fused gromov-wasserseenn graph mixup for graph-level classifications. Advances in Neural Information Processing Systems, 36, 2024.
Diego Nascimento, Bruno Pimentel, Renata MCR Souza, Lilia Costa, Sandro Gonçalves, and Francisco Louzada. Dynamic graph in symbolic data framework: An account of the causal relation using covid-19 reports and some reflections on the financial world. Chaos, Solitons & Fractals, 153:1 11440, 2021.
Pietro Panzarasa, Tore Opsahl, and Kathleen M Carley. Patterns and dynamics of users' behavior and interaction: Network analysis of an online community. Journal of the American Society for Information Science and Technology, 60(5):911-933 2009.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional net- works for dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3363-5370, 2020.
Joonhyung Park, Hajin Shim, and Eunho Yang. Graph transplant: Node saliency-guided graph mixup with local structure preservation. arXiv preprint arXiv:2111.05639 2021.
Judea Pearl. Causal inference in statistics: a primer. John Wiley & Sons, 2016.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CambridgeUnieersitpppeess, 19:2, 2000.
13

---

Published as a conference paper at ICLR 2025
Hao Peng. Hongfei Wang, Bowen Du, Md Zakirul Alam Bhuiyan, Hongyuan Ma, Jianwei Liu, Lihong Wang, Zeyu Yang, Linfeng Du, Senzhang Wang, et al. Spatial temporal incidence dynamic graph neural networks for traffic flow forecasting, Information Sciences, 521:277-290 2020.
Hao Peng, Bowen Du, Mingsheng Liu, Mingzhe Liu, Shumei Ji, Senzhang Wang. Xu Zhang, and Lifang He. Dynamic graph convolutional network for long-term traffic flow prediction with rein- forcement learning. Information Sciences, 578:401-416, 2021.
Rui Qian, Tianjian Meng, Boqing Gong, Ming-Hsure Yang, Huisheng Wang. Serge Belongie, and Yin Cui. Spatiotemporal contrastive video representation learning. In Proceedings of the IEEE/CVF conference on computer vision and patiern recognilion, pp. 6964-6974, 2021.
Xiao Qin, Nasrullah Sheikh, Chuan Lei, Berthold Reinwald, and Giacomo Domeniconi. Seign: A simple and efficient graph neural network for large dynamic graphs. In 2023 IEEE 39th Interna- lional Conference on Data Engineering (ICDE), pp. 2850-2863. IEEE, 2023.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk min- imization. In International Conference on Learning Representations, 2021. URL https:
// //openreview. net/ weerrrmidd-bbNaaS
42.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural rep- resentation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 519-527, 2020.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pp. 362-373. Springer, 2018.
Kartik Sharma, Rakshit Trivedi, Rohit Sridhar, and Srijan Kumar. Temporal dynamics-aware adver- sarial attacks on discrete-time dynamic graph models. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2023-2035, 2023.
Xiao Shen, Dewang Sun, Shirui Pan, Xi Zhou, and Laurence T Yang. Neighbor contrastive learning on learnable graph augmentation. In Proceedings the AAAI conference artificial intelligence, volume 37, pp. 9782-9791, 2023.
Connor Shorten, Taghi M Khoshgoftaar, and Borko Furht. Text data augmentation for deep learning. Journal of big Data, 8(1):101, 2021.
Jiasheng Si, Yingjie Zhu, and Deyu Zhou. Exploring faithful rationale for multi-hop fact verifi cation via salience-aware graph learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 13581,13581, 2023.
Yongduo Sui, Qitian Wu, Jiancan Wu, Qing Cui, Longfei Li, Jun Zhou, Xiang Wang. and Xiangnan He. Unleashing the power of graph data augmentation on covariate distribution shift, Advances in Neural Information Processing Systems, 36, 2024.
Mengying Sun, Jing Xing, Huijun Wang, Bin Chen, and Jiayu Zhou Mocl: data-driven molecular fingerprint via knowledge-aware contrastive learning from molecular graph. Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 3585-3594, 2021.
Qingyun Sun, Jianxin Li, Hao Peng. Jia Wu, Xingeheng Fu, Cheng Ji, and S Yu Philip. Graph structure learning with variational information bottleneck. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 4165-4174, 2022.
Zihan Tan, Guancheng Wan, Wenke Huang, and Mang Ye. Fedssp: Federated graph learning with spectral knowledge and personalized preference. Thirty-eightt Annual Conference on Neural Information Processing Systems, 2024.
14

---

Published as a conference paper at ICLR 2025
Jie Tang, Sen Wu, Jimeng Sun, and Hang Su. Cross-domain collaboration recommendation. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1285-1293, 2012.
Sana Tonekaboni, Danny Eytan, and Anna Goldenberg. Unsupervised representation learning for time series with temporal neighborhood coding. arXiv preprint arXiv:2106.00750, 2021.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2019.
Guancheng Wan, Zewen Liu, Max S.Y. Lau, B. Aditya Prakash, and Wei Jin. Epidemiology-aware neural ode with continuous disease transmission graph. arXiv preprint arXiv:2410.00049 20244,
Guancheng Wan, Yijun Tian, Wenke Huang, Nitesh V Chawla, and Mang Ye. S3gel: Spectral, swift, spatial graph contrastive learning. In Forty-first International Conference on Machine Learning, 2024b.
Junshan Wang, Wenhao Zhu, Guojie Song, and Liang Wang. Streaming graph neural networks with generative replay. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1878-1888, 2022.
Kun Wang. Guohao Li, Shilong Wang, Guibin Zhang. Kai Wang, Yang You, Junfeng Fang, Xiao- jiang Peng. Yuxuan Liang, and Yang Wang. The snowflake hypothesis: Training and powering gnn with one node one receptive field. In Proceedings of the 30th ACM SIGKDD Conference on
Knowledge Discovery and Data Mining, KDD '24, pp. 3152-3163, New York, NY, USA. 2024. Association for Computing Machinery. ISBN 9798400704901. doi: 10. 10.11457663758833677766.. URL wwwptttpp////c /ooi /10. 11111111333335 3671766
Tianchun Wang, Dongsheng Luo, Wei Cheng, Haifeng Chen, and Xiang Zhang. Dyexplainer: Ex- plainable dynamic graph neural networks. arXiv preprint arXi::2310.16375 2023.
Yiwei Wang, Wei Wang. Yuxuan Liang. Yujun Cai, and Bryan Hooi. Graphcrop: Subgraph cropping for graph classification. arXiv preprint arXiv:2009. 10564, 2020.
Yiwei Wang. Yujun Cai, Yuxuan Liang, Henghui Ding. Changhu Wang, Siddharth Bhatia, and Bryan Hooi. Adaptive data augmentation temporal graphs Advances in Neural Information Process- ing Systems, 34, 2021a.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference, pp. 3663-3674, 2021b.
Jiapeng Wu, Meng Cao, Jackie Chi Kit Cheung, and William L. Hamilton. Temp: Temporal message passing for temporal knowledge graph completion. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Lan- guage Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 5730-5746. Association for Computational Linguisties, 2020.
Lirong Wu, Haitao Lin, Zihan Liu, Zicheng Liu, Yufei Huang, and Stan Z Li. Homophily-enhan self-supervision for graph structure learning: Insights and directions. IEEE Transactions Neu- ral Networks and Learning Systems, 2023.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27401, 2022a.
Qitian Wu, Fan Nie, Chenxiao Yang, Tianyi Bao, and Junchi Yan. Graph out-of-distribution gen- eralization via causal intervention. In Proceedings of the ACM Web Conference 2024, pp- 850-860, 2024.
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2021.
15

---

Published as a conference paper at ICLR 2025
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In The Tenth International Conference on Learning Repre- sentations. OpenReview.net, 2022b.
Suorong Yang, Weikang Xiao, Mengchen Zhang, Suhan Guo, Jian Zhao, and Furao Shen. Image data augmentation for deep learning: A survey. arXiv preprint arXiv:2204.0800 2022.
Yu Yang, Hongzhi Yin, Jiannong Cao, Tong Chen, Quoe Viet Hung Nguyen, Xiaofang Zhou, and Lei Chen. Time-aware dynamic graph embedding for asynchronous structural evolution. IEEE Transactions on Knowledge and Data Engineering, 35(9):656-9677) 2023.
Jiaxuan You, Tianyu Du, and Jure Leskovec. Roland: graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pp.
2022.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
Yuning You. Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. In International Conference on Machine Learning, pp. 12121-12132. PMLR, 2021.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint 1rXiv:1709:04875 2017.
Haonan Yuan, Qingyun Sun, Xingcheng Fu, Cheng Ji, and Jianxin Li. Dynamic graph information bottleneck. In Proceedings of the ACM on Web Conference 2024, pp. 469-480, 2024.
Linan Yue, Qi Liu. Ye Liu, Weibo Gao, Fangzhou Yao, and Wenfeng Li. Cooperative classification and rationalization for graph generalization. In Proceedings of the ACM on Web Conference 2024, pp. 344-352, 2024a.
Yanwei Yue, Guibin Zhang, Haoran Yang, and Dawei Cheng. Fast track to winning tickets: Repow- ering ohe-shot pruning for graph neural networks. arXiv preprint arXiv:2412.07605, 2024b.
Guibin Zhang, Yiqiao Chen, Shiyu Wang, Kun Wang, and Junfeng Fang. Fortune favors the invari- ant: Enhancing gnns' generalizability with invariant graph learning. Knowledge-Band Systems, 292: 192:111622 12600, 2024a.
Guibin Zhang, Xiangguo Sun, Yanwei Yue, Chonghe Jiang, Kun Wang, Tianlong Chen, and Shirui Pan. Graph sparsification via mixture of graphs. arXiv preprint arXiv:2405. 14260, 2024b.
Guibin Zhang, Kun Wang, Wei Huang, Yanwei Yue, Yang Wang, Roger Zimmermann, Aojun Zhou, Dawei Cheng, Jin Zeng, and Yuxuan Liang. Graph lottery ticket automated. In The Twelfth International Conference on Learning Representations, 2024c. URL https:://oooot //pprr/iee/.e..www... fort/form22 2id=iiddd- iid=nmBBBB-- jBZoySX.
Guibin Zhang, Yanwei Yue, Kun Wang, Junfeng Fang. Yongduo Sui, Kai Wang, Yuxuan Liang, Dawei Cheng, Shirui Pan, and Tianlong Chen. Two heads are better than one: Boosting graph sparse training via semantic and topological awareness. arXiv preprint arXiv:2402.01 00242222..22.... 2024d.
Haozhen Zhang, Le Yu, Xi Xiao, Qing Li, Francesco Mercaldo, Xiapu Luo, and Qixu Liu. Tie- gnn: A temporal fusion encoder using graph neural networks for fine-grained encrypted traffic classification. In Proceedings of the ACM Web Conference 2023, pp. 2066-2075. 2023a.
Mengqi Zhang, Shu Wu, Xueli Yu, Qiang Liu, and Liang Wang. Dynamic graph neural networks for sequential recommendation. IEEE Transactions Knowledge and Data Engineering, 35(5): 4741-4753, 2022a.
Shilei Zhang, Toyotaro Suzumura, and Li Zhang. Dyngraphtrans: Dynamic graph embedding via modified universal transformer networks for financial transaction data. In 2021 IEEE Interna- fional Conference on Smart Data Services (SMDS), pp. 184-191. IEFF, 2021.
16

---

Published as a conference paper at ICLR 2025
Xin Zhang, Qiaoyu Tan, Xiao Huang, and Bo Li. Graph contrastive learning with personalized augmentation. IEEE Transactions on Knowledge and Data Engineering, 2024e.
Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmentation for graph contrastive learning and beyond. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 11289-11297, 2023b.
Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Zhou Qin, and Wenwu Zhu. Dynamic graph neural networks under apatio-tempone distribution shift. Advances in neural information pro- cessing systems, 6089, 2022b.
Jianan Zhao, Qianlong Wen, Mingxuan Ju, Chuxu Zhang, and Yanfang Ye. Self-supervised graph structure refinement for graph neural networks. In Proceedings of the Sixteenth ACM Interna- tional Conference on Web Search and Data Mining, pp. 159-167, 2023.
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification on graphs with graph neural networks. In Proceedings of the 14th ACM international conference web search and data mining, pp. 833-841, 2021a.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. In Proceedings of the AAAI Conference Artificial Intel- ligence, volume 35, pp. 11015-11023, 2021b.
Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. arXiv preprint arXiv:2202.08877 088771 2022a.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfactual links for link prediction. In International Conference on Machine Learning, pp. 26911 166922. PMLR, 2022b.
Tong Zhao, Xianfeng Tang, Danqing Zhang, Haoming Jiang, Nikhil Rao, Yiwei Song, Pallav Agrawal, Karthik Subbian, Bing Yin, and Meng Jiang. Autogda: Automated graph data aug- mentation for node classification. 2022c.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 11458-11448 1468. PMLR, 2020.
Chenyu Zheng, Guoqiang Wu, and Chongxuan Li. Toward understanding generative data augmen- tation. Advances in Neural Information Processing Systems, (6o544046-50060 2023.
Zhou Zhiyao, Sheng Zhou, Bochao Mao, Xuanyi Zhou, Jiawei Chen, Qiaoyu Tan, Daochen Zha, Yan Feng, Chun Chen, and Can Wang. Opengsl: A comprehensive benchmark for graph structure learning. Advances in Neural Information Processing Systems, 36, 2024.
Mengting Zhou and Zhiguo Gong. Graphsr: a data augmentation algorithm for imbalanced node classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp- 4954-4962, 2023.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1399-1407, 2019.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du Jieyu Zhang, Qiang Liu, Carl Yang, and Shu Wu. A survey on graph structure learning: Progress and opportunities. arXiv e-prints, pp. arXiv-2103, 2021.
Dongcheng Zou, Hao Peng, Xiang Huang, Renyu Yang, Jianxin Li, Jia Wu, Chunyang Liu, and Philip S Yu. Se-gsl: A general and effective graph structure learning framework through structural entropy optimization. In Proceedings of the ACM Web Conference 2023, pp. 499-510, 2023.
Daniel Zügner, Amir Akharnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847-2856, 2018
17

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL SETUP
A.1 BASELINE SETUPS
Since many of the baselines we selected are originally designed for static graphs, in this section, we outline how these methods adapted for dynamic graphs
Stochastic methods DropEdge. DropNode, and DropMessage belong stochastic dropping methods, which can be naturally integrated into the spatial modeling module of DyGNNs, as all three backbones use GNNs capture spatial correlations.
Mixup methods Graph Mixup two-stage approach. After fully training the original DyGNN, we freeze its temporal module and continue training the spatial module following the Mixup paradigm from Wang et al. (2021b).
Graph Structure Learning Both NeuralSparse and SUBLIME are graph structure learning meth- ods for GDA. For NeuralSparse, we initialize denoising network for each graph snapshot and co- train it with DyGNN. For SUBLIME, we ensure that both X1:r and A are visible to the model.
Graph Rationalization RGDA operates at both the graph and node levels. We apply its node-level augmentation independently for each snapshot and use pooling for Combinn((:)) in RGDA.
A.2 BASELINES NoT CHOOSED
We acknowledge that some classical or highly relevant GDA methods are included in our evalu- ation. This is primarily due to two main reasons:
Task specificity to graph-level tasks: Many graph rationalization methods designed clusively for graph-level tasks, including DIR (Wu et al., 2021), GREA (Liu et al., 2022a), GraphAug (Luo al., 2023), DCT (Liu et al., 2024b), AIA (Sui al., 2024), and C2R (Yue et al., 2024a). Thus, they were not selected for our evaluation.
Limited to static graphs: When adapting static GDA methods to dynamic graphs, faced considerable difficulties, especially with approaches that are inherently designed for individual graphs. For instance, GAUG-O (Zhao et al., 2021b) perturbs the original graph to generate K perturbed graphs, which causes issues for DyGNN's temporal module when aggregating across different snapshots, it cannot determine which perturbed snapshot to select. Consequently, had to exclude several classical yet incompatible GDA baselines, such as Graph Transparent (Park al., 2021), AutoGDA (Zhao et al., 2022c) and FLAG (Liu al., 2022c).
B SUPPLEMENTARY EXPERIMENT RESULTS
B. RESULTS FOR RQ3
In Figure 7, we present the performance comparison of various GDA methods under a feature attack, where Gaussian noise is added node features, Similarly, Figure 8 shows the performance comparison under the Nettack.
B.2 RESULTS FOR ABLATION STUDY
To further compare the impact of different environment augmentation strategies within DyAug, we designed three variants: using only spatial replacement, using only temporal replacement, and using only spatial-temporal replacement. The results, as shown in Table 4, demonstrate that the variant with only spatial-temporal replacement closely approximates the performance of the full Dy On the Yelp and ACT datasets, Ay (spa.) exhibits significant performance drop, which is likely due to the longer edge timespans in these datasets (as shown in Figure 4), indicating a higher need for temporal augmentation.
18

---

Published as a conference paper at ICLR 2025
90
before feature attack
after feature attack
79.6
79.8
79.8
79.6
78.1
80.7
80.3
81.4
82.3
AUC (%)
63-5
61.2
624
64.6
58.4
59.3
59.0
40
Vanilla
+DropEdge
+DropNode
+rropMessage
+GraphMixup
+NeuralSparse
+SUBLIME
+RGDA +DyAug (Ours)
Figure The performance comparison of various GDA methods under feature attack on DYSAT+YELP.
before NETTACK
after NETTACK
85
79.6
79.8
79.8
79.6
80.7
80.3
81.4
82.3
78.1
AUC (%)
72.6
70
67-4
68..0
65
63.8
65.7
644-3
65_1
63.7
61.2
60
Vanilla +DropEdge +DropNode +DropMessage +GraphMixup
NNeuralSparse
+SUBLIME
+RGDA
+DyAug (Ours)
Figure& 8: The performance comparison of various GDA methods under Nettack on DySAT+YELP.
Table AUC score (%) DyAug and variants equipped with different augmentation strategies on real- world datasets. We select DYSAT as the backbone. (lem.), (spa.), and (spa-tem.) denote the configurations where only temporal replacement, only spatial replacement, and only spatial-temporal replacement are applied.
Model
COLLAB
Yelp
Bitcoin
ACT
DyAug
0.8925 0..004
0..033.0.0043
0.7860110.00
DyAug (tem.)
0.8923-0.0047
0.8217=000047
0.8960=000052
0.7869+000000
DyAug (spa.)
0.8841 0.0050
0.8193110.006
0.8938.10.0022
0.7725110.0433
DyAug (lem-spa.)
0.8937
0.0005
0.9079110.008
0.7810110.0022
In addition, Tables 5 and 6 provides supplementary ablation studies under the scenarios of distribu- tion shift, feature attack, and Nettack.
B.3 RESULTS FOR SENSITIVITY ANALYSIS
To provide more comprehensive evaluation of DyAug, have included sensitivity analysis the window size w using the COLLAB and Yelp datasets, as shown in Table
It can be observed that DyAug performs consistently well when E 4), while for 8, there a notable performance drop on the COLLAB dataset (1.50% 1 compared to w = 2). We attribute this to the overly large window size, the COLLAB dataset consists of only 16 snapshots. With such a large window, the majority the dynamic graph sequence considered as "positive pairs," rendering Lar ineffective. Therefore, have fixed 2 for all subsequent experiments.
19

---

Published as a conference paper at ICLR 2025
Table 5: Ablation study under distribution shift. The backbone is GRCN, and the dataset is COLLAB.
Variant
DyAug
DyAug w/o TC
DyAug w/o RA
DyAug w/o CR
DyAug w/o CL
ROC-AUC
73.22
72.76
70.58
73.08
72.70
Table 6: Ablation study under topological attack and Nettack. The backbone is set as GRCN, and the dataset
ACT.
Variant
DyAug
DyAug w/o TC
DyAug w/o RA
DyAug w/o CR
DyAug w/o CL
Feature attack
72.35
69.58 72.05
65.18
70.51 70.95
Nettack
74.68
71.41
74.36
73.05
Table Sensitivity analysis on parameter w with GRCN backbone.
Dataset
COLLAB
Yelp
2
0.8495 + 0.0070
0.6795 + 0.0204
0.8506 = 0.0082
0.6785 = 0.0139
0.8469 = 0.0069
0.6732 + 0.0188
0.8345 + 0.0112
0.6690 + 0.0228
B.4 RESULTS ON LARGE-SCALE GRAPHS
We extended our experiments to include a large-scale dynamic graph dataset, DGraphFin (Huang et al., 2022), using the slicing and data splitting strategy outlined in (Feng et al., 2024). This dataset comprises 4,889,537 nodes and 4,300,999 edges, as detailed in Table 8. We believe this benchmark effectively tests DyAug's scalability.
Table 8: Dataset characteristics.
Dataset
COLLAB
Yelp
Bitcoin
UCI
ACT
DGraphFin
#Nodes
23,035
13,095
5,881
1,899
20,408
4,889,537
#Edges
151,790
65,375
35,591
59,835
202,339
4,300,999
#Time steps
21
13
We evaluated DyAug's performance on DGraphFin using DySAT as the backbone model, as shown Table From Table we can conclude that DyAug seamlessly scales to ultra-large graphs. Graph structure learning methods like NeuralSparse and SUBLIME impose substantial GPU memory de- mands with marginal or even negative performance gains (2.46% J for NeuralSparse). Rule-based augmenters such as DropEdge and DropNode introduce negligible computational overhead but fail deliver notable performance gains, consistent with the findings in Table 1. DyAug, however, achieves 1.72% AUC improvement with additional GPU memory burden of less than 2 GB, demonstrating its exceptional scalability.
B.5 RESULTS ON TD-PGD ATTACKS
We conducted additional experiments to evaluate DyAug under the more advanced attack method TD-PGD Sharma et al. (2023), as shown Table 10. The results demonstrate that DyAug maintains strong robustness even under TD-PGD attacks. Notably, mance improvement of 0.14% when applied on DUCA What's more, DyAug demonstrated significant robustmess the DASAT+ACT setting under the TD-PGD attack. proved the attacked performance from 68, 68.53% to 74.90% at e = 0.3, achieving a remarkable 6.37% gain, which we believe serves compelling evidence of its resilience in more challenging scenarios.
0. Dy even achieves perfor-
successfully im-
20

---

Published as a conference paper at ICLR 2025
Table Results DOraphhFin+DySAA.. The implementation DySAT is from Amazon-TGL (https: //github. com/ amazon wwwp:oonnnniiinceggggee The results are reported on single NVIDIA Tesla A100 40G
GPU.
Metric
AUC (%)
Per-epoch time (s)
GPU Memory (GB)
Vanilla
73.26
47s
3.7GB
+DropEdge
72.69
43s
3,7GB
+DropNode
73.50
41s
3.7GB
+DropMessage
71.22
53s
3.7GB
+NeuralSparse
70.80
186s
17GB
+SUBLIME
73.15
147s
21GB
+RGDA
74.12
69s
6,9GB
+DyAug
74.98
56s
5.6GB
Table 10: Results tested with TD-PGD attack.
Data
Method
0.0
0.1
0.2
0.3
DySAT
0.750240.0056 0.7698=0.0063 0.7712=000080
0.7418+0.0092
0.7276+0.0143
0.7191=0.0129
UCI
+DyAug
0.7456+0.0120
0.7466=0.0174
DySAT
0.7790=0.00366 0.7698+0.0028
0.733440.0138
0.6853=0.0262
ACT
+DyAug
0.7860=0.0054
0.7834x0.0112
0,7682+0.0109
0.7490=0.0176
B.6 RESULTS WITH MORE ADVANCED DYGNN BACKBONES
To further validate the wide applicability of DyAug, we have incorporated two advanced DyGNN backbones, Roland You al. (2022) and SLATE Karmim et (2024). The experimental results are presented in Table 11. We observe that DyAug maintains excellent generalizability across these backbones, achieving 1.0% and 1.87% performance gain on Roland and SLATE,, respectively.
Table 11: Results the UCI dataset. Roland is implemented with Roland-GRU.
Backbone
Roland
SLATE ROC-AUC (%)
ROC-AUC (%)
Gain
Gain
Vanilla
79.53-L0.6122
81.26-10.3051
+DropEdge
79.25=00.822
-0.28
80.1240.4715
-1.14 J
+ +DropNode
79.29-0.6590
-0.24
80.59:10.3552
-0.67 |
+DropMessage
79.72+
+0.19
81.77+0.5819
+0.51
+GraphMixup
77.50+0.8911
-2.03
80.35+007400
-0.91
+NeuralSparse
79.86:10.4818
+0.33
81.75:10.421
+0.491 f
+SUBLIME
80.2340
+0.70
82.56110.306
+1.30
+RGDA
79.86-
+0.33
82.77:10.3593
+1.51 f
+DyAug
80.53+0.7318
+1.00
83.131002669
+1.87 1
21


Reviews:
[{"review_id": "fplyqH88Rh", "reviewer": "Reviewer_AF5m", "summary": "In this paper, the authors identify limitations in applying existing graph data augmentation (GDA) techniques to dynamic graphs. Through a detailed investigation, they reveal that these methods often degrade performance by disrupting temporal consistency within the graph structures. To address this challenge, the authors introduce DyAug, a graph data augmentation approach specifically designed for dynamic graphs. DyAug achieves this by partitioning the input graph into a \"rational\" component, which preserves essential temporal consistency, and an \"environmental\" component, which can be modified to enrich the training data. Building on this partitioning, they propose three replacement strategies to selectively augment the dynamic graph without compromising consistency. Experimental results demonstrate that DyAug significantly improves both the performance and robustness of dynamic GNNs.", "questions": "Here are some questions that may help strengthen the overall merit of the paper:\n\n1. Have you considered evaluating the proposed scheme on continuous-time dynamic graphs (CTDGs)? How do you anticipate the approach would perform on CTDGs compared to discrete-time settings?\n\n2. Could you provide insights into the scalability of your approach? Have you tested it on larger graphs, and if so, how does performance scale with increasing graph size? Additionally, what are the associated overheads?\n\n3. Could you share more evaluation results of the approach on recent models to provide a broader validation of its effectiveness? For instance, models such as TGAT [1], ROLAND [2], or DyGFormer [3]?\n\n4. Given that the adversarial attacks used in the evaluation are not the most advanced, do you plan to test your approach against state-of-the-art adversarial attacks, such as [4]? How do you anticipate your method would perform in these more challenging scenarios?\n\n[1] Xu, Da, et al. \"Inductive representation learning on temporal graphs.\" arXiv preprint arXiv:2002.07962 (2020).\n\n[2] You, Jiaxuan, Tianyu Du, and Jure Leskovec. \"ROLAND: graph learning framework for dynamic graphs.\" Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2022.\n\n[3] Yu, Le, et al. \"Towards better dynamic graph learning: New architecture and unified library.\" Advances in Neural Information Processing Systems 36 (2023): 67686-67700.\n\n[4] Sharma, Kartik, et al. \"Temporal dynamics-aware adversarial attacks on discrete-time dynamic graph models.\" Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has the following strengths:\n\n- The authors focus on emerging dynamic graphs, a format increasingly common in real-world applications, making the approach highly relevant.\n\n- The proposed approach is well-founded and effectively enhances the resulting model's performance and robustness.\n\n- The authors thoroughly compare various existing GDA methods, demonstrating significant improvements in outcomes.", "weaknesses": "The paper has the following weaknesses:\n\n- The proposed scheme's effectiveness is not evaluated on continuous-time dynamic graphs (CTDGs), which are also crucial in dynamic graph learning.\n\n- The scalability of the approach is not thoroughly assessed, leaving uncertainty about its performance on larger graphs.\n\n- The dynamic GNN models used in the evaluation are relatively outdated, potentially limiting the generalizability of the results.\n\n- The adversarial attacks used for testing the approach are not as advanced as state-of-the-art methods, which may affect the robustness evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kxCUTJnHt9", "reviewer": "Reviewer_uP12", "summary": "This paper introduces DyAug, a novel framework designed to enhance dynamic graph neural networks (DyGNNs) through graph rationalization and data augmentation, addressing the limitations of static graph augmentation methods when applied to dynamic graphs. DyAug utilizes temporal consistency-aware augmentation strategies to separate causal and non-causal graph components across time, leading to improved performance, generalization, and robustness against adversarial attacks and temporal distribution shifts. Extensive experiments demonstrate that DyAug consistently outperforms state-of-the-art methods.", "questions": "1. How does DyAug perform on large-scale dynamic graphs with millions of nodes and edges, especially considering the additional complexity introduced by rationalization and consistency regularization?\n2. The current focus is on discrete-time dynamic graphs. How challenging would it be to adapt DyAug to continuous-time dynamic graphs (CTDGs)?\n3. Could there be scenarios where the rationale-environment separation introduces new spurious correlations, and how can this be mitigated?\n4. How sensitive is the model's performance to the choice of window size $w$ in the consistency regularization loss, and does this affect the robustness of DyAug?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed DyAug framework extends GDA to dynamic graphs, a less explored area. It offers an innovative approach by focusing on maintaining temporal consistency, which is crucial for dynamic graphs.\n2. DyAug effectively maintains temporal consistency, ensuring that augmentations do not disrupt the natural evolution of dynamic graphs.\n3. DyAug introduces the concept of graph rationalization for dynamic GNNs, separating causal subgraphs from non-causal parts. This enables the model to learn more meaningful temporal representations.", "weaknesses": "1. DyAug introduces additional computational complexity from causal mask estimation, contrastive loss, and consistency loss, which could pose scalability issues for large graphs.\n2. While the paper includes comparisons with several GDA methods, some notable methods like DIR [1] and GREA [2] were excluded due to compatibility issues. This might make the performance comparisons less comprehensive.\n3. DyAug's augmentation techniques (spatial, temporal, spatial-temporal replacements) rely on heuristic selection strategies, which might not generalize well across all types of dynamic graphs.\n4. Although an ablation study is provided, it could be more exhaustive, especially in terms of testing the impact of different hyperparameters and rationale generation methods on diverse datasets.\n\n[1] Discovering invariant rationales for graph neural networks.\n[2] Graph rationalization with environment-based augmentations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uz9CBYJVkS", "reviewer": "Reviewer_7aTN", "summary": "This paper introduces a novel framework for dynamic graph data augmentation called DyAug, addressing a critical challenge in applying static GDA methods to dynamic graphs: maintaining temporal consistency across graph snapshots. By combining causal subgraph rationalization with environmental subgraph augmentation, DyAug performs augmentation across three dimensions: spatial, temporal, and spatiotemporal. Extensive experimental results demonstrate the effectiveness of DyAug.", "questions": "1. What are the limitations of dynamic graph augmentation methods targeting dynamic graph OOD, and what is the motivation to design DyAug under these previous methods?\n2. How does DyAug's approach to causal discovery and causal perturbation differ from that of existing dynamic graph OOD methods? A more detailed explanation is needed.\n3. Which component of DyAug ensures that its augmentation does not disrupt the temporal consistency of dynamic graphs, and why? This requires further clarification.\n\nFor details, please refer to the Weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper tackles the challenge of maintaining temporal consistency across graph snapshots, an issue that, according to the authors, has not been previously addressed. The approach of combining causal subgraph rationalization with environmental subgraph augmentation to enhance the graph from spatial, temporal, and spatiotemporal perspectives is some what novel.\n2. The paper demonstrates the performance, robustness, and generalization capacity of DyAug through comprehensive experiments.\n3. The paper is generally clear, with a structured presentation that facilitates understanding of the DyAug. The figures are particularly effective in illustrating key concepts, such as the causal and the proposed augmentation strategies.\n4. The significance of DyAug lies in its potential impact on the field of robustness dynamic GNNs.", "weaknesses": "1. The authors claim to be pioneers in exploring graph data augmentation (GDA) within dynamic graphs. However, several works on out-of-distribution (OOD) handling in dynamic graphs [1][2][3] have already incorporated augmentation strategies specifically for dynamic graphs. These works focus on enhancing the generalization ability of dynamic GNNs.\n2. In DyAug, a causal identification mask is constructed to separate rational and environmental factors, followed by disturbing the spurious factors to augment the dynamic graph, ensuring that the GNN learns the causal factors. However, this approach aligns closely with standard techniques in dynamic graph OOD works [1][2][3], which also focus on dynamic graphs.\n3. The paper argues that prior static graph augmentation methods overlook temporal consistency. However, it remains unclear how DyAug’s dynamic augmentation maintains this consistency. The authors only provide experimental evidence in Section 4.2 (Observation 1) to support temporal consistency. A more detailed explanation is needed to clarify which DyAug module specifically ensures that augmentation does not disrupt temporal consistency.  \n[1] Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift, NeurIPS 2022  \n[2] Environment-aware dynamic graph learning for out-of-distribution generalization, NeurIPS 2024  \n[3]Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts, NeurIPS 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VTWGBpBmqy", "reviewer": "Reviewer_nnH6", "summary": "This paper proposes a novel data augmentation method designed for dynamic graphs. Previous static graph data augmentation methods have shown poor performance on dynamic graphs, a phenomenon the authors attribute to the direct application of static graph augmentation techniques, which neglects the temporal consistency of graph structures. The authors introduce a learnable data augmentation method for dynamic graphs, incorporating a consistency loss function to ensure the temporal consistency of graph structures. Additionally, to enhance the performance of this data augmentation method in out-of-distribution generalization scenarios, the authors adopt a causal inference perspective to partition the original graph into rationale and environment subgraphs, thereby improving the algorithm's stability under data distribution shifts.", "questions": "1. The source code repo is expired.\n2. In section 3.4, the description of $\\overline{M}=1_N-M$ and the specification that $1_N\\in \\set{1}^{N\\times N}$ is an all-one matrix is somewhat perplexing. Given the typical sparsity of graphs, the transformation $\\overline{M}=1_N-M$ would result in a very dense matrix, thereby significantly increasing computation as the number of edges grows. This raises the question of whether the intended expression was $\\overline{M}=A-M$, where $A$ represents the adjacency matrix of the graph, rather than an all-one matrix.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors present a new data augmentation approach motivated by the intuitive notion of temporal consistency in graph structures, which consistently achieves favorable performance in dynamic graph tasks. Furthermore, this method demonstrates stable augmentation in scenarios such as adversarial attacks and out-of-distribution generalization, showcasing the robustness of the algorithm.\n2. The authors conducted extensive experiments based on various baselines, illustrating that this data augmentation method consistently provides enhancement across different baselines and scenarios.", "weaknesses": "1. The authors omitted ablation experiments in out-of-distribution generalization scenarios and adversarial attack scenarios other than structure attacks, which reduces the persuasiveness of the algorithm's effectiveness explanation.\n2. The complexity analysis presented in section 3.6. Specifically, during the computation of the consistency loss, the complexity associated with determining the similarity between two graphs is not constant. Instead, it is plausible that this complexity scales linearly with respect to the number of edges. Consequently, the overall complexity might be revised to $\\mathcal{O}(wT|\\mathcal{E}|)$.\n3. More recent works about dynamic graphs should be properly included in related works or compared as baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)