Recurrent Temporal Revision Graph Networks
Authors: YIZHOU CHEN
Anxiang Zeng
Qingtao Yu
Kerui Zhang
Cao Yuanpeng
Kangle Wu
Guangda Huzhang
Han Yu
Zhiming Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: temporal graph
temporal graph network
temporal graph model expressiveness
continuous-time dynamic graph
TL;DR: New temporal graph network SOTA

Abstract: Temporal graphs offer more accurate modeling of many real-world scenarios than static graphs. However, neighbor aggregation, a critical building block of graph networks, for temporal graphs, is currently straightforwardly extended from that of static graphs. It can be computationally expensive when involving all historical neighbors during such aggregation. In practice, typically only a subset of the most recent neighbors are involved. However, such subsampling leads to incomplete and biased neighbor information. To address this limitation, we propose a novel framework for temporal neighbor aggregation that uses the recurrent neural network with node-wise hidden states to integrate information from all historical neighbors for each node to acquire the complete neighbor information. We demonstrate the superior theoretical expressiveness of the proposed framework as well as its state-of-the-art performance in real-world applications. Notably, it achieves a significant +9.4% improvement on averaged precision in a real-world Ecommerce dataset over existing methods on 2-layer models.

Recurrent Temporal Revision Graph Networks
Yizhou Chen' Shopee Pte Ltd., Singapore
Anxiang Zeng" SCSE, Nanyang Technological University, Singapore
Guangda Huzhang" Shopee Pte Ltd., Singapore
Qingtao Yu Shopee Pte Ltd., Singapore
Kerui Zhang Shopee Pte Ltd., Singapore
Yuanpeng Cao Shopee Pte Ltd., Singapore
Kangle Wu Shopee Pte Ltd., Singapore
Han Yu SCSE, Nanyang Technological University, Singapore
Zhiming Zhou' Shanghai University of Finance and Economics, China
Abstract
Temporal graphs offer more accurate modeling many real-world scenarios than static graphs. However, neighbor aggregation, critical building block of graph networks, for temporal graphs, is currently straightforwardly extended from that of static graphs. It can be computationally expensive when involving all historical neighbors during such aggregation. In practice, typically only a subset of the most recent neighbors are involved. However, such subsampling leads to incomplete and biased neighbor information. To address this limitation, we propose a novel framework for temporal neighbor aggregation that uses the recurrent neural network with node-wise hidden states to integrate information from all historical neighbors for each node to acquire the complete neighbor information. We demonstrate the superior theoretical expressiveness of the proposed framework as well as its state- of af-the-art performance in worldworld applications. Notably, it achieves significant +9.6% improvement on averaged precision real-world Ecommerce dataset over existing methods 2-layer models.
Introduction
Many real-world applications (such as social networks 28 recommender systems traffic forecasting [18. 45] and crime analysis (II) involve dynamically changing entities and increasing interactions, which can be naturally modeled as temporal graphs (also known as dynamic graphs) where nodes and edges appear and evolve over time. Compared with static graph solutions 1 35 9
dynamic graphs can be more accurate in modeling node states and inferring future events.
In modern graph representation learning, neighbor aggregation, i.c., generating higher-level node embeddings via referring to the embeddings of their neighbors 13 35 [7], is a critical common ingredient that helps more effectively leverage the connectivity information in the graphs. Practically, however, relatively hot nodes may have rapidly growing lists of neighbors, which makes involving all neighbors in neighbor aggregation computationally expensive. In static graphs, SAGE [8] suggests randomly sampling d neighbors to approximate neighbors. For temporal graphs, the prevalent approach is consider only the most recent neighbors
28 33
But such subsampling of neighbors
'The three authors contributed equally to paper. CCorespooding author. zhouzhiming @ wmw.l.suuf...du.com
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

could lead to incomplete and biased information, as the neighbor information preceding the most recent d neighbors is permanently lost.
To mitigate the problem caused by neighbor subsampling, we propose an alternative solution to classic neighbor aggregation for temporal graphs, called recurrent temporal revision (RTR), which can be used as a standard building block (a network layer) for any temporal graph network. Each RTR layer incorporates a hidden state for each node integrate the information from all its neighbors using a recurrent neural network (RNN). The hidden state will serve as the embedding of each node that layer, embracing the complete neighbor information and having the flexibility to focus more on long-term or short-term behaviors depending on the characteristics of the problem / dataset.
The existence of such hidden state implies that all historical neighbors have already been integrated through previous updates. So when a new edge event comes, we may build a message with the latest neighbor to update the hidden state through the RNN. On the other hand, taking the state updates of previous neighbors into account can also be beneficial, which could provide additional information including new interactions of these neighbors 28 as well updates in the neighbor states due to the influence of their own neighbors. In other words, re-inputting neighbors would enable revising their previously provided information. Therefore, we propose a module called temporal revision (TR) to collect state updates of previous neighbors to update the hidden state together with its latest interaction. To better capture the state updates, besides their current states, we additionally input the revisions and state changes of neighbors into the temporal revision module. Subsampling of such state updates of neighbors can be less problematic, since the state of each neighbor has already been observed and integrated by the hidden state in the past.
Towards further enhancement, we propose to introduce heterogeneity in temporal revision, i.e., treating involved nodes non-uniformly, to boost its theoretical expressiveness. Heterogeneity can be naturally incorporated, since when a node collects revisions from its neighbors, the neighbors may, the other way around, collect the revision from the node (at a lower level), which is, however, directly accessible to the node itself. We thus introduce heterogeneity by recursively identifying and marking such self- ooffprrbing nodes as specialties in revision calculation. We theoretically show that such heterogeneous revision leads improved expressiveness beyond Temporal- IWL [33], and practically verify its potential to promote effective information exchange among nodes.
Our contributions can be summarized as follows:
We propose novel neighbor aggregation framework for temporal graphs to tackle the challenges arising from the necessary subsampling of neighbors.
We propose two expressiveness measures for temporal graph models in terms of temporal link prediction and temporal graph isomorphism test, and characterize their theoretical connection. We prove theoretically the superior expressiveness of our proposed framework, as well as provide several new results the expressiveness of other baselines.
We demonstrate in experiments that the proposed framework can significantly outperform state-of- the-art methods. In particular, we can consistently get improvements as the number of aggregation layers increases, while previous methods typically exhibit only marginal improvements 28 38
An Ecommerce dataset is provided along with this submission, which can be valuable for evaluating temporal graph models in real-world settings.
2 Preliminaries
2.1 Temporal Graph Modeling
A temporal graph can be represented as an ordered list of timed events, which may include the addition, deletion, and update of nodes and edges. For simplicity, we will only discuss the handling of edge addition events in this paper, where newly involved nodes will be accordingly added and We denote the set of nodes and
initialized. It can be easily extended to handle other events 28 edges up to time t as Vtt) and E(t), respectively.
Modeling of temporal graph typically generates node embeddings that evolve over time as graph events occur, which can be used by downstream tasks such as link prediction 2 29) and node classification 20 4 The base node embeddings can have various sources, including direct node

---

features 8
35 11, learnable parameters 9 36
generated by other modules such as an RNN 28
B8
5 Or specifically designed module E 16
Modern temporal graph methods 28
typically employ additional layers top of the base embeddings to (further) leverage the connectivity information within the graph, generating higher-level node embeddings with wider receptive field that encompasses relevant edges and nodes.
2.2 (Temporal) Neighbor Aggregation
Among various approaches, neighbor aggregation is one of the commonly used techniques in various graph models as a critical ingredient, where the embedding of each node is updated by considering the embeddings of its neighbors. In the context of temporal graphs, the neighbor aggregation layer
can be defined as follows
28
38 33
(t) (((, (t),B((ev;))) Cue,e E E(t)))
(1)
h COMBINE (n: (1),
(2)
where denotes the current time. Cue,r denotes the event between node u and node v at time l' t). ((Cun.e) encodes the event feature, as well as its related time and sequence information, which may include the current time, the event time, the current number of interactions of u and v. etc. AGG and COMBINE" denote arbitrary learnable functions, which are typically shared layer k. (t) the aggregated information from neighbors at the k layer, while h (t) is the new embedding of node at layer k, combining its current embedding the k 1 layer with the aggregated information a (D). This can be viewed as a straightforward extension of classic graph convolution layers 13 with additional time sequence information.
2.3 Expressiveness of Temporal Graph Models
Expressiveness measure is crucial for identifying and comparing the capabilities of different models. While several studies have explored the expressiveness of (temporal) graph models EC 5 B 39 [R]
a widely accepted definition for the expressiveness of temporal graph models is currently lacking.
Towards addressing this gap and establishing solid groundwork, we propose the following formal definition of expressiveness in terms of temporal graph isomorphism test and temporal link prediction:
Definition 1. (Temporal graph isomorphism indistinguishabiiitt). Given a pair of temporal graphs (G,(t), (t),),, say they are indistinguishable w.r.t a model f, if and only if there exists bijective mapping between nodes of G1 (t) and Gz( such that, for each pair of nodes in the mapping, their embeddings generated by f are identical at any time t' i t.
Definition 2. (Temporal link prediction indistinguishabilit)). Given temporal graph G(t) and two pairs of nodes ((u,, 02), (W2, 12)) therein representing two temporal link prediction problems, we say they are indistinguishable w.r.t. model f. if and only if the embedding of un and u2 U1 and V22 generated by f are identical at any t' st.
Definition 3. (Temporal graph isomorphism expressiveness). If a model f can distinguish any pair of temporal graphs that model JB can distinguish, while being able to distinguish certain graph pair that fB fails, we say fA is strictly more expressive than fg in temporal graph isomorphism test.
Definition 4. (Temporal link prediction expressiveness). If model JA can distinguish any pair of temporal link prediction problems that model I' can distinguish, while being able to distinguish certain pair of temporal link prediction problems that J fails, we say fA is strictly more expressive than fB in temporal link prediction.
We can similarly define equally expressive, more or equally expressive, and so on.
Through above, we have, for the first time, provided a consistent definition of expressiveness for both temporal graph isomorphism test and temporal link prediction. Besides, compared with existing definitions, ours is more concise and straightforward, avoiding the introduction of concepts such as the Identifiable Set as in (5) and Temporal Computation Tree as in [3]
Most existing results on the expressiveness of temporal graph models can be easily transferred to our definition. For example, massage-passingg temporal graph networks (MP-TGN) strictly
3

---

4000
A.R.M.M
2
R
3
5
UPDATE
RMSC
amzzddingg
Round enstedding
Found & embooding
BARR
TR
Oura
4
2 PT PWSG prade reching massage))
5
RTR
Hiltern sade joone provazse rengttora)
Round ambedding
Base embedding A*
(a)
(h)
Figure 1: (a) A comparison of our framework and other classic aggregations. Classic temporal aggregation typically involves subsampled neighbors in each step, which leads to incomplete and biased neighbor information, while our proposed RTR layer integrates the whole information of neighbors into node-wise hidden states. (b) An illustration of the inner structure of RTR layer and our RTRGN, which builds A successive RTR layers on top of the base embedding. We provide the pseudocode for RTRGN embedding calculation in Appendix
more expressive in isomorphism test when the (temporal) neighbor aggregation layers are injective (referred to as IMP-TGN) 33 and IMP-TGN would be as expressive temporal 1-Weisfeiler- Lehman (Temporal- WLL test 3 39 if with sufficient many layers.
The Proposed Method
3.1 Recurrent Temporal Revision
In large graphs, having too many neighbors can pose practical computation challenges in neighbor aggregation. For static graphs, SAGE [ suggests approximating neighbor information by randomly subsampling a fixed number (d) neighbors. For temporal graphs, recent models [28] [ typically involve the most recent d neighbors reduce the computation cost of temporal neighbor aggregation, which often yields better performance compared with uniform sampling (28). But such subsampling of neighbors fails to provide complete neighbor information and biases it towards short-tern behaviors. The effects are illustrated in Figure (a).
Towards addressing this problem, we propose to introduce a hidden state (t))) in each aggregation layer & for each node to integrate information from all its historical neighbors under state transition model, typically recurrent neural network (RNN). Since events in the temporal graph, and hence the addition of neighbors, occur sequentially, such integration can be done naturally.
Formally, when an event E occurs, we will need to update the hidden state h of u (and also v). straightforward implementation would be updating the hidden state with a message of the new event. However, taking the state updates of previous neighbors into account can also be beneficial, which can provide additional information including: the new interactions of neighbors, their state evolutionary directions, updates in the neighbor states due to the influence of their own neighbors. To achieve this, we introduce a module called temporal revision (TR) to collect state updates of previous neighbors, which will be later fused with the latest event to update the hidden state:
r (t) TR (((({ ( Ab (t), (t),
(t), ((eun.)) )) Cun,e' E E(()))
(t),
(3)
where T is arbitrary learnable function shared layer k, t. represents the time right before We collect not only the newest states of neighbors h (t) at the & 1 layer, but also their state changes Ah (t) = h -t)- -t)--tt-(FF" and their revisions r (t), as well as the event information @(Cuv. help the model better extract the state update information. We set r
vectors. When requesting the embedding of a node at the 0-th layer, we refer to its base embedding. Please refer Appendix for more detailed discussions of the base embedding.
In subsequent ablation studies, we show that retaining Ahk- alone, while removing hy- will not lead to degeneration of performance, which means the effectiveness in aggregation rely

---

solely on the changes of states, while not necessarily on the neighbor states themselves. Temporal revision hence substantially different from classic temporal aggregations ES
28
35
To encode all neighbor update information, we build state revising message (RMSG) via:
(t) RMSG* (t), h ( (t), ((Ev,.))
where RMSG* is an arbitrary learnable function shared at layer k, integrating the node embedding at the k - 1 layer h (t), the embedding of the new neighbor at the k - layer h (t), the collected neighbor state update information (t). as well as the event information o (Ccuv.))
Then the proposed recurrent temporal revision (RTR) layer be formulated as:
(t) UPDATE* (h", (t).
(5)
where the state revising message consumed to update the hidden state h from time t to f via UPDATE*, a learnable function shared at layer k responsible for hidden state transition. For all RTR layers, we initialize (0) as zero vectors for all nodes.
3.2 Heterogeneous Revision
Heterogeneous message passing can improve the expressiveness static GNN which can be naturally integrated into revision computation.
The term r (t) recursively gathers revision from previously interacted nodes, and they may in turn gather the revision of node u (at a lower level), which is, however, directly accessible itself. Therefore, we may adopt a different treatment for such self-probing calculations during recursive aggregation. To achieve this, we may mark all nodes in the recursive computation path as specialties.
Formally, we define the heterogeneous revision as:
(1, (((:: ((,S(()),, (1, ((Go,,)) 1 eS] Cun,r F(())): (6)
where we introduce an extra argument S for revision, which is a set that initialized as empty Ø and recursively adds each encountered along the computation path. 1 stands for the indicator function, which triggers the difference between nodes in and the rest, bringing about heterogeneity in the revisions. To switch to heterogeneous revision, we replace (1) in with (1, We set the base case (1, S) as zero vectors for any u and S.
We show in the next section that incorporating such heterogeneous revision theoretically leads to enhanced expressiveness, which will be subsequently validated our later experiments.
We illustrate the complete inner structure an RTR layer in Figure [b). The implementation details, including the design of all these learnable functions, provided in Appendix A
3.3 Model Expressiveness
For model expressiveness, we assume our RTR layers are built on top of a base RNN. For a fair comparison, it is assumed the base RNNs for all models are the same and of the best expressiveness, as suggested 5 33 We focus on RTR layers whose (learnable) functions 4
are injective,
which can be achieved by adopting similar approaches as
We refer such a model as
RTRGN. Besides, we assume node and edge attributes come from a finite set as 25 33
We will mainly compare RTRGN with PINT K3 which is instance of IMP-TGN that can be equally expressive as Temporal 1- 1-WL in isomorphism test. PINT also offers augmented positional features (referred to as PINT-pos) designed to enhance its expressiveness.
Our first theoretical result demonstrates that the temporal graph isomorphism test is inherently more challenging than temporal link prediction. All proofs are deferred to Appendix B
Proposition 1. Being more expressive in temporal graph isomorphism test implies being more expressive in temporal link prediction (fA> ff (pffB) but not vice versa (fA fyfB f ttfB).
When there event time for u, but requesting the message, we set h. k-1 (t) @ in
5

---

Table 1: Summary of our theoretical results. Temporal graph isomorphism test inherently more challenging than temporal link prediction. While Hime-then-Iie IMP and PINT are equally expressive as Temporal-1 WWL, our proposed RTRGN is strictly more expressive than the Temporal- WI, both tasks. Relevant existing results are represented in gray for better reference.
Expressiveness (Link Prediction)
Expressiveness (Isomorphism Test)
Pis Jp = LA Plp Jo (Prop.
SA Jn JA Elp Jo (Comllary
PINT-pos >1 PINT >ip MP-TGNS BK
PINT Ss, Temporal- IWL
33
Time-then-IMP Sip PINT Si Temporal-IWL (Prop. g
Time-then-IMP s., PINT
Temporal- IWL (Prop. 2
RTRGN ",y, PINT (Prop. 3
RTRGN > PINT (Prop.
3
PINT-pos can be false positive (Prop.
PINT-pos can be false positive (Prop
Most expressive: RNN Temporal Relational Pooling (Prup. mm Appendix
The first part of this proposition can be proved by reducing the temporal link prediction problem into a temporal graph isomorphism test of the current graph adding the two temporal links separately. The second part of this proposition is proved by constructing pair of two models: one more expressive than the other in temporal link prediction, while being not more expressive in temporal graph isomorphism test. The proof and the construction of the counter-examples inside suggest that temporal graph isomorphism test is a more challenging task than temporal link prediction, as it requires global distinguishability rather than just local distinguishability of the involved nodes.
Next, we demonstrate that Time-then-IMP, the strongest among the three classes of temporal graph models suggested in [3] with the graph module of its time- tene-then-gee thhnng scheme being injective message passing (IMP) to ensure IWL expressiveness [39], is equally expressive as PINT and Temporal- in both temporal graph isomorphism test and temporal link prediction.
Proposition 2. Seme-then-IMP is equally expressive as PINT and Temporal- /WL in both temporal graph isomorphism test and temporal link prediction.
The proof establishes that all these models are equally expressive as Temporal- I IL in both temporal link prediction and temporal graph isomorphism test. The proposition suggests that Time-then- then-t----IM.... although utilizes a distinct form of base RNN to encode all historical features of nodes and edges (which comes at the cost of significantly more space needed to embed each edge), its expressivenes: is ultimately equivalent to the Temporal- IL class, which includes models like PINT.
We next show that RTRGN is more expressive than PINT, as well as the Temporal- WLL 1WL class: Proposition 3. RTRGN is strictly more expressive than the Temporal- /WL class represented by PINT in both temporal graph isomorphism test and temporal link prediction.
As we have shown, the expressiveness of all the previously mentioned models is bounded by the Cemporal-1WL. which, although powerful, can fail in certain cases. To illustrate this, we construct temporal graph isomorphism test task called Oscillating CSL (Figure 2 where all Temporal- WL models, including Time-ther of the graph snapshots and stacked graphs at each timestamp, which cannot be distinguished by WI. tests. RTRGN excels in this task due to the heterogeneity introduced in its revision Temporal- WI.
WWL fail. The difficulty of the task stems from the regular structure
computation, which enables its expressiveness to go beyond the limit of Temporal- I WL.
Proposition 4. PINT-pps can be false positive in both temporal graph isomorphism test and temporal link prediction, e.g., may incorrectly classify isomorphic temporal graphs as non-isomorphic.
On the other hand, we observe that PINT-pos can produce false positives (unlike the other models). Specifically, there are cases where PINT-pos mistakenly categorizes isomorphic temporal graphs as non-isomorphic, and incorrectly distinguishes two temporal links that should not be distinguishable. fails essentially because its positional feature is permutation-senssee models permutation-invarian.. which is a desirable property in graph model design [ 251 This further highlights the superiority of heterogeneous revision over augmented positional features.
while all other mentioned
Finally, we formulate a most expressive model that can always output the ground truth (Appendix B
"Note that, in our definition for both temporal link prediction and temporal graph isomorphism test, only node embeddings are considered. Time-then-IMP builds edge features. However, such edge features still do not contribute to distinguishing, for instance, between the two Oscillating CSL graphs in Figure 2 Junder temporal isomorphism test. This is because, at any given time, the set of neighbors for any node in either of the two graphs remains identical: two neighbors with consistently connected edge, two with the edge showing pattern of occurrence [1, 0, 1, O,...... ..... J. and two with pattern of occurrence [0, 1, 10.

---

C
C33
C2
C₁3
A synthetic temporal graph isomorphism test task called Oscillating CSL, where only RTRGN is expressive enough give the correct result. The task is distinguish the top and bottom temporal graphs, both of which oscillate but in different order between two regular structures called circular skip links (CSL). The right side shows the stacked view of the two temporal graphs.
Figure 2:
4 Related Works
Early approaches in dynamic graphs learning focused on discrete-time dynamic graphs (DTDGs). which consist of sequence of graph snapshots usually sampled regular intervals [27
42 They
employed techniques such as stacking graph snapshots and then applying static methods 19 1 31
and assembling snapshots into tensors for factorization 44 2
Among them, ROLAND
introduced hierarchical hidden states, but each state update is followed by a heavy finetuning of the entire model, which can be computationally expensive when applied to continuous-timg dynamic framework is directly applied to CTDGs, handling the lists of
graphs (CTDGs). In comparison, timed events, and can much more efficient.
DTDGs can always be converted to CTDGs without information loss. However, the high computation cost poses major obstacle for applying most DTDG methods to CTDGs. More and more research focuses CTDGs. Sequence- based methods such as DeepCoevolve E) Jodie [16], and Dyrep K2! utilize RNN to capture the evolution of node representations, while some other works 26 24 employ random walks to model CTDG, including CAWN [37] NAT [1]] caches the high-order neighbor information for computing joint neighbor features.
TGAT BH and TGN 23 were the first to introduce GNN for CTDGs. Subsequently, combining GNNs with RNNs for temporal graph embedding generation became mainstream idea. PINT (33 introduced MLP-based injective aggregators to replace attention-basee aggregators in TGN, GRU-
GCN analyzed three strategies combine GNN with RNN and classified them into time-and and-gragg
(e.g., 30 7 2),, time-then-gre -rr-hh (e.g., B8 and graph-then-tingg frameworks (e.g.. [27
Our heterogeneous revision leads to enhanced expressiveness. Similar ideas were adopted in static GNNs. For example, 43 introduced heterogeneity in the root node during message passing.
5
Experiments
5.1
Temporal Link Prediction on Benchmark Datasets
We evaluate the proposed RTRGN with the temporal link prediction task on 8 real-world datasets (7 public datasets well as private Ecommerce dataset that will be released along with this submission), and compare it against related baselines, including Dyrep [. Jodie [6.. TGAT BS)
TGN 22 CAWN 377. NAT 21,, GRU-GCN [5] and PINT 33 The evaluation is conducted in
two settings: the transductive which predicts links involving nodes observed during training, and the inductive which predicts links involving nodes that never observed during training.
The official implementations of different baselines can vary in their experiment settings, especially on the datasel preparation and the negative edge sampling. To ensure fair and consistent comparison, we calibrate the experiment settings of all baselines with the one used by TGN, which is the same as TGAT and PINT, but differs somewhat from other works such CAWN and NAT. The latter may
7

---

Table 2: Average Precision (AP, %) on temporal link prediction tasks with 1-layer models 1).
First and second best-performing methods are highlighted. Results are averaged over 10 runs.
Model
MovieL.ens
Wikipedia
Keddi
SocialE.. Im
Sociall.
UCLFSN
Ubantu
Eeurmmence
Dynep
=
S1.74=
2
Tranddacive
Jodie
78. 12.12+ 0.4
96.15 0.1
97.29 0.1
70:20
81.83 1.1
86,07 = 0.7
91.32 0.2
68. =
TGAT
6
98.26 0.2
51.97 0.6
30.75
73.01
81.69 0.3
65.13 0.5
97.58 0.2
98.30
0.3
91.06
90.18
83.60
CAWN
a 0.4
98.28 0.2
9 0.2
$4.62 0.4
83.49 0.7
90.03 0.4
64.58 0.1
NAT
75.85
96.27
0.1
98.71
65.84 0.4
91 11.35-1
90.86 0.5
0.2
GRU-GCN
84.70 0.2
96.27 0.2
98.09
86.02
81.22 2.5
90.51 0.4
86.52 0.2
79.
0.4
PINT
83.25 0.9
98.45 0.1
98.39 0.1
S0.97 2.2
84.94 3.4
02.68 0.5
80.50 4 0.1
80.36 0.3
KTRGN
50.55= 0.2
9
0.1
Dyrep
74.47 0.3
94.72 0.2
97.04 0.3
76.58 + 2.1
88. 49 0.6
50:43 1.2
71.49
53.59 0.7
Jodie
7
85.58 0.4
95.96 0.3
73.32
79.58 0.8
+ 0.8
83.81 0.3
61 61 0.6
Inductive
TGAT
06.33+00.4
83.82 0.3
96.42 0.3
52.17
30.63++0..1
66.89
78.922 0.5
64.58 0.8
TON
82.07 0.2
07.05 0.2
96.87 a 0.2
68.70 0.5
89.06
81.53 0.2
81.81 0.4
81.81 0.5
CAWN
74.50
97.70 0.2
97.37
7 0.4
0.5
89.65 a 0.4
63.30
NAT
77.56
97.74 0.4
97.19 0.7
86.16
85.32+
81.09 0.9
76.85 0.2
GRU-GGN
82.81 0.2
93.50 0.2
96.38 0.3
$3.76 1.8
79.21 4.5
85.45 0.6
73.71 0.5
78.54 0.2
PINT
97.
+
71.86
77.
RTRGN (ours)
85.03 0.2
98.06 = 0.2
98.26
01.73 0.7
92. 4
94.26 0.1
92.95 0.1
86.91
Table 3: Average Precision (%) on temporal link prediction tasks with 2-layer models (k 2).
Model
Movielens
WiLipedia
Reddit
Sociall: lm
SocialE.
UCI-FSN
Ubunt
Ecommerce
TGN
0..
18.38
98.55
91.63 0.3
91.50
86.69 0.3
92.12
0.2
NAT
80.04 1.2
98.
0.1
98.85 0.1
90.41 0.3
91.68 0.6
93.03 0.1
82.32
PINT
84.18
0.1
0.1
8.2
0.4
9.1
8
KIRGN
94.90 0.4
98.79 0.2
93.30
94.
98.04
9..
95.28
TGN
0.5
0.2
97.27
9.5
0.6
0.3
8..3 0.
NAT
97.73
97.32 0.1
90.87 0.2
90.56 0.9
8.6
0.8
78.72
PINT
81.95
96.39
96.59 0.2
8.7
79.79 1.6
0.3
0.2
80.30 1.0
KIRGN
93.37 0.3
98.28 0.2
97.76
931
93.99 0.2
9.1
9.1
92.87 0.1
lead to inflated results, with inductive performance surpassing transductive performance, potentially reaching 99% accuracy in CAWN and NAT. We set d= 10 for experiments. More details about the datasets, the baselines, and the experiment settings can be found in Appendix C
The results for the I-layer setting (k 1) are presented in Table 2 It is evident that our proposed RTRGN surpasses all baselines by a significant margin, suggesting substantial improvement. To delve deeper into the problem, we further examine the results for the 2-layer setting (Table { where we compare RTRGN against baselines that have demonstrated potentially better performance than other baselines in the I-layer setting. As we see, the performances of the basclines show limited improvement when transitioning from the I-layer to 2-layer setting, aligning with previous findings (38, PS By contrast, RTRGN consistently exhibits significant improvements in the 2-layer setting: the average gap of transductive AP between RTRGN and the second best method + +4.4%. The largest gap appears in Ecommerce dataset, which is +9.6%. The gap on Wikipedia is small probably due to a I-layer model already sufficient to give strong performance.
This indicates that layer design is important for temporal graph networks to more effectively leverage the power multiple layers. Another advantage, as shown in Figure 3 we found experiments that the training converges faster for larger k.
100
Valiestion AP (16
90
80
8
10
12
15
20
25
30
Epoch
Figure 3: The convergence trend for different number of layers k.
8

---

5.2 Temporal Graph Isomorphism Test
To validate the superior expressiveness of the proposed RTRGN against existing methods, we conduct experiments of temporal graph isomorphism tests two synthetic datasets. We run 4-layer models on testing graphs, where at each time step, we compute and store the embedding for each node. To check the isomorphism between two temporal graphs under model, gather the lists of generated embeddings (stacking in time for each node) of the two graphs and verify whether there exists a bijective mapping such that the two lists are identical (via sort and scan). If the lists identical, we conclude that the model outputs isomorphic (negative); otherwise, non-isomorphic (positive).
Oscillating CSL is synthetic temporal graph isomorphism test task, which is commonly used benchmark for assessing the expressiveness of GNNs [25 5]. Each graph in this task is composed of sequence of graph snapshots (of length 6) that correspond to the oscillation between 2 different prototypes randomly selected from { (C1.22...., }.
Here CN.s denotes a circular skip link (CSL) graph with N nodes and skip length The goal is to determine whether the temporal graph follows the pattern CN.,, + .2 is isomorphic to its reversed counterpart CN.., CN.s. (Figure
Comer
edge
Figure 4: (left) An illustration of the Hittite cuneiform signs. (right) An example where TGN and GRU-GCN fail to output non-isomorphic, due the special structure within the arrangement edges, i... two triangles versus a hexagon.
Cuneiform Writing is modified version of the Cuneiform graph dataset [4] (Figure 4 which consists of graphs representing Hittite Cuneiform signs. The dataset was originally derived from tablets, where individual wedges along with their arrangements were automatically extracted. We draw out arrangement edges with short spatial distances, while ensuring that each depth node has at most arrangement edges. To transform static graphs into temporal graphs, we adopt sequential edge generation that adds arrangement edges first, then the wedge edges. For each task, we randomly select 2 cuneiform signs with equal number of nodes. Refer to Appendix C for more details.
Table 4: Isomorphism test results. Non-isomorphic is regarded as positive. TNR is true negative rate.
Oscillating CSI.
Cuneiform Writing
Precision
Recall
TNR
Accuracy
AUC
Precision
Recall
TNR
Accuracy
AUC
TGN
0.00
0.00
100.0
100.0
74.19
79.80
GRU-GCN
0.00
0.00
100.0
16.67
50.0
100.0
95.44
100.0
96.43
97.61
PINT-pos
83.33
100.0
0.00
83.33
50.0
82.03
100.0
21.09
82.85
60.93
RTRGN (w/ HR)
0.00
0.00
100.0
16.67
50.0
100.0
95.41
100.0
96.43
97.61
RTRGN
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
The results are shown in Table 4 RTRGN achieves perfect accuracy in both experiments, attributed to its heterogeneous revision (HR). Notably, PINT-pos fails entirely correctly identify true negatives in the Oscillating CSL task. TGN and GRU-GCN on the other hand exhibit partial failures in accurately distinguishing challenging -somooooop graphs. One such failure case is illustrated in Figure !
5.3 Ablation Studies
We conduct set of ablation studies to dissect the impact of each proposed component in our RTRGN. The experiments are conducted on three representative datasets: MovieLens, Wikipedia, and UCI. The results for Moviel.nns are presented in Figure 5 while the results for the remaining two datasets, which validate the consistency of our findings, are included in Appendix D

---

k=1
k-2
Davelime cara Allaion
rovision
Dassines
Adnedaa an apdans
Abaition
100
AAratton
Abliliiss reviaiion
prats spaans
updint
Transductive AUC
90
90-
100
mresst
airr
we
cio
10
POTT
ctty
emm
sld win
wein
TDM
wen
with
tp
100
Figure Transductive AUC (%) on MovieLens dataset. Results averaged over 10 runs.
Ablation on state update. Our first ablation study is on (t-,, where we set (t-) in ( for k O, hence do not retain the hidden state but compute aggregation dynamically, denoted as w/o (t"). The results suggest that including the hidden state crucial for further improving performance when k > 1. As the second ablation study, we set r. (1) in which leads to a pure RNN design without neighbor aggregation, denoted w/o r (t). It results significant performance drops, indicating the criticality of integrating revisionary neighbor information in the message.
Ablation TR module. The rest ablation studies are performed the temporal revision module. As the first, we remove h (t) in ( denoted as w/o h (()). Interestingly, this setting exhibits only marginal performance drop and even slightly outperforms the setting denoted as w/o Ah Ah (t) where Ah R-1 (t) is removed instead. suggests that the effectiveness of revision can primarily rely on the state change of neighbors, not necessarily the neighbor states. This may be attributed to that the hidden states have already incorporated such information through previous messages. As the last (t) in (6). denoted as w/o r =f-1(t), (t). and use the homogeneous version of revision ( instead of the heterogeneous version 3 denoted as w/o HR. Both settings result in noticeable performance drops, indicating the benefits of incorporating revisions of neighbors in the TR module, as well as the introduction heterogeneity in revision.
two settings, remove r +(-((t)
We provide the theoretical analysis of the time and space complexity of RTRGN in Appendix A More experiments, e.g., ablation studies on subsampling amount d and practical run-time comparisons, can be found in Appendix
6 Conclusion
We have proposed new aggregation layer, named recurrent temporal revision (RTR) for temporal graphs. We have shown that it leads to superior expressiveness that goes beyond Temporal- WL. We have also demonstrated that it can lead to significant improvements over current state-of-the- -arthe-art methods. As an important breakthrough, we have demonstrated that it enables effective utilization of multiple aggregation layers, while existing methods have difficulties effectively harnessing the power of multiple layers.
7
Acknowledgements
This research is supported in part by the National Natural Science Foundation of China (U22B2020); the National Research Foundation, Singapore and DSO National Laboratories under the Al Singapore Programme (AISG Award No: Engineering (AME) Programmatic Fund (No. A20G8b0102), Singapore; the Shanghai University of Finance and Economics Research Fund (202111006)
the RIE 2020 Advanced Manufacturing and
References
[1] Nahla Mohamed Ahmed and Ling Chen. efficient algorithm for link prediction in temporal uncertain social networks. Information Sciences, 331:120-133 1122--36,,001 2016.
10

---

[2] Jinyin Chen, Xueke Wang, and Xuanheng Xu. Gc-lstm: Graph convolution embedded Istm for dynamic network link prediction. Applied Intelligence, pages 1-16, 2022.
[3] Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. Deep coevolutionary network: Embedding user and item features for recommendation. arXiv preprint arXiv: (ed:::60033555 2016.
[4] Songgaojun Deng, Shusen Wang, Huzefa Rangwala, Lijing Wang, and Yue Ning. Graph message passing with cross-location attentions for long-term ili prediction. arXiv preprint arXiv:1912.10202. 2019.
[5] Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In Proc. ICML. pages 7052-7076. PMLR. 2022.
[6] Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge- Based Systems, 187:104816 2020.
[7] Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. arXiv preprint arXiv: / 2018.
[8] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in NeurlPS, 30, 2017.
[9] Xiangman He, Kuan Deng. Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proc. SIGIR, pages 639-648, 2020.
[10] Nahla Mohamed Ahmed Ibrahim and Ling Chen. Link prediction in dynamic social networks by integrating different types of information. Applied Inielligence, 42:738-750, 2015.
[11] Guangyin Jin, Qi Wang, Cunchao Zhu, Yanghe Feng, Jincai Huang, and Jiangping Zhou. Addressing crime situation forecasting task with temporal graph convolutional neural network approach. In Proc. ICMTMA, pages 474-478. IEEE, 2020.
[12] Seyed Mchran Kazemi, Rishab Goel, Sepehr Eghbali, Janahan Ramanan, Jasprect Sahota, Sanjay Thakur, Stella Wu, Cathal Smyth, Pascal Poupart. and Marcus Brubaker. Time2vec: Learning a vector representation of time. arXiv preprint (XXXv:1907005322 2019.
[13] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: |rXiv: /609.02907 2016.
[14] Nils M Kriege, Matthis Fey, Denis Fisseler, Petra Mutzel, and Frank Weichert. Recognizing cuneiform signs using graph based methods. In International Workshop on Cost-Sensitive Learning, pages 31-44. PMLR, 2018.
[15] Nils M Kriege, Matthias Fey, Denis Fisseler, Petra Mutzel, and Frank Weichert. Recognizing cunciform signs using graph based methods. In International Workshop on Cost-Sensitive Learning, pages 31-44. PMLR, 2018.
[16] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proc. SIGKDD, pages 1269-1278, 2019.
[17] Jia Li, Zhichao Han, Hong Cheng, Jiao Su, Pengyun Wang, Jianfeng Zhang, and Lujia Pan. Predicting path failure in time-evolving graphs. In Proc. SIGKDD, pages 1279-1289, 2019.
[18] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv: 1707,0196, 2017.
[19] David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proc. CIKM, pages 556-559, 2003.
[20] Mingxuan Lu, Zhichao Han, Zitao Zhang, Yang Zhao, and Yinan Shan. Graph neural networks in real-time fraud detection with lambda architecture. arXiv preprint arXiv:2110.04559, 2021.
[21] Yuhong Luo and Pan Li. grgghborhood-wwarg scalable temporal network representation learning.
In Proc. LoG, 2022.
[22] Yao Ma, Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proc. SIGIR, pages 719-728, 2020.
[23] Yunpu Ma, Volker Tresp, and Erik A Daxberger. Embedding models for episodic knowledge graphs. Journal of Web Semantics, 59:100490, 2019.

---

[24] Sedigheh Mahdavi, Shima Khoshraftar, and Aijun An. dynnode2vec: Scalable dynamic network embedding. In 2018 IEEE International Conference on Big Data, pages 3762-3765. IEEE, 2018.
[25] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Proc. ICML, pages 4663-4673, PMLR, 2019.
[26] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion Proc. The Web- Conf, pages 969-976, 2018.
[27] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kaneza- shi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In Proc. AAAI, volume 34, pages 5363-5370, 2020.
(28) Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. ICML. 2020 Workshop on Graph Representation Learning, 2020.
[29] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In Proc. WSDM, pages 519-527, 2020.
[30] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In Proc. ICONIP, pages 362-373. Springer, 2018.
[31] Umang Sharan and Jennifer Neville. Temponall-relaioonal classifiers for prediction in evolving domains. In Proc. ICDM, pages 540-549. IEEE, 2008
[32] Hava T Siegelmann and Eduardo D Sontag. On the computational power of neural nets. In Proc. COLT, pages 440-449, 1992.
[33] Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph networks. Proc. NeurlPS, 35:32257-32285 2022.
[34] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In Proc. ICLR, 2019.
[35] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20):10 1ee:111044500 2017.
[36] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collabo- rative filtering. In Proc. SIGIR, pages 165-174 2019.
[37] Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974, 2021.
[38] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. In Proc. ICLR, 2020.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. ICLR, 2019.
[40] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proc. ICML, pages 5453-5462. PMLR, 2018.
[41] Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proc. SIGKDD, pages 974-983, 2018
[42] Jiaxuan You, Tianyu Du, and Jure Leskovec. Roland: graph learning framework for dynamic graphs. In Proc. SIGKDD, pages 2358-2366, 2022.
[43] Jiaxuan You, Jonathan M Gomes-Selman Rex Ying, and Jure Leskovee. Identity- graph neural networks. In Proc. AAAI, volume 35, pages 10737-10745, 2021.
[44] Wenchao Yu, Wei Cheng, Charu C Aggarwal, Haifeng Chen, and Wei Wang. Link prediction with spatial and temporal consistency dynamic networks. Proc. IJCAI, pages 3343-3349, 2017.
12

---

[45] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint 1803.07294 2018.
13


Reviews:
[{"review_id": "aF1lCXppT6", "reviewer": "Reviewer_gXqR", "summary": "The paper introduces a novel framework called Recurrent Temporal Revision (RTR) to address the challenge of neighbor subsampling in temporal graphs, an issue commonly encountered in real-world applications like social networking, recommender systems, traffic forecasting, and crime analysis. RTR serves as a standard building block for any temporal graph network, utilizing a recurrent neural network to integrate all neighbor information through a hidden node state. This hidden state mitigates the problem caused by neighbor subsampling and aims to capture complete neighbor information.\n\nThe paper also introduces a new concept of \"temporal revision\" to update the hidden state by capturing the state changes of neighbors. To further boost the theoretical expressiveness of this technique, the authors propose incorporating heterogeneity into temporal revision by recursively identifying and marking certain nodes as specialties in the revision calculation process.\n\nThe authors suggest that this new approach offers superior expressiveness in terms of temporal link prediction and temporal graph isomorphism test, a claim that is backed by theoretical proofs and experimental results. Additionally, they provide a new Ecommerce dataset for evaluating temporal graph models in real-world settings. Their experimental results indicate the proposed framework's significant improvement over state-of-the-art methods, particularly as the number of aggregation layers increases.", "questions": "From the proof of proposition 3, the extra expressiveness of the proposed model comes from the heterogenous revision which could be in principle added to other IMP-TGN representation model. Can we conclude that heterogeneity help improve expressiveness of temporal graph model?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The authors introduce innovative ways of evaluating the expressiveness of graph algorithms by defining two novel metrics: the temporal graph isomorphism test and the temporal graph link prediction. They apply these new measures to several state-of-the-art models, successfully establishing an equivalence between Temporal-1WL and these baseline models which implies the shared drawbacks of these models.\n- The paper presents a unique temporal learning model grounded on two inventive ideas: 1) Utilizing hidden states to retain aggregated information which is subsequently updated through a temporal revision layer, and 2) Embedding heterogeneity by giving special treatment to the central node during the recursive revisioning process. The authors compellingly argue that their proposed method outperforms state-of-the-art models in terms of expressiveness, as defined within the context of this paper.\n- The proposed method demonstrates promising performance in real-world temporal graph tasks, particularly in the temporal link prediction task. Additionally, it excels in the graph isomorphism test examples, reinforcing its potential for practical applications in various fields.", "weaknesses": "- The rationale behind the new definition of expressiveness isn't effectively conveyed in the paper. While it's true that there isn't a universally accepted definition for the expressiveness of a temporal graph model at present, the paper falls short in clarifying why its proposed isomorphism test improves upon existing ones. The lack of a clear explanation leaves a gap in understanding the superiority of the proposed metrics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback which we will consider seriously in our revised paper. \n\n**Regarding your consideration of the rationale behind our new definition of expressiveness.** We develop the set of new expressiveness measures mainly for the following two reasons. First, as you have reckoned, there is currently no universally accepted definition for the expressiveness of a temporal graph model, especially for temporal link prediction. Our definition is an effort towards addressing this gap, providing a consistent definition for the expressiveness of both the temporal graph isomorphism test and the temporal link prediction. Second, existing definitions of expressiveness are relatively complex. By contrast, our proposed ones are concise and straightforward, avoiding the introduction of Identifiable Set as in [5] and Temporal Computation Tree as in [33]. We will reorganize related text to make the rationale behind more clear. \n\n**Regarding your question about heterogeneity.** Indeed, previous studies [43], as mentioned in our related work, have shown that incorporating heterogeneity is a principal approach to enhancing the expressiveness of static graph models. Our work in a sense has extended this finding to temporal graph models. We believe that it could potentially also lead to improvements in expressiveness if integrated into other IMP-TGN models. However, it requires further verification. "}, {"review_id": "1xuVzNe0oL", "reviewer": "Reviewer_sEkX", "summary": "In this paper, the authors propose a novel aggregation layer based on a recurrent neural network dubbed recurrent temporal revision (RTR) for temporal graph networks to solve the dynamic temporal graph embedding problem. Specifically, a new aggregation function is proposed, which encodes neighbor state information and event information. This paper also proposes two expressive measures and uses them to demonstrate theoretically the difference from previous work. Empirical results on several well-known datasets show the effectiveness of the proposed method.", "questions": "1.\tSome symbols and formulations need to be clarified:\n    a)\tEq. (4) should be accurately formulated.\n    b)\tr_t^0(t) in Line 148 should be a vector. \n2.\tWhich variance or function in Eq3 and Eq4 can reflect the two proposed measurements?\n3.\tThe organization of Section 3 should be improved. Each subsection ends abruptly without a clear takeaway message. \n4.\tTable 1 is hard to read.\n5.\tThe differentiation between the current work and previous works (especially TGAT, and TGS) need to be explained more clearly.\n6.\tWhy do the 2-layer experiments only run in selected datasets? What’s the selection criterion?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1．\tThe explanations of the components of the approach are clear and detailed.\n2．\tThis work uses the proposed two measurements, and theoretically, fully justifies the difference from the previous methods. It also includes algorithm time complexity and running time analysis\n3．\tAblation settings are very detailed.\n", "weaknesses": "1.\tIt is unclear which part of the ablation experiment corresponds to which of the two proposed measurements. It would be good to clarify that.\n2.\tIt’s better to have an Algorithm line by line to clearly correspond to specific formulae and modules for Figure 1b.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback which we will consider seriously in our revised paper. \n\n**Regarding your confusion about the correspondence between the ablation experiments and the two proposed measurements.** We would like to clarify that while the first two experiment sections (5.1 and 5.2) are dedicated to studying the expressiveness of temporal link prediction and temporal graph isomorphism test respectively, the entire ablation experiment section (5.3) was focused on the temporal link prediction setting: all the ablation experiments therein are conducted on the temporal link prediction task and measured by the average precision of temporal link prediction. Note that our theoretical analysis has suggested that the heterogeneous revision (HR) is the essence of improved expressiveness in the temporal graph isomorphism test, which is also verified by the results in Table 4 (w/o HR). This is the main reason why our ablation studies were primarily focused on temporal link prediction. Another reason is that most real-world problems revolve around link prediction and most datasets are also predominantly suited for the link prediction task. \n\n**Regarding your suggestion to enhance the illustration with the help of algorithm pseudocode.** We appreciate this constructive feedback, and will provide such an algorithm alongside and make necessary improvements to Figure 1b in our revised paper. \n\n**Regarding your question 1.** For a more accurately formulated Eq. (4), we would like to refer you to Appendix A.2, where we have provided detailed implementations of all learnable functions we mentioned in the main paper. We intended to present our framework from a general perspective in the main paper, deliberately separated the implementation details to the appendix, to encourage the exploration of potentially improved implementations in the future. Considering the importance of implementation details to a full understanding as suggested, we will mention the implementation ideas in the main paper and refer readers to the Appendix for more details. And yes, $r_t^0(t)$ in Line 148 should be a vector. We will enhance the notation, as well as other related ones, to make it clear. \n\n**Regarding your question 2.** Strictly speaking, the proposed expressiveness measurements are general and independent of the proposed model. We assume you mean which formula of the proposed model contributes to the improved expressiveness. In fact, the heterogeneous revision (Eq. (6)) is the key to the theoretical improvement of expressiveness, when assuming the full neighborhoods are involved in aggregation -- which is the common practice in theoretical analysis. While practically, as baseline methods typically only involve subsampled neighbors, our proposed Recurrent Temporal Revision framework (Eq. (3) - (5)) contributes to the majority of practical improvements of performance, due to its better modeling of neighborhood information. \n\n**Regarding your question 3.** Thank you for this valuable feedback. We will add takeaway messages to each subsection. \n\n**Regarding your question 4.** We will briefly describe the main message of Table 1 in its caption. We will also try to improve its coloring and layout for better readability. \n\n**Regarding your question 5.** We assume by TGS, you were referring to TGN. Despite other minor differences, the most important distinction between our proposed model and baseline models like TGN and TGAT lies in the aggregation strategy. We adopt the proposed Recurrent Temporal Revision, while TGN and TGAT employ the classic temporal aggregation. As illustrated in Figure 1a, classic temporal aggregation typically involves subsampled neighbors in each step, which leads to incomplete and biased neighbor information. By contrast, the proposed RTRGN, ideally, can integrate the whole information of neighbors. We will clarify this in the revised paper. \n\n**Regarding your question 6.** We selected 4 out of 8 datasets, due to limited computational resources, as representative which have covered different characteristics such as bipartite/non-bipartite and with/without edge features. We now have the full experiment results on all 8 datasets, which are provided in the uploaded PDF in the global rebuttal. As we can observe, the basic trend remains the same as before. Baseline methods show limited improvement when transitioning from the 1-layer setting to the 2-layer. By contrast, our proposed RTRGN exhibits significant improvements in the 2-layer setting (except for Wikipedia and Reddit where the precision of the 1-layer model is already as high as 98\\% and the 2-layer model may suffer from overfitting) and clearly outperforms all baselines. "}, {"review_id": "kK1Vs8NRbQ", "reviewer": "Reviewer_UPBh", "summary": "The paper studies the problem of temporal graph learning. The authors propose the recurrent temporal revision (RTR) layer, which involves learning a hidden state for each node and utilizing recursive neural networks to integrate information from all neighbors. Additionally, the authors introduce heterogeneity in RTR and theoretically demonstrate that this heterogeneous revision enhances expressiveness beyond Temporal-1WL.", "questions": "Please refer to W1-W3.", "limitations": "I have some concerns about the scalability of the proposed method.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The majority of the paper is easy to follow.\n\nS2. Experimental results show that RTR outperforms state-of-the-art methods.\n", "weaknesses": "W1. My main concern is with the motivation of paper. Why do we need to make each node embrace complete neighbor information? In real-world recommendation system data, the browsing/purchasing tendencies of users are often more closely related to their short-term interests. The inclusion of excessive and outdated information may introduce more noise to the model instead.\n\nW2. The proposed RTR can be understood as weight learning and important neighbor selection based on complete historical information. Could changing the sampling strategy from selecting k nearest neighbors to selecting k most important historical neighbors for methods like TGN also result in similar performance improvements?\n\nW3. The paper lacks an analysis of time complexity as well as a comparison of the model's parameter count.\n\nMinor comments\n\nM1. Page 1, Line 16: social network, recommender system -> social networks, recommender systems\n\nM2. Page 4, Line 160: an learnable function -> a learnable function\n\nM3. Page 8, Figure 4 caption: TGN and GRU-GCN fails to -> TGN and GRU-GCN fail to\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback which we will consider seriously in our revised paper. \n\n**Regarding your comment W1.** We would like to emphasize that long-term user behavior has been a major focus in recommender systems. Numerous studies, such as [R1, R2, R3, R4, R5], have demonstrated its effectiveness in improving the accuracy of user behavior modeling. While it is true that short-term behaviors can have a significant impact on a user's near-future actions, they come with limited volume and thus may not fully capture the preferences of users over time, which may impair the performance in more general scenarios. The hidden state in our proposed RTRGN will be fed with the entire interaction sequence under a recurrent update scheme, which enables it to flexibly focus on either long-term or short-term behaviors based on the characteristic of the problems/datasets at hand. We will discuss more about the long-term and short-term trade-off and further explain the motivation behind our approach in the revised paper. \n\n**Regarding your question in W2.** Switching from k nearest neighbors to k most important historical neighbors could potentially benefit methods like TGN. However, 1) a fixed k can limit its performance. By contrast, RTRGN with its RNN and hidden state could potentially take a broader range of historical information into account; 2) accurately and effectively calculating/maintaining the k most important neighbors of dynamically evolving nodes can be time-consuming and challenging. In comparison, RTRGN with RNN can use simple nearest sampling to efficiently model the entire interaction history. \n\n**Regarding your question W3 and your concern about the scalability.** We would like to note that we have a thorough theoretical analysis of both the time and space complexity in Appendix A.4. Furthermore, we have practical run-time comparisons on real-world datasets, which can be found in Appendix D.6. To ensure easy access to this information, we will highlight the references to Appendix A.4 and D.6 in the revised paper. We will also include a comparison of the parameter counts of models. It is important to note that a substantial portion ($>$90\\%) of the parameters in temporal graph models are the base embeddings (the node-wise hidden states of the base RNN, which are non-trainable, updated by the base RNN). An RTR layer has roughly 75\\% more parameters than a TGN layer of the same configuration, where the increment of trainable parameters is mainly attributed to the additional state transition functions (Eq. (5)) and message function (Eq. (4)) introduced in RTRGN. When considering the whole model, further including the parameters of the base GRU and the time encoders, the growth ratio of trainable parameters of RTRGN compared with TGN would be less. As an example, when the hidden state dimension is 172, a 2-layer RTRGN model has about 2M trainable parameters, while a classic 2-layer TGN model with the same setting contains 1.57M trainable parameters. \n\nWe sincerely appreciate your valuable feedback and hope our responses could largely address your concerns. \n\n\n[R1] User behavior retrieval for click-through rate prediction, SIGIR 2020. \n\n[R2] Search-based user interest modeling with lifelong sequential behavior data for click-through rate prediction, CIKM 2020.\n\n[R3] Adversarial filtering modeling on long-term user behavior sequences for click-through rate prediction, SIGIR 2022.\n\n[R4] Sampling is all you need on modeling long-term user behaviors for CTR prediction, CIKM 2022.\n\n[R5] TWIN: TWo-stage Interest Network for Lifelong User Behavior Modeling in CTR Prediction at Kuaishou, arXiv 2023."}, {"review_id": "ZhWC8SeDwR", "reviewer": "Reviewer_2aAk", "summary": "Temporal graphs are more accurate for modeling real-world scenarios compared to static graphs, but the current approach of extending neighbor aggregation from static graphs to temporal graphs is computationally expensive when considering all historical neighbors. To address this, the authors propose a novel framework that uses recurrent neural networks with node-wise hidden states to integrate information from all historical neighbors for each node, ensuring complete neighbor information without subsampling biases.", "questions": "1. Eq.3, 4 and 5 all refer to arbitrary learnable function, could you please specify what function is used in this paper?\n\n2. In the experiment shown in Table 3, is it possible to display the results of all datasets?", "limitations": "The authors adequately addressed the limitations. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The model proposed by the authors looks reasonable, at least  their experiments suggest so.\n\n2. The authors do a good job in describing the model. They propose two measures of expressiveness for temporal graph models, specifically in the context of temporal link prediction and temporal graph isomorphism tests. They establish a theoretical connection between these measures and demonstrate the superior expressiveness of their framework, while also presenting new findings on the expressiveness of other baseline methods.\n\n3. The ablation studies display the positive effect of each mechanism.", "weaknesses": "Some concerns in this paper should be discussed precisely. \n\n1. In introduction, the heterogeneity in temporal revision is not explained.\n\n2. Figure 1 lacks a specific description. The other baselines and the framework in this paper can be specified in the legend.\n\n3. This paper lacks a description of Table 1. The authors can add a description of Table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback which we will consider seriously in our revised paper. \n\n**Regarding your comment on weakness 1.** Thank you for this valuable feedback. We will add a simple explanation of what  heterogeneity means in the context of temporal revision. In simple terms, it means we will treat self-probing nodes differently in revision calculation. \n\n**Regarding your comment on weakness 2.** In our revised paper, we will refine the legend and caption to more clearly indicate which figure illustrates which. \n\n**Regarding your comment on weakness 3.** Thank you for this valuable feedback. We will provide a summary of the results and the main insights therein in the caption of Table 1. \n\n**Regarding your question 1.** We would like to refer you to Appendix A.2, where we have provided detailed implementations of all learnable functions we mentioned in the main paper. We will mention the implementation ideas in the main paper and refer readers to the Appendix for more details. \n\n**Regarding your question 2.** We selected 4 out of 8 datasets, due to limited computational resources, as representative which have covered different characteristics such as bipartite/non-bipartite and with/without edge features. We now have the full experiment results on all 8 datasets, which are provided in the uploaded PDF in the global rebuttal. As we can observe, the basic trend remains the same as before. Baseline methods show limited improvement when transitioning from the 1-layer to the 2-layer setting. By contrast, our proposed RTRGN exhibits significant improvements in the 2-layer setting (except for Wikipedia and Reddit where the precision of the 1-layer model is already as high as 98\\% and the 2-layer model may suffer from overfitting) and clearly outperforms all baselines. \n\nWe sincerely appreciate your valuable feedback and hope that our responses could adequately address your concerns. "}]

Author rebuttal:
We sincerely thank all the reviewers for their constructive feedback. We provide the extended Table 3 in the attached PDF, while all other concerns reviewers raised are addressed in their respective rebuttals. 

Meta-review: This work proposes a novel aggregation layer based on a recurrent neural network dubbed recurrent temporal revision (RTR) for temporal graph networks. Specifically, the new aggregation function encodes neighbor state information and event information. This paper also proposes two expressive measures and uses them to demonstrate theoretically the difference from previous work.

This paper provides a substantial improvement in our understanding of temporal graph representation learning. After reading the paper in depth, I found the analysis in the paper both well-written and insightful (the Oscillating CSL example is very good. I believe Proposition 2 is incorrect but that does not detract from the rest of the paper). The reviews and rebuttals further solidify this is a good paper.

Proposition 2 seems incorrect: The error in the proof is to assume that Time-then-graph in [5] proses to map the set of edges. Time-then-graph [5] works in the Oscillating CSL since the authors propose encoding the edges as a sequence "edge attributes are sequences of non-existing (0) and existing (1) over time", not sets of edges. The time-then-graph of GRU-GCN results in Table 4 are probably due to an implementation choice of the authors, not a limitation of Time-then-graph. We trust the authors will address this misunderstanding in the camera ready. This does not detract from the paper.
Decision: Accept (poster)