Towards Understanding Link Predictor Generalizability Under Distribution Shifts

## Abstract

Abstract Recently, multiple models proposed for link prediction (LP) demonstrate impressive results on benchmark datasets.
However, many popular benchmark datasets often assume that dataset samples are drawn from the same distribution (i.e., IID samples). In real-world situations, this assumption is often incorrect; since uncontrolled factors may lead train and test samples to come from separate distributions.
To tackle the distribution shift problem, recent work focuses on creating datasets that feature distribution shifts and designing generalization methods that perform well on the new data. However, those studies only consider distribution shifts that affect node- and graph-level tasks, thus ignoring link-level tasks. Furthermore, relatively few LP generalization methods exist. To bridge this gap, we introduce a set of LP-specific data splits which utilizes structural properties to induce a controlled distribution shift. We verify the shift’s effect empirically through evaluation of different SOTA LP methods and subsequently couple these methods with generalization techniques. Interestingly, LP-specific methods frequently generalize poorly relative to heuristics or basic GNN methods. Finally, this work provides analysis to uncover insights for enhancing LP generalization. Our code is available at: https://github.com/revolins/LPStructGen

## 1 Introduction

Link Prediction (LP) is concerned with predicting unseen links (i.e., edges) between two nodes in a graph []. The task has a wide variety of applications including: recommender systems, [], knowledge graph completion [], protein-interaction [], and drug discovery []. Traditionally, LP was performed using heuristics that model the pairwise interaction between two nodes [, , ].
Recently, the success of Graph Neural Networks (GNNs) [], have prompted their usage in LP [, ]. However, they have been shown to be inadequate for LP, as they are unable to properly capture the joint representation of a pair of nodes [, ]. To combat this problem, recent methods (i.e., GNN4LP) empower GNNs with the necessary information to capture the pairwise interaction of two nodes [, , , ] and demonstrate tremendous ability to model LP on real-world datasets [].

While recent methods have shown promise, current benchmarks [] assume that the training and evaluation data are all drawn from the same structural feature distribution. This assumption often collapses in real-world scenarios, where the structural feature (i.e., covariate) distribution may shift from training to evaluation. Therefore, it’s often necessary for models to generalize to samples whose newly-introduced feature distribution differs from the the training dataset [, , , ].

If we consider the graphs in Figure 1 as snapshots pulled from a social network with which a node represents a user and an edge represents a connection between users. Our task is to predict new interactions (the dotted-lines) that will form between existing users. Then, an ideal LP model trained on the first graph would learn a representation that captures the pairwise relations of the connected nodes [] to make effective predictions. However, this model would likely fail to generalize to the graphs with “blue” and “green” links, since the representations necessary to capture these pairwise relations would require tracking unseen numbers of CNs. To resolve this, our proposed data splitting strategy generates and controls for this scenario in real-world datasets, providing a means from which new models may solve this problem.

Figure: Figure 1: A “realistic” example where sampled edges are represented with dotted lines. The additional edges cause a structural shift where the model learns with more Common Neighbors (CNs). Red = 0 CNs, Blue = 1 CN, Green = 2 CNs.
Refer to caption: extracted/5663139/figs/CNOverTime.png

Furthermore, while numerous methods work to account for distribution shifts within graph machine learning [], there remains little work doing so for LP. Specifically, we observe that (1) No Benchmark Datasets: Current graph benchmark datasets designed with a quantifiable distribution shift are focused solely on the node and graph tasks [, ], with none existing for LP. (2) Absence of Foundational Work: There is no existing work that gives a comprehensive overview of the types of distribution shifts relevant to LP. Current methods are primarily focused on detecting and alleviating anomalies within node- and graph-level tasks [, , , , , , , ]. Additionally, few methods exist which are explicitly designed for correcting distribution shift in LP [, , , ]. Also, other LP generalization methods that have been argued to implicitly improve generalization in this shifted scenario remain crucially untested [, ].

To tackle these problems, this work proposes the following contributions:

- •
Creating Datasets with Meaningful Distribution Shifts. LP requires pairwise structural considerations [, ]. Additionally, when considering realistic settings [] or distribution shift [], GNN4LP models perform poorly relative to models used in graph [, ] and node classification [, ]. To better understand distribution shifts, we use key structural LP heuristics to split the links into train/validation/test splits. By using LP heuristics to split the data, we induce shifts in the underlying feature distribution of the links, which are relevant to their existence [].
- •
Benchmarking Current LP Methods. To our surprise, GNN4LP models struggle more than simpler methods when generalizing to data produced by our proposed strategy. Despite the existence of generalization methods that aids link prediction model performance in standard scenarios, there is no means to account for distribution shift and then generalize to our proposed structural distribution shift without re-training the LP model [, , ]. This reduces the reliability of LP models in-production, since the model will likely to fail to generalize and then require integration into expensive/time-consuming frameworks before re-training on the shifted dataset. This work quantifies the performance of current SOTA LP models and provides analysis for a better foundation to correct this issue. We further quantify the effects of LP generalization methods, finding that they also struggle to generalize to different structural distributions.

The remainder of this paper is structured as follows. In Section 2, we provide background on the heuristics, models, and generalization methods used in LP. In Section 3, we detail how the heuristics relate to our proposed splitting strategy and formally introduce said strategy. Lastly, in Section 4, we benchmark a selection of LP models and generalization methods on our proposed splitting strategy, followed by analysis with the intent of understanding the effects of the new strategy.

## 2 Related Work

LP Heuristics: Classically, neighborhood heuristics, which measure characteristics between source and target edges, have functioned as the primary means of predicting links. These heuristics show limited effectiveness with a relatively-high variability in results, due to the complicated irregularity within graph datasets, which only grows worse as the dataset grows larger []. Regardless of this, state-of-the-art GNN4LP models have integrated these neighborhood heuristics into their architectures to elevate link prediction results [, ].

For a given heuristic function, $u$ and $v$ represent the source and target nodes in a potential link $(u,v)$, $\mathcal{N}(v)$ is the set of all edges connected to the node $v$, and $f(v_{i,i+1})$ is a function that considers all paths of length $i$ that being at node that starts at $v$. We consider the following few heuristics:

Common Neighbors []: The number of neighbors shared by two nodes $u$ and $v$,

$$ $\text{CN}(u,v)=|\mathcal{N}(u)\cap\mathcal{N}(v)|.$ (1) $$

Preferential Attachment []: The product of the number of neighbors (i.e., the degree) for nodes $u$ and $v$,

$$ $\text{PA}(u,v)=|\mathcal{N}(u)|\times|\mathcal{N}(v)|.$ (2) $$

Shortest Path Length []: The length path between $u$ and $v$ which considers the smallest possible sum $\Sigma$ of length $n-$nodes,

$$ $\text{SP}(u,v)=\operatorname*{arg\,min}_{\Sigma}(\Sigma^{n-1}_{i=1}f(v_{i,i+1} )).$ (3) $$

GNNs for Link Prediction (GNN4LP): LP’s current SOTA methods rely on GNNs to constitute a given model’s backbone. The most common choice is the Graph Convolutional Network (GCN) [], which defines a simplified convolution operator that considers a node’s multi-hop neighborhood. The final score (i.e., probability) of a link existing considers the final representation of both nodes. However, [] have shown that such methods aren’t suitably expressive for LP, as they ignore vital pairwise information that exists between both nodes. To account for this, SEAL [] conditions the message passing on both nodes in the target link by applying a node-labelling trick to the enclosed k-hop neighborhood. They demonstrate that this can result in a suitably expressive GNN for LP. NBFNet [] conditions the message passing on a single node in the target link by parameterizing the generalized Bellman-Ford algorithm. In practice, it’s been shown that conditional message passing is prohibitively expensive to run on many LP datasets []. Instead, recent methods pass both the standard GNN representations and an additional pairwise encoding into the scoring function for prediction. For the pairwise encoding, Neo-GNN [] considers the higher-order overlap between neighborhoods. BUDDY [] uses the subgraph counts surrounding a target link, which is estimated by using subgraph sketching. Neural Common-Neighbors with Completion (NCNC) [] encodes the enclosed 1-hop neighborhood of both nodes. Lastly, LPFormer [] adapts a transformer to learn the pairwise information between two nodes.

Generalization in Link Prediction: Generalization methods for LP rely on a mix of link and node features in order to improve LP model performance. DropEdge [] randomly removes edges with increasing probability from the training adjacency matrix, allowing for different views of the graph. Edge Proposal Sets (EPS) [] considers two models – a filter and rank model. The filter model is used to augment the graph with new edges that are likely to be true, while the rank method is used to score the final prediction. [] defines Topological Concentration (TC), which considers the overlap in subgraph features of a node with each of it’s neighbors. It demonstrates that it correlates well with performance of individual links in LP. To improve the performance of links with a low TC, it considers a re-weighting strategy that places more emphasis on links with a lower TC. Counter-Factual Link Prediction (CFLP) [] conditions a pre-trained model with edges that contain information counter to the original adjacency matrix. The intent is that the counter-factual links will provide information that is not present in a given dataset.

## 3 Benchmark Dataset Construction

Figure: Algorithm 1 Dataset Splitting Strategy

In this section, we attempt to induce a shift in each dataset’s structural features/covariates by proposing a strategy for identifying important structural measures. A structural measure’s importance is determined by how closely-associated it is with how links form within the graph. We further explain how to use these importance measures for generating new splits.

### 3.1 Types of Distribution Shifts

We consider inducing distribution shifts by splitting the links based on key structural properties which affect link formation and thereby LP. We consider three type of metrics: Local structural information, Global structural information, and Preferential Attachment. Recent work by [] has shown the importance of local and global structural information for LP. Furthermore, due to the scale-free nature of many real-world graphs and how it relates to link formation [], we also consider Preferential Attachment. A representative metric is then chosen for each of the three types, shown as follows:

(1) Common Neighbors (CNs): CNs measure local structural information by considering only those nodes connected to the target and source nodes. A real-world case for CNs is whether you share mutual friends with a random person, thus determining if they are your “friend-of-a-friend” []. CNs plays a large role in GNN4LP, given that NCNC [] and EPS [] integrate CNs into their framework and achieve SOTA performance. Furthermore even on complex real-world datasets, CNs achieves competitive performance against more advanced neural models []. To control for the effect of CNs, the relevant splits will consider thresholds which include more CNs.

(2) Shortest Path (SP): SP captures a graph’s global structural information, thanks to the shortest-path between a given target and source node representing the most efficient path for reaching the target []. The shift in global structure caused by splitting data with SP can induce a scenario where a model must learn how two dissimilar nodes form a link with one another [], which is comparable to the real-world scenario where two opponents co-operate with one another [, ].

(3) Preferential Attachment (PA): PA captures the scale-free property of larger graphs by multiplying the degrees between two given nodes []. When applied to graph generation, PA produces synthetic Barabasi-Albert (BA) graphs which retain the scale-free property to effectively simulate the formation of new links in real-world graphs, such as the World Wide Web [, ]. Similar to CNs, the relevant PA splits will consider thresholds that integrate higher PA values.

### 3.2 Dataset Splitting Strategy

In the last subsection we described the different types of metrics to induce distribution shifts for LP. The metrics cover fundamental structural properties that influence the formation of new links. We now describe how we use these measures to split the dataset into train/validation/test splits to induce such shifts.

In order to build datasets with structural shift, we apply a given neighborhood heuristic to score each link. This score is then compared to a threshold ($i_{train},i_{valid})$ to categorize a link as a different sample. As denoted in Alg. 1, the heuristic score of the link $(u,v)$ is $h(u,v)$. The link falls into: training when $h(u,v)<i_{train}$, validation when $i_{train}\leq h(u,v)<i_{valid}$, and testing when $h(u,v)>i_{valid}$. The training graph is constructed from the training edges extracted from the original OGB dataset []. Validation and testing samples extracted from this training graph are limited to 100k edges maximum and subsequently removed to prevent test-leakage. The full algorithm is detailed in Algorithm 1 with additional details in Appendix B.

With Figure 2, we provide a small example of how splits are produced by our proposed splitting strategy. Specifically, Figure 2(a) demonstrates the outcome of the CN split labelled “(0,1,2)” where sampled edges pulled from the: black-dotted line = training (no CNs), red-dotted line = validation, (1 CN), and blue-dotted line = testing ($\geq$2 CNs). See Appendix B for information on Figure 2(b) and Figure 2(c).

Figure: (a) CN
Refer to caption: extracted/5663139/figs/CNSplitStrategy.png

Finally, to test the effect of different threshold values on performance, we further adjust the $i_{train}$ and $i_{valid}$ thresholds to produce 3 varying splits by CNs and PA and 2 varying splits for the SP thresholds. These variations in splits were chosen based on two conditions. 1) A given sampled edge contains structural information within the user-defined threshold. The core idea is that a training split with a more generous threshold and therefore more structural information will give the model an easier time generalizing to testing samples. 2) The final dataset split contains a sufficient number of samples, so as to provide enough data within each split for a model to generalize to. Given the limited size of the SP split samples and based on condition 2), the SP splits were limited to 2 variants, see Appendix B for more information.

## 4 Experiments

To bridge the gap for GNN4LP generalizing under distribution shifts, this work addresses the following questions: (RQ1) Can SOTA GNN4LPs generalize under our proposed distribution shifts? (RQ2) Can current LP generalization methods further boost the performance of current methods? and (RQ3) What components of the proposed distribution shift are affecting the LP model’s performance?

### 4.1 Experimental Setup

Datasets: We consider the ogbl-collab and ogbl-ppa datasets [] to represent tasks in two different domains, allowing a comprehensive study of the generalization of LP under distribution shift. For both datasets, we create multiple splits corresponding to each structural property detailed in Section 3.2. For the “forward” split, denoted as $(X,Y,Z)$, an increase in $Y$ and $Z$ indicates more structural information available to the training adjacency matrix. The “inverse” split swaps the training and testing splits from their counterpart in the “forward” split, resulting in the training adjacency matrix losing access to structural information as $X$ and $Y$ increase. See Appendix E for more details.

GNN4LP Methods: We consider multiple SOTA GNN4LP methods including: NCNC [], BUDDY [], and LPFormer []. We further consider GCN [] as a simpler GNN baseline. Lastly, we also consider the Resource Allocation (RA) [] heuristic. Additional models, such as SEAL [] and Neo-GNN [] are not considered due to runtime considerations coupled with the relative effectiveness from the variety of currently-selected GNN4LP methods, with differences detailed in Section 2.

Generalization Methods: We also consider enhancing the performance of different LP models with multiple generalization techniques. This includes DropEdge [], which randomly removes a portion of edges from the training adjacency matrix. Edge Proposal Sets (EPS) [] utilizes one GNN4LP method to filter edges based on their common neighbors and another method to rank the top-k filtered edges in the training adjacency matrix. Lastly, we consider Topological Concentration (TC) [], which re-weights the edges within the training adjacency matrix based on the structural information captured by the TC metric. Note: we did not run Counterfactual LP [] due to experiencing an out-of-memory error on all tested dataset splits.

Evaluation Setting: We consider the standard evaluation procedure in LP, in which every positive validation/test sample is compared against $M$ negative samples. The goal is that the model should output a higher score (i.e., probability) for positive sample than the negatives. To create the negatives, we make use of the HeaRT evaluation setting [] which generates $M$ negatives samples per positive sample according to a set of common LP heuristics. In our study, we set $M=250$ and use CNs as the heuristic in HeaRT.

Evaluation Metrics: We evaluate all methods using multiple ranking metrics as a standard practice in LP literature []. This includes the mean reciprocal rank (MRR) and Hits@20.

Hyperparameters: All methods were tuned on permutations of learning rates in $\{1e^{-2},1e^{-3}\}$ and dropout in $\{0.1,0.3\}$. Otherwise, we used the recommended hyperparameters for each method according to their official implementations. Each model was trained and tested over five seeds to obtain the mean and standard deviations of their results. Given the significant time complexity of training and testing on the customized ogbl-ppa datasets, NCNC and LPFormer were tuned on a single seed, followed by an evaluation of the tuned model on five separate seeds.

Table: Table 1: ogbl-collab results on the Forward splits. Results reported in MRR with the best bolded and the second best underlined.

Table: Table 2: ogbl-ppa results on the Forward splits. Results reported in MRR with the best bolded and the second best underlined.

### 4.2 Results for GNN4LP

In order to provide a unified perspective on how distribution shift affects link prediction models, each GNN4LP method was trained and tested across five seeded runs on versions of ogbl-collab and ogbl-ppa split by Common Neighbors, Shortest-Path, and Preferential-Attachment. Examining the results, we have the two following key observations.

Observation 1: Poor Performance of GNN4LP

As shown in Tables 3, 1, and 2, both RA and GCN consistently out-perform GNN4LP models. In Table 1, RA is overwhelmingly the best-performing, achieving performance more than ten percent higher than the next closest model. However the results for the ogbl-ppa forward split, as shown in Table 2, indicate LPFormer as the best-performing model on the PA split, albeit with a much lower average score than those demonstrated within the ogbl-collab forward split.

**Table 3: Mean LP model rank on all splits, determined by Hits@20.**
| Models | Forward | Inverse |
| --- | --- | --- |
| RA | 2.06 | 3.67 |
| GCN | 2.75 | 2.80 |
| BUDDY | 3.31 | 3.33 |
| NCNC | 3.44 | 2.80 |
| LPFormer | 3.44 | 2.40 |

Given ogbl-ppa’s reduction in performance and the superiority of simpler methods with ogbl-collab, the structural shift induced by our proposed splitting strategy makes it difficult for GNN4LP to generalize. A key consideration for this result is our proposed splitting strategy’s direct effect on graph structure, which implicitly shifts features if structure is correlated to the features, much like how spatio-temporal [] and size [] shift affect an input graph.

Table: Table 4: ogbl-collab results on the Inverse splits. Results reported in MRR with the best bolded and the second best underlined.

Table: Table 5: ogbl-ppa results on the Inverse splits. Results reported in MRR with the best bolded and the second best underlined.

Observation 2: Performance Differs By Both Split Type and Thresholds.

As shown in Figure 3, regardless of whether a model is tested on a “Forward” or “Inverse” split; subsequent splits from the same heuristic alter the structural information available across all splits and result in gradual change in the given model’s performance. It is interesting to note that the results for ogbl-ppa and ogbl-collab nearly mirror one another for any given “Forward” split, where an ogbl-ppa split increases the respective ogbl-collab decreases. On the “Inverse” split, a stark increase is seen across most splits, which indicates that increasingly-available structural information in the training adjacency matrix yields improved LP performance []. The fact that these results include splits produced by Preferential-Attachment, Global Structural Information, and Local Structural Information further indicates the importance of any structural information when training LP models [].

Figure: Figure 3: The mean scores of the best-performing GNN4LP models tested with our proposed splitting strategy. Each line represents a given dataset and split, arranged uniformly between figures. In the case of decreasing performance, the model with the highest average values was selected.
Refer to caption: extracted/5663139/figs/temp_performance.png

### 4.3 Results for Generalization Methods

In this section, we apply DropEdge [], EPS [], and TC [] on the previously benchmarked GCN [] and BUDDY [] to determine the feasibility of LP models’ generalization under our proposed distribution shift.

**Table 6: The mean change in performance for all splits for a given generalization methods applied to GCN.**
|  | ogbl-collab | ogbl-ppa |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Methods | Forward | Inverse | Overall | Forward | Inverse | Overall |
| DropEdge | +4% | +2% | +3% | -1% | 0% | -0.5% |
| EPS | -39% | -40% | -40% | -35% | -15% | -25% |
| TC | -9% | -35% | -22% | 0% | 0% | 0% |

Observation 1: LP-Specific Generalization Methods Struggle. As demonstrated in Table 6, the two generalization methods specific to LP: TC [] and EPS [] fail to improve the performance of our tested LP models. EPS always results in a decrease of performance from our baseline, indicating a failure to fix the change in performance that our splitting strategy’s structural shift brings. To validate this, we calculate Earth Mover’s Distance (EMD) [] between the heuristic scores of the training and testing splits. As shown in Figure 4, EPS updates the training adjacency matrix to alter the distance between the sampled distributions; given the results in Table 6, generalizing under our proposed structural shift surpasses the scope of simply updating the training graph’s structure.

Figure: Figure 4: The EMD values calculated between the heuristic scores of training and testing samples. Note: The tested heuristics correspond to their labelled splits, so as to simulate the dataset splitting.
Refer to caption: extracted/5663139/figs/emd_collab_plot.png

TC results in a decrease of performance for ogbl-collab and no change in performance for ogbl-ppa. This is likely due to the thresholds imposed by our strategy which separates splits. There is no distinguishable overlap between sampled distributions: TC can’t re-weight the training adjacency matrix in order to improve LP generalization [, ]. This result runs contrary to current work, where re-weighting is effective for handling distribution shifts in other graph tasks [] and even computer vision [].

Observation 2: DropEdge Occasionally Works. Additionally, as demonstrated in Table 6, DropEdge [] is the only generalization method that improves the performance of our tested LP methods on all splits for ogbl-collab, although it has a small detrimental effect on ogbl-ppa. This result is interesting given that DropEdge is not LP-specific and ogbl-collab has an inherent distribution shift involved in predicting unseen author collaborations [, ]. However, Figure 4 indicates that DropEdge only has a significant effect on EMD when handling the “Inverse” ogbl-collab CN split, indicating that the performance improvement is due to the change in the adjacency matrix structure, not the change in the distance between sample distributions. Additional EMD results are detailed in the Appendix within Tables 13 and 14.

### 4.4 Discussion

Does GNN4LP generalize and do LP generalization methods work? As demonstrated by the results of the LP4GNN models and LP generalization methods in Section 4 and relative to their baseline results [], all tested models fail to generalize and only DropEdge [] improves LP performance when handling the proposed distribution shift.

How is the proposed distribution shift affecting performance? When considering the EMD calculations for the training and testing samples, it appears that adjustments to the structure of the training adjacency matrix are ineffective for enabling models to generalize under our proposed distribution shift. Regarding the current landscape of LP models and generalization methods, a new framework or architecture, similar to [], that leverages disentangled learning in regards to structural shift may remedy the problem generated by our proposed dataset splitting strategy.

## 5 Conclusion

This work proposes a simple dataset splitting strategy for inducing structural shift relevant for link prediction. The effect of this structural shift was then benchmarked on ogbl-collab and ogbl-ppa and shown to pose a unique challenge for current SOTA LP models and generalization methods. Further analysis with EMD calculations demonstrated that generalization under this new structural shift may require techniques which go beyond influencing the structure of the graph data. As such, our proposed dataset splitting strategy provides a new challenge for SOTA LP models and opportunities to expand research for generalizing under structural shifts.

## 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 G.
(c)
Did you discuss any potential negative societal impacts of your work?
[Yes] See Appendix H.
(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 experimental results (either in the supplemental material or as a URL)?
[Yes] See [https://github.com/revolins/LPStructGen](https://github.com/revolins/LPStructGen).
(b)
Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
[Yes] See Section 4.1 and Appendix E.
(c)
Did you report error bars (e.g., with respect to the random seed after running experiments 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 E.
- 4.
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…
(a)
If your work uses existing assets, did you cite the creators?
[Yes]
(b)
Did you mention the license of the assets?
[Yes] See Appendix F.
(c)
Did you include any new assets either in the supplemental material or as a URL?
[Yes] See [https://github.com/revolins/LPStructGen](https://github.com/revolins/LPStructGen).
(d)
Did you discuss whether and how consent was obtained from people whose data you’re using/curating?
[Yes] See Appendix F.
(e)
Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?
[N/A]
- 5.
If you used crowdsourcing 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, if applicable?
[N/A]
(c)
Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation?
[N/A]

## Appendix A Heuristic Choice

Resource Allocation and Adamic-Adar Index were not considered for splitting strategies given that they build upon the original Common Neighbor formulation. We acknowledge this may lead to interesting analysis on how higher-order heuristics could influence distribution shifts, however it is redundant given our intentions to induce distinct structural scenarios to the test LP models using just link prediction heuristics for splitting strategies.

## Appendix B Splitting Strategy – Additional Algorithmic Details

This section provides additional details about the way data was formatted before being used as input for Algorithm 1 of our proposed splitting strategy and the intuition behind how Preferential-Attachment and Shortest-Path work within the splitting strategy. The details on the algorithm includes:

- •
Validation and Testing Edges are limited to 100k edges total.
- •
PPA Training Edges are limited to 3 million edges total.
- •
Negative Testing and Validation edges are produced via HeaRT [].
- •
Validation and testing edges that are duplicated with training edges are removed from the edge index.
- •
In order to provide overlap within a given dataset, validation and testing edges that do not connect to training nodes are removed from the edge index.
- •
After sampling the necessary training edges, the adjacency matrix is extracted from the edge index, converted to an undirected graph and has any edge weights standardized to 1.

Common Neighbors, Preferential-Attachment and Shortest-Path, as shown in Figure 2(a), 2(b), and 2(c) respectively, are interchangeable within the dataset splitting strategy. Details about how Common Neighbors functions within the strategy are included in Section 3.2. Figure 2(b) and Figure 2(c) serve as toy examples and do not correspond directly to any dataset splits tested within our study. However, the examples illustrated within Figure 2(b) and Figure 2(c) do correspond to how their given heuristic functions within our splitting strategy.

For Figure 2(b) or Preferential-Attachment, it determines the degrees between a given source and target node and then multiples the two to produce the score, based on that score, the sample is then sorted into a new dataset split.

For Figure 2(c) or Shortest-Path, the heuristic determines the score by determining the minimum number of nodes necessary to reach the target node from the source node. If there is a link between the two nodes, we remove the link and then re-add to the adjacency matrix after the score calculation. The final Shortest-Path score applies the calculated shortest-path length, $SP(u,v)$ as the denominator in a ratio of $\frac{1}{SP(u,v)}$, which is then used to sort the sample into it’s respective dataset split.

## Appendix C Size of Dataset Samples

In this section we detail the number of training, validation, and test edges for all of the newly created splits detailed in Section 3. There are in Tables 7 and 8 for ogbl-collab and ogbl-ppa, respectively.

**Table 7: Number of samples in the ogbl-collab dataset for the forward and backward heuristic splits, separated into columns allocated for training, validation, and testing splits.**
| Heuristic | Split | Train | Valid | Test |
| --- | --- | --- | --- | --- |
| CN | (0, 1, 2) | 57638 | 6920 | 4326 |
| (0, 2, 4) | 237928 | 20045 | 14143 |  |
| (0, 3, 5) | 493790 | 31676 | 21555 |  |
| (2, 1, 0) | 1697336 | 23669 | 9048 |  |
| (4, 2, 0) | 1193456 | 24097 | 11551 |  |
| (5, 3, 0) | 985820 | 25261 | 11760 |  |
| SP | ($\infty$, 6, 4) | 46880 | 1026 | 2759 |
| ($\infty$, 4, 3) | 52872 | 1238 | 3457 |  |
| (4, 6, $\infty$) | 1882392 | 5222 | 2626 |  |
| (3, 4, $\infty$) | 1877626 | 4384 | 7828 |  |
| PA | (0, 50, 100) | 210465 | 46626 | 9492 |
| (0, 100, 200) | 329383 | 62868 | 25527 |  |
| (0, 150, 250) | 409729 | 75980 | 39429 |  |
| (100, 50, 0) | 1882392 | 5222 | 2626 |  |
| (200, 100, 0) | 1877626 | 4384 | 7828 |  |
| (250, 150, 0) | 457372 | 65323 | 30999 |  |

**Table 8: Number of samples in the ogbl-ppa dataset for the forward and backward heuristic splits, separated into columns allocated for training, validation, and testing splits**
| Heuristic | Split | Train | Valid | Test |
| --- | --- | --- | --- | --- |
| CN | (0, 1, 2) | 2325936 | 87880 | 67176 |
| (0, 2, 4) | 3000000 | 95679 | 83198 |  |
| (0, 3, 5) | 3000000 | 98081 | 88778 |  |
| (2, 1, 0) | 3000000 | 96765 | 92798 |  |
| (4, 2, 0) | 3000000 | 93210 | 85448 |  |
| (5, 3, 0) | 3000000 | 92403 | 81887 |  |
| SP | ($\infty$, 6, 4) | 17464 | 149 | 20 |
| ($\infty$, 4, 3) | 134728 | 4196 | 1180 |  |
| (4, 6, $\infty$) | 3000000 | 90511 | 458 |  |
| (3, 4, $\infty$) | 3000000 | 97121 | 74068 |  |
| PA | (0, 5k, 10k) | 95671 | 95671 | 45251 |
| (0, 10k, 20k) | 98562 | 98562 | 63178 |  |
| (0, 15k, 25k) | 99352 | 99352 | 72382 |  |
| (10k, 5k, 0) | 3000000 | 90623 | 44593 |  |
| (20k, 10k, 0) | 3000000 | 89671 | 34321 |  |
| (25k, 15k, 0) | 3000000 | 91995 | 35088 |  |

## Appendix D Dataset Results

In this section, we include all of the results for each experiment conducted on the generalization methods and EMD calculations. Results from Tables 9, 10, 11, and 12 were used for the calculations demonstrated in Figure 6. Figure 4 was constructed from results within Table 13.

**Table 9: ogbl-collab results on the forward and inverse splits when using DropEdge and TC.**
|  | DropEdge | TC |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Heuristic | Split | GCN | BUDDY | GCN | BUDDY |
| CN | (0, 1, 2) | 13.92 ± 0.78 | 15.54 ± 0.98 | 12.26± 0.28 | 11.27 ± 2.03 |
| (0, 2, 4) | 15.85 ± 0.25 | 16.16 ± 0.17 | 12.62± 0.57 | 12.39 ± 1.43 |  |
| (0, 3, 5) | 17.75 ± 0.11 | 16.34 ± 0.17 | 13.3± 0.47 | 14.99 ± 1.69 |  |
| (2, 1, 0) | 5.96 ± 0.17 | 2.61 ± 0.09 | 4.95 ±0.16 | 5.28 ± 0.05 |  |
| (4, 2, 0) | 6.14 ± 0.065 | 2.88 ± 0.11 | 5.37 ±0.13 | 5.23 ± 0.05 |  |
| (5, 3, 0) | 7.20 ± 0.15 | 4.99 ± 0.08 | 6.04± 0.07 | 6.03 ± 0.10 |  |
| SP | ($\infty$, 6, 4) | 11.94 ± 0.46 | 12.31 ± 0.51 | 11.42 ±0.43 | 7.25 ± 0.81 |
| ($\infty$, 4, 3) | 13.87 ± 0.43 | 17.11 ± 1.02 | 12.88± 0.43 | 9.33 ± 1.66 |  |
| (4, 6, $\infty$) | 9.18 ± 0.52 | 5.34 ± 0.43 | 9.09± 4.74 | 6.88 ± 0.30 |  |
| (3, 4, $\infty$) | 6.71 ± 0.13 | 2.93 ± 0.18 | 3.57± 2.30 | 6.24 ± 0.13 |  |
| PA | (0, 50, 100) | 20.76 ± 0.19 | 21.35 ± 0.36 | 17.55±0.57 | 18.82 ± 1.35 |
| (0, 100, 200) | 14.57 ± 0.20 | 13.84 ± 0.64 | 13.22±1.1 | 12.13±1.04 |  |
| (0, 150, 250) | 13.78 ± 0.28 | 12.85 ± 0.78 | 13.03±0.24 | 10.63±0.55 |  |
| (100, 50, 0) | 21.34 ± 0.65 | 26.09 ± 0.62 | 6.4 ± 0.2 | 15.84 ± 1.13 |  |
| (200, 100, 0) | 12.89 ± 0.59 | 15.68 ± 0.85 | 4.3 ± 0.14 | 9.15 ± 0.39 |  |
| (250, 150, 0) | 11.68 ± 0.37 | 13.13 ± 0.94 | 4.4 ± 0.16 | 6.7 ± 0.2 |  |

**Table 10: ogbl-ppa results on the forward and inverse splits when using DropEdge and TC.**
|  | DropEdge | TC |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Heuristic | Split | GCN | BUDDY | GCN | BUDDY |
| CN | (0, 1, 2) | 8.20 ± 0.34 | 7.83 ± 0.27 | OOM | 5.27 ± 0.34 |
| (0, 2, 4) | 7.39 ± 0.33 | 3.83 ± 0.25 | OOM | 2.91 ± 0.06 |  |
| (0, 3, 5) | 6.04 ± 0.32 | 3.06 ± 0.06 | OOM | 2.67 ± 0.13 |  |
| (2, 1, 0) | 3.50 ± 0.16 | 1.61 ± 0.04 | OOM | 3.44 ± 0.08 |  |
| (4, 2, 0) | 3.01 ± 0.07 | 2.47 ± 0.07 | OOM | 3.45 ± 0.1 |  |
| (5, 3, 0) | 2.97 ± 0.06 | 2.56 ± 0.08 | OOM | 3.55 ± 0.13 |  |
| SP | ($\infty$, 6, 4) | 6.17 ± 0.76 | 3.86 ± 0.39 | OOM | 4.0 ± 0.29 |
| ($\infty$, 4, 3) | 5.55 ± 0.22 | 5.87 ± 0.16 | OOM | 4.82 ± 0.39 |  |
| (4, 6, $\infty$) | 3.44 ± 0.17 | 3.86 ± 0.39 | OOM | 13.2 ± 0.45 |  |
| (3, 4, $\infty$) | 15.69 ± 0.54 | 5.87 ± 0.16 | OOM | 2.89 ± 0.09 |  |
| PA | (0, 50, 100) | 4.19 ± 0.43 | 3.93 ± 0.98 | OOM | 3.62 ± 0.21 |
| (0, 10k, 20k) | 4.98 ± 0.52 | 6.38 ± 3.48 | OOM | 3.13 ± 0.12 |  |
| (0, 15k, 25k) | 5.95 ± 0.28 | 2.49 ± 0.01 | OOM | 3.33 ± 1.38 |  |
| (10k, 5k, 0) | 1.51 ± 0.02 | 3.13 ± 0.1 | OOM | 1.78 ± 0.16 |  |
| (20k, 10k, 0) | 1.25 ± 0.07 | 2.56 ± 0.19 | OOM | 1.5 ± 0.0008 |  |
| (25k, 15k, 0) | 1.28 ± 0.03 | 2.40 ± 0.03 | OOM | 1.53 ± 0.04 |  |

**Table 11: ogbl-collab results on the forward and inverse splits when using EPS for each given Filter + Rank model configuration.**
| Heuristic | Split | GCN + BUDDY | BUDDY + GCN | RA + GCN | RA + BUDDY |
| --- | --- | --- | --- | --- | --- |
| CN | (0, 1, 2) | 8.50 ± 1.10 | 5.81 ± 0.11 | 7.42 ± 0.12 | 3.94 ± 0.51 |
| (0, 2, 4) | 12.85 ± 0.83 | 5.31 ± 0.22 | 7.07 ± 0.16 | 6.61 ± 0.30 |  |
| (0, 3, 5) | 15.35 ± 0.96 | 5.88 ± 0.16 | 7.52 ± 0.13 | 7.16 ± 0.09 |  |
| (2, 1, 0) | 5.46 ± 0.11 | 4.90 ± 0.08 | 5.24 ± 0.14 | 4.32 ± 0.19 |  |
| (4, 2, 0) | 5.36 ± 0.12 | 4.62 ± 0.16 | 5.27 ± 0.09 | 4.45 ± 0.12 |  |
| (5, 3, 0) | 5.96 ± 0.06 | 5.17 ± 0.09 | 5.15 ± 0.26 | 4.93 ± 0.11 |  |
| SP | ($\infty$, 6, 4) | 7.38 ± 0.82 | 7.10 ± 0.43 | 7.38 ± 0.42 | 3.84 ± 0.59 |
| ($\infty$, 4, 3) | 9.60 ± 0.39 | 6.24 ± 0.52 | 7.07 ± 0.46 | 7.63 ± 0.25 |  |
| (4, 6, $\infty$) | 6.86 ± 1.13 | 6.51 ± 0.24 | 6.11 ± 0.48 | 6.86 ± 1.13 |  |
| (3, 4, $\infty$) | 6.47 ± 0.24 | 4.86 ± 0.38 | 5.23 ± 0.23 | 6.47 ± 0.24 |  |
| PA | (0, 50, 100) | 15.92 ± 1.01 | 13.84 ± 0.14 | 13.23 ± 0.21 | 15.92 ± 1.01 |
| (0, 100, 200) | 9.47 ± 0.31 | 10.85 ± 0.11 | 10.71 ± 0.10 | 9.47 ± 0.31 |  |
| (0, 150, 250) | 9.60 ± 0.41 | 10.33 ± 0.15 | 9.96 ± 0.06 | 9.60 ± 0.41 |  |
| (100, 50, 0) | 14.34 ± 1.05 | 5.23 ± 0.28 | 5.07 ± 0.21 | 14.34 ± 1.05 |  |
| (200, 100, 0) | 8.35 ± 0.34 | 3.06 ± 0.08 | 2.93 ± 0.06 | 8.35 ± 0.34 |  |
| (250, 150, 0) | 5.50 ± 0.33 | 3.14 ± 0.14 | 2.79 ± 0.07 | 5.50 ± 0.33 |  |

**Table 12: ogbl-ppa results on the forward and inverse splits when using EPS for each given Filter + Rank model configuration.**
| Heuristic | Split | GCN + BUDDY | BUDDY + GCN | RA + GCN | RA + BUDDY |
| --- | --- | --- | --- | --- | --- |
| CN | (0, 1, 2) | 4.48 ± 0.33 | OOM | 3.53 ± 0.03 | 4.04 ± 0.26 |
| (0, 2, 4) | 3.79 ± 0.28 | OOM | 3.35 ± 0.03 | 3.42 ± 0.20 |  |
| (0, 3, 5) | 3.16 ± 0.10 | OOM | 3.22 ± 0.04 | 2.95 ± 0.13 |  |
| (2, 1, 0) | 3.19 ± 0.08 | OOM | 2.79 ± 0.11 | 2.58 ± 0.09 |  |
| (4, 2, 0) | 3.25 ± 0.09 | OOM | 2.64 ± 0.02 | 3.04 ± 0.05 |  |
| (5, 3, 0) | 3.36 ± 0.13 | OOM | 2.55 ± 0.09 | 3.10 ± 0.15 |  |
| SP | ($\infty$, 6, 4) | 4.00 ± 0.20 | OOM | 2.09 ± 0.17 | 3.89 ± 0.23 |
| ($\infty$, 4, 3) | 5.53 ± 0.92 | OOM | 5.18 ± 0.51 | 5.53 ± 0.94 |  |
| (4, 6, $\infty$) | 14.41 ± 0.67 | OOM | 6.46 ± 0.84 | 13.63 ± 0.97 |  |
| (3, 4, $\infty$) | 2.93 ± 0.15 | OOM | 2.48 ± 0.06 | 2.51 ± 0.14 |  |
| PA | (0, 50, 100) | 3.66 ± 0.38 | OOM | 4.34 ± 0.06 | 3.66 ± 0.38 |
| (0, 100, 200) | 3.19 ± 0.22 | OOM | 4.23 ± 0.03 | 3.19 ± 0.22 |  |
| (0, 150, 250) | 2.88 ± 0.06 | OOM | 3.78 ± 0.07 | 2.88 ± 0.06 |  |
| (100, 50, 0) | 2.05 ± 0.05 | OOM | 1.43 ± 0.05 | 2.05 ± 0.04 |  |
| (200, 100, 0) | 1.67 ± 0.03 | OOM | 1.26 ± 0.02 | 1.65 ± 0.05 |  |
| (250, 150, 0) | 1.66 ± 0.02 | OOM | 1.30 ± 0.02 | 1.64 ± 0.03 |  |

**Table 13: EMD calculations for ogbl-collab on the forward and inverse splits. Scores with a distance multiple-times different than the baseline are in bold**
| Heuristic | Split | Baseline | DropEdge | EPS - GCN | EPS - BUDDY |
| --- | --- | --- | --- | --- | --- |
| CN | (0, 1, 2) | 1.31 | 1.31 | 6.62 | 3.6 |
| (0, 2, 4) | 1.6 | 1.6 | 4.91 | 2.52 |  |
| (0, 3, 5) | 1.45 | 1.65 | 3.82 | 2.22 |  |
| (2, 1, 0) | 1.87 | 1.15 | 1.71 | 2.91 |  |
| (4, 2, 0) | 2.26 | 1.49 | 1.29 | 2.99 |  |
| (5, 3, 0) | 2.28 | 1.52 | 0.314 | 2.14 |  |
| SP | ($\infty$, 6, 4) | 5.93 | 5.94 | 0.012 | 0.012 |
| ($\infty$, 4, 3) | 5.35 | 5.38 | 0.002 | 0.003 |  |
| (4, 6, $\infty$) | 3.6 | 3.53 | 1.22 | 1.22 |  |
| (3, 4, $\infty$) | 1.85 | 1.78 | 3.17 | 3.23 |  |
| PA | (0, 50, 100) | 1.87 | 1.89 | 2.94 | 3.42 |
| (0, 100, 200) | 2.29 | 2.32 | 3.59 | 2.72 |  |
| (0, 150, 250) | 2.34 | 2.36 | 3.73 | 3.08 |  |
| (100, 50, 0) | 4.29 | 4.3 | 3.31 | 2.48 |  |
| (200, 100, 0) | 3.79 | 3.82 | 2.84 | 0.78 |  |
| (250, 150, 0) | 3.48 | 3.5 | 2.7 | 2.48 |  |

**Table 14: EMD calculations for ogbl-ppa on the forward and inverse splits.**
| Heuristic | Split | Baseline | DropEdge | EPS |
| --- | --- | --- | --- | --- |
| CN | (0, 1, 2) | 2.82 | 2.82 | >24hrs |
| (0, 2, 4) | 3.13 | 3.13 | >24hrs |  |
| (0, 3, 5) | 3.05 | 3.19 | >24hrs |  |
| (2, 1, 0) | 3.1 | 2.36 | >24hrs |  |
| (4, 2, 0) | 3.3 | 2.55 | >24hrs |  |
| (5, 3, 0) | 3.19 | 2.44 | >24hrs |  |
| SP | ($\infty$, 6, 4) | 5.81 | 5.84 | >24hrs |
| ($\infty$, 4, 3) | 1.36 | 1.4 | >24hrs |  |
| (4, 6, $\infty$) | 2.14 | 2.14 | >24hrs |  |
| (3, 4, $\infty$) | 0.72 | 0.72 | >24hrs |  |
| PA | (0, 5k, 10k) | 2.55 | 2.55 | >24hrs |
| (0, 10k, 20k) | 2.76 | 2.76 | >24hrs |  |
| (0, 15k, 25k) | 2.78 | 2.78 | >24hrs |  |
| (10k, 5k, 0) | 2.96 | 2.96 | >24hrs |  |
| (20k, 10k, 0) | 2.68 | 2.68 | >24hrs |  |
| (25k, 15k, 0) | 2.48 | 2.48 | >24hrs |  |

## Appendix E Additional Training Details

This section provides relevant details about training and reproducing results not mentioned in Section 4.1:

- •
NCNC for all datasets and splits, besides the ogbl-ppa PA splits, considers the ’NCNC2’ variant of NCNC with an added [depth](https://github.com/GraphPKU/NeuralCommonNeighbor/blob/main/README.md) argument of 2 []. For the ogbl-ppa PA splits, we apply a depth argument of just 1 in order to ensure that a single seeded run does not exceed 24 hour runtime.
- •
All experiments were conducted with a single A6000 48GB GPU and 1TB of available system RAM.
- •
Please consult the project [README](https://github.com/revolins/LPStructGen/blob/main/README.md) for building the project, loading data, and re-creating results.

## Appendix F Dataset Licenses

The dataset splitting strategy proposed in this paper is built using Pytorch Geometric (PyG). As such, this project’s [software](https://github.com/revolins/LPStructGen) and the [PyG datasets](https://pytorch-geometric.readthedocs.io/en/latest/) are freely-available under the MIT license.

## Appendix G Limitations

The proposed dataset splitting strategy is restricted to inducing distribution shifts solely with neighborhood heuristics. So, it does not consider other types of distribution shifts that are possible within the link prediction task (i.e. spatio-temporal [] or size [] shift). Additionally, since the neighborhood heuristics compute discrete scores produced from an input graph’s structural information and effectively training GNN4LP models requires no leakage with validation/testing, it may be difficult to determine the correct thresholds to extract a meaningful number of samples. For Common Neighbors and Preferential-Attachment, this is especially relevant with smaller training graphs, given that larger and/or denser graphs have inherently more edges. Therefore, larger and denser graphs have inherently more possible Common Neighbors and Preferential-Attachment scores. For Shortest-Path, splitting can be exceptionally difficult for denser graphs, as demonstrated with the tiny split sizes for ogbl-ppa in Table 8.

## Appendix H Impact Statement

Our proposed dataset splitting strategy mimics the formatting of PyTorch Geometric datasets. This means that our strategy is simple to implement, enabling future work involved with understanding this type of structural shift for link prediction and promoting beginner-friendly practices for artificial intelligence research. Additionally, since the structural shift we propose in this article affects real-life systems, which integrate link prediction models, this research can provide a foundation for the improvement of relevant technologies; which holds positive ramifications for society and future research. No apparent risk is related to the contribution of this work.

## Appendix I Exclusion of non-LP Generalization Methods

Given that this study is focused on elevating the current understanding for how link prediction models handle the generalized-case of structural shift, our focus was on two objectives: 1) producing and then benchmarking meaningful dataset splits relevant to structural shift in LP, 2) improving understanding on whether generalization methods specifically designed for LP aid GNN4LP on datasets shifted by our proposed splitting strategy. Given the lack of testing for LP-specific generalization methods under any form of distribution shift, our focus on 2) is especially pertinent in order to improve understanding on how LP-specific generalization methods aid performance under distribution shift. We refer readers to [] for more information on how non-specific generalization methods aid performance for link prediction models under spatio-temporal shift.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
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.
soundness: 2
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.
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.
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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: I am curious what is the main difference among node-level graph OOD method and link-level graph OOD method?
soundness: 3
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.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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?
soundness: 2
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.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
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?
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
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.
soundness: 3
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.
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.
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.

Meta-review: 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.

Decision: Reject