Mind the truncation gap: challenges of learning on dynamic graphs with recurrent architectures
Authors: João Bravo
Jacopo Bono
Hugo Ferreira
Pedro Saleiro
Pedro Bizarro
Venue: Accepted by TMLR ()

Abstract: Systems characterized by evolving interactions, prevalent in social, financial, and biological domains, are effectively modeled as continuous-time dynamic graphs (CTDGs). To manage the scale and complexity of these graph datasets, machine learning (ML) approaches have become essential. However, CTDGs pose challenges for ML because traditional static graph methods fail to account for event timings naturally. Newer approaches, such as graph recurrent neural networks (GRNNs), are inherently time-aware and offer advantages over static methods for CTDGs. Yet, GRNNs face another issue: the short truncation of backpropagation-through-time (BPTT) whose impact has never been properly examined until now. In this work, we demonstrate that this truncation can limit the learning of dependencies more than a hop away, resulting in reduced performance. Through experiments on a novel synthetic task as well as real-world datasets, we reveal that there exists a performance gap between full backpropagation-through-time (F-BPTT) and the truncated backpropagation-through-time (T-BPTT) commonly used to train GRNN models. We term this gap the "truncation gap" and argue that understanding and addressing it is essential as the importance of CTDGs grows, discussing potential future directions of research for this type of models.

Published in Transactions on Machine Learning Research (12/2024)
Mind the truncation gap: challenges of learning on dynamic graphs with recurrent architectures.
João Bravo Feedzai, Portugal
jo0o. bono.bravo@feedzai.. com
Jacopo Bono Fredzai, Portugal
bacopo.bonoo@fee com
Pedro Saleiro Feedzai, Portugal
Hugo Ferreira Feedzai, Portugal
hugo.ferreinu@@fedaaaccomm
Pedro Bizarro Feedzai, Portugal
pedro. cadrobiiaarro@eeezzai.. com
Reviewed on OpenReview: https: operevieee net/ forum? id= QezaDgd5hf
Abstract
Systems characterized by evolving interactions, prevalent in social, financial, and biological domains, are effectively modeled contimous--inme dynamic graphs (CTDGs). To manage the scale and complexity of these graph datasets, machine learning (ML) approaches have become essential. However, CTDGs pose challenges for ML. because traditional static graph methods do not naturally account for event timings. Newer approaches, such as graph recurrent neural networks (GRNNs), are inherently time-aware and offer advantages over static methods for CTDGs. However, GRNNs face another issue: the short truncation of patprroppgaatoon-truuuttttiii
(BPTT), whose impact has not been properly examined until now. In this work, we demonstrate that this iruncation can limit the learning of dependencies beyond single hop, resulting in reduced performance. Through experiments on novel synthetic task and real-world datasets, we reveal performance gap between full packpropagationnthroune time (F-BPTT) and the truncated nodppoopggtiion-ttrnggg--t (T-BPTT) commonly used to train GRNN models. We term this gap the "truncation gap' and argue that understanding and addressing it is essential as the importance of CTDGs grows, discussing potential future directions for rescarch in this area.
1 Introduction
In many domains, data naturally takes the form of a sequence of interactions between various entities, which can be represented an evolving network. Examples include interactions between users on social networks, card payments from users to merchants in payment networks, bank transfers between entities in financial networks. These interactions typically involve only pair of entities and are often modeled dynamic graph, where each entity is represented by a node and each interaction by an edge with an associated timestamp.
Unlike static graphs, where links between entities are persistent, dynamic graphs capture the sequential aspect of interactions, which can provide valuable information for different inference tasks. In these settings, the latent variables associated with nodes, such as user preferences social networks, can evolve over time. Tasks on dynamic graphs involve predicting certain edge or node properties or the likelihood of an event involving two nodes at specific point in time based past information.

---

Published in Transactions on Machine Learning Research (12/2024)
Sequence Data
Dynamic Graph Data
Trr
Timm Depandarcce
Endly
Deperdeeto
Ently
Event
Event
Erdly
Enily
merscton
updatis)
Enilyy
4
Entiy
Ume
Figure Truncation of temporal history becomes severe in dynamic graphs. (left) Sequence based data can be grouped by sequence when defining batches. In this specific example of sequences with two events, with batch capacity of entity updates, we can include two sequences per batch. Temporal dependencies between the events (horizontal dotted lines) are not broken by batching. (right) Due to the interactions between states, we cannot consider isolating a subset of entitics in batch on dynamic graphs as we need the counterparty entity's state to updale an autity's state when an event occurs. Batches are defined by time instead of by entity but this leads to more extreme gradient truncation along the time axis (time dependencies are broken by batching). In the example, with the same capacity of 4 entity updates, each batch now includes only a single event per entity.
Notably, Dai et al. 2017 Trivedi et al. 2019 Kumar et al. 2019 Rossi et al. 2020) have proposed treating such dynamic graphs as dynamical systems where a state for each entity evolves over time. The dynamics of these states are based on recurrent neural network (RNN) cells that use the previous states of both interacting nodes when computing the new states, therefore coupling both sides of an interaction the time of an event. We call this class of models graph recurrent neural networks (GRNNs) because they are straightforward extension of the RNNs used for sequence modeling to dynamic graphs.
Although there are differences in how various GRNN approaches handle training, all of them have in common that batches are formed using sequential time windows over the events. Backpropagation applied to cach batch obtain the gradients with respect to the learnable parameters and therefore the learning signal cannot. cross batch boundaries. In other words, this truncation of the backpropagation ignores the dependence of information older than the current batch.
In sequence modeling tasks, one typically has many sequences that are fully independent. If small enough, these sequences can be included in their entirety in a batch, or alternatively, they can be broken down into sizable chunks thus mitigating the impact of truncating the backpropagation (Figure [ left). On dynamic graphs, however, it is not possible to split the data into different sequences per entity due to the coupled dynamics. Effectively, we have single global sequence and batches need to be defined over globally ordered interaction events, from oldest to newest (Figure | right). Because such a sequential batch of events can involve completely different entities, if the number of entities is large enough one can find themselves in a situation where batches include single update per entity. This in turn means that, from the entity point of view, only temporal dependencies spanning a single hop in the graph can be learned accurately. Such drastic truncation could lead to incorrect training gradients and a failure in learning to leverage longer term dependencies existing in the data.
The main goal of this work comparing the training approach proposed in previous works with F-BPTT, We propose synthetic edge regression task dynamic graph that truncated backpropagation fails to learn when dependencies over
investigate the impact of this truncation in GRNN models by
2

---

Published in Transactions on Machine Learning Research (12/2024)
more hops are required. We also show that gap exists between the performance achievable with truncated and full backpropagation, real world dynamic graph datasets by comparing both training methods on popular benchmarks. We call this drop in performance the truncation gap, since it is solely caused by the truncated backpropagation.
While F-BPTT not practical solution for large dynamic graph datasets due to its memory scaling, our results show that current training approaches based on truncating backpropagation are not able to fully exploit the capacity of GRNN models. We believe that further investigation into better training approaches for these models is warranted and propose possible future research directions.
2 Background
Initial approaches to dynamic graphs relied on static GNNs applied to different snapshots of the graph over chosen temporal windows. Because these are too dependent on the granularity of the time windows, ignoring the ordering of events within each window, other approaches that can more naturally cope with the sequential nature of edges were developed. These can be broadly categorized into transformer and RNN based approaches, mirroring the status quo sequence modcling, together with a third class of methods based on random walks on the temporal graph.
Transformer based approaches such TGAT (Xu al. 2020), DyG2Vec (Alomrani et al. 2024 and DyGFormer (Yu et al. 2023) explicitly consider temporal neighborhood as the context for cach prodiction, typically restricted to a few hops. While, by construction, this limits the extent of past information that the model can leverage, these methods don't suffer from the same issue as RNN based approaches where the computational graph that is back-propagated through is a truncated version of the computational graph used to arrive at a forward prediction. Furthermore, these approaches often still require some degree of approximation in the form of subsampling of the temporal neighborhood (also known as neighhorhood dropout).
Random walk-based methods (Wang et al. 2022 Jin et al. 2022 take a similar approach where rather than sampling a neighborhood of a node of interest, temporal random walks over the dynamic graph are used to aggregate information that is relevant for inference. While a random walk offers a limited context for inference, because backpropagation is run on the same computational graph used during the forward pass, these methods don't suffer from the truncation issue that is the focus of this work.
2.1 Graph Recurrent Neural Networks (GRNNs)
RNN based approaches define a dynamical system over the network where the state comprises a hidden state for every node, i E [1..N], in the network: h = (h(1),... ,..,..... h()) E R.N.. For a k-th event between a source node, 8k, and a destination node, da, at time lx, the hidden states, (=() and h (dx) for the nodes involved in the interaction are updated using a pair of functions, Is and ga:
(((t)) Is (w (
(#6) (da)
h
(1)
h (da) ga w (ot((le) h (dde
(9k) Xx
Here, w(ot) is an optional function producing an embedding for the time elapsed since the last update for each node, and X3 the message of the current interaction (which could itself be a combination of edge and node features). These functions are generally based on RNN cells such as LSTM (Hochreiter & Schmidhuber 1997) or GRU (Cho et al.] 2014), therefore, extending the use of RNNs to the dynamic graph setting. We will refer to these as GRNNs, noting that other names have been used in the literature, such as memory-based temporal graph neural networks (Zhou et al. 2023) and message passing temporal graph networks (Souza et al. 2022). A more general framework for GRNNs is discussed in Appendix A
An early example of the GRNN approach is Wang et al. (2016) which proposes a temporal point-process model for event prediction where a latent state for each entity in the network is kept and updated on each
The proposed synthetic task available future approaches learn temporal dependencies.
as benchmark of the ability of
3

---

Published in Transactions on Machine Learning Research (12/2024)
Edge updale
Batth
Batch 1
Batch
Batch
h4
1gg
12g
hg
h.
h2
time
time
time
Figure 2: Three different batching strategics illustrated. Four nodes with respective states h ... h4 interact in Figure ] untiil time lg- Each blue box denotes interaction, where the hidden states of the two interacting nodes are updated. On the left the approach of Dai et al. (2017) where different computation graph is built for each mini-batch. Due to the sequential processing within a batch, computational efficiency is lost. In the middle the t-Batching strategy of Kumaar et al. (2019) which uses variable sized batches to guarantee no sequential dependencies within a batch, allowing parallel processing. On the right, the approach of Rossi et al. (2020) that uses fixed size batches and parallel processing at the cost of correctness, leading to inconsistent histories where the latent states used for the third event ignore the updates of the previous two events.
event with a coupled dynamic model based on a Hawkes process. Dai et al. (2117) extend this model with a more generic update based on a standard RNN cell and Trivedi al. (2017) apply a similar model dynamic knowledge graphs. JODIE (Kumar al. 2019) uses similar architecture but foregoes predicting the time of interaction, instead focusing ranking how plausible interactions between pairs of entities are at given time.
DyRep (rrvedi et al. 2019) and TGN Rossi et al. 2020 constitute hybrid solutions, incorporating transformer elements into a GRNN architecture. DyRep proposes a recurrent model where the messages coming from the counterparty are itself the result of a graph attention operation over the counterparty graph neighborhood. TGN introduces instead an attention based embedding module on top of the recurrent memory model to deal with the staleness problem of the hidden states in the absence of events.
Unlike previous approaches which require access to the temporal graph at inference time and perform complex operations over it, for pure GRNNs the graph itself does not need to be explicitly stored. Instead, it suffices to store the node embeddings and update them using the recurrent architecture whenever a new edge arrives. This makes these models appcaling for inference scenarios requiring low-latency such as fraud detection.
Another advantage of GRNNs over transformer or random walk models that they would seem promise infinite causal context towards the past. However, due to the way they are trained, the ability leverage information that is far in the past can be compromised as we discuss in the next subsection.
2.2 Training GRNNs: Batch Processing Strategies
RNNs are typically trained with Back Propagation Through Time (BPTT) truncated version of this algorithm, T-BPTT, when sequences become too long. In dynamic graphs, however, there is no good option to define sequences, since nodes interact with each other (Figure 1 Because future events are influenced by past events, the natural way to define batches is by adopting a sliding window over the globally ordered events. In other words, no random shuffling of events or sequences possible, and each epoch will contain batches of sequential events between any pair of nodes in the graph. There are different approaches in the literature how to define and process these batches:
4

---

Published in Transactions on Machine Learning Research (12/2024)
Deep CoEvolve and DyRep. Dai et al. (2017 and Trivedi et al. (0019) consider sequential batches of interactions. A computation graph for the forward pass is built for each batch, processing each event in the batch in sequence (Figure 2.2 left). This graph is then back pooo-propaggtee through. Gradient propagation is therefore restricted to each batch, ignoring the model paramcter dependencies of the hidden states cach entity that serve as inpuls to this computational graph. When batches are large enough, this sequential processing of each event in a batch can allow for the learning of multi-hop temporal dependencies, but the cost of being very slow (essentially each edge in the dataset is processed sequentially). Furthermore, for large networks and if events are well distributed across many entities, single update per entity would be processed in each batch and therefore only single hop temporal dependency is learned.
JODIE. Kumar et al. 2019 propose instead using variable sized batches that single update per entity is present in each batch (which they call t-Batches), Figure 2.2 middle). This makes the training more efficient since all updates in single batch can now occur in parallel, but also exacerbates the problem of gradient truncation because it guarantees a truncation horizon of a single hop per entity.
TGN. Rossi et. al. (2020) consider fixed size batches of temporally ordered events, but ignore any sequential dependencies within each batch by processing all updates in parallel (Figure 2.2 right). When multiple events involving single entity are present in batch, this leads to an inconsistent history where the last edge effectively determines the final state of the node, ignoring previous edges that occurred in the same batch. While this approach makes the processing more efficient and straightforward, it (1) guarantees truncation horizon of single hop and (2) introduces an approximation that can potentially deteriorate the results. This forces the authors to propose keeping batch sizes large enough to be more efficient than (Deep)CoEvolve (Dai et al. 2017). but small enough to avoid serious deterioration of results. Empirically, they found that a batch size of 200 provided a reasonable trade-off. We also note that the GNN module on top of the recurrent cell may help alleviate the deterioration, since it provides an alternative way model dependencies in the data the GRNN component.
In summary, all discussed methods suffer from truncating backpropagation with typically small horizons. Because this flaw is tightly linked to the use of backpropagation, and due to the success of backpropagation in other settings and the ease of implementation in current deep learning frameworks, it has been accepted as an unavoidable shortcoming when using GRNNs. In fact, none of the above works discusses this truncation's 's effect on learning. In the next section, we propose a synthetic task to benchmark performance the various approaches on learning temporal dependencies. We identily severe degradation of performance due to the truncation, and subsequently discuss future research directions to mitigate this issue.
3 Synthetic Task
In order to investigate the effect of limiting the backpropragation to a single batch in GRNNs on their ability to learn longer term dependencies we propose a novel edge regression synthetic task. We construct the task achieve the following desirable properties:
A parameter M should regulate the amount of past edge memory necessary to solve the task (larger M would denote older information is needed to correctly predict the label).
The latent state of the source node is updated using the destination node's latent state and vice-versa. Otherwise, non-graph based methods would be able to solve the task.
The code to generate the data will be made available upon acceptance, such that this task can be used in future rescarch to benchmark the developed methods.
3.1 Task Specification
We took inspiration from the adding task (Hochreiter & Schmidhuber 1997). a benchmark frequently used for recurrent neural networks, and construct a variation for graphs that satisfies the above properties. We
5

---

Published in Transactions on Machine Learning Research (12/2024)
M
y
AVG
New interaction between two nodes
Average with x to update internal states
Compute output
h
2
2 3
9
1
2
3
x = 10
10
y
8
5 6 7
Figure 3: Visual depiction of synthetic task dynamics. A fixed size FIFO buffer with length M (4 in the picture) is used to store the internal state of each node. When a new edge between two nodes occurs (a); the input averaged with the last elements each counterparty node's buffer order to determine the new number to be stored in each buffer (b). The sum of these last elements also determines the output for the edge (c).
consider an internal state for each node E [1..N] in a graph, consisting of a memory buffer of size M, h()) E R-M, Each edge, Eg = (sk, du, Ikk Mk), ) defined by two nodes, S and de, an input numeric feature ø and target Vk- The target computed by adding the last clements of the buffers of the nodes (prior the state update for event k):
Vk
(5k) h
k-1
+ (hx-1)
denotes the Mth element of the internal state for node Sy (superscript) step (subscript). The memory buffer of each node is updated after each edge arrival by shifting the values in the buffer using first-nn-frst-ouut (FIFO) principle. Importantly, the newly stored value depends on the edge feature and the counterparty node, such that the second property above is satisfied:
Here, (h(ow)) M
h
(9t)
1 (de)
+ Tz
0 2
M
h (sk)
= k-1
(ok)
i-1 i [
The update is symmetrical for (dx), A schematic representation the task is depicted in Figure 3.1
This task bocomes more challenging as M increases since it determines a delay (in number of edges) between input being observed and it affecting an output for the same node. A recurrent model will have learn the underlying dynamics of the task from these input/ suput/output pairs in order to correctly solve it. It will, therefore, have to memorize older information for cach node as M increases.
To generate dynamic graphs for this synthetic task we sample edges randomly by picking a random pair of nodes, $ę and de, uniformly and a corresponding random edge feature, I& Mi.dd (0, 1), drawn from a standard normal distribution. The states for all nodes are initialized the zero vector. For our experiments consider dynamic graphs consisting of 1000 edges and using a total of 100 nodes, which we refer to as one epoch. We generate new dynamic graph per epoch.

---

Published in Transactions on Machine Learning Research (12/2024)
10a4
--- 0 baseline
FBPTT:
GRU32
GRU64
MSE
10
GRU128
10-3
GRU128
10-4
Memory
Figure 4: Mean squared error (MSE) obtained for different sized GRU models trained with both F-BPTT and T-BPTT. The depicted error bars correspond to the min and max MSE values over 5 different random seeds used for parameter initialization and dynamic graph sampling. The solid lines correspond to the mean MSE over the different seeds.
3.2 Results
All models are based on Equation using a single GRU cell for both updates (since the dynamics are symmetric) and without time encoding.
We train a first model with F-BPTT by back-propagating through an entire epoch (i.c. the entire dynamic graph) in order to compute the gradient of the total loss (sum of losses for all edges). One gradient step is taken per epoch using AdamW optimizer Loshchilov & Hutter (2019) with learning rate of 1e-3 and weight decay of 1c-4 for a total of 5000 epochs.
For the model using T-BPTT we compute truncated gradients for each edge and accumulate these (i.e., sum them) over an entire epoch, performing a single gradient step at the end. We use the same optimizer and hyperparamcters for the same number of epochs as with F-BPTT. The reasoning behind this setup to be directly comparable with F-BPTT but, in this instance, employing an online setup where gradient step is taken per edge did not seem to significantly alter the results for T-BPTT.
We train models using F-BPTT and T-BPTT and with hidden state sizes of 32, 64 and 128. For all models, we compute the average loss over the last 100 epochs across various values of the memory parameter M. For comparison, we also plot the performance of a trivial baseline that predicts OK- = 0 for every edge.
While for M = the models using T-BPTT are able to approximately solve the task, their performance rapidly degrades as M is increased, In contrast, models trained using F-BPTT are able fully solve the task (the final loss is orders of magnitude smaller than the target variance) for every value of M tested (Figure
3.2
4 Dynamic Graph Benchmark Results
In order to show that the truncation gap also present in real world dynamic graphs we conduct a simple experiment on three publicly available dynamic graph datasets from Kumar al. (2019) (Reddit, Wikipedia and MOOC).

---

Published in Transactions on Machine Learning Research (12/2024)
Table 1: Search space for the 25 trials of random search used tune the hyperparameters of the optimizer and the model dropouts. The last parameter refers to a uniform at random choice between the two types of state dropout.
Parameter
Domain
Distribution
learning_rate
[10-3, 10-
Log- Uniform Log-Uniform
veight_decas
[10-5:
mip_dropout
[0, 0.3]
Uniform
_aate_dropuut
[0, 0.3]
Uniform
state_ caate_dropout_eee pyppe (Regular, Recurrent]
Uniform
We consider a GRNN model based on a GRU cell with a hidden state size of 64. Similar to Rossi et al. 2020 we use the same GRU for the updates to both source and destination nodes (note that despite these nodes being heterogeneous, using a GRNN model with non-symmetric dynamics did not lead to better performance). We also disregard any timestamp information on the edges by not having our update function depend on any öt, therefore assuming that there are no autonomous dynamics between events. These choices are made to simplify the experimental setup since our goal is not to challenge the state of the art results for dynamic graphs. Our choice of state size is limited by the memory required to run full backpropagation on the training set.
We train the GRNN model with both truncated and full BPTT, using the same batching strategy of Rossi et al. (0200) (see Section 2.2) with a batch size of 200. We note that while this strategy introduces some error by potentially ignoring some updates in each batch, it the most efficient and practical implement, allowing us to run full BPTT with a reasonable hidden state size on these benchmark datasets. We also employ the same negative sampling strategy where for every edge in the graph, negative edge is obtained by uniformly sampling a random destination node. The training loss is then the binary cross-entropy for classifying positive and negative edges. For F-BPTT we backpropagate through all the batches in the training data, computing the gradient of the total training loss for the epoch. This is possible for the selected datasets due to their relatively small size. In order to enable a fair comparison, we also accumulate the truncated gradients for every batch computed with T-BPTT, performing a single parameter update per training epoch. This allows us to have a common training setup with the same number of epochs and the same number of parameter updates for both methods with the same potential choices of hyperparameters.
We use the Adamm oplimizer (Loshchilov & Hutter, 2019), and tune the learning rate and weight decay parameters using 25 trials of random search. We also tune the values for the dropout of the multilayer pereeptron classifier as well as a state dropout that is applied to the node states modified in cach batch. For this state dropout we experiment with two approaches:
(i) a regular dropout layer applied directly to all the states updated at each batch or (ii) a layer that keeps each element of the previous state with a given dropout probability instead of updating the newly computed state (which we call recurrent dropout). The search space used for these tuned parameters is summarized in Table I. We repeat our experiments using 3 different seeds determining the hyperparameter sampling, model initialization, dropout and negative edge selection during training for the Wikipedia and MOOC datasets. A single seed is used for Reddit, which is the largest dataset, due to it being substantially slower to run.
For evaluation we use a similar setup to Kumar et al. (2019) and Huang et al. (0233). We process the validation and test sets using the same batching strategy used during training, and then rank for every edge all the possible destination nodes according to the probabilities predicted by the model. Note that since the number of destination nodes for these datasets is at most 1000 we don't use any negative sampling for evaluation. Mcan Reciprocal Rank (MRR) and Recall@10 values are computed based on the rank of the true destination node for each edge. We stop each trial when neither metric has improved for 250 epochs.
The results are reported in Table 2 where we can observe a large truncation gap on the Reddit and MOOC datasots representing at minimum a 10% improvement when using F-BPTT. For Wikipedia, while a 3% improvement in the Recall metric was also observed, a non-statistically significant (negative) result is obtained for MRR.
8

---

Published in Transactions on Machine Learning Research (12/2024)
Table Truncated BPTT results in worse performance across most datasets and metrics. Results the benchmark dynamic graph datasets showing that there is performance gap between the models trained with truncated and full backpropagation. For Wikipedia and MOOC, the reported values are the means and standard errors on the test set over the different seeds.
Reddit
Wikipodia
MOOC
MRR
Recall@10
MRR
@1
MRR
Recall@@0
T-BPTT
0.549
0.717
0.534 +0.011
0.677
+0.007
0.281
0.643 40.022
F-BPTT
0.648
0.803
0.525 20.012
0.698 20.006
0.343 =0.008
0.708 =0.07
Truncation Gap
0.010
0.085
-0.009 #0.012
0.022 20.000
0.062 #0.000 0o0
0.064 =0.000
Improvement. (%)
18.1
11.9
-1.8
3.2 +0
22.2 422.6
10.1 +3.0
5 Beyond Backpropagation
While we argued that recurrett neural network architectures are well-suited to handle tasks on dynamic graph data, we have shown that the truncation present stato-of-tho-art approaches can lead to the failure of learning tasks requiring dependencies more than hop away. Since the truncation inevitable in approaches using backpropagation, solving the issue warrants looking beyond backpropagatton--base methods.
Viable research directions could include approximations to real-time recurrent learning (RTRL). More specifically, Tallec & Ollivier (017)) Mujika et al. (2018); Benzing et al. (2019) describe unbiased stochastic low-rank approximations to the true Jacobians in recurrent neural networks on sequential data, which make online learning feasible. Adapting such methods for the dynamic graph settings would an interesting avenue to resolve the temporal dependency learning issue. Another approach would be adopt simpler recurrent architectures that make RTRL feasible, similar to what is proposed in Zucchet et al. (2023) in the context of sequence modeling.
6 Conclusions
We surveyed current methods leveraging recurrent architectures for inference tasks dynamic graphs, discussing the strengths and weaknesses of various training and batching strategies. We identified that backpropagation may reach its limits in this dynamic graph setting, due to severe truncation of the history, confirming that it is holding back GRNN models both a proposed novel synthetic task and in publicly available real-world datasets. Thercfore, we believe that methods beyond backpropagation warrant more attention in this context.
References
Mohammad Ali Alomrani, Mahdi Biparva, Yingxue Zhang, and Mark Coates. Dyg2vec: Efficient representation learning for dynamic graphs, 2024. URL https://arxiv, httg/abs/221..111
Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika, Anders Martinsson, and Angelika Steger. Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning. In Proceedings of the 36th International Conference on Machine Learning, pp- 604-60 613. PMLR, May 2019. URL httpp://proceednngs.tt presss/v97/benzing119. html ISSN: 2640-3498.
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural Ordinary Differential Equations, December 2019. URL http::://aaxiii.orrabbbb.. / arXiv:1806.07366 [es, stat).
Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcchre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rmn encoder-decoder for statistical machine translation, 2014. URL httpps///aax...og//aa//LOO.....

---

Published in Transactions on Machine Learning Research (12/2024)
Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. Deep Coevolutionary Network: Embedding User and Ttem Features for Recommendation, February 2017. URL http:p//aakk..orrr//////00000000 arXiv:1609.03675 [cs].
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735 1780, 1997.
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovee, Michael Bronstein, Guillaume Rabusscau, and Reihanch Rabbany. Temporal Graph Benchmark for Machine Learning on Temporal Graphs, September 2023. URL http:///axxii arggabs/2307.... 01026 arXiv:2307.0100 [cs]-
Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware represcntation lcarning on contimuous-time dynamic graphs. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 19874-19886, Cur- ran Associates, Inc., 2022. URL httpps://proceedngs..s (aaccbberr/Ssda56aaaaaeaeeerrrrr
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Dala Mining, KDD '19, pp. 1269 1278, New York, NY, USA, July 2019. Association for Computing Machinery. ISBN 978-1-4503-6200 doi: 10.1145/3995000333385 URL https://doi..rrr 10. 1145/3292500 33308955
Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization, jan 2019. URL http://arxiv org/abs/11A1.0510 arXiv:1711.05100
[cs, math).
Asier Mujika, Florian Meier, and Angelika Steger. Approximating Real-Time Recurrent Learning with Random Kronecker Factors. arxic:1805. 10842 fes, statj, December 2018. URL htt.hatpp//aarvv.og//bbbb////// 10842
arXiv: 1084.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal Graph Networks for Deep Learning on Dynamic Graphs, October 2020. URL http://arxiv
org/ ht//abb/2000... 10637 arXiv:2006. 10637 [cs, stat].
Amauri H. Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive tempo- ral graph networks. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, Novem- ber 28- December 9, 2022, 2022. URL http::/papers.....//////// nips. cc/paper wttp:/ppe..illeeeppeeeeeeeeeeeee https//aaa/eaa/ee/////eeeeee 0022677e00112220770009933333 Abstract Conferenceeeeeeceeeeooo html
Corentin Tallec and Yann Ollivier. Unbiased Online Recurrent Optimization. arXiv:1702.0510 [cs), May
2017. URL http://rxiiv.orrras//////o 170.. 05043] arXiv: 1702.05043.
Rakshit Trivedi, Hanjun Dai, Yichen Wang. and Le Song. Know-Evolve: Deop Temporal Reasoning for wxXiv:105.005422
Dynamic Knowledge Graphs, June 2017. URL
[cs).
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL http:://ppearrriee../f//oooooo HyePrhR5KX
Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive represstioot learning in temporal networks via causal anonymous walks, 2022. URL. http:://aaxxv..rrraaa///0.0..0/
10

---

Published in Transactions on Machine Learning Research (12/2024)
Yichen Wang, Nan Du, Rakshit Trivedi, and Le Song. Coevolutionary Latent Feature Processes for Contimuous- Time User-Ttem Interactions. In Aduances in Newral Information Processing Systems, volume 29. Cur- ran Associates, Inc., 2016. URL https::/ppoccedding httpagg...eurrpp.ppcppppeaee fills//paper22166/aall
55c0567/4222275557777777456666 Abw.:oct..btttt.t.tt..mc html
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive Repre-
sentation Learning on Temporal Graphs, February 2020. URL httptp:///a...oor////bb///////// wtt.://rrgg/bb//22.099959 arXiv:2002.07962 [cs, stat].
Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library, 2023. URL https:///axii org/ /2033. 13047
Hongkuan Zhou, Da Zheng, Xiang Song, George Karypis, and Viktor Prasanna. Disttgl: Distributed memory-based temporal graph neural network training. In Procecdings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '23, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701092. doi: https://doi.ors org/ 10.
URL
Nicolas Zucchet, Robert Meier, Simon Schug, Asier Mujika, and Joao Sacramento. Online learning of long-range dependencies. In A. Oh, T. Naumann, A. Globerson, K. Sacnko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 10477-10493. Cur- ran Associates, Inc., 2023. URL https::/proccedddgg www.eeddiinnnn.uiiis.eee.. hetph/ssspeerrpp....ppppprpr files//aper//023/fi 2244660cccccfaaa000077777700/066
A A General Framework for GRNNs
One can define a dynamical system over the graph with a hidden state comprising hidden state for every node, i E [1... .V,, in the network: h(t) (h (t)....... (t)). Between edges (i.c. interaction events), this state can be subject to autonomous evolution which we will assume to be lime-invariant and similar and independent for each node in the network:
h - (1-,))17))))))
(2)
We visualize this evolution the blue trajectories in Figure Here we express this time evolution in integral form, but it could instead be given differential equation (NeuralODE) (Chen et al. 2019). Note that if the network is heterogeneous, (i.e., there are different types of entities), we could have different evolution laws for each entity type.
ordinary differential equation such neural ordinary
An edge, é = (sk, der lk X&), is defined by a source entity, 8 E H. a destination entity, dy E X, a timestamp, le and a set of input features, X X. The states for both nodes associated with the edge are updated by a function, g H. x H. X' + H. x H. This update allows information encoded in the state of one node to be propagated to the counter-party node of the edge and vico-versa. We assume this update to be time invariant for simplicity:
(r(w) (da) (c))(tt)) = (1(w)) (tt),
(3)
h (tT). i i (sk,
(4)
We can visualize this update as the red arrows in Figure
In most settings, the state of a node is only needed for the end task al a time of an interaction involving that node. In this case, we can simplify the above model by merging the autonomous evolution f together with the state update into single update function There are two possibilitics for this, depending on whether one needs the state immediately before or after potential interaction for the end-task. As an example, for edge classification regression task where the target for the edge may depend directly on the edge
11

---

Published in Transactions on Machine Learning Research (12/2024)
h(
autonomous evolution (f)
update at interactions (g)
h(2)
h(3)
time
2
Figure 5: The dynamical system over the hidden states can in general contain two components: function / encoding the evolution between interactions (blue), and function g encoding the updates due to interaction events (red). In this example interactions happen at times t1, t2 and t3 between nodes 2-3, 1-3 and 2-3 respectively.
features could use the node states after the update. We denote by (() the last timestamp before where an edge involving node i was obscrved and st(.)) = tx - (txx and write:
(nk (5)) b(aw)) (oelew) s((de) h (de) xxa)
where also defined b((h) h(* ((
Here h is given by applying first f starting from the state immediately after the previous update of each node and then for the edge update. This is depicted on the left (a) of Figure 6 and can be written as
h (51( (de) hea))
(ek) (da) h R-11 Xx xx)=)xx)))) ( ( Inta)): .s (51(a)) n(de)) ( xxx
(6)
For link prediction scenario one would instead like answer the question of whether a link between two nodes is likely at given time (or simply rank how likely potential links between different nodes are). For this task, the node states immediately before (potential) interaction necessary since information about the (potential) edge be considered. We can thus redefine h (sx) (sw)
(sz) and st(2) to be
the time between edge and potential future interaction in Equation the node updates, 9, and then propagating the states using f. This is depicted on the right (b) of Figure 6 Note that a practical application, the update for event k for node would only be computed at the time of future potential event for node i, thus requiring that extra memory of the last event for each node be maintained. In the example of Figure 6 the update for event could be computed at time to for node 2 and Ia for node 3. This is the approach taken in Rossi et al. (2020) where the update is polentially recomputed several times with different values of öt corresponding to the times that node is evaluated as a possible link for another node (i.c., it is selected as a negative example) and when a future edge involving node occurs.
is then given by first applying
12

---

Published in Transactions on Machine Learning Research (12/2024)
a) and then g
b) g and then
h
hg
h, (2)
h, (2)
hgo (2)
hg
h, ())3)
h
t
time
t
time
öt (1)
öt, (2)
ōt, (2)
öt, (3)
Figure 6: The two different possibilities for merging the autonomous evolution and event update into single function. On the left (a) in blue is the update corresponding to the third event between node and 2. The state of each node immediately after its last update first propagated using the autonomous evolution, f. up to 1g and then the update, 9, is computed. On the right (b) in blue the update corresponding to the first event betwoen nodes and 3. The state of cach node immodiately before the event is first updated using g and then propagated using up until the next (potential) event where the state is needed. Note the different definitions of (9) and (t(()) On the left they refer to the state immediately after event k and the time elapsed since the last update the node before event & respectively. On the right they refer to the
state immediately before event. & and the time it will take until the next (potential) update of each node after event A respectively.
13


Reviews:
[{"review_id": "JyUw3nXXWS", "reviewer": "Reviewer_5to8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The paper tackles an interesting research problem which can be useful to both machine-learning researchers and practitioners\n2. The writing, figure, and notation are all clear and accessible even for non-experts\n3. The paper does manage to highlight the severity of truncation in dynamic graphs through Figure 1 \n\n\n**Weaknesses:**\n\nAlthough the paper tackles a very interesting problem, I interpret the current version of the paper as (a) a brief overview of eight GRNN methods used in the literature, and (b) experiments on a synthetic task on three benchmark datasets. Unfortunately, it does not answer a lot of questions that I would look for in a work of this nature. More specifically:\n1. A comprehensive taxonomy chart for the surveyed architectures is not available\n2. The surveyed architectures are all very interesting, but as a practitioner I would want to know what the strengths of each architecture are (particularly if the survey is to be a major contribution of this work). Section 3.1. throws some light on how some of the surveyed works use different kinds of batching strategies but none of these are touched upon in the experiments section.\n3. As mentioned in the beginning of the Weaknesses section, I currently interpret the experiments section as the performance of FBTT v/s TBTT for the Reddit, Wikipedia, and MOOC datasets. However, these experiments, although certainly useful, do not provide a clear picture of the truncation gap (at least in my mind). For instance, the authors mention that they use the batching strategy from Rossi et al.'s paper which is only one of the many batching strategies they talk about in Section 3.1. It is also not clear why the truncation gap is smaller for Wikipedia than the other two datasets. A comparison between the surveyed methods in this section would be necessary to not only better understand how the truncation gap works but also to assess the severity of the truncation gap in these methods (or if it is even significant).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper examines the effect of using truncated backpropagation through time (TBTT) on the learning of continuous time-dynamic graphs (CTDGs). In the first section of the paper, the authors examine a set eight papers that fit the more general GRNN-based framework that use TBTT to batch and learn parameters. In the second section of the paper, the authors define a synthetic task and measure the performance of FBTT versus TBTT on a set of benchmark datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have read the reviews of the other reviewers as well. In addition to the Weaknesses I outlined above, I agree with reviewer i7NF's assessment that the authors should include the other more recent architectures and also specify in more concrete terms if the truncation gap extends to non-GRNN based models.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1ko6vuXKno", "reviewer": "Reviewer_i7NF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strenghts\n- The fundumental appraoch to study the shortcomings of baseline methods in dynamic graphs is very important. Diving into the underlying mechanisms behind the learning dynamics through back-propagation is very insightful.\n- Quantifying the learning deficiency of BPTT and measuring the gap between the optimal case with the sub-optimal case is persuaded in the paper. \n- The paper aims to open up the details behind the common practices for the batching mechanism in CTDG. This has been very less visited by the research community and it will bring good value for the future research works. Additionally, it is very critical to highlight and distangle the nature of dynamic interatctions in CTDG and why over-simplification of dynamic graphs to sequential data is overdone and very detrimental.\n\n## Weakness\n- The surveyed papers are out-dated with respect to the first indicated controbution of the paper. There are recent SoTA such as CaW [1], NAT [2], GraphMixer [3], DyG2Vec [4], Dygformer [5], Todyformer [6] that needs to be cited, studied, and analyzed according to the ascpect the current one are investigated. At the current stage, the claim on the contribution is insufficient with respect to the span of papers surveyed.\n- There is an unaddressed gap between the claim and the supporting evidence. The claim is the truncation which is not studied before in CTDGs, limits the learning resulting into lower performance. However, down the road, both the survey, and the formulation are limited to a specifica category of methods limited to memory-based and RNN-based MPNNs for CTDGs while it is not clear what the other categories such as non-memory-based (i.e. Transformer-based) models are doing according to the truncation gap, whether it exists or not, and how it is quantitatively.\n- In addition to the divergence on the survey and the formulation and theoretical investigation, the emprical supporting evidence are obtained from a simplified experimental setup on both the synthetic and real datasets where this further increases the gap between the claim and the evidence by straying from the experimental setup of SoTA.\n- There is a lack of emprical evidence to prove the claim is properly supported. The experimental evaluation is limited to simple real datasets, to an early baseline (from 2020), there are simplifications such as dropping the temporal information of interactions that might harm the significance of the analysis.\n- Due to the limitation to memory-based (RNN) approaches like TGN there are assumption all over the paper that are not accurate to generalize to all the methods for CTDGs. For instane, memory-based methods would require chronological and sequential training while recent Transformer-based approaches like DyG2Vec does not require that.\n\n[1] Yanbang Wang et al. Inductive representation learning in temporal networks via causal anonymous walks. In Proc. Int. Conf. on Learning Representations, 2021.\n\n[2] Yuhong Luo and Pan Li. Neighborhood-aware scalable temporal network representation learning. In The First Learning on Graphs Conference, 2022.\n\n[3] Weilin Cong, et al. Do we really need complicated model architectures for temporal networks? ICLR, 2023.\n\n[4] Mohammad Ali Alomrani, et al. Dyg2vec: Representation\nlearning for dynamic graphs with self-supervision. TMLR 2022.\n\n[5] Le Yu, et al. Towards better dynamic graph learning: New architecture and unified library. NeurIPS, 2023.\n\n[6] Mahdi Biparva, et al. TodyFormer: Towards holistic dynamic graph transformers with structure-aware tokenization. TMLR, 2024.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The summary of the contributions of the paper is as follows:\n\n- The paper targets to study the Continuous-time dynamic graphs (CTDGs) which are increasingly important for modeling complex systems in various domains where interactions evolve over time.\n\n- It is indicated that the static graph methods struggle to accurately represent these dynamic interactions because they fail to incorporate the timing of events, which is crucial for understanding the dynamic behavior of domains represented by CTDGs.\n\n- Graph recurrent neural networks (GRNNs) have emerged as a promising approach for modeling CTDGs, as they are specifically designed to be time-aware, allowing them to better capture the correlations of evolving interactions.\n\n- It is highlighted that despite the advantages, GRNNs face a significant challenge due to the short truncation of backpropagation-through-time (BPTT). The paper claims the short truncation can hinder the ability of the models to learn and retain important temporal dependencies present in the data to a significant extend resulting in reduced performance. It is noted that the paper is the first to investigate the shortcoming, and present analysis on the truncation gap.\n\n- Through emprical invesitagtions, the authors support the claim through revealing a notable performance gap—referred to as the \"truncation gap\"—between the results obtained using full backpropagation-through-time (F-BPTT) and those achieved with truncated backpropagation-through-time (T-BPTT) using a synthetic task and , highlighting the limitations of the latter.\n\n- The authors believes that as the relevance of CTDGs continues to grow in various fields, it becomes crucial to understand and address this truncation gap to enhance the performance and applicability of machine learning models in dynamic graph scenarios.\n\n- The paper concludes by discussing potential research avenues aimed at mitigating the truncation gap, suggesting that further exploration in this area could lead to more effective methods for handling temporal dependencies in CTDGs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Based on the aforementioned strenghts and weaknesses, the requested changes are provided in a orderly manner from the highest to the lowest importance as follows:\n- The overall claim of the paper needs to be lowered and limited to memory-based approaches through a RNN point-of-view. This needs to be clearly communicated that this study does not cover non-memory-based approaches where some of the assumptions are not valid, for instance, sequntial/chronological training, caching of hidden states, etc. If it is decided to cover boarder categories of CTDG models, the theoretical aspect and the formulation behind the fundamentals of learning then would need to be improved to cover non-RNN approaches (e.g. Transformer-based). It is not clear if the truncation gap is only limited to memory-based appraoches, if Transformer-based approaches suffers from it as well, etc. Since memory-based appraoches are inefficient due to the two shortcomings, if Transformer-based appraoches does not have truncation gap to a significant extedn, then the motivation is voided and the claim of the study is invalid.\n- The supporting evidence needs to be improved to be able to support the claim in the following directions:\n  1. aligning the experimental setup with the one used in the literature, for instance consider temporal information of the interactions during the encoding.\n\n\n  2. Show the truncation gap on the real dataset for the baseline having the same performance as reported by the original paper. This will make the analysis accurate and help to improve the quality of the evidence to support the claim.\n  3. Provide the experimental results for more baselines (even if it is limited to memory-based approaches).\n- It is highly recommended to start investigating how the recent SoTA are observed and related to the interests of the paper. There are several recent approaches noted before such as CaW, NAT, GraphMixer, DyG2Vec, Dygformer, Todyformer.\n- The first contribution of the paper needs to be expanded with respect to the number of appraoches to cover a wider spectrum of approaches to be considered as a survey. Otherwise, claim of the contribution in the introduction can be dropped and left to be a typical related work. To highlight this, it is important to mention that almost 6 pages of the paper are dedicated to the survey while still recent SoTA are left behind. \n- There is a lack of motivation behind why studying the tuncation gap in CTDG is important while the real problems require processing of ever-growing dynamic graphs using limited computational resources. It reminds of the gap between the Gradient Descent and the Stochastic Gradient Descent. Furthermore, the truncation might be regarded as a welcoming mechanism that would impose some regularization on learning.\n- Elaboration on this on page 6 is needed \"Finally, Zhou et al. (2023) propose efficient ways to distribute the training of the above models over multiple\nGPUs, but its proposed methods do not affect the truncation problem\"\n- This statement does not seem accurate: \"Because this flaw is tightly linked to the use of backpropagation, and due to the success of backpropagation in other settings and the ease of implementation in current deep learning frameworks, it has been accepted as an unavoidable shortcoming\". BPTT in RNN has been a challenge in the DL community while recent years, Transformer-based (or recent variants of the state-space models) appraoch have shown to be able to overcome some of the shortcomings.\n- There is a lack of motivation on how the synthetic task helps understand the truncation gap caused by the batching strategies noted in Sec. 4; \"In order to investigate the effect of limiting the backpropragation to a single batch in GRNNs on their ability to learn longer term dependencies we propose a novel edge regression synthetic task\". This is a reference to the point that the gap between the claim and evidence start to increase where the setup is designed for a synthetic task to highlight the shortcoming of RNN to learn using BPTT. It should be motivated how this directly related to CTDG as CTDG are not sequential data where RNN are proppsed to represent. \n- It should be emphasized how the claim on the truncation gap is based on the presumptions on memory-based methods such as chronological training. If the presumptions are voided, does the truncation gap issue is no-longer valid. Elaboration on this point is needed.\n- Fig 4.b seems problematic where (4+10)/2=7 and should go to (h^2)_0 according to the earlier eq.  while is gone to (h^1)_0. \n- The notatation (h^(s_k)_(k))_M seems slighly ambigious particuarly when it comes to the subscript k and k-1 as it is not clear what it aims to show. Explicit delineation is very helpful to further distangle the notation.\n- the synthetic data generation does not completely mimick the distribution of dynamic graph approached in CTDGs. The assumption that not only the order of edges but also the time interval between them matters. A node may have an interation at the edge sequence order of 0 and 10 but the interval between the two might range from 1 second all the way to one year. Consequently, the time scale is neglicted in this experimental setup and needs to be aligned with respect to the common experimental specification in CTDGs.\n- It is too late to clarify on the fact that the aim of the paper is not to challenge SoTA at the end of page 8; \"These choices are made to\nsimplify the experimental setup since our goal is not to challenge the state of the art results for dynamic graphs.\". The narration of the paper at the beginning has been towards the delineating fact that the SoTA for CTDG inherent the truncation gap and hence suffers from the lack of performance. While the claim is high the supporting evidence stemmed from the over-simplified experimental setup by lifting the time scale dyancmis in the empricial studies seems to harm closing the gap between the evidence and claims to be fuuly supported with accurate and convincing claims. As noted before, either the claim needs to be narrowed down to a limited type of CTDGs or the experimental setup upgraded to cover similar setups studied by SoTA hence the evidence would be accurate and convincing.\n- further detailed information on the dynamic graph generation is required to clear out with more acucrate details \"For our experiments we consider dynamic graphs consisting of 1000 edges and using a total of 100 nodes, which we refer to as one epoch. We generate a new dynamic graph per epoch.\". What is the generation process? What is the nature of the nodes and edges?\n- It is not clear how the training procedure on the real datasets for the F-BPTT is achieved with mini-batching of size 200 where it was expected to have the full propagation across the entire training set rather than a sum of batches of edges. Under this scenario, F-BPTT seems similar to T-BPTT due to the batching mechanism. Batching is the source of truncation. It is vague that through mini-baching how F-BPTT is different from T-BPTT and how the gradient truncation is done in the latter with respect to the non-truncated one in the former.\n- Additionally, there is a significant missing details on how the experiments could be managed to handle computationally datasets like MOOC where there are ~7K nodes and ~400K edges.\n- There is a significant gap between the results for the truncated case with the baseline method TGN for all 3 benchmark datasets let alone the results of the recent SoTA. This is another reason the supprting evidence has further been fallen behind the claim of the paper and hence deteriorating closing the gap. It is highly recommended to push the results of the truncated case all the way up to the comperative level with the baseline and then demonstrate and analyze what the truncation gap is. Since the experimental result is too low, the empirical evidence fall behind being able to support the claim in the real world setup.\n- under section 6, there is a contrary statement to the part pointed the intention is not to challenge SoTA \"While we argued that recurrent neural network architectures are well-suited to handle tasks on dynamic graph data, we have shown that the truncation present in state-of-the-art approaches can lead to the failure of learning tasks requiring larger temporal dependencies\"\n- Furthermore, the paper seems not accurate on statements such as \"More specifically, recent work (Tallec & Ollivier, 2017; Mujika et al., 2018; Benzing et al., 2019) describe unbiased stochastic low-rank approximations to the true Jacobians in recurrent neural networks on sequential data,\nwhich make online learning feasible\" where references from 2017-2019 are regarded as recent work.\n- an study on the memory and space complexity tradeoff between the two truncation modes would be insightfull.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NpOblYB6px", "reviewer": "Reviewer_A1Qi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This manuscript is easy to follow.\n1. The figures are clear and intuitive, conveying key concepts effectively.\n\nWeaknesses:\n1. The truncation gap of RNNs is a well-studied problem. Relevant works even date back to the 90s [1-3]. The major issues of BPTT with short truncation length are (1) the limited temporal context, which makes it hard to capture long-term dependencies, (2) vanishing/exploding gradients, and (3) overfitting to short-term patterns. However, none of them are discussed in this work.\n1. The related work simply lists eight past works and introduces their architecture designs and batch-processing strategies one by one. If the survey is one of the major contributions, readers are expected to see a taxonomy study and an in-depth discussion of the key design choices supported by experiment results.\n1. Important related works [4, 5] in the Temporal GNN domain that do not use RNN to capture temporal relationships are missing. The advantages and disadvantages of those works need to be discussed in detail and supported by experiment results.\n1. Evaluation only includes T-BPTT and F-BPTT on limited datasets, which is incomplete. In addition, there is no analysis of the amount of temporal dependencies and their durations in each dataset. Why is there no improvement on the Wikipedia dataset? Is there anything unique about this dataset? The readers expect an evaluation that covers a granular grid in the dimensions of different datasets, different network architectures, different batching strategies, and different truncation lengths, with a few hypotheses that shed light on future Temporal GNN design. Accuracy, runtime, and convergence speed should all be compared. Even if simply altering the `--backprop_every` parameter in the TGN [code](https://github.com/twitter-research/tgn/blob/master/train_self_supervised.py#L36C24-L36C38) might provide some insightful findings, which would not cost more than a few hours to run. \n\n[1] Learning long-term dependencies with gradient descent is difficult, https://ieeexplore.ieee.org/document/279181\n\n[2] Memory Augmented Neural Networks with Wormhole Connections, https://arxiv.org/pdf/1701.08718\n\n[3] An Empirical Exploration of Recurrent Network Architectures, https://arxiv.org/pdf/1701.08718\n\n[4] Inductive Representation Learning on Temporal Graphs, https://arxiv.org/abs/2002.07962\n\n[5] Do We Really Need Complicated Model Architectures For Temporal Networks?, https://arxiv.org/abs/2302.11636", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work revisits the truncation gap problem for batched training of RNN-based Temporal GNNs. The authors review eight related works and summarize their architecture designs and batch-processing strategies. Experiments on synthetic and real-world tasks are performed where results of BPTT for one event and BPTT for the whole graph are compared.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The truncation gap problem in Temporal GNNs is a good research direction, I suggest the authors start from scratch and submit to another conference/journal.", "broader_impact_concerns": "I do not have concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JWhKJGZuAR", "reviewer": "Reviewer_Y1ML", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper addresses a critical but often overlooked issue in the training of Graph Recurrent Neural Networks (GRNNs) for dynamic graphs, specifically the impact of truncated backpropagation-through-time (BPTT).\n- The paper provides empirical evidence from both synthetic and real-world datasets, demonstrating the practical implications of the truncation gap on model performance.\n\nWeaknesses:\n-  While the paper identifies the truncation gap, it could provide a more detailed explanation of how exactly truncated BPTT impacts the learning of temporal dependencies in GRNNs. Can the authors elaborate on the mechanics of this impact?\n- The paper notes the use of a simple model for the experiments. How would more complex models, capable of capturing deeper dependencies, fare with truncated BPTT? Does the truncation gap increase with model complexity?\n- While the paper focuses on the truncation issue, it does not delve deeply into the computational complexity of GRNNs, particularly how this complexity scales with the size of the dynamic graph.\n- The paper focuses on RNN-based methods. How do the findings compare to non-recurrent methods that may be used for dynamic graph data? Is the truncation gap a problem unique to RNNs, or is it a more general issue?\n- The paper could benefit from a comparison with other models that do not use BPTT to understand how unique the identified truncation gap is to GRNNs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper identifies and addresses the \"truncation gap\" in training Graph Recurrent Neural Networks for dynamic graphs, demonstrating the impact of backpropagation truncation on learning temporal dependencies and proposing future research directions to mitigate this issue.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This decision is a little tricky, since the reviewers span all 4 possible options (Accept, Leaning Accept, Leaning Reject, Reject). It is worth noting that, of the 3 reviewers I invited to review this paper, 2/3 recommended accept. The 4th reviewer (who recommended Leaning Reject) volunteered to review. 

From reading the reviews of the reviewers' that recommend reject, the weaknesses identified are focused on: 1) not being state-of-the-art, 2) not providing a wide enough investigation of all the architectural/hyper-parameter properties that affect the results. While I believe these are limitations of this work, they are not sufficient to reject the paper from the TMLR acceptance criteria. 

For the above reason, I recommend accepting the paper. The authors updated their manuscript to meet the comments of the reviewers, and I do not think additional minor editing would provide much change. Therefore, I am recommending accepting as is.
Decision: Accept (poster)