PULL: PU-Learning-based Accurate Link Prediction

Junghun Kim, Ka Hyun Park, Hoyoung Yoon, U Kang

Abstract

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.

Introduction: The Challenge of Edge-Incompleteness

In the real world, graphs are rarely perfect. Whether it’s a social network where users haven't found all their potential friends or a citation network missing recent references, we are almost always working with edge-incomplete graphs.

The standard approach to link prediction is to treat observed edges as positive examples and all unconnected node pairs as negative examples. This creates a fundamental "misconception": the model is forced to learn that a missing edge is a "true negative," even if that edge is just a "missing positive." This bias prevents models from propagating information through potential hidden paths, leading to over-reliance on a flawed, incomplete structure and ultimately degrading prediction accuracy.

Methods: The PULL Framework

The authors introduce PULL (PU-Learning-based Link Predictor), which shifts the paradigm from standard binary classification to Positive-Unlabeled (PU) learning.

  1. PU Learning Framework: Instead of Positive vs. Negative, PULL treats observed edges as Positive and all unconnected pairs as Unlabeled.
  2. The Expected Graph ($\bar{G}$): PULL proposes latent variables for every unconnected node pair. It constructs an "expected graph" where edge weights represent the probability of a link existing. This allows the model to "see" and propagate information through likely hidden connections.
  3. Iterative Refinement: The process is a two-step loop where the link predictor estimates probabilities to update the expected graph, which in turn is used to further train the predictor.
The iterative pipeline of PULL, showing the update loop between the expected graph and the link predictor.
  1. Dual Loss Function: To prevent the model from "hallucinating" edges and then reinforcing its own mistakes (self-reinforcement), PULL uses two losses: $L_E$ (training on expected weights) and $L_C$ (Correction Loss against the original graph).
  2. Scalability: PULL uses a "candidate edge set" based on high-degree nodes, keeping the computation linear and scalable to large networks like ogbn-arxiv.

Key Insights

  • Stop the "Negative" Bias: Treating missing links as "unknown" rather than "zero" gives the model flexibility to discover the underlying structure.
  • Information Propagation: By using a weighted "expected graph," PULL allows information to flow through "ghost" edges, improving node embeddings.
  • Theoretical Grounding: The iterative approach is mathematically proven to be a form of the Expectation-Maximization (EM) algorithm, providing a rigorous statistical foundation.
  • The Danger of Self-Reinforcement: The inclusion of the $L_C$ loss is a vital insight. Without it, the model's accuracy can drop sharply once it starts adding more edges than actually exist in the ground truth.

Experimental Results

PULL was evaluated on several real-world datasets, including PubMed, Cora-full, and Facebook, with simulated incompleteness (10-20% missing edges).

Experimental results showing PULL consistently outperforming baselines in AUROC and AUPRC across multiple datasets.

PULL consistently achieved the highest AUROC and AUPRC scores across all tested datasets. For instance, on the "Crocodile" dataset with 10% missing edges, PULL reached an AUROC of 98.31, significantly higher than standard GCN+CE (96.91) or VGAE (95.29). Furthermore, PULL acts as a "plug-and-play" framework, improving existing models like GAE or VGNAE when integrated.

Limitations and Future Work

While PULL works excellently with GCN-based schemes, it is currently harder to apply directly to models with complex attention mechanisms (like GAT) because the expected graph propagation is optimized for standard GCN layers. Future work could explore more sophisticated candidate selection methods to further improve accuracy in highly sparse networks and reduce sensitivity to the "increase ratio" hyperparameter.

Conclusion

PULL addresses the inherent bias in link prediction for edge-incomplete graphs by leveraging PU-learning and an iterative expected graph approach. Its ability to propagate information through unobserved but likely edges, combined with a grounding correction loss, makes it a robust and accurate solution for real-world network analysis.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kim2025pull,
  author = {Junghun Kim and Ka Hyun Park and Hoyoung Yoon and U Kang},
  title = {{PULL: PU-Learning-based Accurate Link Prediction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i17.33966},
}
Figure