Learnable Diffusion-based Positional Encodings for Link Prediction

Link prediction relies on pairwise structural proximity, but standard node representations are not explicitly designed so that their interactions reflect such signals. Existing structure-aware approaches address this gap through specialized architectures or handcrafted proximity features, often at the expense of generality or additional computational cost. In this work, we take a data-centric approach and propose $\text{LinkDPE}$, a learnable $\underline{\text{d}}$iffusion-based $\underline{\text{p}}$ositional $\underline{\text{e}}$ncoding framework that injects structural proximity into the node features. Our key idea is that diffusion kernels, which capture multi-scale connectivity patterns, admit a factorization into node-wise embeddings whose inner products recover pairwise proximity scores. Based only on the observed training graph, $\text{LinkDPE}$ constructs diffusion-based encodings across scales, adaptively selects complementary diffusion scales, and learns task-specific spectral weightings, enabling a wide range of link predictors to exploit structural information without architectural modification. Theoretically, we show that (i) diffusion proximity admits a node-wise kernel factorization, (ii) many classical link prediction heuristics are recovered as special cases of low-order walk and diffusion operators, and (iii) multi-scale spectral responses allow the model to capture a richer set of structural similarity patterns within a shared truncated spectral basis. Across 8 benchmark datasets and 5 representative base models, $\text{LinkDPE}$ consistently improves link prediction performance over original features and positional-encoding baselines, yielding average gains of 6.97% over the unaugmented base models.