# Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
## 3 Understanding the Effect of Splitting a Dynamic Graph Based on Time
### The Birth-Death Diagram  
For a given a cutoff time \(t_{\text{split}}\), the Birth and Death times of nodes and edges clearly distinguish whether they are historical, overlap, or inductive. By extension, the distribution of their Birth and Death times characterizes the difficulty of the test set for any cutoff time.  
We therefore introduce the Birth-Death diagram: a scatter plot visualization that represents each node or edge by its Birth time (on the y-axis) and Death time (on the x-axis). Figure 1 illustrates the Birth-Death diagram on a dataset of face-to-face interactions among high school students. Moreover, in Figure 2, we plot the Birth-Death diagrams for different CTDG datasets from the benchmark of [PERSON] et al. [8]. We refer the reader to [8] for details about the datasets.  
**Remark 1**.: _For all datasets in our illustration, the cutoff time is determined as the \(1-\alpha\)-th quantile of the event times, where \(\alpha\) is a train-test split ratio set to \(\alpha=0.15\). In simpler terms, this means that the cutoff time \(t_{\text{split}}\) is set to the point in time beyond which 15% of the events occur. Any events that occur before this point in time are included in the training set, while any events that occur after this point in time are included in the test set._  
From Figure 2, we can draw some interesting observations, which we discuss here.  
Figure 2: Birth–Death diagrams for nodes and edges in datasets from the dynamic graph benchmark from [PERSON] et al. [8]. The datasets are split into train and test sets containing 85% and 15% of the events, respectively.  
**Seasonality of Birth and Death Times**. The seasonality of lifespan patterns can be observed in both the HighSchool and MOOC datasets as the points corresponding to edges and nodes tend to cluster into squares representing days. The UCI dataset, which describes online interactions among students from April to October 2004, also shows seasonality in the holiday break: there is a white stripe during the holiday break (slightly before \(t_{split}\)). This seasonality is a crucial property of the Link Prediction task at hand. For instance, in the case of the HighSchool dataset, a possible task can be predicting interactions between students during a specific day, given that we trained a model on the past few days. For these datasets, carefully representing time using techniques such as time encoding [37] can be crucial to achieve good performances.  
**Short-Lived Nodes and Edges**. The high density of points on the diagonal of these diagrams, in particular in the Wikipedia dataset, indicates that most nodes and edges have very _short lifespans_. As a result, information learned by models about these instances has a higher chance of becoming obsolete after some time. Here, it is crucial that methods take into account time and prioritize active edges/nodes. Conversely, however, some nodes and edges have very long lifetimes in the Wikipedia and Flights datasets (their scatter points are in the lower right), so memorization may work well on these.  
**\"Easy\" Datasets**. There are some datasets, namely UNtrade, Enron, CanParl, and HighSchool, where most of the nodes are observed at least once in the train set, with only a few nodes starting interactions in the test set. Memorization heuristics such as Preferential Attachment and EdgeBank will constitute strong baselines for these datasets.  
Finally, it is crucial to note that for User-Item graphs, such as Wikipedia, MOOC or Lastfm, the Birth-Death diagram will yield different profiles for the User and Item nodes. We showcase and discuss these differences in Appendix A.