Research map / Graph learning / Graph self-supervised learning

Implicit degree bias in the link prediction task

ICML 2025 · Graph learning › Graph self-supervised learning · approach: Heterophily and imbalance on graphs · 1 citations (OpenAlex)

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.

Shows that uniform edge sampling in link prediction benchmarks biases positive edges toward high-degree nodes, so a degree-only PA predictor scores highly, and proposes a degree-corrected negative sampling benchmark that better aligns with recommendation rankings and improves GNN community detection.

Problem

The standard link prediction benchmark samples positive edges uniformly while negatives are sampled uniformly over nodes, creating a degree mismatch that lets degree-only predictors score nearly optimally, so the benchmark may not measure useful graph learning.

Approach

Sample negative node pairs with the same degree-proportional bias as positive edges (nodes drawn from a list where each node appears k_i times), making positive and negative edges indistinguishable by degree; theoretically derived that PA's AUC-ROC under log-normal degrees approaches the maximum as heterogeneity grows.

Key results

• Preferential attachment, a degree-only predictor, achieves average AUC-ROC 0.83 (ranked 13th of 26) under the standard benchmark, dropping to 0.54 (last of 26) under the degree-corrected benchmark.
• The degree-corrected benchmark yields higher RBO agreement with the recommendation task ranking than the original benchmark across 90 graphs.
• Degree-corrected training improves GNNs (notably GIN, GCN, GraphSAGE) on LFR community detection, with gains larger for heavier-tailed degree distributions.

Measured effects reported in the paper

Surprising findings

• A null degree-only method (PA) outperforms more than half of 26 advanced link prediction methods under the standard benchmark.
• Under the degree-corrected benchmark, GCN, node2vec, DeepWalk and EigenMap rise substantially in rank, while PA falls to last place.

Limitations

• Standard hyperparameters were used for all methods without task-specific tuning.
• Community structure is the only non-trivial structure tested for the training benefit; other structures such as centrality were not evaluated.
• Theoretical analysis assumes log-normal degrees and no degree assortativity, which may not match real data.

Experimental setup

Datasets: 90 empirical graphs Price graph (synthetic) LFR synthetic benchmark graphs

Benchmarks: link prediction (AUC-ROC) on 90 graphs link recommendation (VCMPR@C) LFR community detection

Metrics: AUC-ROC VCMPR@C rank-biased overlap adjusted element-centric similarity normalized mutual information

Baselines: Preferential Attachment Common Neighbors Laplacian EigenMap node2vec DeepWalk GCN GIN GraphSAGE

Builds on: Preferential Attachment Rank-biased overlap LFR benchmark

Closest papers by meaning

• A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.89)
• Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
• Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning (AAAI 2025 · similarity 0.88)
• Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction (ICML 2024 · similarity 0.88)
• On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
• Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.87)