Link Prediction Eval

link-prediction-eval

Implicit degree bias in the link prediction task — Aiyappa et al. (2024) (arXiv:2405.14985, 2024)

What this evaluates

Evaluates a model's ability to predict missing or future edges in a graph based on its structural topology. It specifically probes whether the model learns meaningful graph patterns or merely exploits implicit degree biases inherent in the standard edge sampling procedure.

Datasets

• Empirical graphs (90 datasets) — total ?; splits: test (-1); repo https://github.com/skojaku/degree-corrected-link-prediction-benchmark

Metrics

• AUC-ROC (primary) — range: [0, 1]
  • The probability that the model assigns a higher score to a positive edge than to a negative edge: P(s_neg ≤ s_pos). Computed as the area under the Receiver Operating Characteristic curve plotting true positive rate against false positive rate across classification thresholds.

Input / output format

Input: Unweighted, undirected graph G=(V, E) without node attributes. For each evaluation instance, the model receives a node pair (i, j) and the graph structure.

Output: A scalar score s_ij representing the predicted likelihood that an edge exists between nodes i and j.

Scoring recipe

def compute_auc_roc(pos_scores, neg_scores):
    scores = np.concatenate([pos_scores, neg_scores])
    labels = np.concatenate([np.ones_like(pos_scores), np.zeros_like(neg_scores)])
    fpr, tpr, _ = roc_curve(labels, scores)
    return auc(fpr, tpr)

Common pitfalls

• Positive edges are sampled uniformly from the edge list, making high-degree nodes disproportionately likely to appear in the positive set, while negative edges are sampled uniformly from all node pairs, creating a fundamental degree bias.
• Trivial methods like Preferential Attachment (PA) that only use node degrees can achieve near-optimal AUC-ROC scores, misleadingly validating models that overfit to degree rather than structural patterns.

Evidence (verbatim from paper)

Fourth, the effectiveness of a method is evaluated using the Area Under the Receiver Operating Characteristic Curve (AUC-ROC), which represents the probability that the method gives a higher score to a positive edge than a negative edge.

Citation

@misc{aiyappa2024implicit,
  title={Implicit degree bias in the link prediction task},
  author={Aiyappa et al. (2024)},
  year={2024},
  note={arXiv:2405.14985}
}

• arXiv: 2405.14985