DyG2Vec: Representation Learning for Dynamic Graphs With Self-supervision
Authors: Mohammad Ali Alomrani
Mahdi Biparva
Yingxue Zhang
Mark Coates
Venue: Submitted to ICLR 2023 (2023)

Abstract: The challenge in learning from dynamic graphs for predictive tasks lies in extracting fine-grained temporal motifs from an ever-evolving graph. Moreover, task labels are often scarce, costly to obtain, and highly imbalanced for large dynamic graphs. Recent advances in self-supervised learning on graphs demonstrate great potential, but focus on static graphs. State-of-the-art (SoTA) models for dynamic graphs are not only incompatible with the self-supervised learning (SSL) paradigm but also fail to forecast interactions beyond the very near future. To address these limitations, we present DyG2Vec, an SSL-compatible, efficient model for representation learning on dynamic graphs. DyG2Vec uses a window-based mechanism to generate task-agnostic node embeddings that can be used to forecast future interactions. DyG2Vec significantly outperforms SoTA baselines on benchmark datasets for downstream tasks while only requiring a fraction of the training/inference time. We adapt two SSL evaluation mechanisms to make them applicable to dynamic graphs and thus show that SSL pre-training helps learn more robust temporal node representations, especially for scenarios with few labels. 

Under review as a conference paper at ICLR 2023
DYG2VEC: REPRESENTATION LEARNING FOR DY- NAMIC GRAPHS WITH SELF-SUPERVISION
Anonymous authors Paper under double-blind review
ABSTRACT
The challenge in learning from dynamic graphs for predictive tasks lies in ex- tracting ine-grained temporal motifs from an ever-evolving graph. Moreover. task labels are often scarce, costly to obtain, and highly imbalanced for large dy- namic graphs. Recent advances in eeff-superviee learning on graphs demonstrate great potential, but focus static graphs. State-of-the-an (SoTA) models for dy- namic graphs are not only incompatible with the self-supervised learning (SSL) paradigm but also fail to forecast interactions beyond the very future. To ad- dress these limitations, we present DyG2Vec, an SSL-compatible, efficient model for representation learning dynamic graphs. DyG2 uses window-bar based mechanism to generate task-agnostic node embeddings that can be used to fore- cast future interactions. DyG2Vec significantly outperforms SoTA baselines on benchmark datasets for downstream tasks while only requiring fraction of the training/inference time. We adapt two SSL evaluation mechanisms make them applicable to dynamic graphs and thus show that SSL pre-training helps learn more robust temporal node representations, especially for scenarios with few la- bels.
INTRODUCTION
Graph Neural Networks (GNNs) have recently found great success in representation learning for complex networks of interactions, as present in recommendation systems. transaction networks, and social media (Wu et al.] 2020 Zhang et al. 2019 Qiu et al. 2018). However, most approaches ignore the dynamic nature of graphs encountered in many real-world domains. Dynamic graphs model complex, time-evolving interactions between entities (Kazemi et al. 2020 Skarding et al.) 2021 Xue et al., 2022). Multiple works have revealed that real-world dynamic graphs possess fine- grained temporal patterns known as temporal motifs (Toivonen et al. 2007; Paranjape et al. 2017). For example, a simple pattern in social networks specifies that two users who share many friends likely interact in the future. A robust representation learning approach must be able to extract such temporal patterns from an ever-evolving dynamic graph in order to make accurate predictions.
Self-Supervised Representation Learning (SSL.) has shown promise in achieving competitive per- formance for different data modalities on multiple predictive tasks (Liu et al.) (021). Given large corpus of unlabelled data, SSL postulates that unsupervised pre-training is sufficient learn ro- bust representations that are predictive for downstream tasks with minimal fine-tuning. However, it is important specify a pre-training objective function that induces good performance for the downstream tasks. Contrastive SSL methods, despite their early success, rely heavily on negative samples, extensive data augmentation. and large batch sizes (Jing al. 2022 Garrido al. (022). Non-contrastive methods address these shortcomings. incorporating information theoretic principles through architectural innovations or regularization methods. These closely resemble strategies em- ployed in manifold learning and spectral embedding methods (Balestricro & LeCun (022).. The success of such SSL methods on sequential data (Tong et al. [2022] Eldele et al. [022 Patrick al.) 2021) suggests that can leam rich temporal node embeddings from dynamic graphs without direct supervision.
SSL methods attractive for dynamic graphs because it is often costly to generate ground truth labels. Contrastive approaches are very sensitive to the quality of the negative samples, and these challenging identify in dynamic graphs due to the temporal evolution of interactions and the

---

Under review as a conference paper at ICLR 2023
lack of semantic labels at the contextual level. As result, it is desirable to explore non-contrastive techniques, but state-of-the-ane models for dynamic graphs suffer from shortcomings that make them hard to adapt to SSL paradigmss First, they heavily rely on chronological training full history of interactions to construct predictions (Kumar et al., 2019 Xu et al. 2020) Rossi et al.] (020)) Wang et al. b02 Second, the encoding modules either iefffiiiet
ceassage-passsnngg procedures (Xu et al. 2020). memory blocks (Kumar et al.] 2019 Rossi et al.) 2020), or expensive random walk- 2021b) that are designed for edge-level tasks only. As a result, while
based algorithms (Wang et al.
SSL pre-training has been applied successfully for static graphs (Thakoor et al., 2022 Hassani &
Khasahmadi] (2020) You et al. 2022). there has been limited success in adapting SSL pre-training to dynamic graphs.
In this work, we propose DyG2Vec novel encoder-decoder model for continuous- 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 pessaae-passingg across structure and time to output task-agnostic node embeddings. Experimental results for 7 benchmark datasets indicate that DyG2Vec outperforms SoTA baselines on future link prediction and dynamic node classification in terms of performance and speed, particularly in medium- and long-range fore- casting. The novelty of our model lies in its compatibility with SoTA SSL approaches. That is, we propose a joint-embedding architecture for DyG2Vec that can benefit from non-contrastive SSL. We adapt two evaluation protocols (linear and cumi-supervised probing) to the dynamic graph setting and demonstrate that the proposed SSL pre- pre-training is effective in the low-label regime.
RELATED WORK
Self-supervised representation learning: Multiple works explore learning visual representations without labels (see (Liu et al. 202T) for a survey). 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. 2019. With the goal of attaining hard negative samples, such methods typically use large batch sizes Chen et al. (2200a) or memory banks (He et al., 2019|Chen Chen et al.] 2020b). Non-contrastive methods such as YOL (Grill et al. 2020) and VICReg (Bardes et al. 2022) eliminate the need for negative samples through various techniques that avoid representation collapse (Jing et al. 2022) Recently, several SSL methods have been adapted to pre-train GNNs (Xie et al. 2022). Deep Graph Infomax (DGI) (Velickovic et al. 2019) and InfoGCL (Xu et al. 202 ()) rely on mutual information maximization or information bottle-necking between patch-level and graph-level summaries. MV-
GRL (Hassani & Khasahmadi (020)) incorporates multiple views, and BGRL (Thakoor al.) (022) adapts BYOL to graphs to eliminate the need for negative samples, which are often memory- in the graph setting. The experiments demonstrate the high degree of scalability of non-contrastive methods and their effectiveness in leveraging both labeled and unlabeled data.
Representation learning for dynamic graphs: Early works on representation learning for
continuous-timg 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] Parrea 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 et al. 2019) employs two RNN modules to update the source and destination embeddings respectively a arriving edge. DyRep (Trivedi et al.) 2019) adds a temporal attention layer to take into account multi-hop interactions when updating node embeddings. TGAT (Xu et al. 2020) includes an attention- based message passing (AMP) ar- chitecture to aggregate messages from historical neighborhood. TGN (Rossi et al.] (2220) alleviates the expensive neighborhood aggregation of TGAT by using an RNN memory module to encode the history of each node. CaW (Wang 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 prediction. In contrast prior works, our method operates on fixed window of history to generate node embeddings. Additionally, we do not recompute embeddings for every prediction, which allows for efficient computation and memory usage.
We are going to open-source the code upon acceptance.
2

---

Under review as a conference paper at ICLR 2023
3 PROBLEM FORMULATION
A Continuous-Tine Dynamic Graph (CTDG) 9 (V) is sequence of E' |8| interactions, where X' = (XV, xB) is the set of input features containing the node features XV E NRDD and the edge features X E IR ERE .E {ei, . e is the set of interactions. There are N [V] nodes, and DV and D F are the dimensions of the node and edge feature vectors, respectively. An edge e, (we, Us. t4; m,) is interaction between any two nodes u4, E V, with t, R being a continuous timestamp, and m, E X an edge feature vector. For simplicity, we assume that the edges are undirected and ordered by time (i.e., 4 S 1++1). A temporal sub-graph Gi, is defined as a set of all the edges in the interval [t,, f,] such that E = { 4 S 14 S 1,). Any two nodes can interact multiple times throughout the time horizon; therefore, 9 is a multi-graph.
Our goal is to learn a model f that maps the input graph to a representation space. The model is a pre-trainable encoder-decoder architecture, / = (ge.dy): dz). The encoder go maps dynamic graph to node embeddings H E RNNDD" the decoder d, performs a task-specific prediction given the em- beddings. The model is parameterized by the encoder/decoder parameters (0,7). More concretely,
H = (9),
-= (H:E),
(1)
where Z E NxD" is the prediction of task- labels (e.g.. edge prediction or source node classification labels) of all edges in E. 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 et al. 2020; Xu et al.) 2020) Wang et al.) 20215), 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-speeific 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 as a two-stage framework. In the first stage, we use non-contrastive SSL method to learn the model pssl = (go, de)) over various sampled dynamic sub-graphs with self-supervision. da is an SSL decoder that is only used in the SSL pre- pree-traiing 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 tasks, e.g., future edge prediction or dynamic node classification (Xu et al. 2020: Wang et al. 2021b).
We consider two example downstream tasks: future link prediction (FLP), and dynamic node clas- sification (DNC). In each case, there is a prediction horizon of the next K interactions. The test window for FLP starting at time t; is E = {u,, Uj. ty,t,, m;)li E i + K]}. This is augmented by set of K negative edges. Each negative edge (uj, v/y my] differs from its corresponding positive edge only in the destination node, v/j # Vy, which is selected random from all nodes. The FLP task is then binary classification for the test set of 2K edges. In the DNC task, a dy- namic label is associated with each node that participates in an interaction. We are provided with f(u,, ti E [i, + K]}. i.e., the source node and interaction time. The goal is to predict the source node labels for the next K interactions. The performance metrics are detailed in Appendix AA.4
METHODOLOGY
We now introduce novel dynamic graph learning framework DyG2Vec, which can achieve downstream task-agnostic representation. We first present the SSL pre-training approach with a non-contrastive loss function for dynamic graphs. We then introduce the novel window-based down- stream training approach. Finally, we outline the encoder architecture.
Given the full dynamic graph Go,E. E. set of intervals I is generated by dividing the entire time-span {to, f into M = LES] 1 intervals with stride S and interval length W (See Appendix A.4 for details). Let B / be the mini-batch of intervals. Given B, the sub-graph sampler m (g, B; W) constructs the mini-batch of input graphs: G (9i, I [i,.]) E B). The corresponding mini- of target graphs is denoted by ς = {Gis+k x [(,5) E BJ. In principle, Gi. E 9 is an input (history) graph used to predict the target labels of the corresponding target (future) graph 9 E G. The parameter W controls the size of the history while K controls how far the model predicting into
3

---

Under review as a conference paper at ICLR 2023
Dynamic Graph
Temporal Subgraph Sampler
Mini Batch of sub-graphs
Views
Embedding
Prediction
g
v(Z')
(2.6,X)
H
Z'
c(Z')
mLG. B; W)
s(Z' zz
90
H
PΦ
z"
c(z")
g"
v(Z"
Figure 1: The joint embedding architecture for the non-contrastive SSL Framework. Each slice of the input dynamic graph contains edges arriving at the same continuous timestamp. is a batch of intervals of size W. 9 is batch of the corresponding input graphs of each interval.
the future. S controls the stride between intervals. In practice, we set S K so that each edge is only predicted once each epoch. Since & is only provided for training the downstream task, SSL pre-training only operates on G, as seen in Figure
4.1 STAGE 1: PRE-TRAINING ON DYNAMIC GRAPHS WITH SELF-SUPERVISION
We formulate joint-embedding architecture (Bromley et al. 1993) for DyG2 in which two views a mini-batch of sub-graphs are generated through random transformations. The trans- formations randomly sampled from distribution defined by distortion pipeline. The encoder maps the views to node embeddings which are processed by the predictor to generate node represen- tations. We minimize SSL. objective (Eq. 2 described below) optimize the model parameters end-to-end in the pre-training stage. See Figure for an overall design of the SSL framework.
Views: The temporal distortion module generates two views of the input graphs g' = =((g) and G" = E" (9) where the transformations i' and E" are sampled from distribution T over pre- defined set candidate graph transformations. this work, we use edge dropout and edge feature masking (Thakoor et al. 2022) in the transformation pipeline. See Appendix A.4 for more details.
The encoding model go an attention-based message-passing (AMP) neural network that produces node embeddings H and H" for the views ğ' and g" of the input graphs Gi,j. We elaborate the details of the encoder in Sec.
Embedding:
Prediction: The decoding head d,, for our self-supervised learning design consists of node-level predictor ps that outputs the final representations Z and z", where Z = Po (H).
SSL Objective: In order learn useful representations, we minimize the VICReg regularization- based SSL loss function from (Bardes et al. 2022):
J SSL = 1(2 z') As Z z²) ml((2)) + vl o(Z x(c(z)) +c("""
(2)
In this loss function, the weights X. μ., and y control the emphasis placed on each of three regu- larization terms. The invariance term encourages representations of the two views to be similar. The variance term included to prevent the well-known collapse problem (Jing al. 2022). The covariance term promotes maximization of the information content of the representations. More details and complete expressions for 5, e and c are provided in Appendix A.3
Unlike previous regularization-basse computer vision, we do not use projector network because the embedding dimensions are relatively small in the graph domain. The full pre-training procedure is illustrated in Figure [ Following the pre- pre-traine training stage, we replace the SSL decoder with a task-specific downstream decoder dp that is trained top of the frozen pre-trained encoder.
SSL approaches (Chen et al. 2020a Bardes et al. 2022 in
4

---

Under review as a conference paper at ICLR 2023
K
Km
Ex
$= (V,6,X)
CCI W
mGG B; W)
Gut G
SSL Pre-training Task
GL G
GJJ+K G
Downstream Task
Figure 2: DyG2Vec Window Framework. Every slice of the dynamic graph 9 contains edges that arrived at the same continuous timestamp. The blue interval represents the history graph 9i-w, that is encoded to make a prediction on the next K edges (yellow interval). is a batch of intervals of size W edges. G is batch of input graphs. G is batch of target graphs that is only used in the downstream stage.
4.2 STAGE DYG2VEC DOWNSTREAM TRAINING
In the downstream training stage, the DyG2 model f (go, d+s) consists of the SSL pre-trained encoder ge and a task-specific decoder dy which trained using a similar window-based training strategy. The model is trained to make predictions depending prediction node classification) given the input and target graphs ς and & as follows: H =9)()) the node embeddings returned by the encoder, and Z dæ H: E) is the prediction output of the decoder. Here & is set of (partial) edges for which predictions are requested from the decoder. The model parameters optimized by training with a loss function LD Z. O), where CD is defined depending on the downstream task and O contains task-specific labels (See Section 3}.
the downstream tasks (c.g. link
The hindow-based training strategy has several major advantages. First, the window acts regu- larizer by providing a natural inductive bias towards recent edges, which are often more predictive of the future. It also avoids costly time-based neighborhood sampling techniques (Wang et al., (021b). Second, relying on a fixed window-size for message-passing passing allows for constant memory and com- putational complexity, which is well-suited to the practical online streaming data scenario. Third, unlike previous works (Xu et al., 2020: Wang et al. 2021b) which generate separate node embed- dings for each target edge, generic encoder allows
use the same set of embeddings for any prediction. This dramatically reduces the training/inference overhead. Another advantage of this design that it allows the model forecast unseen edges relatively far into the future, in contrast to existing works (Xu et al. 2020 Rossi al. 2020) that focus predicting the next occurring edge.
4.3 DYG2VEC ENCODER ARCHITECTURE
Our encoder combines a self-attention mechanism for message-passine with the Time2 module (Kzzei al. 2019) that provides relative time encoding. We also introduce novel temporal edge encoding that efficiently captures the temporal structural relationship between nodes.
Given dynamic graph G, the encoder go computes the embed- ding h/- node through a series of multi-head attention (MHA) layers (Vaswani et al. 2017) that aggregate messages from its L-hop neighborhood (Xu et al. 2020 Velickovic et al. 2018).
Temporal Attention Embedding:
5

---

Under review as a conference paper at ICLR 2023
Given node embedding he h/ layer 1-1, we uniformly sample N 1-hop neighborhood interac- tions of node i, (it) (ep-...... e ε. The embedding hy at layer / is calculated by:
h W W MHA' (q', K V"),
(3)
q' = h K' = v'= (tp(t)).... Px (fx)].
(4)
(5)
Here, W, is a learnable mapping matrix, (.) is a multi-head dot-produc attention layer, and (t,)) represents the edge feature vector of edge cp (up: Up: Eyp m.) (i)
at time typ
kp(tpp | fp(t)) || mpl-
(6)
fp =(t,, - tpp Op(tp),
(7)
& = max {tz le (upp)
(8)
where denotes concatenation and Φ(.) is a learnable Veme2 module that helps the model be aware of the relative timespan between sampled interaction and the most recent interaction of node Up in the input graph. (,).) 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 our encoder is 'flat': every iteration, the same set of node embeddings used to propagate messages to neighbors. Our encoder performs message passing once to generate set of node embeddings H used for all target predictions on G.
Temporal Edge Encoding: Dynamic graphs often follow evolutionary patterns that reflect how nodes interact over time (Kovanen et al., [21T). 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 behaviour of dynamic graphs. The temporal edge encoding function is then:
@p(tp) Walzp(tp)]lcppe
where we incorporate (i) Temporal Degree Centrality zp(1p) E IR22: the concatenated current degrees of nodes Up and up at time fp: and (ii) Common Neighbors cp(tp) E R: the number of common 1-hop neighbors between nodes up and Up at time tp-
By using the degree centrality 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 future interaction (Yo et al. 2016).
edge feature, the model is able to learn any bias towards more
EXPERIMENTAL EVALUATION
5.1 EXPERIMENTAL SETUP
Baselines: We compare DeG2Vec to five state-of-the-art baseline models: DyRep (Trivedi et al. 2019), JODIE (Kumar al. 2019), TGAT (Xu et al.] 2020), TGN (Rossi al. 2020), and CaW (Wang et al. (0221b). DyRep. JODIE, and TGN sequentially update node embeddings us- ing 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.
We evaluate all models on 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 timestamp. For each positive edge, we sample negative edge that the model is trained to predict as negative. The DNC task involves predicting the label of the source node of future interaction. Both tasks are trained using binary cross entropy loss. Contrary to prior works which only evaluate under the K = 1 setting, we evaluate all models under K E {1, 200, 2000}. This is a more challenging evaluation scheme it tests the forecasting capabilities of the models across multiple time horizons. See Appendix A.4 for details.
Downstream Tasks:
For the FLP task, report both classification and recommendation metrics: Average Precision (AP), Mean Reciprocal- Rank (MRR), and Rec@ 10. For the DNC task, we report the area under the curve (AUC) metric due the prevailing issue of class imbalance in dynamic graphs.

---

Under review as a conference paper at ICLR 2023
Speed ys Performance: LastFM
Speed Performance: SocialEvol.
Speed vs Performance: MOOC
A.0
Pyy22er
CaW
0.90
PyG2Ver
'GN
0y/pp
CaW
0.88
0.35
.TGN
5.70
075
7GN DyRep
0.80
0.33
Jodie
DDyRep
Caw
0.0
A.00
0.60
8.5
JGAT
JGAT
TGAT
0.50
400 Figure 3: Transductive FLP Performance (Test AP for K 200) vs Inference runtime (8) on datasets. Inference time represents the time it takes to predict the whole test set.
1000
15:0
2000
1000
2000
4000
Inference Time (Seconds)
Inference Time (Secords)
Inference Time (Seconds)
Table 1: Transductive Future link Prediction Performance in AP (Mean + Std). Avg. Rank reports the mean rank of VyG2Vec across all datasets. Bold font and underline font represent first- and second-best performance respectively.
K Model
Wikipedia
Reddi
MOOC
LasFMM
Earon
UC1
SocialEvol
Avg Kank
JODIE
11.0112
0.979
0.001
0.797
0.001 0:000
0.02)
0,822 0.010
0.847
0.014
4.71
DyRep
0.955
0.004
1e-4
0.840
0.004
0.683 0.033
0.796 + 0.042
+00076
0.004
TGAT
0.998
0.001
0.9%5
3
0
0.633+
0.637 0.0002
0
0.003
0/831 Bood
TGN
0.886 1 0.001
0.085
0.001
0.911 0.010
0.713 0.000
0.866 0.000
0.813 1 0.090
0.968
0.001
2.57
CaW
0.976 + 0.007
0.988
2e-4
0.340
0.014
0.903 = 1o44
0.970 #: 0.001
0.509 + 1.008
0.947 + Ic-d
1.57
DyG2Vec
0.977 4 0.001
0.987 1 0.001
0.892
0.005
0.843 4 0.007
0.911 1 0.008
0.953 1 0.002
0,939 & 0,001
2.14
JODIE
0.336 + 0.003
0.975 + 1o-4
0.796 = 0.02
0:089 4: 0.018
0.756 a: 0.02
0.700 + 1.008
0 0.01
4.42
DyRop
0.954 + 0.003
0.981 + 0.001
0.859
0.006
0.684 0.034
0.788 + 0.042
0.522 + 0.081
0.856 + 0.020
4.71
300
TGAT
0.358 + 0.002
0,985 + 1o-4
0.203
0.007
0.519 0.002
D.G16 + 0.004
0.727 + 0.010
0.516 + 0.001
5.14
TGN
0.060 1 0.001
0.085 0.001
0.854
0.0L0
0,709 1.0000
0,858 1: 0.008
0,762 1 0.110
0,907 led1
0.965
0.001
0.001
0.001
0:001
DyG2Vec
1 0.001
0.986 0.001
0.878
0.004
0.841 0.005
0.905
0.918 0.002
0.938 0.001
JODIE
0,380 0.001
0.700 0.020
0.614
0.729
0 4 (1.00
0.691 0,023
DyRep
0.002
0.776 0.005
0,590
0,729 0.942
2000
0.951
0.001
0,985 1o44
0.006 0.007
0.513
0.618
+
0,500 0:001
TGN
0.933 + 0.0001
0.984
0.001
0.700 0.010
0:089 2: 0.000
0.842 # 0.010
0.746 + (1022)
0.839 = 0.007
3:28
CaW
0.971
3e-4
0.984
2n-4
0.732 0.001
0.811 + 1e
0.929 + 0.001
0.706 + 0.003
0.847 + 0.001
DyC2Vec
0.356 + 0.001
0.384 + 0.002
0.798
0.002
0.829 0.004
0.579 0.306
0.866 + 0.002
0.908 = 0.001
1.1
Datasets: We use 7 real-world datasets: Wikipedia, Reddit, MOOC, and LastFM (Kumar et al. 2019); SocialEvolution, Enron, and UCI (Wang et al., 2021b). These datasets span wide range in terms of number of nodes and interactions, time range, and repetition ratio. We perform the same 70%-15%-15% chronological split for all datasets in (Wang et al., 2021b). The datasets are split differently under two settings: Transductive and Inductive. More details can be found in Appendix
A.1
The code and datasets will be publicly available upon publication.
Training Protocols and Hyper-parameters: We train and evaluate the models under three dif- ferent settings commonly used in vision SSL works (Grill et al.) 2020 Bardes et al. (022). In the supervised setting. DyG2Vee is initialized with random parameters and trained directly on the down- stream tasks and compared all supervised baselines. In the self-supervised setting, the encoder is pre-trained using our SSL framework, and the performance is measured under two evaluation proto- cols: Linear and Semi-supervised Probing. In the linear evaluation setting, the decoder trained on top of the frozen encoder and compared to the supervised counterpart. In the semi-supervised eval- uation setting, the decoder is trained on top of the frozen pre-trained encoder on a random portion of the dataset (i.e., fraction of the intervals I). The DyG2Vec encoder performs L = 3 layers of message passing. We sample N = 20 temporal neighbors at each hop as in Xu et al. (2020). Other hyperparameters are discussed in Appendix A.5)
For the DNC task, following prior work Rossi et al. (2020), the decoder trained on top of the frozen encoder that is pre-trained the future link prediction task unless otherwise explicitly stated.
5.2 EXPERIMENTAL RESULTS
Future Link Prediction: We report the tranductive test AP scores for future link prediction in Table
Unlike previous work which focuses on K = 1, we evaluate all models under K {1, 200, 2000} to test their medium- and longer-term forecasting capabilities. Unsurprisingly. all methods degrade as K increases. Our model significantly outperforms all sequential and message -aaggnng baselines on 5/7 of the datasets for K > 1 and is on par with SoTA (CaW) for K = 1. The gap is particularly large on the UCI and SocialEvol. datasets for K 2000, where DyG2 Vec outperforms the second-
7

---

Under review as a conference paper at ICLR 2023
Table 2: Transductive Dynamic Node Classifica- tion Performance in AUC (Mean + Std) for K e
0.70
{1, (1,200, 2000
Test AUC
0.85
Model
Wikipedia
Reddit
MOOC
TGAT
0.800 0.001
0.664
0.673 + 0.006
0.60
JODIE
0.843 : 0.003
0.566 1. 0.016
0.672 1: 0.002
Setting
Dyrep
0.873 + 0.002
0.633 0.0008
0.661 0.012
Random-init
TGN
0.828 = 0.004
0.655
0.671 = 0.007
LP-init SSL-init
DyG2Vee
0.833 0.008
0.744 + 0.01
0.716 0 0.00
TGAT
0.819 1 0.014
0.654 1 0.011
0.664 0.004
JODIE
0.813
0.003
0.672 0,002
5%6 10%
20%
40%
80%
100%
Dyrep
0,872 1 0.002
0.633 1. 0.009
0.664 1. 0.011
Percentage of Training Data
0.834 0.003
0.655 0.011
0.641 0.000
DyG2Vec
0.927 1 0.004
0.745 1 0.006
0.683 0.002
Figure 5: Semi-Supervised Learning on Dy- namic Node Classification. For each setting, DyG2Vee was trained on varying random por- tion of the training data.
TGAT
0.828 = 0,017
0.650 1: 0.022
0.667 = 0.010
JODIE
0.867 = 0.002
0.55 + 0.019
0,632 = 0,008
Dyrep
0,873 = 0.002
0.597 1: 0.012
0.692 = 0 0.002
TGN
0.840 1 0.003
0.646 0.009
0,638 1 0.030
DyG2Vec
0.915 - 0.003
0.743 1: 0.007
0.609 = 0.002
best method (CaW) by over 10% and 6% respectively. Interestingly, while SocialEvol. is the largest dataset with ~ 2M edges, our model is able to achieve this performance while only using the last 1000 edges (See Table to predict any future edge. This further cements the findings by Xu et al. (2020) that capturing recent interactions may be more important for certain tasks. Our window-basse framework offers a good trade-off between capturing recent interactions and recurrent patterns which both have a major influence on future interactions. Appendix A.2 contains results in the Inductive setting which show that DyG2Vec is competitive with CaW for 4/7 of the datasets while using a small fraction of the computation (See Figure B)
Dynamic Node classification: We evaluate DyG2Vec on datasets for node classification where the labels indicate whether user will be banned from editing/posting after 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 157K interactions result in ban). We measure performance using the AUC metric to deal with the class imbalance. Table 2 shows that DyG2Vec outperforms all baselines on 7/9 of the tasks for different K. Interestingly, the performance of all methods does not always drop as K increases. This could be explained by the fact that depending on slightly out-of-date history can help make less noisy and more consistent predictions; thus, increasing performance.
Training/Inferenn Inference Speed: Relying on fixed window of history to produce task-agnostic node embeddings gives DyG2Vec Vec a significant advantage speed and memory. F the per- formance and runtime per epoch of all methods on the three large datasets: LastFM, SocialEvolution and MOOC, with K 200. DyG2Vee Vec is many orders of magnitude faster than CaW due to the lat- ter's expensive random walk sampling procedure. RNN-based methods such as TGN have 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- based methods are slower for settings where a node's 's memory is updated frequently. Furthermore, while TGAT has similar AMP encoder, Dee improves the efficiency and performance signif- icantly. This reveals the significance of the window-based mechanism and the encoder architecture. Overall, Vec presents the best trade-off between speed and performance.
SSL for Future Link Prediction: Table 3 reports the transductive AP results for DyG2Vec under 3 differ- ent settings. Namely, we compare a random frozen encoder (Random- init) and an SSL pre-trained encoder (SSL-init) with the supervised base- line. The results reveal that our SSL pre-training learns informative node embeddings that are almost on par with the fully supervised baseline. This supports the capability of the non-contrastive methods to learn generic representations across unlabelled large-scale dynamic
Table 3: Linear probing AP results (Mean + Std) on Trans- ductive Future Link Prediction for K E {1, 200, 2000}
Setting
UCT
Earon
MOOC
LasPM
Randon--ini
0.927
0.001
0.888 = 0.001
0.785 = 0.007
0.181 0.001
Supervised
0.953 + 0.002
0.911 + 0.006
0.892 + 0.005
0.843
4443-+00 0.007
SSL-inni
0.945
0.001
0.902
0.002
0.861
0.003
0.796
Random-inir
0.304 + 0.001
0.830 + 0.005
0.787 + 0.002
0.184 + 0.00
Supervised
0.918
0.002
0.894 0.006
0.878
0.004
0.844 0.005
SSL-init
0.915 + 0.001
0.857 + 0.003
0.859 + 0.002
0.792 + 0.01
Random-init
0.851
0.001
0.832 = 0.007
0.742 = 0.003
0.776 0.001
Supervised
0.866
0.002
0.879
+ 0.006
0.795 + 0.002
0.829 0.004
SSL-iinit
0.863 0.002
0.876 0.007
0.789 0.003
0.785 0.01
8

---

Under review as a conference paper at ICLR 2023
graphs, which is in line with the findings for other data modalities (Bardes et al. 2022) Random-init baseline is surprisingly good, as observed by recent works Thakoor et al. 2022). but is outperformed by the SSL pre-trained encoder.
The
Semi-supervised Learning on Dynamic Node Classification: The DNC task challenging due to its highly imbalanced labels. Previous works alleviate this issue by pre-training the encoder future link prediction. In Figure BJ we show that SSL is a more effective pre-training strategy for dynamic graphs than FLP, particularly in the low-label data regime where each model is trained on a portion of the target intervals /. This further cements the findings that reconstruction-bast tasks such link prediction overemphasize proximity which can be limiting for some downstream tasks Velickovic et al. 2019; You et al. 2020)..
5.3
ABLATION STUDIES
0:38
1.00
Temporal
we Temporal Edge Features
0.86
0.55
0.95
0.94
Wikinedla
0.50
Willpedis MODC
0.90
NOOC
UO
UCI
0.53
512
2k
4K
18K
32K
64K
Wikipedia
MOOC
UCI
Window Size
Number of Layers
Dotaset
Figure 6: Ablation studies on 3 datasets for the FLP transductive task.
We perform detailed study on different instances of our framework with 3 datasets. All ablation results are reported in Figure
We observe that each dataset has its own optimal window size W due to the inher- ently different recurring temporal patterns. As observed by by(Xu et al. (2020). recent and/or recurrent interactions are often the most predictive of future interactions. Therefore, datasets with long range dependencies favor larger window sizes to capture recurrent patterns while some datasets benefit from an increased bias towards recent interactions. Our window-based framework coupled with uni- form neighbor sampling strikes a balance between the two. Morcover, increasing the window size to 64K for UCI, which is effectively full history as it has 60K edges in total, results in 4% drop in performance. This 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.
Window Size:
Number of Layers: Most datasets benefit from more embedding layers, and some (e.g. MOOC) more than others. This suggests that these datasets contain higher order temporal correlations among nodes that must be learned using long-range message passing. Overall, the results show that one can choose sacrifice some performance further improve the speed of DyG2Vec by decreasing the window size and the number of layers.
Temporal Edge Features:
The results show a significant decrease in performance for MOOC when temporal edge features are removed (i.e. 1-5% drop). This indicates that such temporal edge features provide useful multi hop information about the evolution of the dynamic graph (Yao et 2016).
6 CONCLUSION
In this paper, we introduce DyG2Vec, a novel window-based encoder-decoder model for dynamic graphs. We present an efficient attention-based message-passing model that utilizes hierarchical multi-head attention modules to encode node embeddings across time. Furthermore, we present a joint-embedding architecture for dynamic graphs in which two views of temporal sub-graphs are encoded to minimize a non-contrastive loss function. We evaluate the SSL pre-training of
DyG2Vec under both linear and semi-supervised protocols and demonstrate the effectiveness such pre-training on benchmark datasets. Our window-based architecture allows for efficient message- passing and robust forecasting abilities. We aim to further explore ways to improve the capacity of the dynamic graph models to leam long-range dependencies. Additionally, other SSL paradigms such as masked enttoeess are worthwhile future explorations for dynamic graphs given their success sequential tasks.

---

We describe the details of the benchmarks we used in Appendix A. We also include the full implementation details in Appendix A.4 including our detailed model design for decoder, negative sampler, distortion pipeline for view generations and etc. Besides, we provide justification for elaborate the baselines Under review as a conference paper at ICLR 2023
7 ETHICS STATEMENT
Dynamic graph neural network techniques have been commonly used for prediction tasks in social networks and recommender systems. Our techniques, as an efficient and effective variant of dy- namic graph representation technique, can be used in those scenarios to further improve the model performance. However, having such an ability is a double-edged sword. On one hand, it can be beneficial to greatly improve user experience. On the other hand, there may be some concerns about the potential use of the model to exploit data relating to user behaviour and thus invade privacy. Overall, our paper does not include content which has immediate ethical concerns.
REPRODUCIBILITY STATEMENT
choice of hyperparameters in Appendix A.5 Additionally, consider in our paper as well as their hyper-parameter details in Appendix [A.6] We helieve with
the code open-sourced upon acceptance and the detailed description of our model and the baselines provided in the paper, our work is fully reproducible.
REFERENCES
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning cover global and local spectral embedding methods. arXiv preprint arXiv:2205./1500 2022.
Adrien Bardes, Jean Ponce, and Yann LeCun. VICReg: Varrineeiimarrinee-ccvarnnn regulariza- tion for self-supervised learning. In Proc. Int. Conf. Leurning Representations, 2022.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature veri- fication using "siamese" time delay neural network. In Proc. Int. Conf. on Neural Information Processing Systems, 1993.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proc. Int. Conf. on Machine Learning, 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXhv:2003.04297, 2020b.
Weilin Cong, Yanhong Wu, Yuandong Tian, Mengting Gu, Yinglong Xia, Mehrdad Mahdavi, and Chun cheng Jason Chen. Dynamic graph representation learning via graph transformer networks. 2022.
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 E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman, and Yann Lecun. On the duality be- tween contrastive and non-contrastive self-supervised learning. arXiv preprint arXiv:2206.0224 02574, 2022.
Bean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, and et al. Bootstrap your own latent a new approach to self-supervised learning. In Proc. Advances in Newral Information Processing Systems, 2020.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In Proc. Int. Conf. on Machine Learning, 2020.
10

---

Under review as a conference paper at ICLR 2023
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. arXiv preprint arXiv: 2019.
Linpu Jiang, Ke-Jia Chen, and Jingqiang Chen. Self-supervised dynamic graph representation learn- ing via temporal subgraph contrast. arXiv preprint arXiv:21 2021.
Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. Sub-graph contrast for scalable self-supervised graph representation learning. IEEE International Confer- ence on Data Mining (ICDM), 2020.
Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive sule--sup learning. In Proc. Int. Conf on Learning Representations, 2022.
Seyed Mehran Kazemi, Rishab Goel, Sepehr Eghbali, Janahan Ramanan, Jaspreet Sahota, Sanjay Thakur, Stella Wu, Cathal Smyth, Pascal Poupart, and Marcus Brubaker. TimeZvec: Learning a vector representation of time. arXiv preprint
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. arXiv preprint arXiv: 6980, 2014.
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 tem- poral interaction networks. In 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 or contrastive. IEEE Transactions on Knowledge and Data En- gineering, 2021.
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 al. Evolvegen: Evolving graph convolutional networks for dynamic graphs. Proc. of the AAAI Con- ference on Artificial Intelligence, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, and et al. Pytorch: An imperative style, hirf-peeformance deep learning library. In Proc. Advances in Neural Informa- tion Processing 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. Computer Vision, 2021.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Tang. Deepinf: Social influence prediction with deep learning. In Proc. Int. Conf. Knowledge Discovery & Data Mining, 2018
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. ICML Workshop on Graph Representation Learning, 2020.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural represen- tation learning on dynamic graphs via self-attention networks. In Proc. Int. Conf. on Web Search and Data Mining, 2020.
Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial. Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey. IEEE Access, 2021.
11

---

Under review as a conference paper at ICLR 2023
A. H. Souza, D. Mesquita. S. Kaski, and V. Garg. Provably expressive temporal graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 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. In Proc. Int. Conf. on Learning Representations, 2022.
Sheng Tian, Ruofan Wu, Leilei Shi, Liang Zhu, and Tao Xiong. Self-supervised representation learn- ing on dynamic graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 1814-1823, 2021.
Ritta Toivonen, Jussi Kumpula, Jari Saramäki, Jukka-Pekka Onnela, János Kertész, and Kimmo Kaski. The role of edge weights in social networks: modelling structure and dynamies. In Noise and Stochastics in Complex Systems and Finance, 2007.
Zhan Tong, Yibing Song, Jue Wang, and Limin Wang. Videomae: Masked autoencoders are data- efficient learners for self-supervised video pre- pre-training. arXiv preprint arXiv:2203. 12602,, 2022.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning rep- resentations over dynamic graphs. In Proc. Int. Conf. on Learning Representations, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Infor- mation Processing Systems, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proc. Int. Conf. Learning Representations, 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. Proc. Int. Conf. on Learning Representationss 2019.
Lu Wang, Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Le Song.Jingren Zhou, and Hongxia Yang. Tel: Transformer-based dynamic graph modelling via contrastive learning, 2021a.
Yanbang Wang. Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In Proc. Int. Conf. on Learning Representations, 2021b.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 2022.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive represen- tation learning on temporal graphs. Proc. Int. Conf. on Representation Learning, 2020.
Dongkuan Xu, Wei Cheng, Dongsheng Luo. Haifeng Chen, and Xiang Zhang, InfoGCL: Information-aware graph contrastive learning. In Proc. Advances in Neural Information Pro- cessing Systems, 2021.
Guotong Xue, Ming Zhong, Jianxin Li, Jia Chen, Chengshuai Zhai, and Ruochen Kong. Dynamic network embedding survey. Neurocomputing, 2022.
Lin Yao, Luning Wang, Lv Pan, and Kai Yao. Link prediction based common-neighbors for dynamic social network. Procedia Computer Science, 2016.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Proc. Advances in Neural Information Processing Systems, 2020.
12

---

Under review as a conference paper at ICLR 2023
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. Bringing your own view: Graph contrastive learning without prefabricated data augmentations. Proc. Int. Conf. on Web Search and Data Mining, 2022.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys, 2019.
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 DATASETS
Table 4: Dynamic Graph Datasets. % Repetitive Edges: than once in the dynamic graph. The labels column specifies whether the dataset contains dynamic node labels or not.
percentage of edges which appear more
Nodes
# Edges
Unique Edges
Edge Features Labels
Bipartite
Repetitive Edges
Reddit
11,000
672,447
78,516
54%
Wikipedia
9,227
157,474
18,257
48%
MOOC
7,047
411,749
178,443
53%
LastFM
2,000
1,293,103
154,993
68%
UCI
1899
59,835
20,296
62%
Emron
184
125,235
3,125
92%
SocialEvolution
74
2,099,519
4,486
97%
We describe several real-world dynamic graph datasets which we train on:
Reddit (Kumar et al. 2019]: A dataset tracking active users posting in subreddits. Data is repre- sented as bipartite graph with nodes being the users or subreddit communities. An edge represents embedding vector which is used
posting subreddit. Each user's post is mapped as an edge feature. A Dynamic label indicates whether user u is banned from posting after an interaction (post) time t.
Wikipedia (Kumar et al., 2019): A dataset tracking user edits on Wikipedia pages. The data is also represented a bipartite graph involving interactions (edits) between users and Wikipedia pages. Each user edit is mapped to an embedding vector which is treated as an edge feature. A dynamic label indicates whether a user u is banned from posting after an interaction (edit) time L.
MOOC (Kumar et al. 2019): This dataset tracks actions performed by students on the MOOC online course platform. Nodes represent students or items (i.e., videos, questions, etc.). A dynamic label indicates whether student drops out after performing action at time t.
LastFM (Kumar et al. 2019): This dataset tracks songs that users listen to throughout one month. Nodes represent users or songs. Dynamic labels are not present.
UCT (Wang et al. 2021b): dataset that records online posts made by university students on forum.
Enron (Wang et al. 2021b): A dataset that records email communication between employees company over several years.
SocialEvolve (Wang et al. 2021b): dataset tracking the evolving physical proximity between students in dormitory over year.
Dataset Splitting: As mentioned earlier, we follow the setup of (Wang et al. 202 to perform chronological split for each dataset. The datasets are split differently under two settings: Transductive and Inductive. Under the transductive setting, dataset is split normally by time, i.e., the model is trained the first 70% of links and tested on the rest. In the inductive setting, we strive to test the model's 's prediction performance on edges with unseen nodes. Therefore, following (Wang al. 2021b), randomly assign 10% of the nodes the validation and test sets and remove any interactions involving them in the training set. Additionally, to ensure an inductive setting, we remove any interactions not involving these nodes from the
A.2 ADDITIONAL RESULTS
A.2.1 INDUCTIVE SETTING AND RANKING METRICS
Table reports the future link prediction results in the inductive setting. DyG2Vec is generally competitive with CaW while using 50-100x less inference and training runtime (See 3 and 7 re- spectively). Tables 6 and 7 report the future link prediction ranking performance for K I the transductive and inductive tasks, respectively. While ranking metrics should provide more fine- grained analysis, the results consistent with the AP results (See Tables and 5).
14

---

Under review as a conference paper at ICLR 2023
Table 5: Inductive Future link Prediction Performance in AP (Mean + Std) for K (1, 200, 2000). Avg. Rank reports the mean rank of DyG2Vec across all datasets. Bold font and underline font represent first- and second-bes performance respectively.
Madill
Wikipella
MODX
LasFMM
Firon
Sectal Fvolvve
Aug Rani
JOITE
0.331 0000
0.805 0.221
0.507 = 1.123
0.805 1.03
0.737 = 0.051
0.:05
00011
0.791 #0D31
4.35
DyRep
0.800 1
0.921 1: 0.003
0.725 1. 0.009
0.869
0.015
0.666 1 0.055
0.457
0.002
0.904 -eed
4.71
IGAT
0.54 0000
0.979 0.001
0.805 a: 0.006
IL = 0.002
0.683
= 0.004
08200
0.632 = 0L00
4.14
TON
0.974 +.000
0.954+0000
0.855 + 0.014
0.789 1 0.050
0.746
+ 0.015
0.791
0.057
0.504 + 0.023
3.42
20-4 0,989
0.890
0.001
0.581
+0.002
0.950 1e-4
1.28
DyCDVec
0.951
0.799
0.910 0.010
0.827
0.022
0.045 0.005
0.008
2.57
TOITE
0.591 +002
0.960 + 0102
0.701 + 0.022
0.300
0.05
0.745 + 0.020
0,702 0.010
0.224
00025
4.14
DyRep
0.554 0.002
0.919 0.000
0.725 L 0.019
0.864
0.015
0.638 1 0.071
0.451
0.021
0,88 0.024
4.57
TGAT
0.002
0.977
0.001
0.002
0.0093 0,009
0.008
0.009
0.5178
0.001
TGN
0.948 0.000
0.745 0.316
0.709 0.083
0,701
0,019
0.083 0.083
0.029
0.001 0.978
0.975 0.001
0.812
0.009
0.787
0.003
0.905
004
0.819 0.003
0,871 0.001
DyG
0.925 1 0.004
0.063 0.001
0.774 1 0.009
0 9.0
0.020
0.773 0.067
0.007 0,880
0.538 1 0.038
2.14
JONT
0.71400000
0.712
0.588 0.013
0.715 0.034
0.423 + 0.052
0.727 0.045
01687 0.110
DyRep
0.757 0.006
0.842 0.006
1.500 0,010
0.082 0.032
0.4022 + 0.012
0.483 0.011
0.687 0.0-9
TOAT
0.912 0.002
0.976
000
0.899 +: 0.004
0.528
0.578 + 0.007
0.660 0.008
0,511 1: 0.003
3.14
2000
TGN
0.557 1. 0.00
0.855 4: 0.005
BJ655 4: 0.018
0.7 0.068
0.378 = 1,024
0.631 0.019
0.481 2: 0.002
4.43
CaW
0.976
+ 0.001
0.975 + 0.001
0.742 + 0.011
0.759 + $-44
0.865 + D 000
0.737
0.807
0.833
+ 000001
1.28
DyC2Vec
0,850 1 0.000
0.942 1 0.003
0.71 L 0.015
0.890 1 0.02
0,108 1 0.033
0.553 0.007
0.780 1 0.0.95
2.57
Table 6: Tranductive Setting. Ranking metries, Recall @ 10 and Mean Reciprocal Rank (MRR), for future link prediction K = I. Avg. Rank reports the mean rank of DyG2Vec across all datasets
Matric
Model
Wikipedia
Rolde
MODC
LasEM
Earon
UCI
SocialEvol
Aug Bank
IODE
F..00
0LIR 0.00G
FD.UR
0.131 +0009)
01265
0.25 + 0026
5:07
DyRap
0.067 + 0.019
0.815 + 0.005
0.502 C.015
0.139++0000 +0.049
0.285 0.079
0.010+00.01
0.780+ 0.010
4.57
Recalle 10
TGAT
TGN
0.717 0.010
0.865 1.0000
0.861
0.820 1..00
0.0004
0.511 0.000
0.207 0.013
0.025 0.000
0.208 1.0.0
0.106 0.0022
0.40-110.000
0.154 0.004
0.399-10.100
0.947 0.003
0.147 0.001
2:14
5,00
Caw
0.888
100001
0.000
C.002
0.411 0.0002
0.720 a
0.72
0.702 20-4
DyG2Ves
0,797
0.002
0.763
0,065 0.000
0.606 0.008
0.0011000000
0.922 0.003
JODIE
0.371 0.000
0.000
0100
0.057 1.0010
0. 0:000
0.001 0.000
0:301 1 0.019
5.28
DyRep
0.122 0.015
0.558 2 0.000
0.224 2 0.007
0.065 t 0.022
0.118 +: 0.05
0.010 0.000
0.355 0.010
4.42
MRR
TGAT
TGN
0.084 0.000
0.464 1 0.116
0,619
0,504 0.030
2 0.004
0.364 1 0.030
0.121 1 0.006
0,100 0.020
0 3e
0.053 2 0.001
0.206 1 0.010
0.242 1 0.070
0.111 1 0.0012
0.666 1: 0.017
3,001 2 000005
4.85
2.42
CLW
0.717
4: +.0.001
0.6115 0.002
0.314 + 0.010
0.191 + 0.001
0.516 0.003
0.001 + 0.0004
0.323 + 26-4
1.85
DyG2Voz
0.096 62
0.636 #: 0.011
0272 2 0.05
0.164 2 0.002
0.264 0.009
0.360 0.010
0.4014 0.002
2.34
A.2.2 EFFECT OF K DURING TRAINING
One of the advantages of the VyG2 framework is that, unlike prior work, it is trained to forecast with K= > 1. In fact, the parameter K can be set during training based on how much long-range range forecasting is favored. In our experiments, we found that training with K = 200 achieves good balance between long and short-range forecasting capabilities. Moreover, the limited history of W edges forces the model to be more inductive as is predicting based on limited long-range histor- ical information. To better understand this, we trained both DyG2 and CaW under K = {1, 200} and evaluate on K = {1, 200, 2000]. Table & shows that training DyG2Vec with short-range predic- tion (K 1) improves performance to be par with CaW on K and outperform it for K > 1. However, as expected, this comes at a cost of ~ 2% drop for long-range forecasting (K > 1) when compared to Vec trained with K 200. On the other hand, CaW's performance drops sig- nificantly when trained with K = 200 (i.e. over 10% drop for UCI and MOOC). We believe this is due to the sampling bias which may be incorrectly favoring recent edges over edges that occurred further in the past but can help for long-range forecasting. Unfortunately, we were unable to address this by re-tuning a. An interesting direction for future research would be study training settings under which all models can have improved forecasting abilities.
Table 7: Inductive Setting. Ranking metries, Recall 10 and Mean Reciprocal Rank (MRR), for future link prediction K = 1. Avg. Rank reports the mean rank of DyG2Vec across all datasets
Merric
Medel
Wikiieddis
Reddi
MOOC
LaIFMM
Faron
UCT
Sociallbol
Aug Rank kJ00
JODE
0:215 200S
0.01
0.201 2 0000
OURN 1 DINE
DAMS 2 0082
DyRap
0.187 + 0.000
0.531 + 0.016
0.327 + C.019
0.479 0.057
0.144 + 0.075
04085 + 0.001
0.855 + 0.006
4.14
10 10
TGAT
0.634
6.002
0.792 + 0.005
0.3% G.001
TUUSS = Tm-
0.105 0.006
0.155 0.007
0.147 0.002
4.57
TGN
0.776.0.012
0.81 0.000
0585
0.451 0.034
0201100.016
0.2611 0.055
0.860
2,71
CAW
0.804
1-00002
0.005
0.888
0.0016
0427 1 0.003
0.687 0.0010
0.709 0.000
0.773 2 00000
2:14
DyG2Vec
0.742
0.000
0.543
0.535100.020
0.001
0.616 0.020
0.774 0.057
JODIE
0.122
20.06
Mill 2..133
0121 20:01
0UN1
2 0.025
0.3001 25 00007
4.85
DyRap
0.322
0.005
0:301 0.016
0.130 0.007
0.179 0.099
0.01
: 0.0255
0.066 + 0.000
0.427 :: 2.0012
4.28
MRR
TGAT
TGN
0.6iN5 1 0.000
0.464
+ 0.006
0.420 1 0.000
0.528 + 009
0.285 1 0.0199
0.186 + 0.004
0,127 0.015
0.016 + 2n-4
0.115 1. 0.011
0.052 + 0.005
0.185 1. 0.125
0.135 + 0.008
0.425 L. 100075
0.071 + 3m-4
6.42
2.71
CaW
0.712
0 0.004
0,521
1. 0.002
0,202 0.03
0.158
1 0.001
0.205
1 0.000
0.584
1. 0.0004
0.511 L. 0000
2.28
DyG2Voz
0.564
0.523 030000
OL1US C.030
0.204 2 0.000
0.305 0.006
0.280 0.019
0.362 00005
2.42
15

---

Under review as a conference paper at ICLR 2023
Table 8: Future link prediction test AP Results with different K during training. Both CaW and
DyG2Vec were run with optimal hyperparameters for each dataset.
MOOC
UCT
Enron
Training K
Model
200
2000
200
2000
200
2000
DyG2Vec
93.0
84.3
74.5
97.2
89.6
84.03
96.2
91.9
K =
CaW
94.0
82.2
73.2
93.9
85.6
76.6
97.0
92.9
92.9
DyG2Vec
89.2
87.8
79.8
95.3
91.8
86.6
91.1
89.4
87.9
= 200
CaW
81.9
61.2
60.8
84.2
63.6
58.0
91.8
78.6
78.0
Speed vs Performance: LastFM
Speed vs Performance: SocialEvol.
Speed vs Performance: MOOC
DyG2Vec
_CoW
0.00
PyG2Vec
JGM
Jejiipp
.CeWi
DyG2Ver
AP
TGN 'yRRep
Uy Jodie
.CaW
0.30
0.70
0.60
0.75
TGAT
JGAT
JGAT
0.70
9.0
2000 4000 6000 8000 15000 12000 Training (Seconds)
5000
15000
20000
Training (Seconds)
Training
(Seconds)
Figure 7: Transductive FLP performance (Test AP for K 200) vs Training Time (s) on 3 datasets. Training time represents the time it takes to train on the whole training set.
A.2.3 RUNTIME AND COMPUTATIONAL COMPLEXITY
Figure shows the training time per method for 3 datasets. DeG2 is orders-of -fgggnntude faster than CaW and is on par with memory based methods in terms of speed.
The main runtime overhead lies in how each of the baselines processes the input graph to predict a batch of K target edges. 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 a different L-hop subgraph for each target edge. DyG2Vec samples a single L-hop subgraph within constant window size W for all target edges.
Thus, assuming we use sparse operations in Pytorch Geometric (Fey Lenssen 2019) for message- passing, the encoding computational complexities are: DyG2 O(LW); CaW O(LMN, and TGN and variants = LN.). Here, .₂ represents the maximum number of sampled nodes that the main
in L-hop subgraph and K is the number of target edges to predict. We difference is the factor M and the fact that this sampling is done for each of the K target edges. The factor N₂ comes from the complexity of message passing at each hop (assuming sparse operations). Note that VeG2Vec is limited to O(W) nodes so it does not have this factor.
A.3 PRELIMINARY: VICREG
We outline the details of the VICReg (Bardes al. 2022) method used in our SSL pre-training stage. Given z' R and image) generated through random distortions, the objective non-contrastive SSL is two-fold. First, the output representation of 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-know problem of collapse (Jing et al.) [0222 in the mapping space. More concretely, let Z [2|,.... 21] and z" = ,,,", the batches composed of n representations of dimension d.
RRd, the representations of random views of object (e.g..
The variance regularization term v the mean over the representation dimension of the hinge function on the standard deviation of the representations along the batch dimension:
Variance term:
v( Z b Ei max(O, 7 ()). Here Z,j is the column j of matrix Z. S is the regu-
16

---

Under review as a conference paper at ICLR 2023
larized standard deviation defined by S(z,c) Var(z)) + Y is a constant value set to 1 in our experiments, and e is a small scalar that helps to prevent numerical instability. This term avoids dimensional collapse by maximizing the volume of the distribution of the mapped views in all di- mensions. In other words, it prevents the well-known trivial solution where the representations of the two views of sample collapse to the same representation (Jing et al. (022).
Covariance term: The covariance regularization terms C decorrelates different dimensions of the representations and prevents them from encoding similar information. The covariance matrix of Z is C(Z) 1 1 - (z; - z)" where 1 E. 24. The covariance regularization term e is then defined as the sum of the squared off-diagonal coefficients of the covariance matrix as follows c(Z) à (C())( where ( is the element at row and column j of the matrix CZZ). Both the variance and covariance terms helps to maximize the information encoded by the model in the representation space.
Invariance criterion: The invariance criterion between Z and Z" is defined the mean squared Euclidean distance between the representation vectors in the two views s s(Z', 2z z") =
+ >. || - z; l|g- The invariance term encourages the parametric mapping to ensure that the views of an object remain close in the latent space.
Finally, the SSL loss function CSSL over a batch of representations is a weighted average of the invariance, variance, and covariance terms:
LSSL = 1(Z =1l'= "Z') As z") ulv(Z)) + =lo cc c(z")
(10)
In our experiments, we set = 11 = 25 and v = following Bardes et al. (2022).
A.4 IMPLEMENTATION DETAILS
We train 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 activation function is used for all models. The code and datasets publicly available
Window-based framework: As mentioned in Section 4 the full dynamic graph Go, is divided into set of intervals / that is generated by dividing the entire time-span into M [E/S] intervals with stride S and interval length W:
-= [ max (0.x W), min(jS, 1j e (1. ...,,....AA.......... 3
I
(11)
Here, W defines the number of edges in an interval and S defines the stride. Note that we include all intervals up but not including [E W, E') so that the target interval contains least one edge.
Negative Sampling: For future link prediction, we sample an equal number of negative interactions and positive (target) interactions. Negative interactions are sampled by sampling random negative destination node from the set of all possible nodes. For the Recall @ 10 and MRR metrics, we sample 500 random negative destinations for each positive target edge.
Decoder Architecture:
Denote by maa the timestamp of the latest interaction, within the provided history, incident to node w. For future link prediction, to predict target interaction (u, v. f), our decoder maps the sum of the two node embeddings of u and e and time embedding of t - aua to an edge probability. Following Xu et al. (2020), the FLP decoder is a 2-layer MLP.
For dynamic node classification, to predict the label of node u for interaction (u, v, f), the decoder maps the source node embedding and time embedding of maar to class probabilities. Following Xu et al. (2020), the DNC decoder is 3-layer MLP with dropout layer with = 0.1.
The time embedding is calculated using trainable Time2Vec module (Kazemi 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.
hhans://githhb.ccm/mmmmaanngg
17

---

Under review as a conference paper at ICLR 2023
For SSL pre-training, the predictor pa is simple 2-layer MLP that maps node embeddings H to node representations Z.
Distortion Pipeline:
Following static graph SSL methods such Thakoor et al. (2022)
edge dropout and edge feature dropout as distortions. Both distortions are applied with dropout probability Pa 0.3 which we have found work best in a validation experiment exploring the values Pa E {0.1, 0.15, 0.2, 0.3). The edge feature dropout is applied on the temporal edge encod- ings introduced in Section 4.3 i.e., zp(bp) and cy)))). More advanced temporal distortions could be explored such as time distortions or edge shuffling, but we leave those for future work.
A.5 PYPER-PARAMETERS
Hyper-parametee We use a constant learning rate of 0.0001 for all datasets and tasks, DeG2Vec is trained for 100 epochs for both downstream and SSL pre-training. The model from the last epoch of pre- pre-training is used for downstream training. For downstream evaluation, we pick the model with the best validation AP performance. Overall, we found that DyG2Vec converges within ~ 50 epochs.
For downstream training, the window size W is tuned on the validation set from the range {IK, 4K, SK, 12K, 32K, 65K}. The best window sizes per dataset can be found in Table 9 The larget window size K is fixed to 200 during training. The stride is always fixed to be equal to K, so that each edge is only predicted once. One could augment the dataset by changing S but we leave this for future work. The batch size is always set to I; hence, only predict one target interval of size K at a time. However, the model could be sped up by increasing batch size at the cost of higher memory.
During SSL pre-training, we use constant window size of 32K with stride 200. The DyG2Vec encoder hyperparameterr can be found in Table 10
Table 9: Optimal Window size W for downstream training.
Dataset
Window Size W
Wikipedia
65K
Reddit
65K
MOOC
12K
LastFM
32K
UCI
4K
Enron
8K
EvolutEnonution
IK
Following previous work (Rossi et al. experiments are performed with deca parameter 0.00001 to alleviate over-fitting
2020
Xu al.
2020 all dynamic node classification training
A.6 BASELINES
Baselines:
Following prior work (Rossi al. 2020 Xu et al. 2020), all baselines are trained with
constant learning rate of 0.0001 using the Adam optimizer (Kigmma & Ba (014) on batch-size 200 for a total of 50 epochs. The early stopping strategy is used to stop training if validation AP does not improve for epochs. For JODIE (Kumar et al. 2019). DyRep (rrvedi et al. (Rossi et al. 2020). we use the general framework implemented by Rossi al.
2019). and TGN
2020). The node
memory dimension is set to 172. Other encoder hyperparameters are specified in Table 10
the default hyperparameters of 2 layer neighbor sampling with 20 neighbors sampled at each hop. Other hyperparameters are specified in Table 10 For the CaWW]methon we tune the time decay parameter
For TGAT
{0.01, 0.1, 0.3, 0.5. 1, 2,2,4 4, 10) x 10-6 and length of the walks m E {2. 3, 4, 5} on the validation set. The optimal hyperparameters for each dataset are specified in Table 11 The number of heads for the walking- based attention is fixed to 8.
18

---

Under review as a conference paper at ICLR 2023
Table 10: Hyperparameters for DyG2Vec, RNN-based methods (JODIE, DyRep, and TGN), and TGAT.
Param
Value
Node Embedding Dim
100
Time Embedding Dim # Attention Heads
100
2
Sampled Neighbors
20
Dropout
0.1
Table 11: Hyperparameters for CaW.
Dataset
Time Decay a
Walk Length m
Wikipedia
4e-6
4
Reddit
le-8
3
MOOC
le-4
3
LastFM
le-6
3
UCI
le-5
2
Enron
le-6
5
SocialEvolution
3e-5
3
A.7 COMPUTING INFRASTRUCTURE
All experiments were done on Ubuntu 20.4 server with 72 Intel(R) Xeon(R) Gold 6140 CPU @ 2.30GHz cores and RAM of size 755 Gb. We use NVIDIA Tesla V100-PCIE-3200 GPU,
A.8 ADDITIONAL RELATED WORK
Self-supervised learning for dynamic graphs: Most adaptations of SSL for dynamic graphs have focused on improving downstream task performance via auxiliary losses rather than learning general pre-trained models. Jiang al., (222)) adapt a sub-graph contrastive learning method (Jiao al. 2020) where a node representation is contrasted in both structure and time. That is, for each node in the graph, a GNN encoder trained contrast its real temporal subgraph to its fake temporal sub- graph This is done by constructing a positive sample, a structural negative sample and temporal negative sample. The positive sample is time-weighn weightedd subgraph representation. The margin triplet loss is proposed to maximize the mutual information with the positive sample while maximizing dis- tance with the structural and temporal negative samples. Experiments on downstream link prediction task 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 nodes). Second, the
the method not suitable for the inductive scenario (i.e. predicting 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 et al. 2021b).
Cong et al.] 2022) propose the dynamic graph transformer (DGT) which is a transformer-based graph encoder for discrete-time dynamic graphs. DGT is composed of two-tower networks that embed the temporal evolution and topological information of the input graph. Moreover, temporal- union graph structure proposed efficiently summarize the temporal evolution into one graph. DGT is trained to encode the temporal-unio graph using two complementary seff-supervised pretext tasks. Namely, temporal reconstruction 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 tasks. While they operate in a different domain, an interesting direction for future work would to adapt their pre-training strategy for continuous-time dynamic graphs.
several datasets for link prediction
19

---

Under review as a conference paper at ICLR 2023
Downstream Freeze test AP Results (after pre-training) for K=1. DDGCL pre-training and downstream training were run with default parameters described in the work. DyG2Vec was run with parameters described in A.5
Table 12:
Model
MOOC
Enron
UCI
LastFM
DeG2Vec
86.1
90.1
94.5
79.8
DDGCL
84.3
83.0
85.3
78.8
Tian al. (2021) adapt the TGAT encoder with 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 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 classifica- tion. Nonetheless, their approach comes with several shorteomings. First, is built on the TGAT encoder which, as seen in Tables and 5] 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 T2 shows the results for downstream future link prediction under the freeze setting. The results show up 10% gap compared DyG2Vec, partic- ularly for datasets where the TGAT encoder under-performs (e.g. Enron, UCI).
More encoders for temporal graphs: [Souza al. (2022) is concurrent work that establishes series of theoretical results on temporal graph encoders. Their analysis exposes several weakness of both memory-basee beasory-based methods (e.g. TGN) and walk-based methods (e.g. CaW). Given these insights, they propose PINT, a memory-based method that leverages injective message-passing 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. An interesting direction for future research would be to evaluate the expressive power of DyG2 compared to baselines using their theoretical framework (e.g. temporal WL. test).
Wang et al. (2021a) adapt the vanilla transformer architecture to dynamic graphs by designing two- stream encoder that extracts temporal and structural information from the temporal neighborhoods associated with any two interaction nodes. Rather than treating link prediction a binary classifica- tion 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 pa- per does compare to the SoTA CaW method (Wang et al., 2021b). Moreover, experiments limited to the future link prediction task.
20


Reviews:
[{"review_id": "XhvcKSQSdNy", "reviewer": "Reviewer_gYTF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method to improve representation learning for dynamic graphs using self-supervised learning (SSL) approach. Named DyG2Vec, the method is equipped with a SSL pre-training component that uses a non-contrastive loss objective, a window-based architecture as well as fine-tuning component that can tune the task-agnostic representations for the concerned dynamic graph learning tasks. As for the architecture, an encoder decoder pipeline is adopted that uses attention based graph neural network, as well as additional temporal edge encoding which captures degree centrality as well as common neighbors between two nodes. Experimental evaluation on multiple datasets show promise of using DyG2Vec.", "summary_of_the_review": "The paper overall does great in presenting a self-supervised pre-training approach that can be used to generate task-agnostic node representations for dynamic graph learning, and is intuitively and empirically powerful than existing works. There are a few missing details (as asked in the weaknesses and questions section above) which can further be provided or answered.", "strength_and_weaknesses": "Strengths:\n1. The paper contributes an approach that can be used to perform SSL pre-training on dynamic graphs using non-contrastive approach. This evidently improves the trained architecture for temporal graph tasks in a majority of the empirical evaluations shown.  \n2. The background of the research topic is clearly written which follows the need to proposed DyG2Vec.  \n3. The window-based training is interesting and from the experiments its observed that it is able to predict longer future events.  \n4. Figure 3 study shows DyG2Vec is more efficient yet high performing compared to baselines.  \n5. Ablation studies and experimental details are sufficiently mentioned that provides robustness of the studies as well as details for reproducibility later (after code release).  \n\nWeaknesses and questions:  \n1. There are couple of related works that could be discussed - SSL for dynamic graphs using contrastive loss [1], and provably expressive temporal networks [2], and where possible, their performance comparison with DyG2Vec can be mentioned.  \n2. Page 6: How is temporal degree centrality is computed for an edge? It mentions \"the current degrees of nodes u_p and v_p at time t_p.\" the degrees of u_p and v_p could be different; how are the two values combined to make the edge degree centrality?  \n3. After reading the experimental discussion, the curiosity on what is the major contribution of DyG2Vec for the improve in performance -- SSL pre-training? window-based framework? temporal edge encoding? For instance, if its SSL pre-training can it be easily used in prior models as an augmentation or extension and whether it would provide an equivalent boost in performance? And for temporal edge encoding -- is it providing features to the architecture which otherwise cannot be learned by the temporal graph attention?  \n4. Page 8: \"Table 2 shows that DyG2Vec outperform all baselines significantly\" - Although the performance of DyG2Vec is impressive, the quoted statement in Page 8 (as well as similar claims in other experimental sections) is misleading and incorrect as per the table of results. For example, in Table 2, DyG2Vec does not beat baselines in 2 out of 9 instances. Such precise numbers may be mentioned to correct the claims as quoted.  \n5. For the performance versus Inference time graphs in Figure 3, how do the models compare in terms of parameters or sizes? Are all the models plotted in Figure 3 are of comparable model size (eg. number of layers or number of parameters)?  \n\n[1] Jiang, L., Chen, K.J. and Chen, J., 2021. Self-Supervised Dynamic Graph Representation Learning via Temporal Subgraph Contrast.   \n[2] Souza, A.H., Mesquita, D., Kaski, S. and Garg, V., 2022. Provably expressive temporal graph networks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XDMRnVy5Y0", "reviewer": "Reviewer_yV1s", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a SSL-compatible, efficient dynamic graph model named DyG2Vec, which uses a window-based mechanism to generate task-agnostic node embeddings. Experiments on benchmark datasets and two downstream tasks show that the method has stronger prediction ability and less inference time than SOTA baselines. The paper also introduces SSL pretraining and finetuning protocals for dynamic graphs.\n", "summary_of_the_review": "The paper proposes a new SSL learning method for dynamic graphs by using a window-based mechanism and extensive experiments show that the method has stronger prediction ability and less inference time than SOTA baselines. However, the reviewer concerns that 1) the motivation and presentation is not clear 2) the technical novelty is limited 3) importance related works are missing 4) deeper analyses of the proposed method is missing. ", "strength_and_weaknesses": "[+] A new SSL learning method for dynamic graphs by using a window-based mechanism.\n\n[+] Experiments on benchmark datasets and two downstream tasks show that the method has stronger prediction ability and less inference time than SOTA baselines.\n\n[+] The paper also introduces SSL pretraining and finetuning protocals for dynamic graphs.\n\n[-] Limited novelty and unclear motivation. a) the proposed window-based mechanism seems straight-forward adaption from ssl learning for static graphs, and the view generators for ssl, i.e. edge dropping and edge feature masking in this paper, are commonly adopted in graph ssl literature. It is expected to design specific ssl methods by utilizing the dynamics which can not be considered in static graphs. b) It is not well explained why the window-based mechanism acts as a good ssl method for dynamic graphs. c) The motivation of SSL for dynamic graphs is also not well-explained. The authors state that \"task labels are often scarce, costly to obtain, and highly imbalanced for large dynamic graphs\", but it seems not supported in dynamic graph literature. The authors are expected to give support for the statement in detail. Moreover, in link prediction, which is common downstream task in dynamic graph literature, edges serve as training task labels (historic edges) and also testing task labels (future edges), and it does not support the statement \"task labels are often scarce\".\n\n[-] Presentation can be largely improved. \n\n[-] Lack of deeper analyses. For example, it is not well-explained why the proposed method has better forecasting capability in larger horizon.\n\n[-] Missing important related works. There are a few related works about self-supervised dynamic graph learning methods, e.g [1-4].\n\n[1] Tian, Sheng, et al. \"Self-supervised Representation Learning on Dynamic Graphs.\" Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021.\n[2] Cong, Weilin, et al. \"Dynamic Graph Representation Learning via Graph Transformer Networks.\" arXiv preprint arXiv:2111.10447 (2021).\n[3] Wang, Lu, et al. \"Tcl: Transformer-based dynamic graph modelling via contrastive learning.\" arXiv preprint arXiv:2105.07944 (2021).\n[4] Jiang, Linpu, Ke-Jia Chen, and Jingqiang Chen. \"Self-Supervised Dynamic Graph Representation Learning via Temporal Subgraph Contrast.\" arXiv preprint arXiv:2112.08733 (2021).\n\n(Minor)\n1. typo in Figure 6.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Uv1aNtRcWuK", "reviewer": "Reviewer_46gJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a self-supervised learning framework for dynamic graphs. Temporal edges are split into windows which are then used as sub-graph samples for self-supervised learning. The proposed model is efficient and obtains empirical improvements on several datasets.", "summary_of_the_review": "An interesting approach for dynamic graphs but further investigations are needed.", "strength_and_weaknesses": "The idea proposed in this paper is interesting to me, and experiments show some empirical improvements and efficiency. However, I still have the following concerns and questions for the current version of this paper:\n\n1. Section 4 is not easy to follow. In particular, the notation definitions are not clear enough. For example, at the beginning of Section 4, Eq (2) has M+1 intervals rather than M; What's the difference between stride S and window length W? Can the intervals defined in Eq (2) overlap?\n\n2. Window size is essential to capture the temporal pattern and varies on different datasets (according to Figure 6 left). It is difficult to predefine, which hinders the practical use of the proposed approach.\n\n3. The experimental results are mixed. The baseline CAW does better in many settings, especially on the inductive link prediction task (Table 5).\n\n4. I'm curious about the efficiency comparison against CAW because CAW proposes an efficient link sampling algorithm and claims high efficiency. In addition to Figure 3, it would be better to give some formal time complexity analysis or profiling. This will make readers understand where the gap is.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ECMWZ-O6YW-", "reviewer": "Reviewer_fBK8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel SSL pretraining architecture based on encoder-decoder model called DyG2Vec for dynamic graphs. It is a fixed window-based method to learn node embeddings for future predictions. Paper uses two views of temporal subgraphs in a non-contrastive SSL framework. The SSL objective consists of three terms, invariance criterion, variance term and covariance term. Two evaluation mechanisms are adapted for experiments. Authors performed two downstream tasks such as future link prediction and dynamic node classification on 7 benchmark datasets. ", "summary_of_the_review": "The work is presented well and has advantages being an SSL framework, inexpensive, etc. However, I have a few concerns that it is not outperforming in the majority of the settings. Rather CaW looks more like a generalized method but it is quite expensive. What is the rationale behind using the K>1 setting? There is similar work in a different domain (meshes)", "strength_and_weaknesses": "1. The problem is challenging and impactful. \n2. Being an SSL framework, it has more advantages than supervised models. It can be used for a wide variety of tasks. \n3. Experimental results in Tables are not convincing although some of the results like Fig3 and Fig6 are interesting. \n4. Paper is easy to follow, and well-written. However, I see a major weakness in experimental results. \n5. Although there is a benefit of using DyG2Vec due to its inexpensiveness. However, it looks like CaW does a better job overall. \n6. This method might be useful for large graphs if this can make training faster at the cost of some % of accuracy but cannot be considered for all the scenarios. \n7. The authors mentioned in 5.1 that existing methods evaluate for K=1. However, this paper includes more results with K=200, 2000. What is the rationale for doing this? I see that results for K=1 are not good for DyG2Vec but better for K=200, 2000. Any intuition behind this is not explained. Why do other works have considered only K=1? \n8. Fig6 shows that MOOC and UCI datasets are sensitive against the value of W. \n9. I have seen a similar work [1] but for meshes in which the method takes a mesh and predicts a mesh for a future timestamp. Can you please comment on the similarity with this work? \n[1] LEARNING MESH-BASED SIMULATION WITH GRAPH NETWORKS ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject