# Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 20 May 2024.

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

- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [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)
- [Dist-PU: Positive-Unlabeled Learning from a Label Distribution Perspective](https://mlsanity.com/paper/2212.02801/) (2022)
- [Variational Graph Normalized Auto-Encoders](https://mlsanity.com/paper/2108.08046/) (2021)
- [Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection](https://mlsanity.com/paper/2212.12488/) (2022)
- [Link Prediction in Social Networks: the State-of-the-Art](https://mlsanity.com/paper/1411.5118/) (2014)
- [Model-Agnostic Augmentation for Accurate Graph Classification](https://mlsanity.com/paper/2202.10107/) (2022)
- [Accurate Node Feature Estimation with Structured Variational Graph Autoencoder](https://mlsanity.com/paper/2206.04516/) (2022)
- [Positive-Unlabeled Node Classification with Structure-aware Graph Learning](https://mlsanity.com/paper/2310.13538/) (2023)

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

- [AugWard: Augmentation-Aware Representation Learning for Accurate Graph Classification](https://mlsanity.com/paper/2503.21105/) (2025)
- [Enhancing Contrastive Link Prediction With Edge Balancing Augmentation](https://mlsanity.com/paper/2508.14808/) (2025)
- [FairExpand: Individual Fairness on Graphs with Partial Similarity Information](https://mlsanity.com/paper/2512.18180/) (2025)
- [A Community-Enhanced Graph Representation Model for Link Prediction](https://mlsanity.com/paper/2512.21166/) (2025)
- [Robust Graph Clustering Network for Multiple Missing Data](https://mlsanity.com/paper/2609.31033/) (2026)

## Abstract (arXiv)

Given an edge-incomplete graph, how can we accurately find the missing links? The link prediction in edge-incomplete graphs aims to discover the missing relations between entities when their relationships are represented as a graph. Edge-incomplete graphs are prevalent in real-world due to practical limitations, such as not checking all users when adding friends in a social network. Addressing the problem is crucial for various tasks, including recommending friends in social networks and finding references in citation networks. However, previous approaches rely heavily on the given edge-incomplete (observed) graph, making it challenging to consider the missing (unobserved) links during training. In this paper, we propose PULL (PU-Learning-based Link predictor), an accurate link prediction method based on the positive-unlabeled (PU) learning. PULL treats the observed edges in the training graph as positive examples, and the unconnected node pairs as unlabeled ones. PULL effectively prevents the link predictor from overfitting to the observed graph by proposing latent variables for every edge, and leveraging the expected graph structure with respect to the variables. Extensive experiments on five real-world datasets show that PULL consistently outperforms the baselines for predicting links in edge-incomplete graphs.