GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction
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
| Models | Cora | Citeseer | Pubmed | Ogbl-ddi | Ogbl-collab | Ogbl-ppa | Ogbl-citation2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| MRR | H@10 | MRR | H@10 | MRR | H@10 | MRR | H@20 | MRR | H@20 | MRR | H@20 | MRR | H@20 | ||
| GNN | GCN | 16.61 | 36.26 | 21.09 | 47.23 | 7.13 | 15.22 | 13.46 | 64.76 | 6.09 | 22.48 | 26.94 | 68.38 | 19.98 | 51.72 |
| GAT | 13.84 | 32.89 | 19.58 | 45.30 | 4.95 | 9.99 | 12.92 | 66.83 | 4.18 | 18.30 | OOM | OOM | OOM | OOM | |
| SAGE | 14.74 | 34.65 | 21.09 | 48.75 | 9.40 | 20.54 | 12.60 | 67.19 | 5.53 | 21.26 | 27.27 | 69.49 | 22.05 | 53.13 | |
| GAE | 18.32 | 37.95 | 25.25 | 49.65 | 5.27 | 10.50 | 3.49 | 17.81 | OOM | OOM | OOM | OOM | OOM | OOM | |
| GT | LPFORMER | 16.80 | 34.03 | 26.34 | 51.72 | 9.99 | 21.43 | 13.20 | 62.66 | 7.62 | 21.04 | 40.25 | 84.10 | 24.70 | 57.30 |
| Models | Cora | Citeseer | Pubmed | |||
|---|---|---|---|---|---|---|
| MRR | H@10 | MRR | H@10 | MRR | H@10 | |
| GNN + SP | 8.32 | 20.02 | 21.13 | 45.05 | 8.52 | 15.32 |
| Seq. Model | 16.86 | 36.03 | 10.93 | 19.23 | 7.12 | 13.56 |
| SP4LP | 28.84 | 45.39 | 29.48 | 49.52 | 10.87 | 23.01 |
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| Models | Cora | Citeseer | Pubmed | Ogbl-ddi | Ogbl-collab | Ogbl-ppa | Ogbl-Citation2 | |
|---|---|---|---|---|---|---|---|---|
| MRR | MRR | MRR | MRR | MRR | MRR | MRR | ||
| GNN | GCN | 16.61 ( 0.30) | 21.09 ( 0.88) | 7.13 ( 0.27) | 13.46 ( 0.34) | 6.09 ( 0.38) | 26.94 ( 0.48) | 19.98 ( 0.35) |
| GAT | 13.84 ( 0.68) | 19.58 ( 0.84) | 4.95 ( 0.14) | 12.92 ( 0.39) | 4.18 ( 0.33) | OOM | OOM | |
| SAGE | 14.74 ( 0.69) | 21.09 ( 1.15) | 9.40 ( 0.70) | 12.60 ( 0.72) | 5.53 ( 0.50) | 27.27 ( 0.30) | 22.05 ( 0.12) | |
| GAE | 18.32 ( 0.41) | 25.25 ( 0.82) | 5.27 ( 0.25) | 3.49 ( 1.73) | OOM | OOM | OOM | |
| GT | LPFORMER | 16.80 ( 0.52) | 26.34 ( 0.67) | 9.99 ( 0.52) | 13.20 ( 0.54) | 7.62 ( 0.26) | 40.25 ( 0.24) | 24.70 ( 0.55) |
| Models | Cora | Citeseer | Pubmed | Ogbl-ddi | Ogbl-collab | Ogbl-ppa | Ogbl-Citation2 | |
|---|---|---|---|---|---|---|---|---|
| Hits@10 | Hits@10 | Hits@10 | Hits@20 | Hits@20 | Hits@20 | Hits@20 | ||
| GNN | GCN | 36.26 ( 1.14) | 47.23 ( 1.88) | 15.22 ( 0.57) | 64.76 ( 1.45) | 22.48 ( 0.81) | 68.38 ( 0.73) | 51.72 ( 0.46) |
| GAT | 32.89 ( 1.27) | 45.30 ( 1.30) | 9.99 ( 0.64) | 66.83 ( 2.23) | 18.30 ( 1.42) | OOM | OOM | |
| SAGE | 34.65 ( 1.47) | 48.75 ( 1.85) | 20.54 ( 1.40) | 67.19 ( 1.18) | 21.26 ( 1.32) | 69.49 ( 0.43) | 53.13 ( 0.15) | |
| GAE | 37.95 ( 1.24) | 49.65 ( 1.48) | 10.50 ( 0.46) | 17.81 ( 9.80) | OOM | OOM | OOM | |
| GT | LPFORMER | 34.03 ( 1.33) | 51.72 ( 1.83) | 21.43 ( 1.30) | 62.66 ( 0.37) | 21.04 ( 0.16) | 84.10 ( 0.10) | 57.30 ( 0.50) |
| Models | Cora | Citeseer | Pubmed | |||
|---|---|---|---|---|---|---|
| MRR | Hits@10 | MRR | Hits@10 | MRR | Hits@10 | |
| GNN + SP len. | 8.32 ( 0.28) | 20.02 ( 0.67) | 21.13 ( 0.99) | 45.05 ( 1.24) | 8.52 ( 0.01) | 15.32 ( 0.66) |
| Sequence Model | 16.86 ( 1.26) | 36.03 ( 1.75) | 10.93 ( 2.93) | 19.23 ( 4.20) | 7.12 ( 0.75) | 13.56 ( 0.85) |
| SP4LP | 28.84 ( 5.45) | 45.39 ( 9.58) | 29.48 ( 10.17) | 49.52 ( 9.77) | 10.87 ( 0.31) | 23.01 ( 0.39) |
| Maximum hops | MRR (%) | Hits@10 (%) | Preprocessing (s) |
|---|---|---|---|
| 2 | 7.00 | 14.98 | 1 |
| 5 | 7.59 | 16.34 | 150 |
| 7 | 9.16 | 18.21 | 320 |
| Full | 10.87 | 23.01 | 570 |
| Dataset | GCN MRR | SP4LP MRR | MRR | |
|---|---|---|---|---|
| Cora | 0.127 | 16.61 | 28.84 | +12.23 |
| Citeseer | 0.372 | 21.09 | 29.48 | +8.39 |
| Pubmed | 0.341 | 7.13 | 10.87 | +3.74 |
| Dataset | Cora | Citeseer | Pubmed | ogbl-collab | ogbl-ddi | ogbl-ppa | ogbl-citation2 |
|---|---|---|---|---|---|---|---|
| #Nodes | 2708 | 3327 | 18717 | 235868 | 4267 | 576289 | 2927963 |
| #Edges | 5278 | 4676 | 44327 | 1285465 | 1334889 | 30326273 | 30561187 |
| Dataset | Split | Queries | Total | No path | No path (%) | Mean | Variance |
|---|---|---|---|---|---|---|---|
| Cora | Train † | Pos. | 263 | 35 | 13.31 | 3.00 | 2.13 |
| Train † | Neg. | 131500 | 30077 | 22.87 | 6.87 | 5.14 | |
| Val. | Pos. | 263 | 41 | 15.59 | 3.09 | 2.71 | |
| Val. | Neg. | 131500 | 18828 | 14.32 | 5.48 | 5.33 | |
| Test | Pos. | 527 | 77 | 14.61 | 3.15 | 2.74 | |
| Test | Neg. | 263500 | 36857 | 13.99 | 5.48 | 5.20 |
| Parameter | Cora | Citeseer | Pubmed | ogbl-collab | ogbl-ddi | ogbl-ppa | ogbl-citation2 |
|---|---|---|---|---|---|---|---|
| GNN | GCN | GCN | SAGE | SAGE | GCN | GCN | GCN |
| Learning rate | 0.001 | 0.01 | 0.001 | 0.001 | 0.01 | 0.001 | 0.01 |
| Dropout | 0.5 | 0.5 | 0.1 | 0 | 0 | 0.3 | 0.3 |
| Weight decay | 0 | 0 | 0 | 0 | 0 | 0 | |
| GNN layers | 1 | 1 | 2 | 3 | 3 | 3 | 3 |
| GNN hidden dimension | 128 | 128 | 128 | 256 | 256 | 256 | 128 |
| Method | B | C |
|---|---|---|
| GAE | ||
| Neo-GNN | ||
| BUDDY | ||
| SEAL | ||
| NCN | ||
| NCNC |
Link Prediction
Link prediction estimates missing or future relationships in graphs, from social ties and knowledge-graph facts to biological interactions.
See all 51 papers