TL;DR
Standard graph neural networks for link prediction assume non-edges are true negatives, leading them to overfit to edge-incomplete graphs and miss latent relationships. PULL (PU-Learning-based Link Predictor) reframes link prediction as Positive-Unlabeled (PU) learning: it treats observed edges as positive and non-edges as unlabeled, iteratively inferring an expected graph structure over latent variables to propagate information and refine predictions.
What Problem Does This Paper Address?
In real-world graphs—such as social networks or citation graphs—absence of an edge rarely guarantees absence of a relationship; users simply haven't connected yet, or authors haven't cited relevant papers.
Most link prediction frameworks (e.g., GAE, VGAE, standard GCN classifiers) overlook this reality. By treating missing links as true non-edges (negatives) during training, models:
- Overfit to the observed, incomplete topology.
- Cannot propagate messages across missing links during message passing, bottlenecking representation quality.
The core challenge is estimating the true underlying graph structure without blowing up computation, given that an unlabeled edge set $E_U$ yields $2^{|E_U|}$ possible graph configurations.
Methods
PULL tackles this problem through a theoretically grounded iterative framework:
- Latent Edge Formulation: Every edge $e_{ij}$ is assigned a binary latent variable $z_{ij} \in \{0, 1\}$. For observed edges ($E_P$), $z_{ij} = 1$; for unconnected pairs ($E_U$), $z_{ij}$ is unknown.
- Tractable Expected Adjacency via Line Graphs: To make expectation over $2^{|E_U|}$ states tractable, the authors model the line graph of potential edges as a pairwise Markov random field. Marginalizing edge potentials yields the expected adjacency matrix $\bar{A}_{ij} = \phi_{ij}(z_{ij}=1 \mid \theta) = \text{sigmoid}(h_i^\top h_j)$.
- Top-$K$ Sparse Approximation: Directly propagating on the fully connected expected graph $\bar{G}$ causes oversmoothing and computational bloat. PULL retains only the top-$K$ edges with the highest predicted probabilities, linearly expanding $K \leftarrow K + r|E_P|$ across iterations as model confidence improves.
- Two-Loss Training Objective:
- $\mathcal{L}'_E$: A PU cross-entropy loss utilizing the predicted probabilities of top-$K$ edges as soft pseudo-labels.
- $\mathcal{L}_C$: A correction loss comparing observed edges against randomly sampled unconnected pairs, which counters model drift and runaway self-reinforcement (confirmation bias).
- EM Connection: The authors prove that iteratively optimizing $\mathcal{L}_E$ mathematically mirrors maximizing the expected log-likelihood $Q(\theta^{\text{new}} \mid \theta)$ in the Expectation-Maximization (EM) algorithm.
Datasets
The authors evaluate PULL on seven standard graph benchmarks:
- Citation Networks: PubMed, Cora-full, ogbn-arxiv, and Physics (co-authorship/citation).
- Wikipedia Hyperlink Networks: Chameleon and Crocodile.
- Social Network: Facebook (user-follower relations).
No new datasets were introduced; missing edge ratios were simulated at $r_m \in \{0.1, 0.2\}$.
Key Insights and Ideas
- Message Passing on Inferred Topology: Instead of fixing the input graph during GNN aggregation, updating the message-passing graph with high-confidence latent edges allows features to diffuse through likely missing paths, boosting embedding quality.
- EM-Style Self-Correction: Framing pseudo-labeling under the EM lens provides theoretical backing for why iterative retraining with expected adjacency works without collapsing.
- Balancing Noise vs. Oversmoothing: Expanding $K$ gradually prevents the model from hallucinating noisy edges early on, while stopping near the ground-truth edge count prevents the oversmoothing typical of dense graphs.
Key Results
- Consistently Superior Accuracy: Across all datasets and missing edge ratios (10% and 20%), PULL consistently outperforms baselines—including GCN/GAT/GraphSAGE with cross-entropy, autoencoder variants (GAE, VGAE, ARGA, ARGVA, GNAE, VGNAE), and Bagging-PU.
- Large Graph Gains: On
ogbn-arxiv($r_m = 0.1$), PULL achieves 85.9% AUROC / 88.1% AUPRC, outperforming the best baseline (GAE at 80.4% / 85.1%). OnPhysics, PULL reaches 97.1% AUROC. - Plug-and-Play Compatibility: Integrating PULL's expected-graph iteration into other autoencoder baselines (GAE, VGAE, ARGA, ARGVA) yields uniform accuracy gains (e.g., boosting Chameleon VGAE AUROC from 95.9% to 97.0%).
- Linear Empirical Scalability: Runtime grows linearly with graph edge count on sampled subgraphs due to top-$K$ sparsification.
Limitations and Future Work
- Iterative Computational Overhead: Training a predictor across multiple outer iterations—where each outer loop involves graph reconstruction and full GNN retraining—demands noticeably more wall-clock training time than single-pass methods.
- Limited to Simple Homophily / Dot-Product Similarities: The edge potential definition relies on inner products of representations ($h_i^\top h_j$). Consequently, PULL does not naturally extend to signed graphs (with "dislike" or "distrust" links) or multi-relational/heterogeneous knowledge graphs.
- Future Directions: The authors suggest developing a single-iteration end-to-end variant to eliminate iterative retraining, as well as generalizing the latent potential formulations to multi-relational graphs.
Summary updated