The goal of dynamic link property prediction is to predict the property (often the existence) of a link between a node pair at a future timestamp.
Negative Edge Sampling. In real applications, the true edges should not known upfront. Subsequently, a lot of node pairs are queried, and onlypairs with the best scores are treated as edges. Motivated by this, we frame the link prediction task as a rating problem and sample multiple negative edges per each positive edge. Particularly, for a given positive edge (s,d,t), we fix the source node s and timestamp t and sample q different destination nodes d. For every dataset, q is chosen based on the trade-off between evaluation completeness and test set inference time. Out of the q negative samples, half are sampled uniformly at random, while the opposite half are historic negative edges (edges that were observed within the training set but should not present at time t).
Performance metric. We use the filtered Mean Reciprocal Rank (MRR) because the metric for this task, because it is designed for rating problems. The MRR computes the reciprocal rank of the true destination node among the many negative or fake destinations and is usually utilized in advice systems and knowledge graph literature.
Results on small datasets. On the small tgbl-wiki and tgbl-reviewdatasets, we observe that one of the best performing models are quite different. As well as, the highest performing models on tgbl-wiki similar to CAWN and NAT have a big reduction in performance on tgbl-review. One possible explanation is that the tgbl-reviewdataset has a much higher surprise index in comparison to the tgbl-wikidataset. The high surprise index shows that a high ratio of test set edges is rarely observed within the training set thus tgbl-reviewrequires more inductive reasoning. In tgbl-review, GraphMixer and TGAT are one of the best performing models. As a result of their smaller size, we’re in a position to sample all possible negatives for tgbl-wikiand 100 negatives for tgbl-reviewper positive edge.
Most methods run out of GPU memory for these datasets thus we compare TGN, DyRep and Edgebank on these datasets resulting from their lower GPU memory requirement. Note that some datasets similar to tgbl-commentor tgbl-flightspanning multiple years thus potentially leading to distribution shift over its very long time span.
Insights. As seen above in tgbl-wiki, the variety of negative samples used for evaluation can significantly impact model performance: we see a big performance drop across most methods, when the variety of negative samples increases from 20 to all possible destinations. This verifies that indeed, more negative samples are required for robust evaluation. Curiously, methods similar to CAWN and Edgebank have relatively minor drop in performance and we leave it as future work to analyze why certain methods are less impacted.
Next, we observe as much as two orders of magnitude difference in training and validation time of TG methods, with the heuristic baseline Edgebank all the time being the fastest (because it is implemented simply as a hashtable). This shows that improving the model efficiency and scalability is a crucial future direction such that novel and existing models will be tested on large datasets provided in TGB.