Towards Understanding Link Predictor Generalizability Under Distribution Shifts

Authors: Jay Revolinsky, Harry Shomer, Jiliang Tang
Primary area: datasets and benchmarks
Keywords: Link Prediction, Graph-Structured Data, GNN4LP, Distribution Shifts, Structural Heuristics, Splitting Strategies

Abstract:
State-of-the-art link prediction (LP) models demonstrate impressive benchmark
results. However, popular benchmark datasets often assume that training, validation, and testing samples are representative of the overall dataset distribution. In
real-world situations, this assumption is often incorrect; since uncontrolled factors
lead to the problem where new dataset samples come from different distributions
than training samples. The vast majority of recent work focuses on dataset shift
affecting node- and graph-level tasks, largely ignoring link-level tasks. To bridge
this gap, we introduce a novel splitting strategy, known as LPShift, which utilizes
structural properties to induce a controlled distribution shift. We verify the effect of LPShift through empirical evaluation of SOTA LP methods on 16 LPShift
generated splits of Open Graph Benchmark (OGB) datasets. When benchmarked
with LPShift datasets, GNN4LP methods frequently generalize worse than heuristics or basic GNNs. Furthermore, LP-specific generalization techniques do little
to improve performance under LPShift. Finally, further analysis provides insight
on why LP models lose much of their architectural advantages under LPShift.

Decision: reject
Reviewer scores: 5, 6, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1729044396001

thread_type:
official_review

<thread_object>
creator: reviewer_ryku

<content>
summary:
This paper investigates the distribution shift issues on LP tasks on the graph, where the links in training, validation, and testing sets may be drawn from different distributions. The authors introduce a graph edge splitting method LPShift, which can artificially create a split with distribution shift. Three traditional LP methods are selected as the metrics to perform the LPShift: CN, Shortest-Path, and Preferential Attachment. LPShift is applied to OGB datasets: Collab and PPA to generate a set of new splits. By evaluating the LP methods' performance on these new splits, the authors conclude that current LP methods are sensitive to the distribution shift problem, and advocate for further exploration on this issue.

strengths:
[S1] The paper is easy to read. It has a clear demonstration of the problem setup, methods, experiments, and conclusions.

[S2] Different from previous distribution shift studies, this paper identifies the issue of LP tasks, which is novel.

[S3] The experiment shows that LPShift can effectively cause a distribution shift problem for current SOTA LP methods.

weaknesses:
[W1] My major concern is whether the study has any practical merit. It is unknown if the distribution shift problem for LP tasks (widely) exists in the existing benchmarks. Instead, in this paper, the problem is artificially created and identified by manually creating such a dataset. There is Collab that has such an issue, but it is already reported in [1], with a very similar plot. It would be more convincing if the authors could show and identify more existing datasets that suffer from such an issue.

[W2] The experimental results are confusing. Table 1 uses Hits@20 as the metrics to rank models, but Table 7/8 uses MRR for actual performance. If both metrics have to be applied here, then they should both have the same set of tables (ranking table as of table 1, actual performance table as of table 7) for a clear demonstration.

[W3] The relative comparison among LP methods in Table 1 can be misleading. The authors attempt to conclude that simpler methods with Collab can perform better because GNN4LP struggles to generalize due to the structural shift induced by LPShift. However, the LPShift also uses HeaRT[2] to generate negative samples. And under the HeaRT setting alone, simpler methods like RA can already perform better than GNN4LP. This leads to confusion about whether it is the HeaRT or LPShift that causes GNN4LP to fail to generalize.

Minor issues:

* Authors use "inverse split" and "backward split" interchangeably, which causes confusion.


[1] Neural Common Neighbor with Completion for Link Prediction.

[2] Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking.

questions:
[Q1] Link-MoE [3] uses a set of link predictors as experts to perform LP tasks and achieves SOTA performance. Given that the authors show that different methods have different capabilities to handle distribution shift, will a mixture of experts model help with the issue by integrating strengths of different models together?

[Q2] Since CN, SP, and PA are selected as the metrics for LPShift, it would be interesting to include SP and PA and see how they work under the shifting, similar to RA.

[Q3] Follow up on W1, if Collab already shows a distribution shift issue, is it necessary to further manually corrupt the dataset?

[3] Mixture of Link Predictors.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729286262308

thread_type:
official_review

<thread_object>
creator: reviewer_15w6

<content>
summary:
This paper benchmarks the generalizability of LP models under distribution shifts, which is often neglected in link-level tasks. It introduces a dataset splitting strategy called LPShift, which uses structural properties to induce distribution shifts, enabling the study of LP model performance under such conditions. The authors evaluate various LP models and generalization techniques on 16 LPShift-generated dataset splits. The paper concludes that structural shifts significantly impact LP model performance, advocating for further exploration of generalization techniques.

strengths:
1. The problem of link prediction under distribution shifts is not fully explored, and the paper has the potential to bridge the important gap.
2. The proposed LPShift strategy can be applied to real-world datasets, offering a practical tool for researchers to evaluate the generalization of LP models in realistic scenarios.
3. Many experimental results are provided showing the limitations of current LP-specific generalization methods.

weaknesses:
1. The writing is problematic with many grammar errors and confusing sentences. For example, the CN example in the introduction confuses me without a specific source node and target node context. What is a "red" graph? Line 52: requires $\rightarrow$ require.
2. All splits are based on statistical heuristics without any real-world shift splits, e.g., temporal shift, which produces not enough the significance.
3. Traditional generalization baselines are missing, e.g., IRM, VREx, etc. It is not sure whether not LP specific methods can already solve the LP OOD problem.
4. The hyper-parameter sweeping space is not large enough to produce significant experimental conclusions.
5. As a benchmark, no code is provided.

questions:
1. Why are the proposed splits significant? For example, if a generalization method works well on your split, which real OOD problem can the method solve? Can you provide experiments and discussions to validate that?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730700159158

thread_type:
official_review

<thread_object>
creator: reviewer_xf2u

<content>
summary:
This paper proposes a new problem related to data distribution shift in link prediction. To address this, this paper introduces a novel splitting strategy called LPShift to create benchmark data for distribution shift in link prediction. The proposed dataset is used to evaluate current link prediction methods and analyze why these models exhibit weaknesses.

strengths:
The paper proposes a method to introduce distribution shift in link prediction.

By evaluating various methods across multiple benchmarks, it demonstrates that existing models are vulnerable to distribution shifts in link prediction.

Through several analyses, the authors aim to show the effectiveness of the proposed method for inducing distribution shift and to explain why there is a drop in model performance.

weaknesses:
1. The most critical issue is the lack of clarity on why distribution shift is necessary in link prediction and what realistic scenarios justify this need. Can’t we consider changes in edge connections as changes at the graph level? How does graph-level distribution shift differ from this? It would be beneficial to provide specific scenarios that demonstrate the importance of this problem. Without this, it might seem like the issue is being created without a clear purpose.

2. It’s unclear whether this problem is genuinely challenging. In Table 2 for DropEdge and TC (ogbl-ppa), the mean change in performance is marginal, ranging from -1% to +4%. Additionally, in Tables 1 and 7, simple RA and GCN show strong performance. 
While these results may highlight limitations of LP methods, could you further explain why this new problem is challenging and why there is a need to advance methods to address it?

3. As a minor suggestion, placing citations within parentheses would enhance readability.

questions:
Please refer to W1 and W2.

1. The most critical issue is the lack of clarity on why distribution shift is necessary in link prediction and what realistic scenarios justify this need. --> Regarding this, please refer to following questions to better justify the importance and novelty of the proposed work:
(1) Provide concrete examples of real-world scenarios where link prediction models face distribution shifts.
(2) Clarify how the proposed distribution shift differs from or relates to graph-level changes.
(3) Explain more explicitly why existing graph-level distribution shift benchmarks are insufficient for link prediction tasks.

2. It’s unclear whether this problem is genuinely challenging. In Table 2 for DropEdge and TC (ogbl-ppa), the mean change in performance is marginal, ranging from -1% to +4%. Additionally, in Tables 1 and 7, both Simple RA and GCN show strong performance. 
While these results may highlight limitations of LP methods, could you further explain why this new problem is challenging and why there is a need to advance methods to address it?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745173451

thread_type:
official_review

<thread_object>
creator: reviewer_dnus

<content>
summary:
The paper introduces a dataset-splitting strategy to assess the generalizability of the link prediction models under distribution shifts. LPShift utilizes three structural metrics—Common Neighbors, Shortest Path, and Preferential Attachment—to induce shifts, creating training, validation, and testing sets with distinctive structural properties. The empirical results reveal that GNN4LP models perform poorly under LPShift, with simple heuristics sometimes outperforming complex models. The paper posits LPShift as a framework for studying distribution shifts in LP tasks and highlights the need for generalization methods.

strengths:
1. This paper tackles a compelling and timely research problem: handling complex distribution shifts in graph data for link prediction tasks, a topic of significant recent interest.
2. The splitting strategy is straightforward and well-explained, which is easy to understand.
3. The observations are inspiring to show the author’s motivations.

weaknesses:
1. The novelty is somewhat concerning to me since there is no comprehensive approach proposed.
2. The paper lacks detailed theoretical analyses to support their main claims.
3. I think this paper seems to be a technical report/benchmark paper instead of a research paper. The authors might address this concern by presenting a formal method rather than intuitive explanations to answer the presented questions.

questions:
I am curious what is the main difference among node-level graph OOD method and link-level graph OOD method?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730778159428

thread_type:
official_review

<thread_object>
creator: reviewer_qsyv

<content>
summary:
The paper investigates the generalizability of link prediction models under distribution shifts, a crucial problem given the structural differences often encountered between training and real-world data. To address this, the authors introduce LPShift, a dataset-splitting strategy that induces distribution shifts based on structural properties, allowing for a controlled study of model performance under these conditions. They evaluate several state-of-the-art Graph Neural Network for Link Prediction models and generalization methods across multiple split scenarios.

strengths:
1. The focus on distribution shifts in link prediction is valuable, as models often fail to generalize well when such shifts occur in real-world settings, like social networks or recommender systems. This paper directly addresses this issue by benchmarking models in varied shift scenarios.

2. The paper provides comprehensive baseline comparisons under the distribution shift setting.

weaknesses:
1. The motivation behind distribution shifts in link prediction is not effectively illustrated in the introduction. A clearer example is needed to demonstrate why link prediction models might struggle with distribution shifts:  
Figure 1 is confusing. Models should easily predict links with more common neighbors (blue and green links) compared to red links, aligning with typical link prediction assumptions. However, this is not explained well, which weakens the introductory motivation.

2. The definition of distribution shift, based solely on heuristics, feels arbitrary. It would strengthen the study if the importance of these heuristics in link prediction were demonstrated upfront, clarifying their role in creating meaningful shifts.  
a) Previous studies (e.g., [1]) emphasize the significance of global structure information, which seems not fully considered in the LPShift splitting strategy.
b)  The use of temporal datasets like Collab may not suit this split strategy, as it is sensitive to time. As a benchmark paper, two datasets seem limited.

3. The paper’s terminology needs refinement for clarity. For example, using consistent names for terms like “inverse”/“backward” splits would reduce confusion. “’repair’” should be replaced with “repair” for consistency and correctness.

4. As a benchmark study, the insights provided are minimal. It would be more valuable to include a deeper analysis, such as how different splitting strategies impact performance or specific guidance on choosing GNN4LP models based on observed patterns in the results.

[1] Revisiting Link Prediction: A Data Perspective. ICLR 2024.

questions:
Why is it important to focus on distribution shifts in link prediction? While distribution shifts can impact GNN performance, is it useful to have a benchmark dedicated to evaluating these shifts independently? In many cases, performance on the original dataset splits remains a key concern. For instance, using the time-based splits in OGB-Collab might offer a more practical perspective. I would consider raising the score if the authors provide a promising rebuttal for my questions and concerns.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733185716861

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal Summary (2/2)

comment:
* *Heuristic Type*
    * Since there is no currently quantifiable means to induce distribution shift relevant for link prediction, LPShift leverages well-known link prediction heuristics in order to ensure that pairwise information is properly considered within the distribution shift. As such, LPShift is modular since all it needs is a heuristic to generate dataset splits based on threshold magnitudes and direction. Our study focuses on Common Neighbors, Shortest-Path, and Preferential-Attachment since these heuristics allow targeting for local, global, and node-degree information, respectively.
* *Time Efficiency*
    * Given LPShift's use of heuristics, applying LPShift as a splitting strategy is far more time-efficient than gathering a new dataset manually. As such, researchers wishing to target local structural information within a real-world dataset can apply various magnitudes and directions for a given heuristic in an LPShift split to generate multiple different perspectives on the original dataset.

Our study on LPShift provides a foundation to quantify the previously-mentioned factors. From which, we observe interesting patterns in the behavior of GNN4LP and basic LP methods:
* Resource Allocation (RA) overwhelmingly performs the best on LPShift's "Forward" ogbl-collab splits. However, RA performs the worst on the "Backward" SP and CN - 2,1 splits, whereas GCN performs the best. This result is especially interesting, since a prevailing assumption in link prediction is that **GNN4LP generalize better in scenarios where local structural information is more available between training and validation. LPShift induces this exact scenario with it's "Forward" splits.**
* NCNC performs worse than GCN on the CN - 2,1 split for both ogbl-collab and ogbl-ppa. However, NCNC rises to become the best-performing model on the subsequent CN - 4,2 and CN - 5,3 splits. Therefore indicating **NCNC's sensitivity to shifts within local information**, but a capability to generalize well once more local structural information is made available.
* LPFormer and SEAL perform competitively on many of the PA splits for ogbl-collab and ogbl-ppa, with a special case for NCNC on the "Backwards" ogbl-ppa PA split. In this scenario, the three models frequently out-performs other GNN4LP models by margins of 10 MRR. Therefore, indicating their ability to generalize given an abundance of highly-connected nodes within the training distribution. This is especially interesting given that Neo-GNN frequently performs the worst on these splits, indicating that **the neighborhood information Neo-GNN requires is lost within the "Backwards" PA splits**.
* BUDDY demonstrates an interesting resilience to the "Backwards" SP splits for both ogbl-ppa and ogbl-collab. From which, BUDDY always out-performs other GNN4LP methods. In this same scenario, SEAL's lower performance indicates that **the ability to distinguish subgraph features is more important than neighboorhood information when considering a shift in long-range structural information**.

Given the previously-mentioned observations, **LPShift allows analysis to adopt a fine-grained perspective which eliminates concerns about whether a GNN4LP model can leverage an unfair advantage by exploiting structural quirks within given datasets**. Such a level of analysis would be tedious with real-world disitribution shifts, requiring identification and then expensive computations in order to find targeted graph substructures.  Given that **distribution shift is not just dataset-dependent but can also be task-specific**, there is no one-size-fits-all solution. However, as long as a structural heuristic (or any combination of heuristics) is relevant to a given researcher's interest, then **LPShift serves as a means to test any link prediction models under targeted structural shifts and gain insights about model weakpoints**.


[1] Liben-Nowell, David, and Jon Kleinberg. "The link prediction problem for social networks." Proceedings of the twelfth international conference on Information and knowledge management. 2003.

[2] Zhao, Jianan, et al. "Learning on large-scale text-attributed graphs via variational inference." arXiv preprint arXiv:2210.14709 (2022).

[3] Gui, Shurui, et al. "Good: A graph out-of-distribution benchmark." Advances in Neural Information Processing Systems 35 (2022): 2059-2073.

[4] Ji, Yuanfeng, et al. "DrugOOD: Out-of-Distribution (OOD) Dataset Curator and Benchmark for AI-aided Drug Discovery--A Focus on Affinity Prediction Problems with Noise Annotations." arXiv preprint arXiv:2201.09637 (2022).

[5] Zou, Deyu, et al. "GeSS: Benchmarking Geometric Deep Learning under Scientific Applications with Distribution Shifts." The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track.

[6] Mao, Haitao, et al. "Revisiting link prediction: A data perspective." arXiv preprint arXiv:2310.00793 (2023).
</content>
</thread_object>

</thread>
<thread>
creation date:
1733185738570

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal Summary (1/2)

comment:
Our deepest thanks to all reviewers, your varied perspectives and feedback improved the quality of our paper significantly. Since we are approaching the end of the rebuttal period, we summarize how we've adressed all concerns below: 

* Numerous grammatical edits for clarity on motivations and insights provided by the paper. In particular, we detail why distribution shift matters for link prediction.
* Additional observations, examples, and updated figures/tables on how LPShift affects link prediction performance and relates to realistic scenarios.
* Updated repository for replication of baseline results and generating LPShift splits with included code re-factoring plan.
* 5 new tests on traditional generalization methods: VRex, IRM, GroupDRO, DANN, Deep CORAL. From which, we were able to determine that LPShift is resistant to performance improvements from traditional generalization methods. 
* 3 additional datasets: Cora, Citeseer, and PubMed for quantifying the effect of LPShift on smaller benchmark datasets.

Additionally, we wish to detail the core motivation behind LPShift, shown below:

The core motivation for building LPShift is it's practical utility. Not only is there a lack of OOD benchmark datasets in link prediction, but also **a lack of study understanding distribution shift and it's mechanisms within link prediction**. We attribute this lack of study to the difference in task-dependent mechanisms between graph/node classification and link prediction. Pairwise and neighborhood structural heuristics are critical for link prediction performance [1]. As a self-supervised task, link prediction requires understanding structure within samples to determine if target links will form. Whereas node/graph classification do not require understanding pairwise structural dynamics to significantly boost performance [2].

Given link prediction's reliance on pairwise information, **all tested GNN4LP architectures integrate structural information for powerful performance**. The methods for integrating structural characteristics into GNN4LP models are distinct; NCNC integrates Common Neighbors (CN), BUDDY integrates subgraph features and RA, Neo-GNN applies neighborhood characteristics, SEAL elevates structural expressiveness with the labelling trick, LPFormer applies pairwise attention. But their ability to generalize under distribution shift was not deeply studied until LPShift.

Real-world distribution shifts, like molecular scaffold shift, can be seen as a mixture of heuristic structural shifts. So, applying current GNN4LP models on **complicated real-world shifts make it unnecessarily difficult to control how GNN4LP and their distinct structural methods generalize under distribution shift**. Therefore, we apply LPShift not just for building datasets with distribution shift, but to also **control** the shift introduced into the dataset [3,4, 5]. **LPShift's fine-grained control makes it simple to analyze how specific structures and their attributes affect GNN4LP performance**. From here, LPShift integrates factors such as the magnitude, direction, heuristic type, and time efficiency in order to define a structural shift that was previously un-quantifiable. We break the dynamics behind these factors further:

* *Magnitude*
    * We determine the amount of structural information contained within each sample distribution with hard-boundary threshold values. For example, CN - 1,2 has a valid threshold at 1 and a testing threshold at 2; meaning that training has zero Common Neighbors, validation has a single Common Neighbors, and testing contains 2 or more Common Neighbors. The magnitude of structural information within these splits can then be easily adjusted to accomodate more or less information (i.e. CN - 2,4 with zero and 1 Common Neighbors in training, 2 and 3 Common Neighbors in validation, and 4 or more Common Neighbors in testing).
* *Direction*
    * Given a certain magnitude between training, validation, and testing; we then build a "Forward" and "Backward" split of LPShift for each dataset. The "Forward" split represents a scenario where the magnitude of structural information available subsequently increases between splits (i.e. CN - 1,2). The "Backward" split represents the scenario, were the magnitude of structural information available within splits subsequently decreases between splits. From example, CN - 2,1 will have training samples with 2 or greater Common Neighbors but then validates on samples with 1 Common Neighbors and eventually test on samples with no Common Neighbors.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work tackles the important task of evaluating link prediction models' generalizability under distribution shifts. The work proposes LPShift, a dataset-splitting strategy designed to induce distribution shifts based on structural properties, enabling a controlled examination of model performance under these conditions. Through comprehensive experiments on multiple datasets and state-of-the-art Graph Neural Network (GNN) models, the paper shows that existing link prediction methods are vulnerable to distribution shifts, often resulting in poor performance compared to their in-distribution versions.

However, despite the importance of the problem and the potential impact of the proposed benchmark, the reviewers have raised several concerns regarding the paper's writing quality and clarity. More significantly, the paper lacks a rigorous theoretical and empirical justification for the proposed LPShift benchmark. As reviewer QSyV astutely points out in the rebuttal, the very few foundational works on link prediction under distribution shifts does not excuse not having a solid theoretical grounding and real-world justification for the benchmark itself.

Upon closer examination of the paper, it becomes apparent to me that many of the reviewer concerns stem from the authors' failure to provide a clear and well-motivated causal model for the distribution shift. Specifically, the paper could benefit from: (1) a more explicit causal model that underlies the proposed shift, (2) a thorough justification of this causal model through real-world mechanisms or theoretical arguments, (3) a proof or empirical demonstration that the proposed shift indeed produces the correct structure under the assumed causal model, and (4) deeper insights into the problem, including an analysis of the implications of the distribution shift on the link prediction task.

By addressing these concerns and providing a more comprehensive and theoretically sound foundation for the LPShift benchmark, the authors could significantly strengthen their contribution and provide a more convincing case for the importance and relevance of their work. In the current form, I feel the paper is not ready for publication, unfortunately.