cs.LGJul 9, 2025

GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction

Authors: Francesco Ferrini, Veronica Lachi, Antonio Longa, Bruno Lepri, Andrea Passerini

Abstract

Graph Neural Networks (GNNs) often struggle to capture the link-specific structural patterns crucial for accurate link prediction, as their node-centric message-passing schemes overlook the subgraph structures connecting a pair of nodes. Existing methods to inject such structural context either incur high computational cost or rely on simplistic heuristics (e.g., common neighbor counts) that fail to model multi-hop dependencies. We introduce SP4LP (Shortest Path for Link Prediction), a novel framework that combines GNN-based node encodings with sequence modeling over shortest paths. Specifically, SP4LP first applies a GNN to compute representations for all nodes, then extracts the shortest path between each candidate node pair and processes the resulting sequence of node embeddings using a sequence model. This design enables SP4LP to capture expressive multi-hop relational patterns with computational efficiency. Empirically, SP4LP achieves state-of-the-art performance across link prediction benchmarks. Theoretically, we prove that SP4LP is strictly more expressive than standard message-passing GNNs and several state-of-the-art structural features methods, establishing it as a general and principled approach for link prediction in graphs.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. From Link Prediction to Linear Community Detection: A Finite-Sample Guarantee for Graph Pretraining

    Nov 11, 2026Ying Chen, Zhangyang Wang, Yixuan HeGraph Representation LearningGraph Neural Networks

  2. Link prediction on multi-relational graphs from an influence propagation perspective

    Aug 5, 2026Zidu Yin, Yuankai Qi, Dong Gong +3Graph Neural NetworksLink Prediction

  3. Leveraging Graph Structure in Seq2Seq Models for Knowledge Graph Link Prediction

    May 18, 2026Luu Huu Phuc, Ratan Bahadur Thapa, Mojtaba Nayyeri +3Sequence ModelingKG Completion