Towards Understanding Link Predictor Generalizability Under Distribution Shifts

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.

Within link prediction, the distribution shift problem remains largely unknown. We note that this is the first study to consider benchmarking performance for distribution shifts in link prediction. So, the foundational knowledge provided by our study enhances it's practical merit. Since ogbl-collab has a known distribution shift, while little remains known about how distribution shift functions and then affects link prediction performance; then it becomes increasingly important to understand how different and quantifiable distribution shifts affect performance in link prediction.

All other graph out-of-distribution benchmarks [1-4] manually induce distribution shifts in pre-existing datasets to generate datasets that suffer from distribution shift. As such, LPShift functions as a means to induce a distribution shift in order to better understand how distribution shift affects link prediction; a currently under-explored area of research in graph representation learning.

We also note, that the plots included in Figure 5 of our original submission makes an important distinction about the extent of the distribution shift for Common Neighbors between splits, whereas Figure 1 in the NCNC paper [5] is interested in the overall density of Common Neighbors. As such, our Figure 5 becomes more relevant for a study on distribution shift between different splits.

[1] Gui, Shurui, et al. "GOOD: a graph out-of-distribution benchmark." Proceedings of the 36th International Conference on Neural Information Processing Systems. 2022.

[2] 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).

[3] Koh, Pang Wei, et al. "Wilds: A benchmark of in-the-wild distribution shifts." International conference on machine learning. PMLR, 2021.

[4] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 33 (2020): 22118-22133.

[5] Wang, Xiyuan, Haotong Yang, and Muhan Zhang. "Neural Common Neighbor with Completion for Link Prediction." The Twelfth International Conference on Learning Representations.

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.

We agree this is important for clarity and have amended the additional results tables showing Hits@20 scores for ogbl-collab and ogbl-ppa to the revised Appendix Section F of our paper. The Tables are numbered: 8, 10, 12, and 14 respectively

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.

The traditional link prediction setting relies on random negative samples, such samples are known to be trivial for link prediction models to classify [1]. Given that LPShift is concerned with structural shift within a given dataset split, and therefore amongst the positive samples pulled from that same split, it becomes counter-intuitive to forego structure for the negative samples. Following the intuition provided by HeaRT, random samples extracted for the "Forward" CN split then allow the model to generalize more easily. Following the intuition demosntrate in our original Figure 1, the "Backward" CN split induces a more difficult scenario for the LP model to generalize to as the positive and negative samples are often hard to distinguish (e.g., all have 0 common neighbors).

Our intention is not to be misleading. So, in the Table 1 (shown below), we include MRR results for the ogbl-collab datasets affected by the 'Forward' and 'Backward' CN LPShift with random samples pulled from the original ogbl-collab dataset in order to verify our intuition.

Tables 1 (shown above): MRR Results for LPShift's CN Backward and Forward split on ogbl-collab.

We make three observations on Table 1:

1. The performance boosts significantly for the both splits versus the LPShift baselines with HeaRT sampling. We note that the forward split follows common LP assumptions; that LP models will generalize much better to testing data with more structural information. We also note that the performance boost for the backward split is not as significant as the performance increase for the forward split.
2. Common Neighbors, Adamic-Adar, and Resource-Allocation continue to outperform GCN and BUDDY on all of the 'Foward' splits and the CN - 5,3 split.
3. GCN outperforms BUDDY in the CN - 2,1 split, which follows along with the intuition presented in our article's Figure 1. However, BUDDY begins to outperform GCN once more structural information is made available.

Given observations (1), it is apparent that HeaRT leads to a decrease in performance for the initial LPShift baseline tests. However, observations (2) and (3) indicate the powerful impact that a change in structural information has on the performance of LP models. In particular, every tested LP model suffers under the CN - 2,1 split.

[1] Li, Juanhui, et al. "Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking." Advances in Neural Information Processing Systems 36 (2024).

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

We apologize for any confusion caused by a lack of clarity. Our revised paper now clarifies an 'inverse' split as a 'backward' split. We include an example of this below:

Lines 436-437: However, Figure 4 indicates that DropEdge only has a significant effect on EMD when handling the “backward” ogbl-collab CN split.

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?

This is a great suggestion, given that different GNN4LP models integrate structural features into their architectures, like RA into BUDDY or NCNC acts as a neural-version of Common Neighbors, then those models should naturally generalize better in scenarios where a given structual heuristic is increasingly present in the training data. Therefore, leveraging the strengths of different models as experts could enhance performance under distribution-shifted scenarios.

We have contacted the authors, who just recently made the Link-MoE code publicly-available. We will be running experiments in the meantime and hope to report back soon.

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.

Thank you for the suggestion, we include available results on PA and SP in Tables 2,3,4, and 5 as shown below. Given the expensive runtime of SP and the large size of the ogbl-collab and ogbl-ppa datasets, SP is still running on the remaining splits.

With the current results, we determine that even though PA and SP are relevant for link prediction, the methods fail to generalize under LPShift scenarios. This is likely due to the high-importance of local information for predicting links within ogbl-collab and ogbl-ppa.

Table 2 (shown above): MRR results for PA and SP on the Forward LPShift split of ogbl-collab.

Table 3 (shown above): MRR results for PA and SP on the Forward LPShift split of ogbl-ppa.

Table 4 (shown above): MRR results for PA and SP on the Backward LPShift split of ogbl-collab.

Table 5 (shown above): MRR results for PA and SP on the Backward LPShift split of ogbl-ppa.

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

As shown in Figure 6 of our original submission, the inherent Common Neighbor shift in ogbl-collab indicates that local structural information leads to decreased LP performance. Since LPShift allows manual and fine-grained control over the extent and type of structure used to split a graph dataset. LPShift then makes it possible to parse the specific structural characteristic affecting performance of LP models on ogbl-collab. For example, reduced LP performance on the CN - 2,1 split versus the CN - 5,3 split empirically demonstrates the importance of increased local structural information for enhancing performance on ogbl-collab.

On a similar note, given the flexibilty of LPShift as a splitting strategy, it is possible to integrate other structural perspectives, like global structural information with SP or high-level concepts such as preferential-attachment (PA). If LPShift is used in this manner then it serves as a way to provide a more nuanced perspective for structural analysis on an affected dataset.

Dear Reviewer RYKU,

Thank you for taking the time to review our work! Your input greatly improves the quality of our study.

We have posted our rebuttal and hope that it addresses all of your concerns, especially about the practical merit of LPShift. Please consider it in your evaluation and inform us of any additional concerns.

Kind Regards,

Authors

Table 7 (shown above): The rankings for all models with just HeaRT on ogbl-ppa, as determined by the Hits@20 Results from Table 5 in the HeaRT paper. The final six columns represent the change in Hits@20 for each LPShift split type and respective split direction versus the original HeaRT. Note: RA and BUDDY (3*) are tied for third best performing model. LPFormer was untested within the HeaRT paper and not included in these rankings.

Figure 3 still uses "inverse split".

Our apologies, Figure 3 has been updated with the correct title indicating 'Backward' Splits.

For the first subplot in Figure 5, I still cannot understand how it differs from the one in the NCNC paper. In the NCNC paper, they clearly state that they find a CN distribution shift between training and testing on the Collab dataset. Figure 5 in this paper almost repeats such a finding, adding one extra CN distribution of the validation set. The finding is too subtle to differentiate itself, which hurts the new knowledge brought by this study.

The intent of Figure 5 is to demonstrate that LPShift is capable of inducing a meaningful distribution shift. So, we include the first subplot, with the added validation split, to demonstrate the realistic distribution shift for the original ogbl-collab dataset. We then apply the "Backward" LPShift, as indicated from the changes in the distribution observed between the second to third subplot. We apply the 2 KS-test to determine whether the training/validation/testing distributions can be sampled from one another. A p-value of 0 indicating with statistical significance that the distributions are distinct, while a p-value of 1 indicating that the distributions cannot be distinguished from one another. We revise our paper's Section 4.4 to better clarify the contribution of LPShift along with the inspiration from NCNC, shown below in blockquotes:

The first subplot in Figure 5 extends the reasoning introduced with NCNC Wang et al. (2023a). As such, this subplot indicates there is a natural shift for CNs within the original ogbl-collab dataset Hu et al. (2020). The p-value of 0, measured across both split permutations, indicates that the training distribution of CNs is shifted from the validation and testing distributions. The second subplot depicts a randomly-split HK graph Holme & Kim (2002), where CN distributions for each split match one another, further indicated by the p-values of 1. The third subplot depicts the HK graph from the second subplot split with LPShift’s CN - 5,3 strategy, resulting in a distinct shift between all dataset splits, as confirmed by the 0 p-values. As such, LPShift induces structural shift that is as measurably dissimilar as the structural shift present in the original ogbl-collab dataset, even when the initial dataset splits are measurably identical. Additionally, the CN - 5,3 split causes the shape of the HK graph’s CN distributions to become more similar to the shift observed within the original ogbl-collab dataset, indicating that the ”Backward” LPShift strategy can function like a real-world distribution shift.

I appreciate the authors providing Table 8/10/12/14. However, what makes me confused is in the "Observation 1" in Sec 4.2. The authors claim that RA is robust to LPShift in Table 1, measured by ranking Hits@20. Then it further said RA is best-performing in Table 7, which is measured by MRR. These two different measures make it difficult to understand the context.

We have edited Observation 1 in Section 4.2, and made sure to highlight the best- and underline the second-best performing models within Tables 8/10/12/14. The updates indicate that RA is the best-performing model in Table 7 and Table 8, clarifying it's ability to rank and predict information under LPShift with both MRR and Hits@20. We provide the updated Section 4.2 in block quotes below:

As shown in Table 1, RA and GCN consistently out-perform or remain competitive with GNN4LP models, with more detailed results included in Appendix G. In Table 7 and 8, RA is overwhelmingly the best-performing, achieving scores at least 6 MRR and 13 Hits@20 higher than the next best model. However the results for the ogbl-ppa forward split, as shown in Table 9, indicate LPFormer as the best-performing model on the PA split and NeoGNN on the CN - 3,5 split, albeit with a much lower average score than those demonstrated within the ogbl-collab forward split.

There should be some typo in Table 12, where NCNC and RA always have the same results. Based on Table 12/14, the ranking of RA in Table 1 with backward PA split is calculated by mistake.

Thank you for catching this, this was indeed a typo. We have updated Table 12 with the correct scores and double-checked the ranking. Therefore, no changes were necessary within Table 1 to accurately reflect rankings as determined by the results for Tables 12 and 14.

a. If HeaRT still needs to be included in LPShift, a ranking table like Table 1 should be made for HeaRT alone. Then a comparison between the ranking of models under HeaRT vs under HeaRT+LPShift should tell how effective LPShift is to introduce an issue to LP models.

Thank you for your suggestions, we want to clarify one consideration about HeaRT and it's relation to LPShift.

• LPShift works as a natural extension of HeaRT; HeaRT was constructed as a sampling technique which solves two key issues posed by random negative sampling: 1) Non-personalized samples, where there is no change in the negative samples tested for each positive sample. 2) Easy Negative Samples, where negative samples have no relation to the positive sample; making it trivial for the link prediction model to distinguish if a link forms within a given sample. From which, HeaRT applies pairwise structural heuristics and then targets relevant edges within positive samples to create better negative samples. Given that LPShfit induces a unique type of structural covariate shift which is also focused on pairwise relations, we consider HeaRT an integral component of the LPShift strategy. The integration of HeaRT into LPShift becomes especially prevalent due to the LPShift+Random results, indicating that the models could be overfitting to structure due to the supervised nature of link prediction and the structural shift exacerbating the triviality of the random negative samples.

However, we agree that this sort of distinction is important to improve understanding of LPShift's effects. We provide Table 6 and 7 as requested in suggestion a.) to allow for comparison of the results across LPShift datasets and their splits to the HeaRT results. Additionally, we add the "Backward" and "Forward" LPShift columns to indicate the average change in Hits@20 between LPShift+HeaRT versus HeaRT for each split type and direction of a respective dataset.

We make these observations with included insights about the effect that LPShift has when combined with HeaRT:

• The rankings in our revised paper's Table 1 do not perfectly align with the HeaRT rankings. We attribute this to RA's reliance on structural information; meaning it drastically loses performance on "Backward" splits.
• ogbl-ppa has signficantly reduced performance, where the performance declines at least 59.5% but can rise up to 100% loss of performance. The only exception being the "Forward" SP split. We attribute this significant and consistent decrease in performance to the size of ogbl-ppa and it's relative abundance of positive and negative samples.
• The "Backward" CN and SP split for ogbl-collab typically result in a performance decrease ranging from 17.5% up to 100%. The only exceptions are GCN and NCNC. We attribute GCN's success since it does not rely on structure within it's architecture. We attribute NCNC's initial success on the "Backward" CN split to it's ability to effectively capture local information. However, NCNC loses 86.8% performance on the subsequent "Backward" SP split.
• The "Backward" PA and all "Forward" splits for ogbl-collab overwhelmingly lead to an increased performance for all models, typically resulting in 2 to 3 times better performance. This serves as measured proof for the prevailing assumption in link prediction; that LP models can generalize better to scenarios with more structural information than what was available in training. The only exception is for SEAL on the "Forward" SP split. We attribute this to the lack of neighborhood overlap, which inhibits the expressive power of SEAL's labelling trick.

Given these observations, it is clear that LPShift has a significant impact on LP performance, especially in the "Backward" the direction. In particular, the effect on performance for the ogbl-ppa dataset indicates how vulnerable GNN4LP models are to structural shift in larger datasets.

Table 6 (shown above): The rankings for all models with just HeaRT on ogbl-collab, as determined by the Hits@20 Results from Table 5 in the HeaRT paper. The final six columns represent the change in Hits@20 for each LPShift split type and respective split direction versus the original HeaRT Note: LPFormer was untested within the HeaRT paper and not included in these rankings.

Dear Reviewer RYKU,

Given that today is the last day to revise the paper, we hope to have addressed your concerns about the challenge that LPShift poses.

We have included LPShift's effect on performance (rebuttal Table 6 and 7) into Appendix Section J as Tables 23 and 24. We removed the HeaRT rankings from the paper revision given that it added noise to the percentage values in Tables 23 and 24. That and we believe that the percent change in performance is sufficient to indicate the challenge posed by LPShift as well as it's effect on HeaRT's original performance. We also provide discussion with insights on this effect, shown in blockquotes below:

As shown in Appendix Section J, the ”Backward” CN and SP splits on ogbl-collab and all ogbl-ppa splits result in a 30−90% performance decrease from the HeaRT standard (Li et al., 2024). This is especially notable given the difficulty HeaRT imposes on the original benchmark setting (Hu et al., 2020). We also note that the majority of PA and forward splits for ogbl-collab result in a 2-3 times performance increase. This result quantifies the prevailing assumption that GNN4LP generalize well in scenarios with increasing structural information (Mao et al., 2024; Wang et al., 2023a). However, LPShift’s ogbl-ppa suffers from the inverse scenario, where the majority of splits result in a 60 − 90% decrease in performance. Therefore indicating that LPShift has stronger effects across dataset domains, particularly when the dataset is larger.

We hope that this addresses your concerns and are happy to discuss any other concerns or questions.

Best Regards,

Authors

Table 10 (shown above): The model rankings for HeaRT and the ogbl-collab 'Forward' splits. HeaRT Rankings determined by the Hits@20 Results from Table 5 in the HeaRT paper. LPFormer is not included in this table since it was not included in HeaRT. (+) = Rank improvement, (-) = Rank decline.

Table 11 (shown above): The model rankings for HeaRT and the ogbl-collab 'Backward' splits. HeaRT Rankings determined by the Hits@20 Results from Table 5 in the HeaRT paper. LPFormer is not included in this table since it was not included in HeaRT. (+) = Rank improvement, (-) = Rank decline.

We hope this clarifies how LPShift affects HeaRT as a baseline. Once allowed, we will include these new rank tables into the revised article's Appendix. In particular, LPShift's overwhelming effect on HeaRT's ogbl-ppa and many "Backwards" ogbl-collab splits indicate that a significant structural shift occurs from the HeaRT baseline. Please let us know if there are any further concerns, we will be happy to discuss them.

Thank you for your feedback, your perspective improves the quality of our work immensely! We apologize for the confusion and provide justifications below:

• To clarify, Tables 6 and 7 from this rebuttal demonstrate the performance change that LPShift affects on the HeaRT baseline. Given the stark performance decrease seen on all ogbl-ppa splits and most of the "Backward" CN and SP ogbl-collab splits, LPShift serves as a means to induce a significant structural shift on the HeaRT baseline.

• We would like to further clarify why we include HeaRT in LPShift. The random samples used in the original link prediction evaluation bear little correlation to the positive samples [1], making it easy for the supervised LP model to distinguish the positive link from the negative. For example, if we consider just structure, positive link samples with 5 Common Neighbors will be easy to distinguish from negative samples with fewer than 5 Common Neighbors when pulling from the same distribution. This is a problem for real-world scenarios, given that realistic positive and negative link samples are likely to have many features in common. Our use of HeaRT samples resolves this issue by aligning the structural features of the positive and negative samples used within LPShift's valid and testing distributions.

[1] Li, Juanhui, et al. "Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking." Advances in Neural Information Processing Systems 36 (2024).

We agree that clarity for LPShift's impact on HeaRT performance is important. To demonstrate this change in performance, we include the HeaRT and LPShift+HeaRT ranks in Tables 8-11 below:

We make the following observations about the ranked results:

1. GCN displays resilience to ogbl-ppa's LPShift, as indicated by an average rank increase of 2.875 on the "Forward" split and 1.75 on the "Backward" split. Neo-GNN performs notably well with a respective increase of 2.75 and 1.625.
2. NCNC displays resilience to ogbl-collab's LPShift, indicated by an average rank increase of 1.825 on the "Forward" split and 2.875 on the "Backward" split.
3. GCN consistently performs 2nd or 1st against GNN4LP models on the ogbl-ppa datasets.
4. RA overwhelmingly performs 1st on the ogbl-collab "Forward" splits.
5. Where RA fails on the ogbl-collab "Backward" split, GCN will take 1st or 2nd. The only exception being the 'PA - 100,50' split.

Observations 1. and 2. provide clarity on the resilience of GCN, NCNC, Neo-GNN in dataset-dependent scenarios. It is worthwhile to note that NCNC experiences a sharp rank increase on 'CN - 4,2' and 'CN - 5,3' splits, indicating the impact of increased local structural information between training and validation.

Observations 1., 3., 4., and 5. indicate LPShift scenarios where GNN4LP methods lose much of the competitive advantage established on the original HeaRT baseline.

Table 8 (shown above): The model rankings for HeaRT and the ogbl-ppa 'Forward' splits. HeaRT Rankings determined by the Hits@20 Results from Table 5 in the HeaRT paper. LPFormer is not included in this table since it was not included in HeaRT. (+) = Rank improvement, (-) = Rank decline.

Table 9 (shown above): The model rankings for HeaRT and the ogbl-ppa 'Backward' splits. HeaRT Rankings determined by the Hits@20 Results from Table 5 in the HeaRT paper. LPFormer is not included in this table since it was not included in HeaRT. (+) = Rank improvement, (-) = Rank decline.

4. "Where RA fails on the ogbl-collab "Backward" split": On the ogbl-collab "Backward" split, RA drops dramatically when LPShift is introduced. If the conclusion here is that GCN generalized better, then similarly we conclude that RA generalizes worse.

RA ranks whether a link will form based on the RA heuristic. So, this result is a natural occurrence of the "Backwards" splits; where the training distribution has far more structural information than the testing distribution. Therefore, meaning the ranking predictor has limited information to effectively rank links. We agree that the language in the paper should make this distinction about the "Backward" split clear.

In fact, I think it can be beneficial to completely remove HeaRT from LPShift. Two reasons: 1. it makes the demonstration of experimental results easier to understand.

Although including HeaRT adds a level of nuance to our results, the random samples would not necessarily make the experimental results easier to understand. Many of the assumptions within our paper are made to simulate how link prediction operates within the real world.

Within the real-world setting, it is not apparent which validation and testing link samples are positive or negative. So, AI practitioners are required to extract a set of potential link candidates and then rank them based on some metric, like Common Neighbors or a Random-Walk, in order to build their positive and negative sets. HeaRT discusses this further in Appendix Section G.1 of their paper [1]. As such, we felt that HeaRT was the perfect addition to simluate the real-world scenario. However, we agree that this distinction is not clear within the paper and we will be certain to include language that clarifies this.

2. I suspect HeaRT alone can already introduce some structural distribution shift effect on graphs since it looks at negative testing edges with more Common Neighbors. And its effect is significant, probably more than LPShift. Without HeaRT, LPShift can show a stronger effect on the distribution shift issue.

This is an interesting consideration, and one of the key reasons why we study LPShift. Given that training samples are always random and likely to have 0 Common Neighbors; it then follows that ranking samples based on some heuristic is likely to introduce bias/shift when compared against validation and testing samples that are likely to contain at least a single Common Neighbor.

However, we note that even though LPShift use CNs as the primary heuristic for constructing negative validation and testing samples. HeaRT also avoids shift and bias by applying random-walk and PPR in order to capture global information and unique sample candidates (also detailed in Appendix Section G.1 of the HeaRT paper) [1].

Also, we note that any sampling techniques will draw from the bias or shift that is already present within the initial graph. Given this, HeaRT serves as a natural extension of LPShift since it operates on the same principle as LPShift.

[1] Li, Juanhui, et al. "Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking." Advances in Neural Information Processing Systems 36 (2024). https://arxiv.org/pdf/2306.10453

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 require.

We apologize for any confusion caused by a lack of clarity in our writing. We make the necessary edits in our revised paper, as highlighted in blue. We include an example of this revision in block quotes below:

We apply the 2-sample Kolmgorov-Smirnov (KS) test (Hodges Jr, 1958) to compare training, validation, and testing distributions before and after applying LPShift. As a controlled baseline to test LPShift, we generate a Holme-Kim (HK) graph (Holme & Kim, 2002) with a 40% chance to close a triangle, allowing the HK graph to contain numerous Common Neighbors without becoming fully-connected.

Additionally, we update the writing with a better description for Figure 1 in the Introduction section. We include this revision in block quotes below:

Consider the three graphs in Figure 1 as samples pulled from a larger graph dataset. In order of appearance, each of the three graphs represent samples from the: training, validation, and testing splits of our dataset. Our task is to predict whether new links will form between existing nodes. These predicted links are shown as dotted lines with colors: “green” = training, “blue” = validation, “red” = testing. An optimal LP model trained on the first graph sample effectively learns a representation understanding source and target nodes with 2 Common Neighbors Zhang & Chen (2018), making the model effective at predicting new links in structure-rich scenarios. However, such a model is likely to fail when predicting links on the subsequent validation and testing samples; the second and third graph in Figure 1 with 1 CN and 0 CNs, respectively. The learned representation necessary to capture the differing pairwise relations in the second and third graphs requires generalizing to a scenario with fewer CNs, and therefore less structural information. As such, the previously-mentioned scenario represents a case of structural covariate shift, where the training distribution cannot effectively model the testing distribution, defined mathematically as P^{Train}(X)̸ = P^{Test}(Y). LPShift, our proposed splitting strategy, provides a controllable means to induce the scenario shown in Figure 1 (labelled in experiments as the CN - 2,1 split), as well as fifteen other tested scenarios. More details on structural shift are included in Section 3.2.

All splits are based on statistical heuristics without any real-world shift splits, e.g., temporal shift, which produces not enough the significance.

We would like to clarify core contributions of LPShift to demonstrate it's significance:

• The application of LPShift is novel. LPShift uses structural heuristics in a flexible splitting strategy, where a user controls the: magnitude, type, and direction of the structural shift in their desired dataset. Since the user is aware of the magnitude, type, and direction of shift that they applied to their dataset; any further analysis on the updated dataset enables understanding distribution shift in link prediction in a way that has never been previously quantified.

• Figure 5 within our submission indicates that ogbl-collab, a dataset with temporal shift also experiences a structural shift with common neighbors. Given that a change in graph structure functions as a change over time, then temporal shift and structural shift can be considered synonymous with one another. For example, the CN - 2,1 split of LPShift (as shown in our updated Figure 1) causes models to learn on a well-connected training split and then generalize on disconnected testing data, just like temporal shift. Additionally, link prediction heuristics are integrated into high-performing GNN4LP models, such as RA in BUDDY and CN into NCNC, indicating their effectiveness as tools for enhancing link-prediction models and relevance to the link prediction problem.

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.

Our initial study could not consider traditional generalization methods given that the traditional methods rely on invariance between training environments to generalize in OOD scenarios. LPShift considers structural covariate shift, $P^{Train}(X) ≠ P^{Test}(Y)$, within a single environment, making evaluation of the traditional generalization baselines impractical.

To overcome this barrier, we construct an updated test setting which applies a given link prediction heuristic on each LPShift split to build training environment subsets with distinctive structural characteristics. Given these distinctive structural characteristcs, the environmental subsets are well-suited for testing how well the traditional generalization methods work under LPShift.

Following the standard set in the GOOD paper [1], we tuned the parameters for IRM across {0.1, 1, 10} and VREx across {10, 100, 100}.

We include results which apply IRM and VREx to BUDDY and GCN for all tested splits in the table detailed below:

Table 1 (shown above): MRR Results for VREx and IRM applied to GCN and BUDDY on the "Forward" LPShift splits of ogbl-collab.

Table 2 (shown above): MRR Results for VREx and IRM applied to GCN and BUDDY on the "Backward" LPShift splits of ogbl-collab.

From our tests we make three observations:

1. VREx is the only method that increases performance under LPShift. The CN - 1,2 split for ogbl-collab is notable example, given that it nearly doubles BUDDY's original performance.
2. IRM fails to improve performance across all splits and even reduces performance by 33% in certain scenarios; such as the "Backward" splits for SP on ogbl-collab.
3. Since IRM and VREx rely on multiple environmental subsets in the training data, training all of these methods is significantly slower following our current methodology of dividing invariant subsets.

The hyper-parameter sweeping space is not large enough to produce significant experimental conclusions.

Our initial study analyzed 32 unique dataset splits. From which we measured the performance over 5 different seeds, and tuned over a grid search-space of {dropout: 0.1, 0.3} and {learning rate: 1e-3, 1e-2}. When we consider the 7 tested models, this results in a total of 4,480 independent runs to conduct just the baseline experiments for this paper. Additional experiments were necessary for the analysis.

Initial parameter tuning within our study included tuning parameters such as batch size and L2-regularization. However, tuning these two parameters provided limited effect on performance. Given the massive computation load for conducting baseline experiments, we prioritized conducting additional analysis over including more parameters in our grid search.

Additionally, it is quite common for graph benchmark papers to limit fine-tuning of tested models and prioritize testing more models or datasets. We include a list detailing tuning practices for other graph-related benchmarks:

• GOOD [1] -- Fixed the baseline model parameters and focused on tuning single hyperparameters in generalization algorithms.
• DrugOOD [2] -- Grid search over learning rate and batch size, average performance over 3 random seeds.
• WILDS [3] -- Grid search over learning rate and L2-regularization strengths on publicly-available pre-trained models.
• OGB [4] -- Fixed baseline model parameters, tuned on dropout ratio between 0.0 and 0.5.

[1] Gui, Shurui, et al. "GOOD: a graph out-of-distribution benchmark." Proceedings of the 36th International Conference on Neural Information Processing Systems. 2022. [2] 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). [3] Koh, Pang Wei, et al. "Wilds: A benchmark of in-the-wild distribution shifts." International conference on machine learning. PMLR, 2021. [4] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 33 (2020): 22118-22133.

As such, our hyperparameter grid-search across 6 variants of learning rate and dropout along with our initial batch size investigations reaches the standard set by other graph benchmark papers. This is especially true given that any remaining hyperparameters were fixed following guidance provided in the original paper for a given model and other graph benchmarks measure performance across fewer seeds than what LPShift is tested on.

We conduct grid-search tuning on dropout: {0.1, 0.3} and learning rate: {1e-4, 5e-3} for GCN across all splits on ogbl-collab and ogbl-ppa to demonstrate empirically the robustness of our model performance. With the best results for MRR detailed below:

Table 2 (shown above) : MRR Results for GCN on LPShift's ogbl-collab with additional tuning on dropout and learning rate.

Table 3 (shown above) : MRR Results for GCN on LPShift's ogbl-ppa with additional tuning on dropout and learning rate.

Given Table 2 and 3, we make three observations:

1. Even with additional tuning on learning rate and dropout, only two of the thirty-two possible results receive a performance boost large enough to eliminate overlap between the score distributions from our original GCN results.
2. The only scenarios where further tuning increases performance is the CN - 2,4 and CN - 3,5 split on ogbl-collab. We note that this follows general assumptions with link prediction, where a model can be expected to generalize more effectively on validation and testing data with more structural information than training.
3. None of the "Backward" splits for both datasets receive any noticeable change in their originally-reported performance. This follows along with the initial motivation provided by Figure 1 in our revised paper. As such, experimental conclusions drawn about the extent that LPShift impacts performance holds. So, this result actually serves to bolster any experimental conclusions about the impact of LPShift, given the principle that all of the "Backward" LPShift splits subsequently lose structural information from training to validation and then testing.

As a benchmark, no code is provided.

We are sorry the code was not available within our main paper submission. We include the link from Appendix Section C here: Anonymous GitHub Link

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?

Subplot 1 in Figure 5 of our original submission details that the unaltered ogbl-collab dataset suffers from a structural shift in Common Neighbors. From there, Figure 6 demonstrates that the CN distribution shift induced by LPShift can behave like the temporal shift in ogbl-collab. Given that Figure 6 and 1 are both concerned with CN - 2,1 split, we conclude that the decreased structural information contained within the validation and testing simulates a scenario where LP models must generalize to new nodes with relatively few edge make connections to an existing dataset; like how new papers cite previous work but have no citations themselves.

In order to better align with GOOD [6], we attempted to apply Mixup for LPShift. However, the original Mixup does not function for graph data [7]. There is an implementation of Mixup designed for node- and graph-classification [8], but has no readily-apparent link-prediction equivalent.

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

[7] Zhang, Hongyi. "mixup: Beyond empirical risk minimization." arXiv preprint arXiv:1710.09412 (2017).

[8] Wang, Yiwei, et al. "Mixup for node and graph classification." Proceedings of the Web Conference 2021. 2021.

As a benchmark, it is important to be transparent about all the details. Instead of claiming using the recommended hyperparameter searching spaces, please list them explicitly. I have seen many works saying that using recommended hyperparameters without really doing a full evaluation.

We agree that transparency on model parameters is critical for effective AI research, especially benchmarking work. We have revised our paper to include fixed hyperparameters in Appendix Section D - Table 21 of our revised paper (also shown below):

Table 5 (shown above): Fixed model hyperparameters for each tested model across respective LPShift datasets.

We also provide additional details in Appendix Section D on parameters that are not set by default within our updated code repository, shown here in block quotes:

• NCNC for all datasets and splits, besides the ogbl-ppa PA splits, considers the ’NCNC2’ variant of NCNC with an added depth argument of 2 Wang et al. (2023a). 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. • NeoGNN use 2-hop neighborhoods on the LPShift ogbl-collab datasets and 1-hop on the LPShift ogbl-ppa datasets. • Initial investigations on batch size fixed learning rate at 1e−3 and dropout at 0.1, model performance was then tested for a single run across a space of {8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536}. This was done with the intent to balance computational time with performance when conducting full experiments.

The quality of the code provided is not high enough without minimal instructions, documentation, and proper coding structures, which is not usable for most of the readers. I highly encourage the authors to align their work with previous benchmarks.

The replication of results is important for us as well. To better align with benchmarks like HeaRT and GOOD, we have updated our README, gen_synth.sh, and run/ script files. All files are available at the following link: Updated Anonymous Repository. Note: All hyperparameters in their respective run/{model_name}.sh files are fixed to recreate results within our paper.

Compared to the previous benchmark like GOOD the authors mentioned. The traditional OOD baselines are still not enough. I appreciate the new results on IRM and VREx, where the authors found good performances on VREx. I believe the authors have already realized that, in this case, it is necessary to evaluate traditional OOD baselines comprehensively. Please refer to the GitHub Repo of DomainBed [1] for more typical baselines.

Thank you for your prompt response! We agree additional evaluation is important to understand the scope of the problem posed by LPShift. To demonstrate this, we include current results for GroupDRO, DANN, and Deep CORAL in Table 4. The generalization methods were tuned over the same parameter space as GOOD:

• GroupDRO: {0.1, 0.01, 0.001}
• DANN: {0.01, 0.1, 1.0}
• Deep CORAL: {0.01, 0.1, 1.0}

We note that our 5 newly-tested generalization methods are comprehensive in the breadth of their functionality for improving performance under distribution shift:

• IRM determines invariant correlations across training environments [1].
• VREx is specially designed for covariate shift and extrapolating to variance within training environments [2].
• GroupDRO regularizes weights for the worst training environments to interpolate towards better performance [3].
• DANN applies additional layers to generate adversarial predictions to then enhance domain adaptation [4].
• Deep CORAL computes a covariance and applies it in order to better align training and testing distributions [5].

Table 4 (shown above): MRR results for GroupDRO with GCN on LPShift's ogbl-collab splits.

We make three additional observations based on Table 2 and Table 4:

1. DANN and Deep CORAL improve performance on just the SP - 17,26 and PA - 50, 100, and PA - 100, 200 splits.
2. GroupDRO does not succeed at improving performance.
3. All "Backward" splits do not experience a significant increase in performance.

We attribute all observations to the graph structure in the training environments. There are two explanations:

• The CN - 1,2 split contains limited structure within the training environment (i.e. zero Common Neighbors), meaning that invariance across each training environment has limited usefulness for improving downstream performance.
• The "Backward" splits have plenty of structural information within their training environments (i.e. CN - 5,3 contains 5 Common Neighbors at minimum) but must generalize to validation and testing splits with increasingly limited structural information. Therefore, eliminating any advantage provided by our 5 tested generalization methods.

[1] Arjovsky, Martin, et al. "Invariant risk minimization." arXiv preprint arXiv:1907.02893 (2019).

[2] Krueger, David, et al. "Out-of-distribution generalization via risk extrapolation (rex)." International conference on machine learning. PMLR, 2021

[3] Sagawa, Shiori, et al. "Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization." arXiv preprint arXiv:1911.08731 (2019).

[4] Ganin, Yaroslav, et al. "Domain-adversarial training of neural networks." Journal of machine learning research 17.59 (2016): 1-35.

[5] Sun, Baochen, and Kate Saenko. "Deep coral: Correlation alignment for deep domain adaptation." Computer Vision–ECCV 2016 Workshops: Amsterdam, The Netherlands, October 8-10 and 15-16, 2016, Proceedings, Part III 14. Springer International Publishing, 2016.

Dear Reviewer 15W6,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

Thank you, we appreciate your dedication to help us improve our work!

We include the results for the traditional OOD generalization method in our revised paper's Appendix Section H as Tables 19 and 20. We include a reference to the Tables including appropriate citations in Section 4.4 under the subsection 'Does GNN4LP generalize and do generalization methods work?'. Shown in block quotes below:

Traditional generalization methods (Arjovsky et al., 2019; Sagawa et al., 2019; Ganin et al., 2016; Sun & Saenko, 2016), such as VREx (Krueger et al., 2021), achieve some promising results. However, these gains are typically marginal, especially on the ”Backward” ogbl-collab split; as indicated in Appendix Section H

We note that the anonymous repository is the functional code for this paper and includes a detailed README and shell scripts to enable replication of baseline results reported in this paper.

Given the technical debt within the repository, it will likely take longer than the review period to truly improve the code's standard. However, we acknowledge that the code repository is unwieldy and provide a plan detailed below:

Within the next few days:

• Flatten the folder structure to provide easier access to code modules.
• Re-organize modules for easier results replication.

Within the next few months:

• Build a pip package or integrate LPShift into PyTorch Geometric.
• Archive the current working repository with a link to a re-factored project repository.

We hope this addresses your concerns, please let use know if there are any specific pain points within the code repository that need addressing.

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. (1) Provide concrete examples of real-world scenarios where link prediction models face distribution shifts.

Our apologies for the lack of clarity on this distinction. We have updated the Introduction section and Figure 1 to provide a more intuitive understanding of this problem and how it relates to covariate shift. We include this revision below in block quotes:

Consider the three graphs in Figure 1 as samples pulled from a larger graph dataset. In order of appearance, each of the three graphs represent samples from the: training, validation, and testing splits of our dataset. Our task is to predict whether new links will form between existing nodes. These predicted links are shown as dotted lines with colors: “green” = training, “blue” = validation, “red” = testing. An optimal LP model trained on the first graph sample effectively learns a representation understanding source and target nodes with 2 Common Neighbors Zhang & Chen (2018), making the model effective at predicting new links in structure-rich scenarios. However, such a model is likely to fail when predicting links on the subsequent validation and testing samples; the second and third graph in Figure 1 with 1 CN and 0 CNs, respectively. The learned representation necessary to capture the differing pairwise relations in the second and third graphs requires generalizing to a scenario with fewer CNs, and therefore less structural information. As such, the previously-mentioned scenario represents a case of structural covariate shift, where the training distribution cannot effectively model the testing distribution, defined mathematically as P^{Train}(X) \neq P^{Test}(Y). LPShift, our proposed splitting strategy, provides a controllable means to induce the scenario shown in Figure 1 (labelled in experiments as the CN - 2,1 split), as well as fifteen other tested scenarios. More details on structural shift are included in Section 3.2.

Additionally, we acknowledge that realistic examples are important for the practical applicability of our work, and amend these examples into a new Appendix Section. The examples are as follows:

• Adversarial Recommender Systems = Shortest-Path: A company may want to understand which products to avoid showing to a potential customer without need to hear the user's preferences directly. In this scenario, global information, as captured by Shortest-Path, becomes the most valuable for the specific use-case.
• Social Recommender Systems = Preferential-Attachment: A video-streaming platform working with independent content creators may wish to understand what drives users to engage with the platform's content creators, so that engagement can increase for less-popular creators. As a starting point, the content creators with the most followers may have different characteristics that increase engagement versus less-popular creators. So, the streaming platform may wish to tune their dataset to determine if their recommendation system can generalize from more to less-popular creators.
• Movie Recommender Systems = Common-Neighbors: A movie-streaming platform wants to provide suggestions to users that are the most relevant to the user's current interests. So, the movie platform sorts possible movie recommendations by how much overlap the movies share with one another. In order to enhance exposure to new movies that overlap with a user's interests, the streaming platform can apply the Common Neighbor LPShift to their dataset to force the algorithm to generalize in a scenario where movies may not fully-overlap.

(2) Clarify how the proposed distribution shift differs from or relates to graph-level changes + Can’t we consider changes in edge connections as changes at the graph level?

Since link prediction considers interactions between source and target nodes, it operates at a finer-scale than what is relevant for graph-classification. Even though enough link-level edits can result in the entire graph structure changing, the addition of a few nodes with sparse edges to a social network is unlikely to induce a graph-level shift. Whether another link will form between these new nodes is likely to remain difficult for link prediction models to predict, even if node or graph classification models succeed at distinguishing the update graphs/nodes. As such LPShift applies pairwise structural heuristics as a means to target link-level shifts within graph datasets.

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) Explain more explicitly why existing graph-level distribution shift benchmarks are insufficient for link prediction tasks.

Existing graph benchmark datasets are concerned entirely with graph- and node-classification, although structural dynamics are important for building effective classifiers with these datasets, (i.e. classifiers should be aware of the differences in molecule structures). These datasets are more concerned how the features define the way the graph is represented. For example, OGB and DrugOOD select similar (or dissimilar) molecule scaffolds within a given molecule dataset to group molecules with backbone structures in the same splits. Link prediction, and by extension LPShift, is concerned with modelling finer-scale connections of links forming.

Since link prediction is a supervised task, LP models must generalize to scenarios where two nodes with dissimilar features will form a link but two nodes with similar features may not. For example, children in the same grade may take all of their classes together but never become friends due to conflicting interests and vice versa. To effectively model such a scenario, LPShift applies pairwise heuristics to control for the extent that edge structure may influence link prediction. If we were too apply the scaffold split used within OGB or DrugOOD then there is no guarantee that there is a structural shift for the molecule edges at a scale small enough to be applicable for link prediction.

There is a practical difference between graph- or node-classification and link prediction as downstream tasks for graph representation learning. Even though a node-classificaiton model could consider pairwise dynamics; it is impractical for a link prediction model to consider just node labels in order to predict if a link will form between said nodes. Pairwise dynamics are distinct in that they determine how a graph forms on a finer scale, whereas node information constitutes what a graph is made of. The distinctness of these pairwise dynamics then necessitates dedicated evaluation to edge structures within the graphs. As such, LPShift provides a mean to measurable define a shift in these pairwise dynamics to allow evaluation that is relevant for link prediction.

There has been no foundational work that studies how distribution shift affects link prediction performance. As such, this study quantifies what effect structural shift has on LP performance.

There are also no graph benchmarks that are specifically catered towards link prediction, meaning that the problem itself is so under-studied that even knowing where to start is difficult. This study aims to provide a starting point for building new methods.

Even though ogbl-collab is a link-prediction dataset with a known distribution shift, there is no currently practical means to define a metric on the extent that ogbl-collab experiences a distribution shift. So, LPShift provides a benchmark that determines how changes in the direction and intensity of structural shift impacts (and typically decreases) link prediction model performance.

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%.

We would like to clarify that Table 2 indicates results for ogbl-collab and ogbl-ppa. The application of DropEdge across all LPShift splits of ogbl-collab indicate only a slight increase of 4% and 2% on the forward and backward split, respectively. On ogbl-ppa, DropEdge fails to increase the performance when applied to the backward split and even reduces performance by 0.5% when applied to the forward split.

This implies that DropEdge doesn't work to improve performance on our datasets, especially in the backward split scenario. As demonstrated in Figure 1 and 6 of our original submission, the backward split scenario is analogous to realistic distribution shifts.

Additionally, in Tables 1 and 7, simple RA and GCN show strong performance.

We consider the strong performance of RA and GCN versus GNN4LP models a symptom of the larger problem caused by distribution shift in link prediction. Why bother training advanced GNN4LP models when structural heuristics can achieve similar, if not better, results in a small fraction of the time and computations? Such a result suggests that new methods need to be created in order to tackle distribution shifts for link prediction. This becomes especially pertinent when advanced GNN4LP models, which are designed to understand pairwise dynamics in graphs, fail to generalize under LPShift since they are more sensitive to structural changes in the dataset versus simpler baselines.

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

Thank you for the suggestion, readability is a priority of ours. However, our submission uses the template and style provided by the ICLR Conference. So, it may violate ICLR policy to implement this suggestion.

Dear Reviewer xF2u,

Thank you for taking the time to review our work, your input greatly improves the quality of our study!

We have posted our rebuttal and hope that it addresses all of your concerns, especially about LPShift's practicality when compared to realistic distribution shift scenarios. Please consider it in your evaluation and inform us of any additional concerns.

Kind Regards,

Authors

Dear Reviewer xF2u,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

The novelty is somewhat concerning to me since there is no comprehensive approach proposed.

Thank you for the suggestion, this was a strong consideration in our initial investigation of this study. Since distribution shift in link prediction is less-studied than distribution shift in graph and node classification, we consider LPShift as a means to understand independent structural mechanisms that affect the formation of links within networks. As such, we build LPShift to serve as a tool which induces distribution shift in current link prediction datasets and benchmark those results.

Since there is limited foundational work on distribution shift in link prediction, we submitted this paper to the datasets and benchmarks track. Therefore, the goal of this paper is to construct a foundational understanding on structural shift in link prediction. This foundational understanding can then foster more research towards building models that can comprehensively handle distribution shift relevant for link prediction.

The paper lacks detailed theoretical analyses to support their main claims.

Given that this paper is intended as a datasets & benchmarks submission and meant to empirically understand how distribution shift can occur in link prediction datasets, we have prioritized results over theory. In the future, we believe that a paper in similar style to [1] as a means to provide a theoretical perspective.

However, we revise Section 1 in our paper to provide mathematical definitions on how LPShift is a special case of structural covariate shift and relates to more general covariate shift. We include these revisions below as well:

Section 1:

Consider the three graphs in Figure 1 as samples pulled from a larger graph dataset. In order of appearance, each of the three graphs represent samples from the: training, validation, and testing splits of our dataset. Our task is to predict whether new links will form between existing nodes. These predicted links are shown as dotted lines with colors: “green” = training, “blue” = validation, “red” = testing. An optimal LP model trained on the first graph sample effectively learns a representation understanding source and target nodes with 2 Common Neighbors Zhang & Chen (2018), making the model effective at predicting new links in structure-rich scenarios. However, such a model is likely to fail when predicting links on the subsequent validation and testing samples; the second and third graph in Figure 1 with 1 CN and 0 CNs, respectively. The learned representation necessary to capture the differing pairwise relations in the second and third graphs requires generalizing to a scenario with fewer CNs, and therefore less structural information. As such, the previously-mentioned scenario represents a case of structural covariate shift, where the training distribution cannot effectively model the testing distribution, defined mathematically as P^{Train}(X) \neq P^{Test}(Y). LPShift, our proposed splitting strategy, provides a controllable means to induce the scenario shown in Figure 1 (labelled in experiments as the CN - 2,1 split), as well as fifteen other tested scenarios.

[1] Mao, Haitao, et al. "Demystifying structural disparity in graph neural networks: Can one size fit all?." Advances in neural information processing systems 36 (2024).

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.

We clarify that this paper was submitted to the dataset & benchmarks track for ICLR. However, we acknowledge that further insights are important to enhance pracical applicability of this research. As such, we updated analysis within Section 4.2 and the Conclusion to provide more practical insights:

Section 4.2:

Observation 3: Impacts on Performance Vary by Model. Note: In order to save space, all raw scores are stored in Appendix Section F within Tables 7 to 14. Common Neighbors: Most models fail to generalize on the “Backward” CN splits. However, once more Common Neighbors are made available in the CN - 4,2 and CN - 5,3 splits; NCNC performs 2 to 3 times better than other GNN4LP models. Therefore, indicating that it is possible to generalize with limited local information. Shortest-Path: GNN4LP Models which rely more on local structural information (i.e. NCNC, LPFormer, and SEAL) typically suffer worse under the “Backward” SP splits, resulting in the models consistently under-performing 2x to 4x worse versus BUDDY or GCN. Therefore, indicating the necessity for models to extrapolate in scenarios in an absence of local structural information. Preferential-Attachment: There is limited consistency for trends between model performance for the PA splits. However, it is important to note that performance on the PA split often exceeds the original ogbl-collab but reduces drastically with LPShift’s ogbl-ppa. Therefore, indicating the impact that structural shift incurs on larger datasets.

Conclusion:

Further analysis with EMD calculations and CN distributions indicate that current generalization methods do not improve performance under structural shift. As such, LPShift provides a challenging problem requiring new considerations about how structure functions within link prediction architectures.

I am curious what is the main difference among node-level graph OOD method and link-level graph OOD method?

Thank you for the question, link prediction (LP) is unique from graph- and node-classification since LP is concerned with determining if a link forms between two nodes for a given sample. Advanced link prediction models take advantage of this princple to consider pairwise interactions between nodes and improve model performance. As such, LPShift leverages LP-relevant structural heuristics to create scenarios where this pairwise information is shifted from the original dataset. Therefore, creating a unique type of structural covariate shift affiliated with pairwise information in graph data. Since the node- and graph-classification tasks are not concerned with structural information encoded within edges, understanding these pairwise dynamics for graph- and node-level shifts is irrelevant. For example, understanding a change in graph size means that the graph represents a new molecule is more important for classifying the graph than understanding that a link will form between two atoms in a given molecule.

Dear Reviewer dNUs,

Thank you for taking the time to review our work! Your input greatly improves the quality of our study.

We have posted our rebuttal and hope that it addresses all of your concerns, especially about the theory and analysis contained within our study. Please consider it in your evaluation and inform us of any additional concerns.

Kind Regards,

Authors

Dear Reviewer dNUs,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

Dear Reviewer dNUs,

Thank you for your review, we appreciate the input since it improves our work! If you have any further concerns or questions please feel free to leave a comment.

Best Regards,

Authors

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.

We are sorry for any lack of clarity within the writing. We've revised the paper submission to make it consistent. We highlight edits in blue, including Table captions in the Appendix. We include example sentences of this correction, as detailed below:

Lines 433-434: However, Figure 4 indicates that DropEdge only has a significant effect on EMD when handling the “backward” ogbl-collab CN split... Lines 361-364: On the “backward” 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 (Wang et al., 2023a).

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.

Our revised Discussion section 4.2 includes a new 'Observation 3', highlighted in blue, that provide more detailed analysis on how different splitting strategies affect LP model performance and relevant insights about structural dynamics that can aid choosing effective GNN4LP models. Shown below in block quotes:

Common Neighbors: Most models fail to generalize on the “Backward” CN splits. However, once more Common Neighbors are made available in the CN - 4,2 and CN - 5,3 splits; NCNC performs 2 to 3 times better than other GNN4LP models. Therefore, indicating that it is possible to generalize with limited local information. Shortest-Path: GNN4LP Models which rely more on local structural information (i.e. NCNC, LPFormer, and SEAL) typically suffer worse under the “Backward” SP splits, resulting in the models consistently under-performing 2x to 4x worse versus BUDDY or GCN. Therefore, indicating the necessity for models to extrapolate in scenarios in an absence of local structural information. Preferential-Attachment: There is limited consistency for trends between model performance for the PA splits. However, it is important to note that performance on the PA split often exceeds the original ogbl-collab but reduces drastically with LPShift’s ogbl-ppa. Therefore, indicating the impact that structural shift incurs on larger datasets.

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?

The importance of benchmarking distribution shifts in link prediction is threefold:

1) Data Perspective: To clarify, link prediction is a task focused on understanding the dynamics present when edges form between nodes; requiring models to effectively understand these dynamics to determine whether a link will form (or not). As such, link prediction is more interested in pairwise dynamics than what is necessary for graph and node classification. Due to this distinction, there is limited overlap between graph/node classification and link prediction. As such, distribution shifts that are relevant in graph and node classification do not mean as much in link prediction. For example, we consider the scaffold shift imposed on molecule datasets within the DrugOOD benchmark. This special type of structural shift groups molecules with similar subgraphs in a way to induce an out-of-distribution scenario. Given that DrugOOD scaffold shift is not associated with the formation of links, then it loses it's relevancy when applied to models that learn pairwise dynamics necessary for link prediction.

2) Model Perspective: Structural heuristics that consider pairwise information are important for SOTA link prediction models. For example, BUDDY integrates RA directly into it's architecture and NCNC elevates CN into a neural architecture. SOTA node classification models can be concerned with how graph structure may enhance node features. For example, GLEM is a node classification model that merges text-attributed graphs architectures with graph structure to produce SOTA performance on ogbn-products. However, instead of considering pairwise information, GLEM leverages the information of neighboring nodes to produce better node classifications; completing ignoring how altering edges may affect the model.

3) Application Perspective: There is a practical difference between graph- or node-classification and link prediction as downstream tasks for graph representation learning. Even though a node-classificaiton model could consider pairwise dynamics; it is impractical for a link prediction model to consider just node labels in order to predict if a link will form between said nodes. Pairwise dynamics are distinct in that they determine how a graph forms on a finer scale, whereas node information constitutes what a graph is made of. The distinctness of these pairwise dynamics then necessitates dedicated evaluation to edge structures within the graphs. As such, LPShift provides a mean to measurable define a shift in these pairwise dynamics to allow evaluation that is relevant for link prediction.

[1] Zhao, Jianan, et al. "Learning on Large-scale Text-attributed Graphs via Variational Inference." The Eleventh International Conference on Learning Representations.

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.

Benchmarks on link prediction models have begun to reach near-perfect performance. However, structural shift causes a noticeable decrease in performance, even for datasets in the same domain. For example, GraphGPT(d1n30) reaches an MRR score of 93.05±0.2 on the ogbl-citation2 dataset whereas ogbl-collab lags behind with a Hits@50 score of 71.29±0.18. As demonstrated in our original submission's Figure 5, there is a noticeable shift in the Common Neighbors distribution between the training and validation/testing splits of the original ogbl-collab. Since both ogbl-collab and ogbl-citation2 are split temporally, then it becomes less promising to induce time-based shifts. This is due to the fact that the graph structure in citation networks is not likely to change over time, meaning that a quantifiable temporal shift which decreases performance is difficult to induce. LPShift handles this problem by using structural heuristics to create an easily-defined threshold; allowing researchers to determine the exact value that contributes to a decrease in performance.

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.

Thank you for bringing this to our attention. We have updated Figure 1 to demonstrate the CN - 2,1 LPShift scenario instead of the originally depicted CN - 1,2 LPShift scenario. The figure now follows prevailing assumptions in link prediction, detailing a scenario where a link prediction model trains on 2 Common Neighbors and then must generalize on testing samples with 0 Common Neighbors. Our empirical tests on the "Backward" CN splits align with this assumption, as indicated by the loss in performance shown between Table 7 (the 'Forward' ogbl-collab split) and Table 11 (the "Backward" ogbl-collab split) in the Appendix. We include a representative example of results both tables in Table 1, as shown below:

Table 1 (shown above): An example of the CN Results combined from Tables 7 and 11 in Appendix Section F of the revised paper. Note: the significant decrease in performance for most models between the "Backward" splits in the final three columns versus the "Forward" splits in the first three columns. Notably, RA and NCNC performance improves signficantly once more Common Neighbors are made available in the validation and testing splits, highlighted in bold (i.e. CN - 4,2 and CN - 5,3).

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.

Thank you for the suggestion. We've revised our paper in the following ways:

• We relate LPShift to the mathematical definition of covariate shift. This can be found in the updated introduction section, highlighted in blue indicating that LPShift induces a special case of structural covariate shift. We also provide a more detailed perspective on how LPShift can create meaningful dataset shifts. Detailed below:

Consider the three graphs in Figure 1 as samples pulled from a larger graph dataset. In order of appearance, each of the three graphs represent samples from the: training, validation, and testing splits of our dataset. Our task is to predict whether new links will form between existing nodes. These predicted links are shown as dotted lines with colors: “green” = training, “blue” = validation, “red” = testing. An optimal LP model trained on the first graph sample effectively learns a representation understanding source and target nodes with 2 Common Neighbors Zhang & Chen (2018), making the model effective at predicting new links in structure-rich scenarios. However, such a model is likely to fail when predicting links on the subsequent validation and testing samples; the second and third graph in Figure 1 with 1 CN and 0 CNs, respectively. The learned representation necessary to capture the differing pairwise relations in the second and third graphs requires generalizing to a scenario with fewer CNs, and therefore less structural information. As such, the previously-mentioned scenario represents a case of structural covariate shift, where the training distribution cannot effectively model the testing distribution, defined mathematically as $P^{Train}(X) \neq P^{Test}(Y)$. LPShift, our proposed splitting strategy, provides a controllable means to induce the scenario shown in Figure 1 (labelled in experiments as the CN - 2,1 split), as well as fifteen other tested scenarios. More details on structural shift are included in Section 3.2.

• We include a discussion of the importance that the structural heuristics play in link prediction and the types of structural shifts they can induce. This is in Section 3.1, highlighted in blue.

Furthermore even on complex real-world datasets, CNs achieves competitive performance against more advanced neural models Hu et al. (2020). To control for the effect of CNs on shifted performance, the relevant splits will consider thresholds which include more CNs.

a) Previous studies (e.g., [1]) emphasize the significance of global structure information, which seems not fully considered in the LPShift splitting strategy.

We would like to clarify that we consider global structure information in Section 3.1 of our original submission, including a citation by Mao et. al [1]. Following this consideration, we apply the Shortest-Path heuristic with LPShift for it's ability to capture global structure information; with further details provided in part (2) of Section 3.1, detailed below in quotes:

(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 Russell & Norvig (2009). 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 Evtushenko & Kleinberg (2021), which is comparable to the real-world scenario where two opponents choose to co-operate with one another Schelling (1978); Granovetter (1978).

[1] Haitao Mao, Juanhui Li, Harry Shomer, Bingheng Li, Wenqi Fan, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Revisiting link prediction: A data perspective. ICLR, 2024.

b) The use of temporal datasets like Collab may not suit this split strategy, as it is sensitive to time.

We agree that the distinction amongst splits types is important for learning effective graph representations. However, LPShift functions as a means to induce a tunable shift within the structure of a given link prediction dataset. Even though the original ogbl-collab dataset is split temporally based on the node years, the distribution of Common Neighbors within the graph samples inherently capture the temporal nature of this split. We visualize this natural shift in edges within Subplot 1 of Figure 5.

We can then consider how the graph structure within ogbl-collab changes over time and how that relates to LPShift. Ogbl-collab's nodes from more recent years are likely to have fewer edges than older nodes, a shifted scenario due to the fact that older nodes in ogbl-collab have progressively more time to accumulate more edges/citations. Given that LPShift functions on the adjacency matrix as a whole, regardless of dataset split, the CN - 2,1 split can be seen as means to test a similar scenario caused by the original ogbl-collab. As such, the original temporal split remains captured within datasets altered by LPShift.

As a benchmark paper, two datasets seem limited.

We originally made this decision since the ogbl datasets are relatively large compared to other datasets, such as cora and citeseer. Therefore, the evaluation of LPShift more closely follows what is expected in real-world settings with larger and difficult datasets. However, we acknowledge that additional datasets will provide more solid empirical evidence for our claims. In Table 2, shown below, we include additional empirical results for cora, citeseer, and pubmed.

We note the following observation from the results shown in Table 1:

1. The general trend that we discuss in our original paper remains: a change in the structure of the training adjacency matrix results in a change in performance. Thus, indicating the importance of structural information for LP model performance.
2. RA performs significantly worse than all tested LP models.
3. Regardless of the 'forward' and 'backward' splits, there is an increase in performance for all GNN4LP and LP models.
4. Also following along the trend of our original submission, GCN continues to perform competitively against GNN4LP models. However, there are scenarios, such as Pubmed - CN 3,5, where GNN4LP models can outrank GCN.

• The limited effectiveness of RA along with the reduced competitiveness of GCN is attributed to the relative lack of structural information contained within the LPShift versions of Cora, Citeseer, and Pubmed. Since Cora, Citeseer, and Pubmed are a fraction of the size of ogbl-collab and ogbl-ppa, there is simply less relevant links captured by CN, SP, and PA. As such, RA has fewer training links to reliably rank testing links, causing it's performance to plummet.
• In regards to GCN, since the raw number of relevant CN, SP, PA links in each split is markedly lower than the LPShift versions of ogbl-collab and ogbl-ppa; this means that the structural information captured in the training adjacency matrix is more important. Therefore, resulting in more competitive performance from the GNN4LP models versus GCN as well as the increase in perforamnce regardless of 'forward' or 'backward' split.

Table 2 (shown below): Cora, citeseer, pubmed results for all models tested with LPShift.

Dear Reviewer QSyV,

Thank you for taking the time and effort to review our work! We appreciate your input, it greatly improves the quality of our study.

We have posted our rebuttal and hope that it addresses all of your concerns, especially about the importance of studying distribution shifts in link prediction. Please consider it in your evaluation and inform us of any additional concerns.

Kind Regards,

Authors

Dear Reviewer QSyV,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

Dear Reviewer QSyV,

Thank you for taking the effort to review our paper! We appreciate your input as it improves our work.

Given that today is the last day to revise the paper, we hope we have addressed your concerns. Please let us know if you have additional questions or concerns.

Best Regards,

Authors

Thank you for your review, given the extended discussion period we are happy to address any further concerns.

Our paper considers:

• 5 datasets, with 16 LPShift splits and 7 tested models. (3 new datasets -- 560 model experiments)
• 5 traditional OOD generalization methods (new)
• 2 LP-Specific and 1 graph-data generalization method with included analysis (updated) on the effect that these methods have on dataset structure.
• In particular, the ogbl-ppa and ogbl-collab datasets are much larger than most available benchmark datasets and consist of two distinct domains; allowing insights from this paper to better translate to real-world settings.

Given that this paper is for the datasets & benchmarks track, our insight is focused on LPShift's effect for current model and generalization method performance. This way, we intend to provide a foundation from which future research can develop methods to handle distribution shift in link prediction. We hope further concerns about the insights are addressed clearly within our revised paper. Please let us know if there any specific pain points about the datasets or analysis insights.