- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper investigates how negative candidate construction affects link prediction evaluation, arguing that existing protocols may inflate measured performance and distort comparisons between methods. Using full-space evaluation, which ranks each positive test edge against all valid endpoint-replacement negatives, as an idealized reference, the authors evaluate 20 methods across seven datasets. The results show that the heuristic-based protocol HeaRT can substantially overestimate MRR relative to this reference and alter relative model comparisons.
As a computationally cheaper alternative for downstream evaluation, the paper proposes model-screened evaluation. A learned screener, Context-Augmented MLP (CAM), uses a fixed architecture and training configuration across datasets to select 500 high-scoring negative candidates per test edge. The experiments show that these candidate sets generally approximate full-space evaluation more closely than HeaRT. Additional experiments investigate alternative screening architectures, candidate-set sizes, and the inference efficiency of downstream link prediction methods.
Critical strengths
S1. Important benchmarking problem supported by extensive evidence. The paper addresses a relevant issue in link prediction benchmarking, showing that candidate selection can substantially affect evaluation outcomes. The experiments cover 20 methods and seven datasets, with HeaRT exhibiting average MRR deviations of 22.1 percentage points on Squirrel and 14.8 on ogbl-ddi relative to full-space evaluation (Table 2). This systematic analysis is valuable independently of the proposed screening method.
S2. Simple protocol with limited dataset-specific design choices. Using a fixed screening architecture and training configuration across datasets reduces the need for manually designed selection heuristics. The experiments with alternative screeners (MLP, GCN, SEAL) and different candidate-set sizes suggest that the improvements are not specific to one configuration. The availability of code and implementation details is also appreciated.
Critical weaknesses
W1. Fidelity to full-space evaluation is not fully established, particularly regarding model rankings. While the absolute deviations from full-space evaluation are generally small, the normalized deviations in Table 2 remain substantial on some datasets. For example, model-screened evaluation exhibits a normalized MRR-Diff of 105% and Gap-Diff of 66.7% on ogbl-ppa, and 39.6% and 19.2%, respectively, on ogbl-citation2. Since model-screened evaluation uses a subset of the full candidate space, the 105% normalized MRR-Diff implies that the average MRR across methods is approximately twice the full-space value. More importantly, the paper primarily assesses fidelity through MRR deviations and pairwise performance-gap deviations, without directly measuring ranking consistency. Since the authors argue that existing protocols can distort method comparisons, it would be important to quantify whether model-screened evaluation preserves the relative ordering of methods under the same metric. Measures such as Kendall's tau, top-k overlap, or the proportion of pairwise ranking reversals would provide more direct evidence supporting this claim.
W2. The computational efficiency analysis excludes the cost of candidate screening. Table 3 reports only the inference time of downstream models, excluding the cost of generating the candidate sets. However, CAM must still score all valid endpoint-replacement candidates before selecting the top 500 negatives, which may be expensive on large graphs such as ogbl-citation2 (approximately 2.9 million nodes). Training the screener also introduces additional overhead. I acknowledge that the paper focuses on downstream inference costs and that candidate sets can be shared across methods, allowing screening costs to be amortized. Nevertheless, without end-to-end measurements, it is difficult to assess the actual computational savings compared with full-space evaluation and HeaRT.
Questions for authors
Q1. Could the authors report direct measures of agreement between model-screened and full-space rankings under the same evaluation metric (e.g., Kendall's tau, Spearman's correlation, or pairwise ranking reversals), particularly on ogbl-ppa and ogbl-citation2? This would help establish whether the proposed protocol preserves model-selection conclusions beyond approximating absolute performance values.
Q2. What is the total computational cost of model-screened evaluation, including CAM training, candidate scoring, and top-M selection? How does it compare with HeaRT and full-space evaluation on the largest datasets, and how many downstream evaluations are needed to amortize the screening overhead?
2 comments
Additional Experiments on Model-ranking Consistency.
In addition to Spearman’s rank correlation, we have added top-1 agreement, top-3 overlap (as suggested by Reviewer zcQ5), Kendall’s , and pairwise ranking reversals in Appendix B.8, Tables 11–13. Our model-screened evaluation shows clear advantages over HeaRT across all these metrics, further supporting its more faithful preservation of full-space model rankings.
Response to Reviewer jH7v
W1: Remaining deviations from full-space evaluation.
We acknowledge the remaining discrepancy on ogbl-ppa. This partly reflects the finite candidate budget: with 500 negatives per positive, model-screened evaluation caps the rank at 501, whereas full-space ranks can exceed one million, allowing much smaller reciprocal ranks. Moreover, because the full-space MRR is small, the 105% normalized deviation corresponds to an average absolute MRR difference of approximately one percentage point, as reported in Table 2. This nevertheless represents a substantial reduction from HeaRT’s 698% normalized deviation.
Q1: Model-ranking consistency.
Following your suggestion, we now report Spearman’s rank correlation in Section 5.5 of the revised manuscript, comparing model rankings based on mean MRR under each protocol with those under full-space evaluation. Model-screened evaluation achieves higher ranking agreement than HeaRT on all seven datasets, including ogbl-ppa and ogbl-citation2, supporting more faithful preservation of relative method rankings. These results complement the reduced deviations in pairwise performance gaps, providing direct evidence of improved fidelity in method comparisons.
W2/Q2: End-to-end computational cost.
We have added an end-to-end cost analysis in the revised manuscript. Table 4 reports preparation costs, including CAM training, exhaustive candidate scoring, and top-500 selection, while Table 3 reports downstream inference costs per evaluation. For a fixed evaluation setup, preparation is performed once and the resulting candidates can be reused across downstream methods, checkpoints, and hyperparameter configurations.
Although full-space evaluation requires no screener training, its exhaustive downstream scoring incurs substantially higher per-evaluation costs. Accounting for both preparation and inference, model-screened evaluation becomes cheaper than full-space evaluation after 2–6 evaluations for most of the evaluated pairwise GNNs; for the Transformer-based model T1, a single evaluation suffices on either dataset.
HeaRT and model-screened evaluation retain the same number of negatives and incur comparable downstream inference costs. Thus, relative to HeaRT, model-screened evaluation trades additional one-time offline preparation for substantially closer agreement with full-space evaluation in MRR, inter-method performance gaps, and model rankings.