Research map / Graph learning / GNN architectures
Neural Common Neighbor with Completion 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.
Proposes NCN, an MPNN-then-SF link prediction architecture that pools MPNN node representations over common neighbors, and NCNC, which softly completes unobserved common-neighbor links with NCN before reapplying NCN.
Problem
Link prediction models that combine structural features with MPNNs trade off expressivity against scalability, and graph incompleteness (unobserved links in the input graph) reduces common neighbors and causes train/test distribution shifts that hurt performance.
Approach
MPNN-then-SF runs MPNN once on the original graph and uses structural features (common-neighbor sets) to guide pooling of node representations, giving SEAL-like expressivity at GAE-like cost; common neighbor completion (CNC) softly fills unobserved common-neighbor edges using NCN's predicted probabilities before a second NCN pass.
Key results
- NCNC achieves the best score on all seven benchmarks in the main table; e.g., on ogbl-ppa HR@100 of 61.42% versus 49.85% for BUDDY.
- NCN surpasses all baselines on 5 of 7 datasets and gives about 5% average improvement over BUDDY; NCNC adds roughly 2% more on average.
- NCN and NCNC have inference cost similar to GAE on ogbl-collab, while SEAL takes about 86 times more time than NCN at batch size 2048.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add common-neighbor completion to NCN | NCN · Cora | HR@100: 89.05{\scriptstyle \pm 0.96} -> 89.65{\scriptstyle \pm 1.36} | Helped |
| add common-neighbor completion to NCN | NCN · Citeseer | HR@100: 91.56{\scriptstyle \pm 1.43} -> 93.47{\scriptstyle \pm 0.95} | Helped |
| add common-neighbor completion to NCN | NCN · Pubmed | HR@100: 79.05{\scriptstyle \pm 1.16} -> 81.29{\scriptstyle \pm 0.95} | Helped |
| add common-neighbor completion to NCN | NCN · Collab | HR@50: 64.76{\scriptstyle \pm 0.87} -> 66.61{\scriptstyle \pm 0.71} | Helped |
| add common-neighbor completion to NCN | NCN · PPA | HR@100: 61.19{\scriptstyle \pm 0.85} -> 61.42{\scriptstyle \pm 0.73} | Helped |
| add common-neighbor completion to NCN | NCN · Citation2 | MRR: 88.09{\scriptstyle \pm 0.06} -> 89.12{\scriptstyle \pm 0.40} | Helped |
| add common-neighbor completion to NCN | NCN · DDI | HR@20: 82.32{\scriptstyle \pm 6.10} -> 84.11{\scriptstyle \pm 3.67} | Helped |
| add common-neighbor pairwise features to GAE (ablation) | GAE · OGB datasets | link prediction score: 70% | Helped |
| use MPNN-then-SF NCN instead of MPNN-and-SF GAE+CN (ablation) | GAE+CN · link prediction benchmarks | link prediction score: 5.5% | Helped |
| add high-order neighborhood overlap (ablation) | NCN · Cora, Citeseer, Pubmed, Collab | link prediction score: 88.87{\scriptstyle \pm 1.34}; 91.36{\scriptstyle \pm 1.02}; 80.21{\scriptstyle \pm 0.78}; 65.43{\scriptstyle \pm 0.46} | No clear effect |
| add neighborhood-difference representations (ablation) | NCN · DDI | HR@20: 82.32{\scriptstyle \pm 6.10} -> 17.67{\scriptstyle \pm 8.70} | Hurt |
Surprising findings
- Explicitly modeling higher-order neighbors (NCN2) gives marginal gains over first-order NCN once MPNN is included.
- Graph incompleteness on ogbl-collab causes a train/test distribution shift in common-neighbor counts that is absent in the complete graph, and CN test performance drops accordingly.
Limitations
- Only one instantiation of the MPNN-then-SF design space (NCN and variants) is explored.
- Only common-neighber structure is analyzed for incompleteness; other structural features are not studied.
- NCNC has higher cost on some datasets (e.g., ogbl-ppa training time 77385 s vs 9375 s for NCN) and is computationally heavier than NCN.
Experimental setup
Datasets: Cora Citeseer Pubmed ogbl-collab ogbl-ppa ogbl-citation2 ogbl-ddi
Benchmarks: Cora Citeseer Pubmed ogbl-collab ogbl-ppa ogbl-citation2 ogbl-ddi
Metrics: Hits@K MRR inference time GPU memory
Baselines: CN RA AA GCN SAGE SEAL NBFNet Neo-GNN BUDDY GAE Node2Vec DeepWalk
Builds on: Graph Autoencoder SEAL Neo-GNN BUDDY PLNLP
Closest papers by meaning
- Pure Message Passing Can Estimate Common Neighbor for Link Prediction (NeurIPS 2024 · similarity 0.90)
- OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction (NeurIPS 2025 · similarity 0.88)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.87)
- Structural Information Enhanced Graph Representation for Link Prediction (AAAI 2024 · similarity 0.86)
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.85)
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.84)
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.