Research map / Graph learning / GNN architectures

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

NeurIPS 2026 · Graph learning › GNN architectures · approach: Subgraph and distance-aware GNNs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SP4LP, which runs a GNN once over the graph and then feeds the node embeddings along each pair's shortest path into a sequence model to get expressive, efficient link representations.

Problem

Pure GNNs assign identical representations to non-automorphic links whose endpoints are automorphic, and existing structural-feature methods are either costly (per-link subgraph extraction) or limited to heuristics such as common neighbors.

Approach

Combine GNN node embeddings with a sequence model (LSTM, Transformer, or injective sum) applied to the node embeddings along the shortest path between the two endpoints, computed as a preprocessing step, so that link representations capture multi-hop structure while message passing runs only once.

Key results

• SP4LP reports MRR of 41.08 on Citeseer versus 28.65 for the second-best method NCN under the HeaRT protocol.
• SP4LP ranks first in MRR on four of five datasets and reports MRR of 9.46 on ogbl-collab and 10.87 on Pubmed.
• On ogbl-ddi, SP4LP reaches MRR 15.00 and is weaker on Hits@20 (47.96) than GAT, SAGE and NCN; the authors attribute this to the lack of node features.

Surprising findings

• On ogbl-ddi, which has no node features, SP4LP underperforms several baselines on Hits@20, which the authors attribute to missing features.

Limitations

• Expressiveness advantage depends on shortest paths existing, so disconnected graphs may reduce it.
• Uses only one shortest path per pair (first returned by BFS/networkx) as the aggregation, which discards other shortest paths.
• Weaker on featureless ogbl-ddi, where node embeddings carry less information.

Experimental setup

Datasets: Cora Citeseer Pubmed ogbl-collab ogbl-ddi

Benchmarks: Cora Citeseer Pubmed ogbl-collab ogbl-ddi

Metrics: MRR Hits@10 Hits@20

Baselines: CN AA RA Katz Node2Vec MF MLP GCN GAT GraphSAGE GAE SEAL

Builds on: NCN NCNC SEAL NBFNet BUDDY

Closest papers by meaning

• Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.90)
• A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.90)
• Structural Information Enhanced Graph Representation for Link Prediction (AAAI 2024 · similarity 0.90)
• Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.89)
• Pure Message Passing Can Estimate Common Neighbor for Link Prediction (NeurIPS 2024 · similarity 0.89)
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2024 · similarity 0.88)