Class imbalance occurs when classification classes appear with substantially unequal frequencies. In link prediction, sparse graphs produce many more negative examples—node pairs without relationships—than positive examples. section 10.2.3 section 10.2
Class imbalance creates practical modeling problems:
- Negative examples can scale quadratically with the number of nodes, while positive relationships scale linearly. section 10.2.3
- A model can achieve high accuracy by always predicting the majority class, while misclassifying most minority-class examples. section 10.2.3
- Link-prediction workflows commonly subsample negative examples until their count is approximately comparable to the positive examples. section 10.2 section 10.6
Sparse social-network relationships
A social platform may contain billions of possible user pairs but only a small number of existing relationships for each user. Predicting that no link exists for every pair could produce around 99% accuracy while failing to identify new relationships. A practical exercise constructs roughly 13,082 negative examples—or the number of positive examples produced—while ensuring the selected pairs have no relationship in the feature, training, or test sets. section 10.2.3
