Beyond Local Neighborhoods: Fractional Diffusion with Levy Flights on Simplicial Complexes for Link Prediction

Owing to enhanced capabilities to capture a broad range of higher-order interactions, simplicial neural networks (SNNs) have emerged as a new powerful methodology for graph learning. However, prevailing SNNs are often limited in efficient exploration of heterogeneous graphs, thereby restricting the SNN utility on downstream tasks. To address this challenge, we introduce the concept of L\'{e}vy flights over simplices, offering a new efficient alternative to learning higher-order graph (sub)structures under heterogeneous scenarios. Specifically, we develop a new Fractional Hodge Laplacian Simplicial Neural Network (FHL-SNN), a novel approach leveraging fractional powers of the Hodge-Laplacian and allowing for a more efficient exploration of the underlying higher-order graph organization in conjunction with the link prediction. We establish a theoretical connection between a fractional diffusion process and graph exploration over simplices. In particular, we prove that the L\'{e}vy flight over simplices yields a lower mixing time than that of its non-fractional counterpart. Our extensive experiments on both directed and undirected link prediction tasks illuminate the power of non-local search of graph space via fractional dynamics, yielding relative gains of up to 9\%. Finally, we show that the idea of L\'{e}vy flights over simplices is versatile and that the integration of fractional dynamics to existing SNNs has the potential to further boost the model performance.