# Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
## 5 Experimental Setup
### Methods  
In our experiments, we consider 4 different DLP algorithms. The first two methods are simple parameter-free heuristics, which work by memorizing either the _nodes_ or the _edges_ observed in past events. We describe them here, and detail the type of error that these are susceptible to commit:  
* **Preferential Attachment (PA)** assigns a score of 1 to an event \((u,v,t)\) if and only if both the nodes have been observed in the past \(\mathcal{H}_{t}\): \[s(u,v,t|\mathcal{H}_{t})=\mathbb{1}_{\{u\in\mathcal{U}_{t}\wedge v\in\mathcal{ U}_{t}\}}.\] (6) This method issues a false negative when the true event \((u,v,t)\) is such that neither \(u\) nor \(v\) were ever observed prior to \(t\), and a false positive when the negative event \((u^{\prime},v^{\prime},t)\) is such that both \(u^{\prime}\) and \(v^{\prime}\) were involved in a past event.
* **EdgeBank**[8] assigns a score of 1 to an event \((u,v,t)\) if and only if the edge \((u,v)\) has been observed in the past \(\mathcal{H}_{t}\): \[s(u,v,t|\mathcal{H}_{t})=\mathbb{1}_{\{(u,v)\in\mathcal{E}_{t}\}}.\] (7) This method yields false negatives whenever the true event \((u,v,t)\) is such that the edge \((u,v)\) was never involved in any event up to time \(t\). It produces false positives whenever the negative event \((u^{\prime},v^{\prime},t)\) is such that \((u^{\prime},v^{\prime})\) was involved in an event before \(t\).  
While simple, these baselines are helpful reference points to assess the performance of more sophisticated methods, as they relate directly to the Birth-Death diagrams presented in Section 3.3. Indeed, one can think of Preferential Attachment and EdgeBank as follows. If we draw a horizontal line at the y coordinate corresponding to the current time \(t\), PA will assign a score of 1 to any event \((u,v,t)\) such that both \(u\) and \(v\) are below the line, i.e.,have a Birth time prior to \(t\): \(b^{u}_{\mathcal{H}}<t\) and \(b^{v}_{\mathcal{H}}<t\). Similarly, EdgeBank will output a score of \(1\) to any event such that the _edge_\((u,v)\) is represented by a point below the horizontal line with a y coordinate equal to \(t\) (i.e., \(b^{(uv)}_{\mathcal{H}}<t\)). On top of these methods, we consider two memory-based dynamic graph representation learning methods, which we briefly introduce below:  
* **TGN-attn**[11] is a DLP algorithm composed of two main modules. A memory module is responsible for maintaining a node-level memory state, encoding the past events at the node level. Using an attention module, the memory states of different nodes are then combined and subsequently used to calculate the probability of the event \((u,v)\).
* **DyRep**[32] has a similar architecture, but specifically uses an attention mechanism on the destination node in order to update the memory given an incoming event.  
In terms of implementation, we use a common approximation to the memory-based methods discussed above. Instead of updating the memory state (set of observed nodes or edges for PA/EdgeBank, node memory states for TGN and DyRep) at every newly observed events, the interactions are consumed by mini batches of 200 events. For each batch, the models successively compute a prediction score for the events in this batch and the associated negative samples, and then update their memory by ingesting the events in that batch.