# Edge Proposal Sets for Link Prediction

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 30 Jun 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Pseudo-Labeling and Confirmation Bias in Deep Semi-Supervised Learning](https://mlsanity.com/paper/1908.02983/) (2019)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [Community Interaction and Conflict on the Web](https://mlsanity.com/paper/1803.03697/) (2018)
- [Structural inference for uncertain networks](https://mlsanity.com/paper/1506.05490/) (2015)
- [Link-Prediction Enhanced Consensus Clustering for Complex Networks](https://mlsanity.com/paper/1506.01461/) (2015)

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

- [Modeling Dynamic Environments with Scene Graph Memory](https://mlsanity.com/paper/2305.17537/) (2023)
- [A Comprehensive Survey on Distributed Training of Graph Neural Networks](https://mlsanity.com/paper/2211.05368/) (2022)
- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)
- [Optimizing Long-tailed Link Prediction in Graph Neural Networks through Structure Representation Enhancement](https://mlsanity.com/paper/2407.20499/) (2024)
- [You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction](https://mlsanity.com/paper/2302.14189/) (2023)
- [EEGNN: Edge Enhanced Graph Neural Network with a Bayesian Nonparametric Graph Model](https://mlsanity.com/paper/2208.06322/) (2022)
- [Link Prediction without Graph Neural Networks](https://mlsanity.com/paper/2305.13656/) (2023)
- [Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methods](https://mlsanity.com/paper/2411.14711/) (2024)
- [Improving random walk rankings with feature selection and imputation](https://mlsanity.com/paper/2111.15635/) (2021)
- [Refined Edge Usage of Graph Neural Networks for Edge Prediction](https://mlsanity.com/paper/2212.12970/) (2022)
- [PROXI: Challenging the GNNs for Link Prediction](https://mlsanity.com/paper/2410.01802/) (2024)
- [Attribute-Enhanced Similarity Ranking for Sparse Link Prediction](https://mlsanity.com/paper/2412.00261/) (2024)
- [Citation network applications in a scientific co-authorship recommender system](https://mlsanity.com/paper/2111.15466/) (2021)
- [CORE: Data Augmentation for Link Prediction via Information Bottleneck](https://mlsanity.com/paper/2404.11032/) (2024)
- [Towards Understanding Link Predictor Generalizability Under Distribution Shifts](https://mlsanity.com/paper/2406.08788/) (2024)
- [Subgraph Generation for Generalizing on Out-of-Distribution Links](https://mlsanity.com/paper/2507.11710/) (2025)

## Abstract (arXiv)

Graphs are a common model for complex relational data such as social networks and protein interactions, and such data can evolve over time (e.g., new friendships) and be noisy (e.g., unmeasured interactions). Link prediction aims to predict future edges or infer missing edges in the graph, and has diverse applications in recommender systems, experimental design, and complex systems. Even though link prediction algorithms strongly depend on the set of edges in the graph, existing approaches typically do not modify the graph topology to improve performance. Here, we demonstrate how simply adding a set of edges, which we call a proposal set, to the graph as a pre-processing step can improve the performance of several link prediction algorithms. The underlying idea is that if the edges in the proposal set generally align with the structure of the graph, link prediction algorithms are further guided towards predicting the right edges; in other words, adding a proposal set of edges is a signal-boosting pre-processing step. We show how to use existing link prediction algorithms to generate effective proposal sets and evaluate this approach on various synthetic and empirical datasets. We find that proposal sets meaningfully improve the accuracy of link prediction algorithms based on both neighborhood heuristics and graph neural networks. Code is available at urlhttps://github.com/CUAI/Edge-Proposal-Sets.