Source-linked AI summary
Evaluating Link Prediction Methods
Yang Yang, Ryan N. Lichtenwalter, Nitesh V. Chawla
TL;DR
Link prediction methods are difficult to compare reliably because evaluation involves extreme imbalance, sampling choices, temporal effects, directionality, and threshold selection. The paper analyzes these issues with proofs and experiments, showing that common evaluation practices can produce deceptive performance and rankings. It recommends precision-recall curves and AUPR, careful sampling, and other guidelines for fairer evaluation.
Problem
Link prediction evaluation lacks reliable, reproducible evidence about practical method performance because extreme imbalance and additional evaluation parameters complicate comparisons.
Method
The paper combines theoretical proofs, empirical examples, and analyses of sampling, imbalance, directionality, new nodes, threshold metrics, and threshold curves.
Results
The paper reports that ROC curves and AUROC can be deceptive for sparse link prediction, while precision-recall curves and AUPR provide better evaluation; negative undersampling can distort performance and rankings.
Takeaways & Limitations
Use precision-recall curves and AUPR, avoid arbitrary fixed thresholds, evaluate by geodesic distance, and preserve the original distribution when sampling negatives.
Takeaways & Limitations
TPRK evaluation is too sensitive to arbitrary K, which may change evaluations and reverse method rankings.
Abstract
from arXiv · showhide
Link prediction is a popular research area with important applications in a variety of disciplines, including biology, social science, security, and medicine. The fundamental requirement of link prediction is the accurate and effective prediction of new links in networks. While there are many different methods proposed for link prediction, we argue that the practical performance potential of these methods is often unknown because of challenges in the evaluation of link prediction, which impact the reliability and reproducibility of results. We describe these challenges, provide theoretical proofs and empirical examples demonstrating how current methods lead to questionable conclusions, show how the fallacy of these conclusions is illuminated by methods we propose, and develop recommendations for consistent, standard, and applicable evaluation metrics. We also recommend the use of precision-recall threshold curves and associated areas in lieu of receiver operating characteristic curves due to complications that arise from extreme imbalance in the link prediction classification problem.
1. Introduction
Link prediction evaluation must account for temporal construction, extreme class imbalance, sampling, directionality, and metric choice. The paper develops formalisms, proofs, empirical demonstrations, and guidelines for fairer evaluation.
- 1. Introduction: Link prediction predicts whether absent node pairs will gain links or contain missing links, with positives forming a small minority of instances.Future-link prediction models network evolution, whereas missing-link inference addresses static networks.
- 1. Introduction: Extreme sparsity makes test-set sampling common, but unrepresentative sampling can bias measured performance and predictor rankings.The paper recommends complete, unsampled test sets whenever possible and purely random negative sampling when necessary.
- 1. Introduction: Evaluation uses temporally separated feature and label snapshots for training and testing, with future testing labels excluded from training.Training features and labels precede testing features and labels, while testing labels come from Gt+1.
- 1. Introduction: Link prediction evaluation has additional complications beyond binary classification, including directionality and methods that may produce different outputs for source-target designations.The paper identifies directionality as an issue without an analog in typical classification tasks.
- 1. Introduction: The paper contributes theoretical proofs, empirical evidence, and guidelines addressing deceptive metrics, test sampling, and fair comparison of link predictors.Its stated objective is fair and effective evaluation rather than demonstrating one predictor's superiority.
2. Preliminaries
The paper evaluates link prediction on four longitudinal networks using predictors based on node statistics, common neighbors, and paths or random walks. It defines the network, prediction task, predictor families, and evaluation terminology used in the study.
- 2. Preliminaries: Experiments use four publicly available longitudinal datasets: Condmat, DBLP, Enron, and Facebook.The datasets represent collaboration or communication events over time.
- 2. Preliminaries: The three predictors represent node statistics, common neighbors, and paths or random walks: preferential attachment, Adamic/Adar, and PropFlow.Preferential attachment uses degree product; Adamic/Adar uses common neighbors; PropFlow uses restricted outward-moving random walks.
- 2. Preliminaries: A network is represented as G = (V, E), with nodes V and edges E; link prediction concerns whether an absent pair e(u, v) has or will have a link.The notation also defines Γ(u) as the neighbors of node u.
- 2. Preliminaries: The top K predictive rate, TPRK, is the percentage of correctly classified positives among the top K ranked instances and is equivalent to R-precision.K is a definable threshold.
- 2. Preliminaries: ROC and precision-recall curves summarize performance across score thresholds, while AUROC denotes area under the ROC curve.Each precision-recall point corresponds to a threshold with associated precision and recall.
3. Evaluation Metrics and Existing Challenges
Link-prediction evaluation relies on metrics and threshold choices that become unreliable under extreme class imbalance, poorly calibrated scores, and directional predictions. The paper highlights threshold-curve comparisons and explicit handling of ordering as necessary for interpretable, reproducible results.
- Fixed-threshold Metrics: Threshold curves avoid choosing a single score threshold when fixed-threshold metrics are difficult to interpret for poorly calibrated predictors.Even minor threshold changes can produce completely different evaluations.
- Fixed-threshold Metrics: Different score distributions, illustrated for Adamic/Adar and Preferential Attachment on DBLP, make normalized-score thresholds difficult to identify.The two methods exhibit different probability and cumulative density distributions.
- Fixed-threshold Metrics: TPRK percentages are meaningful only under specific geodesic-distance settings or when K is logically justified; otherwise cardinality thresholds can yield unstable evaluations.The paper limits percentage use to ℓ=2 or ℓ≤∞ under stated conditions.
- Class Imbalance: Accuracy can approach one for all-negative predictors because positive links are rare, making rare-positive performance especially important.Under extreme imbalance, random and trivial classifier metric expectations diverge.
- Directionality: In undirected networks, directional predictors may assign different scores to the same edge depending on which endpoint is treated as the source.The paper defines such a predictor as directional when P(u, v) ≠ P(v, u).
- Directionality: For directional predictors, selecting a single output from two order-dependent scores depends on both the predictor and deployment scenario and must be reported for reproducibility.The paper does not select an optimal mapping between the two values.
- Directionality: Two valid treatments of directional PropFlow predictions produced AUROCs of 0.610 and 0.625 on Condmat, demonstrating that evaluation handling changes reported results.One ranks both orderings; the other averages the two predictions before ranking.
4. Test Set Sampling and Class Imbalance
Test-set negative sampling can make link-prediction evaluation unstable or unrepresentative despite ROC theory suggesting class-distribution invariance. The paper shows that extreme imbalance, sampling variance, and distance-dependent score behavior can distort measured performance and obscure deployment-relevant comparisons.
- Impact of Sampling on ROC: Removing negative instances from test sets increases measured-performance variance as the negative-class sampling percentage decreases.Theorem 4.1 establishes this relationship for any link predictor.
- Impact of Sampling on ROC: AUROC remains stable only down to 1% negative-class sampling in Condmat and 10% in Facebook, DBLP, and Enron before destabilizing.These thresholds vary across datasets and learning settings.
- Impact of Sampling on ROC: Balanced-test-set sampling can shift AUROC by more than 0.007 for PropFlow and more than 0.01 for preferential attachment.Further sampling causes larger deviations, with susceptibility varying across predictors and networks.
- Impact of Sampling on ROC: Extreme link-prediction imbalance makes balanced sampled test sets too unstable for meaningful evaluation, even though sampling is often used to control test-set size.The paper notes that imbalance ratios can easily exceed thousands to one.
- The Real Testing Distribution: The paper compares complete and 2-hop prediction scenarios through surrogate AUROC simulations to expose how testing distributions affect apparent performance.The simulations designate Psub for the 2-hop sub-problem and Pfull for the complete problem.
- The Real Testing Distribution: Overall ROC performance can greatly exceed distance-restricted performance because score orderings conflate neighborhoods with different imbalance levels.For PropFlow, apparent Condmat performance is 36.2% higher overall than in the best individual distance ordering.
5. New Nodes
Test-set construction must match the prediction setting: returning confident predictions differs from answering queries involving unfamiliar nodes. The paper therefore determines test pairs from training data, avoiding added complexity from testing-network extraction.
- Two test-set construction strategies use either predictor-network nonedges or testing-network links to define potential links and labels.
- For returning a most-confident prediction set, unfamiliar testing nodes are irrelevant because their identities cannot be predicted from existing nodes.
- For query answering, handling new nodes becomes an important performance consideration, with responses shaped by cost and expected class distribution.
- Testing-network extraction complicates distance-based decomposition because distances require single-source shortest paths after pretending testing-only links were removed.
- The paper selects training-based test pairs unless testing-network extraction is compelling, excluding only links impossible to anticipate from training data equally across predictors.
6. Top K Predictive Rate
The top K predictive rate connects ranking quality with classification performance when K matches the number of positives. However, unknown or arbitrary K values can change evaluations and reverse predictor rankings.
- TPRK is the percentage of correctly classified positive samples among the top K ranked instances.
- When K = |P|, sensitivity and specificity are linearly dependent on TPRK.
- Specificity increases monotonically with TPRK and is linearly dependent on it.
- TPRK can estimate performance when K is appropriately selected, but arbitrary K values produce different evaluations and can reverse predictor rankings.
7. The Case for Precision-Recall Curves
Extreme imbalance and temporal or neighborhood distance make AUROC potentially deceptive for link prediction. The paper shows that precision-recall curves and AUPR better reflect changing baseline difficulty and expected performance patterns.
- In sparse networks, AUROC can appear exceptional while precision remains only a small fraction because millions of false positives may accompany each true positive.
- Precision-recall curves provide a more discriminative view in extreme imbalance, plotting recall on the x-axis and precision on the y-axis across score thresholds.
- AUPR is higher for ℓ= 2 than for ℓ≤∞, while increasing neighborhood distance raises imbalance and prediction difficulty.
- Temporal Effect on Link Prediction Evaluation: The temporal experiments divide testing data into five equal-duration subsets to compare performance across increasing temporal distance.
- Temporal Effect on Link Prediction Evaluation: AUROC values fluctuate with temporal distance, whereas AUPRs decline monotonically as temporal prediction becomes harder.
- Temporal Effect on Link Prediction Evaluation: When more years are aggregated, AUPRs for all three predictors increase monotonically while AUROCs decline or remain unstable.
8. Conclusion
The paper argues that link-prediction evaluation choices can produce questionable or misleading conclusions about predictor performance. It proposes guidelines addressing evaluation metrics, thresholds, distance-based reporting, and negative sampling.
- Evaluation strategies in link prediction involve many parameters with potentially undesirable values, making method performance difficult to specify and interpret reliably.The paper argues that these issues can lead to questionable or misleading results.
- The paper’s class-balance premise may be tenuous for rare networks, although the authors observed differing class-balance ratios across distances in all networks they studied.
- The authors propose precision-recall curves and AUPR because ROC curves and AUROC can be deceptive for link-prediction evaluation.
- Fixed thresholds should be avoided unless supplied by the problem domain because fixed-threshold metrics have identified limitations and drawbacks.
- Performance should be evaluated by geodesic distance, and by temporal distance when temporal distance is a significant prediction component.Distance-specific subproblems can differ significantly from overall link-prediction performance.
- Negative edges should not be undersampled from test sets because undersampling can inaccurately measure performance and incorrectly rank link predictors.