Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs
Authors: Ming Jin
Yuan-Fang Li
Shirui Pan
Venue: NeurIPS 2022 Accept (2022)
Keywords: dynamic graph
graph representation learning
temporal walk
graph motif

Abstract: Continuous-time dynamic graphs naturally abstract many real-world systems, such as social and transactional networks. While the research on continuous-time dynamic graph representation learning has made significant advances recently, neither graph topological properties nor temporal dependencies have been well-considered and explicitly modeled in capturing dynamic patterns. In this paper, we introduce a new approach, Neural Temporal Walks (NeurTWs), for representation learning on continuous-time dynamic graphs. By considering not only time constraints but also structural and tree traversal properties, our method conducts spatiotemporal-biased random walks to retrieve a set of representative motifs, enabling temporal nodes to be characterized effectively. With a component based on neural ordinary differential equations, the extracted motifs allow for irregularly-sampled temporal nodes to be embedded explicitly over multiple different interaction time intervals, enabling the effective capture of the underlying spatiotemporal dynamics. To enrich supervision signals, we further design a harder contrastive pretext task for model optimization. Our method demonstrates overwhelming superiority under both transductive and inductive settings on six real-world datasets.

Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs
Ming Jin Monash University ming. jin@monash edu
Yuan-Fang Monash University yuanfang. 1i0monash.o edu
Shirui Pan Griffith University s. pan@griffith edu.au au
Abstract
Continuous-timg dynamic graphs naturally abstract many real-world systems, such as social and transactional networks. While the research on continuous dy- namic graph representation learning has made significant advances recently, neither graph topological properties nor temporal dependencies have been well-considered and explicitly modeled in capturing dynamic patterns. In this paper, we introduce a new approach, Neural Temporal Walks (NeurTWa) for representation learning continuous-ting dynamic graphs. By considering not only time constraints but also structural and tree traversal properties, our method conducts spatiotemporal- biased random walks retrieve a of representative motifs, enabling temporal nodes to be characterized effectively. With component based on neural ordinary differential equations, the extracted motifs allow for rregularlyssampled temporal nodes to be embedded explicitly over multiple different interaction time intervals, enabling the effective capture of the underlying spatiotemporal dynamies. To enrich supervision signals, we further design harder contrastive pretext task for model optimization. Our method demonstrates overwhelming superiority under both transductive and inductive settings on six real-world datasets
Introduction
Continuous-time dynamic graphs (CTDGs) consist of temporal events with respect to nodes (e.g., node addition/deletion) and edges (i.e., temporal interactions), which naturally arise in many real- world systems such as social networks and knowledge graphs [13, 32]. Traditional studies in dynamic graph modeling manually extract expressive patterns that are beneficial for understanding the crucial laws behind [36]. For example, two people are likely to know each other if they have common friend (Figure 1). Such dynamic graph motif describes how social connections are established [31]. Other expressive patterns, such as feedforward control loops, have also been investigated [20]. However, manually extracting motifs expensive, time-consuming. and requires domain knowledge, thus hindering the learning dynamic graphs with more complicated laws [36].
The advent of graph neural networks (GNNs) makes it possible to understand more complicated graphs by automatically learning the laws behind [40, 42]. While GNNs have demonstrated great success in modeling static graphs. the research on dynamic graphs is still nascent. Current research on dynamic graph neural networks (DGNNs) faces fundamental challenges. Firstly, the entangled spatial and temporal dependen- cies in real-world CTDGs typically need a specific design to model, preventing the direct use of
Temporal M
f2
Dynamic
temporal neighbor tend to be connected in the future
Figure 1: Temporal walks capture the law
Corresponding Author.
Code available at https/uuwbmmmm/iieee/eeeeeaaaaa Temporal Walks
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

off-the-shelf GNNs. To overcome this barrier, previous works simplify CTDGs to series of static
graph snapshots with uniform time intervals (i.e., discrete- dynamic graphs, DTDGs) [24, 29]. However, this approximation compromises the modeling precision. Although [15] and [34] propose to learn on CTDGs directly, the inductiveness of the patterns they captured is not guaranteed because node identities are directly involved in their modeling process. Some recent methods [38, 27, 36] attempt to alleviate this issue. However, they only consider time but not topological and tree traversal properties when sampling temporal neighbors, limiting their ability to extract diverse and expressive patterns from dynamic systems. Secondly, temporal events in CTDGs occur irregularly (e.g., nodes and interact with b at different timestamps in Figure 1), resulting in a significant challenge in modeling temporal dependencies. Previous works typically bypass this challenge with the time encoding [38] to enable the use of message passing [38, 27] or sequence models (15,36], However, time encoding hurts model performance as temporal dependencies are modeled implicitly.
To tackle the above challenges, we propose the Neural Temporal Walks (NeurTWs) method for representation learning on CTDGs, which extracts and encodes informative dynamic graph motifs composed of irregularly-sampe sptaiotemporal-bine -obaadd bbassdd random walks to extract diverse and expressive patterns from a CTDG by not only considering time constrains but also topological properties and tree traversals, allowing the sampler to be better aware of the importance of temporal neighbors while maintaining the exploration and exploitation trade-off. To explicitly model temporal dependencies and capture essential dynamic temporal nodes are
temporal nodes. Specifically, motivated by [36], we propose
laws more effectively, the extracted motifs consisting of irregularly-samppl encoded with the proposed continuous evolution and instantaneous activation processes to learn time-aware node representations. The former process learns latent spatiotemporal dynamics across multiple interaction time intervals with ordinary differential equation (ODE) function, and the second process regularizes the latent state trajectories with those ireeuulaly-samppled observations.
On this basis, we acquire time-aware node embeddings by retrieving and encoding neighboring representative dynamic graph motifs, where a contrastive objective can be naturally designed to optimize NeurTWs by maximizing the mutual information between interacting temporal nodes. Compared with most existing works that use a simple link prediction objective, this harder contrastive pretext task helps enrich supervision signals, thus lifting the learning ability of NeurTWs.
On five benchmark datasets and a new dense e-commerce dataset, our method significantly and consistently outperforms all state-of-the of-the-art methods in general. Specifically, it surpasses the strongest baselines by around 3% and 5% in all transductive and seven out of eight inductive link prediction tasks. It also achieves the best on-par performance on dynamic node classification tasks. In summary, our technical contributions are three-fold: (1) We propose novel spatiotemporal-bine random walks to extract diverse and expressive patterns from CTDGs by considering not only time constraints but also topological and tree traversal properties; (2) We introduce a new perspective temporal nodes, explicitly and better modeling the underlying spatiotemporal dynamics: (3) We integrate contrastive learning into dynamic graph modeling to enrich supervision signals, which lifts the learning ability of our model.
to encode dynamic graph motifs composed of irregularly-sample
2 Related Work
Dynamic Graph Neural Networks (DGNNs). Existing DGNNs can be broadly classified into two categories based on their inputs. Discrete-time DGNNs operate over sequence of evenly-sampled static graph snapshots, where different strategies are proposed to model spatial and temporal clues, e.g., combining GNNs with sequence models [30, 24, 5, 29]. Our work relates to the second category, continuous-time DGNNS, where time-dependent node or edge embeddings are learned directly on CTDGs. Among these works, an in-demand design updates latent node states by aggregating k-hop neighborhood information with temporal message passing. For instance, TGAT [38] samples a set of k-hop temporal neighbors and proposes learnable time encodings to preserve time information in message passing. TGN [27] further equips TGAT with node memory update mechanism as in [15]. Another line of research leverages random walks to learn on CTDGs. Specifically, CTDNE [23] is the first to propose CTDG embedding method with temporal walks. CAWs [36] extend this concept with anonymous temporal walks and uses a recurrent net to learn walk embeddings that are further aggregated when calculating interactive representations. Our method is different from prior walk- based approaches three aspects: (1) We propose a new perspective on sampling temporal walks. While prior arts only consider time constraints, our method leverages multidimensional information,

---

allowing the model to explore diverse and expressive patterns from CTDGs; (2) We propose a novel and intuitive motif embedding method to model latent spatiotemporal dynamics among irregularly- sampled temporal nodes on CTDGs without relying on time encodings, which allows temporal dependencies to be modeled explicitly; (3) We replace the simple link prediction- learning objective with a more challenging contrastive pretext task, which helps provide stronger supervision signals.
Neural Ordinary Differential Equations (NODEs). Chen et al. [2] propose a new paradigm that generalizes discrete deep neural networks by parameterizing the derivative of latent states. This concept has been applied in research areas including time series forecasting [12, 28] and computer vision [9. 1]. Recently, some works have extended NODEs to the graph domain, where most consider building deeper GNNs while alleviating the negative impacts of over- soo-hhng [37, 25]. Notably, the time information is absent among those works. In dynamic graph learning, most ODE-based works focus on discrete-time settings [12, 6, 8). and only a few extend NODEs to learn on CTDGs [7]. In this paper, inspired by the research on time series forecasting [28]. we propose NeurTWs to encode extracted motifs with rrrgularly-samplee temporal nodes on CTDGs, which is fundamentally different from [7]: We directly integrate over multiple interaction time intervals to explicitly model the latent spatiotemporal dynamics across different temporal nodes with an ODE function, while [7] relies on a time encoding- encoding-assisted assisted message passer to learn from historical temporal events.
Graph Contrastive Learning (GCL). Recently, GCL has achieved great success in graph self- supervised learning [19]. Most existing works are on static graphs [35, 435,43,444 43, 44, 11]. While some studies have explored the possibility of dynamic graph contrastive learning, many of them are on DTDGss For example, STGCL [18] enhances the model's forecasting ability with DTDG augmentations and an auxiliary contrastive loss. A similar design also exists in [41, 39] and [26]. On CTDGs, Tian et al. [33] propose to maximize the agreement between time-aware node embeddings at different time points. In DySubC [10], the mutual information between node and its surrounding temporal subgraphs is maximized. Different from these works, we design an effective pretext task for model optimization, where the mutual information between two nodes in an interaction is maximized. Meanwhile, we push nodes away in the embedding space if there are no temporal interactions.
3 Problem Formulation
We start by formally introducing the learning problem CTDGs. A complete notation table is in Appendix A. This paper defines a CTDG as a stream of temporal interactions, i.c., G {(s,, where each interaction has two nodes at a specific time, e.g., (e,, t.) == ((u,, ) f:), t, Rt. As many real-world CTDG datasets are unattributed and for simplicity, we first assume these temporal interactions are without node and edge attributes and later will discuss how method is extended to learn on attributed CTDGs. Facing the challenge of lacking label information, DGNNs are typically supervised by temporal interactions [45]. Thus, dynamic link prediction is widely adopted testbed to evaluate how accurate a DGNN is in predicting future interactions with the observation of historical events. Specifically, given two nodes u and at time & in G, we aim learn their time-aware embeddings h2 and h.. where the presence of an interaction between them can be predicted with downstream classifier, i.e., Fu,n,t clf( Jt.). The ground truth yu,,,t = if there exists an interaction between u and v at time otherwise yn,n,t = O. On this basis and with learned time-aware node representations, conducting other downstream tasks, such as dynamic node classification with another classifier, is also feasible.
4
The Proposed Method: Neural Temporal Walks
4.1 Preliminaries: Temporal Walks and Dynamic Graph Motifs
Given a dynamic graph G, we define a motif as a subset of temporal nodes with their interactions within defined time range [14], e.g., 0 < S q- As those motifs reflect certain dynamic laws in CTDG, it is desirable to characterize a temporal node with its surrounding motifs.
Definition 4.1.1 (Temporal Walk). Given a dynamic graph G, we denote the interactions that are
directly associated with node u before cut time as G,,t = ((e,t') I' < I, u E e, (e, E 9)- A reverreversed) temporal walk rooted at node u at time t is defined as W. which is sequence of
3

---

different temporal walks
groph
Anonymized walks
0 sS557
Figure 2: Triadic closures and the dynamic graph motifs: Two example temporal walks form two different triadic closures but represent the same motif within the time range 0 S t 7.
dynamic graph with timestamped edges a querled Interaction a specilic time
M
My
0.24
G.4.5
1,8
3,4
A(M
A(M
Termporal-biased
Spatictemporal blased walk
Spatiotemporal-bee hetteemmpppra--ieeeedddeeee biased walk with exploration exploitation trade-off
Anonymized node
Anonymization operation
(a) Dynamic Graph Motif Extraction
(b) Walk Anonymization
Figure 3: Temporal walk sampling and anonymization. Given a CTDG and a queried interaction (u, v, 8), we first extract surrounding temporal motifs by sampling a set of diverse and expressive temporal walks started from u and v, respectively, denoted as M,, and M,. Then, the walks in two sets are anonymized by replacing nodes' identities with their position encodings.
temporal nodes as in [36], i.e., node wi at time t, with == and to == t:
W (w,, 4,) i N, 0 < i <1, to
lt, (1w,, w;-1),4)) G.n for i 1},
(1)
where / is the walk length. We also use W and [[]][ (i.e., wy and 4 in (wi, respectively) to denote the specific node and time in the i-th step.
Each walk W rooted at temporal node can actually be regarded as of its surrounding motifs if f - f is bounded within the defined motif time range. A concrete example is given Figure 2, where two walks in the leftmost side form two triadic closures, which essentially represent the same motif on the rightmost side after an individual walk anonymization [21]. The necessity of anonymization is to replace original node identities in walks with their relative identities, which maps each walk to a particular pattern and thus connects temporal walks and dynamic graph motifs.
Definition 4.1.2 (Anonymous Walk). Given temporal node and walk W, the anonymization operation A(-) is defined as follows [36]:
A(w; W) = [vo. ... 2/- 2s WH,, where i" is the smallest index s.t. U/e w.
(2)
4.2 Dynamic Graph Motif Extraction
Temporal Walk Sampling. Existing path-based methods mainly employ temporal-biased sampling method when extracting dynamic graph motifs [23, 36). Specifically, given node u at time the probability of its neighbor a in ((a, (a, (') E Gu. to be sampled is proportion to exp(a((l - ()), which discounts stale neighbors and tends to sample more current nodes with timestamps closer to A larger emphasizes more this bias. Although more current neighbors more likely to be informative, the underlying topological and tree traversal properties are not respected, which hinders the extraction of diverse and expressive patterns. Here, propose spatiotemporal- biased random walks with the exploitation and exploration trade-off.
Our motivations are twofold: (1) Most-recent neighbors should be allocated larger sampling probability x exp((a((' - ()) as they are typically more informative w.r.t. a root node at time In Figure 3(a), given root node u and its two temporal neighbors / and c, temporal biased sampling path is more likely to be a +> instead of u - c; (2) Neighbors with higher connectivity need be emphasized to allow exploring more diverse and potentially expressive motifs. Given a node at time

---

t', we use its degree du = Ga.r to reify its connectivity, thus the proposed spatial spatial-biased probability xc exp(-5/da) with a hyperparameter walk sampling procedures with the above considerations. Given a node at time I, the probability of its temporal neighbor a to be sampled is the average of the following normalized probabilities:
control the bias intensity. Algorithm 1 illustrates the
explalta -t) t))
exp(-B/da)
Pri(a) = En'esu. exppax(le' - 1))
Pr.(a) Ed'es... exp( -B/d2)
(4)
Although Algorithm complements the temporal- biased schema by considering the additional topolog- ical information, may overly encourage the depth- first search (DFS), which could misleadingly sam- ple many homogeneous motifs with a limited bud- get. Take an extreme example, if [Mu] is restricted in Figure (a)), paths + + c + u may be sampled three times, leaving no room to explore Thus, we
Algorithm Sampling Temporal Walks
Require: Root node wo, cut time to. G. C, I: Initialize (W. = ((wb, (o)) [1ScsC)
2: for i in 1, 2. ... d'o
3: for in 1,2, 2..................... ...,C.dd do
4: tp [i] [1[1][]]
5: Initialize dw = 0 for all w E Supite
6: for te) in Gup.to do
7:
Let = {w,, wp), , du Geel end for
u - - b -> a and + f v design an exploitation & exploration trade-off to reg- ularize the walk sampling with another probability:
8:
9:
Sample one (e, E Gwpdy with prob. x erp(a((t - tp) and 3/dm))
exp(
10: Let = {w, wpt. We = (,),(w,t)
(r) Enres...
(5)
11: end for
12: end for
where 8a and y denotes the traversal times of node and the intensity of such regularization.
13:
return (Wa [Wel1seS0)
Our complete walk sampling algorithm and its complexity analysis are in Appendices B. and B.3. In a nutshell, given a temporal node, the probability of its neighbor to be sampled is the average of the probabilities defined in Equations 4 and 5. In NeurTWs, given queried interaction between two temporal nodes u and v as shown in Figure 3, we sample a set of C temporal walks rooted at each node with length denoted M,, and M,-
A Anonymization. Walk anonymization replaces node identities with position encodings (aka relative identities), which injects structural information while maintaining the inductiveness of NeurTWs. A drawback of Equation 2 is that the position encoding of each node only depends on its specific walk, leading anonymous walks rooted at the same node sharing different name spaces [36]. Thus, consider two practical solutions: unitary and binary anonymization to address this problem. For a temporal node in at least one walk rooted at node u, its unitary anonmization w.r.. u considers the name space defined over Ma, the set of walks rooted at u:
A(w; Mw) = [W w= = W[]] W E MaH), where i E {0, (0,-.-,44)
(6)
In Equation 6, the identity of w is replaced by vector A(w; M.) with length I, where the i-th element counts the number walks that have node w appearing in position
While unitary anonymization anonymizes node w w.r.t. M2 as A(w; Mu), for interacting root nodes and v. A(w; M.) and A(w; M,) belong to different name spaces. Since DGNNs are typically supervised by temporal interactions, establishing the correlations between W E My U M. may be beneficial. Thus, the binary anonymization defined as follows [36]:
(7) where || denotes the concatenation operation to establish the connections among motifs in M,, and M,. In the rest of the paper, we abbreviate the two anonymization strategies as A(w) for simplicity and denote W = (A(w.)),t) (w, t.) e W for i = 0, 1.. ,.) as an anonymous walk.
A(w; My. My) = A(w; Mw) A(w; Mo),
4.3 Neural Temporal Walk Encoding
A significant challenge to model CTDGs is that interactions occur irregularly. Previous works bypass this challenge by concatenating node attributes with extra time encodings when aggregating the neighbourhood information [38, 27, 36], where temporal dependencies are modeled implicitly. A detailed discussion in Appendix D.2. encode motif with irreuularl-saappled temporal nodes, we explicitly integrate over multiple interaction time intervals to learn the latent spatiotemporal dynamics with those discrete observations. Figure 4 and Algorithm 2 describe our method a nutshell, which consists of two interleaving steps: Continuous evolution and instantaneous activation.
5

---

Algorithm 2 Neural Temporal Walk Encoding
A(o) " >g) A(o) 2 A(+)
Require: An anonymous temporal walk W {(A(wx) 4:) (wx,4) E W for i = 0,1, ... .0
Nevral Tonppraa Volk Sxcoding
1: Reverse the order of elements in W
1-1 = to, h =
3: for i in 0, ,dd
Feature Estraction
hi = (1E
AG
AC
A Aw::)) = M (A(ue))
Imegulor trajectory latert state moolidion
14 = (o, (w:))
Figure 4: The spatiotemporal dynam- ics behind irregularly-sanan temporal nodes are explicitly modeled.
7: end for
8: return The walk embedding h4
Continuous Evolution. Given series of temporal nodes at different time, i.e., (A(w,).4) e W and ensuring t;-1 & by reversing the order of elements in W, the latent spatiotemporal dynamics among those nodes are modeled as follows:
f f(he, 0) dt, J4
h; - -i=hi-i+
(8)
where h4-1 denotes the latent states after encoding (A(W:-1), E W. We define the ODE function f(he, 0) an autoregressive gated recurrent unit parameterized by O. See Appendix B.2.
Instantaneous Activation. The latent state evolution in Equation conditions on a series discrete observations. Thus, we define function to activate latent state trajectories with instantaneous inputs:
h g(h A (w:).
where g( Φ) can be standard RNN cell parameterized by o, and A' (w.) MLP(A(W:), ()) denotes the linear mapping of a discrete observation A(w,) in an anonymous walk W.
Compared with [36], we naturally model spatiotemporal dynamics behind walks with irregularly- sampled temporal nodes, where the time information has been explicitly reflected in this modeling process. On this basis, for a temporal node u, we obtain its time-aware representation by pooling the embedding of walks in Ma. denoted as hg. In this paper, we adopt the sum pooling for simplicity.
4.4 Contrastive Optimization
A self-supervised pretext task is required to train DGNNs due to the scarcity of the labeling informa- tion. Most current works formulate their learning problems as a binary classification task, where the existence of interaction is predicted. From the contrastive point of view, a binary cross-entropy loss essentially forms a particular case of the Jensen-Shannon estimator [19], where the number of negatives is and thus provides limited supervision signals.
Here, we introduce harder contrastive pretext task, where the mutual information between interacting temporal nodes (e.g., node и and in Figure 3) is maximized. We detail the complete training algorithm of our method in Appendix B.4. In brief, the following noise-contrastive loss is minimized in the proposed approach:
L
E
log
(10)
hw))) + EWeG, expl simmtu.. New
sim(-) measures the similarity between two entities, i.e., sim(hus hv) (MLP(h E)), where o()) and & are sigmoid activation and trainable parameters.
4.5 Extension and Discussion
Learning on Attributed CTDGs. Our method can be easily extended to model CTDGs with node and interaction attributes. To achieve this, we only need to slightly modify Equation 9 as follows:
h4 g(hi, A (wx) ) Xw: || X| Φ),
(11)

---

Table 1: The dataset statisties. Average interaction intensity À 2N/((VIT) [16, 36] embodies the
density of interactions in a fixed period, where T and [V] are dataset duration and number of nodes.
Statisties
CollegeMig
Euron 143 & 62,617
Taobao
MOOC
Wikipedia
Reddit 10,984 & 672,447
4 Nodes Interactions
1899 & 59,835
64,703 77.46
7,144 & 411,749
9.227 157,474
Duration (scoond)
16,621,303
72.322520
36,000
2,572,086
2,678.375
2,678,390 172 & 172
# Nodes & Intematioon attributes
0&
0 1.2 x 10-
0
0&
172 & 172
Average interaction intensity X
3.79 10-4
6.61 x
4.48
1.27 x 10-
1.57 x 10
4 Dynamically labeled nodes
217
366
where Xw: and Xe, are linearly mapped features of node and edge == [w;-1, w;} in W.
Batching and Computational Complexity. One computational challenge is that each walk contains irregularly-samee samplee nodes at different timestamps, requiring the model to separately solve C different ODEs to calculate the embedding of root node, thus hindering training in batches. To solve all ODEs at once in a minibatch with B sampled interactions, we unify the integral time among all ODEs (see Appendix B.3) to a certain range, which results in lower time complexity of O()) instead of O (BI). In Appendix B.3, we also provide detailed complexity analysis and discuss how to make solving Equation 8 tractable with very large time intervals.
Experiments
5.1 Experimental Setting
Baselines. Our model is compared with six statc-of-the-ar methods in modeling CTDGs. They be divided into two categories based on their intrinsic mechanisms: (1) message passing- based methods, including DyRep [34], TGAT [38], and TGN [27]: (2) sequential model-based methods, including CTDNE [23], JODIE [15], and CAWs [36]. More details can be found in Appendix C.2.
Datasets. We evaluate model performance on six real-world datasets. CollegeMsg [17] is a social network dataset consisting of message sending activities. Enron [17] is an email communication network. Taobao [46] is an attributed user behavior dataset containing user-item interactions. MOOC [17] is an attributed network consisting of student-course interactions. Wikipedia and Reddit [15] are two bipartite interaction networks consisting of editor-page and user-post activities with rich attributive information. The dataset statistics are summarized in Table I, and their detailed descriptions are in Appendix C.I.
Evaluation Protocols. For link prediction, we follow the evaluation protocols of CAWs [36] and consider two different downstream tasks for evaluation: trunsductive and inductive link prediction.
In transductive link prediction, we sort and divide all N interactions in a dataset by time into three separate sets for training, validation, and testing. Specifically, the ranges of training, validation, and testing sets are [0, Niro). (Nern,Neal) [Na NN. where Nern/N /N and Nowt/ /N are 0.7 and 0.85.
In inductive link prediction, we use the same splits but mask proportion of nodes (10%) and associated interactions during training, which are predicted during inference to evaluate the model inductiveness. Specifically, we first remove all interactions connected with masked nodes in the training set and then remove all interactions not associated with them in the validation and testing sets. In particular, we have two specific settings: (1) New-Olt Old tasks require the model to predict the interactions with one unobserved (i.e., masked) and one observed nodes; and (2) New-New tasks aim to predict the interactions between all unobserved nodes.
For dynamic node classification, we follow the evaluation protocol in [27]. Specifically, we first obtain model under the setting of transductive link prediction. Then, we train and test separate classifier on top of this tre-trained model with the temporal nodes observed in Nvaz) and [Nvat, N).
Training Details. We implement and train all models under unified evaluation framework with the Adam optimizer. The tuning of primary hyperparameters is discussed in Appendix C.3. In solving ODEs, we use the Runge-Kutta Kutta method with the number of function evaluations set to by default. For fair comparisons and simplicity, we use sum-pooling when calculating node representations in both our method and CAWs. We also test NeurTWsf, which is equipped with the binary anonymization, while NeurTWs adopts the default unitary anonymization. All methods tuned thoroughly with nonlincar 2-layer and 3-layer perceptrons to conduct downstream link
7

---

Table Transductive and inductive link prediction performances w.r.t. AUC. We use bold font and underline to highlight the best and second best performances. NeurTwsf is a vairant of our method with the binary anonymization.
Task
Method
Ms
Enron
Taobao
MOOC
JODIE [15]
0,5846 + 0.038
0.8714 + 0.011
0.8477 0.015
0.6815 + 0.014
Transductive
DyRep [34]
0.5297 + 0.042
0.8632 + 0.013
0.8462 + 0.012
0.6195 + 0.018
TGAT [38]
0.7528 1 0.004
0.6592 1 0.012
0,5400 + 0.005
0.6750 1 0.035
TGN [27]
0.8990 0.003
0.8944 1 0.015
0.8484 1 0.029
0.7703 1 0.032
CAWs [36]
0.9002 + 0.002
0.9520 1 0.002
0.8719 1 0.001
0.6948 1 0.053
NeurTWs
0,9526 + 0.002
0,9564 + 0.005
0.9100 + 0.014
0.7756 + 0.031
NeurTWst
0.9750 = 0.004
0.9704 = 0.012
0.8911 + 0.014
0.7470 0.028
JODIE [15]
0.4589 + 0.028
0.8182 1 0.022
0.7626 1 0.002
0.6304 1 0.006
DyRep [34]
0.4486 0.021
0.7241 1 0.025
0.7641 1 0.012
0.5504 0.010
New-Ol Old
TGAT [38]
0.7240 1 0.008
0.6131 1 0.049
0.5537 0.018
0.6410 T 0.024
TGN [27]
0.8699 + 0.007
0.7068 + 0.116
18706=0.000
0.6968 + 0.008
Inductive
CAWs [36]
0.8911 = 0.015
0.9612 = 0.002
08744
0.7479 0.023
NeurTWs
0.9575 0.011
19525
0.9316 0.018
0.7822 0.004
NeurTWat
0.9699 0.010
0.9566 + 0.007
0,9037 + 0.013
0.7772 4: 0.006
JODIE [T]]
0.5135 + 0.048
0.7537 1 0.025
0.7791 = 0.004
0.8243 0.007
DyRep [34]
0.5813 + 0.066
0.7184 + 0.061
0.7716
0.017 0.017
0.5288 + 0.021
New- New
TGAT [38]
0.7283 + 0.029
0,6340 = 0.032
0,5479 0.025
0.6365 + 0.014
TGN [27]
0.7745 0.102
0,9217 1 0.026
0,8701 0.011
0.6448 1 0.053
CAW' [36]
0.8974 = 0.009
0.9777 + 0.001
0.8762 + 0.004
0.7558 + 0.036
NeurTWs
0,9649 + 0.008
0.9906 + 0.007
0.9242 + 0.005
0.8329 + 0.010
NeurTWat
0.9768 + 0.008
0.9858 + 0.015
0.9140 + 0.013
0.8302 + 0.007
prediction and node classification tasks, and we adopt the commonly used Area Under the ROC Curve (AUC) and Average Precision (AP) as the evaluation metrics. More implementation details can be found in Appendix C.3.
5.2 Results and Discussion
The link prediction performance of our method and state-of-the-ard baselines are summarized in Table 2 (w.r.t. AUC) and Appendix D.1 (w.r.t. AP). As can be seen from this table, our method achieves the best performance on different tasks and datasets in general. Notably, NeurTWs sur- passes the strongest model, CAWs, significantly on both unattributed and attributed CTDGs, c.g., 7.76% and 4.78% on average on CollegeMsg and Taobao. Particularly, NeurTWs and Neur achieve strong AUC result Z 0.95 on Col- legeMsg. while all baselines have their AUCs
Table 3: Dynamic node classification performance w.r.t. AUC. We use bold font and underline to highlight the best and second best performances.
The baseline results are taken from [27].
Method
Wikipedia
Reddit
CTDNE [23]
0.7589 1 0.005
0.5943 1 0.006
JODIE [15]
0.8484 1 0.012
0.6183 0.027
DyRep [34]
0.8459 1 0.022
0.6291 1: 0.024
TGAT [38]
0,8369 - 0.007
0.6556 = 0.007
TGN [27]
0.8781 + 0.003
0.6706 = 0.009
NeurTWs
0.8851 + 0.003
0.6652 0.022
S 0.9, demonstrating the effectiveness of the proposed method.
Specifically, on both transductive and inductive tasks, we make the following observations. (1) Our method performs well on both attributed and unattributed datasets, while the effectiveness of baseline models varies significantly. For instance, JODIE and DyRep have enormous performance gaps between Taobao and CollegeMsg in all three tasks. It indicates that our NeurTws method is better at capturing essential dynamic laws. This superiority can be attributed to our spatiotemporal walks and associated encoding mechanism: (2) Our method effective under both transductive and inductive settings. On the contrary, some baseline models cannot well generalize to predict interactions with unseen nodes (e.g., the performance of JODIE and DyRep drops on inductive tasks) because they rely on node identities. TGAT, TGN, and CAWs can yield better performances but leave room to improve.
worth noting that simple unitary anonymization (i.e., NeurTWs) and more complex binary anonymization (i.e., Neur yield similar performance in most cases. Our method with the default, simpler unitary anonymization performs significantly better than CAWs, which utilizes binary anonymization, again demonstrating the superiority of our approach in modeling
8

---

Table 4: Ablation study with the proposed NeurTWs method. The performance in predicting all inductive interactions is reported.
CollegeMsg
Taobao
No.
Configuration
AUC
AP
AUC
AP
Full model (NeurTWs)
0.958
0.01
0.966 1 0.01
0.938 1 0.02
0.933 1 0.02
w/o T-biased probability
0.918 + 0.02
0.928 : 0.02
0.932 = 0.03
0.03
0,927 = 0.01
2
w/o S- b-biased probability
0.949 + 0.02
0.958 + 0.02
0.915 0.01
0,915 = 0.01
w/o E&E-biased probability
0.957 + 0.01
0.965 1 0.01
1
0.927 0.01
0.01
w/o continuous evolution
0.868 0.02
0.898 0.01
0.860 1 0.05
0.901 + 0.02
5 w/o contrasitve learning
0.954 + 0.01
0.962 + 0.01
0.935 + 0.01
0.01
0,932 + 0.01
CTDGs without relying on sophisticated position encodings; (3) Comparing the results on Taobao, our method's 's improvements over CAWs are more significant than on CollegeMsg, e.g., 7.48% vs. 3.81% on transductive and 7.91% vs. 5.26% on inductive settings. Similar observations can also be found when compared on MOOC and CollegeMsg. This is because the CollegeMsg dataset has a lower average interaction intensity (i.e., À = 3.79 x 10-9) compared with Taobao and MOOC datasets (i.e., À = 6.64 x 10-5 and 4.48 x 10 10-5). A lower À indicates larger average time span in a temporal walk, for which our proposed continuous evolution process is more effective.
In addition, we compare the performance of our method (i.e., NeurTWs) on dynamic node classi- fication with sfate-of-the-art baselines as shown Table 3, where our approach achieves the best or on-par performances, further confirming the effectiveness of the proposal. We do not report the results of NeurTWst because node classification mainly considers properties of temporal nodes rather than interactions.
5.3 Ablation Study
In Table 4, we report the results of our ablation study on predicting inductive interactions in both new-old and new-new settings. Specifically, ablations 1, 2, and 3 remove Equations 3, 4, and 5 when sampling temporal walks. Ablation 4 disables Equation 8 when encoding an anonymous walk. Ablation 5 replaces contrastive loss with binary cross entropy loss. From the above variants, we see performances degradation when retrieving motifs without considering the temporal or spatial information, demonstrating the effectiveness of the proposed ppatiotemporal-biasee walk sampler. Moreover, disabling the exploitation & exploration trade-off also hurts performances. When removing the continuous evolution, more severe performance drops are found on CollegeMsg, further demonstrating that NeurTWs excel on CTDGs with more sparse interactions where existing works usually fail to model them well. The performance drops also exist when our contrastive pretext task is disabled. A specific study related to continuous evolution is in Appendix D.2.
5.4 Parametric Sensitivity
We study the important settings in NeurTWs and have the following observations: (1) For each dataset, there are sweet spots in balancing three intensities (i.c., o, B, and 7). Specifically, different datasets with different average interaction intensities, namely X, prefer different temporal-biasee biased intensities. For example, relatively large benefits on CollegeMsg but hurts the performance on Taobao as shown in Figure 5(a). On both datasets, overly emphasizing the topology information with large 3 hurts the performance (see Figure 5(b)) because the temporal information is overly neglected. However, setting a relatively large 7 seems beneficial (see Figure 5(c)), indicating the importance of balancing exploitation and exploration in temporal walk sampling: (2) We also investigate the choice of walk length and number of walks C' as shown in Figures 5(e) and 5(f). On both datasets, sampling 16 or 32 walks with the length 2 or 3 seems sufficient to characterize a temporal node; (3) For efficiency, we limit the number of negatives in Equation 10 instead of calculating he for all v' E G where v' of v. Specifically, we find that large number is usually beneficial on both datasets as shown in Figure S(d), where the performance increases to converge with an increasing number of negatives. In our method, we normally do not have to tune continuous evolution-related hyperparameters, but we provide detailed study in Appendix D.2.

---

Average Prextsion
Average Procision
Average Precision
CollegeMog
CollegeMsg
Tacbao
CollegeMig
Temggrakbiased Intensity
Spatial-biased Intensity
(c) E E-biased Intensity
Reerage Prectsion
Avarage Pracision
Averogg age Precision
Taobao CollegeMsg
Taobao CollegeMMg
CollegeMsg
(d) Number of Negslives
(e) Temporal Walk Length
10 Number of Temporal Walks
Figure 5: Study important settings of NeurTWs. The performance in predicting all inductive interactions is reported.
Discussion and Conclusion
Limitations. There are few limitations for our method. Firstly, more sophisticated time interval normalization required. In real-world dynamic graphs, there may some large time intervals between temporal nodes when constructing temporal walks. Although we propose simple solution based on logarithmic transformations (see Appendix B.3), there is no theoretical guarantee of stability when solving the continuous evolution process by this normalization trick. Secondly, the calculation of spatial-bist biased probabilities is computationally heavy. While is practical to limit the number of spanned temporal neighbors to alleviate the computational burden (see Appendix D.4), we resort to finding a more efficient implementation the future.
Social Impacts. Continuous-ting dynamic graph representation learning benefits a wide range of real-world applications, including but not limited to recommender systems, social network mining, and industrial process modeling. However, there are also some potential negative impacts. For example, NeurTWs may learn skewed representations there are biased patterns in the training data, which may result stereotyped predictions. Also, powerful dynamic graph models may augment harmful activities (c.g., attacking and phishing) on real-world dynamic systems.
Conclusion. We propose novel and competitive method for modeling CTDGs, which has advan- tages in three aspects. Firstly, our approach complements existing temporal neighborhood sampling algorithms by simultaneously considering temporal, topological, and tree traversal properties, en- abling diverse and expressive dynamic graph motifs to be retrieved. Secondly, the proposed method allows these motifs with irregularl-sampller temporal nodes to be better embedded, where temporal dependencies are now explicitly modeled. Thirdly, our model forms harder contrastive pretext task to enrich supervision signals. Consequently, the NeurTWs method outperforms existing works by large margins, revealing significant application prospects in many real-world scenarios, which will be an exciting focus in our future work.
Acknowledgments and Disclosure of Funding
Some computing resources for this project are supported by 2ASSIVE, We thank Guangsi Shi for additional computational resources and assistance in model training and deployment.
S. Pan was partially supported by an Australian Research Council (ARC) Future Fellowship (FT210100097). Y.-F Li was partially supported by the DARPA CCU program (HR001121S0024)
Phttps://www http:://wwwwmm.ieee...mmmm mwwsive. org.au/ au/
10

---

References
[1] Eric Z. Chen, Terrence Chen, and Shanhui Sun. Mri image reconstruction via learning opti- mization using neural odes. In International Conference Medical Image Computing and Computer-Asistted Intervention, pages 83-93. Springer, 2020.
[2] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. Advances in Neural Information Processing Systems, 2018.
[3] Ricky TQ Chen, Brandon Amos, and Maximilian Nickel. Neural spatio-temporal point processes. In International Conference on Learning Representations, 2020.
[4] Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. In Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation, pages 103-111, 2014.
[5] Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Martinez Canedo. Capturing network dy- namics using dynamic graph representation learning, March 5 2020. US Patent App. 16/550,771.
[6] Zhen Han, Zifeng Ding, Yunpu Ma, Yujia Gu, and Volker Tresp. Temporal knowledge graph forecasting with neural ode. In Proceedings the 202/ Conference Empirical Methods in Natural Language Processing, page 8352-8364, 8364, 2021.
[7] Zijie Huang, Yizhou Sun, and Wei Wang. Learning continuous system dynamics from uregularly-sampler partial observations. Advances in Neural Information Processing Sys- tems, 33: 33:16177-161187 2020.
[8] Zijie Huang, Yizhou Sun, and Wei Wang. Coupled graph ode for learning interacting system dynamics. In 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021, pages 705-715, 2021.
[9] Boyan Jiang, Yinda Zhang, Xingkui Wei, Xiangyang Xue, and Yanwei Fu. Learning com- positional representation for 4d captures with neural ode. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5340-5350, 2021.
[10] Linpu liang, Ke-Jia Chen, and Jingqiang Chen. Self-supervised dynamic graph representation learning via temporal subgraph contrast. arXiv preprint arXiv:2112.08773,, 2021.
[11] Di Jin, Luzhi Wang, Yizhen Zheng, Xiang Li, Fei Jiang, Wei Lin, and Shirui Pan. Cgmn: A contrastive graph matching network for self-supervised graph similarity learning. In Proceedings of the Thirty-Firs International Joint Conference Artificial Intelligence, pages 2101-2107 2022.
[12] Ming Jin, Yu Zheng, Yuan-Fang Li, Siheng Chen, Bin Yang, and Shirui Pan. Multivariate time series forecasting with dynamic graph neural odes. arXiv preprint arXiv:2202.08-03 2022.
[13] Seyed Mehran Kazemi. Dynamic graph neural networks. In Graph Neural Networks: Founda- tions, Frontiers, and Applications, pages 323-300 223-349. Springer, 2022.
[14] Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time-dependent networks. Journal of Statistical Mechanies: Theory and Experiment, 201 2011(11):PI 1005, 1.
[15] 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 & data mining, pages 1269-1278, 2019.
[16] Günter Last and Mathew Penrose. Lectures on the Poisson Process. Institute of Mathematical Statistics Textbooks. Cambridge University Press, 2017.
[17] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection; 2014, 2016.

---

[18] Xu Liu, Yuxuan Liang, Yu Zheng, Bryan Hooi, and Roger Zimmermann. Spatio-temporal graph contrastive learning. arXiv preprint arXiv:2108.1183 2021.
[19] Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip Yu. Graph self-supervised learning: A survey, IEEE Transactions on Knowledge and Data Engineering, 2022.
[20] Shmoolik Mangan and Uri Alon. Structure and function of the ford-forward loop network motif. Proceedings of the National Academy of Sciences, 100(21): (0021))11980-11999 1980-11980---0 1985, 2003.
[21] Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments, Discrete Applied Mathematics, 200:108-122, 2016.
[22] Michael C Mozer, Denis Kazakov, and Robert V Lindsey. Discrete event, continuous time rnns. arXiv preprint arXiv: 1710.04) 10, 2017.
[23] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-ting time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pages 969-976, 2018.
[24] 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 Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3370, 2020.
[25] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations. In International Workshop on Deep Learning on Graphs, 2019.
[26] Rui Qian, Tianjian Meng, Boqing Gong, Ming-Hsuan Yang, Huisheng Wang, Serge Belongie, and Yin Cui. Spatiotemporal contrastive video representation learning. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1964-6974, 2021.
[27] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. In ICML 2020 Workshop on Graph Representation Learning, 2020.
[28) Yulia Rubanova, Ricky TQ Chen, and David K Duvenaud. Latent ordinary differential equations for pregularly-samphhe time series. Advances in Neural Information Processing Systems, 32, 2019.
[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 Proceedings of the 13th International Conference Web Search and Data Mining, pages 519-527, 2020.
[30] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pages 362-373. Springer, 2018.
[31] Georg Simmel. The sociology of georg simmel, volume 92892. Simon and Schuster, 1950.
[32] Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial. Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey. IEEE Access, 9:79 1779943-79168, 2021.
[33] Sheng Tian, Ruofan Wu, Leilei Shi, Liang Zhu, and Tao Xiong. Self-supervised representation learning on dynamic graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1814-1823, 2021.
[34] Rakshit Trivedi, Mehrdad Farajtabar, Prasenject Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In International Conference on Learning Representations, 2019.
[35] Petar Velickovic, William Fedus, William I. Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In International Conference Learning Representations, 2019.
12

---

[36] Yanbang Wang. Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In International Conference on Learning Representations, 2021.
[37] Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In International Conference on Machine Learning, pages (0432-10441. PMLR, 2020.
[38] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive repre- sentation learning on temporal graphs. In International Conference Learning Representations, 2020.
[39] Yiwen Zhan, Yuchen Chen, Pengfei Ren, Haifeng Sun, Jingyu Wang, Qi Qi, and Jianxin Liao. Spatial temporal enhanced contrastive and pretext learning for skeleton-basee action representation. In Asian Conference on Machine Learning, pages 534-547 PMLR, 2021.
[40] He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint urXiv:2205.07424 2022.
[41] Yujia Zhang. Lai-Man Po, Xuyuan Xu, Mengyang Liu, Yexin Wang. Weifeng Ou, Yuzhi Zhao, and Wing- Yin Yu. Contrastive representation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
pretext learning for sulf-supe video
[42] Xin Zheng, Miao Zhang, Chunyang Chen, Chaojie Li, Chuan Zhou, and Shirui Pan. Multi- relational graph neural architecture search with fine-grained message passing. In IEEE Interna- tional Conference on Data Mining, 2022.
[43] Yizhen Zheng, Ming Jin, Shirui Pan, Yuan-Fany Juan-Fang Li, Hao Peng, Ming Li, and Zhao Li. Towards graph supe-supe learning with contrastive adjusted zooming. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[44] Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, and Philip S Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. Advances in Neural Information Processing Systems, 2022.
[45] Hongkuan Zhou, Da Zheng, Israt Nisa, Vasileios loannidis, Xiang Song, and George Karypis. Tgl: A general framework for temporal gnn training on billion-scale graphs. Proceedings of the VLDB Endowment, 1572)1157- 2022.
[46] Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. Learning tree-based deep model for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1079 2018
13


Reviews:
[{"review_id": "maHfa313o1C", "reviewer": "Reviewer_avBg", "summary": "The authors propose a method based on random walks and neural ordinary differential equations to capture and encode irregularly-sampled walks consisting of temporal nodes. The authors also provide in-depth analysis to reveal the connections between temporal graph motifs and temporal walks and why it is essential to capture them to learn temporal graph representations. Compared with previous work, this paper demonstrates good performance in both attributive and non-attributive scenarios.", "questions": "- How the proposed method deals with large time intervals compared with the time encoding approach? \n\n- How to deal with the case where the number of the spanned neighborhood is large? Based on the complexity analysis in the appendices, the time complexity of the proposed sampling algorithm is proportion to $k_s$, which makes the proposed method hard to scale on dynamic graphs with higher average temporal node degree.\n", "limitations": "- The discussions of how the proposed method can learn on dynamic graphs with large average time intervals and higher temporal node degrees are necessary.\n\n- The details of paper writing can be further improved, e.g., u->b in Fig. 3 can also be a temporal-biased walk since the timestamp of node b is the same as node f.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \n\nThe paper is overall well-written, and the motivations are justified clearly. In general, the improvements over existing work on dynamic graph learning are significant based on the experimental results.\n\n- Representation learning on continuous-time dynamic graphs is an important but less explored task. This paper presented an effective method for solving this problem.\n\n- Overall, the novelty of the proposed method is somewhat significant compared with existing random walk-based methods. Notably, capturing the information of time intervals with NODE demonstrates significant improvements over the widely adopted time encoding approach, which may open a new possibility in modeling continuous-time dynamic graphs.\n\nCons:\n\n- Regarding the walk anonymization to establish the structural connections between walks, there is no significant breakthrough compared with CAW.\n\n- The complexity analysis is prone to error, e.g., the time complexity of walk anonymization has not been counted when calculating the total time complexity of the proposed method.\n\n- Optimizing Eq. 8 may be problematic. In real-world dynamic graphs, the time intervals may be extremely large (in seconds), which leads to large integral intervals when solving the ODE.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_oUZ_6iyKcD", "reviewer": "Reviewer_zmsk", "summary": "This paper proposes a method based on the concepts of temporal walks and neural ordinary differential equations to learn effective node representations on continuous-time dynamic graphs. The main contributions of this work are in three aspects. Firstly, it proposes a more effective way to sample temporal walks from dynamic graphs. Secondly, it learns continuous latent dynamics of temporal walks, showing significant performance gains (Tab. 3). Thirdly, it borrows the idea of contrastive learning to optimize the dynamic graph learning problems. Compared with the existing methods, especially for its predecessor CAWs, the proposed method shows significantly better performances on downstream tasks.", "questions": "1.\tHow is the spatial information handled in the proposed neural temporal walk encoding method?\n\n2.\tWhy have the authors not experimented on the widely adopted Wikipedia and Reddit datasets used in TGAT, TGN, and CAWs?\n\n3.\tWhat are the connections and comparisons between the random walk-based methods (e.g., NeurTWs) and message passing-based methods (e.g., TGAT and TGN)? In other words, what is the significance between NeurTWs and those local aggregation methods?\n", "limitations": "Yes. The authors have addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n+\tIn general, this paper is well-presented. The learning problem on dynamic graphs is clearly formulated, and the technical writing in Sec. 4 is easy to follow. The overall architecture design makes sense to me, where the contributions and improvements over CAWs can be easily distinguished.\n\n+\tThe experimental design is straightforward and comprehensive. Firstly, the effectiveness of the proposed method can be proved compared with state-of-the-art baselines. Secondly, necessary ablation and parameter studies are also clearly presented in the paper's main text. Thirdly, I can see supplementary experiments in the appendices, including the analysis of important designs and the visualization results, which help confirm the effectiveness of the proposed method.\n\nCons:\n\n+\tThe readability can be further improved. It requires the readers to have some background knowledge on anonymous and temporal walks to fully understand the proposed method.\n\n+\tSome description is unclear. For instance, how is the spatial information handled in the proposed neural temporal walk encoding method?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FKjDpArP1_k", "reviewer": "Reviewer_qteb", "summary": "The paper proposes a new approach for representation learning on temporal graphs (or CTDGs). The proposal can be viewed as an extension of the walk sampling scheme from CAW [1], modified to also count on node degree and time traversal information. The paper also employs a NeuralODE-based approach aiming to better leverage fine-grained temporal information. Results on three benchmark datasets show the effectiveness of the proposal.\n", "questions": "- In the Introduction, the paper says “[..] studies in dynamic graph modelling extract expressive patterns manually […]” and cites [1]. Although [1] uses triadic closure as a motivation, the design in [1] can capture a large collection of structures/motifs. Why is this regarded as manual motif extraction?\n- “[..] time encoding hurts model performance because temporal dependencies are modelled implicitly”. What is the basis for this strong claim?\n- In Definition 1: $i \\in \\mathbb{N}^+$ means that $i$ lies in the natural numbers without zero, which conflicts with $0 \\leq i$. Also, by definition of $G_{\\cdot, t}$, no pair $(\\cdot, t_i)$ can belong to ${G}_{\\cdot, t_i}$. This definition deserves some polishing. \n- What can continuous evolution bring in terms of expressive power that sequence-based models (e.g., RNNs) cannot?\n- The chosen datasets are small. It would be helpful to report the performance of NeurTW on the Reddit and MOOC datasets.\n- Is the proposed model able to deal with (node-level and edge-level) deletion events? How would so?\n- Can the model be applied to node-level prediction tasks? How could we obtain node embeddings using NeurTW?\n- In the ablation study Ab.4, what is done to replace the continuous evolution procedure? Is the temporal information completely disregarded? \n- It would be helpful to report a time comparison between NeurTW vs. TGN and CAW. \n\n**Typos:** \n- Line 165: \"a nodes u\"\n- Line 162: \"to allows\"\n- Line 126: \"Specifically, Given\"\n- Line 187: \"with the length $l$\"\n- Line 234: \"We details\"\n\n[1] CAW: https://arxiv.org/pdf/2101.05974.pdf ", "limitations": "The authors do not discuss the limitations of their work. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is easy to follow despite some typos and minor technical errors. I like the simplicity of the proposed method and the fact it leads to promising results. Also, the paper discusses a relevant topic in AI/ML. However, I would rank novelty as limited: modification of existing approaches (sampling strategy of CAW) combined with previous strategies (ODE-based solvers, contrastive loss) and evaluated using a standard setup. Also, no theoretical insights or claims are established in the paper. The proposal seems to incur a computation burden on a model that is already slow (CAW, [1]). Last, the paper only considers three benchmarks as opposed to six in [1]. \n\nStrengths:\n- Promising results\n- Simplicity\n\nWeaknesses: \n- Lack of a more principled motivation behind the proposed design choices\n- Limited evaluation setup\n- Limited technical novelty\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept