Dyn-βRW: Dynamic β-Random Walk for link prediction

Abstract

Graph embedding represents nodes in a continuous, low-dimensional latent space while preserving the graph’sunderlying structure. In practice, however, most real-world graphs are far from static — nodes and edges appear, vanish,and shift in weight as time passes. Despite this, a large portion of the embedding literature is built around the static setting,leaving the temporal dimension as an afterthought or ignoring it entirely.We propose Dyn-βRW-GNN, a dynamic graph embedding framework that couples β-Random Walks with a GraphSAGEbased encoder. Rather than folding time into a single monolithic pipeline, the architecture keeps two concerns cleanlyseparate: the β-Random Walk module handles temporal exploration, producing temporally-aware node embeddings thatreflect how each node’s neighborhood evolves over time; a subsequent multi-layer GraphSAGE encoder then refines theseinto richer structural representations. A lightweight MLP decoder operates on candidate node pairs to produce a linkprediction score, completing the pipeline.We separate these tasks on purpose. Mixing temporal exploration with representation learning often leads to poor results forboth. By giving each task its own stage, the model can better capture detailed structural patterns and long-term temporalchanges without the two goals interfering with each other. Experiments on dynamic graph benchmarks show consistentimprovements over competitive baselines on the link prediction task, confirming that explicit temporal exploration is aworthwhile inductive bias when the graph itself is moving.