PaperlayerView exact revision on arXiv

Source-linked AI summary

Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking

Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma, Neil Shah, Jiliang Tang, Dawei Yin

arXiv:2306.10453v3cs.LGcs.SI

TL;DR

Recent link-prediction methods lack careful evaluation amid underreported results, inconsistent settings, and easy negatives. The authors benchmark methods under shared settings and introduce HeaRT; under this setting, simple methods rank among the top performers more often, while model variance falls across datasets.

  • Problem

    Recent GNN-based link-prediction methods lack careful examination, while existing evaluations include underreported results, inconsistent settings, and easy negatives.

    Source: §1 · p. 1, §4.1 · p. 7

  • Method

    The authors benchmark methods under shared settings and introduce HeaRT, which ranks each positive against a limited set of heuristic-selected hard corruptions.

    Source: §1 · p. 3, §4.2 · pp. 7–8

  • Results

    Under HeaRT, simple methods appear in the top three twice as often as under the existing setting, and mean standard deviation decreases across all datasets.

    Source: §4.3 · pp. 8–9

  • Takeaways & Limitations

    HeaRT’s negatives remain substantially more challenging despite using fewer samples, motivating methods that can tackle harder negatives.

    Source: §4.3 · p. 10

Abstract

from arXiv · show

Link prediction attempts to predict whether an unseen edge exists based on only a portion of edges of a graph. A flurry of methods have been introduced 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 pitfalls currently exist that hinder our ability to properly evaluate these new methods. These pitfalls mainly include: (1) Lower than actual performance on multiple baselines, (2) A lack of a unified data split and evaluation metric on some datasets, and (3) An unrealistic evaluation setting that uses easy negative samples. To overcome these challenges, we first conduct a fair comparison across prominent methods and datasets, utilizing the same dataset and hyperparameter search settings. We then create a more practical evaluation setting based on 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 implementation and data are available at https://github.com/Juanhui28/HeaRT

1 Introduction

Link prediction methods for GNNs have proliferated, but recent methods lack a careful, comprehensive evaluation. The paper identifies underreported performance, inconsistent settings, and easy negative samples, then benchmarks methods fairly and proposes HeaRT.

1 Introduction

  • Existing link prediction evaluations face underreported model performance, inconsistent dataset splits and metrics, and easy negative samples.These pitfalls hinder reliable comparisons of current methods.Source: §1 · pp. 1–2
  • On ogbl-collab, tuning raises Neo-GNN’s Hits@50 by around 8.5 points over its originally reported performance.The paper reports that Neo-GNN then achieves the best overall ogbl-collab performance in its study.Source: §1 · p. 2
  • The authors conduct a fair, reproducible comparison across methods and datasets using shared hyperparameter settings and multiple evaluation metrics.For Planetoid datasets, they also use a unified data split.Source: §1 · pp. 2–3
  • HeaRT evaluates each positive against a limited set of hard, heuristic-selected corruptions that share one of its nodes.The authors propose it as a more realistic and challenging alternative to the existing negative-sampling evaluation.Source: §1 · p. 3

2 Preliminaries

The paper formulates link prediction as estimating whether two nodes are linked, reviews heuristic, embedding, GNN, and combined methods, and specifies its datasets and evaluation settings.

2.1 Task Formulation

  • Link prediction estimates the likelihood of an edge between two nodes from graph structure and node features.The paper represents the estimated probability for a node pair as p(u, v).Source: §2.1 · p. 3

2.2 Link Prediction Methods

  • The study groups methods into heuristics, embeddings, GNNs, and GNNs augmented with pairwise or subgraph information.Heuristic methods use graph structure or paths, while GNNs integrate multi-hop structure through message passing.Source: §2.2 · pp. 3–4

2.3 Datasets and Experimental Settings

  • Experiments cover homogeneous Cora, Citeseer, Pubmed, and four OGB datasets, using AUC and ranking metrics with dataset-specific settings.The authors grid-search hyperparameters, with narrower fixed ranges for large OGB datasets, and use one negative per positive during training.Source: §2.3 · p. 4

3 Fair Comparison Under the Existing Setting

Under the existing evaluation setting, the study finds that tuned methods can outperform previously reported results, while results vary across datasets and metrics. It also reports high seed variance and divergence between AUC and ranking-based metrics.

3 Fair Comparison Under the Existing Setting

  • 66.13 versus 57.52: Neo-GNN achieves the best ogbl-collab test Hits@50 in this study, compared with its reported result.The authors attribute the lower reported result to the original study’s omission of validation edges during testing.Source: §3 · p. 5, Table 2 · p. 5
  • Tuned GAE [20] reaches the second-best Citeseer MRR, while GCN reaches the third-best ogbl-ddi Hits@20.The paper says conventional baselines generally perform better than originally reported across datasets.Source: §3 · p. 5, Table 3 · p. 6
  • 29.60 versus 78.51: BUDDY [13] achieves a lower-than-reported Hits@20 on ogbl-ddi under the study’s one-negative training and no-pretraining comparison.The authors also report that weak validation-test relationships complicate hyperparameter tuning for other methods.Source: §3 · p. 6
  • Ranking-metric standard deviations reach 8.82, 8.96, and 7.75 for MRR on Cora, Citeseer, and Pubmed, respectively.The authors say high variance makes comparisons and replication more difficult.Source: §3 · p. 6
  • Shortest Path has Hits@K of 0 on ogbl-ppa despite an AUC above 99%, illustrating divergence between AUC and ranking metrics.The paper notes prior arguments that AUC is unsuitable for highly imbalanced link-prediction problems.Source: §3 · p. 6

4 New Evaluation Setting

Section 4 critiques global random negatives as mismatched to real-world link prediction and often easy, then introduces HeaRT’s personalized heuristic sampling. Under HeaRT, most datasets show lower performance and model variance falls.

4.1 Issues with the Existing Evaluation Setting

  • The existing setting reuses global negatives, which can be unrelated to each positive pair, and random negatives are often trivial because they have no common neighbors.Source: §4.1 · p. 7

4.2 Heuristic Related Sampling Technique (HeaRT)

  • HeaRT samples from endpoint corruptions of each positive and uses multiple heuristics to select a hard subset, splitting K evenly across its two endpoints.The considered heuristics include RA, PPR, and feature similarity; the full corruption set is avoided because evaluating against it is computationally costly.Source: §4.2 · pp. 7–8

4.3 Results and Discussion

  • Most datasets show significantly lower performance under HeaRT than the existing setting despite typically using fewer negative samples; ogbl-ppa instead improves, but its small test subset nullifies comparison.Source: §4.3 · pp. 8, 10
  • Simple models rank in the top three 10 times under HeaRT versus 5 under the existing setting, and rank best overall 3 versus 1 times.Source: §4.3 · pp. 8–9
  • On ogbl-collab, Katz ranks second and RA third, showing strong heuristic performance against more complicated models.Both Katz and RA incorporate common-neighbor information, or paths of length 2; ogbl-collab is a dynamic collaboration graph with a somewhat different negative-sampling strategy.Source: §4.3 · p. 9
  • Mean model standard deviation falls under HeaRT on every dataset, by over 85% on Cora, Citeseer, and Pubmed, improving comparison reliability.Table 6 reports Hits@20 for ogbl-ddi, Hits@50 for ogbl-collab, Hits@100 for ogbl-ppa, and MRR otherwise.Source: Table 6 · p. 9, §4.3 · p. 9

5 Conclusion

The paper identifies pitfalls in link-prediction evaluation, establishes a fairer benchmark, and introduces HeaRT as a more practical evaluation setting. The authors argue that HeaRT supports better comparisons and could guide development of more effective models.

5 Conclusion

  • The study establishes a fair and consistent benchmark across diverse link-prediction models and datasets.It reports observations about models’ performance and characteristics.Source: §5 · p. 10
  • HeaRT introduces a more practical, real-world evaluation setting based on limitations observed in existing evaluation.The authors say it results in a better comparison among methods.Source: §5 · p. 10
  • The authors propose that rigorous, realistic assessment could guide the field toward more effective link-prediction models.Source: §5 · p. 10

7 Checklist

The appendix documents checklist responses and supporting material on common-neighbor distributions, evaluation metrics, and negative sampling. It contrasts existing and HeaRT sampling patterns and specifies how samples and ranks are used.

7 Checklist

  • The checklist reports that code, data, and experimental details are available, while human-subject items are marked not applicable.It also affirms reporting limitations and potential negative societal impacts, with references to appendices.Source: §7 · p. 14

A Common Neighbor Distribution

  • Under existing evaluation, most negative samples in ogbl-collab, ogbl-ppa, and ogbl-citation2 have no common neighbors, making them easy to identify with that heuristic.Figure 3 extends the distribution comparison to Cora, Citeseer, Pubmed, and ogbl-ddi.Source: A Common Neighbor Distribution · p. 15, Figure 3 · p. 15
  • Unlike the other datasets, ogbl-ddi’s negative samples mostly have common neighbors; its average degree is 625.68, versus 105.25 for ogbl-ppa.The authors attribute this pattern as likely related to ogbl-ddi’s greater density.Source: A Common Neighbor Distribution · p. 15
  • HeaRT’s common-neighbor distribution is more aligned with positive samples, reducing the advantage for models that use common-neighbor information.Figures 4 and 5 show the distributions for Planetoid and OGB datasets, respectively.Source: A Common Neighbor Distribution · p. 15, Figure 4 · p. 16, Figure 5 · p. 16

B.1 Evaluation Metrics

  • Hits@K measures whether a positive sample ranks within the top K, while MRR averages reciprocal ranks across positive samples.A rank of 1 means the positive sample scores above all negatives.Source: §B.1 · pp. 15–16
  • AUC measures the likelihood that a positive sample ranks above a random negative sample.The formula compares positive and negative sample ranks.Source: §B.1 · p. 16

B.2 Negative Sampling

  • Training negatives are random node pairs, typically with one negative generated per positive sample.The sampling procedure selects each node uniformly from the graph’s node set.Source: §B.2 · p. 17
  • Existing evaluation reuses the same random negative set for each positive, except ogbl-citation2, which evaluates each positive against 1,000 corruptions containing one of its nodes.Source: §B.2 · p. 17

C.1 Datasets

The experiments cover homogeneous graphs ranging from smaller Planetoid datasets to larger OGB datasets, with dataset-specific splits and training procedures. The appendix details shared optimization choices, hyperparameter-search constraints, and selected model-specific adjustments.

C.1 Datasets

  • The benchmark is limited to homogeneous graphs: Cora, Citeseer, Pubmed, and four larger OGB datasets.Cora, Citeseer, and Pubmed use an 85/5/10 train/validation/test split; OGB uses its fixed benchmark splits.Source: §C.1 · p. 17

C.2 Experimental Settings

  • Models use binary cross-entropy optimized with Adam and one randomly sampled training negative per positive.Source: §C.2 · p. 17
  • Training can run up to 9,999 epochs, stopping when validation performance fails to improve across a dataset- and model-dependent number of checkpoints.Checkpoint patience is generally 50 for smaller datasets, 100 for simpler methods on larger OGB datasets, and 20 for advanced methods; exceptions are specified.Source: §C.2 · p. 17
  • Hyperparameter searches are larger for smaller graphs; OGB searches fix several settings, and ogbl-citation2 uses embedding size 128 because of GPU memory constraints.The fixed OGB settings include weight decay, model and prediction layer counts, and embedding dimension.Source: §C.2 · pp. 17–18
  • When search ranges cause substantial degradation, selected settings follow published source-code recommendations, including adjustments for PEG, NCN/NCNC, NBFNet, and SEAL.For example, NCNC pretraining is omitted on ogbl-ddi to facilitate a fair comparison.Source: §C.2 · p. 18
  • For BUDDY on ogbl-ppa, the experiments use RA and normalized degree as input features and exclude raw node features.This follows the authors’ published optimal hyperparameters.Source: §C.2 · p. 18

D Reported vs. Our Results on ogbl-ddi

The appendix compares reported and reproduced ogbl-ddi results and investigates validation–test alignment. Under the existing setting, validation performance is a poor guide to test performance for the examined methods; the figure caption reports a stronger relationship with HeaRT.

D Reported vs. Our Results on ogbl-ddi

E Additional Investigation on ogbl-ddi

E.1 Existing Evaluation Setting

  • For NCN on ogbl-ddi, validation performance of 70 can correspond to test performance from 3 to 80, illustrating poor validation–test alignment.The investigation records checkpoints over 10 seeds using each model’s reported hyperparameters; the authors say the cause needs further investigation.Source: §E.1 · p. 19, Figure 6 · p. 19

E.2 New Evaluation Setting

Under the new evaluation setting, validation and test performance show a better relationship than under the existing setting. The authors conjecture that tailoring negatives to each positive may make the comparisons more natural.

E.2 New Evaluation Setting

  • The new setting shows a much better relationship between validation and test performance than the existing setting, including on ogbl-ddi.Figure 7 plots validation and test performance by checkpoint for various models; the comparison is with Figure 6.Source: §E.2 · pp. 19–20
  • Additional existing-setting results are presented for Cora and Citeseer in Tables 10 and 11.The table captions identify the datasets and evaluation setting but do not provide result values here.Source: Table 10 · p. 20, Table 11 · p. 20
  • The authors conjecture that tailoring negatives to each positive makes comparison with its negatives more natural, possibly strengthening validation–test alignment.They state that the cause of the poor relationship under the existing setting is unclear.Source: §E.2 · p. 20

F Additional Results Under the Existing Setting

This material adds existing-setting results and details how HeaRT generates and ranks hard negatives. The procedure combines multiple heuristic rankings to select negatives for each positive sample.

F Additional Results Under the Existing Setting

G Additional Details on HeaRT

  • HeaRT generates K corruptions per positive sample, splitting them evenly between its two nodes.The candidates are drawn from S(a, b); multiple heuristics are used to select difficult negatives.Source: G Additional Details on HeaRT · p. 21

G.1 Determining Hard Negative Samples

  • The negative-sample heuristics combine local resource allocation, global personalized PageRank, and feature similarity on Cora, Citeseer, and Pubmed; candidate filtering also varies for dynamic ogbl-collab.Filtering excludes positive training samples, self-loops, and the sample itself, with validation positives also excluded for test negatives except under the stated ogbl-collab strategy.Source: §G.1 · p. 22

G.2 Combining Heuristic Ranks

  • HeaRT combines heuristic ranks using the minimum rank across heuristics, then selects the top K/2 nodes; insufficient candidates are filled randomly.The minimum aggregation is intended to capture distinct samples, particularly when heuristics disagree.Source: §G.2 · p. 22

H Additional Results Under HeaRT

The appendix presents further HeaRT results and illustrates the negative-sample generation algorithm. These results include hit metrics not shown in the main tables.

H Additional Results Under HeaRT

I Additional Investigation on ogbl-collab

The ogbl-collab investigation shows how treating a dynamic collaboration graph affects hard-negative evaluation, while the paper notes a potential efficiency cost for HeaRT. The paper also describes potential societal benefits and reports no apparent risk.

I Additional Investigation on ogbl-collab

  • For ogbl-collab, past collaborations may be negatives for future predictions: the task predicts 2019 collaborations from 2017 training and 2018 validation data.Source: I Additional Investigation on… · p. 23
  • When test negatives exclude positive train/validation samples, Shortest Path and Katz perform well; around 46% of test positives also appear in training, creating a direct-link shortcut.Under that setting, the MRR gap between second-ranked Shortest Path and third-ranked BUDDY is 14.29.Source: I Additional Investigation on… · pp. 23–24, Table 16 · p. 24
  • Allowing train/validation positives among HeaRT test negatives removes Shortest Path’s superior performance; Table 5 MRR values all exceed 10, versus approximately 6 as the highest MRR in Table 16.The authors conclude that excluding those positives disproportionately helps Shortest Path.Source: I Additional Investigation on… · pp. 24–25, Table 15 · p. 24

K Limitation

  • Customized negatives per positive may increase evaluation cost, especially with many positives, although independent node pairs permit parallelization.Source: K Limitation · p. 25

L Social Impact

  • The authors state that HeaRT aligns evaluation more closely with real-world scenarios and report no apparent risk related to their work.Source: L Social Impact · p. 25

Related papers

Loading 2306.10453v3…