acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Link Prediction Evaluation: Full-Space Reference and Model-Screened Candidates

Abstract

Link prediction aims to infer unobserved edges in graphs and underlies many real-world applications. In practice, industrial systems typically use learned screening models to narrow vast candidate spaces and retain high-likelihood candidates before downstream prediction. However, academic evaluation protocols often construct candidate sets by randomly sampling or heuristically selecting non-edges, which may omit plausible and challenging negatives and lead to overly optimistic estimates of predictive capability. To quantify the effect of such candidate omission without imposing an additional selection rule, we use full-space evaluation, which ranks each test edge against the complete valid candidate space, as an idealized selection-free reference. Across 20 methods and seven datasets, we find that heuristic candidate selection can substantially inflate measured performance and distort method comparisons. Because full-space evaluation becomes costly on large graphs, we propose model-screened evaluation, which adapts the learned screening principle used in industrial systems to academic benchmarking and uses a learned model to retain a controllable number of high-likelihood candidates. With a fixed screening architecture and training configuration across all datasets, our protocol closely preserves the evaluation conclusions of the full-space reference. For example, on ogbl-ddi, model-screened evaluation reduces the average MRR deviation from full-space evaluation from 14.8 to 0.16 percentage points and the average pairwise MRR-gap deviation from 4.5 to 0.08.

Primary area:
datasets and benchmarks
Keywords:
Link Prediction, Evaluation Protocols, Benchmarking

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jH7vOpenReview ↗
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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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 τ\tau, 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.

Reviewer_zcQ5OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper is focused on link prediction evaluation. More specifically, link prediction methods are often evaluated using a random sample of negative pairs, which tends to avoid hard negatives. One way to address this issue is to sample all negative pairs, however that might be infeasible for large graphs due to the associated computing cost. The authors propose model screened evaluation: applying a model to filter candidate edges before link prediction. The proposed approach, called CAM, which combines node embeddings and neighborhood aggregation to score candidate pairs. The experiments apply seven datasets, 20 link prediction methods (heuristic, embedding-based, standard GNN, pair-aware GNN, and Transformer-based methods), and three types of evaluation (full, HeaRT, and model-screened). The results show that the model-screened evaluation is a better approximation of the full evaluation (all negative pairs) than HeaRT, while being significantly more efficient than the full evaluation.

Critical strengths

S1) The paper addresses a relevant problem, which is the evaluation of link prediction methods.

S2) The proposed solution is quite clear and the idea of applying model-based screening for link prediction evaluation seems novel.

S3) The experimental results support the main hypothesis in the paper: model-based screening is a better approximation for the full sampling results than HeaRT.

Critical weaknesses

W1) The novelty of the paper is very limited: As the paper notices, the issue with randomly sampled negative pairs was already known. The key novelty of the paper is the idea of model screening (instead of heuristics) for selecting candidate pairs. This is not sufficient for a publication at a major conference.

W2) The idea of training a model for screening candidate edge pairs is not well-supported in the paper. The screener relies on a trained MLP (using random negative sampling). The time to train the screener is not discussed and compared against HeaRT. Finally, to convincingly make a case that that CACM is better than HeaRT, one would have to show that the ranking of link prediction methods is more accurate using CACM than using HeaRT.

W3) An Important related work is not discussed in the paper:

@inproceedings{mattos2025attribute, title={Attribute-Enhanced Similarity Ranking for Sparse Link Prediction}, author={Mattos, Jo{~a}o and Huang, Zexi and Kosan, Mert and Singh, Ambuj and Silva, Arlei}, booktitle={Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1}, pages={1044--1055}, year={2025} }

Questions for authors

Q1) Why does the paper spends significant space repeating hypothesis from previous work regarding negative sampling?

Q2) Why is running a trained model over all candidate pairs feasible for evaluation? Why does the screener not suffer from the same issues it is trying to solve (random negative samples)?

Q3) How is the screener trained? What is the cost of training such a screener?

Q4) Why is the proposed solution (replacing a heuristic by a trained model) a major contribution?

3 comments
AuthorsOpenReview ↗

Response to Reviewer zcQ5

Q4/W1: Novelty and significance.

The central issue is whether academic link prediction (LP) benchmarks measure progress relevant to the applications they aim to serve. Industrial recommendation systems widely use learned screening, while academic evaluation often relies on random or heuristic candidate selection. If reported gains depend on omitting challenging alternatives, their practical significance becomes questionable. Since benchmarks guide model development and define progress, this mismatch can misdirect an entire line of research.

Our study shows that this concern persists under HeaRT (NeurIPS'23): even heuristic hard-negative selection can substantially distort conclusions about LP methods. We address this problem by adapting learned candidate screening to academic benchmarking and validating its fidelity against full-space evaluation, assessing whether it preserves performance estimates, inter-method gaps, and model rankings.

CAM provides an easily reproducible implementation with architecture and hyperparameters fixed across datasets. Comparable results with MLP, GCN, and SEAL screeners (Table 8) show that the benefits extend beyond a particular architecture, supporting the contribution at the evaluation-protocol level.

Q1: Background on random negative sampling.

We briefly discuss random negative sampling as background given its widespread use. We do not repeat prior analyses or experiments on its known limitations.

W2/Q2: Feasibility and random negatives in CAM training.

Neither CAM nor full-space evaluation considers all graph-wide non-edges for each test positive. Following HeaRT, each positive (u,v)(u,v) is compared against valid pairs (u,w)(u,w) or (w,v)(w,v), excluding self-loops and known positives. Thus, the candidate pool has O(∣V∣)O(|V|) pairs per positive, rather than all O(∣V∣2)O(|V|^2) graph-wide pairs. Full-space retains the O(∣V∣)O(|V|) pool; CAM scores the full endpoint-specific pool and retains 500 negatives. This exhaustive screening is a one-time preparation step, shared across downstream models and repeated evaluations; the measured costs are reported in Section 5.4.

Training CAM with random negatives may affect screener quality, but it does not restrict the candidate pool scored during screening. CAM is a coarse screener, analogous to candidate retrieval before fine ranking in industrial recommendation systems. It need only retain challenging candidates, not precisely rank them. We therefore assess its adequacy through downstream agreement with full-space evaluation, rather than its performance on random negatives. Table 2 and the ranking analysis below support its effectiveness.

W2/Q2/Q3: Screener computational cost.

CAM's training procedure is detailed in Appendix B.3.2, with no dataset-specific tuning. We have added a computational cost analysis in Section 5.4. Table 4 reports CAM training and candidate-generation times, including exhaustive scoring and top-500 selection, alongside HeaRT and full-space evaluation on ogbl-ppa and ogbl-citation2. Table 3 reports downstream LP inference times per evaluation.

Total preparation takes less than three hours on ogbl-citation2. For comparison, training the SEAL screener on ogbl-citation2 takes around six hours (Table 9). Preparation is performed once per fixed evaluation setup, and candidate sets are reusable across downstream models, configurations, and checkpoints.

Although model-screened evaluation requires more preparation time than HeaRT, it achieves substantially closer agreement with full-space results (Table 2). Both protocols retain the same number of negatives and incur comparable downstream inference costs.

Full-space evaluation requires no screener training but incurs substantially higher per-evaluation inference costs. The inference savings of model-screened evaluation offset its additional preparation cost relative to full-space evaluation after 2–6 evaluations for most of the evaluated pairwise GNNs, depending on the model and dataset; for the Transformer-based model T1, a single evaluation suffices.

W2: Model-ranking consistency.

Following Reviewer jH7v's suggestion, we report Spearman's rank correlations between model-screened or HeaRT model rankings and full-space rankings, based on mean MRR, in Section 5.5. Model-screened evaluation achieves higher correlations than HeaRT on all seven datasets, demonstrating more accurate model ordering.

W3: Related work.

We thank the reviewer for highlighting Mattos et al. (KDD 2025). Their work analyzes class imbalance, proposes Gelato, and evaluates each positive against all graph-wide non-edges. Our candidate universe follows HeaRT by fixing either endpoint and varying the other, modeling item or contact recommendation for a given user. Within this universe, we use full-space evaluation to examine the bias remaining under heuristic hard-negative selection. We have added the citation and clarified these differences in Section 3.1.

Reviewer_zcQ5OpenReview ↗

Response to the rebuttal

I read the rebuttal and checked the updated paper. Itried to answer the rebuttals within 24 hours (I was notified about this rebuttal yesterday).

  • Q4/W1: I am focusing on novelty here. I am not disagreeing that link prediction evaluation continues to be a problem (see S1). However, this paper revisits an evaluation problem from a benchmark paper published in 2023 that itself revisited a problem studied earlier. I don't think contribution 1 holds given the existing literature. I see this paper as a potential benchmark paper that attempts to improve on HeaRT (contributions 2 and 3).

  • W2/Q2: Most link prediction papers, including the baselines considered (academic), do not assume that candidate links are induced by a node. You could call one problem link prediction and the other link recommendation. If you want to predict potential links that include every node in the graph, the time complexity is the same, so the problems are not so different.

  • W2/Q2/Q3: Screening should be orders of magnitude faster than SEAL. There are more scalable link prediction algorithms that outperform SEAL, so this is not the best way to sell a screener. The challenge is that even a fast screener that evaluates too many candidates might not be fast enough in practice (an efficient data structure might be needed).

  • W2: Instead of computing the correlation, it would be easier to simply show the ordering of the methods. This paper has a good example: https://icml.cc/virtual/2025/poster/44481 From Figure 4, it seems that all the alternatives often agree on which is the best link prediction method for each dataset, but the correlation might be more affected by methods that are not necessarily at the top.

  • W3: This paper is also worth checking/citing: https://arxiv.org/pdf/2102.07878

To conclude, I will discuss this paper and the rebuttal with the other reviewers and it is possible that we disagree on what constitutes sufficient novelty for this particular conference. I would rather not change my score before the discussion to make sure that some of my concerns will at least be accounted for before we make the final decision.

AuthorsOpenReview ↗

Follow-up Response to Reviewer zcQ5

We thank the reviewer for the thoughtful follow-up and for further clarifying the concerns.

Q4/W1: Novelty and significance.

Our Contribution 1 addresses a question not systematically examined in prior LP benchmarks: how far evaluation conclusions deviate from an idealized, selection-free full-space reference. While prior studies have identified limitations of random negatives and proposed harder alternatives, to our knowledge, they have not systematically quantified the remaining distortions against exhaustive endpoint-replacement ranking. Such a reference is essential for measuring how much evaluation bias remains. Using it, we show that even HeaRT (a prominent work in NeurIPS'23) substantially distorts performance estimates, inter-method gaps, and model rankings across 20 LP methods and seven datasets.

More importantly, we adapt learned screening from industrial recommendation systems to academic LP benchmarking, achieving closer agreement with full-space evaluation at manageable cost. Comparable results across different screeners (Table 8) further establish the contribution at the evaluation-protocol level rather than in a particular architecture. This industry–academia gap matters because benchmarks guide model development and define research progress.

W2/Q2: Candidate space and evaluation setting.

HeaRT criticizes graph-wide random negative sampling for often selecting unrelated, easily distinguishable node pairs (Section 4.1). It therefore adopts endpoint replacement to provide more challenging, node-specific evaluation (Section 4.2). Our candidate space follows HeaRT's own setting, so endpoint replacement does not artificially disadvantage HeaRT; it preserves the setting that motivated HeaRT itself.

We agree that many academic LP models can score arbitrary node pairs without assuming a fixed query node. However, this does not require evaluating against all graph-wide non-edges. The candidate universe is an evaluation-protocol choice, and node-conditioned evaluation also aligns with industrial recommendation systems. We compare HeaRT, model-screened, and full-space evaluation within the same endpoint-replacement universe. Thus, the observed differences arise from candidate selection rather than different evaluation settings. We will clarify this scope in the revision.

W2/Q2/Q3: Screening efficiency

Our primary goal is evaluation fidelity, not screening speed. HeaRT is faster but exhibits substantially larger deviations from full-space evaluation (Table 2), while random sampling is even faster but yields even worse evaluations. Moreover, CAM has training costs comparable to MLP (Table 9). Even on ogbl-citation2, with millions of nodes and tens of millions of edges, CAM training and exhaustive candidate generation take <3hours on a single H100 GPU (Table 4). Like constructing a benchmark dataset, this is a one-time offline preparation cost, shared across downstream models, checkpoints, and configurations. Once candidates are generated, model-screened introduces no additional candidate-scoring workload over HeaRT for downstream prediction models, as both generate the same number of candidate pairs. Unlike real-time industrial prediction, offline benchmark preparation is not subject to strict latency constraints in practice.

W2: Model-ranking consistency.

To directly address this concern, in Table 11, we have additionally reported top-1 agreement and top-3 overlap with full-space evaluation, alongside Kendall's tau and pairwise reversals in Tables 12 & 13. Compared with HeaRT, model-screened evaluation improves top-1 agreement from 2/7 to 5/7 and aggregate top-3 overlap from 10/21 to 17/21. These results further demonstrate that model-screened evaluation preserves full-space rankings substantially better than HeaRT. Moreover, benchmarking goes beyond identifying the winner. It also measures improvements over existing methods and helps determine whether new model designs represent meaningful progress. This is why we explicitly evaluate pairwise performance gaps in Table 2. Even when the winner remains unchanged, HeaRT's inflated performance estimates and distorted gaps can misrepresent the significance of reported improvements.

W3: Related work.

LinkWaldo (ICDM'20) focuses on efficiently discovering plausible missing or future links from graph-wide candidates, whereas our work focuses on constructing challenging negatives for reliable benchmark evaluation. We have added this citation and clarified the distinction on Page 5.

Reviewer_kEx3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how candidate selection affects the link prediction evaluation. The paper uses full-space ranking as a reference and proposes CAM, a learned model that selects a small candidate set. Various experiments show that learned screening produces results closer to full-space evaluation than existing methods.

Critical strengths
  1. The paper addresses an important evaluation problem.
  2. The experiments cover many methods and graph data from various domains.
  3. The screening-model and candidate-budget ablations were useful.
Critical weaknesses
  1. All downstream models are selected using HeaRT validation. This is reasonable for isolating candidate-selection effects, but it leaves an important use case, which is, whether screened validation selects the same models and checkpoints as full-space validation.
  2. Table 3 reprorts downstream inference time, excluding CAM training and candidate generation.
Questions for authors
  1. Deos model-screened validation select models and checkpoints with comparable full-space test performance to those selected using full-space validation?
  2. What is the total evalutation time including CAM training and candidate generation?
1 comment
AuthorsOpenReview ↗

Response to Reviewer kEx3

W1/Q1: Validation and checkpoint selection.

We have added an experiment in Appendix B.5 that uses model-screened and full-space validation to select models and checkpoints, and then evaluates all selected models using full-space test ranking. Both protocols select from the same pool of hyperparameter configurations and checkpoints. We exclude ogbl-ppa and ogbl-citation2 from this experiment due to the substantial time required for repeated full-space validation on these two large datasets. Table 10 shows that the two protocols yield comparable full-space test MRR: the absolute differences, averaged across downstream methods for each dataset, range from 0.08 to 0.24 percentage points. These results support model-screened validation as a practical alternative to full-space validation on these datasets.

W2/Q2: End-to-end computational cost.

We report CAM training and candidate-generation times, including exhaustive candidate scoring and top-500 selection, in Table 4 of the revised manuscript, while Table 3 reports downstream link prediction inference times per evaluation. A detailed analysis is provided in Section 5.4. CAM uses fixed hyperparameters across datasets without dataset-specific tuning. Even on ogbl-citation2, which contains millions of nodes and tens of millions of edges, total preparation takes less than three hours. For comparison, training the SEAL screener on ogbl-citation2 takes around six hours (Table 9). CAM training and candidate generation are performed once per fixed evaluation setup, and the resulting candidate sets can be reused across downstream models, checkpoints, and hyperparameter configurations.

Although HeaRT has lower preparation costs, it produces substantially larger deviations from full-space evaluation (Table 2). The additional preparation cost of model-screened evaluation relative to full-space evaluation is amortized after 2–6 evaluations for most of the pairwise GNNs, depending on the model and dataset; for the Transformer-based model T1, a single evaluation suffices.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their constructive feedback. Motivated by the gap between learned candidate screening in industry and random or heuristic candidate selection in academic benchmarks, we investigate the evaluation bias that persists under HeaRT. Using full-space evaluation as a selection-free reference, we adapt the industrial screening paradigm to academic benchmarking through model-screened evaluation. CAM serves as an easily reproducible screener within this protocol; our contribution centers on evaluation methodology and its empirical assessment rather than architectural novelty.

In response to the reviewers' feedback, we have added experiments and analyses addressing three aspects: (i) end-to-end computational costs, including screener training, candidate scoring and selection, and downstream evaluation; (ii) model ranking consistency with full-space evaluation; and (iii) the use of model-screened evaluation for validation and checkpoint selection.

We have submitted a revised PDF incorporating these changes, with all revisions highlighted in blue (pages 5, 10, and 16). We address the reviewers’ specific concerns individually below.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.