# Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
## 4 Towards More Targeted Negative Sampling Strategies for Dynamic Link Prediction
### Background on Dynamic Link Prediction  
Having thoroughly analyzed the nodes and edges in a CTDG, we now formalize the task of Dynamic Link Prediction (DLP). **Definition 7** (Dynamic Link Prediction). : _The Dynamic Link Prediction (DLP) problem is the task of distinguishing positive (true) interactions \((u,v,t)\) from interactions \((u^{\prime},v^{\prime},t)\) that do not occur at the same time t._ \begin{table}
\begin{tabular}{l|c|c c c c c|c c c c c} \hline \hline  & **Events** & \multicolumn{6}{c|}{**Nodes**} & \multicolumn{6}{c}{**Edges**} & \\  & & **Total** & **Historical** & **Overlap** & **Inductive** & **Surprise** & **Total** & **Historical** & **Overlap** & **Inductive** & **Surprise** \\ \hline UCI & 59,835 & 1899 & 1052 & 681 & 166 & 0.196 & 20,296 & 17,069 & 657 & 2570 & 0.796 \\ HighSchool & 45,047 & 180 & 18 & 160 & 2 & 0.012 & 2239 & 1577 & 445 & 217 & 0.328 \\ Wikipedia & 157,474 & 9227 & 5663 & 2648 & 916 & 0.257 & 18,257 & 13,667 & 2046 & 2544 & 0.554 \\ Enron & 125,235 & 184 & 43 & 138 & 3 & 0.021 & 3125 & 1914 & 724 & 487 & 0.402 \\ USLegis & 60,396 & 225 & 112 & 101 & 12 & 0.106 & 26,423 & 18,884 & 5857 & 1682 & 0.223 \\ UNvote & 1,035,742 & 201 & 7 & 194 & 0 & 0.000 & 31,516 & 4487 & 26,583 & 446 & 0.017 \\ UNtrade & 507,497 & 255 & 27 & 228 & 0 & 0.000 & 36,182 & 10,595 & 24,347 & 1240 & 0.048 \\ SocialEvo & 2,095,919 & 74 & 12 & 62 & 0 & 0.000 & 4486 & 2609 & 1827 & 50 & 0.027 \\ MOOC & 411,749 & 7144 & 4732 & 2185 & 227 & 0.094 & 178,443 & 147,612 & 6628 & 24,023 & 0.785 \\ Flights & 1,927,145 & 13,169 & 2182 & 10,698 & 289 & 0.026 & 395,072 & 264,189 & 85,369 & 45,514 & 0.348 \\ Reddit & 672,447 & 10,984 & 1369 & 9578 & 37 & 0.004 & 78,516 & 53,589 & 17,933 & 6994 & 0.281 \\ Lastfm & 1,293,103 & 1980 & 227 & 1681 & 72 & 0.041 & 154,993 & 106,038 & 30,883 & 18,072 & 0.369 \\ CanParl & 74,478 & 734 & 384 & 340 & 10 & 0.029 & 51,331 & 38,401 & 7432 & 5498 & 0.425 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Dataset statistics, including the node and edge surprise indices, for a test ratio of 15%. For most datasets, the nodes are mostly all observed during training, hence a relatively low node surprise index. The edge surprise is higher however, since many edges that interact in the test set were never observed in the test set. For example, the task at hand can be to predict which two people \(u\) and \(v\), at the present time \(t\), are most likely to interact in a social network. **Algorithms for DLP. ** In practice, DLP algorithms are required to output a _score_\(s(u,v,t|\mathcal{H}_{t})\) that expresses the likelihood of the event \((u,v,t)\) given the past history of events \(\mathcal{H}_{t}\) up to time \(t\) (as any future event would be unavailable at that time). When discussing DLP algorithms, it will then be helpful to also define \(\mathcal{U}_{t}\) as shorthand notation for the set of nodes interacting up to time \(t\) and \(\mathcal{E}_{t}\) for the set of edges. We note that parametric DLP algorithm (e.g., neural networks) will typically output a score \(s(u,v,t|\mathcal{H}_{t})\) that is a function of the past history \(\mathcal{H}_{t}\) and of the parameters of the model. Thus, to evaluate the score of a given test event \((u,v,t)\), DLP algorithms are given access to the history up to time \(t\), but are not allowed to update their parameters based on these test events. **Negative Sampling for Evaluation**. As already discussed, the goal of DLP algorithms is to accurately score the events \((u,v,t)\), conditioned on the past \(\mathcal{H}_{t}\) at time \(t\). Ideally, a perfect model would score any _positive_ event \((u,v,t)\), i.e., an event that actually occurs in history \(\mathcal{H}\), higher than any _negative_ event \((u^{\prime},v^{\prime},t)\), such that \((u^{\prime},v^{\prime})\
eq(u,v)\), i.e., an event that could have occurred (but did not) at time \(t\). The default strategy would thus be to gather all possible edges and calculate their scores jointly with the positive event at time \(t\).