# Neural Common Neighbor with Completion for Link Prediction

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 35 references that are in the map.
- First posted on arXiv 2 Feb 2023.

## Builds on (most cited first, 26 of 26)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [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)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [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)
- [Pairwise Learning for Neural Link Prediction](https://mlsanity.com/paper/2112.02936/) (2021)
- [Self-Supervised Graph Structure Refinement for Graph Neural Networks](https://mlsanity.com/paper/2211.06545/) (2022)
- [Rethinking Knowledge Graph Evaluation Under the Open-World Assumption](https://mlsanity.com/paper/2209.08858/) (2022)
- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)
- [GIDN: A Lightweight Graph Inception Diffusion Network for High-efficient Link Prediction](https://mlsanity.com/paper/2210.01301/) (2022)

## Built on by (most cited first, 30 of 64)

- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Pure Message Passing Can Estimate Common Neighbor for Link Prediction](https://mlsanity.com/paper/2309.00976/) (2023)
- [Efficient Neural Common Neighbor for Temporal Graph Link Prediction](https://mlsanity.com/paper/2406.07926/) (2024)
- [LPFormer: An Adaptive Graph Transformer for Link Prediction](https://mlsanity.com/paper/2310.11009/) (2023)
- [PageRank Bandits for Link Prediction](https://mlsanity.com/paper/2411.01410/) (2024)
- [Universal Link Predictor By In-Context Learning on Graphs](https://mlsanity.com/paper/2402.07738/) (2024)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [4DBInfer: A 4D Benchmarking Toolbox for Graph-Centric Predictive Modeling on Relational DBs](https://mlsanity.com/paper/2404.18209/) (2024)
- [Mixture of Link Predictors on Graphs](https://mlsanity.com/paper/2402.08583/) (2024)
- [Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning](https://mlsanity.com/paper/2405.16435/) (2024)
- [On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks](https://mlsanity.com/paper/2409.17475/) (2024)
- [TAGLAS: An atlas of text-attributed graph datasets in the era of large graph and language models](https://mlsanity.com/paper/2406.14683/) (2024)
- [Optimizing Long-tailed Link Prediction in Graph Neural Networks through Structure Representation Enhancement](https://mlsanity.com/paper/2407.20499/) (2024)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [TFMLinker: Universal Link Predictor by Graph In-Context Learning with Tabular Foundation Models](https://mlsanity.com/paper/2602.08592/) (2026)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [A Pure Transformer Pretraining Framework on Text-attributed Graphs](https://mlsanity.com/paper/2406.13873/) (2024)
- [Learning Scalable Structural Representations for Link Prediction with Bloom Signatures](https://mlsanity.com/paper/2312.16784/) (2023)
- [Temporal Graph Rewiring with Expander Graphs](https://mlsanity.com/paper/2406.02362/) (2024)
- [Reconsidering the Performance of GAE in Link Prediction](https://mlsanity.com/paper/2411.03845/) (2024)
- [Unlearning Inversion Attacks for Graph Neural Networks](https://mlsanity.com/paper/2506.00808/) (2025)
- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)
- [Prior-Informed Flow Matching for Graph Reconstruction](https://mlsanity.com/paper/2601.22107/) (2026)
- [Stochastic Subgraph Neighborhood Pooling for Subgraph Classification](https://mlsanity.com/paper/2304.08556/) (2023)
- [Link Prediction with Untrained Message Passing Layers](https://mlsanity.com/paper/2406.16687/) (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)
- [Open Your Eyes: Vision Enhances Message Passing Neural Networks in Link Prediction](https://mlsanity.com/paper/2505.08266/) (2025)

## Abstract (arXiv)

In this work, we propose a novel link prediction model and further boost it by studying graph incompleteness. First, we introduce MPNN-then-SF, an innovative architecture leveraging structural feature (SF) to guide MPNN's representation pooling, with its implementation, namely Neural Common Neighbor (NCN). NCN exhibits superior expressiveness and scalability compared with existing models, which can be classified into two categories: SF-then-MPNN, augmenting MPNN's input with SF, and SF-and-MPNN, decoupling SF and MPNN. Second, we investigate the impact of graph incompleteness -- the phenomenon that some links are unobserved in the input graph -- on SF, like the common neighbor. Through dataset visualization, we observe that incompleteness reduces common neighbors and induces distribution shifts, significantly affecting model performance. To address this issue, we propose to use a link prediction model to complete the common neighbor structure. Combining this method with NCN, we propose Neural Common Neighbor with Completion (NCNC). NCN and NCNC outperform recent strong baselines by large margins, and NCNC further surpasses state-of-the-art models in standard link prediction benchmarks. Our code is available at https://github.com/GraphPKU/NeuralCommonNeighbor.