Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking
Authors: Juanhui Li
Harry Shomer
Haitao Mao
Shenglai Zeng
Yao Ma
Neil Shah
Jiliang Tang
Dawei Yin
Venue: NeurIPS 2023 Datasets and Benchmarks Poster (2023)
Keywords: Link Prediction
Graph Neural Networks
New Evaluation

Abstract: Link prediction attempts to predict whether an unseen edge exists based on only a portion of the graph. A flurry of methods has been created in recent years that attempt to make use of graph neural networks (GNNs) for this task. Furthermore, new and diverse datasets have also been created to better evaluate the effectiveness of these new models. However, multiple limitations currently exist that hinders our ability to properly evaluate these new methods. This includes, but is not limited to: (1) The underreporting of performance on multiple baselines, (2) A lack of a unified data split and evaluation metric on some datasets, (3) An unrealistic evaluation setting that produces negative samples that are easy to classify. To overcome these challenges we first conduct a fair comparison across prominent methods and datasets, utilizing the same dataset settings and hyperparameter settings. We then create a new real-world evaluation setting that samples difficult negative samples via multiple heuristics. The new evaluation setting helps promote new challenges and opportunities in link prediction by aligning the evaluation with real-world situations.

Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking
Juanhui Life, Harry Shomer Haitao Mao
Shenglai Zeng'
Yao Ma² Neil Shah .Jiliang Tang* Dawei Yin' MMichigan State University, RRnsssllarr Polytechnic Institute SSnap Inc., "Baidu Inc.
{1i juanh1, shomerha, haitaoma, saameraa, zengshe1, ttaggj may13@rpi.edi edu, nshah@snap. com, com, yindawei @acm. org
mongjill ili) @msu. edu
Abstract
Link prediction attempts to predict whether an unseen edge exists based on only portion of edges of graph. A flurry of methods have been introduced in re- cent years that attempt to make use of graph neural networks (GNNs) for this task. Furthermore, uate the effectiveness of these new models. However, multiple pitfalls currently exist that hinder ability to properly evaluate these methods. These pit- falls mainly include: (1) Lower than actual performance on multiple baselines, (2) A lack of unified data split and evaluation metric some datasets, and (3) An unrealistic evaluation setting that uses easy negative samples. To overcome these challenges, first conduct fair comparison across prominent methods and datasets, utilizing the same dataset and hyperparameter search settings. We then create practical evaluation setting based a Heuristic Related Sampling Technique (HeaRT), which samples hard negative samples via multiple heuristics. The new evaluation setting helps promote new challenges and opportunities in link prediction by aligning the evaluation with real-world situations. Our implementa- tion and data are available https :/ //github. com/ Juanhui28/Heall
and diverse datasets have also been created to better eval-
Introduction
The task of link prediction is to determine the existence of an edge between two unconnected nodes graph. Existing link prediction algorithms attempt to estimate the proximity of different pairs of nodes in the graph, where node pairs with higher proximity are more likely to interact [I]
Link prediction applied in many different domains including social networks 2 biological net- works (3), and recommender systems (4.
Graph neural networks (GNNs) (5] have gained prominence in recent years with many new frame-
works being proposed for variety of different tasks. Corresponding to the rise in popularity of GNNs, there has been number of studies that attempt to critically examine the effectiveness of different GNNs on various tasks. This can be seen for the task of node classification [6) graph classification 77), knowledge graph completion (KGC) I0 and others [I]
However, despite a number of new GNN-based methods being proposed 12 for link prediction, there is currently no work that attempts to carefully examine recent advances in link prediction methods. Upon examination, we find that there are several pitfalls in regard to model evaluation that impede our ability to properly evaluate current methods. This includes:
* Equual contribution.
37th Conference on Neural Information Processing Systems (NeurIPS 2023) Track on Datasets and Bench- marks.

---

ogbl-collab - Common Neighbor Distribution
ogbl-gpa Neighibor Distribution
nehi-taaten2 Common Neighter Derribution
% of Samples
100%
Positive Negative
% of Samples
80%
Negative
Positive
Sample
100%
Positive Negative
% 5a
60%
60%
40%
-0%%
KELOOL
40%
20%
0%
10. 17
[1.
res
B.
1122
10)
[10, m)
0%
[0. 33
[1,
40%%%
[5, 25)
1.00
[25, m]
0.325
0%
10. 13
11.
1.00%
13.30
15, x3
Number of CNs
Number of CNs
Number of CNs
(a) ogbl-collab
(b) ogbl-ppa
(c) ogbl-citation2
Figure Common neighhor distribution for the positive and negative test samples for the ogbl- collab, ogbl-ppa, and ogbl-citation2 datasets under the existing evaluation setting.
1. Lower than Actual Performance. We observe that the current performance of multiple mod- els is underreported. For some methods, such as standard GNNs, this is due to poor hyperpa- rameter tuning. Once properly tuned, they can even achieve the best overall performance on some metries (see SAGE [66 in Table Furthermore, for other methods like Neo-GNN [T4] we can achieve around an 8.5 point increase in Hits @50 on ogbl-collab relative to the origi- nally reported performance. This results in Neo-GNN achieving the best overall performance on ogbl-collab in study (see Table 2). Such problems obscure the true performance of different models, making difficult to draw reliable conclusions from the current results.
Lack of Unified Settings. For Cora, Citeseer, and Pubmed datasets [77], there exists no uni- fied data split and evaluation metrics used for each individually. For the data split, some works 18
19 use a single fixed train/valid/test split with percentages 85/5/10%. More re- cent works 35 use 10 random splits of size 70/10/20%. In terms of the evaluation metrics, metrics such as MRR or Hits @ K while others 20) 19 use ranking-bass
some studies 13, 15]
report the area under the curve (AUC). This is despite multiple studies that argue that AUC is poor metric for evaluating link prediction 21 22). Additionally, for both planetoid (i.e., Cora, Citeseer and Pubmed) and ogbl-collab dataset, some methods incorporate validation edges dur- ing the testing phase [13], whereas others 14, exclude them. This lack of a unified setting makes it difficult to compare those works and hampers our ability to determine which methods perform best on these datasets.
3. Unrealistic Evaluation Setting. During the evaluation, we are given set of true samples (i.e., positive samples) and a set of false samples (i.e., negative samples). We are tasked with learning classifier f that assigns higher probability to the positive samples than the nega- tives. The current evaluation setting uses the same set of randomly selected negative samples for each positive sample. We identify two potential problems with the current evaluation pro- cedure. (1) It is not aligned with real-world settings. In a real-world scenario, we typically care about predicting links for specific node. For example, in friend recommendations, we aim to recommend friends for a specific user u. To evaluate such models for u, we strive to rank node pairs including u. However, this does not hold in the current setting is not included in most of the negative samples. (2) The current evaluation setting makes the task too easy. As such, it may not reflect the model performance in real- world applications. This is because the nodes in a randomly selected negative "node pair" are likely to be unrelated to each other. As shown in Figure almost all negative samples in the test data have common neighbors, typically strong heuristic, making them trivial to classify them.
To account for these issues, we propose first conduct fair and reproducible evaluation among cur- rent link prediction methods under the existing evaluation setting. We then design new evaluation strategy that is more aligned with real- world setting and detail our results. Our key contributions are summarized below:
Reproducible and Fair Comparison. We conduct fair comparison of different models across multiple common datasets. To ensure fair comparison, we tune all models on the same set of hyperparameters. We further evaluate different models using multiple types of evaluation

---

metrics. For the Planetoid datasets [17], we further use a unified data split to facilitate a point of comparison between models. To the best of our knowledge, there are no recent efforts to comprehensively benchmark link prediction methods (several exist for KGC [10] g 8 thermore, we open-source the implementation in our analysis to enable others in their analyses.
B) Fur-
New Evaluation Setting. We recognize that the current negative sampling strategy used in evaluation is unrealistic and easy. To counter these issues, we first use more realistic setting of tailoring the negatives to each positive sample. This is achieved by restricting them to be corruptions of the positive sample (i.e., containing one of its two nodes as defined in Eq. (3). Given the prohibitive cost of utilizing all possible corruptions, we opt instead to only rank against K negatives for each positive sample. In order to choose the most relevant and difficult corruptions, we propose Heuristic Related Sampling Technique (HeaRT)), which selects them based combination of multiple heuristics. This creates more challenging task than the previous evaluation strategy and allows us to better assess the capabilities of current methods.
The rest the paper is structured as follows. Section 2 we introduce the models, datasets, and settings used for conducting fair comparison between methods. In Section 3 we show the results of the fair comparison under the existing evaluation setting and discuss our main observations. Lastly, in Section 4 we introduce our evaluation setting. We then detail and discuss the performance of different methods using our new setting.
2
Preliminaries
2.1 Task Formulation
In this section we formally define the task of link prediction. Let G - (V,E) be graph where V and & are the set of nodes and edges in the graph, respectively. Furthermore, let X E RI be set of d-dimensional features for each node. Link prediction aims to predict the likelihood of a link existing between two nodes given the structural and feature information. For pair of nodes u and v, the probability of a link existing, p(u, v), is therefore given by:
p(u, v) p(u, v 9)X).
Traditionally, p(u,2) 2) was estimated via non-learnable heuristic methods 23 methods that use learnable parameters have gained popularity [3] estimate p(u, v) via a learnable function f such that:
24 More recently,
13 These methods attempt to
p(u, v) f(u v G, 0),,)),
where θ represents a set of learnable parameters. common choice of are graph neural net- works 25 In the next subsection we detail the various link prediction methods used in this study.
2.2 Link Prediction Methods
In this section we given an overview of the different methods used in this study. Conventional methods (23 (4] often exploit hand-craft graph structural properties (i.e., heuristics) between node pairs. GNNs attempt to learn the structural information to facilitate link prediction 126 15 13.
Given the strong performance of pairwise-based heuristics [5). some recent works use both GNNs and pairwise information, demonstrating strong performance.
For our study, we consider both traditional and state-of-the-art GNN-based models. They can be roughly organized into four categories. 1) Heuristic methods: Common Neighbor (CN) (27), Adamic Adar (AA) (28), Resource Allocation (RA) (29). Shortest Path [24], and Katz [30]. These methods define a score to indicate the link existence based on the graph structure. Among them, CN, AA, and RA are based on the common neighbors, while Shortest Path and Katz are based on the path information. 2) Embedding methods: Matrix factorization (MF) (3 Multilayer Percep- tron (MLP) and Noce2Vec [31]. These methods are trained to learn diw-dimensional node embed- dings that are used to predict the likelihood of node pairs existing. 3) GNN methods: GCN (32), GAT [88. SAGE [66, and GAE 20 These methods attempt to integrate the multi-hop graph struc- ture based on the message passing paradigm. 4) GNN Pairwise Information methods: Standard GNN methods, while powerful, are not able to capture link-specific information (26). As such,
3

---

works have been proposed that augment GNN methods by including additional information to bet- ter capture the relation between the nodes in the link we are predicting. SEAL [26]. BUDDY [ and NBFNet [19 use the subgraph features. Neo-GNN [4] NCN 15 and NCNC [S] are based
on common neighbor information. Lastly, PEG 33 uses the positional encoding derived from the graph structure.
2.3 Datasets and Experimental Settings
In this section we summarize the datasets and evaluation and training settings. We note that the settings depend on the specific dataset. More details are given in Appendix
Datasets. We limit our experiments to homogeneous graphs, which are the most commonly used datasets for link prediction. This includes the small-scale datasets, i.e., Cora, Citeseer, Pubmed [[7], and lcage-scale datasets in the OGB benchmark [34), i.e. ogbl-collab, ogbl-ddi, ogbl-ppa, and ogbl- citation2. We summarize the statistics and split ratio of each dataset in Appendix
Metries. For evaluation, we use both the area under the curve (AUC) and ranking- metrics, i... mean reciprocal rank (MRR) and Hits K. For Cora, Citeseer, and Pubmed we adopt K e (1,3, 10, 1003. We note that K 100 reported in some recent works [3] [5]). However due to the small number of negatives used during evaluation (e.g., z 500 for Cora and Citeseer) K = 100 likely not informative. For the OGB datasets, we adopt K E (20, 50, 100) to keep consistent with the original study (4 Please see Appendix B. f for the formal definitions of the various evaluation metries.
Hyperparameter Ranges. We conduct a grid hyperparameter search across a comprehensive range of values. For Cora, Citeseer, and Pubmed this includes: learning rate (0.01, 0.001), dropout (0.1, 0.3, 0.5), weight decay (Ie-4, 1e-7, 0), number of model layers (1, 2, 3), number of prediction layers (1, 2, 3), and the embedding size (128, 256). Due to the large size of the OGB datasets, it's infeasible to tune over such a large range. Therefore. following the most commonly used settings among published hyperparameters, we fix the weight decay to 0, the number of model and prediction layers to be 3, and the embedding size to be 256. The best hyperparameters are chosen based on the validation performance. We note that several exceptions exist to these ranges when they result in significant performance degradations (see Appendix [ for more details). We further follow the existing setting and only sample one negative sample per positive sample during training.
Existing Evaluation Settings. In the evaluation stage, the same set of randomly sampled negatives are used for all positive samples. We note that one exception is ogbl-citation2, where they randomly sample 1000 negative samples per positive sample. For Cora, Citeseer, and Pubmed the number of negative samples is equal to the number of positive samples. For the OGB datasets. we use the existing fixed set of randomly chosen negatives found in [34]. Furthermore, for ogbl-collab we follow the existing protocol (34] and include the validation edges in the training graph during testing. This setting is adopted on ogbl-collab under both the existing and new evaluation setting.
3 Fair Comparison Under the Existing Setting
In this section, we conduct fair comparison among link prediction methods. This comparison is spurred by the multiple pitfalls noted in Section [ which include than--than-actual model perfor- mance, multiple data splits, and inconsistent evaluation metrics. These pitfalls hinder our ability to fairly compare different methods. To rectify this, we conduct a fair comparison adhering to the settings listed in section 2.3
The results are split into two tables. The results for Cora, Citeseer, and Pubmed are shown in Table and OGB in Table For simplicity, we only present the AUC and MRR for Cora, Citeseer, and Pubmed. For OGB datasets, we include AUC and the original ranking metric reported in B4 to allow a convenient comparison (Hits@20 for ogbl-ddi, Hits@50 for ogbl-collab, Hits@ 100 for ogbl-ppa, and MRR for ogbl-citation2). We use ">24h" to denote methods that require more than 24 hours for either training one epoch or evaluation. OOM indicates that the algorithm requires over 50Gb of GPU memory. Since ogbl-ddi has no node features, we mark the MLP results with a "N/A". Additional results in terms of other metrics are presented in Appendix F We have several noteworthy observations concerning the methods, the datasets, the evaluation settings, and the overall results. We highlight the main observations below.

---

Table 1: Results on Cora, Citeseer, and Pubmed %) under the existing evaluation setting. High- lighted are the results ranked first, second, and third.
Cora
Citeseer
Pubmed
Models
MRR
AUC
MRR
AUC
MRR
AUC
CN
20,99
70.85
28.34
67.49
14.02
63.9
AA
31.87
70.96
29.37
67.49
16,66
63.9
Heuristic
RA
30.79
70.96
27.61
67.48
15.63
63.9
Shortest Path
12.45
81.08
31.82
75.5
7.15
74.64
Katz
27.4
81.17
38.16
75.37
21.44
74,86
Vode2Voc
37.29 = 8.82
90.97 # 0.64
44.33 = 8.99
94.46 0,59
34.61 = 2.48
93.14 0.18
Fimhedding
MF
14.29 5.79
80.29 + 2.26
24.80 4.71
75.92 + 3.25
19.29 + 6.29
93.06 + 01.43
MLP
31.21 + 7,90
95.32 + 0.37
43.53 = 7.26
94,45 + 0.32
16.52 + 4.14
98.34 0.10
GCN
32.50 6.87
95.01 1 0.32
50.01 =: 6.04
95.89 1: 0.26
19.94 + 4.24
98.69 i: 0.06
GAT
31.86 +: 6.08
93.90 4: 0.32
48.69 7.53
96.25 4 0.20
18.63 à 7.75
98.20 a 0.07
GNN
SAGE
37.83 + 7.75
95.63 + 0.27
47,84 6.39
97.39 + 0.15
22.74 + 5.47
98.87 +: 0.04
GAE
3.21
95.08 0.33
63.33
97.4 0.22
97.47 0.08
SEAL
26.69 5.89
90.39 0.75
39.36 4.99
88.52 1.40
38,06 + 5.18
97.77 0.40
BUDDY
0.36 95,06 4.44
$9.48 8.96
9.22
23.98 5.11
Nea-GNNN
22.65
93.73
53.97 +
94.89
31.45 3.17
98.71 0.05
GNN+Puirwise Info
NCN
32.93
96.76 + 0.18
54.97
97.04 0.26
35.65 + 4.60
98.98 + 0.04
NCNC
29.01 + 3.83
96.90 + 0.28
64.03
97.65 0.30
4.448
99.14 0.03
NBFNet
37.69 3.97
92.85 + 0.17
38.17 3.06
91.06 0.15
2.12
98.34 0.02
PEG
22.76 1.84
94.46 + 0.34
16.12 6.62
21.05 2.85
96.97 + 0.39
Table 2: Results on OGB datasets (%) under the existing evaluation setting. Highlighted are the results ranked first, second, and third.
oghi-collah
oghl-ddi
aghl-ppa
oghl-citution2
Models
Hitses0
AUC
Hiixe20
AUC
H0s
AUC
MRR
CN
61.37
82.78
17.73
95.2
27.65
97.22
74.3
64.17
82,78
18.61
95.43
32.45
97.23
75.96
Heuristic
49.33
Shorest Pach
46.49
96.51
0
59.07
D
99.13
>24h
Kaiz
64.33
90.54
17.73
95.2
27.65
97.22
74.3
Node2Vec
0.04
99.77
45.04
Embedding
MF
41.81
1.67
83.75 # 1.77
23.50 5.35
99.46 0.10
28.4 = 4.62
99.46 0.10
50.57 = 12.14
MI.P
1.08 35.81
95.91 + 0.08
N/A
N/A
0.45 + 0.04
90.23 0.00
38.07 0.09
97.89
2.90
0.03
0.07 0OM
GNN
SAGE
GAT
59.44 1.37
55.00 3.28
98.08 = 0.03
97.11 0.09
49.84 = 15.56
88 8.83
99.63 0.21
99.96 :: 0.00
41.02 1.94 00M
00M
99.82 0.00 0OM
00M
83.06 0.09
GAF
00M
GOM
6.02 7.09
75.34 +15.96
ODM
SEAL
63.37 0.69
95.65 1 0.29
25.25 3.90
97.97 1 0.19
48.80 5.61
99.79
0.02
86.93 a 0.43
BUDDY
64.59 0.46
96.52 + 0.40
29.60 4.75
99.81 + 0.02
47.33 = 1.96
99.56 0.02
87.86 2 0.18
Nco-GNN
66.13 0.61
98.23 0.05
20.95 6,03
98.06 2.00
48.45 1.01
97.30 0.14
63.54 a 0.32
GNN Pairwise Info
63.86
97.83
76.52 10.47
99,97 0.00
62.63
99.95
89.27
NUNC
65.97 1.03
98.20 a 0.05
70.23 =: 12.11
99.97 + 0.01
62.61 0.76
99.97 0.01
89882 0.43
NRFNet
0OM
0OM
>-4hh
5:4h
ODM
OOM
ODM
30.28
OOM
0OM
Observation Better than Reported Performance. We find that for some models we are able to achieve superior performance compared to what is reported by recent studies. For instance, in our study Neo-GNN 14] achieves the best overall test performance on ogbl-collab with Hits@ 50 of 66.13. In contrast, the reported performance in [1] is only 57.52, which would rank seventh under our current setting. This is because the original study [4 does not follow the standard setting of including validation edges in the graph during testing. This setting, as noted in Section 2.3 used by all other methods on ogbl-collab. However was omitted by [14), resulting lower reported performance. Furthermore, on oghl-citation2 34. our results for the heuristic methods are typically around 75% MRR. This significantly outperforms previously reported results, which report an MRR of around 50% 226 [3). The disparity arises previous studies treat the ogbl-citation2 as methods, ogbl-citation2
directed graph when applying heuristic methods. However, for is typically converted to a undirected graph. We remedy this by also converting ogbl-citation2 to an undirected graph when computing the heuristics, leading to a large increase in performance.
Furthermore, with proper tuning, conventional baselines like GCN 25 and GAE 22 generally exhibit enhanced performance relative to what was originally reported across all datasets. For ex- ample, we find that GAE can achieve the second best MRR on Citeseer and GCN the third best Hits @ on ogbl-ddi. comparison of the reported results and ours are shown in Table 3 We note that we report AUC for Cora, Citeseer, Pubmed as it was used in the original study. These
5

---

Table 3: Comparison of ours and the reported results for GCN and GAE.
ogbl-collab Hins
ogbi-ppa His 100
agbl-ddi Hin 20
ogbl-citation2 MRR
Cora
Citeseer
Pubmed ALCC
GCN
GAE
AIC
ALC
Reported
4 54.96 +: 3.18
18.67 + 1.32 29.57 + 2,90
5.07 49,90 + 7:23
84.74
Reported
91,00
Ours
84.85 a 0.07
Ours
95.08 a 0.35
97.06 = 0.22
97.47 = 0,08
observations suggest that the performance of various methods are better than what was reported in their initial publications. However, many studies [5]] 26] only report the original performance for comparison, which has the potential to lead to inaccurate conclusions.
Observation 2: Divergence from Reported Results ogbl-ddi. We observe that our results in 2 for ogbl-ddi differ from the reported results. Outside of GCN, which reports better perfor- mance, most other GNN-based methods report lower-than-reporte performance. For example, for BUDDY we only achieve a Hits 20 of 29.60 vs. the reported 78.51 (see Appendix [ for a comprehensive comparison among methods). We find that the reason for this difference depends on the method. BUDDY 13 reported using 6 negatives per positive sample during training, leading to an increase in performance. Neo-GNN [14 first pretrains the GNN under the link prediction task, and then uses the pretrained model as the initialization for Neo-GNN For a fair comparison among methods, we only use 1 negative per positive sample in training and we don't 't apply the pretraining. For other methods, we find that a weak relationship between the validation and test performance complicates the tuning process, making it difficult to find the optimal hyperparameters. Please see Appendix E for a more in-depth study and discussion.
Observation High Model Standard Deviation. The results in Tables I and 2 present the mean performance and standard deviation when training over 10 seeds. Generally, we find that for multiple datasets the standard deviation of the ranking metrics is often high for most models. For example, the standard deviation for MRR can be as high as 8.82, 8.96, or 7.75 75 for Cora, Citeseer, and Pubmed, respectively. Furthermore, on ogbl-ddi the standard deviation of Hits @20 reaches as high as 10.47 and 15.56. A high variance indicates unstable model performance. This makes it difficult to compare results between methods as the true performance lies in a larger range. This further complicates replicating model performance, as even large differences with the reported results may still fall within variance (see observation 2). Later in Section 4.. we find that our new evaluation can reduce the model variance for all datasets (see Table 6 This suggests that the high variance is related to the current evaluation procedure.
Observation 4: Inconsistency of AUC vs. Ranking-Based Metrics. The AUC score is widely adopted to evaluate recent advanced link prediction methods (20 19 However, from our results in Tables [ and 2 we observe that there exists a disparity between AUC and aunking-bssed metrics. In some cases, the AUC score can be high when the ranking metric is very low or even 0. For example, the Shortest Path heuristic records a Hits K of O on ogbl-ppa. However, the AUC score is > 99%. Furthermore, even though RA records the third and fifth best performance on ogbi-ppa and ogbl- collab, respectively, it has a lower AUC score than Shortest Path on both. Previous works 22 21 argued that AUC is not proper metric for link prediction. This is due to the inapplicability of AUC for highly imbalanced problems 335 36).
4 New Evaluation Setting
In this section, we introduce a new setting for evaluating link prediction methods. We first discuss the unrealistic nature of the current evaluation setting in Section 4.1 Based on this, we present our new evaluation setting in Section 4.2 which aims to align better with real-world scenarios. Lastly, we present and discuss the results based on our new evaluation setting.
in Section 4.3
4.1 Issues with the Existing Evaluation Setting
The existing evaluation procedure for link prediction is rank a positive sample against a set of K randomly selected negative samples. The same set of K negatives are used for all positive samples

---

(a, b)
Negstives
Negatives
(a.
p.
Heuristic
Merge Ranks K/2 samples
(a, ")
Rank samples by each heuristic
Combine Lists
Heuristic
(a) Negative sample genera- tion one positive sample.
(b) Process of determining negative samples that contain node
Figure 2: Pipeline for generating the hard negative samples for positive sample (a, b).
(with the exception of ogbl-citation2 which uses 1000 per positive sample). We demonstrate that there are multiple issues with this setting, making it difficult to properly evaluate the effectiveness of current models.
Issue 1: Non-Personalized Negative Samples. The existing evaluation setting uses the same set of negative samples for all positive samples (outside of ogbl-citation2). This strategy, referred to as global negative sampling (37), is not a commonly sought objective. Rather, we are often more interested in predicting links that will occur for specific node. Take, for example, a social network that connects users who are friends. In this scenario, we may be interested in recommending new friends user This requires learning a classifier f that assigns probability to a link existing. When evaluating this task, we want to rank links where u connects to an existing friend above those where they don't For example, However, the existing evaluation setting doesn't I explicitly test for this. Rather it compares true sample (u, a) with a potentially unrelated negative sample, e.g., (c, d). This not aligned with the real-world usage of link prediction on such graphs.
friends with a but not we hope that f(u, a) > f(, b).
Issue Easy Negative Samples. The existing evaluation setting randomly selects negative samples to use. However given the large size of most graphs (see Table in Appendix randomly sampled negatives are likely to choose two nodes that bear no relationship to each other. Such node pairs are trivial to classify. We demonstrate this by plotting the distribution of common neighbors (CN), strong heuristic, for all positive and negative samples contain no CNs, making them easy to classify. We further show that the same problem afflicts even the smaller datasets in Figure in Appendix A
samples in Figure [ Almost all the negative
These observations suggest that more realistic evaluation strategy desired. At the core this challenge which negative samples to use during evaluation. We discuss our design for solving this in the next subsection.
4.2 Heuristic Related Sampling Technique (HeaRT)
In this subsection, we introduce new strategy for evaluating link prediction methods. To address the concerns outlined in Section [.]] we design new method for sampling negatives during evaluation. Our strategy, HeaRT, solves these challenges by: (a) personalizing the negatives to each sample and (b) using heuristics to select hard negative samples. This allows for the negative samples to be directly related to each positive sample while also being non-trivial. We further discuss how to ensure that the negative samples are both personalized and non-trivial for a specific positive sample.
From our discussion in Section 4.1 we are motivated in personalizing the negatives to each positive sample. Since the positive samples in the current datasets are node pairs, we seek personalize the negatives to both nodes in the positive sample. Extending our example in Section 4. this is analogous to restricting the negatives to contain one of the two users from the original friendship pair. As such, for positive sample (u, a), the negative samples will belong to the set:
S(u, a) = (uu',a) w' E V) [(u, a') a' E V).
where is the set of nodes. This is similar to the setting used for knowledge graph completion (KGC) 38 which uses all such samples for evaluation. However, one drawback of evaluating each
7

---

Table Results on Cora, Citeseer, and Pubmed (%) under HeaRT. Highlighted are the results ranked first, second, and third.
Cora
Citeseer
Puhmed
Models
MRR
Hits@
MRR
Hits
MRR
Hits @
9.78
20.11
2.28
4.78
AA
11.91
24.10
10.82
22.20
2,63
5.51
Heuristic
RA
11.81
24.48
10.84
22.86
2.47
4.9
Shortest Path
5.04
15.37
5.83
16.26
0.86
0.38
Katz
11.41
22.77
11.19
24.84
3,01
5,98
Node2Vec
14.47 0.60
32.77 + 1.29
21,17 1.01
45.82 4: 2.01
3.94 = 0.24
8.51 4 0.77
Embedding
6.20
15.26 3.39
7.80
16.72 = 1.99
4,46 0.32
9.42
MLP
0..52
31.01 1.71
22.62
1.79 48.02
6.41 0.25
15.04 0.67
GCN
0,330
36,26 1.14
21.09
0.88
47.23 + 1,88
7.13 = 0.27
15.22 # 0.57
GNN
GAT
0..84
32.89
1.27
19.58 0.84
45,30 +: 1.3
4,95 0.14
9.99 + 0.64
SAGE
0.674
34.65
1.47
21.09 1.15
48.75 1.85
0.70
20.54 1.40
GAE
0.43
1.24 37.95
0.82 25.25
49.65 a: 1.48
5.27 0.25
10,50 + 0.46
SEAL
10.67:3.44
24.27 = 6.74
13.16 1.66
27.37 + 3.20
5.88 0.53
12.47 = 1.23
BUDDY
+..59
30.40 1.18
22.84 0.36
48.35 +
7.56
16.78 + 0.53
Neo-GNN
13,95
31.27 0.72
17.34
41.74 1.18
7.74 0.30
17.88 0.71
GaN+Pairwise Info
NCN
14,66 0.95
35.14 1.04
28.65 + 1.21
$3.41 + 1.46
5.84 0.22
13.22 + 0.56
NCNC
1.00
36.70 1.57
24.10
53.72 0.97
8.58
18.81 1.16
NBFNet
13.56
31.12 0.75
14.29 0.80
31.39 + 1.34
>24h
>24h
PEG
15.73 0.39
36.03 a 0.75
21.01 0.77
45.56 4 1.38
4.4
8.70 = 1.26
positive sample against the entire set of possible corruptions is the high computational cost. To mitigate this issue we consider only utilizing small subset of S(u, a) during evaluation.
The key challenge is how to generate a subset of S(u, a). If we randomly sample from S(u, a), we risk only utilizing easy negative samples. This is one the issues of the existing evaluation set- ting (see Issue 2 in Section 4.1, whereby randomly selecting negatives, they unknowingly produce negative samples that are too easy. We address this by selecting the negative samples via combi- nation of multiple heuristics. Since heuristics typically correlate well with performance, we ensure that the negative samples will non-trivial classify. This is similar the concept of candidate generation 39 40), which only ranks subset of candidates that are most likely to be true.
An overview of the generation process is given in Figure For each positive sample, we generate K negative samples. To allow personalization to both nodes in the positive sample equally, we sample K/2 negatives with each node. For the heuristics, we consider RA 129 PPR [1], and feature similarity. A more detailed discussion on the negative sample generation is given in Appendix G It's important to note that our work centers specifically on negative sampling during the evaluation stage (validation and test). This is distinct from prior work that concerns the negatives sampled used
during the training phase 42 43 existing and HeaRT setting.
As such, the training process remains unaffected under both the
4.3 Results and Discussion
In this subsection present results when utilizing HeaRT. We follow the parameter ranges introduced Section 2.3 For all datasets we use K = 500 negative samples per positive sample during evaluation. Furthermore for ogbl-ppa only positive samples (100K each) for evaluation. This is because the large size of the validation and test sets (see Table in Appendix C) makes HeaRT prohibitively expensive.
small subset of the validation and test
The results are shown in Table 4 (Cora, Citeseer, Pubmed) and Table 5 (OGB). For simplicity, we only include the MRR and Hits@ 10 for Cora, Citeseer, Pubmed, and the MRR and Hits 20 for OGB, Additional results for other metrics can be found Appendix [ We note that most datasets, outside of ogbl-ppa, exhibit much lower performance than under the existing setting, This is though we typically use much fewer negative samples in the new setting, implying that the negative samples produced by HeaRT are much harder. We highlight the main observations below.
Observation Better Performance of Simple Models. We find that under HeaRT, "simple" base- line models (i.e., heuristic, embedding, and GNN methods) show greater propensity to outperform their counterparts via ranking metrics than under the existing setting. Specifically, we focus on MRR in Table I and 5 and the corresponding ranking- based metries in Table 2 Under the existing
8

---

Table Results on OGB datasets (%) under HeaRT. Highlighted are the results ranked first, second,
and third.
ogbl-coollab
ogbl-ddi
oghl-ppa
ogbl-citation?
Models
MRR
Hiis 20)
MRR
MRR
MRR
Hiiv@0 20
CN
12.60
27.51
6,71
38.69
25.70
68.25
17.11
41.73
AA
16.40
32.65
6.97
39.75
26.85
70.22
17.83
43.12
RA
28.14
41.16
8.70
44,01
28.34
71.50
17.79
43.34
Shortest Path
46.71
46.56
0
0.54
1.31
>24h
>24h
Katz
47.15
48.66
6.71
38.69
25,70
68.25
14.10
35.55
Vese
12.10 0.20
25.85 = 0.21
11.14 = 0.95
63.63 + 2.05
=
53.42 0.11
14.67 +
42.68
1..88:0..22 0.20
MF
26,86 :: 1.74
38.44
0.07
13,99 = 0.47
59.50 + 1.68 N/A
22.47
1.53
70.71 1 4.82
8.72 2,60
29.64
7.30
MLP
12.61 0.66
23,05
0.89
N/A
0.98 + 0.00
1.47 + 0.00
0.07
43.15
GCN
18.28 0.84
32.90 0.66
13,46 0.34
64.76 = 1.45
26.94 0.48
68.38 0.73
19.98 0.35
51.72 0.46
GAT
10.97 + 1.16
29.58
2.42
12.92 + 0.39
66.83 2.23
0OM
00M
00M
OOM
SAGE
20.89 1.06
33,83 0.93
12.60 0.72
67.19 + 1.18
27.27 0,30 0OM
69.49 0.43 0OM
22.05 0.12 OOM
53.13 0.15 ODM
GAR
0OM
0OM
3.49 1.73
17.81 9.80
SEAL
22.53
36.48 = 2.55
9.99 0.90
49.74 + 2.39
29.71 0.71
76.77
0,94
20.60 1.28
48.62 1.93
BUDDY
32.42 +: 1.88
45.62 0.52
12.43 + 0.50
58.71 = 1.63
27.70 17,70=1 0.33
71 50 0.68
19.17 0.20
47.81
0.37
21.90
10.86
16.12
43.17
NCN
17.51 2,50
37,07 = 2.97
12.86 0.78
65.82 + 2.66
35,06 #: 0.26
81.9 0.31
23.35 + 0.28
53.76 + 0.20
NCNC
>24h
82.24
NBENet
0OM
0OM
>24h
>24h
0OM
0OM
00M
OOM
PEG
15.68 1,10
29.74 0.95
12.05 1.14
6..12
0OM
0OM
00M
00M
setting, such methods only rank in the top three for any dataset total of 5 times. However, under HeaRT this occurs 10 times. Furthermore, under the existing setting only 1 "simple" method ranks best overall while under HeaRT there are 4. This suggests that recent advanced methods may have benefited from the easier negative samples in the existing setting.
Another interesting observation is that on ogbl-collab, heuristic methods are able to outperform more complicated models by large margin. Specifically, we find that Katz is the best ranked method, Shortest Path the second, and RA the fourth. Furthermore, the MRR gap between the second ranked method (Shortest Path) and the third (BUDDY) is very large 14.29 points. We observe that this result is caused by the dynamic nature of the graph, where node pairs that are linked in the training data may also be present positive samples in the test. We further expound on this observation in Appendix H
Observation 2: Lower Model Standard Deviation. We observed earlier that, under the existing evaluation setting, the model variance across seeds was high (see observation 3 in Section 3). This complicates model comparison as the model performance is unreliable. Interestingly, we find that HeaRT is able to dramatically reduce the variance for all datasets. We demonstrate this by first calculating the mean standard deviation across all models on each individual dataset. This was done for both evaluation settings with the results compared. As demonstrated in Table 6 the mean standard deviation decreases for all datasets. This is especially true for Cora, Citeseer, and Pubmed, which each decrease by over 85%. Such a large decrease in standard deviation is noteworthy as it allows for a more trustworthy and reliable comparison between methods.
We posit that this observation is caused by stronger alignment between the positive and negative samples under our new evaluation set- ting. Under the existing evaluation setting, the same set of negative samples is used for all pos- itive samples. One consequence of this is that a single positive sample may bear little to no relationship to the negative samples (see Sec- tion 4.1 for more discussion). However, under our new evaluation setting, the negatives for positive sample are subset of the corruptions of that sample. This allows for a more natu- ral comparison via ranking- based metrics as the samples are more related and can be more eas- ily compared.
Table 6: Mean model standard deviation for the existing setting and HeaRT. We use Hits@20 for ogbl-ddi, Hits @ 50 for ogbl-collab, Hits @ 100 for ogbl-ppa, and MRR otherwise.
Dataset
Existing
HeaRT
% Change
Cora
5.19
0.79
-85%
Citeseer Pubmed
5.94
0.88
-85%
4.14
0.35
-92%
ogbl-collab
1.49
0.96
-36%
ogbl-ppa
2.13
0.36
-83%
ogbl-ddi
6.77
3,49
.4%%
oghl-citation2
1.39
0.59
-58%

---

Observation 3: Lower Model Performance. We observe that the majority of datasets exhibit significantly reduced performance comparison the existing setting. For example. under the existing setting, models typically achieve a MRR of around 30, 50, and 30 on Cora, Citeseer, and Pubmed (Table D. respectively. However, under HeaRT the MRR for those datasets is typically around 20, 25, and 10 (Table 4 Furthermore for ogbl-citation2, the MRR of the best performing model falls from a shade under 90 on the existing setting to slightly over 20 on HeaRT. Lastly, we note that the performance subset of the total test set when evaluating on HeaRT, nullifying any comparison between the two settings.
ogbl-ppa actually increases. This is because we only utilize small
These outcomes are observed despite HeaRT using much fewer negative samples than the original setting. This suggests that the negative samples generated by HeaRT are substantially more chal- lenging than those used the existing setting. This underscores the need to develop more advanced methodologies that can tackle harder negatives samples like in HeaRT.
Conclusion
In this work have revealed several pitfalls found in recent works on link prediction. To overcome these pitfalls, we first establish a benchmarking that facilitates a fair and consistent evaluation across diverse set of models and datasets. By doing so, we are able to make several illuminating obser- vations about the performance and characteristics of various models. Furthermore, based on several limitations we observed the existing evaluation procedure, we introduce more practical setting called HeaRT (Heuristic Related Sampling Technique). HeaR'T' incorporates more real-world eval- uation setting, resulting better comparison among methods. By introducing more rigorous and realistic assessment, HeaRT could guide the field towards more effective models, thereby advancing the state of the art link prediction.
6 Acknowledgements
This research is supported by the National Science Foundation (NSF) under grant numbers CNS 2246050, IIS IIS1845081, IS2221202,, I182212144. IOS2107215, DUE 2234015, III-2212145, III- 2153326, DRL2025244 and IOS2035472, the Army Research Office (ARO) under grant num- ber 191- the Home Depot, Cisco Systems Inc, Amazon Faculty Award, John- son&Johnson, JP Morgan Faculty Award and SNAP.
References
[1] Linyuan Lü and Tao Zhou Link prediction in complex networks: survey. Physica A: statistical mechanics and its applications, 390(6): 150-1170, 2011.
[2] Nur Nasuha Daud, Siti Hafizah Ab Hamid, Muntadher Saadoon, Firdaus Sahran, and Nor Badrul Anuar. Applications of link prediction in social networks: review. Journal of Network and Computer Applications, 166: 102716, 2020.
[3] István A Kovács, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Dac-Kyum Kim, Nishka Kishore, Tong Hao, et al. Network-based prediction of protein interactions. Nature communications, 10(1):1240, 2019.
[4] Zan Huang, Xin Li, and Hsinchun Chen. Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM/IEEE- CS joint conference Digital libraries, pages 141-142,
2005.
[5] Zonghan WU, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4 (::4)))44444 22, 2020.
[6] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 18881100868. 2018
10

---

[7] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Proceedings of the 8th International Con- ference on Learning Representations (ICLR), 2020.
[8] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations.
[9] Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Sharifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 48: 8845, 2021.
[10] Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re- evaluation of knowledge graph completion methods. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics, pages 5516-5522, 2020.
[11] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
[12] Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. Advances in neural information processing systems, 31, 2018.
[13] Benjamin Paul Chamberlain, Sergey Shirobokov. Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. arXiv preprint arXiv:2209. 15486, 2022.
[14] Seongjun Yun, Scoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34:13683-13694, 2021.
[15] Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.00890. 2023.
[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[17] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learn- ing with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[18] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:20, 2017.
[19] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-fort networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29490, 2021.
[20] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 161.v:1611.07308, 2016.
[21] Yang Yang. Ryan N Lichtenwalter, and Nitesh V Chawla. Evaluating link prediction methods. Knowledge and Information Systems, 45(3):751-782, 2015.
[22] Zexi Huang, Mert Kosan, Arlei Silva, and Ambuj Singh. Link prediction without graph neural networks. arXiv preprint 2rXiv:2305.13653 2023.
[23] Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. In Joint european conference on machine learning and knowledge discovery in databases, pages 437- 452. Springer, 2011.
[24] David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge manage- ment, pages 556-559, 2003.
11

---

[25] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.
[26] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9077 2021.
[27] Mark EJ Newman, Clustering and preferential attachment in growing networks. Physical review E, 64(2):025102, 2001.
[28] Lada Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211-230 2003.
[29] Tao Zhou, Linyuan Lüi, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal
71::6 71:623 630, 2009.
[30] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-44 1953.
[31] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[32] Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classi- fication. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7370-7377, 2019.
[33] Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint arXiv:2203.00199 2022.
[34] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18-22133, 2020.
[35] Jesse Davis and Mark Goadrich. The relationship between precision-rectt reccll and roc curves. In Proceedings of the 23rd international conference on Machine learning, pages 233-240, 2006.
[36] Takaya Saito and Marc Rehmsmeier. The precision-recall plot is more informative than the roc plot when evaluating binary classifiers on imbalanced datasets. PloS one, (0())=01184332. 2015.
[37] Zhitao Wang, Yong Zhou, Litao Hong, Yuanhang Zou, Hanjing Su, and Shouzhi Chen. Pair- wise learning for neural link prediction. arXiv preprint arXiv:21 12.0296, 2021.
[38] Antoine Bordes, Nicolas Usunier, Alberto Carcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
[39] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. Wtf: The who to follow service at twitter. In Proceedings of the 22nd international conference on World Wide Web, pages 505-514, 2013.
[40] Chantat Eksombatchai, Pranav Jindal, Jenry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. Pixie: A system for recommending 3+ billion items 200+ million users in real-time. In Proceedings of the 2018 world wide web conference, pages 1775-1784, 2018.
[41] Sergey Brin and Lawrence Page. The anatomy of large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7):007-117, 1998.
[42] Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Under- standing negative sampling in graph representation learning. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1666-1676, 2020.
12

---

[43] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the Twenty-Fifth Conference Uncertainty in Artificial Intelligence, pages 452-461, 2009.
[44] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6909, 2014.
[45] JC de Borda. M'emoire sur les' elections au scrutin. Histoire de l'Acad' emie Royale des Sciences, 1781.
13

---

7 Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix[] L
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments (e.g. for benchmarks)...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] See https://github. cwm/ hatm//Jannii//HHee /HeaRR
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Yes. See Section 2.3 and Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
4. If you are using existing assets (e-g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix J
(c) Did you include any new assets either the supplemental material or as URL? [Yes] See https: //gpts////ttb..../ com/ Juanhui 28/HeaRT
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "QCl11Ur93A", "reviewer": "Reviewer_vjFt", "summary": "", "questions": "", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "Review experiments* like these are always useful and powerful contributions and should be lauded as a key contribution to the field. (Ideally, every subfield of machine learning should regularly re-test its state-of-the-art models).\n\nMaking the evaluation more realistic and challenging is also a sound contribution. This is clear from the fact that KG models are already evaluated in a way similar to what the authors propose.\n\n* That is, experiments, which introduce no new models, but take a set of published models and redo their training under uniform circumstances for a fair comparison.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "We6qFb7h5N", "reviewer": "Reviewer_rGWc", "summary": "", "questions": "", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. The writing is overall clear. The overall organization is satisfying.\n2. The introduced observations and the solutions are reasonable.\n3. The experimental results are comprehensive and can basically reflect the claims in the paper.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "grvvoNEDe7", "reviewer": "Reviewer_P7Ue", "summary": "", "questions": "", "limitations": "L1. It is inappropriate to make benchmark existing methods by changing their pretraining setting, the ratio between positive/negative samples, and their negative sampling technique, because those existing methods are designed based on those pretraining settings, the positive/negative sampling ratio, and the negative sampling technique. \nIn this sense, it is reasonable that the accuracies for BUDDY and Neo-GNN decrease, if we change their pretraining setting and the positive/negative sampling ratio.\n\nL2. Efficiency in the test phase is important in practice. In that sense, the proposal (HeaRT) may not be practical as the paper described, \"the large size of the validation and test sets (see Table 7 in Appendix B) makes HeaRT prohibitively expensive\".", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "S1. The study conducts various experiments using seven representative datasets and 19 existing techniques. Through experiments, it reveals the shortcomings of existing benchmarks, including cases where higher accuracy is achieved than reported in the original papers, large standard deviations in accuracy, inconsistencies between evaluation metrics such as AUC and Hits@K, and the issues with using accuracy reported in the original papers.\n\nS2. Evaluating using multiple metrics is valuable. Particularly, Hits@K is a more appropriate evaluation metric, since AUC does not provide the metric from users' perspective.\n\nS3. Categorizing existing techniques into four types (Heuristic, embedding, GNN, GNN+pairwise info) is appropriate and clear.\n\nS4. Through the benchmarking experiments using the proposed negative sampling technique, this study gives new insights on existing methods. Notably, some heuristic methods outperform the latest techniques such as GNN in ogbl-collab. Additionally, a significant reduction in the standard deviation of accuracy is achieved.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "DVSGYXKaeW", "reviewer": "Reviewer_dRZC", "summary": "", "questions": "", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. The paper finds several important pitfalls in the link prediction tasks with suitable solution\n2. The proposed evaluation setting is more aligned with the real-world scenario.\n3. Comprehensive experiments indicate the new potential provided in the link prediction domain. ", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "9H51Lj7bBE", "reviewer": "Reviewer_KDed", "summary": "", "questions": "", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. The paper unveal an important but unfounded positive and negative edge issue on the evaluation of link prediction problem\n2. The paper propose a new evaluation setting more aligning with the real-world scenario.\n3. Comprehensive experiments indicate the new potential provided in the link prediction domain. ", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: Paper addresses an important task (link prediction) with a variety of applications. Classifying a positive edge VS random is an easy task. However, in reality, e.g., in recommender systems, the model should be able to rank positives (few) over N^2 negatives (can be in the millions or billions). This paper bridges some of that gap, by creating a more-realistic link prediction evaluation benchmark with harder negatives.
Decision: Accept (Poster)