Structural proximity matches complex models for predicting future links
Revisiting Temporal Link Prediction through Structural Proximity
Social and Information NetworksMachine Learning
Summary
Predicting future connections in networks usually involves complex computer models that learn from patterns over time. This paper shows that a classic approach, Personalized PageRank (PPR), which looks at the structure of past interactions, can perform just as well or better without fancy training. The researchers tested this on many datasets and found that simple methods based on how closely nodes are connected historically work surprisingly well. This challenges the idea that more complicated temporal models are always needed for good predictions.
What this means in practice
- •For social media platform engineers: Use simple structural proximity measures like time-decayed PPR to predict future user interactions efficiently without complex training.
- •For network security analysts: Identify likely future communication links in computer networks using fast, classical methods to anticipate and monitor potential threats.
Authors
Yuzhang Fei, Yanping Zheng, Lu Yi, Zhewei Wei
Abstract
Existing temporal link prediction methods typically rely on learned temporal representations to capture evolving interaction patterns. In this paper, we show that a classical structural proximity measure can match or outperform these methods without training or learned temporal sequence modeling. We revisit Personalized PageRank (PPR) on historical interaction graphs, using simple sliding-window retention or exponential time decay. Surprisingly, across 14 datasets, Time-decay PPR ranks first on nine and second on four among the compared methods, including datasets with few repeated edges. To understand this result, we examine the historical paths connecting source nodes to previously unseen destinations. We find that such paths contain useful predictive information, and that PPR outperforms a strong neural baseline on queries where historical structure clearly distinguishes the true destination from negative candidates. These results show that strong performance on current benchmarks does not necessarily require complex temporal models. More fundamentally, they raise the question of how much predictive value learned temporal modeling adds beyond historical structural proximity. Our findings motivate reassessing progress in temporal link prediction with strong classical baselines.