Research map / Graph learning / Knowledge and temporal graphs
Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PULL, a PU-learning link predictor for edge-incomplete graphs that treats unconnected pairs as unlabeled, uses expected graph structure over latent edge variables, and iteratively refines pseudo-labels with a correction loss.
Problem
Link prediction in edge-incomplete graphs where unconnected node pairs are wrongly treated as true negatives, so models over-trust the observed graph and miss hidden links.
Approach
Treat observed edges as positives and unconnected pairs as unlabeled; assign latent variables to unconnected pairs, compute the expected graph under a line-graph pairwise Markov model (equivalent to EM-style soft labels), keep top-K confident edges as pseudo-labels, grow K over iterations, and add a correction BCE loss on the observed graph.
Key results
- PULL achieves the best AUROC/AUPRC on most datasets at missing ratio 0.1, e.g., Crocodile AUROC 98.31 vs 97.47 for the next best (Bagging-PU).
- Applying PULL to GAE improves Chameleon AUROC from 96.88 to 98.04 and to VGAE raises PubMed AUROC from 94.61 to 95.81.
- On ogbn-arxiv (r_m=0.1), PULL reaches AUROC 86.46 vs 85.91 for NESS, the strongest baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply PULL to GAE, VGAE, and VGNAE | GAE, VGAE, and VGNAE · PubMed, Cora-full, Chameleon, Crocodile, and Facebook, missing ratio 0.1 | AUROC and AUPRC | Helped |
| Add the correction loss L_C (ablation) | PULL · PubMed and Crocodile across iterations | AUC | Helped |
| Use weighted random sampling instead of top-K edge selection and omit L_C (ablation) | PULL · PubMed, Cora-full, Chameleon, Crocodile, and Facebook, missing ratio 0.1 | AUROC: 96.54 $\pm$ 0.18 vs 96.59 $\pm$ 0.19; 95.94 $\pm$ 0.31 vs 96.06 $\pm$ 0.34; 97.69 $\pm$ 0.28 vs 97.87 $\pm$ 0.33; 97.38 | Hurt |
| Use weighted random sampling instead of top-K edge selection and omit L_C (ablation) | PULL · PubMed, Cora-full, Chameleon, Crocodile, and Facebook, missing ratio 0.1 | AUPRC: 96.80 $\pm$ 0.14 vs 96.83 $\pm$ 0.18; 96.12 $\pm$ 0.32 vs 96.25 $\pm$ 0.35; 97.68 $\pm$ 0.28 vs 97.83 $\pm$ 0.33; 97.66 | Hurt |
| Increase the number of selected expected-graph edges over iterations | PULL · PubMed, Chameleon, Crocodile, and Facebook | AUC | Helped |
Surprising findings
- NESS is the best baseline on Cora-full, beating PULL in AUROC at missing ratio 0.2 (96.07 vs 95.39).
Limitations
- Not directly applicable to GAT, GraphSAGE, ARGA, ARGVA because they use different propagation schemes.
- Relies on approximations (top-K edge selection, independence assumption on marginals) without formal guarantees beyond the EM analogy.
- Results on some datasets (e.g., Cora-full) are not best across all settings, with NESS sometimes stronger.
Experimental setup
Datasets: PubMed Cora-full Chameleon Crocodile Facebook Physics ogbn-arxiv
Benchmarks: PubMed Cora-full Chameleon Crocodile Facebook Physics ogbn-arxiv
Metrics: AUROC AUPRC
Baselines: GCN+CE GAT+CE SAGE+CE GAE VGAE ARGA ARGVA VGNAE Bagging-PU NESS
Builds on: GAE VGNAE NESS Bagging-PU GCN
Closest papers by meaning
- Implicit degree bias in the link prediction task (ICML 2025 · similarity 0.88)
- Learning from Counterfactual Links for Link Prediction (ICML 2022 · similarity 0.86)
- Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.86)
- Link Prediction in Multilayer Networks via Cross-Network Embedding (AAAI 2024 · similarity 0.85)
- TEG-DB: A Comprehensive Dataset and Benchmark of Textual-Edge Graphs (NeurIPS 2024 · similarity 0.84)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.