mlsanityData to 7 Oct 2026

Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning

arXiv 2405.11911 ↗First posted 20 May 2024cs.AI cs.LG cs.SIcited by 5

Not on the map. Why?

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.

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

Builds on

18 of 44 references.

References · 18

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  5. 2016Variational Graph Auto-Encoderscited by 1,373
  6. 2018Link Prediction Based on Graph Neural Networkscited by 829
  7. 2017Positive-Unlabeled Learning with Non-Negative Risk Estimatorcited by 217
  8. 2021Identity-aware Graph Neural Networkscited by 197
  9. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  10. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  11. 2022Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Predictioncited by 78
  12. 2022Dist-PU: Positive-Unlabeled Learning from a Label Distribution Perspectivecited by 37
6 more
  1. 2021Variational Graph Normalized Auto-Encoderscited by 29
  2. 2022Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selectioncited by 26
  3. 2014Link Prediction in Social Networks: the State-of-the-Artcited by 22
  4. 2022Model-Agnostic Augmentation for Accurate Graph Classificationcited by 21
  5. 2022Accurate Node Feature Estimation with Structured Variational Graph Autoencodercited by 12
  6. 2023Positive-Unlabeled Node Classification with Structure-aware Graph Learningcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 1.

5 papers.

  1. 2025AugWard: Augmentation-Aware Representation Learning for Accurate Graph Classificationcited by 2
  2. 2025Enhancing Contrastive Link Prediction With Edge Balancing Augmentationcited by 0
  3. 2025FairExpand: Individual Fairness on Graphs with Partial Similarity Informationcited by 0
  4. 2025A Community-Enhanced Graph Representation Model for Link Predictioncited by 0
  5. 2026Robust Graph Clustering Network for Multiple Missing Datacited by 0