Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning

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

Introduction: The Challenge of Edge-Incompleteness

In real-world scenarios, graphs are rarely complete. Social networks contain pairs of individuals who are friends in reality but haven't yet connected online; citation networks often miss relevant links between papers. These are known as edge-incomplete graphs.

Traditional link prediction models typically treat observed edges as positive examples and all unconnected node pairs as negative examples. This approach introduces a significant bias: the model is forced to learn that missing links are inherently "wrong," even when they are simply unobserved. This "false negative" trap restricts the model's ability to propagate information through potential paths, leading to degraded performance in highly incomplete graphs.

To address these limitations, the authors propose PULL (PU-Learning-based Link Predictor). PULL reframes link prediction as a Positive-Unlabeled (PU) learning problem. Instead of a binary "edge vs. no-edge" classification, PULL treats observed edges as Positive ($P$) and all other pairs as Unlabeled ($U$).

Overview of the PULL framework addressing the challenge of edge-incomplete graphs by treating unobserved edges as unlabeled examples.

The PULL framework consists of several key components:

  • Latent Variables for Edges: Every unconnected pair is assigned a latent variable representing the probability that a hidden link exists.
  • The Expected Graph: Rather than training on a sparse, incomplete graph, PULL constructs an "expected graph" ($\bar{G}$). This graph uses current model predictions to weight potential edges, allowing information to flow through "likely" missing links during training.
  • Iterative Refinement: The process follows an EM-like iterative approach. The model predicts link probabilities, updates the expected graph based on these probabilities, and then retrains the link predictor on the refined structure.
  • Dual Loss Function: To ensure stability, PULL employs two loss terms: $L_E$ (Binary Cross-Entropy), which treats high-confidence unlabeled pairs as pseudo-positives, and $L_C$ (Correction Loss), which prevents the model from "hallucinating" excessive edges by anchoring it to the original observed structure.
  • Efficiency and Scalability: To avoid the $O(N^2)$ complexity of calculating probabilities for all possible pairs, PULL utilizes a candidate selection strategy based on node degrees, focusing on nodes more likely to form links.

Experimental Evaluation and Key Results

The researchers evaluated PULL across seven diverse real-world datasets, including citation networks (PubMed, Cora-full), Wikipedia hyperlink networks (Chameleon, Crocodile), and social networks (Facebook). To simulate edge-incompleteness, these datasets were "thinned" by removing 10-20% of existing edges.

  • Superior Accuracy: PULL consistently outperformed state-of-the-art baselines, including GCN, GAT, and VGAE. In several instances, it improved AUROC and AUPRC by multiple percentage points.
  • Robustness to Sparsity: The performance advantage of PULL became more pronounced as graph incompleteness increased, demonstrating its effectiveness in data-starved scenarios.
  • Scalability: Despite its iterative nature, PULL maintains linear time complexity relative to the number of nodes and edges, making it suitable for large-scale networks.
  • Flexibility: The PULL logic can be integrated into other GNN architectures (e.g., GAE or VGNAE) to enhance their predictive capabilities.

Insights and Future Directions

The core insight of PULL is that "unconnected" signifies uncertainty rather than a definitive negative label. By allowing information to propagate via uncertainty—passing messages through potential edges weighted by probability—the model learns superior node embeddings in sparse regions. The introduction of the Correction Loss ($L_C$) is also vital, acting as a guardrail to prevent the model from drifting too far from reality during iterative updates.

While highly effective, PULL currently faces challenges in mapping its "expected graph" weights to complex attention mechanisms like GAT or neighborhood sampling methods like GraphSAGE. Future research may explore extending PULL to directed or heterogeneous graphs, further broadening its applicability in complex 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 for link prediction 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 prediction), 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{kim2025accurate,
  author = {Junghun Kim and Ka Hyun Park and Hoyoung Yoon and U Kang},
  title = {{Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i17.33966},
}
Figure