Link Prediction Eval

---
name: link-prediction-eval
description: 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. Use when the user wants to benchmark on Empirical graphs (90 datasets), or asks about evaluating this task. Reports AUC-ROC.
metadata:
  skill_kind: dataset_eval
  source_arxiv: 2405.14985
  bibtex_key: aiyappa2024implicit
  confidence: high
---

# 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

```python
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

```bibtex
@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