DyG2Vec: Efficient Representation Learning for Dynamic Graphs
Authors: Mohammad Alomrani
Mahdi Biparva
Yingxue Zhang
Mark Coates
Venue: Accepted by TMLR ()

Abstract: Temporal graph neural networks have shown promising results in learning inductive representations by automatically extracting temporal patterns. However, previous works often rely on complex memory modules or inefficient random walk methods to construct temporal representations. To address these limitations, we present an efficient yet effective attention-based encoder that leverages temporal edge encodings and window-based subgraph sampling to generate task-agnostic embeddings. Moreover, we propose a joint-embedding architecture using non-contrastive SSL to learn rich temporal embeddings without labels. Experimental results on 7 benchmark datasets indicate that on average, our model outperforms SoTA baselines on the future link prediction task by 4.23% for the transductive setting and 3.30% for the inductive setting while only requiring 5-10x less training/inference time. Lastly, different aspects of the proposed framework are investigated through experimental analysis and ablation studies. The code is publicly available at https://github.com/huawei-noah/noah-research/tree/master/graph_atlas.

Published in Transactions on Machine Learning Research (12/2023)
DyG2Vec: Efficient Representation Learning for Dynamic Graphs
Mohammad All Alomranf Huowei Noah's s Ark Lab
mohammad. ali, www.rronni@uuuuue.cccom
Mahdi Biparva
mahdi mabsk.bbperrudBhaunnr.ccomm
Huawei Noah's Ark Lab
Yingxue Zhang
singrue..hangg@hauue.ccom
Huawei Noah's Ark
Mark Coates
contes@ece.
McGill University
Reviewed on OpenReview: https: // opw.r/veeee...eeee/em/o net/ forum? id- YRKS2J0a36
Abstract
Temporal graph neural networks have shown promising results in learning inductive rep- resentations by automatically extracting temporal patterns. However, previous works of- ten rely complex memory modules or inefficient random walk methods to construct temporal representations. To address these limitations, we present an efficient yet effec- tive attention- based encoder that leverages temporal edge encodings and window-based subgraph sampling to generate task-agnostic embeddings. Moreover, we propose a joint- embedding architecture using non-contrastive SSL to learn rich temporal embeddings with- out labels. Experimental results on benchmark datasets indicate that on average, our model outperforms SoTA baselines on the future link prediction task by 4.23% for the transductive sctting and 3.30% for the inductive sctting while only requiring 5-10x less Training/
beatiinnniinfeeenn inffernce time. Lastly, different aspects of the proposed framework are investi- gated through experimental analysis and ablation studies. The code is publicly available at _tala
1 Introduction
Contimouu--imme dynamic graphs (Kazem et al.) 2020 are graphs in which each edge has a continuous
timestamp and can be naturally found in many real-world applications such as social networks and finance.
Recently, dynamic graph encoders (Rossi et al. 2020 Wang et al.) (2221b] Jin al., 2022 Luo Li, 2022) have emerged patterns from ever-evolving dynamic graph in order to make accurate future predictions. However, such models have several shortcomings. First, they heavily rely chronological training and/or complex
promising representation learning approaches that able to extract temporal
memory modules to construct predictions (Kumar et al. 2019 Xu et al. 2020 Rossi et al. 2020 Wang et al. 2021b). Consequently, encoding any dynamic graph requires sequentially iterating through all edges, which is intractable for large graphs due to the high computational overhead. Second, the encoding modules either use inefficient messago-pes mussagc-passing procodures (Xu et al. 2020) that enforce temporal causality, or expensive random walk-based algorithms (Wang et al.) 2021b Jin el al. 2022 with heuristie feature encoding strategies that engineered for edge-level tasks only. Finally, opposed to other temporal domains (Tong et al.) 2022; Eldele et al. 2021), most works on dynamic graphs have focused on pushing downstream task performance rather than learning general pre-trained models.
"equal contribution

---

Published in Transactions on Machine Learning Research (12/2023)
Self Supervipee Representation Learning (SSL) has shown promise in achieving competitive performance for different data modalities on multiple predictive tasks (Liu et al.] 2021 Given large corpus of unlabelled data, SSL postulates that unsupervised pre-training is sufficient to learn robust representations that are prodictive for downstream tasks with minimal fino-tuning. Contrastive SSL methods, despite their carly success, rely heavily on negative samples, exlensive data augmentation, and large batch sizes [Jing et al. 2022 Garrido et al., 2023). Non-contrastive methods address these shortcomings, incorporating information theoretic principles through architectural innovations or regularization methods (Balestriero & LeCun 2022). The success of such SSL methods sequential data (Tong et al. 2022, Eldele et al., 2021 Patrick et al. 2021 suggests that one can learn rich temporal node embeddings from dynamic graphs without direct supervision. While there are some recent attempts at using SSL for dynamic graphs such as DDGCL (Tian et al. 2021) and DySubC [Jiang et al. 2021), they lend to require high memory and computation due lo negative sampling and focus more on pushing downstream performance rather than learning rich general reprosentations.
In this work, we propose DyG2Vec, novel efficient encoder-decoder model for continuous-Lime dynamic graphs that benefits from a window-based architecture that acts a regularizer to avoid over-fitting. DyG2Vec is an efficient attention- based graph neural network that performs message-passingg across structure and time to output aaskstgnostic node embeddings, without the need for expensive random-
-aakk walk anonymyza-
tion procedures (Wang et al., 2021b Jin et al. 2022) or memory modules (Rossi et al. 2020 Souza et al. 2022). We equip DyG2Vec with the ability to perform non-contrastive SSL, which allows the model to learn rich representations without labels, if needed. Our results on 7 benchmark datasets indicate that on average, DyG2Vec outperforms the SoTA baseline CaW (Wang et al., 2021b) on the future link prediction task by 4.23% for the transductive setting and 3.30% for the inductive setting. In addition, DyG2Vec addresses the elficiency bottleneck often experienced with other dynamic graph encoding alternatives. It reduces the training:inferencee inference time by 5-10x compared to the state-of-the-art models, thereby providing superior model performance with a significantly reduced computational demand. This efficiency gain significantly enhances the model's scalability potential for large graphs.
Our main contributions can be summarized as follows:
We propose an effective message-passing encoder that leverages temporal edge encoding to better capture temporal dependencies.
We climinate the need for memory modules or expensive causal random-wal walk extraction methods through efficient window-based subgraph encoding, making it easier to extract temporal motifs.
2
Related Work
We review the most relevant literature on dynamic graph and self-supervised representation learning. See Appendix A.6 for more tangentially related works.
Representation learning for dynamic graphs: Early works representation learning for continuous- time dynamic graphs typically divide the graph into snapshots that are encoded by static GNN and then processed by an RNN module (Sankar et al.) 2020 Pareja et al. 2020 Kazemi et al. 2020). Such methods fail to learn fine-grained temporal patterns at smaller timescales within each snapshot. Therefore, several RNN-based methods were introduced that sequentially update node embeddings as new edges arrive. JODIE [Kumar al. 2019) employs two RNN modules to update the source and destination embeddings of an arriving edge. DyRep (Trivedi et al., 2019) adds temporal attention layer to take into account multi-hop interactions when updating node embeddings. TGAT (Xu et al. 2020) includes
cnmention-basee Message- Passing (AMP) architecture to aggregate messages from a historical neighborhood. TGN (Rossi et al. 2020 alleviates the expensive neighborhood aggregation of TGAT by using an RNN memory module to encode the history of each node. CaW (Wang el. al.) 2021b) extracts temporal patterns through an expensive procedure that samples temporal random walks and encodes them with an LSTM. This procedure must be performed for every prodiction. PINT (Souza et al. 2022) is a menory-based method that leverages injective pressage-passingg and relative positional encodings overcome the theoretical weakness of both memory- based methods (e.g., TGN) and walk-based methods (e.g., CaW). Jin et al. (Jin et al. 2022 adapt Ca W to
2

---

Published in Transactions on Machine Learning Research (12/2023)
include spatio-temporal bias and exploitation-exploratii trade-off sampling biases, employing differential equations (ODE) to effectively model the irregularly sampled temporal interactions of a node. NAT (Luo & Li 2022) abandons the commonly used message-passing and walk-based paradigms and instead adopts dictionary- learning by caching a fixed mumber of interactions for each node. Node representations are then built by aggregating temporal and structural features within the cache. Finally, GraphMixer (Cong ct al., 2023b) uses conceptually simple MLP-based link classifier that summarizes structural information from the latest temporal links and achieves surprisingly decent performance.
Self-supervised representation learning: Multiple works explore learning visual representations without labels {Liu et al. 2021). The more recent contrastive methods generate random views of images through data augmentations, and then force representations of positive pairs to be similar while pushing apart representations of negative pairs (Chen et al.) 2020a He et al., 2020]. With the goal of attaining hard negative samples, such methods typically use large batch sizes Chen et al. (2020a) or memory banks (He et al.,
2020 Chen et al., 2020b). Non-contrastive methods such as BYOL (Grill et al.) 2020) and VICReg (Bardes) et al. 2022) eliminate the need for negative samples through various techniques such as regularization architecture tricks that avoid representation collapse (Jing et al. 2022). Recently, several SSL methods have been adapted to pre-train GNNs (Xic et al. 2022). BGRL (Thakoor et al., 2022) adapts BYOL to graphs to eliminate the need for negative samples, which are often memory-heavy in the graph setting, In this work, we follow a principled approach for SST pre-training based on VICReg (Balestriero & LeCun 2022) compared to other methods such as BGRL that rely on architecture tricks and heuristics.
Most adaptations of SSL for dynamic graphs have focused on improving downstream task performance via auxiliary losses rather than learning general pre-trained models. Previous works (Jiang et al., 2021 either use contrastive learning methods, which require high memory and computation due to negative sampling (Thakoor et al., 2022), or incorporate weak encoders (Tian et al.] 2021), which leads to performance deteri- oration, particularly for large-scale graphs. Furthermore, readily adapting prior SSL methods to temporal domains is non-trivial as dynamic graphs can involve heavy distribution shifts. For example, new nodes arrive and others depart, and these arrival palterns occur at different timescales. As a result, there has been limited success in adapting SSL pre-training to dynamic graphs.
Position of our work: DyG2Vec relics on efficient message-passiin GNNs without requiring the computa- tionally expensive temporal causality subgraph sampling (Xu el al. 2020). Our archilecture does not use complex memory-basee architectures which require designing memory update schemes and can suffer from obsolete node memory for large batch sizes (Zhou et al.) 2022). While random-walk--bssed works (Wang et al. 2021b; Jin et al.] 2022) alleviate these issues with online feature construction through causal walks, such methods are orders of magnitude slower and difficult to parallelize on GPUs (Luo & Li 2022). In contrast to prior works, our method neither maintains cache or memory for each node nor requires the full history to make predictions. Instead, it operates on a fixed-size window of the past relations to
generate node embeddings. Furthermore, we fall under the message-passing paradigm which can leverage GPU parallelism using cutting-edge frameworks (Fey & Lenssen, 2019). Last, we propose joint-embedding architecture that is compatible with recent SSL methods. In our experiments, we show how this allows the model to learn temporal patterns even without direct training on downstream tasks.
3 Problem formulation
A Continuous-Tine Dynamic Graph (CTDG) 9 (V, E, x) is a sequence of F. = |8] interactions, where X = x=(X", x)) is the set of input features containing the node features X E NNDD and the edge features x E RED = eel,e2...., is the set of interactions. There are N = | nodes, and D and D2 are the dimensions of the node and edge feature vectors, respectively. An edge interaction between any two nodes u;, vi E V, with 4 E R being a continuous timestamp, and m, E X an edge feature vector, For simplicity, we assumee that the edges are undirected and ordered by time (i.e., 4 S 1. A temporal sub-graph G is defined as a set consisting of all the edges in the interval [t,, ty). such that E, = {ex & S t4 < t,). Any two nodes can interact multiple times throughout the time horizon; therefore, g is multi-graph.
(w,, U; ts, m,) is an
3

---

Published in Transactions on Machine Learning Research (12/2023)
Our goal is to learn model f that maps the imput graph to representation space. The model is pre-trainable encoder-decoder architecture, / (go,dy). The encoder go maps dynamic graph to node embeddings H NND' the decoder d, performs task-specific prediction given the embeddings. The model parameterized by the encoder prcoder/decodee decoder parameters (0,7). More concretely,
H = go
2 2H;
(1)
where x E RD is the prediction of task-specific labels (e.g., edge prediction or source node classification labels) of the larget (future) edge The node embeddings H must capture the temporal and structural dynamics of each node such that the future can be accurately predicted from the past, e-g., future edge prediction given past edges. The main distinction of this design is that, unlike previous dynamic graph models (Rossi al. 2020 Xu et al. 2020 Wang et al. 2021b), the encoder must produce embeddings independent of the downstream task specifications. This special trait can allow the model to be compatible with the SSL paradigm where an encoder is pre-trained separately and then fine-tuned together with a task-specific decoder to predict the labels.
To this end, we present a novel DyG2Vec framework, that can learn rich node embeddings at any timestamp independent of the downstream task. DyG2Vee is formulated a two-stage franework. In the first stage, use non-contrastive SSL method to learn the model JssL= (go,dæ) over various sampled dynamic sub-graphs with self-supervision. dø is SSL decoder that is only used in the SSL pre-training stage. In the second stage, a task-specific decoder d, is trained on top of the pre-trained encoder ge to compute the outputs for the downstream lasks, e.g., future edge prediction or dynamic node classification (Xu et al. 2020 Wang et al. 2021bb.
We consider two example downstream tasks: future link prediction (FLP), and dynamic node classification (DNC). In each task, we make a prediction on a set of target (positive) edges E. For FLP, this is augmented by a set of negative edges. Each negative edge (uj, v/ ij m2) differs from its corresponding positive edge only in the destination node, v/ f tj, which is selected at random from all nodes. The FLP task is then binary classification for the test set of 2| odges. In the DNC task, a dynamic label is associated with each node that participates in an interaction. We are provided with {(ug, ie., the source node and interaction time. The goal is to predict the source node labels for the test interactions. It is imporland to note that each prediction must be made given only access to the past, i.e., edges before time ty. The performance metrics are detailed in Appendix
4 Methodology
We now introduce our novel dynamic graph learning framework DyG2Vec. We first outline the encoder architecture. We then introduce the window-based downstream training approach. Finally, we present the SSL approach that can be optionally used to pre-train the dynamic graph encoder.
4.1 DyG2Vec Encoding Model
Our encoder combines self-attention mechanism for pussagg-passing with learnable time-encoding module that provides relative time encoding, We also introduce novel temporal edge encoding that efficiently captures the temporal structural relationship between nodes. The full architecture is outlined in Figure [ For simplicity, we define the message passing on any input graph G; however, as shown in Figure[] the input graph is restricted to be a window of the full graph. See Section 4.2 for details.
Temporal Attention Embedding: Given any input dynamic graph 9, the encoder Bg computes the embedding h E D' of node through series of L multi-head attention (MHA) layers (Vaswani et al. 2017) that aggregate messages from its L-hopp neighborhood (Xu al. 2020 Velickovie et. al. 2018).
4

---

Published in Transactions on Machine Learning Research (12/2023)
[hj 16f-11 E (1,2,3)
W
Temporal Attention Embedding
1ych
Temporal Edge
Encoding
heads
G w.
Es
Time Encoding
R|, v
F6
q'
Attention
f--W
Concatenation
:Adition
0
Activation
Skip Connection
Figure 1: Using VyG2 window framework to encode the target node u. Every slice of the dynamic graph G contains edges that arrived at the same contimuous timestamp. The blue interval represents the history graph Giww, that encoded make a prediction on the larget edge (u, v). Note that both and e share the same sampled history graph. For simplicity, we omit edge features mp from the attention encoder.
Given node embedding h at layer 1-1, we uniformly sample N 1-hop neighborhood interactions of node i, N(i = . ex) S E, where p, k E {1, [E]. The embedding h at layer is calculated by:
h Wi 1h + MH' K', v²),
(2)
q' h!-!,
(3)
K' v = [ ( (1)) +
(4)
Here, W1 is learnable mapping matrix, M.) is multi-head dot- dot-product attention layer, and (tp)
represents the edge feature vector of edge ep (Up: Up. 4p mp)) E (i) at time lp:
/ [ fp(tp) mp)
(5)
4 = - tp) + 1pp(t)) max (ti la (()))
ft((p)
(6)
(7)
where || denotes concatenation and the Time Encoding module Φ(t) = wroowrt....cco cos wptt is a learnable
Time2Vec module that helps the model be aware the relative timespan between a sampled interaction and the most recent interaction of node in the input graph. (.)() RD" is a temporal edge encoding function, described in more detail below. In contrast to TGAT's recursive message passing procedure (Xu) et al. 2020), the message passing in encoder is 'flat': at every iteration, the same set of node embeddings is used to propagate messages to neighbors. That is, we do not restrict mossages to flow towards the source node only but rather treat the sampled temporal graph as undirected. This allows the encoder to better capture the multi-hop common neighbors between the target nodes, which are vital to learning the temporal motifs and predicting future interactions. Moreover, unlike CaW (Wang et al. 2021b), we do not restrict the neighbor sampling go backwards in time (i.c. causal sampling) as we found this to be too restrictive and degrade the overall performance on downstream tasks (See Section G Lastly, note that the relative time encoding is with respect to the latest timestamp, f,, incident to the source and not with respect to the target edge timestamp; hence, allowing the encoding step to be independent of the prediction (decoding) step and making the generated embeddings task-agnostic.
Temporal Edge Encoding: Dynamic graphs often follow evolutionary patterns that reflect how nodes interact over time (Kovanen et al., (011). For example, in social networks, two people who share many friends are likely to interact in the future. Therefore, we incorporate two simple yet effective temporal encoding methods that provide inductive biases to capture common structural and temporal evolutionary
5

---

Published in Transactions on Machine Learning Research (12/2023)
Dynamic Graph
Temporal Subgraph Sampler
Mini- Batt-BBachhee of sub-graphs
Views
Embedding
Prediction
g
DZ))
G = (V)
ge
H
P
(22)
(G, B; W)
s(Z', zz
d"
ge
H
PΦ
Z"
c(z")
G"
v(Z")
The joint embedding architecture for the non-contrastive SST. Framework. Each slice of the input dynamic graph contains edges arriving at the same continuous timestamp. B is a batch of intervals of size W. & is a batch of the corresponding input graphs of each interval.
Figure 2:
behaviour of dynamic graphs. The temporal edge encoding function, parameterized by W RRDxx3 x3 is them:
(p(()) = Walco((>)lco((>>)
where we incorporate (i) Temporal Degree Centrulity zp zp(4p) E R2: the concatenated current degrees of nodes Up and Up at time lpi and (ii) Common Neighbors (1)) E R: the number of common 1-hop neighbors between nodes up and vp at time fp.
By using the degree centrality as an edge feature, the model is able learn any bias towards more frequent interactions with high-degree nodes. The number of common neighbors helps capture temporal motifs, and it is known to often have strong positive correlation with the likelihood of a future interaction (ao et al. 2016
4.2 DyG2Vec Downstream Training
In the downstream training stage, the DyG2Vec model f (ge, d,) consists of the encoder ge and a task- specific decoder d, which is trained using a similar window-based based training strategy. The model is trained to make predictions depending on the downstream tasks (c.g., link prediction or node classification). It is important to note that all lasks considered for dynamic graphs involve predicting a (future) target edge given access to the past interactions. However, rather than having access to all past edges, we limit the model to fixed window of W interactions. That is, to predict target edge ē (uj, Ug tj, my), sample input (history) graph Gy-w.j from the time interval {ty-w. w.,t,, centered at uy and By, and make prediction follows: H = go (oG))w.j) is the matrix of node embeddings returned by the encoder, and = (H::)) Z) is the prediction output of the decoder. The model parameters are optimized by training with a loss function CD(z,o) o). where CD is defined depending on the downstream task and o contains task-specific labels (See Section 3 is important to note that, unlike previous methods (Xu et al., 2020 Wang et al., 2021b)), the embeddings of u, and Uy are generated through message passing on the same sampled graph. Consoquently, the encoder can better recognize similar historical patterns between the target nodes without the need for costly motif-correlation through counting that is performed in walk- methods (Wang et al. 2021b Jin
et al. 2022
The window-based training strategy has several major advantages. First, the window acts as a regularizer by providing a natural inductive bias towards recent edges, which are often more predictive of the immediate future. Second, avoids costly time-based neighborhood sampling (Wang et al. 2021b). Third, relying on a fixed window-size for mosssag-ppassigg allows for constant memory and computational complexity, which is well-suited to the practical online streaming data scenario.

---

Published in Transactions on Machine Learning Research (12/2023)
4.3 Self- Pre-training for Dynamic Graphs
Previous work (Paranjape et al. 2017) has shown that (emporal motils develop at different timescales throughout a dynamic graph. For example, question-answer patterns on StackOverflow typically take 30 min to develop while messaging patterns on social media platforms can take less than 20 minutes to form. Inspired by such observations, we outline a hindow-based pre-training strategy where the encoder can be pre-trained on sliding window of the dynamic graph an effort to learn the fine-grained temporal patterns throughout the time horizon. The full pre-training procedure is displayed in Figure 2
Given the full imput dynamic graph Go set of intervals I is generated by dividing the entire time-span (lo, } into M = [F/S] -1 intervals with stride S and interval length W (See Appendix A.3 for details). Let B C I be a mini-batch (randomly sampled subset) of intervals. Given B, the temporal subgraph sampler m (G, B; W) constructs the mini-batch of input graphs: 9 = { [t,j) E B}. In principle, 9.5 E Ô is an
input graph to the SSL pre-training. The parameter W controls the size of the window while S controls the stride between intervals. In practice, we found that sctting S = 200 and W = 32K gives a rcasonable trade-off to learn both the long-range and short-range patterns within the dynamic graph.
We formulate a joint-embedding architecture (Bromley et al. 1993 for DyG2Vec in which two views of a mini-batch of sub-graphs are generated through random transformations. The transformations are randomly sampled from a distribution defined by a distortion pipeline. The encoder maps the views to node embeddings which are processed by the predictor to generate node representations. We minimize an SSL objective (Eq. described below) to optimize the model parameters end-to-end in the pre-training stage.
Views: The temporal distortion module generates two views of the input graphs g = d' (9) and g" = =d' (G) where the transformations d' and d" are sampled from distribution T over a pre-defined set of candidate graph transformations. In this work, use edge dropout and edge feature masking (Thakoor et al. 2022) in the transformation pipeline. See Appendix
A.3 for more details.
Embedding: The encoding model go is an Attention-based Ceessag--Passigg (AMP) neural network pre- sented in Sec. 4.1 It produces node embeddings H' and H" for the views & and g" of the input graphs Gt,. We elaborate on the details of the encoder in Sec. 4.1
Prediction: The decoding head dy for self-supervised learning design consists of MLP prodictor pe that outputs the final representations z and z", where Z = p.
SSL Objective: In order learn useful representations, we minimize a regularization-basel SSL loss
function [Baddes et al. 2022
LSSL = >s(Z z²) =(o(())) + v(z + +c("")
(9)
In this loss function, the weights X, μu, and v control the emphasis placed on each of three regularization terms. The invariance term 8 encourages representations of the two views to be similar. The variance term included to prevent the well-known collapse problem (Jing et al. (022). The covariance term e promotes maximization of the information content of the representations. See Appendix A.1 for details.
Note that this pre-training stage is only performed when needed i.e. target labels are scarce. Following the pre-training stage, we replace the SSL decoder with task-specific downstream decoder d, that is trained on top of the frozen pre-trained encoder.
5 Experimental Evaluation
5.1 Experimental Setup
Baselines: We compare VeG to five stale-of-the-ar, baseline models: DyRep (rivedi el al. 2019 JODIE (Kumar et al. 2019), TGAT (Xu et al. 2020), TGN (Rossi et al. 2020), CaW (Wang et al. 2021b and NAT (Luo Li 2022). DyRep, JODIE, and TGN sequentially update node emboddings using an RNN. TGAT applies message passing via attention on a sampled temporal subgraph. CaW samples temporal random walks and learns temporal motifs by counting node occurrences in each walk. NAT builds temporal
7

---

Published in Transactions on Machine Learning Research (12/2023)
Table I: Dynamic Graph Datasets. % Repetitive Edges: % of edges which appear more than once.
Dataset
# Nodes
Edges
# Unique Edges
Edge Features Node Labels
Bipartite
% Repetitive Edges
Reddit
11,000
672,447
78,516
54%
Wikipedia
9,227
157,474
18,257
48%
MOOC
7,144
411,749
178,443
53%
LastEM
1980
1,293,103
154,993
68%
UCI
1899
59,835
13838
62%
Enron
184
125,235
2215
92%
SocialEvolution
2,099,519
2506
97%
node representations using cache that stores a limited set of historical interactions for each node. Appendix A.2.3 contains additional comparisons to the GraphMixer (Cong et al. 2023b baseline.
Table 2: Future link Prediction Performance in AP (Mean + Std). Bold font and ul font represent first- and second-best performance respectively. DyG2 is trained end-to-end with no pre-training.
Setting
Model
Wikipedia
Reddit
MOOC
LestFM
Enron
UCI
SocialEvol.
Trasductive
JODIE
0.956 0.002
0.979 0.001
0.797 + 0.01
0.691 + 0.010
0.785 + 0.020
0.869 + 0.010
0.847 0.014
DyRep
0.955 + 0.004
0.981 + 1c-4
0.840 0.004
0.683 + 0.033
0.795 = 0.042
0.324 0.076
0.885 0.004
TGAT
0.968 0.001
0.986 4: 3e
0.793 0.006
0.633 1 0.002
0.637 0.002
0.835 0.003
0.631 0.001
TGN
0.986 0.001
0.985 0.001
0.911 + 0.010
0.743 + 0.030
0.866 0.006
0.843 0.030
0.966 0.001
CaW
0.976 + 0.007
0,988 + 2c-4
0.940 + 0.014
0.903 + 1e-4
0.970 = 0.001
0.939 + 0.008
0.947 = 1c-1
NAT
0.987 +: 0.001
0.991 +: 0.001
0.874 :: 0.004
0.859 1: 1e-4
0.924 = 0.001
0.944 : 0.002
0.944 + 0.010
DyGe
0.995 0.003
0.996 + 2c.4
0.980 + 0.002
0.960 + 1c.4
0.991 0.001
0.988 0.007
0.987 + 2e.4
JODIE
0.891 0.014
0.865 0.021
0.707 +: 0.029
0.865 1:
0.747 0.041
0.753 0.011
0.791 0.031
Inductive
DyRep
0.890
0.002
0.921 0.003
0.723 + 0.009
0.869 + 0.015
0.666 0.059
0.437 0.021
0.904 + 36-4
TGAT
0.954 + 0.001
0.979 + 0.001
0.805 2 0.006
0.644 + 0.002
0.693 = 0.004
0.820 + 0.005
0.632 + 0.005
TGN
0.974 1: 0.001
0.954 +: 0.002
0.855 - 0.014
0.789 1 0.050
0.746 = 0.013
0.791 = 0.057
0.904 + 0.023
CaW
0.977 0.006
0.984 +- 2c-4
0.933 + 0.014
0.890 + 0.001
0.962 0.001
0.931 + 0.002
0.950 + 1e-4
NAT
0.986
0.001
0.986 0.002
0.832 1 1e-4
0.578 0.003
0.949
0.010
0.926 = 0.010
0.952 = 0.006
DyG2Vee
0.992 0.001
0.991 0.002
0.938 0.010
0.979 0.006
0.987 0.004
0.976 0.002
0.978 0.010
We evaluate all models two temporal tasks: future link prediction (FLP), and dynamic node classification (DNC). In FLP, the goal is to predict the probability of future edges occurring given the source, destination, and limestamp. For each positive edge, we sample a negative edge that the model is trained to predict as negative, The DNC task involves predicting the label of the source node of a future interaction. Both tasks are trained using binary cross entropy loss. For FLP, we evaluate all models on the transductive and inductive settings. The latter is a more challenging setting where a model makes a prediction on unseen nodes. See Appendix
Downstream Tasks:
for details.
For the FLP task, report the Average Precision (AP) metric. For the DNC task, we report the area under the curve (AUC) metric due to the prevailing issue of class imbalance in dynamic graphs. By default, Vec is trained end-to-end with no pre-training, just like the baselines. The pre-training stage is only performed to test the potential benefits of SSL (e.g. Fig. 4. Additional results on the benefits of SSL can be found in Appendix A.2
Datasets: We use 7 real-world datasots: Wikipedia, Reddit, MOOC, and LastFM (Kumar et al. 2019): SocialEvolution, Enron, and UCI (Wang et al., (0221b) These datasets span a wide range in terms of number of nodes and interactions, time range, and repetition ratio. The dataset statistics are presented in Table I We perform the same 15%% chronological split for all datasets in Wang et al. (2021b). The datasets are split differently under two settings: Transductive and Inductive. Under the transductive setting, a datasel is split normally by time, ie., the model is trained on the first. 70% of links and lested on the rest. In the inductive setting, we strive to test the model's prediction performance on edges with unseen nodes. Therefore, following Wang et al. (2021b), we randomly assign 10% of the nodes to the validation and test sets and remove any interactions involving them in the training set. Additionally, ensure an inductive setting, we remove any interactions not involving these nodes from the test set.
8

---

Published in Transactions on Machine Learning Research (12/2023)
Training Protocols and Hyperparameters: In Table 2 DyG2Vec is initialized with random parameters and trained end-to-end on the rownstreem tasks and compared to all supervised baselines. In the semi- supervised evaluation setting (left figure of Fig. g. the decoder is trained on top of the frozen (SSL pre- trained) encoder on a random portion of the dataset (i.c., a fraction of the target edges). The DyG2Vec encoder performs = 3 layers of message passing. We sample N 64 temporal neighbors at the first hop and 1 neighbor at the second and third hops. All neighbors are sampled uniformly at random. We found that uniform sampling within a window works better than only looking at the latest N neighbors of node (Xu et al. 2020; Rossi et al., 2020). Other hyperparameters are discussed in Appendix A.3 For the DNC task, following prior work (Rossi et al. 2020). the decoder is trained on top of the frozen encoder that is pre-trained on the future link prediction task.
5.2
Experimental Results
Speed vs Perforaane: LastFM PyG2Vec
Speed vs Performance: SocialEvol.
Speed ys Performance: MOOC
PyG2Ver
4 +yG2Vec
0.95
0.90
CaW
0.95
NAT
JGN
CaW
0.95
CaW
0.85
NAT
DyRep
TGN
0.85
0.90
0.80
JGN
0.75
0.85
0.70
Jodie DyRep
DyRep
0.65
JGAT
0.65
JGAT
Jodie
TGAT
1000
2000
3000
40000
100
Inference Time (Seconds)
Inference Time (Seconds)
Inference Time (Seconds)
Figure 3: Transductive FLPP Performance (Test AP) vs Inference runtime (s) 3 datasets. Inference time represents the time it takes to predict the whole test set. The test sets are approximately of size 400K, 600K, and 100K edges respectively.
Future Link Prediction: We report the test AP scores for future link prediction in Table Our model outperforms all sequential and message-passing baselines 7/7 of the datasets in the transductive setting, The gap is particularly large on the UCI and LastFM datasets, where DyG2Vec outperforms the second-best methods (NAT and CaW) by over 4% and 6% respectively. Interestingly, while SocialEvol. is the largest dataset with ~ 2M edges, our model is able to achieve SoTA performance while only using the last 8000 edges to predict any future edge. This further cements the findings in Xu et al. (2020) that capturing recent interactions may be more important for cerlain tasks. Our window-based framework offers a good trade-off between capturing recent interactions and recurrent patterns which both have a major influence on future interactions. In the inductive scttings, most methods drop in performance due to the difficult nature of predicting over unseen nodes. However, DyG2Vee still outperforms the best methods significantly (e.g., 8% gap for LastFM) which demonstrates its ability to learn temporal motifs rather than overfitting to node identities.
Table 3: Transductive Dynamic Node Classification Performance in AUC (Mean Std). Avg. Rank reports the mean rank of a method across all datasets.
Model
Wikipedia
Reddit
MOOC
Avg. Rank 1
TGAT
0.800 + 0.010
0.664 + 0.009
0.673 0.006
3.0
JODIE
0.843 + 0.003
0.566 + 0.016
0.672 0.002
3.7
Dyrep
0.873 + 0.002
0.633 + 0.008
0.661 = 0.012
3.3
TGN
0.828 + 0.004
0.655 + 0.009
0.674 0.007
2.3
DyG2Vec
0.824 + 0.050
0.649 + 0.020
0.785 = 0.005
2.6
Dynamic Node classification: We evaluate DyG2Vec on 3 datasets for node classification where the labels indicate whether user will be banned from editing aditing/posting after an interaction. This task is challenging both due to its dynamic nature (i.e. nodes can change labels) and the high class imbalance (only 217 of
9

---

Published in Transactions on Machine Learning Research (12/2023)
157K interactions result in ban). We measure performance using the AUC metric to deal with the class imbalance. Table 3 shows that DyG2Vec outperforms all baselines on the MOOC dataset significantly by over 10%. For Wikipedia and Reddit, DyG2Vec is within - 5% of the best performance. Overall, none of the methods display the best performance consistently across all 3 datasets. We believe this is due to the high class imbalance problem which makes it a better fit for anomaly detection methods (Ranshous et al. 2015).
Training/ IInfereneeeneeeeee Speed: Relying fixed window of history to produce task-agnostic node embed- dings gives DyG2Vec significant advantage in speed and memory. Figures 0 and i show the performance and runtime per epoch of all methods on the three large datasets: LastFM, SocialEvolution and MOOC. DyG2Vec is many orders of magnitude faster than CaW due to the latter's expensive random walk sam- pling procedure. RNN-based methods such as TGN have a good runtime on LastFM and MOOC; however, they are significantly slower on SocialEvol. which has a small number of nodes (74) but a large number of interactions (~ 2M). This suggests that memory- basod methods are slower for scttings where a node's memory updated frequently. Furthermore, while TGAT has a similar AMP encoder, DyG2Vec improves the efficiency and performance significantly. This reveals the significance of the window-basee mechanism and the encoder architecture. Overall, DyG2Vee presents the best trade-off between spoed and performance. A more detailed complexity analysis is included in Appendix A.2
Semi-supervised Learning on Dynamic Node Classification: The DNC task is challenging due to its highly imbalanced labels. In Figure 4 we show that SSL an effective pre-training strategy for the DNC task, particularly in the low-label data regime where each model trained on a portion of the target edges, This highlights the potential of SSL to effectively unlabeled data for representation learning and prevent representations from overfitting to such inbalanced classification tasks.
0.750
0.022
Wikipedia
MOOC
UCI
0.020
0.700
Test AUC
0.675
Alpha
0.018
0.650
0.625
Setting
0.016
Random-init SSL-init
0.600
10%
40%
80%
1009
Percentage of Training Data
0.0 0.2
0.6
0.8
Normalized Relative Timespan Figure 4: First figure plots Semi-Supervised Learning results on Dynamic Node Classification. For each setting, DyG2Vec was trained on a varying random portion of the training data. Second figure plots the Average Attention Weight versus Relative Timespan for DyG2Vec trained with W = 64K. The relative timespan is normalized with the maximum timespan across all interactions. higher timespan means a farther interaction.
5.3 Ablation and Sensitivity Analysis
We perform detailed study on different instances of our framework with datasets. All ablation results are reported in Figure 5
We observe that large window size works best for most datasets. However, we see a minor drop in performance (~ 1%) for MOOC due to the inherently different recurring temporal patterns. As observed by Xu et al. (2020), recent and/or recurrent interactions are often the most predictive of future interactions. Therefore, datascts with long range dependencies favor larger window sizes to capture the recurrent patterns while some datasets benefit from an increased bias towards recent interactions. Our window-based framework coupled with uniform neighbor sampling strikes balance bet the two. This
Window Size:
10

---

Published in Transactions on Machine Learning Research (12/2023)
w/ Temporal Edge Features
W/o Temporal Edge Features
0.99
0.98
0.98
0.95
Test
0.97
0.96
0.94
Wile pedia
Wikipedia
0.95
MOOC
MOOC
0.80
UCI
UCI
0.94
512
2k
4K
8K
16K
32K
64K
Wikipedia
MOOC
UCI
Window
Layers
Figure 5: Ablation, sensitivity, and attention analysis on 3 datasets for the FLP transductive task.
shows that the fixed window size also contributes to the performance as it helps limit irrelevant information that is not highly predictive of future interactions. Nonetheless, as we show in Section 6 the attention- encoder coupled with the time encoding function is able to learn the innate temporal dependencies regardless of the window size.
Number of Layers: Increasing the number of embodding layers improves performance for most datascts, and this effect is more noticeable for some (e-g., MOOC). This suggests that these datasets contain higher order temporal correlations among the nodes that must be learned using rang- message passing. Overall, the results show that one can choose to sacrifice some performance to further improve the speed of DyG2Vee by decreasing the window size and the number of layers.
Temporal Edge Features: The results show a substantial decrease in performance for MOOC when temporal edge features are removed (i.e., 1-4% drop). This indicates that such temporal edge features provide useful multi-hop information about the evolution of the dynamic graph (Yao et al. 2016).
6 Analysis
Effect of Encoder Architecture: As noted carlier, of the main advantages of DyG2Vec over the baselines is its transformer-basee architecture. Combined with the simple time-encoding module, DyG2Vee can selectively aggregate temporal and structural information across neighbors that are relevant to the target prediction. Moreover, unlike the baselines, message passing for the source and larget nodes is performed on a shared undirected sampled subgraph to easily detect common neighbors across time which are vital predicting future interactions. In Table 4 we show the effect of replacing our encoder architecture with the MPNN model (Gilmer al., 2017) which performs simple message passing with our temporal edge encodings. The results show significant. degradation (4-9%), displaying the benefits of transformers in attending to relevant history.
Table 4: Benefits of the encoder architecture in the FLP task. In the last row, we replace the transformer architecture (Sec. 4.1b with the simple MPNN architecture GGimeer et al. 2017). All experiments are performed for one trial only in the transductive setting.
Model
UCI
LastFM
Enron MOOC
DyG2Vec (Default)
0.981
0.960
0.990
0.988
DyG2Vec with MPNN
0.942
0.921
0.907
0.916
Attention Weight Analysis: A particular advantage of attention-based architecture is that attention weights allow for casy interpretability of the learned temporal dependencies. In Figure g (right plot), we plot. the atlention weights oi with respect to the relative timespan. That is, for each lest. target edge e, = (4, u/, t),, we plot the attention weights to the one- hop neighbors both target nodes, {a Itp e N(ux)} (Areor lb (W())), versus the relative timespans, {t... t,) U (t., t²). Here, t.,, represents the maximum timestamp incident to node u, Therefore, the attention weights indicate how much the model is attending to old and recent interactions. Unsurprisingly, higher importance is given to the most recent
11

---

Published in Transactions on Machine Learning Research (12/2023)
interactions. However, both Wikipedia and UCI display higher weights for larger timespans compared to MOOC, indicating that they have long-range dependencies. This explains why performance monotonically increases for Wikipedia as W increases while slightly degrades for the MOOC dataset, as seen in Figure 5
Neighbor Sampling and Temporal Edge Encoding: In T we study the effect of neighbor sampling and temporal edge encoding on the downstream FLP task. Although Fig- [ showws the importance of multi- hop sampling for discovering high-order temporal motifs, we found that DyG2Vec gives more importance to one-hop neighbors for most datasets. In fact, sampling 64 one hop neighbors gives SoTA performance compared to sampling 20 neighbors per hop (see 1st and 5th rows in Table 5 This suggests that the 1- hop recent interactions within window are the most representative interactions for future prediction tasks. Moreover, unlike prior random-walk and AMP mots (Xu et al. 2020 Jin et al. 2022 Wang et al. 2021b);
which argue for causal sampling (i.e. sampling backwards in time) to discover evolving temporal motifs, we have found this form of sampling have little effect on the performance (See 2nd row). Lastly, removing odge encodings almost always hurts performance. In fact, performing causal sampling with 20 neighbors each hop, as done in TGAT, and removing temporal edge encodings causes up to 8% drop in performance (See last row). Additional analysis the effect of temporal edge encodings baselines can be found in Appendix A.2
Table 5: Effect of neighbor sampling and temporal edge encoding performance. The first row is the default setting where we sample 64,1,1 neighbors at the first, second and third hops respectively.
Temporal Edge Encoding
Causal Sampling
Num Neighbors
Wikipedia
MOOC
UCI
64,1,1
0.995
0.982
0.988
64,1,1
0.993
0.984
0.986
64,1,1
0.990
0.957
0.980
64,1,1
0.989
0.965
0.976
20,20,20
0.992
0.949
0.981
20,20,20
0.984
0.955
0.971
20,20,20
0.990
0.927
0.958
20,20,20
0.982
0.906
0.946
7 Conclusion
We introduce DyG2Vec, a novel window-based encoder-decoder model for dynamic graphs. It an efficient attention-based message-passing model that utilizes multi-head attention modules encode node embed- dings across time. Furthermore, we present a joint-embedding architecture for dynamic graphs in which two views of temporal sub-graphs are encoded to minimize non-contrastive loss function. Our window-based architecture allows for efficient message-passingg passing and robust prediction abilitics. We aim to further explore ways to improve the capacity of the dynamic graph models to learn long-range dependencies. Additionally, it seems promising to investigate other SSL paradigms aligned with temporal graphs.
12

---

Published in Transactions on Machine Learning Research (12/2023)
References
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. In Proc. Adv. Neural Inf. Proc. Systems, 2022.
Adrien Bardes, Jean Ponce, and Yann LeCun. VICReg: Variane-iimariiacceoovviaa regularization for self-supervised learning. In Proc. Int. Conf. Learning Representations (ICLR), 2022.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a 'siamese' time delay neural network. In Proc. Adv. Neural Inf. Proc. Systems, 1993.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proc. Jnl. Conf. on Machine Learning, 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved basclines with momentum contrastive learning. ar preprint arXiv:2003.0422 2020b.
Weilin Cong, Yanhong Wu, Yuandong Tian, Mengting Gu, Yinglong Xia, Mehrdad Mahdavi, and Chun- cheng Jason Chen. Dyformer: A scalable dynamic graph transformer with provable benefits on general- ization ability. SIAM International Conference on Data Mining, 2023a.
Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mchrdad Mahdavi. Do we really need complicated model architectures for lemporal networks? In Proc. Inl. Conf. Learning Representations (ICLR), 2023b.
Emadeldeen Eldele, Mohamed Ragab, Zhenghua Chen, Min Wu, Chee Keong Kwoh, and et al. Time-series representation learning via temporal and contextual contrasting. In Proc. Int. Joint Conf. on Artificial Intelligence, 2021.
Matthias Fey and Jan F. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman, and Yann LeCun. On the duality between contrastive and non-contrastive self-supervised learning. In Proc. Inl. Conf. Learning Representalions (ICLR), 2023.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proc. Int. Conf. Machine Learning, 2017.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, and et al. Bootstrap your own latent a new approach self-supervised learning. Tn Proc. Adv. Neural Tnf. Proc. Systems, 2020.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proc. IEEE Conf. Computer Vision and Pattern Recognition). 2020.
Linpu Jiang, Ke-Jia Chen, and Jingqiang Chen. Self-supervised dynamic graph representation learning via temporal subgraph contrast. XrXiv preprint arxiv:21 12.08733, 2021.
Yizhu Jiao, Yun Xiong, Jiawci Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. Sub-graph contrast for scalable self-supervised graph representation learning. IEEE International Conference on Dala Mining (ICDM), 2020.
Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on contimuous-ting dynamic graphs. In Proc. Adv. Neural Inf. Proc. Systemss, 2022.
Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive self-supervised learning. Tn Proc. Inl. Conf. Learning Representations (ICLR), 2022.
13

---

Published in Transactions on Machine Learning Research (12/2023)
Seyed Mehran Kazemi, Rishab Goel, Sepehr Eghbali, Janahan Ramanan, Jaspreet Sahota, Sanjay Thakur, Stella Wu, Cathal Smyth, Pascal Poupart, and Marcus Brubaker. Time2vec: Learning vector represen- tation of time. arXiv preprint arXic:1977.0532/ 2019.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey, Journal of Machine Learning Research, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. Inl. Conf. Learning Representations (ICLR), 2015.
Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 2011.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. Proc. Int. Conf. on Knowledge Discovery & Data Mining, 2019.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self-supervised learning: Generative contrastive. JEEE Transaclions Knowledge and Dala Engineering, 2021.
Yuhong Luo and Pan Li. Neighborhood-awwar aware scalable temporal network representation learning. In The First Learning on Graphs Conference, 2022.
Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. Motifs in temporal networks. In ACM Int. Conf. on Web Search and Data Mining, 2017.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, and et al. Evolvegen: Evolv- ing graph convolutional networks for dynamic graphs. Proc. of the AAAI Conference on Artificial Intel- ligence, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, and et al. Pytorch: An imperative style, high--peformance deep learning library. In Proc. Adv. Neural Inf. Proc. Systems. 2019.
Mandela Patrick, Yuki M. Asano, Polina Kuznetsova, Ruth Fong, João F. Henriques, Geoffrey Zweig, and Andrea Vedaldi. Multi-modal self-supervision from generalized data transformations. In Proc. Int. Conf. on Computer Vision, 2021.
Stephen Ranshous, Shitian Shen, Danai Koutra, Steve Harenberg, Christos Faloutsos, and Nagiza F. Sama- tova. Anomaly detection in dynamic networks: a survey. WIREs Computational Statistics, 7(3):223 247, 2015.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bron- stein. Temporal graph networks for deep learning on dynamic graphs. In ICML Workshop on Graph Representation Learning, 2020.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning dynamic graphs via self-attention networks. In Proc. Int. Conf. Web Search and Data Mining, 2020.
A. H. Souza, D. Mesquita, S. Kaski, and V. Garg. Provably expressive temporal graph networks. In Proc. Adv. Neural Inf. Proc. Systems, 2022.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva. L Dyer, Remi Munos, Petar Veličkovié, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. Tn Proc. Int. Conf. Learning Representations (ICLR), 2022.
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, 2021.
14

---

Published in Transactions on Machine Learning Research (12/2023)
Zhan Tong, Yibing Song, Jue Wang, and Limin Wang. VidcoMAE: Masked autoencoders are data-efficient learners for self-supervised video pre-training In Proc. Adv. Neural Inf. Proc. Systems, 2022.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representa- tions over dynamic graphs. In Proc. Inl. Conf- Learning Representations (ICLR), 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proc. Adc. Neural Inf. Proc. Systems, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proc. Int. Conf. Learning Representations (ICLR), 2018.
Lu Wang, Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Le Song, Jingren Zhou, and Hongxia Yang. Tel: Transformer-bass dynamic graph modelling via contrastive learning. arXiv preprinl ar Xiv:21105. 07944, 2021a.
Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In Proc. Int. Conf. Learning Representations (ICLR), 2021b.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: unified review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. Proc. Inl. Conf. Learning Represenlations (ICLR), 2020.
Lin Yao, Luning Wang, Lv Pan, and Kai Yao. Link prediction based common-neighbors for dynamic social network. Procedia Computer Science, 2016.
Hongkuan Zhou, Da Zheng, Israt Nisa, Vasileios loannidis, Xiang Song, and George Karypis. Tgl: A general framework for temporal gnn training on sillion-scale graphs. Proc. VLDB Endow., 2022.
15

---

Published in Transactions on Machine Learning Research (12/2023)
A Appendix
A.1 Preliminary: VICReg
We outline the details of the VICReg (Bardes et al. 2022 method used our SSL pre-training stage. Given the representations of two random views of an object (e-g,, image) generated through random distortions, the objective of non-contrastive SSL is two-fold. First, the output representation of one view should be maximally informative of the input representation of the view. Second, the representation of one view should be maximally predictable from the representation of the other view. These two aspects are formulated by VICReg (Bardes et al. 2022) where a combination of 3 loss terms (i.e. Variance, Covariance, Invariance) is minimized to learn useful representations while also avoiding the well-known problem of collapse (Jing et al. 2022). More coneretely, let. Z = -.], representations of dimension d.
"h.....;2, 2/1 and Z" ...,.... = be the batches composed of n
Variance term: The variance regularization term is the mean over the representation dimension of the hinge function on the standard deviation of the representations along the batch dimension: vi v(Z) D EE=
Here Z is the column j of matrix Z. S is the regularized standard deviation defined by S(z,e) = <Var(z) e,, 7 is a constant value set to 1 in our experiments, and is small scalar that helps to prevent mumerical instability. This term avoids dimensional collapse by maximizing the volume of the distribution of the mapped views in all dimensions. In other words, it prevents the well-known trivial solution where the representations of the two views of a sample collapse to the same representation (Jing
ett al. 2022).
Covariance term: The covariance regularization terms C decorrelates different dimensions of the rep- resentations and prevents them from encoding similar information. The covariance matrix of Z is C(Z)= = Ez (2; - =)" where E == En= z, The covariance regularization ion term e is then defined as the sum of the squared off-diagonal coefficients of the covariance matrix as follows c(Z) = 3 "0t)(C())) where [C( is the element at and column j of the matrix C(Z). Both the variance and covariance terms helps to maximize the information encoded by the model in the representation space.
Invariance criterion: The invariance criterion s between Z and z" is defined as the mean squared 2
Euclidean distance between the representation vectors in the two views s(Z', zz) = + Σ, || 2 ll The
invariance term encourages the parametric mapping ensure that the views of an object remain close in the latent space.
Finally, the SSL loss function LSL over batch of representations is weighted average of the invariance, variance, and covariance terin::
CSSL 11z'( As(2 z") ulu(Z)) + +o(Z")) + ulc(Z') c(z))
(10)
In our experiments, we sct x = = 22 and v = 1, following Bardes et al. 2022
A.2
Additional Results
A.2.1 Effect of Temporal Edge Encodings on Baselines
Our proposed temporal edge encodings theoretically improve the expressiveness of DyG2Vec (ouza ct al. 2022). In Table 0 we investigate whether they can also improve the basclines' performance. That is. we add the temporal edge encodings outlined in Sec. 4.1 to some of the most powerful baselines, TGN Rossi et al. 2020) and CaW (Wang et al., 2021b). Interestingly, we notice only minor improvements (1-2%) for some datascts and, in some cases, minor dogradations. We hypothesize that this is due the nature of basclines' encoder architectures. The use of RNNs or random walks encoder history can make it difficult to effectively leverage the relevant temporal edge encodings across long time horizons.
16

---

Published in Transactions on Machine Learning Research (12/2023)
Table 6: Effect of temporal edge encodings on baselines. All experiments are performed for one trial only
the FLP transductive setting. Temporal edge encodings are simply added as edge features the basclines.
Temporal Edge Encoding
Baseline
UCI
Enron
MOOC
TGN
0.894
0.867
0.911
V
TGN
0.879
0.872
0.936
CaW
0.930
0.970
0.937
CaW
0.944
0.967
0.946
Speed Performance: LastFM
Speed Performance: SocialEvol.
Speed Performance: MODC
DyG2Vec
1.00
NAT
DyG2Vec
JGN
.CaW
1.00
DyG2Vec
,C&W
0.90
NAT
0.90
Sxfep
TGN
CCaW
Test
0.80
0.80
NAT
TGN
0.85
0,70
DyRep
Jodie
TGAT
0.70
JGAT
0.80
DyRRep JogTEGAT
0.60
0.60
2000 4000 6000 8000 10000 12000
5000
10000
15000
20000
0
1000
2000
3000
4000
Training Time (Seconds)
Training Time (Seconds)
Training Time (Seconds)
Figure Transductive FLP performance (Test. AP) vs Training Time (s) on datasets. Training time represents the time it takes to train on the whole training set.
A.2.2 Runtime and Computational Complexity
The main runtime overhead lies how each of the baselines processes the input graph to predict a target edge. CaW samples M L-hop random walks for each target edge. This is followed by an expensive set-based anonymization scheme. To achieve good performance, CaW can require relatively long walks (e-g., for Enron, L 5) On the other hand, memory-based methods and TGAT sample different L-hop subgraph for each target edge. DyG2Vec samples similar to TGAT but does within constant window size W and without enforcing temporal causality.
5).
Thus, assuming we use sparse operations in Pytorch Geometric Fey & Lenssen 2019 for message-passing, the encoding computational complexities are: DyG2Vec=O(LW))) O(L)); CaW = OOLM,, and TGN and variants O(LN,). Here, N₂ represents the maximun number of sampled nodes in an L-hop subgraph. We can see that the main difference is the factor M. The factor N, comes from the complexity of message passing each hop (assuming sparse operations). Note that DyG2Vec is limited to O(W) nodes it does not have this factor.
=
Table 7: Downstream Freeze test AP Results (after pre-training). DDGCL pre-training and downstream training were with default parameters described in the work.
Model
MOOC
Enron
UCI
LastFM
DyG2Vee
93.1
96.6
95.4
93.0 0
DDGCL
84.3
83.0
85.3
78.8
A.2.3 Comparison with Recent Dynamic Graph Models
GraphMixer [Cong et al. 2023b uses conceptually simple MLP- based link classifier that summarizes structural and temporal information from the latest temporal links and achieves surprisingly decent perfor- mance. Table compares DyG2Vec with GraphMixer on transductive future link prodiction. All results were generated under the same evaluation protocol in CaW (Wang el al. 2021bb, using the DyGlib library
17

---

Published in Transactions on Machine Learning Research (12/2023)
Table 8: AP performance on Transduction future link prediction (Mean Std).
Model
Wikipodia
Reddit
MOOC
LastF'
Enron
UCI
SocialEvol.
GrxehMixer
0.974 + 0.001
0.975 + 0.001
0.835 + 0.001
0.862 0.003
0.824 0.001
0.932 0.006
0.935 + 3e
DyG2Vec
0.992 = 0.001
0.991 + 0.002
0.938 = 0.010
0.979 = 0.006
0.987 = 0.004
0.976 = 0.002
0.978 1008
A.2.4 Comparison to other dynamic Graph SSL Methods
As mentioned in Section 2 DDGCL Tian et al. (2021) proposed contrastive SSL method for dynamic graphs that learns rich representations by contrasting node embeddings across time. Though experiments show improved performance on the future link prediction and dynamic node classification lask, we believe the approach comes with several shortcomings that limit it's advantages in real world graphs. First, is built on the TGAT Xu et al. (2020) encoder which, as seen in Table 2 is a weak encoder; particularly, for large datasets such as LastFM. Second, experiments for the FLP task are limited to the Reddit and Wikipedia datasets which are relatively easy. Lastly, the authors do not experiment under the standard settings in graph SSL literature such the freeze and semi-supervised settings. Table 7 shows the results for downstream future link prediction under the freeze setting. The results show up to 10% gap compared to DyG2Vec, particularly for datasets where the TGAT encoder under- mnder-performs (e.g. Enron, UCI).
A.2.5 SSL for Future Link Prediction
Table 9: Evaluating the performance of SSL pre-training using linear probing. Results are reported in AP
(Mean + Std) on Transductive Future Link Prediction.
Setting
UCI
Enron
MOOC
LastFM
Random-init
0.865 0.004
0.913 + 0.007
0.863 0.001
0.817 + 0.002
Supervised
0.988 0.007
0.991 = 0.001
0.980
0.002
0.960 + le-4
SSL-init
0.954 0.002
0.966 + 0.001
0.931 0.001
0.930 + 2e-4
Table 9 reports the transductive AP results for DyG2Vec under 3 different settings. Namely, we compare a random frozen encoder (Random-init) and an SSL pre-trained encoder (SSL-init) with the supervised base- line. Note that all variants use the DyG2Vec architecture. The difference lies how the encoder is initialized and whether is frozen during downstream training. SSL-init initialized with a pre-trained encoder that is frozen during downstream training while "Supervised" is initialized randomly and is fully trained (en- -deoodd))) on the downstream lask. The results reveal that our SSL pre-training learns informative node embeddings that are almost par with the fully supervised baseline. This supports the capability of the non-contrastive methods to learn generic representations across unlabelled large-scale dynamic graphs, which is in line with the findings for other data modalities (Bardes et al. 2022). The Random-in baseline is surprisingly good, as observed by recent works (Thakoor et al. 2022 but outperformed by the SSL pre-trained encoder.
A.2.6 Window-based Pre-training
In Table 10 we show the importance of window-based pre-training to learn the fine-grained temporal motifs of dynamic graphs. The 'Full-graph' SSL setting represents applying the SSL loss on the full dynamic graph at once for a total of 300 epochs. Note that this is similar to the pre-training strategy used on static graphs and difficult to scale for large scale graphs that do not fit memory. The window-based strategy outperforms the full-graph mode for most datasets, particularly for large graphs (e.g. MOOC and LastFM) where we observe up 10% gap.
A.3 Implementation Details
We train our model using the Pytorch framework (Paszke et al. 2019 The dynamic graph data and GNN encoder architecture are implemented using Pytorch Geometric (Fey & Lenssen 2019). The ReLU
18

---

Published in Transactions on Machine Learning Research (12/2023)
Table 10: Effect of Window-based pre-training on Linear probing AP results on Transductive FLP.
SSL Setting
UCI
Enron
MOOC
LastFM
Window-based
0.956
0.965
0.931
0.930
Full-graph
0.954
0.966
0.912
0.838
activation function is used for all models. The code and datasets are publicly available at htttss///iithu: hom/huawest mowaaweiinnoahhoo----eeeeee htwp://oaarrrrerrchehheeeeecaa htt.e/aarrcc/reee///mmtterrrraaa _atlas
Window-based framework: As mentioned in Section 4 during SSI pre-training, the full dynamic graph
Ga,E is divided into set of intervals I that is generated by dividing the entire time-span into M [E/S] -1 intervals with stride S and interval length W:
max mmx(0. (0, W), min(jS, 1 (1,2,..., ...
I I=
(11)
Here, W defines the number of edges in an interval and S defines the stride. Note that we include all intervals up to but not including [E W, F) so that the target interval contains at least one edge.
Decoder Architecture: Denote by guar the timestamp of the latest interaction, within the provided history, incident to node u. For future link prediction, to predict target interaction (u, v, t), our decoder maps the sum of the two node embeddings of and v and time embedding t- to edge probability. Following Xu et al. 2220), the FLP decoder is 2-layer MLP.
For dynamic node classification, to predict the label of node u for interaction (u, v. (), the decoder maps the source node embedding and time embedding of - emer to class probabilities. Following Xu et al. (020 the DNC dccoder 3-layer MLP with a dropout layer with p 0.1.
The time embedding is caleulated using a trainable Time2Vec module (Kazemi et al. 2019 The time embedding allows the decoder to be time-aware; hence, possibly output different predictions for the same nodes/edges at different timestamps.
For SSL pre-training, the predictor pa is a simple 2-layer MLP that maps node embeddings H to node representations Z.
Distortion Pipeline: We use the common edge dropout and edge feature dropout distortions. Both distortions are applied with dropout probability pa = 0.3 which have found to work best in validation experiment exploring the values Pa {0.1, 0.15, 0.2, 0.3). The edge feature dropout is applied on the temporal edge encodings introduced in Section 4.1 i.e., zp(4p) and (p()p).
fyper--arameters: We use a constant learning rate of 0.0001 for all datasets and tasks. DyG2Vec is trained for 100 epochs for both downstream and SSL pre-training. The model from the last epoch of pre- training used for reamstream training- For downsttream evaluation, we pick the model with the best validation AP performance. Overall, we found that DyG2Vec converges within 50 epochs.
For downstream training, We use a constant window size of 64K for all datasets except for MOOC, SocialE- volve, and Enron where we found a smaller window size of 8K works best. The batch size is set to 200 target edges. However, the model could be sped up by increasing batch size at the cost of higher memory. During SSL pre-training, we use a constant window size of 32K with stride 200.
Following previous work (Rossi et al., 2020 Xu al., 2020 all dynamic node classification training exper- iments are performed with L.2-docay parameter À 0.00001 alleviate over-fitting.
A.4 Baselines
Following prior work (Rossi et al. 2020 Xu et al. 2020), all basclines are trained with constant learning rate of 0.0001 using the Adam optimizer (Kingma & Ba 2015) on batch-size 200 for a total of 50 epochs. The early stopping strategy used to stop training if validation AP does not improve for 5 epochs.
Basclines:
19

---

Published in Transactions on Machine Learning Research (12/2023)
For JODIE (Kumar al 2019), DyRep Trivedi et al. 2019 and TGN Rossi et al. 2020 use the general framework implemented by Rossi et al. (020)) The node memory dimension is set to 172. For the NAT baseline Luo & Li (2022). we utilize the results in the paper for the common datasets since the setup is the same. We generate results for the missing datasets with the default hyperparameters. See Tables 12 and 11 for details.
For TGAT, we use the default hyperparameters of 2 layer neighbor sampling with 20 neighbors sampled each hop. For the CaW method, we tune the time decay parameter E S where S =, and length of the walks m {2, 3, 4, 5) on the validation set. The number of heads for the walking based attention is fixed to 8.
Table 1I: Hyperparameters for CaW.
Dataset
Time Decay a
Walk Length m
Wikipedia
4e-6
Roddit
1c-8
3
MOOC
1c44
3
LastFM
1e-6
UCI
1c-5
2
Enron
1e-6
5
SocialEvolution
30-5
3
A.5 Computing Infrastructure
All experiments were done on a Ubuntu 20.4 server with 72 Tntee(R) Xeo Gold 6140 CPU a 2.30GHz cores and a RAM of size 755 Gb. We use a NVIDIA Tesla V100-PCIE-32GB GPU.
A.6 Additional Related Work
Self-supervised learning for dynamic graphs: Jiang et al. (2021) adapt a sub-graph contrastive learning method (Jiao el al. 2020 where a node representation is contrasted in both structure and time. That is, for each node in the graph, GNN encoder is trained to contrast its real temporal subgraph to its fake temporal subgraph This is done by constructing a positive sample, a structural negative sample and a temporal negative sample. The positive sample is a time-weighted subgraph representation. The margin triplet loss is proposed to maximize the mutual information with the positive sample while maximizing distance with the structural and temporal negative samples. Experiments on downstream link prediction lask under the freeze setting show improvement over baselines. However, their approach comes with several shortcomings. First, initial node features are computed as one-hot encodings which makes the method not suitable for the inductive scenario (i.c. predicting on new nodes). Second, the use of contrastive learning method is known to result in high memory and computation due to negative sampling (Thakoor et al. 2022) This makes the method less desirable for large-scale graphs. Third, they do not include results on other downstream tasks (e.g. dynamic node classification). Lastly, they do not compare to the SoTA CaW method Wang al. 2021b).
Table 12: Hyperparamoters for NAT bascline. We use the default settings outlined the paper Luo & Li b022b for all other hyperparameters.
Param
MOOC
LastFM M
Mj
32
32
M2
16
16
F
4
4
Self Rep. Dim
32
72
20

---

Published in Transactions on Machine Learning Research (12/2023)
Tian et al. (202)) | adapt the TGAT encoder with a self-supervised contrastive framework across time. That is, they propose an extension to the classic contrastive learning paradigm by contrasting two nearby temporal views of the same node using a time-dependent similarity metric. Moreover, a de-basied contrastive loss is utilized to correct the typical negative sampling bias in contrastive learning. Experiments on the fine- tune and mutli-task learning settings show that the simple TGAT encoder can be significantly improved on both future link prediction and dynamic node classification. Nonetheless, their approach comes with several shortcomings. First, it is built on the TGAT encoder which, as seen in Tables [ is weak encoder; particularly, for large datasets. Second, experiments for the FLP task are limited to the Reddit and Wikipedia datasets which are relatively easy. Lastly, the authors do not experiment under the standard settings in graph SSL literature such as the freeze and semi-supervised settings. Table 7 shows the results for downstream future link prediction under the freeze selting. The results show up to 10% gap compared to DyG2Vec, particularly for datasets where the TGAT encoder under-performs (e.g. Enron, UCI).
Cong ct 2023a) propose the dynamic graph transformer (DGT) which is a transformer-basee graph en- coder for discrele-lime dynamic graphs. DGT is composed of two-tower networks that embed the temporal evolution and topological information of the imput graph. Moreover, temporal-umion graph structure is proposed to efficiently summarize the temporal evolution into one graph. DGT is trained to encode the temporal-union graph using two complementary self-supervised pretext tasks. Namely, temporal reconstruc- tion and multi-view contrasting. The first aims to reconstruct a snapshot given the past and present similar to how language models are trained. On the other hand, the latter is trained via non-contrastive learning on two views with randomly masked nodes. All together, DGT outperforms SOTA discrete- time baselines on several datasets for link prediction tasks. While they operate in different domain, an interesting direction for future work would be to adapt their pre-training strategy for contimuous- dynamic graphs.
More encoders for temporal graphs: [Souza et al. 2022 is a very recent work that establishes series of theoretical results on temporal graph encoders. Their analysis exposes several weakness of both memory- based mothods (c.g. TGN) and walk-based mothods (c.g. CaW). Given these insights, they propose PINT, a memory-based method that leverages injective message-passingg and novel relative positional encodings. The relative positional encodings count how many temporal walks of a given length exist between two nodes. Experiments show significant improvement over SoTA baselines on the link prediction task. However, the high theoretical expressive power comes at the cost of requiring relational positional encodings which are expensive to calculate in an online fashion. An interesting direction for future research would be to evaluate the expressive power of DyG2Vec compared to baselines using their theoretical framework (e.g. temporal WL test).
Wang et al. (021a) adapt the vanilla transformer architecture to dynamic graphs by designing a reamstream encoder that extracts temporal and structural information from the temporal neighborhoods associated with any two interaction nodes. Rather than treating link prediction a binary classification task, the authors leverage a contrastive learning strategy that maximizes the mutual information between the representations of future interaction nodes. Experiments show improved performance on future link prediction due to the more robust contrastive training strategy. Nonetheless, the paper does not compare to the SoTA CaW method (Wang et al.
2021b Moreover, experiments are limited to the future link prediction task.
NeurTWs Jin et al. (2022 adapt causal walk sampling procedure of CaW Wang et al. (2021b) to include spatio-temppoal bias and exploitation-exploratio trade-off bias. Moreover, the authors propose utilizing or- dinary differential equations (ODF) to better effectively model the irregularly sampled temporal interactions of node and capture the underlying spatio-temporal dynamics. Experiments show good improvements over the bascline CaW model for some datasets. However, the addition of more sampling biases and ODEs comes at the cost of even higher computational complexity than CaW and more hyperparameters to tune, making the method undesirable for large real-world graphs.
TGL Zhou al. 2202 introduce a general framework for training temporal GNNs on large-scale graphs.
This is done by introducing an efficient CSR data structure to store temporal graphs and a parallel sampler
that supports GPUs The framework supports both memory-based methods (o.g. TGN Rossi et al. (020
and AMP architectures (e.g. TGAT Xu et al. (2020)) ). Experiments on billion-scale graphs show up to 13x
21

---

Published in Transactions on Machine Learning Research (12/2023)
speed improvement while achieving the same performance. An interesting direction for future work is to adapt the DyG2Ver architecture into the TGL framework to further speed it up.
22


Reviews:
[{"review_id": "aRZwTNgCKM", "reviewer": "Reviewer_RAaR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n* Demonstration that self-supervised pretraining works well with temporal graphs is useful contribution with practical implications in real-world applications.\n* The model seems highly scalable and efficient, and empirical results support this.\n* The writing of the paper was fairly clear, with the overall ideas and motivations being conveyed well.\n\n*Weaknesses:*\n* The mathematical details could be clarified in places. Some aspects, such as the SSL objective, are not fully specified (even in the appendix, unless I missed it). More concerningly, the main content of temporal \nattention embedding was hard enough to follow that I am not confident I could reproduce the architecture from the description in the paper. (Specific questions in the requested changes.)\n* While the current experiments highlight the strengths, it is possible that the evaluation tasks themselves are simply too easy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work the authors propose an efficient attention-based encoder architecture for temporal graphs - i.e. graphs where edges have an associated timestamp. Their proposed architecture also incorporates temporal edge encodings (which incorporate aspects such as node degree and number of common neighbors at a point in time) and a window-based subgraph sampling procedure (where, when making a prediction for a target edge $(u, v, t)$, the model will create a subgraph centered around $u$ and $v$ which contains edges in the time interval $(t-W, t)$.\n\nThe authors also propose a self-supervised pretraining objective for their encoder, which, given a sampled subgraph in a particular time window, creates two \"distortions\" (by applying edge dropout and feature masking), maps these distorted versions through the encoder to generate node embeddings, which are then put through a decoder which is trained to output node representations. The loss function is a regularization objective with 3 terms: an invariance term (to bring the two representations closer), a variance term (to avoid representation collapse), and a covariance term (to maximize information content).\n\nThey demonstrate that this self-supervised encoder training can result in improved results on future link prediction and dynamic node classification tasks. In these settings, new decoder architectures (MLPs) are fine-tuned for the particular task at hand. The authors show improved results on 7/7 datasets, while also being more efficient than methods which rely on sampling random walks and scaling more readily to large graph sizes (as opposed to methods which operated on a single static graph).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**R1 (critical):** Could you make the explanation of temporal attention (section 4.1) clearer? Specifically, here were a few things I had questions on:\n1. The neighborhood $\\mathcal N(i)$ has also not been defined here - is it temporally aware? Is it taken from a particular time interval? Or are we simply thinking of the temporal graph $\\mathcal G$ as a multi-graph, and taking a neighborhood in the classic sense?\n2. When you write $\\mathcal N(i) = \\\\{e_p, \\ldots, e_k\\\\}$, this is the first time we have seen the indices $p$ and $k$, and it's unclear to me what they are meant to represent. I think what was intended was to say that we uniformly sample some $N$ 1-hop neighborhood interactions of node $i$, $\\\\{e_{k_1}, \\ldots, e_{k_N}\\\\} \\subseteq \\mathcal N(i) \\subseteq \\mathcal E$. (The indices $p$ and $k$ continue through the paper, so if I am correct than these should perhaps be changed elsewhere also.)\n3. A minor note, but $\\phi_p(t_p)$ also seems to depend on $l$, however it doesn't have the superscript the rest of the layer-dependent variables do.\n4. Is $\\Theta_p(t_p)$ a scalar? If so, it would be helpful to mention this.\n\nIn general, this section is presented with many undefined terms which are later clarified, which (personally) I find rather challenging to read because it requires the reader to maintain a lot of state while reading. Beyond the specific points raised above, I would encourage the authors to take another pass at this section.\n\n**R2 (critical):** The discussion under the self-supervised loss (equation (9)) does not mention the $\\mu$ term at all. Also, while the motivation for the various terms were provided, it would be helpful to present the actual functions used, at least in the appendix.\n\n**R3:** In my experience, creating an evaluation for graph-structured data is quite challenging, and often the standard approach of simply comparing a known positive edge vs. a permuted negative is quite easy to \"game\" - for example, by capturing some high-level statistics - without actually learning anything important about the graph. I realize the primary evaluations in the paper are fairly standard, and I am not requesting the authors completely revamp the evaluation for this task, however as we already see performance seemingly saturate in Table 2 and the strong performance of the random initialization baseline in Table 4, it is worth considering whether the evaluation is simply too simple. I would like to know if the authors believe the models have actually learned something significant about the graph, or whether it is more likely that they have exploited some high-level statistics / bias in the test set? As an example of the sort of bias I mentioned - a pattern I have seen perform unreasonably well on other graph evaluations is to make any node which has a child in the training data be a parent to all nodes, and all other nodes have no children. On such datasets, neural models need only learn to be \"parent classifiers\", and can perform unreasonably well despite having learned almost nothing about the graph structure. To be clear, I'm not saying this is exactly what is happening here, but the eval numbers make me suspect that the eval set is simply too easy to tell us much of anything.\n\n**Minor Typos / Suggestions:**\n1. Section 4.2: I believe the decoder in this section should be labeled $d_\\gamma$, not $d_\\psi$.\n2. Page 9: \"performance due to difficult\" -> \"performance due to the difficult\"\n2. Page 10: \"benefit from more embedding layers\" -> delete?\n3. It is mentioned in section 6 and in the caption of Figure 4 that the plot in the right of Figure 4 is a comparison of attention weights with respect to relative timespan. I assume this means the *mean* of the attention weights for a given timespan, correct?\n4. In the section \"Neighbor Sampling and Temporal Edge Encoding\", it is mentioned that \"sampling a single neighbor for higher hops gives SoTA performance compared to sampling 20 neighbors per hop (see 1st and 5th rows in Table 5)\", and some . When I read this, I interpreted this to mean that \"sampling more higher hops is better\", which (after ingesting the results further) I realize is the opposite of the intended meaning. I would suggest conveying this by putting an emphasis on the number of samples in the first hop, rather than the 1 sample from the \"higher hops\".\n5. Is \"linear\" really the right terminology to use when considering the fact that the decoders are MLPs? My understanding was that \"linear probing\" was just that - linear.", "broader_impact_concerns": "The work is mostly of a methodological nature with no particular concerns from a broader impact perspective.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UKI69pqilA", "reviewer": "Reviewer_ncve", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- **Presentation and contextualisation with prior work**. The paper is generally well-written and easy to follow, while the method is well-presented and relatively easy to understand. I also consider quite positive the fact that the related work is extensively covered and contrasted against the proposed method. It is also quite helpful for the reader in order to navigate the temporal graph learning landscape.\n- **Technical soundness, execution and engineering choices**. Both the proposed architecture and the pretraining and downstream task strategies are reasonable and technically sound. At the same time, the above steps are relatively simple (unlike many previous works on temporal graph learning) and easy to implement, while the engineering choices are innovative and well-motivated.\n- **Evaluation**. The experiments are convincing overall, and each building block is ablated and its existence is sufficiently supported by experimental evidence. Moreover, the training/inference runtime results are very encouraging, showing significant improvement w.r.t. efficiency/scalability. I also found the “attention weight analysis” (section 6) quite insightful.\n\nOverall, the authors propose an original, well-executed, simple and efficient framework for self-supervised and supervised learning on continuous-time dynamic graphs with strong empirical performance.\n\n\n### Weaknesses\n-\t**Clarity in the evaluation section**. Some parts of the experiments remain unclear which casts doubt on the fairness of the comparisons. In particular,\n   - In section 5.2., Tables 2 and 3, the authors compare DyG2Vec against several temporal graph learning baselines on the tasks of “future link prediction” and “dynamic node classification”. However, it was unclear to me if DyG2Vec involves a self-supervised pretraining stage here or if it is trained end-to-end. In the case of the former, I was wondering if the baselines were also pre-trained. I believe that for fairness of comparison, the training strategy should be consistent across all methods, in order to clearly understand the benefits of either the pre-training or the new architecture.\n   - It is quite hard to draw any safe conclusion from the performance reported on the dynamic node classification task. I believe the authors should provide more intuition as to why their method has significantly better performance in the 3rd dataset, while in the other two datasets, it is outperformed by the baselines. Additionally, I had trouble understanding this since I was unsure if the same pre-training & downstream task training strategy is conducted across all competing methods (see above). \n   - In section 5.1., paragraph “Training protocols and hyperparameters”, the authors mention three different evaluation setups. However, I was unable to find where the results of these setups are actually reported. What setup do the authors apply in Tables 2 and 3?\n   - Section 5.2, paragraph “SSL for future link prediction”. Comparing Table 4 to Table 2, I understand that the “Supervised” setup corresponds to the overall method proposed by the authors. Does this refer to end-to-end training (without pretraining) or SSL pretraining + fine-tuning on the downstream task? In case the former holds, then where are the benefits of the SSL pretraining shown? In case the latter holds, then what does “SSL-init” setup stand for? Moreover, how do these setups relate to the training protocols mentioned in a previous paragraph (see my comment above)? Could the authors explain these? \n-\t**Clarity of contributions**. Following up on my previous questions, I would like to ask the authors what they consider as their core contributions. Is it the self-supervised pre-training or the architecture + engineering choices (see summary)? I believe this should be more clearly stated in the paper and the reader should be pointed to the corresponding experimental evidence that provides justifications to the claims.\n-\t**Some experiments are missing**.\n   - Depending on the answers to my above questions, perhaps the paper should be amended with extra experiments. E.g. in case Tables 2 and 3 compare fully-supervised baselines to a pre-trained DyG2Vec, then the experiments should be also performed under a consistent setup. In case they are all fully supervised, then more extensive results on pre-trained DyG2Vec should be reported.\n   - Some baselines could be added: As far as temporal graph learning is concerned, I was wondering if the authors have compared to aggregation mechanisms similar to those used in PINT, Souza et al., NeurIPS’22 or GraphMixer, Cong et al., ICLR’23. As far as self-supervised pretraining is concerned, have the authors experimented with BYOL, Grill et al, NeurIPS’20 akin to BGRL, Thakoor et al., ICLR’22 for static graphs, as they nicely mention in their related work section? A few other works are also mentioned in the related work section (Tian et al., CIKM’21, Jiang et al., KDD’23 – the former is also briefly discussed experimentally in the appendix), so I tend to believe that more emphasis should be given to them in the experimental section of the main paper, e.g. by using the architecture + engineering choices of DyG2Vec and comparing only different SSL pretraining strategies.\n   - I have a suspicion that the temporal edge encoding module might theoretically improve expressivity (mainly the “common neighbours” part). Therefore, I was wondering how the baselines would behave had the temporal edge encodings been used in there as well. Similarly (but less so), for the window-based strategy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The present manuscript proposes a framework (DyG2Vec) for learning on continuous-time dynamic graphs. In particular, the core innovations in this work are (1) a new efficient attention-based neural network architecture, and (2) a modification of a well-known self-supervised paradigm (VICReg Bardes et al., 2022) for dynamic graphs that can be used for general-purpose pretraining. Additionally, (3) the authors make several engineering improvements compared to prior work (sampling temporal neighbours uniformly at random, enhancing neighbour messages with additional features – “temporal edge encoding”, window-based training strategy) that allows them to improve the efficiency as well as the performance of their architecture in downstream tasks. The method is conceptually and experimentally compared to several architectures for dynamic graphs on a variety of (large-scale) datasets and test setups (transductive vs inductive, link prediction, node classification) showing state-of-the-art performance in the majority of the cases. The comparative evaluation is complemented with ablation studies of various implementation details, providing justification for the choices made.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-\t**Motivation**. I think it would be helpful for the paper if the authors explain early on (in their introduction), why self-supervised learning is particularly important on dynamic graphs.\n-\t**Clarity**. The authors should aim to clarify the points I raised in my weaknesses above, i.e. both w.r.t. to their contributions, but most importantly w.r.t. to the experimental section and the various evaluation setups (this would be crucial for my recommendation). Additionally, section 4.3. has some minor clarity issues:\n  - The node-level predictor is unclear. I think the explanation in Appendix A.2. should be moved to the main text. Also in section 3 the predictor for the SSL setup is denoted with $d_{\\psi}$ instead of $d_\\gamma$ (as in the “Prediction” paragraph).\n  - Paragraph “SSL objective”: $s, \\mu, c$ are undefined. I think this part should have been explained more thoroughly for those readers not familiar with the VICReg method.\n-\t**Missing experiments**. Similarly (this is also important for my recommendation), I would encourage the authors to complement their experiments with the ones suggested in the \"weaknesses\" section of my review. I would prioritise clarifying if the comparison is fair and if not, amend the experiments accordingly. Then, consistently comparing with/without the temporal edge encodings, and if possible, adding PINT and GraphMixer to the baselines.\n\n**Minor**\n\n-\tIntroduction: “We propose an effective message-passing encoder that leverages temporal edge encoding to increase its expressive power.” --> This is not theoretically proven, so it might be better to reduce this claim.\n-\tSince the temporal neighbours are sampled, I understand that the node embeddings are stochastic. I was wondering if the authors have measured their variance or the variance of the downstream task performance.\n-\tWhy is $\\bar{t}_i$, Eq. (7), calculated only on the sampled temporal neighbourhood and not on the entire one?\n-\tHow crucial are the transformation distributions (section 4.3, paragraph “Views”)? Could the authors perform an ablation study on that? Also, the $t$ symbol denoting the transformations might be confusing since it is also used to denote timestamps.", "broader_impact_concerns": "I do not foresee any major ethical implication of this work, but I would encourage the authors to include a Broader Impact Statement for completeness, given that learning on dynamic graphs may have wide applicability.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1SPOy62D9J", "reviewer": "Reviewer_N3Q4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- It is indeed an interesting problem to learn the representation of the dynamic graph in a self-supervised manner.\n\n- From a big picture of the proposed method, it seems to me promising to achieve self-supervised pre-training and downstream adaptation. However, given the unclear writing and organization of this manuscript, it is hard to check the detailed implementation.\n\n-  The proposed window-wise construction for dynamic graphs makes sense to control the computational cost to a relatively constant value.\n\n### Weakness\n\n- The illustration and the capture of Fig.1 can be improved to make it more straightforward. Specifically, \n\n    1)  the blue interval on the left side is too light to make it distinguished. There is also a dark blue block within the exact figure, making it hard to read at first glance. \n\n    2)  symbols are not introduced well at the time it is first shown. The first reference to Figure 1 occurs in section 4.1 which is too far to be referred to by the readers. Similar problem for the FIgure. 2 and its reference. Reorganizing the narrative of the manuscript is highly recommended.\n\n- For the problem formulation part, the meaning of symbols is improperly used. For example, \n\n    1) The $E$ represents the number of edges but it is also used in $D^E$ to represent the dimension of the edge's feature. It is highly recommended to reformulate the equations and carefully adopt symbols. \n\n    2) There is no symbol $z$ in Equation 1, do the authors mean $Z$?. \n\n    3) $\\theta$ represents the parameters of the encoder, but $\\Theta$ is also the temporal edge encoder in Figure 1. It is recommended to use dissimilar symbols to represent different modules. Similar problems occur across the whole manuscript.\n\n- To make the manuscript self-contained, it is necessary to provide a brief introduction to the definition of dynamic graph and the downstream tasks at the very beginning, as the term \"dynamic graph\" may refer to very different meanings within different sub-fields.\n\n- I’m a little confused about the setup for the evaluation of the SSL for future link prediction shown in Table 4. If I understand in the right way, the SSL-init encoder also works with a trained downstream decoder to perform the task, is that right? Does the “Supervised” method have the same architecture as DyG2Vec? It is a little strange as the performance of the SSL-init one is lower than the pure supervised one if the SSL-init is fine-tuned for the downstream task, as this is one of the purposes of SSL. \n\n- The descript of Figure 1 in Section 4.1 is not self-consistent. There is no “Temporal Attention Embedding” shown in Figure 1 and the “time-encoding” in Figure 1 is not introduced in this section. This unclear writing makes it hard to get the details about how the proposed method works.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript studies the problem of dynamic graph SSL, where the dynamic graph is defined by the kind of graphs that may change their connections over time. The core of the proposed method includes temporal edge encodings and window-based subgraph sampling to generate the feature embedding, which is trained using the non-contrastive SSL similar to that in the computer vision field without a protector. Unfortunately, the writing's ambiguity makes it hard for me to make a summary of how the encoder is achieved.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My primary concern is the manuscript's writing quality, specifically its coherence and structure. I have detailed some of them in the \"Strengths And Weaknesses\" section, which the authors may reference.", "broader_impact_concerns": "There are no Broader Impact Concerns for this manuscript.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The decision among the reviewers is mixed, with one reviewer in particular complaining about the lack of clarity which makes it hard for the reader to implement the proposed method, thus hindering reproducibility. The other two reviewers are in favour of accepting this submission.

Based on the reviews and discussion, the consensus is that the contributions of the paper are worth publication. A "minor revision" is recommended for this paper due to several remaining concerns. I request that the final version of the manuscript considers the final reviewers' comments, particularly the items listed below:
- Based on the discussion with reviewer ncve, it turns out that most of the experiments concern a fully-supervised setup, while the self-supervised method did not work that well in practice. Therefore, the focus of the paper should be mainly placed on the architecture and the training tricks, and not that much on the self-supervised setup. Τhe authors should update the title and the text of the paper to reflect that.
- Provide some explanations on why DyG2Vec outperforms the baselines. Ideally, explanations would be accompanied with some empirical results.
- Improve the quality of the presentation and clarity throughout the paper.
- As promised in the manuscript, make the code publicly available.

The authors are also encouraged to address the reviewers' concerns about the experimental setup. Specifically, it is not clear whether the experimental comparison is fair since the baselines do not utilize temporal edge encodings. The authors could investigate whether such features lead also the baselines to performance improvements.
Decision: Accept (poster)