Research map / Graph learning / GNN architectures
Pure Message Passing Can Estimate Common Neighbor for Link Prediction
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.
Shows that pure message passing over quasi-orthogonal random node signatures can estimate common-neighbor and higher-order structural link features, and proposes MPLP/MPLP+ link predictors that outperform GNN and link-level baselines on 15 benchmarks.
Problem
MPNNs often fail to match simple heuristics like Common Neighbor for link prediction because node-level permutation-invariant representations cannot encode joint structural features of a node pair.
Approach
Use sum-aggregation message passing over random quasi-orthogonal vectors (with one-hot hubs for variance reduction and norm rescaling) so that the inner product of two nodes' signatures unbiasedly estimates CN and distance-labelled structural counts, combined with GNN node embeddings for link classification.
Key results
- MPLP achieves Hits@50 of 92.12 on USAir and 74.28 on C.ele, outperforming the strongest baseline ELPH/SEAL on the non-attributed benchmarks.
- MPLP+ reaches MRR 90.72 on Citation2 and Hits@100 65.24 on PPA, the best reported among compared methods.
- Under the HeaRT setting, MPLP+ attains the top MRR on Collab, PPA and Citation2 (e.g., 41.40 MRR on PPA vs 33.52 for NCNC).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MPLP instead of SEAL | Link prediction · C.ele | Hits@50: 64.80 ± 4.23 -> 74.28 ± 2.09 | Helped |
| Use MPLP instead of NCNC | Link prediction · Computers | Hits@50: 36.48 ± 4.16 -> 43.47 ± 3.61 | Helped |
| Use MPLP instead of NCNC | Link prediction · Photo | Hits@50: 47.98 ± 2.36 -> 58.08 ± 3.68 | Helped |
| Use MPLP+ walk-level features instead of MPLP node-level structural features (ablation) | MPLP · USAir, NS, PB, Yeast, C.ele, Power, Router, E.coli | Hits@50 | Mixed |
| Replace original node attributes with random vectors (ablation) | GCN · Computers | Hits@50: 22.95 ± 10.58 -> 35.86 ± 3.17 | Helped |
| Replace original node attributes with random vectors (ablation) | GCN · Photo | Hits@50: 28.14 ± 7.81 -> 46.84 ± 2.53 | Helped |
| Replace original node attributes with random vectors (ablation) | GCN · CS | Hits@50: 66.00 ± 2.90 -> 51.67 ± 2.70 | Hurt |
| Replace original node attributes with random vectors (ablation) | GCN · Collab | Hits@50: 35.53 ± 2.39 -> 17.25 ± 1.15 | Hurt |
| Increase random feature dimension from 1000 to 10000 (ablation) | GCN · CS | Hits@50: 3.73 ± 1.44 -> 55.91 ± 2.63 | Helped |
| Increase random feature dimension from 1000 to 10000 (ablation) | GCN · Physics | Hits@50: 49.28 ± 2.74 -> 71.88 ± 3.29 | Helped |
| Increase random feature dimension from 1000 to 10000 (ablation) | GCN · Computers | Hits@50: 36.92 ± 3.36 -> 45.26 ± 1.94 | Helped |
| Increase random feature dimension from 1000 to 10000 (ablation) | GCN · Photo | Hits@50: 48.72 ± 3.84 -> 58.12 ± 2.54 | Helped |
Surprising findings
- Random Gaussian or {-1,1} feature vectors often perform on par with or better than original node attributes on several attributed graphs (e.g., GCN with random features beats attributes on Computers and Photo).
- MPLP cannot run on PPA-scale... Actually MPLP runs out of memory on PPA and Citation2 while only MPLP+ scales to them.
Limitations
- MPLP runs out of memory on large attributed graphs such as PPA and Citation2, so only MPLP+ scales there.
- Estimator variance from graph structure remains; hub one-hot encoding only partially mitigates it.
- Random-vector estimates are biased for GCN-style normalization and sensitive to hub selection hyperparameters.
Experimental setup
Datasets: USAir NS PB Yeast C.ele Power Router E.coli CS Physics Computers Photo
Benchmarks: USAir NS PB Yeast C.ele Power Router E.coli CS Physics Computers Photo
Metrics: Hits@50 Hits@100 MRR Hits@20 MSE
Baselines: CN AA RA GCN SAGE SEAL Neo-GNN ELPH NCNC BUDDY
Builds on: DotHash ELPH SEAL Distance Encoding Neo-GNN
Closest papers by meaning
- Structural Information Enhanced Graph Representation for Link Prediction (AAAI 2024 · similarity 0.90)
- Neural Common Neighbor with Completion for Link Prediction (ICLR 2024 · similarity 0.90)
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.89)
- OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction (NeurIPS 2025 · similarity 0.89)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.87)
- Open Your Eyes: Vision Enhances Message Passing Neural Networks in Link Prediction (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.