Revisiting Temporal Link Prediction through Structural Proximity

Temporal link prediction is an important task for understanding evolving real-world systems, encompassing both recurring interactions and the formation of new relations. Existing studies often characterize datasets by the proportion of previously unseen relations. However, an unseen node pair may still be strongly connected through multi-step paths in the historical graph. This raises a more fundamental question: how much of future-link predictability can be explained by historical structural proximity, even without representation learning? To investigate this question, we revisit Personalized PageRank (PPR), a classical training-free measure of structural proximity, to assess how well historical connectivity predicts future interactions.We incorporate temporal decay into PPR to account for interaction recency, yielding Time-decay PPR. Across 14 datasets spanning diverse domains and interaction patterns, Time-decay PPR ranks first on nine and second on four among the compared methods. Further experiments show that multi-step historical paths help distinguish candidate destinations for new relations, suggesting that current neural models may not fully exploit these structural cues. These findings highlight the predictive value of historical structural proximity and offer insights for reassessing existing methods and designing future models.