Research map / Graph learning / Graph self-supervised learning
Revisiting Link Prediction: a data perspective
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.
Analyzes link prediction from a data perspective, identifying local structural, global structural, and feature proximity as key data factors, proving via a latent space model that feature and structural proximity are incompatible, and deriving decoupled SEAL plus dataset-selection guidance.
Problem
No universally best GNN4LP or heuristic algorithm exists across link prediction datasets; the underlying data mechanisms of link formation differ by domain and are not well understood.
Approach
Identifies three data factors (local structural, global structural, feature proximity), builds a latent space model with a feature-proximity parameter to bound link probability, and shows an incompatibility between feature proximity and structural proximity that causes GNN4LP models to underperform on feature-dominated edges; guides a decoupled SEAL design and benchmark selection.
Key results
- Decoupled SEAL consistently outperforms original SEAL, with gains up to 1.03% on the Collab dataset.
- On the Power dataset (GSP-dominated), Katz achieves Hit@10 of 29.85 versus 19.88 for BUDDY and 6.99 for SAGE.
- GNN4LP models outperform vanilla GNNs on LSP- and GSP-dominated edges but underperform on feature-proximity-dominated edges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Katz instead of other listed algorithms | Link prediction · Power | Hit@10: 29.85 (Katz); 19.88 $\pm$ 1.37 (BUDDY) | Helped |
| Use local structural proximity (CN) rather than feature proximity (FH) | Link prediction · Photo | Hit@10: 18.34 (CN); 13.78 (FH) | Helped |
| Use decoupled SEAL, separating original node features and local structural features into different GNNs | SEAL · Link prediction datasets | performance: up to 1.03% | Helped |
| Use GNN4LP rather than vanilla GNNs on edges dominated by structural proximity | GNN4LP models vs. vanilla GNNs · Node pairs dominated by LSP or GSP | performance | Helped |
| Use GNN4LP rather than vanilla GNNs on edges dominated by feature proximity | GNN4LP models vs. vanilla GNNs · Node pairs dominated by FP | performance | Hurt |
| Use GSP heuristics when local structural proximity is deficient | Link prediction heuristics · Sparse graphs with few common neighbors | performance | Helped |
| Use LSP heuristics when common neighbors are abundant | Link prediction heuristics · DDI and PPA | performance | Helped |
Surprising findings
- Deep GNN4LP models do not outperform heuristics on the newly introduced Power and Photo datasets.
- Vanilla GCN can achieve the best performance on certain datasets, so no single model is universally best.
Limitations
- Theory assumes feature proximity acts as an additional noise parameter rather than being combined within the same latent subspace.
- Analysis assumes alpha = +infinity for tractability.
- Latent space model assumes uniformly distributed nodes and independent links.
Experimental setup
Datasets: Cora Citeseer PubMed Collab PPA DDI Power Photo
Benchmarks: Cora Citeseer PubMed Collab PPA DDI Power Photo
Metrics: MRR Hit@10
Baselines: CN Katz FH MLP GraphSAGE GCN BUDDY NeoGNN NCNC SEAL
Builds on: SEAL Katz index latent space model Neo-GNN NCNC
Closest papers by meaning
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.89)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.88)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.88)
- Implicit degree bias in the link prediction task (ICML 2025 · similarity 0.87)
- Mixture of Link Predictors on Graphs (NeurIPS 2024 · similarity 0.87)
- Future Link Prediction Without Memory or Aggregation (NeurIPS 2025 · similarity 0.87)
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.