# Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
## 4 Towards More Targeted Negative Sampling Strategies for Dynamic Link Prediction
### A Taxonomy of Negative Samples  
Given that unrealistic NS leads to an uninformative evaluation of DLP, how might we generate more useful negative samples? Clearly, this depends on the task at hand. For example, in the Flights dataset, the goal is to predict which destination a plane in a given origin airport will depart to at a given time. In this case, most edges will have been observed already, and it is more interesting to evaluate whether our model can distinguish between the actual origin and destination of the flight and an origin-destination pair that has been previously observed. Therefore, a realistic negative sample could be generated by replacing the actual edges with previously observed edges. Similarly, in the case of social networks such as email datasets, the goal may be predicting the receiver of a message emitted by a given sender at a certain time. In this case, one may want to specifically sample a negative edge \((u^{\prime},v^{\prime},t)\) such that the destination node \(v^{\prime}\) interacts in both the train and test sets. The intuition for such a choice is that modelswill tend to naturally assign a higher score to events whose nodes have interacted in the train set. Moreover, the fact that these nodes are also present in the test set indicate that they may still be active at the time of the positive interaction, thus making the negative interaction a reasonable candidate. Here, we aim to contribute NS strategies which can be applied to any dataset or task. Instead of focusing on specific applications, we present a general taxonomy of potential edges that can be used as negative samples. DLP performance can then be appropriately scrutinized for different types of negatives in _any_ application. Considering that machine learning evaluation typically distinguishes performance on the train set from performance on the test set, we make heavy use of our definition of temporal categories in Section 3.2. Assume any NS strategy starts from a positive event \((u,v,t)\) and then 'corrupts' it into (realistic) negatives \(\{(u^{(k)},v^{(k)},t)\}_{k=1,\ldots,K}\). As discussed previously, the timestamp \(t\) is left unchanged, as this is the time at which the prediction is assumed to be made. We can then either corrupt one of the nodes in the event (which we call negative _node_ sampling) or both (which we call negative _edge_ sampling). For both, different strategies can be discerned, as described in the following two definitions. **Definition 9** (Negative Node Sampling). : _Negative node sampling_ (_node-NS_) _takes a positive event \((u,v,t)\) and replaces the source node \(u\) by \(u^{\prime}\in\mathcal{U}\) or the destination node \(v\) by \(v^{\prime}\in\mathcal{U}\). In both cases, the other node is left the same._  
_For a given cutoff time \(t_{split}\), we distinguish six types of negative node samples:_  
**Historical Source (HS)**: \[d^{u^{\prime}}_{\mathcal{H}}<t_{split};\]
**Overlap Source (OS)**: \[b^{u^{\prime}}_{\mathcal{H}}<t_{split}\wedge d^{u^{\prime}}_{\mathcal{H}}\geq t _{split};\]
**Inductive Source (IS)**: \[b^{u^{\prime}}_{\mathcal{H}}\geq t_{split};\]
**Historical Destination (HD)**: \[d^{v^{\prime}}_{\mathcal{H}}<t_{split};\]
**Overlap Destination (OD)**: \[b^{v^{\prime}}_{\mathcal{H}}<t_{split}\wedge d^{v^{\prime}}_{\mathcal{H}}\geq t _{split};\]
**Inductive Destination (ID)**: \[b^{v^{\prime}}_{\mathcal{H}}\geq t_{split}.\]  
**Remark 2**. : _In undirected graphs, source and destination sampling are equivalent._  
**Definition 10** (Negative Edge Sampling).