Adaptive Data Augmentation on Temporal Graphs
Authors: Yiwei Wang
Yujun Cai
Yuxuan Liang
Henghui Ding
Changhu Wang
Siddharth Bhatia
Bryan Hooi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Data Augmentation
Temporal Graphs
Graph Neural Networks

Abstract: Temporal Graph Networks (TGNs) are powerful on modeling temporal graph data based on their increased complexity. Higher complexity carries with it a higher risk of overfitting, which makes TGNs capture random noise instead of essential semantic information. To address this issue, our idea is to transform the temporal graphs using data augmentation (DA) with adaptive magnitudes, so as to effectively augment the input features and preserve the essential semantic information. Based on this idea, we present the MeTA (Memory Tower Augmentation) module: a multi-level module that processes the augmented graphs of different magnitudes on separate levels, and performs message passing across levels to provide adaptively augmented inputs for every prediction. MeTA can be flexibly applied to the training of popular TGNs to improve their effectiveness without increasing their time complexity. To complement MeTA, we propose three DA strategies to realistically model noise by modifying both the temporal and topological features. Empirical results on standard datasets show that MeTA yields significant gains for the popular TGN models on edge prediction and node classification in an efficient manner.

Adaptive Data Augmentation on Temporal Graphs
Yiwei Wang'
Yujun Cai²
Yuxuan Liang'
Henghui Ding?
Changhu Wang2
Siddharth Bhatia
Bryan Hooi'
National University of Singapore
Nanyang Technological University
3 ByteDDacce
wangyw_ hwtps/_seu@foomall.ooo com, [yujun001 ding00933 ntu. edu.
yuxliang@outlook. com, changhu. wang@gmail. com, {siddharth, bcooi .us. edu.
Abstract
Temporal Graph Networks (TGNs) are powerful on modeling temporal graph data based on their increased complexity. Higher complexity carries with higher risk of overfitting, which makes TGNs capture random noise instead of essential semantic information. To address this issue, our idea is to transform the temporal graphs using data augmentation (DA) with adaptive magnitudes, so as to effectively augment the input features and preserve the essential semantic information. Based on this idea, we present the MeTA (Memory Tower Augmentation) module: a multi-level module that processes the augmented graphs of different magnitudes on separate levels, and performs message passing across levels to provide adaptively augmented inputs for every prediction. MeTA can be flexibly applied the training of popular TGNs to improve their effectiveness without increasing their time complexity. complement MeTA, we propose three DA strategies to realistically model noise by modifying both the temporal and topological features. Empirical results on standard datasets show that McTA yields significant gains for the popular TGN models on edge prediction and node classification in an efficient manner.
Introduction
Many real-world graphs are not static but evolving, where every edge (or interaction) has a timestamp to denote its occurrence time. These graphs are called temporal (or dynamic) graphs 39 Recently,
temporal graph networks (TGNs) 25 39 16 have been proposed support learning on temporal graphs. Advanced TGNs utilize an RNN based memory module to represent node's 's history as compact state (see Fig. [ which used predict node's 's activities (28). TGNs are capable of making predictions from complex graph topology and temporal information. thanks to their advanced representational power. However, the increased representational capacity comes with higher model complexity, which induce over-fitting and weaken their generalization ability. In particular, trained TGN may capture random noise instead of semantic information, which is not desired [41].
To combat over-fitting, data augmentation (DA) has been demonstrated to be effective 23 Nev- ertheless. DA for the temporal graphs remains under-explored, of which the main challenges lie in highly irregular dynamic topology. DA applies transformations to input features so to model realistic noise for enriching the input data. The magnitudes of the transformations, known as DA magnitudes, controlled by the input features before and after DA (5). Existing work on image and text data devises adaptive methods, which apply higher DA magnitudes to the less informative parts of input features, in order to effectively augment the input features while preserving the essential semantic information [38).
which is positively related to the difference between
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In order to design such an adaptive DA method on temporal graphs, we consider the informativeness of edges to a target node in terms of both time and topology when predicting the activities of the target node. On the time axis, more recent edges tend to be more informative for predicting the target node's s states than the earlier ones. For example, when a girl is going to watch a movie in the evening, the interaction between her and cinema conductor a few minutes ago is much more informative to predict her behaviors than the academic discussion between her and a student in the morning. Similarly, in terms of topology, the edges directly connecting the target node provide more important information than edges few hops away. Overall, the edges that are closer to the target node in time or topology tend to provide more important information, validated in the existing work (25).
To devise an efficient adaptive DA method for temporal graphs, the central idea of this paper is to generate a few graphs with different DA magnitudes, and perform the message passing between these graphs to provide adaptively augmented inputs for every prediction. We encapsulate this idea in a novel module, called MeTA (Memory Tower Augmentation): Me'TA stacks a few levels of memory modules as tower with weight sharing. where lower levels process the graphs of lower DA magnitudes (see Fig. 2 MeTA includes two message passing mechanisms across levels for adaptive DA. The first one is cross-level propagation, which propagates the features between nodes across levels, while the second one is memory transition, that transmits memory states of a node from higher levels to lower ones periodically. This design allows us to achieve the goal of adaptive DA, since for every prediction, the edges closer to the target node in time or topology corresponding to lower magnitudes, as demonstrated by the theoretical analysis (see Sec. 3.4).
placed on lower levels
To complement MeTT,, we propose three DA strategies augmenting both the temporal and topology features: (i) perturbing the edge time to simulate time shifts, (ii) removing edges, and (iii) adding edges to modify the topology. Our strategies effectively enrich the input data by modeling realistic noise intuitively and theoretically. MeTA is a general module that can be applied for training popular TGNs to enhance their performance. MeTA improves the effectiveness of TGNs without increasing their time complexity during training, as analyzed in Sec. 3.4 Note that our methods do not induce any extra inference cost since DA is not applied during inference.
We evaluate our McTA on edge prediction and node classification tasks using the standard temporal graph datasets: Reddit [3 Wikipedia (20). MOOC [16]. We measure its performance through the metrics: test accuracy, average precision (AP), and the area under the ROC accuracy curve (AUC), under inductive and transductive settings. Overall, MeTA achieves substantial improvements for popular TGN models 25 39
and enhances them to outperform the baseline methods.
2 Related Work
Although many methods have been proposed for representation learning on static graphs 24
[0 22 27
[8 32 34 (3)) the work on representation learning in temporal graphs is much sparser. There exist two main classes of temporal graphs: discrete-time dynamic graphs (DTDG) [17] and continuous-ting time dynamic graphs (CTDG) (25). DTDG are sequences of static graph snapshots taken at intervals in time, while CTDG can be represented as timed lists of events. Representation learning on CTDG is more flexible, general and challenging, which is the focus of this paper. Early models for 1
8 40) Some recent work addresses the learning 30 based on the increased model complexity. For example, [I proposes a temporal graph learning model based on causal anonymous walks, which uses RNNs to encode the temporal information. Our method is orthogonal to these work the sense that we do not propose a new TGN model, but acts as general DA module that can be flexibly incorporated into the training of popular TGNs to improve their effectiveness.
temporal graph learning focus on DTDGs [1] 17
on CTDGs [6]] 28 25|
39
Data augmentation plays a central role in training neural networks, of which the effectiveness has been validated on image data 42 26 77. On the data augmentation for the static graph data, 35
proposes NodeAAg to augment and utilize the unlabeled data in semi-supervised learning, and 33
crops the subgraphs to augment the input features for the static graph classification. In [37], the authors propose the Mixup methods for static graphs, which interpolate the input features of both nodes and graphs in the semantic space as data augmentation. Different from them, our work focuses on the DA for temporal graphs. Our MeTA considers the edge importance related to the temporal and topology information and adaptively augment temporal graphs in an efficient manner, while our DA strategies effectively augment both the temporal and topological features.
2

---

prediction
prediction 2
old target
new target wode's state
node's s state
memmory
memcyy
memocyy
edgo
odge
odge
odge faature
neighbor stato
temporal graph
edges time order
feature propegation
Figure I: TGNs feed edges in time order into an RNN-based memory module, which updates nodes' states for predictions. Every time an edge connecting the node i happens, the memory module takes the i's state, edge feature, and the connected neighbor's state as the inputs, and update the state of node i (see Eq. In this way, the memory state of node i represents i's history.
3 Methodology
In this section, we propose MeTA (Memory Tower Augmentation), an adaptive data augmentation (DA) approach for improving the temporal graph learning. A McTA module can be applied to popular TGN models, and trains them with DA to improve its inference performance. McTA includes two message passing mechanisms: cross-level propagation and memory transition, to provide adaptively augmented inputs for every prediction, as demonstrated by the theoretical analysis.
To complement MeTA, we propose three DA strategies for augmenting temporal graphs by modifying the temporal and topological features, which effectively model the realistic noise to enrich the input data intuitively and theoretically. Using our methods enhance the popular TGNs does not increase their time complexity and does not induce any inference cost.
3.1 Preliminaries
In temporal graph G. interaction between nodes and is denoted temporal edge (t), 0, where e is the edge attributes (25), and is the edge time. t = 0 is generally the time of starting observations.
Advanced TGN models utilize memory module to store and update the (memory) state (t) of node i (see Fig. [ The state of node is expected to represent i's history in compressed format. Given the memory updater as mem, when an edge e.ş (t) connecting node is observed, node i's state is updated as:
s; (t) (s, e,, (t)lss
(1)
where s,(t") is the memory state of node just before time t, || is the concatenation operator, and node j is i's neighbor connected by e.y (t). s, (t) is initialized to 0 values and not changed until the next edge involving node i happens. Edge feature ety(t) and neighbor state Sy are concatenated
as the input update s; (t). .. All edges are fed to the memory modules in time order (see Fig. D..
The implementation of mem varies slightly for different TGN models, of which a common component is recurrent neural network (RNN) such LSTM [12) GRU (4). TGNs make the prediction for node at time using s, (t ), instead of (t), since when making predictions for time f, the interactions time have not happened and cannot be observed.
The number of hops used denote the distance on the topology 22 From Eq. I we observe that the edges connecting node directly contributes to i's state, while the edges, that are multiple hops away from i, have their features propagated node through i's neighbors' states.
3.2 Memory Tower for Adaptive Data Augmentation Temporal Graphs
Data augmentation (DA) aims at creating novel training data by applying transformation to input features (38). The magnitudes of the transformations, known as DA magnitudes, are controlled by the hyper-pane parameters, which is positively related to the difference between the input features before and after DA [5]. effectively augment the input features while preserving the essential semantic information, adaptive DA methods apply low DA magnitudes to the informative parts of the input features and higher magnitudes to the less informative parts [8). For example, TF-IDF based word replacement, a DA method for natural language processing, is designed to remove less important

---

prediction
lower
old target
new target node's staius at level 1
magnitide
level
momory
memory
node's status level
edge
memory
edge
memory time
temporal graph
transition
higher
level
memery
memoory
edge feature
neighbor state at level
magritude
edue
edge
at level
data augmentation
edges in time order
time
cress-level propagation
Figure Our MeTA method with two levels of memory modules. The colors denote the DA magnitudes, i.e., 'green' means lower, and 'yellow' means higher. With the memory transition from level 2 to level I, for every prediction, the earlier edges hold higher DA magnitudes. By propagating the neighbors' states from higher levels, more distant edges on topology hold higher DA magnitudes.
keywords with higher probability 38 This helps the model to generalize better to changes in the uninformative features, and effectively encode the essential features into the representations.
In a temporal graph, when predicting the activities of a target node, different edges are of different informativeness for the target node. For example, an engineer is busy doing a project in the evening. the interaction between him and his colleague a few minutes ago is much more important for predicting his working status than the discussion between him and his daughter on new movie in the morning, Similarly, the edges directly connecting the target node tend to be more informative than the ones that are multiple hops distant since the former directly happen on the target node. Overall, if an edge is more close to the target node in terms of time or topology, it is more informative, as validated in (25].
Applying adaptive DA magnitudes to edges of different informativeness is not trivial, since an edge's informativeness changes with different predictions, i.e., when making predictions for different target nodes, the distance from an edge to the target node changes. A simple method for adaptive DA is to separately augment the graph with adaptive magnitudes for every prediction, which leads different input graphs for different predictions. Therefore, this method repeats feeding the graph edges to the model from the beginning time for every prediction, and is named the refeed method.
Existing work [25 28, 16 trains the memory module in a recursive manner for efficiency, i.e., the as inputs, as shown in Fig. [ since
predictions at time take the former output at time (VT there is no DA and different predictions share the same input graph. The refeed method is much less efficient than recursive training, since in the former one, the memory states before the prediction time have to be recomputed for every prediction, while the number of predictions is generally the same as the number of edges during training, which is large value in practice [16).
We propose the Memory Tower Augmentation (MeTA), which offers appropriate DA magnitudes for every prediction in an efficient manner. MeTA stacks L levels of memory modules as a tower with weight sharing. For level I (1 1, ..... L). augment the graph G as G()) with the magnitude pr- It increases as increases, so that the DA magnitude higher at higher level. Denote the state of node at time t on level l as (()) and the edge connecting nodes and j time on level I, i.c.
belonging to ((), as eij (t). We feed edges at all levels in time order to the memory module, and always make the prediction using the memory states at the first level, i.c., (t).
McTA includes two message passing mechanisms across levels to offer adaptive DA for every prediction: cross-level propagation and memory transition. With cross-level propagation, when (1) observing edge eij (1) involving node at level I, node i's state at level / is updated as:
s (1) (t) mem (t e.e ( (min((+1.1)))
(2)
In this way, the edges that are more distant to the target node in terms of the topology are augmented at a higher magnitude, since their features are propagated to the target node through the neighbors' states (min((+ I,L)) (L-) that are located higher levels (see Proposition
In addition the distances on the topology, the time distances also influence the edge's informative- ness. Hence, the second message passing mechanism design is the memory transition for nodes'

---

Algorithm Memory Tower for Adaptive Data Augmentation on Temporal Graphs
Original Temporal Graph with the node set V and the edge sequence E in time order with timestamps: f1,..., it (0 I f I .... I fy), where is the number edges, a TGN model with the memory module mem, nyper-parameters L for the level number, T for the memory transition period, and the augmented graphs at different levels G 1,...,. ,L Output: The predictions made by the TGN model on time f1....,tt ,,: {p(tz)] = 1, ,,.
Input:
1: Initialize states s, (0), = 1,... L, Vi V, counter values c₁ Vi E V, starting time ty to O.
2: for +- to N do
3: (ly((n) f E/n] (the nith element in E)
4: We order the edges from g I l,.... between fx-1 (inclusive) and in as a sequence
En with timestamps T...... TN, (f T S S TN tn).
5:
for n' 4 to Nn do
6:
kkm (Tw) + En [n''] (the n'th element in E,,)
(1)
Sg (Tw)) t mem Sk (T,..) kkm (Twe) [|sm (min((+1.L))
(!)
7:
8:
Sm (T,7) f mem Sm (T,)) e (T,))
(1)
[|sk (minlI+1.L))
9:
end for
10:
Make prediction pf...) related to edge cit (t.) through states on time t at level 1. for in {i.j} do
11:
12:
Co f- Co +
13:
if c, 2 T then
14:
for - 1 to L do
15:
So (1,)) < So [1+1)
(t,))
16:
end for co 0 0
17:
18:
end
19:
end for
20:
end for
states from higher levels to lower ones, i.e., replacing the level-/ states with the level-l + ones:
! (1+1)
= (t)
The transition is made in the memory tower periodically, so that when we make a prediction at level the more recent edges contributing the prediction are at lower levels corresponding lower DA magnitudes (see Proposition 2). We determine the transition time of node by implementing a counter for node i, which is initialized 0 and increments when the model makes a prediction related to node i. If the counter reaches T, we reinitialize the counter and perform this memory transition for node where T is tyyper-paramed for the transition period.
Overall, we visualize our MeTA method Fig. 2 and summarize to obtain the predictions from memory states and calculate the training loss differ slightly for the specific TGN models and downstream tasks, of which the details can be found in the corresponding
Alg. 1 (see Appendix). How
work [16] 28 25
3.3 Data Augmentation Strategies
We propose three DA strategies for the temporal graphs: (i) perturbing time; (ii) removing edges; (iii) adding edges with perturbed time. The first one augments the temporal features; the second is for the graph topology, while the last augments both the topology and temporal features. The search space for the hyper-parameters of DA magnitudes is large if we set the parameters separately for different DA techniques. Hence, for the convenience of setting the hyper-parameters we use a unified hyper-paranee parameerr p control the magnitude of all the three DA strategies. A higher value of implies a larger magnitude. Next, we introduce our DA strategies in detail.
Perturb Time Each edge has timestamp to denote its happening time. In practice, these timestamps may not precise. For instance, courier can report delivery time earlier or later than the actual time. These time shifts widespread in the real world but do not necessarily affect the semantic
5

---

information. Hence, we perform time perturbation to model this kind of noise as data augmentation. Denote the average intervals between interactions as and the time range of training data [o, Taax] We add Gaussian noise following 7 ~ (00 a²) [2] to the edge time / as nnw = T + I, where knew is the augmented timestamp. We set the standard deviation of Gaussian noise a as 10pi. When p is O, all increases. The augmented time nnw can exceed the time range [max]. This is not practical since only the observations in the set tnew
edges' time is not changed, and the noise's s standard deviation grows
range [0, max] can be observed. Therefore, all the augmented time nnew all in the valid range [0, [. This design also helps us to retain the original distribution of edges' happening time after DA (see Theorem [].
if + t > T max or r + < 0, so that
Remove Edges Removing edges models the realistic noise that some edges may be missing in the data collection. For example, researcher can communicate with hundreds of other researchers one year. Collection of these interactions may have omissions, and it is unnecessary to consider all interactions to predict the researcher's state. A satisfactory TGN model is desired to effectively encode the essential semantic information even in the presence of this noise. We set the probability of removing edge as With higher p. edges are more likely to be removed and the augmented graphs tend to be more incomplete.
Add Edges with Perturbed Time A node can repeat interacting with its neighbor. An engineer, for example, repeats communicating with his colleague to check the project progress, and he talks with a waiter several times to order more food during dinner. We add the edges with the perturbed time model noise from interaction repetition. Denote the edge set of the original graph as E. We uniformly sample the edges from with replacement with the budget P#t to form & and then perturb the time of edges in introduced earlier, where #E is the cardinality of E. We add the edges in & for DA. Higher p corresponds to more edges being added.
3.4 Analysis and Discussion
We analyze how our MeTA and DA techniques work for temporal graph learning. Recall that if an edge is more distant to a target node on either topology or time, is less important or informative to predict the target node's s properties and thus we are expected to apply higher DA magnitude to it. Next, we provide theoretical analysis to show that our methods meet this expectation. The proof is provided in Appendix.
Proposition 1 (Effect of topology). If edge km (T) contributes the node state s, (t), and the distances from nodes k and m to i are equal to or larger than h hops in graph G. we have the level of edge km (T): 1 2 min (h + 1, I.) and the time < t,, where L, is the number of levels.
(1)
Proposition | limpies that the edges more distant to the target node on the topology must be on levels of higher I, and thus of higher DA magnitudes. In addition to the topology, we provide the following proposition to illustrate the effects of the temporal distances.
(1a) (l1) (T)) and eik (12) connect node i and directly contribute Proposition 2 (Effect of time). eeeges 0j to the node state s;(() Eq. (2). we have 1 1,,71 < < t when < holds, and 1, S 12, To T < I holds with Ti > 72.
Proposition 2 shows that the earlier edges tend to be on levels of higher 1, and thus of higher DA magnitudes.
Next, we analyze how our DA strategies retain the original temporal graph characteristics to model realistic noise. Many social and natural activities follow the Poisson process [19] 13 6). Denote the time range of the training data as [0, m. Our data augmentation includes the perturbations on the edge time. If nodes" interactions follows a Poisson process, we provide the following theorem to show that our DA techniques do not change the distribution of edge time.
Theorem 1. If the edges before data augmentation follow a homogeneous Poisson process, our data augmentation does not chunge the distribution of any edge's 's occurrence time.
Theorem 1 illustrates the benefits of our strategies for time perturbation. Otherwise, if the original distribution is broken, the augmented edges cannot reflect the realistic condition and may degrade the TGNs' generalization. In addition to the time distribution, we provide the following proposition to

---

show the expected edge number does not change after our DA. Denote the edge set of the original graph G as & and that of the augmented graph g()) as g(0.
Proposition After our data augmentation, the expected edge number is the same as that before data augmentation for any data augmentation magnitude, i.e., B[#E(0)= = #E, Vpi E [0, 1] holds.
This proposition shows that our data augmentation does not change the density of interactions in expectation, which meets the realistic condition and does not induce extra computation load.
We analyze the time complexity of training TGNs and McTA with respect to the input data. Denote the number of interactions as # the node number #V, and the dimensionality of the input features as d. Since the RNN based memory module updates memory states with every edge and make predictions in recursive manner, the time complexity of the memory module is Od #E). The refeed method introduced in Sec. 3.1 achieves adaptive DA by feeding the input data from the beginning time the prediction time into the memory module for every prediction. The corresponding time complexity is:
#E-1 0 de
# -
(4)
which is much higher than the complexity of original TGNs.
Our MeТА method stacks L levels of memory modules. On level the time complexity is O(d+#E(1)) where g() is the edge set of the augmented graph go) on level I. Summing the complexity of all levels up leads Σ/. 1 d- #E of which the expectation is
o ( Σ d #E = o (E R(#E = =o d. #8 OF
= Od##8),
(5)
which is same the original TGNs. The second equation holds because of Proposition while the last equation holds because I. is a small constant value invariant to the input data, and we find that L generally exhibits satisfactory performance. Compared to the refeed method, our MeTA achieves the adaptive DA with much lower complexity during training. During inference, our MeTA method does not lead to any extra computation load since DA is not applied then.
4 Experiments
In this section, we present the performance of TGN models implemented with our adaptive DA method. We compare our method against variety of strong baselines on the task of edge prediction and node classification on temporal graphs. Our experimental settings closely follow those of the previous work 225
39 30 to ensure fair comparison. To avoid violating temporal constraints, we make predictions that strictly take place after all observations. As for the evaluation metrics, we follow [39 30] to use average precision (AP) and accuracy in the edge prediction tasks and employ the area under the ROC accuracy curve (AUC) for node classification [16].
We use three standard temporal graph datasets: MOOC [16], Reddit [3). and Wikipedia [16] for evaluation. The statistics of these datasets are shown in Table T We use a chronological train-
validation-test split with a ratio of 70%-15%-15% following 25 39
For the hyper-parameters of baseline methods, e.g., the number of hidden units, the optimizer, the number of sampled neighbors. and the learning rate, we set them suggested by their authors. For the sapeee-rrameterss of our MeTA, we set the number of memory levels as = 2, the data augmentation magnitudes P1 = 0.1, P2 0.8. and the memory transition period as T' = 10. by default. Note that these settings are fixed for all experiments unless specifically indicated to be changed. Setting more levels with L. >> 2 offers higher granularity for DA magnitudes, but find that L generally offers satisfactory performance.
4.1 Edge Prediction
Following
we conduct experiments for edge prediction under both transductive and inductive settings for comprehensive evaluation. In the former one, we predict edges connecting the nodes observed during training, and in the latter predict edges for the unseen nodes (25).
39
25
7

---

Table 1: Statistics of the datasets used in our experiments. Edges refer to temporal edges.
Dataset
#Nodes
# #Edges
#Nodes in val./test.
#Edges in val./test.
Nodes' label type
MOOC
7,144 10,984
411,749 672,447
2.599/2.412
61.762/61,763 100,867/100,861 23,621/23,621
course dropout posting ban
Reddit
9,839/9,615
Wikipedia
9,227
157,474
3,256/3.564
editing ban
Table 2: Test accuracy and average precision (AP) of transductive edge prediction. We conduct 100 trials with random weight initialization. Mean (%) and standard deviations are reported. The best results in each column are highlighted in bold font.
MOOC
Reddit
Wikipedia
Method
Accuracy
AP
Accuracy
AP
Accuracy
AP
CTDNE 21
65.34 + 0.7
74.29 + 0.6
73.76 = 0.5
91.41 + 0.3
79.42 0.4
92.17 + 0.5
JODIE 16
76.45 + 0.6
83.87
0.4
90.91 = 0.3
97.11 + 0.3
87.04 0.4
94.62 = 0.5
TGAT 39
75.20
+ 0.4 82.66
92.92 = 0.3
98.12 +
8.214
95.34 0.1
DyRep 128
73.36 0.4
92.11 = 0.2
97.98
87.77 0.2
94.59 + 0.2
TGN 251
81.38
89.79
92.56 0.2
9..
89.51 1
98.46 - 0.1
DyRep + Me'TA (Ours)
76.21 0.4
84.18 +.18+00..
93.04 + 0.3
98.62 0.1
88.92 + +.2
95.63 + 0.2
TGN MeTA (Ours)
83.84 + 0.5
92.03 + 0.3
94.19 0.2
99.08 + 0.1
91.34 0.3
98.87 = 0.1
Table 3:
Test accuracy and average precision (AP) of inductive edge prediction. We conduct 100 trials with random weight initialization. Mean (%) and standard deviations are reported. The best results in each column are highlighted in bold font.
MOOC
Reddit
Wikipedia Accuracy
Method
Accuracy
AP
Accuracy
AP
AP
16 JODIE
75.79
0.5
83.44
0.6
88.34 = 0.9
94.36 + 1.1
84.32 + 0.4
93.11 + 0.4
TGAT 39
74.02 + 0.3
80.84 + 0.5
90.73 = 0.2
96.62 + 0.3
85.35 + 0.2
93.99 = 0.3
DyRep 28
72.92 + 0.4
80.36 + 0.4
89.60 = 0.2
95.68 + 0.2
83.46 + 0.3
92.05 + 0.3
TGN
25
80.73 + 0.2
89.21 0.3
91.62 = 0.1
97.55 + 0.1
88.60 + 0.2
97.81 + 0.1
DyRep + MeTA (Ours)
75.89 0.4
82.56 1 0.3
90.52 = 0,2
96.59 + 0.2
85.67 1 0.3
94.13 - 0.2
TGN + MeTA (Ours)
83.47 1 0.2
90.85 0.2
92.96 = 0.1
98.17 + 0.1
90.82 + 0.2
98.26 - 0.1
For transductive edge prediction we take the state-of-the-art approaches for representation learning on temporal graphs: CTDNE (1,, JODIE [16]. DyRep (28, TGAT [39], and TGN (25 as
baselines for comparison 339 We conduct the experiments for 100 trials with random weight
initialization. We implement McTA with the TGN models DyRep and TGN, Table T reports the results. Our McTA improves the test accuracy of DyRep by 3.9% on MOOC, 1.0% on Reddit, 1.3% on Wikipedia, and TGN by 3.0% on MOOC, 1.8% on Reddit, 2.0% on Wikipedia. As result, our MeTA achieves substantial improvements for DyRep and TGN.
In the inductive setting, we keep the baselines which support inductive learning for comparison. We conduct the experiments for 100 trials with random weight initialization. The results are reported in Table We implement our MeTA with DyRep and TGN to study whether MeTA can improve the performance of TGNs under the inductive setting. We observe that MeTA improves the test accuracy of DyRep by 4.1% on MOOC, 1.0% on Reddit, 2.6% on Wikipedia, and TGN by 3.4% on MOOC, 1.5% Reddit, 2.5% Wikipedia. As result, our McTA method enhances DyRep and TGN to outperform the baseline methods in the inductive task.
Given the TGN models DyRep and TGN, our MeTA achieves consistent and substantial improvements on all datasets, thanks the adaptive data augmentation offered by our MeTA method. MeTA effectively augments the input features while preserving the essential semantic information, which reduces the noise on more informative parts of the input features and increase the diversity of data augmentation on less informative parts with adaptive data augmentation magnitudes. Overall, the results above indicate that our methods are effective in improving the effectiveness of the popular TGN models in both transductive and inductive settings.

---

4.2 Node Classification
The task of node classification on temporal graphs is to predict the time-varying labels of nodes [[)].
Table 4: ROC AUC (%) on the test set for temporal node classifi- cation. We conduct 100 trials with random weight initialization. Mean (%) and standard deviations are reported.
Table reports the test ROC AUC.
We observe that MeTA improves
Method
MO0C
Reddit
Wikipedia
ROC AUC of DyRep by 2.1% % on MOOC, 2.3% on Reddit, 2.4% on
CTDNE 21
67.54 0.7
59.43 + 0.6
75.89 + 0.5
JODIE 16
76.31 + 1.6
61.83 + 2.7
84.84 + 1.2
Wikipedia, and TGN by 2.2% on
TGAT 39
74.25 + 0.9
65.56 + 0.7
83.69 + 0.7
MOOC, 2.0% on Reddit, 2.5% on Wikipedia. As a result, our MeTA method enhances DyRep and TGN to outperform the baseline meth- ods in the temporal node classifica- tion. This validates the importance
DyRep 28
75.32 +: 1.3
62.91
2.4
84.59 + 2.2
TGN 25
77.73
0.7
67.06 1 0.9
87.81 + 0.3
DyRep MeTA (Ours)
76.88
1.1
64.36 1 2.0
86.65 T 1.9
TGN MeTA (Ours)
79.41
0.8
68.37 1 0.9
90.03
0.3
of adaptive data augmentation and our DA strategies enriching the input data for temporal graph learning. Our MeтА adaptively augments the input features with appropriate magnitudes, and thus effectively enhance TGNs node classification.
4.3 Efficiency and Effeetiveness with MeTA
As analyzed in Sec. 3,4 McTA enhance TGNs without increasing their time complexity. We evaluate the efficiency and effectiveness of TGN with MетТ using the Reddit dataset, which holds the largest number of nodes and second largest number of edges among the used datasets. We follow the experimental setting of the transductive edge prediction in Sec. 4.1
The methods we evaluate include: TGN, our MeTA method of the level number L = 1, 2, and the refeed method to achieve adaptive DA introduced in Sec. 3.2 The number of memory updates (# Memory Updates) processed per epoch by different methods and the performance is reported in T where 'Time' is the training time until convergence using a Linux Server with an Intel(R) Xeon R) E5-1650 v4 @ 3.60GHz CPU and a GeForce GTX 1080 Ti GPU. We notice that, compared with the refeed method, our MeTA significantly reduces the number of memory updates per epoch. As a result, much less training time and memory updates than the refeed method, and ex- hibits similar efficiency to the original TGNs without DA, while the running time and test accuracy of refeed are unavailable (denoted N.A.), since it takes too much time to converge. This agrees with the theoretical results in Sec. 3.4 since TGNs' time complex- ity is Old #E), which is the same as that of TGN with MeTA,, while the time complexity of refeed is ((((#))) much higher than our MeTA. Here, # the number of edges, which is gener- ally large value in practice.
MeTA method takes
Table 5: Training time and test accuracy of TGN and TGN with DA on the Reddit dataset. The task is transductive edge prediction. We denote the refeed method for DA (see Sec. 3.2) as refeed. L is the level number of our MeTA method, We report mean values over 100 trials with random weight initialization.
Method
Memory Updates
Time
Accuracy (%)
TGN 25
4.7 x 10a
4625s
92.56
TGN + refeed
1.1 x 10th
N.A.
N.A.
TGN McTA (T. 1)
4.7 x 10
4513s
93.07
TGN + McTA (L = 2)
9.4 x 10
7241s
94.19
In terms of effectiveness, both MeTA (L 1) and McTA (L 2) lead substantial improvements over TGNs. Our DA techniques without McTA enhances TGN to perform better than the original TGN without DA. since it enriches the input data with diverse DA strategies. Furthermore, our McTA (L 2) leads to more significant improvements than only the DA techniques with MeTA of L = 1, which validates the importance of adaptive DA achieved by MeTA. Our MeTA applies higher DA magnitudes to less important features, so as to effectively augment the input features and preserve the essential semantic information. Our DA strategies enhance the generalization of TGNs by applying diverse DA strategies to enrich the input data, while our META improves TGNs further by effectively augmenting the input features and preserving the essential semantic information with adaptive DA magnitudes.

---

4.4 Ablation Study
We investigate the contributions of our data augmentation strategies. We apply different DA strategies sequentially with our MeTA on the DyRep model. The results are presented in Table. 66] Our data augmentation strategies improve the effectiveness of DyRep by mod- eling the realistic noise enrich the training data. Among different DA strategies, adding edges with time perturbation leads the largest benefits, since it augments both the temporal and topology features. Perturbing time gives higher improvements than removing edges, because augmenting the temporal information meets the charac- teristies of the temporal graph data better.
Table 6: Effects of our different DA strategies on the
inductive edge prediction of MOOC.
Technique
Accuracy (%)
A
Cumu A
DyRep
72.92
0
+ Remove Edges
73.64
+0.72
+0.72
Perturb Time
74.68
+1.04
+1.76
Add Edges
75.89
+1.21
+2.97
Next, we evaluate the contributions of two message passing mechanisms in our MeTA module. We apply the cross- level propagation and memory transi- tion mechanisms in our MeTА sequen-
Table 7: Effects of our different message passing mecha-
nisms on the transductive edge prediction of MOOC.
Mechanism
Accuracy (%)
Cumu A
DyRep
73.36
0
0
tially the DyRep model. The results
+ DA Strategies
73.67
+0.31
+0,31
are presented in Table. 7 The row
+ Cross-level Propagation
74.76
+1.09
+1.40
+ Memory Transition
76.21
+1.45
+2.85
(+DA Strategies) means that we apply our DA strategies without the adaptive
DA magnitudes provided by McTA. Our message passing mechanisms improve the effectiveness of DyRep by providing the augmented data adaptive to topology and time. In our two mechanisms, memory transitions provide more improvements than the cross-level propagation. Recall that memory transitions adapt the DA magnitudes with respect to the time distances. This result shows that the time distances matter more than the topology distances the adaptive DA for the temporal data, possibly because the time information meets the characteristics of the temporal graph data better.
Finally, we analyze the sensitivity of MeTA to the hyper-parameter: P1. P2 to control the DA magni- tudes. The result is visualized in Fig. 3 We al- ter P1 among {0, 0.1, 0.2, 0.3, 0.4, 0.5) and P2 among {0.5, 0.6, 0.7, 0.8, 0.9, 1}. The performance of TGN with MeTA is relatively smooth when parameters are within certain ranges. However, extremely large values of P1 and small p2 results in poor performances. Too large DA magnitudes on level with large Pi increase the risks of breaking the essential semantic information, while too small magnitudes on level 2 with small p2 cannot augment the input features sufficiently. Moreover, only a poorly set hyper-parameter does not lead significant performance degradation, which demonstrates that our McTA frame- work is able to provide appropriate DA magnitudes for different parts of input features. We provide additional experiments about the hyper-parameter T to control the memory transitions in Appendix.
0.9
0.8
0.7
0.6
033
0.5
Figure 3: The ROC AUC (% in z-axis) TGN with MeTA on node classifi- cation of Reddit with different hyper- parameters P1 and p2.
5 Conclusion
In this paper, we study the problem of exploring data augmentation to strengthen the TGN models. We propose novel methodology named McTA, which provides adaptively augmented inputs for temporal graph learning. MeTА is generic framework that can use any DA strategies to enhance popular TGN models. In our work, considering the characteristics of temporal graph data, we propose three DA strategies to augment the temporal graphs by modifying both temporal and topology features. Our experimental results show that MeTA, with our DA strategies, yields significant gains for both edge prediction and node classification in an efficient manner. One limitation of our methods is that our DA strategies cannot model all realistic noise on temporal graphs in practice. Therefore, future work could explore other advanced DA strategies to enhance approach.
10

---

Acknowledgements
This paper is supported by NUS ODPRT Grant R252-000-A81-133 and Singapore Ministry of Education Academic Research Fund Tier 3 under MOEs official grant number M0E2017-T3-1-007.
References
[1] Nahla Mohamed Ahmed, Ling Chen, Yulong Wang, Bin Li, Yun Li, and Wei Liu. Sampling- based algorithm for link prediction in temporal networks. Information Sciences, 374:1-14, 2016.
[2] Mohammad Ahsanullah, BM Golam Kibria, and Mohammad Shakil. Normal distribution. In Normal and Student' st Distributions and Their Applications, pages 7-50. Springer, 2014.
[3] Jason Baumgartner, Savvas Zannettou, Brian Keegan, Megan Squire, and Jeremy Blackburn. The pushshift reddit dataset. In Proceedings of the International AAAI Conference on Web and Social Media, volume 14, pages 830-839 009,-83,.200 2020.
[4] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder- decoder for statistical machine translation. arXiv preprint 1406. 1078, 2014.
[5] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 702-703, 2020.
[6] Daryl J Daley and David Vere-Jones. An introduction to the theory of point processes: volume II: general theory and structure. Springer Science & Business Media, 2007.
[7] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint Mxxiv1100..04522 2017.
[8] Daniel M Dunlavy, Tamara G Kolda, and Evrim Acar. Temporal link prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data (TKDD), 5 (2):1-22 2011.
[9] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[10] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. arXiv preprins 170.:v/706.022) 2017.
[11] Ryohei Hisano. Semi-supervised graph embedding approach to dynamic link prediction. In International Workshop on Complex Networks, pages 109-121. Springer, 2018.
[12] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
[13] Tomoharu Iwata, Amar Shah, and Zoubin Ghahramani. Discovering latent influence in online social activities via shared cascade poisson processes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 266-274, 2013.
[14] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 16Xiv: 2016.
[15] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1rXiv:1611.07308, 2016.
[16] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1269-1278, 2019.
11

---

[17] David Siben-Nowell and Jon Kleinberg. The link pre-predittion problem for social networks. Journal of the American society for information science and technology, 58(7):1019-103 1031, 2007.
[18] Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and Xiaokui Xiao. Eignn: Efficient infinite-depth graph neural networks. In Advances in Neural Information Processing Systems, 2021.
[19] Tahmida Mahmud, Mahmudul Hasan, Anirban Chakraborty, and Amit K. Ray-Chowdhury. A poisson process model for activity forecasting. In 2016 IEEE International Conference on Image Processing (ICIP), pages 3339-3343, IEEE, 2016.
[20] Meta. Data dumps meta, discussion about wikimedia projects, 2021, URL httpss:/metts wikimedia, herg///index. phppieeeepppptttlaaaaaaaa.. wttppp/www...eeaauuuuuuooooddddd dumpp880lc.c-229222233333 F-ebbuury-2021I.
[Online; accessed
[21] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pages 969-976, 2018.
[22] Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks,
2020.
[23] Luis Perez and Jason Wang. The effectiveness of data augmentation in image classification using deep learning. arXiv preprint a:Xiv: 2017.
[24] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710, 2014.
[25] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10633 10637, 2020.
[26] Krishna Kumar Singh, Hao Yu, Aron Sarmasi, Gautam Pradeep, and Yong Jae Lee. Hide-and- seek: data augmentation technique for weakly-supervised localization and beyond. arXiv preprint arXiv: 18/ 1, .00555, 2018.
[27] Zekun Tong, Yuxuan Liang, Changsheng Sun, David S Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv preprint arXiv:2004. 13970, 2020.
[28] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In International Conference on Learning Representations, 2019.
[29] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003 2017.
[30] Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang. Bowen Sun, al. Apan: Asynchronous propagate attention network for real-time temporal graph embedding. arXiv preprint arXiv:2011.11544 2020.
[31] Yanbang Wang. Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint 20X10:2001.05577 2021.
[32] Yiwei Wang. Shenghua Liu, Minji Yoon, Hemank Lamba, Wei Wang, Christos Faloutsos, and Bryan Hooi. Provably robust node classification via low-pass message passing. In 2020 IEEE International Conference on Data Mining (ICDM), pages 621-630. IEEF, 2020.
[33] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Graphcrop: Subgraph cropping for graph classification. arXiv preprint arXiv:2009.10566 2020.
12

---

[34] Yiwei Wang. Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Progressive supervision for node classification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 266-281. Springer, 2020.
[35] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 207-217, 2020.
[36] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Curgraph: Curriculum learning for graph classification. In Proceedings of the Web Conference 2021, pages 1238-1248, 2021.
[37] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. Proceedings of the Web Conference 2021, pages
2021.
[38] Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoe Le. Unsupervised data augmentation for consistency training. arXiv preprint arXiv:1904. 12848, 2019.
[39] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. arXiv preprint arXiv:2002.0796. 2020.
[40] Wenchao Yu, Wei Cheng, Charu C Aggarwal, Haifeng Chen, and Wei Wang. Link prediction with spatial and temporal consistency in dynamic networks. In IJCAI, pages 3343-3349, 2017.
[41] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals, Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:/611.035300 2016.
[42] Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data augmentation. arXiv preprint arXiv: S.5i::1708.048880 2017.
13


Reviews:
[{"review_id": "ToN-MRvJRNf", "reviewer": "Reviewer_mhw2", "summary": "The paper introduces Data Augmentation (DA) to the temporal graphs in order to offset the increased variance induced by complex GNNs. Three DA methods: perturb time, remove edges and add edges with perturbed time are considered. To make sure the DA effectively works for edges that are less informative, the author proposes a novel and efficient adaptive DA method based on recursion, which is named Memory Tower Augmentation (MeTA). The proposed MeTA can be added on top of RNN based temporal graph implementation. Experiments results on edge prediction and node classification tasks using public temporal graph data set suggest the effectiveness of the method. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "1. contributions\n\nThis paper proposed an algorithm to implement the adaptive DA for the temporal graphs. The method (MeTA) first stacks layers of the memory module with varying DA parameters then uses the intermedia states from layers with more DA to update the RNN states of interest during training. This idea is both novel and interesting. On a high level, it is very similar to firstly stack temporal graphs with different DA strength and then uses recursion-based temporal graph neural networks (TGNNs) with shared weights across layers. So the time complexity only grows linearly with the number of layers in the MeTA and it works naturally with TGNNS. Overall, I think the idea is both neat and useful.\n\n2. Presentation and quality\n\nThis paper is well organized. The authors do a good job explaining their design choice. However, for readers not very familiar with temporal graphs, it is hard to understand how the proposed method works. For example, I can only make sense of Figure 2 after I read and understand the whole section 3. \n\nThe experiment setting is reasonable. The author compares the proposed method with the most state of temporal graph networks and the MeTA consistently performs better than baselines. \n\n3. Question\n\nThe paper claims the DA is adaptive. But in MeTA, the strength of DA only depends on the time and distance. While it is reasonable to believe the edges from past or distant edges are less informative, this is still heuristic-driven. Firstly the information here is not adequately defined and it is likely that edge/node might be highly useful yet remain distant from the target node. I don't whether the authors have thought about ways of making the DA truly adaptive. \n\nProposition one assumes the edge distributions follow a homogeneous Poisson process. This is a very strong assumption. Even still considering the counting process, a more realistic setting for network events could be [Hawkes process](https://proceedings.neurips.cc/paper/2020/file/c5a0ac0e2f48af1a4e619e7036fe5977-Paper.pdf). Secondly, the proof of theorem 1 basically says any noise distribution won't affect the original edge distribution. But this also relies on the assumption of uniform occurrence. Wondering whether the authors have data to support these assumptions. In general, I don't think these propositions along with their proofs are the key contributions of this paper.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author adequately addressed the issues. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "T6naqLRNWEH", "reviewer": "Reviewer_UsrF", "summary": "This paper proposes MeTA: multi-level module that processes the augmented graphs of different magnitudes on separate levels. Three DA strategies augmenting are adopted (perturbing the edge time to simulate time shifts; removing edges; adding edges). Experiments are conducted on edge prediction and node classification tasks.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strong points: \n1.\tThree DA strategies for the temporal graphs seem making sense, i.e. (i) perturbing time; (ii) removing edges; (iii) adding edges with perturbed time.\n2.\tExperimental results on four benchmarks show that MeTA not only improves accuracy on the baselines, but also reduces the number of memory updates per epoch.\n3.\tThe robustness and sensitivity of the proposed method are verified by the soundness of the ablation study.\n\nWeak points:\n1.\tThe proposed method seems too simple without strong theoretical support. In fact the propositions and lemmas in my mind are a bit trivial and does not directly link to the augmentation performance. The current method only considers adaptive magnitude while in my mind the three augmentation operations shall also be adaptively applied if possible. There are many adpative data augmentation literature at least in vision whereby the different operations are adaptively applied.\n2.\tThe setting in the experiment only compares with the original baseline. Author may compare MeTA with more recent works on DA. \n3.     The writing of the paper can be improved and there are some typos and grammatical errors in current form.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SFM2rv5A_D", "reviewer": "Reviewer_WSXU", "summary": "The paper introduces Memory Tower Augmentation (MeTA) --- an adaptive data augmentation approach for temporal graph networks (TGNs). The proposal aims to tackle overfitting and improve learning in TGNs. MeTA applies a hierarchical message-passing scheme to update TGNs' memory states. In addition, MeTA considers three different data augmentation strategies: i) perturb time, ii) remove edges, and iii) add edges with perturbed time.  The experiments show that MeTA achieves higher accuracy than existing TGNs (without data augmentation) on future link prediction and node classification tasks.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The proposed method (MeTA) is novel as it represents the first attempt to leverage adaptive data augmentation techniques for temporal graph networks. The results show that MeTA can boost the performance of the baselines. The main weakness is that MeTA scales linearly with the number of levels of memory modules ($L$). Also, I found section 3.2 particularly hard to follow, and the authors should consider rewriting it for clarity.\n\n### Comments:\n* Avoiding overfitting is one of the motivations (lines 3, 24). However, current TGNs are shallow models with 1 or 2 temporal aggregation layers. Is overfitting a problem in those methods? How much does the proposal alleviate it? Showing this would strengthen the paper. \n*The experiment with PerturbTime can change the ordering of the events. Does it have any relevant implications? Do the authors have any intuition about why this ordering change does not negatively impact the performance?\n* Figure 4 shows that \"large values of p1 and small p2 results in poor performances\". The authors explain that a large p1 increases the risks of breaking the semantic information, while a small p2 cannot augment the features sufficiently. Based on that intuition, why do large values for p1 (=0.5) and p2 (=1.0) still lead to good performance (Figure 4)?\n*It would be valuable to report numbers for different values of $L>2$ in the supplementary material.\n*For some TGNs, a reasonable choice is to sample/aggregate temporal information that respects time. In this approach, neighbors are events in the past (e.g., see CAWNet). Is that the case for the evaluated TGNs? If so, both topological and temporal distances would convey the same information.\n*The authors should cite this related work: CAWNet (https://arxiv.org/abs/2101.05974).\n\n### Minor (inconsequential) issues\n* In Table 2, denoting MeTA (L=1) in boldface seems misleading since there is no reason for MeTA (L=1) to be faster than the original approach (TGN).\n* Some typos: Gaussion (line 184), tmax (line 188), $s^i$ (line 218), \"more earlier edges\" (line 220), \"magnitudes , as\" (line 53), \"information , as\" (line 42).\n* I don't find the comparison against the refeed method relevant (section 4.3, and line 241). It is clearly much slower than MeTA. \n\n--------------------------------------\nAfter the rebuttal phase, I have decided to increase my score to 7 (accept).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address the limitations and the broader impacts of the proposal.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "3ypiATQDLy0", "reviewer": "Reviewer_bZGD", "summary": "This paper proposes an adaptive data augmentation framework for dynamic graphs that improves the performances of two well-known baseline models on node classification and edge prediction on four datasets. Three data augmentations were used with the purpose of modifying temporal and topological features. These strategies inject the inductive bias that closer events in the dynamic graphs, whether in time or topology, are more informative. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Temporal graph learning is relatively a new field of research in the graph machine learning community. Data augmentation has shown its merits in various fields and so adaptive augmentation for temporal graphs is an interesting and important topic of study. The problem and the approach are well-justified and discussed in the paper and generally, the paper is well written. However, there are a few comments and concerns I'd like to share:\n\nFirst, although the algorithm is simple, efficient, and effective, it is not easy to fully understand it from the text initially. The authors can try and improve the description of the method in a more clarified way. Also, the main algorithm shouldn't be in the appendix. It would be helpful to re-structure the paper so that the pseudocode of MeTA doesn't end up in the appendix. Although the pseudocode also needs more clarification for a smooth reading by other researchers. \n\nSome previous papers are reporting average precision (AP) and accuracy for the studied datasets and this paper is doing the same. However, since in the discussion about the reasoning behind the DA strategies on page 5, the authors are showing the concern of real-world scenarios, it would be great if we can see the results for other metrics like mean reciprocal rank (MRR) or Recall (e.g. recall10) as proposed in JODIE.  In my view, these metrics are closer to real-world settings because most of the time there is no real or fake node to classify and you have to rank other nodes for a potential edge connection in the near future. (Consider recommending an object to a user in a social network based advertisement)\n\nIt is mentioned that DA is not applied during inference and it is a common thing to do, but what happens if DA is applied during inference too? \n\nThe paper properly discussed the efficiency of the method in case of run time. Can you please compare the memory usage as well?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations discussion is very limited and there is no social impact section.\n\nFor the social impact section, the authors can discuss employment of dynamic edge prediction in real-world recommendation systems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After discussions between the reviewers and authors it seems as though a consensus has been reached amongst 3 of the reviewers that this paper is clearly worthy of acceptance.  The reviewer on the side of rejection has not engaged in discussions with the authors or in internal discussions on the paper.  The review against acceptance also lacks details in the objections raised to the paper.

I want to thank the authors for their detailed responses and for listening to and incorporating the feedback from the reviewers and thank those reviewers who did for engaging in discussions with the authors.
Decision: Accept (Poster)