Learnable Diffusion Distances for Link Prediction

In this paper, we address the problem of link prediction (LP) in Graph Neural Networks (GNNs) by learning approximated diffusion distances. Since diffusion distances have a spectral interpretation, we learn the smallest eigenvectors of the normalized Laplacian using the training edges. The resulting “empirical eigenfunctions” are reactive both to the Dirichlet loss that finds the eigenvectors and to the prediction loss. This allows us to chase the spectrum of the network in addition to provide competitive results in many LP benchmarks without precomputing subgraphs or subgraphs sketches (e.g., SEAL, WalkPooling, and ELPH/BUDDY). In addition, we provide a scalable approach for large graphs, where we do not rely on the matrix of diffusion distances.