# Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
## 3 Understanding the Effect of Splitting a Dynamic Graph Based on Time
### The Birth and Death of Nodes and Edges  
Dynamic graphs dynamically evolve over time. A key motivation for our contributions is that many real CTDG datasets only have nodes and edges that interact within a specific timeframe. For instance, in a social network, a new user may join (represented as a node), or a pair of users (i.e., an edge) may cease interacting entirely at a certain time. To formalize these concepts, we introduce the following definitions.  
**Definition 1** (Birth time).: _For any node \(x=u\) or edge \(x=(u,v)\), the **birth time**\(b_{\mathcal{H}}^{x}\) is defined as the earliest time at which this node or edge is involved in an event in history \(\mathcal{H}\):_  
\[b_{\mathcal{H}}^{x}\triangleq\min_{(u,v,t)\in\mathcal{H}^{x}}t. \tag{1}\]  
**Definition 2** (Death time).: _For any node \(x=u\) or edge \(x=(u,v)\), the **death time**\(d_{\mathcal{H}}^{x}\) is defined as the latest time at which this node or edge is involved in an event in history \(\mathcal{H}\):_  
\[d_{\mathcal{H}}^{x}\triangleq\max_{(u,v,t)\in\mathcal{H}^{x}}t. \tag{2}\]  
Note that, by definition, \(b_{\mathcal{H}}^{x}\leq d_{\mathcal{H}}^{x}\). These definitions allow us to capture the lifespan of nodes and edges in dynamic graphs, which is crucial for understanding their behavior and evolution over time.  
We argue that the Birth and Death times of nodes and edges are highly relevant when splitting up a CTDG's events into a train set \(\mathcal{H}_{\text{train}}\) and test set \(\mathcal{H}_{\text{test}}\). Such splitting is performed to assess a model's ability to generalize to unseen data that is encountered in real-world applications, but CTDGs typically see nodes and edges _reoccur_ often. In fact, exploiting recurring patterns is an implicit goal of any machine learning task. Previous work [8; 15] has hypothesized that it is far easier for any parametrized model to predict if and when an edge occurs in the test set \(\mathcal{H}_{\text{test}}\), if it has already learned from the occurrencesof the same edge in the train set \(\mathcal{H}_{\text{train}}\). The formal definition of the Birth and Death times helps to elucidate this assumption. For instance, we can state that the occurrence of an edge in the test set will seem more likely to a model if its Birth time \(b_{\mathcal{H}}^{x}\) was before \(t_{\text{split}}\). Likewise, nodes that were already active in the train set, i.e., they were 'born' at time \(b_{\mathcal{H}}^{x}<t_{\text{split}}\), will be better understood and less surprising than nodes with a Birth time \(b_{\mathcal{H}}^{x}\geq t_{\text{split}}\).  
Moreover, the extent to which different methods are capable of accurately predicting previously unseen edges in the test set may vary between these different situations. Understanding such differences may be important for choosing the most appropriate method in a particular application.  
Therefore, a prudent and useful analysis of (predictions over) a CTDG benefits from partitioning nodes and edges into three categories, which we define here. In all definitions, we denote by \(t_{split}\) the time at which the train-test split is made.  
**Definition 3** (Historical).: _A **historical** (\(H\)) node or edge \(x\) only occurs in the train set \(\mathcal{H}_{\text{train}}\) and never in the test set \(\mathcal{H}_{\text{test}}\), i.e.,_  
\[d_{\mathcal{H}}^{x}<t_{\text{split}}. \tag{3}\]  
**Definition 4** (Inductive).: _An **inductive** (\(I\)) node or edge \(x\) only occurs in the test set \(\mathcal{H}_{\text{test}}\) and never in the train set \(\mathcal{H}_{\text{train}}\), i.e.,_  
\[b_{\mathcal{H}}^{x}\geq t_{\text{split}}. \tag{4}\]  
**Definition 5** (Overlap).: _An **overlap** (\(O\)) node or edge \(x\) occurs in both the train set \(\mathcal{H}_{\text{train}}\) and the test set \(\mathcal{H}_{\text{test}}\), i.e.,_  
\[b_{\mathcal{H}}^{x}<t_{\text{split}}\wedge d_{\mathcal{H}}^{x}\geq t_{\text {split}}. \tag{5}\]