# Pure Message Passing Can Estimate Common Neighbor for Link Prediction

arXiv: https://arxiv.org/abs/2309.00976 · HTML: https://mlsanity.com/paper/2309.00976/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 55 references that are in the map.
- First posted on arXiv 2 Sep 2023.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Shortest Path Networks for Graph Property Prediction](https://mlsanity.com/paper/2206.01003/) (2022)
- [Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2202.13538/) (2022)
- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)
- [Revisiting Embeddings for Graph Neural Networks](https://mlsanity.com/paper/2209.09338/) (2022)
- [DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication](https://mlsanity.com/paper/2305.17310/) (2023)

## Built on by (most cited first, 18 of 18)

- [GraphGPT: Generative Pre-trained Graph Eulerian Transformer](https://mlsanity.com/paper/2401.00529/) (2023)
- [Universal Link Predictor By In-Context Learning on Graphs](https://mlsanity.com/paper/2402.07738/) (2024)
- [TFMLinker: Universal Link Predictor by Graph In-Context Learning with Tabular Foundation Models](https://mlsanity.com/paper/2602.08592/) (2026)
- [Reconsidering the Performance of GAE in Link Prediction](https://mlsanity.com/paper/2411.03845/) (2024)
- [Link Prediction with Untrained Message Passing Layers](https://mlsanity.com/paper/2406.16687/) (2024)
- [You do not have to train Graph Neural Networks at all on text-attributed graphs](https://mlsanity.com/paper/2404.11019/) (2024)
- [PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction](https://mlsanity.com/paper/2404.15225/) (2024)
- [Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach](https://mlsanity.com/paper/2501.11823/) (2025)
- [Using Random Noise Equivariantly to Boost Graph Neural Networks Universally](https://mlsanity.com/paper/2502.02479/) (2025)
- [GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning](https://mlsanity.com/paper/2510.04567/) (2025)
- [Deep Graph Learning will stall without Network Science](https://mlsanity.com/paper/2502.01177/) (2025)
- [OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction](https://mlsanity.com/paper/2505.19719/) (2025)
- [Optimal Transport-Guided Adversarial Attacks on Graph Neural Network-Based Bot Detection](https://mlsanity.com/paper/2602.00318/) (2026)
- [Heuristic Methods are Good Teachers to Distill MLPs for Graph Link Prediction](https://mlsanity.com/paper/2504.06193/) (2025)
- [A Community-Enhanced Graph Representation Model for Link Prediction](https://mlsanity.com/paper/2512.21166/) (2025)
- [Plain Transformers are Surprisingly Powerful Link Predictors](https://mlsanity.com/paper/2602.01553/) (2026)
- [Instance Discrimination for Link Prediction](https://mlsanity.com/paper/2605.20257/) (2026)
- [Neural Message Passing on Structural Interaction Graphs for Fully-Inductive Graph Neural Networks](https://mlsanity.com/paper/2608.08567/) (2026)

## Abstract (arXiv)

Message Passing Neural Networks (MPNNs) have emerged as the em de facto standard in graph representation learning. However, when it comes to link prediction, they often struggle, surpassed by simple heuristics such as Common Neighbor (CN). This discrepancy stems from a fundamental limitation: while MPNNs excel in node-level representation, they stumble with encoding the joint structural features essential to link prediction, like CN. To bridge this gap, we posit that, by harnessing the orthogonality of input vectors, pure message-passing can indeed capture joint structural features. Specifically, we study the proficiency of MPNNs in approximating CN heuristics. Based on our findings, we introduce the Message Passing Link Predictor (MPLP), a novel link prediction model. MPLP taps into quasi-orthogonal vectors to estimate link-level structural features, all while preserving the node-level complexities. Moreover, our approach demonstrates that leveraging message-passing to capture structural features could offset MPNNs' expressiveness limitations at the expense of estimation variance. We conduct experiments on benchmark datasets from various domains, where our method consistently outperforms the baseline methods.