{'fraction_non_alphanumeric': 0.028969417679095097, 'fraction_numerical': 0.009530791788856305, 'mean_word_length': 4.887409051670983, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards Better Evaluation for Dynamic Link Prediction

Despite the prevalence of recent success in learning from static graphs, learning from time-evolving graphs remains an open challenge. In this work, we design new, more stringent evaluation procedures for link prediction specific to dynamic graphs, which reflect real-world considerations, to better compare the strengths and weaknesses of methods. First, we create two visualization techniques to understand the reoccurring patterns of edges over time and show that many edges reoccur at later time steps. Based on this observation, we propose a pure memorization baseline called EdgeBank. EdgeBank achieves surprisingly strong performance across multiple settings because easy negative edges are often used in the current evaluation setting. To evaluate against more difficult negative edges, we introduce two more challenging negative sampling strategies that improve robustness and better match real-world applications. Lastly, we introduce six new dynamic graph datasets from a diverse set of domains missing from current benchmarks, providing new challenges and opportunities for future research. Our code repository is accessible at https://github.com/fpour/DGB.git.


Introduction
Many evolving real-world relations can be modelled by a dynamic graph where nodes correspond to entities and edges represent relations between nodes. Nodes, edges, weights or attributes in a dynamic graph can be added, deleted or adjusted over time. Therefore, understanding and analyzing the temporal patterns of a dynamic graph is an important problem. For instance, in popular online social networks, many users join the platform on a daily basis while connections between users are constantly added or removed [10]. To facilitate more efficient learning on dynamic graphs, many efforts have been devoted to the development of dynamic graph representation learning methods [41,37,40,28,42,43,29,3].
Link prediction is a fundamental learning task on dynamic graphs which focuses on predicting future connections between nodes. Recent methods such as [18,38,42,28,40] show promising performance on this task, with the state-of-the-art (SOTA) performance [28,40] being close to perfect on most existing benchmark datasets. However, considering that link prediction in static graphs, an arguably less complex task, still faces major challenges [11,12], it is important to meticulously examine the near-perfect performance of dynamic link prediction methods. We hypothesize that current evaluation procedures and datasets fail to properly differentiate between the proposed approaches. Therefore, we identify several limitations in the current evaluation procedure and propose solutions towards more robust and effective evaluation protocols.
Limited Domain Diversity. Existing benchmark datasets are mostly social or interaction networks thus limited in domain diversity. It is well-known that networks across different domains exhibit a diverse set of properties. For example, biological networks such as protein interaction networks differ significantly from social networks in community structure and centrality measures [9]. Therefore, it is necessary to test dynamic link prediction methods in various domains outside of social or interaction networks. To this end, we incorporate six new datasets for dynamic link prediction ranging from politics, economics, and transportation networks. In addition, we introduce novel visualization techniques for dynamic graphs. We show that in most networks, a significant portion of edges reoccur over time but the reocurrence patterns vary widely across different networks and domains.  Table 1.
Easy Negative Edges. In a dynamic network, the edges that have been never observed during previous timestamps can be considered as easy negative edges, since it is less likely that these edges occur during the test phase given the reoccurring pattern of dynamic graphs. We introduce two novel Negative Sampling (NS) strategies, specifically designed to incorporate more difficult edges in dynamic graphs, which select negative edges based on the reocurrence of observed edges. As shown in Fig. 1, SOTA methods have a significant decrease in performance when a different set of negative edges is sampled during test time. Moreover, the relative ranking of methods varies significantly across NS settings. Thus, it is important to evaluate methods on different sets of negative edges.
Memorization Works Well. Finally, we introduce a simple memorization-based baseline, named EdgeBank, which simply stores previously observed edges in memory, and then predicts existing edges in memory as positive at test time. In Fig. 1, we contrast the performance of SOTA methods with that of EdgeBank (in horizontal lines). EdgeBank is a surprisingly strong baseline for dynamic link prediction. In the historical NS setting, EdgeBank achieves the second best ranking amongst all methods. As EdgeBank requires neither learning nor hyper-parameter tuning, we argue that it is a strong and necessary baseline for future methods to compare against.
The goal of this work is to propose more effective evaluation strategies to better differentiate dynamic link prediction methods. We identify challenges and drawbacks in the current evaluation setting for dynamic link prediction: (1) existing strategies for sampling negative edges during evaluation are insufficient, (2) memorization leads to over-optimistic evaluation, and (3) there is a lack of diversity in dynamic graph dataset domains. Our main contributions can be summarized as follows: • Novel Negative Sampling Strategies. We evaluate the impact of negative edges on model performance and outline two novel sampling strategies: historical NS and inductive NS, which provide more robust and in depth evaluation. • Strong Baseline. We propose a novel non-parameterized and memorization-based method, Edge-Bank, which provides a strong baseline for current and future approaches to compare against. • New Datasets and Visualization Tools. We present six novel dynamic graph datasets from various domains such as politics, transportation, and economics. These datasets exhibit different temporal edge evolution patterns, which can be understood through our proposed TEA and TET plots.

Related Work
Benchmarking Graph Learning Methods. A number of studies identify several issues in evaluation of existing GNN models [5,33,6,11,22]. Focusing on static graphs, Dwivedi et al. [5] identify issues with comparative evaluation due to inconsistent experimental settings. Shchur et al. [33] show that reusing the same train-test splits in many different works has led to overfitting and using different splits of the data could result in different ranking of the methods. OGB [11] facilitates reproducibility and scalability of graph learning tasks by providing a diverse set of datasets together with unified evaluation protocols, metrics, and data splits. In contrast to these works, we focus on improving evaluation for dynamic link prediction.
For dynamic graphs, Junuthula et al. [14] differentiate dynamic and static link prediction by edge insertion or deletion. Junuthula et al. [15] then consider the problem of incorporating information from friendship networks into predicting future links in social interaction domains. Haghani and Keyvanpour [10] provide a comprehensive review of link prediction methods for social networks and categorize the link prediction task into two groups: missing link prediction, and future link prediction. Similar to these works, we also focus on dynamic link prediction but from different perspectives: new negative sampling strategies, new baseline, and new dataset domains.
Negative Sampling (NS) of Edges in Graphs. Yang et al. [45] argue that NS is as important as positive sampling in graph representation learning. For static link prediction, the most common method is to sample negative edges at random [8,1,32]. Alternatively, the sampling can be based on connecting nodes with specific properties (e.g. a sufficiently large degree) [19], or it can be based on a particular geodesic distance [20,21]. Kotnis and Nastase [17] provide an empirical study of the impact of different NS strategies during training on the learned representations of various methods in knowledge graphs. In our work, we focus on the impact of NS strategies during evaluation, and propose two novel NS strategies based on the history of the observed edges in dynamic graphs. Current evaluation protocol has difficulty differentiating between models as many methods achieve near-perfect performance across the board. In comparison, our proposed NS strategies sample harder negative edges for better evaluation.
Dynamic Graph Representation Learning. Recently there is a surge of interest towards temporal networks. Kazemi et al. [16] present a survey of advances in representation learning on dynamic graphs. Skardinga et al. [35] concentrate on recent studies on Dynamic Graph Neural Networks (DGNNs) and provide a detailed terminology of dynamic networks. Zhang et al. [46] highlights the importance of learning fully temporal embeddings which also models information propagation. Skardinga et al. [35] and Kazemi et al. [16] both argue modeling dynamic graphs with continuous representations has higher potential, since it offers superior temporal granularity. In our experiments we center our attention on five recent models of this type: JODIE [18], DyRep [38], TGAT [42], TGN [28], and CAWN [40]. We summarize these methods in Appendix A.1. As shown in the experiments section, these methods often achieve close to perfect performance for current link prediction tasks on dynamic graphs. This hinders researchers' ability to evaluate if new models are superior. Also, it exaggerates the efficacy of current models on real-world tasks. Hence, we further examine the evaluation procedure, from the perspective of both benchmark datasets and negative sampling.

Understanding Dynamic Graph Datasets
A dynamic graph can be represented as timestamped edge streams -triplets of source, destination, We aim to understand the differences between dynamic graph datasets across a variety of domains. To this end, we first investigate seven widely used benchmark datasets and contribute six novel dynamic graphs (marked as new) from diverse domains currently under-studied in dynamic link prediction literature. The statistics of these datasets are summarized in Table 1, and details are explained in Section 3.1. To better characterize differences between dynamic graphs, we propose two types of plots and define three indices to visualize and quantify the patterns in dynamic graphs and the difficulty of a given evaluation split in Section 3.2 and Section 3.3.

Temporal Graph Datasets
We consider a wide set of dynamic graph datasets from diverse domains. None of these datasets contains node attributes, but we include description of edge attributes when applicable. The data collection and processing details are explained in Appendix A.2. All datasets are publicly available under MIT licence or Apache License 2.0.
• Wikipedia [18]: consists of edits on Wikipedia pages over one month. Editors and wiki pages are modelled as nodes, and the timestamped posting requests are edges. Edge features are LIWCfeature vectors [27] of edit texts with a length of 172. • Reddit [18]: models subreddits' posted spanning one month, where the nodes are users or posts and the edges are the timestamped posting requests. Edge features are LIWC-feature vectors [27] of edit texts with a length of 172. • MOOC [18]: is a student interaction network formed from online course content units such as problem sets and videos. Each edge is a student accessing a content unit and has 4 features. • LastFM [18]: is an interaction network where users and songs are nodes and each edge represents a user-listens-to-song relation. The dataset consists of the relations of 1000 users listening to the 1000 most listened songs over a period of one month. The dataset contains no attributes. • Enron [34]: is an email correspondence dataset containing around 50K emails exchanged among employees of the ENRON energy company over a three-year period. This dataset has no attributes. • Social Evo. [24]: is a mobile phone proximity network which tracks the everyday life of a whole undergraduate dormitory from October 2008 to May 2009. Each edge has 2 features. • UCI [26]: is a Facebook-like, unattributed online communication network among students of the University of California at Irvine, along with timestamps with the temporal granularity of seconds. • Flights (new) [31]: is a directed dynamic flight network illustrating the development of the air traffic during the COVID-19 pandemic. It was extracted and cleaned for the purpose of this study. Each node represents an airport and each edge is a tracked flight. The edge weights specify the number of flights between two given airports in a day. • Can. Parl. (new) [13]: is a dynamic political network documenting the interactions between Canadian Members of Parliaments (MPs) from 2006 to 2019. Each node is one MP representing an electoral district and each edge is formed when two MPs both voted "yes" on a bill. The edge weights specify the number of times that one MP voted "yes" for another MP in a year. • US Legis. (new) [7,13]: is a senate co-sponsorship graph which documents social interactions between legislators from the US Senate. The edge weights specify the number of times two congress persons have co-sponsored a bill in a given congress. • UN Trade (new) [23]: is a weighted, directed, food and agriculture trading graph between 181 nations and spanning over 30 years. The edge weights specify the total sum of normalized agriculture import or export values between two countries. • UN Vote (new) [39]: is a dataset of roll-call votes in the United Nations General Assembly from 1946 to 2020. If two nations both voted "yes" for an item, then the edge weight between them is incremented by one. • Contact (new) [30]: is a dataset describing the temporal evolution of the physical proximity around 700 university students over a period of four weeks. Each participant is assigned an unique ID and edges between users indicate that they are within close proximity of each other. The edge weights indicate the physical proximity between participants.  Figure 2: TEA plots show many real-world dynamic networks contain a large proportion of edges that reoccur over time. Thus, even a simple memorization approach such as EdgeBank can potentially achieve strong performance. The numbers in parentheses report the novelty index. Due to space limitation, the Reddit's TEA plot is presented in Fig. 7a in Appendix A.3.

Temporal Edge Appearance (TEA) Plot
A TEA plot illustrates the portion of repeated edges versus newly observed edges for each timestamp in a dynamic graph, as shown in Fig. 2. The grey bar indicates the number of edges which were observed in previous time steps and the red bar represents the number of new edges seen at each step. To further quantify the observed pattern, we measure the average ratio of new edges in each timestamps as: Here, E t denotes the set of edges present in timestamp t, and E t seen denotes the set of all edges seen in the previous timestamps. This metric gives an estimation of the portion of the positive edges that a pure memorization method cannot predict correctly. Fig. 2 shows high variance across datasets in temporal evolutionary patterns in terms of new and repeated edges. Some datasets such as Social Evo. comprise mainly repeated edges, while others such as MOOC have a high proportion of new edges. The TEA plots also show significant differences in when edges occur, and distinctions between our new datasets and existing ones. For example, our new Flights dataset has significantly more unique edges and higher numbers of edges per timestamp.
TEA plots imply the importance of considering the relative distribution of the repeated and new edges when designing and choosing methods for the dynamic link prediction task. Because when many edges are repeated, a simple memorization approach can potentially achieve strong performance. On the other hand if there are many new edges, memorization cannot be sufficient. While the TEA plot shows how many edges are repeated or new overall, it does not directly show how consistent the edge repeats are. Thus, we now propose:

Temporal Edge Traffic (TET) Plot
A TET plot visualizes the reocurrence pattern of edges in different dynamic networks over time, as shown in Fig. 3. To construct these plots, we first sort edges based on the timestamp they first appear. Figure 3: TET plots illustrates varied edge traffic patterns in different temporal graphs. The horizontal line starting with "x" marks t split . In parentheses, we report the proportion of train edges reoccurring in the test set (reocurrence index) & the proportion of unseen test edges (surprise index), respectively. Due to space limitation, the Reddit's TET plot is presented in Fig. 7b in Appendix A.3.
Then for edges occurring in the same timestamp, we sort them based on when they last occur. Further, we color edges based on whether they are seen in train only (green), test only (inductive edges, red), or both (transductive edges, orange). To quantify the patterns in these plots we define the following two indices: TET plots provide more insights about the edges that are used for training and testing of different DGNN methods. A memorization approach can potentially predict the transductive positive edges, since it has observed and hence recorded them during training. In particular, if they appear consistently, then simple memorization is likely to be successful. This is when reocurrence index is high and surprise index is low. On the other hand, if they appear at some times but then disappear later, then memory is likely still helpful, but simple and full memorization will not work. It would incorrectly predict that those edges still exist, i.e. when reocurrence index is low. Meanwhile, memorization is not helpful at all for predicting inductive positive test edges at their first appearance, since these are new edges that have not been observed before, i.e. high surprise index.
We encourage researchers to investigate the proposed TEA and TET plots to get a more comprehensive overview of dynamic graphs in addition to the network statistics. For example, while Social Evo. and UN Trade have a relatively similar proportion of repeated vs. new edges based on their TEA plots, we see in their TET plots that UN Trade has far more consistent reocurrence. The clear difference we can observe in the visualization is mirrored in the results -the best model on UN Trade is among the worst on Social Evo., and vice versa (Fig. 5).

EdgeBank: A Baseline for Dynamic Link Prediction
We propose a pure memorization-based approach called EdgeBank, in order to understand whether memorizing past edges can be a competitive baseline. This is based on the observations above that many edges in dynamic graphs reoccur over time. The memory component of EdgeBank is simply a dictionary which is updated with newly observed edges at each timestamp, similar to the memory update procedure of TGN [28]. In this way, EdgeBank resembles a bank of observed edges and requires no parameters. The storage requirement of EdgeBank is the same as the number of edges in the dataset.
At test time, EdgeBank predicts a test edge as positive if the edge was seen before (in the memory), and negative otherwise. EdgeBank can predict correctly for edges which reoccur frequently over time. There are two scenarios where EdgeBank will make an incorrect prediction: (i) an unseen edge, or (ii) an edge observed before (in memory) that is a negative edge at the current time. In the standard random negative sampling evaluation [28,42,40], as graphs are often sparse, it is unlikely that an edge observed before will be sampled as a negative edge. Therefore, EdgeBank has strong performance on negative edges in many cases.
We consider two different memory update strategies for EdgeBank thus resulting in two variants: • EdgeBank ∞ stores all observed edges in memory, thus remembering edges even from a long time ago. It is prone to false positives on edges which appear once but rarely reoccur over time. • EdgeBank tw only remembers edges from a fixed size time window from the immediate past. The size of the time window is set to the duration of test split, based on the intuition of predicting the test set behavior from the most similar (recent) period in the train set. Hence, EdgeBank tw focuses on the edges observed in the short-term past.
Note that EdgeBank is not designed to replace state-of-the-art methods. Rather we argue that all dynamic graph representation methods should be able to do better than memorization, thus beating EdgeBank. EdgeBank provides a simple and strong baseline to demonstrate how far pure memorization can go on each dataset.

Revisiting Negative Sampling in Dynamic Graphs
Current SOTA methods for dynamic link prediction often achieve near perfect performance on existing benchmark datasets [18,38,42,28,40,37]. Consequently, one can argue that either the existing datasets are too simplistic or the current evaluation process is insufficient to differentiate methods. We discussed the dataset aspect extensively. Next, we need to carefully examine the current evaluation setting of DGNNs. In particular, although negative edges constitute half of the evaluation edges, little attention has been dedicated to understanding the effect of different sets of negative edges on the overall performance. In this section, we take a closer look at Negative Sampling (NS) strategies for evaluation of dynamic link prediction, and propose two novel NS strategies for more robust evaluation and better differentiation amongst methods. To better motivate the two new methods, we first explain the standard random NS strategy widely used in literature. Random Negative Sampling Current evaluation samples negative edges randomly from almost all possible node pairs of the graphs [18,38,42,28,40]. At each time step, we have a set of positive edges consisting of source and destination nodes together with edge timestamps and edge features. To generate negative samples, the standard procedure is to keep the timestamps, features, and source nodes of the positive edges, while choosing destination nodes randomly from all nodes. This approach has two significant issues: (1) No Collision Checking: most existing implementations have no collision check between positive and negative edges. There are some exceptions, such as [3], but this holds for all the DGNN methods examined in our experiments. Therefore, it is possible for the same edge to be both positive and negative. This collision is more likely to happen in denser datasets, such as UN Vote and UN Trade. A basic accept-reject sampling could address this issue, as applied in our experiments.
(2) No Reoccurring Edges: the probability of sampling an edge which was observed before is often very low due to the sparsity of the graph. Therefore, a simple method like EdgeBank can perform well on negative edges. However, in many real-world tasks such as flight prediction, correct prediction of the same edge for different time steps is particularly important. For example, predicting that there will be no flight between the north and south poles this week is not nearly as practical as predicting whether a standard, reoccurring commuter flight will be canceled.
To address the second issue, we need to sample from previously observed edges, which can be from train or test set. This constitutes the two alternative NS strategies proposed here, illustrated in Fig. 4.
Here, S is the sample space for negative edges. Let U , E all , E train be the set of all possible node pairs, all edges in the dataset (train and test) and all edges in the train set, respectively. Note that In random NS, we sample from edges e ∈ U , with the proportion from E all and E train regulated only by the sizes of those sets relative to U. To resolve the issues with random NS, in the following sections we propose historical NS and inductive NS.
Historical Negative Sampling. In historical NS, we focus on sampling negative edges from the set of edges that have been observed during previous timestamps but are absent in the current step. The objective of this strategy is to evaluate whether a given method is able to predict in which timestamps an edge would reoccur, rather than, for example, naively predicting it always reoccurs whenever it has been seen once. Therefore, in historical NS, for a given time step t, we sample from the edges e ∈ (E train ∩ E t ). Note that if the number of available historical edges is insufficient to match the number of positive edges, the remaining negative edges are sampled by the random NS strategy.
Inductive Negative Sampling. While in historical NS we focus on observed training edges, in inductive NS, our focus is to evaluate whether a given method can model the reocurrence pattern of edges only seen during test time. At test time, after observing the edges that were not seen during training, the model is asked to predict if such edges exist in future steps of the test phase. Therefore, in the inductive NS, we sample from the edges e ∈ (E test ∩ E train ∩ E t ) at time step t. As these edges are not observed during training, they are considered as inductive edges. Similar to before, if the number of inductive negative edges is not adequate, the remaining negative edges are sampled by the random NS strategy.

Experiments
In this section, we present a comprehensive evaluation of the dynamic link prediction task on all 13 datasets with 5 SOTA methods. Our experimental setup closely follows [18,38,42,28,40]. The objective of the link prediction task is to predict the existence of an edge between a node pair at a given time. For all DGNN methods, we use a Multilayer Perceptron as the output layer for edge prediction, where concatenated node embeddings are inputs and the probability of the edge is the output. For all experiments, we use the same 70% − 15% − 15% chronological splits for the train-validation-test sets as [42,28,40]. The averaged results over five runs are reported. The Area Under Receiver Operating Characteristic (AU-ROC) metric is selected as the main performance metric. We visualize the results for easier interpretation, but the exact numbers that produce the visualizations -and the equivalents with Average Precision (AP) -are presented in the Appendix B.1. Fig. 5a compares the performance of all models under the standard random NS strategy. First, we observe significant variation in performance for all models across datasets. This supports the benefits of evaluation on datasets from different domains. Second, we observe a strong inconsistency in relative ranking amongst methods across datasets. For example, while CAWN achieves SOTA on most datasets, on MOOC and Social Evo. it performs significantly worse than several other models. Lastly, note that EdgeBank demonstrates competitive performance even when compared against SOTA methods. Despite being its simplicity, EdgeBank outperforms highly parametrized and complex models on datasets such as LastFM, Enron and UN Trade.
Next, we examine the impact of NS strategies on performance. Fig. 5b and Fig. 5c shows the performance of different methods with the historical NS and inductive NS strategies, respectively. (e) Inductive compared to random NS. Figure 5: Performance of methods in all three NS settings. In (a) the proposed memorization baselines are on par with SOTA methods, and over-performing in some datasets, e.g. LastFM. In (b) and (c), with alternative negative sampling strategies, we observe a more clear gap between the performance of models and the memorization baseline, whilst the ranking of the models also changes, e.g. CAWN not being the ranked one in most datasets, which is in contrast with the rankings obtained in the standard setting. In (d) and (e), we report the performance drop when moving from the standard setting, which can hint at the (lack of) generalization power of different methods, especially in (e).
First, we observe that the ranking of models can change significantly across different NS settings. This shows that relying on a single NS strategy, such as the random NS, is insufficient for the complete evaluation of methods. Second, for the historical NS setting, EdgeBank tw becomes highly competitive, often beating most methods and even achieving SOTA for UN Trade, UN Vote, Flights, Enron, and Contact. This shows that in these datasets, recently observed edges contain crucial information for link prediction. Third, EdgeBank ∞ has a significant drop in performance in both NS strategies. This shows that as the negative edges are sampled from either previously observed edges or unseen edges, naively memorizing all past edges is no longer sufficient. However, EdgeBank can perform competitively under random NS. This further shows that the standard random NS is limited in its ability to effectively differentiate methods. In Fig. 5d and Fig. 5e, we examine the performance changes for each model in historical or inductive NS setting. CAWN, which performed best overall with random NS, collapses on certain datasets such as LastFM and Enron. Other models fare much better on these datasets. All models exhibit a large performance drop on the Flights dataset.
The performance degradation is also correlated with the degree of memorization. Fig. 6 shows that the models which are more correlated with EdgeBank ∞ tend to perform worse in the historical and inductive NS settings. Since EdgeBank ∞ is naively dependent on the memory, higher correlation with it indicates a model relies more heavily on memorization. For example, CAWN has the highest correlation and JODIE the second highest. They have the largest and second largest losses (respectively) in performance with the more challenging negative sampling. Similarly, DyRep is the least correlated with EdgeBank, and experiences the least drop in performance with historical NS and second least with inductive NS. In this paper we proposed tools to improve evaluation of dynamic link prediction. First, we introduced six new datasets to increase the diversity of domains in which link prediction methods are currently being evaluated. Then we created TEA and TET plots to visualize and quantify the temporal patterns of edges in dynamic graphs, and the difficulty of an evaluation split. Next, we showed limitations of current random negative sampling strategy used in the evaluation and introduced two new strategies, historical and inductive sampling, to better test the generalization of different models. Finally, we proposed a competitive yet simple memorization-based baseline, EdgeBank. It can yield insights into how much different models rely on memorization. When we applied these tools to compare existing models, we found that performance and ranking of different models vary significantly. We hope that these tools will lead to more thorough, lucid, and robust evaluation practices in dynamic link prediction.

A Experiment Details
Here, we provide additional information regarding the baselines, datasets, and experimental settings.

A.1 Baselines
We consider the following DGNN methods as our baselines. All of these methods utilize node and edge features during the representation learning process if the network is attributed. In case a network is not attributed, vectors of zeros are passed as the initial features.
• JODIE [18]: focuses on bipartite networks of instantaneous user-item interactions. JODIE has an update operation and a projection operation. The former utilizes two coupled RNNs to recursively update the representation of the users and items. The latter predicts the future representation of a node, while considering the elapsed time since its last interaction.
• DyRep [38]: has a custom RNN that updates node representations upon observation of a new edge. For obtaining the neighbor weights at each time, DyRep uses a temporal attention mechanism which is parameterized by the recurrent architecture.
• TGAT [42]: aggregates features of temporal-topological neighborhood and temporal interactions of dynamic network. The proposes TGAT layer employs a modified self-attention mechanism as its building block where the positional encoding module is replaced by a functional time encoding.
• TGN [28]: consists of five main modules: (1) memory: containing each node's history and is used to store long-term dependencies, (2) message function: for updating the memory of each node based on the messages that are generated upon observation of an event, (3) message aggregator: aggregating several message involving a single node, (4) memory updater: responsible for updating the memory of a node according to the aggregated messages, and (5) embedding: generating the representations of the nodes using the node's memory as well as the node and edge features. Similar to TGAT, TGN also utilizes time encoding for effectively capturing the inter-event temporal information.
• CAWN [40]: generates several Causal Anonymous Walks (CAWs) for each node, and uses these CAWs to generate relative node identities. The identities together with the encoded elapsed time are used for encoding the CAWs by an RNN. Finally, the encodings of several CAWs are aggregated and fed to a MLP for predicting the probability of a link between two nodes.
The source code of baseline methods are publicly available under MIT licence or Apache License 2.0.

A.2 Data Collection and Processing
• Flights (new) [31]: is a directed dynamic flight network illustrating the development of the air traffic during the COVID-19 pandemic. This dataset is derived from the OpenSky dataset [36] and cleaned by Olive et al. 2 [31] with the traffic library [25]. It contains all flights observed by the OpenSky network's 2500 members since January 1st, 2020. To convert the dataset into a machine learning friendly format, we have: (1) removed all flights where either the source or the destination airport is missing, (2) aggregated the flights with shared origin and destination in the same day into weighted edges (increment by 1 per flight), and (3) assigned a unique node ID to each airport. For future research, the final cleaned and processed edge-list is available. The edge weights specify the number of flights between two given airports in a day.
• Can. Parl. (new) [13]: the Canadian Parliament Political network dataset is originally collected and processed by Huang et al. [13] for the network change point detection task. As political networks are currently unrepresented in existing benchmarks, we curate it for dynamic link prediction in this work. The dataset is collected from the Open Parliament initiative which documents the voting process inside the Canadian Parliament. There are 338 Members of Parliament (MPs) where each one represents an electrical district who is elected for four years and can be re-elected. The network documents the collaborative efforts among MPs. Each bill has a sponsor MP and other MPs can vote positively or negatively towards this bill. A directed edge is added from a voter MP to the sponsor MP when the voter MP votes "yes" for the sponsor MP's who sponsors the bill. The edge weights specify the number of times that the voter MP voted positively for the sponsor MP in a year. We assigned an unique node ID to each MP and anonymized the data. • US Legis. (new) [7,13]: the US Legislative network documents social interactions between US legislators based on their co-sponsorship relations on bills presented during the 93rd-108th Congress. The dataset is originally collected by Fowler et al. [7], and then, processed into an edge-list format by Huang et al. [13]. In the US House and Senate, each piece of legislative must be sponsored by a unique legislator. Other legislators can then choose to publicly express support for such bill by cosponsoring it. Therefore, US Legis. network falls in the same domain as Can.
Parl. network where positive interactions between politicians are observed. The main difference being that US Legis. is undirected. If two congress persons cosponsor a bill, an undirected edge is formed between them. The edges are grouped into snapshots biannually (i.e., per congress). Note that the edge weights specify the number of times two congress persons have cosponsored a bill in a given congress. We also assign a unique node ID to each congress person to anonymized the data. • UN Trade (new) [23]: the United Nations food and agriculture trade dataset is originally collected, processed and disseminated by the Food and Agriculture Organization of the United Nations 3 . The data is mainly provided by UNSD, Eurostat and other national authorities as needed. The trade data includes all food and agriculture products imported or exported annually by all the countries in the world. Please refer to [23] for more details about the data. To process the data into a temporal graph format, we sum over the normalized import values across all food types of a country v from another country u as a weighted directed edge from u to v. Likewise, we sum over the normalized export values as weighted outgoing edges between two countries. The processed dataset contains annual data from 1986 to 2017, modelling trading relations between nations. The edge weights specify the total sum of normalized agriculture import or export values between two countries. • UN Vote (new) [39,2]: is a dataset of roll-call votes in the UN General Assembly for 1946 to 2017.
Each country in the United Nations can vote yes, abstain, no, or absent for a given UN bill (such as amendments, security council elections, voting procedure and more). To convert the dataset into a temporal graph, we modelled collaborative votes between nations. For example, if a nation u and another nation v both voted yes for a given bill, we add an undirected edge between them. In this way, the UN Vote network models the evolving political collaborations between nations at the United Nations. Note that the edge weights count the number of times two nations both voted yes for a bill in a year. • Contact (new) [30]: the Copenhagen Contact Network describes the temporal evolution of the physical proximity of around 700 university students over a period of four weeks. This is achieved by collecting data from smartphones and estimating physical proximity via Bluetooth signal strength as part of the Copenhagen Networks Study [30]. Considerable efforts are exercised to anonymize the data and preserve the participants' privacy as indicated in [30]. We cleaned the physical proximity network by removing users outside of the school as they are not tracked consistently and convert the dataset into a temporal edge-list format. Each participant is assigned a unique ID and edges between users indicate that they are within close proximity of each other. The proximity between participants is tracked every five minutes via Bluetooth and the edge weights indicate the Received Signal Strength (RSSI) in units of dBm (Decibel-miliwatt), with a smaller value indicating that two participants are closer in proximity.

A.3 TEA and TET plots for Reddit Dataset
Due to the space limitation in the main paper, we include the TEA and TET plots for the Reddit dataset here in Fig. 7.

A.4 Discussion on Different Performance Metrics
Essentially, the dynamic link prediction task is modeled as a binary classification problem by the existing literature. Therefore, for evaluating the performance of different methods, utilization of threshold curve based metrics, such as Area Under the ROC cure (AU-ROC) and Average Precision (AP), are more encouraged [44]. Other performance metrics (such as Accuracy, Precision, Recall, or F 1 -score) require a proper confidence threshold for their decision. Since, the exact value of the threshold is often ill-defined in the literature, exploiting these metrics leads to unfair comparison across different methods. In this work, we evaluated the performance of different methods in terms of AU-ROC (Table 3, Table 6, and Table 10) and AP (Table 2, Table 4, and Table 8).

A.5 Hyperparameters
For all the methods and datasets, we utilized the Adam optimizer with the learning rate equal to 0.0001. The batch size for the training, validation, and testing was 200. We set the number of epochs equal to 50 and considered an early stopping with a patience of 5. The dropout was 0.1, the number of attention heads was 2, and we set the node embedding size equal to 100.
For TGAT, TGN, and CAWN, the time embedding size was 100. For TGN, we set the memory dimension as 172 and message dimension as 100. Lastly, for the CAWN, we used landing probability as the positional encoding, and we set the positional embedding dimension as 64 and the number of walk attention heads as 8.

A.6 Computing Resources
All the experiments were carried out on the Graham cluster of Compute Canada. For all baselines, we executed each run with one of either P100, V100 or T4 Turing GPUs. The results reported are averaged over 5 runs and each run took on average 24 hours (depending on the dataset and the method). Therefore, each item reported in Table 2 required 5 GPU days except for our proposed EdgeBank method which ran very efficiently on CPU only.

B.1 Extended Results
Here, we report the extended results used to plot the figures in the main paper. In particular, we report the AP and AU-ROC of the dynamic link prediction task in random (Table 2 and Table 3), historical (Table 4 and Table 6), or inductive (Table 8 and Table 10) NS setting. We also report the AP loss and AU-ROC loss of historical (Table 5 and Table 7) and inductive (Table 9 and Table 11) compared to random NS setting.

B.2 More Discussion on Historical and Inductive Negative Sampling
In Section 5, we explain different negative sampling strategies and mention that in case of historical and inductive negative sampling, if there are not enough historical or negative edges to sample from, we randomly sample negative edges to preserve dataset balance during the test phase. Here, we elaborate more on the statistics of the negative samples selected during the test phase for each dataset.
Specifically, in the historical negative sampling setting, all considered datasets have enough historical edges to sample from during the test phase. Thus, there is no need to sample random edges. The    detailed statistics of the number of random versus historical negative edges during the test phase are given in Table 12, second and third column.
In the inductive negative sampling setting, at the first batches of the initial timestamps of the test phase, there are not enough inductive negative edges. Therefore, some random edges should be selected to compose a balanced dataset. As an example of such a dataset, we can consider Social Evo. whose TET plot is illustrated in Fig. 3e. We can observed that this dataset does not have enough inductive edges, therefore the majority of the negative edges during the test phase are randomly selected. This also affects the performance change for Social Evo. dataset reported in Fig. 5e. Because a lot of negative edges are sill selected randomly, we observe a less severe performance drop for Social Evo. in Fig. 5e. The detailed statistics of the number of random versus inductive negative edges in the test phase are given in Table 12, fourth and fifth column. Fig. 8 demonstrates the average change in performance with historical and inductive NS across different SOTA methods. In general, the decrease is at least 10 percentage points. The new Flights and Contact datasets are particularly challenging, with more than 25 percentage points average loss when comparing historical or inductive NS with random NS. In case of the Flights network, this can be interpreted as the models struggle to correctly predict whether a flight that happened in the past will happen again.    We expect this work to have a major impact on the fundamental as well as applied dynamic graph research.
Essentially, high-quality datasets from diverse domains play undeniable roles in advancement of research (e.g., OGB [11] or ImageNet [4]). By contributing 5 new datasets from less explored real-world domains, we aim to enrich available datasets for dynamic graph learning tasks, and facilitate the development of novel dynamic graph models.
In addition, our proposed dynamic graph visualization techniques (i.e., TEA and TET plot) together with the defined indices (i.e., novelty, reoccurrence, and surprise index) provide comprehensive summary of datasets characteristics. EdgeBank also provides   a simple yet strong baseline for the dynamic link prediction task that future learning models can easily compare against. Additionally, our investigation on the impact of negative sampling in dynamic graphs leads to more robust evaluation setup for the dynamic link prediction task and facilitates methodological advancement in dynamic graph ML.
Since dynamic link prediction has many applications in different domains, such as recommendation systems, academic graphs, computational finance, etc., we expect this work to facilitate the development of applied methods in different domains as well.

Potential Negative Impact
In this work, we have investigated several dynamic graph datasets that are under study in dynamic graph research. One potential negative impact is that future research may narrow down their study to these datasets. We aim to regularly update the datasets with the input from the community to prevent this issue.
Additionally, improving link prediction can be associated with several potential negative use cases such as user profiling. While our work does not directly lead to such negative impacts, being aware of such impacts is important and appropriate precautions should be considered.

D Limitations
We consider two main limitations for this work:   First, in the current evaluation setup, there is a single point split for past and future links, which is the current common practice. It might be more relevant to consider alternative settings where temporal information plays a stronger role, from splitting in more time points to predict the exact time of an edge.
Second, we have only considered the transductive setting where all nodes are seen during training, since this is the only setup that we could easily check for memorization. The baseline and historic negative sampling strategy proposed here are only considered in the transductive setting.
In addition to these two main limitations, we only considered the dynamic link prediction task and leave the exploration of similar concepts in the related node classification task in dynamic graphs as future work.

E Maintenance Plan
To provide an easy to use, robust and diverse benchmark for dynamic link prediction, we will be maintaining a code repository at https://github.com/fpour/DGB.git to run the experiments and benchmarks. The relevant datasets will be maintained at https://zenodo.org/record/ 7008205#.Yv_a_3bMJPZ. These code and data repositories will be updated regularly to include more datasets and benchmarks as they become available. We also plan to increase accessibility of the benchmark by adding more documentations and tutorials and providing a simple command for python package manager.