Expressive and Efficient Representation Learning for Ranking Links in Temporal Graphs

Temporal graph representation learning (T-GRL) aims to learn representations that model how graph edges evolve over time. While recent works on T-GRL have improved link prediction accuracy in temporal settings, their methods optimize a point-wise loss function independently over future links rather than optimize jointly over a candidate set per node. In applications where resources (e.g., attention) are allocated based on ranking links by likelihood, the use of a ranking loss is preferred. However it is not straightforward to develop a T-GRL method to optimize a ranking loss due to a tradeoff between model expressivity and scalability. In this work, we address these issues and propose a Temporal Graph network for Ranking (TGRank), which significantly improves performance for link prediction tasks by (i) optimizing a list-wise loss for improved ranking, and (ii) incorporating a labeling approach designed to allow for efcient inference over the candidate set jointly, while provably boosting expressivity. We extensively evaluate TGRank over six real networks. TGRank outperforms the state-of-the-art baselines on average by 14.21%↑ (transductive) and 16.25% ↑ (inductive) in ranking metrics while being more efficient (up-to 65× speed-up) to make inference on large networks.