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.
The PULL Framework: Link Prediction as PU Learning
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$).
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