Risk Aware Negative Sampling in Link Prediction

We thank you for your detailed review of our work. Your suggestions have helped us identify areas where we can improve both the clarity and depth of our work, and we are committed to addressing these points in our revision.

W1: We thank the reviewer for pointing this out. We believe that there may have been a misunderstanding about how RANS works algorithmically, and have updated the paper to make this point more clear. In particular, during each RANS resampling procedure, we draw a fixed number of negatives. If we ultimately desire $N$ negatives, we draw $kN$ negatives where $k>1$. These negatives can be drawn from any distribution, and in our case that distribution is the uniform distribution. In practice, $kN << N^2$. RANS does require $kN$ model calls, but graph models tend to be quite small. The linear number of model calls is similarly shared by MCNS, one our of baselines, that has enjoyed industrial usage.

In addition to updating the prose of the paper to clarify this point, we have added a table comparing runtimes in the appendix. We observe that RANS is competitive from the perspective of computational cost with the other baselines presented, while providing superior performance.

W2: We agree that while the presented results are promising, the datasets are small. We have added results for both ogbl-ddi and ogbl-collab, and have included them in Table 1. In both we observe significant performance improvements.

W3: We believe that the paper is link prediction focused in at least two ways. The first is that, in the theoretical analysis, we consider the case where our number of negatives drastically outweights our positives (eg $N^2$ vs $N$), as is common in link prediction. Furthermore, our theoretical analysis that follows in Section 5 turns on some of the implicit assumptions of link prediction. Namely, there exist "easy" and "hard" samples, with "easy" samples far outweighing the hard ones. Beyond this, we note that the intuition the construction of RANS is based in link prediction as well. $\eta$ controls how many negatives need to be easy before we re-sample. An $\eta$ near one corresponded to a situation where most of the information had been "extracted" from the negatives. The intuition for $\delta$ is more link prediction inspired. Essentially, once the positive and negative edges have been separated, there is limited predictive benefit to "run up the score" by becoming even more confident about edges you already accurately categorize.

It is true that some industrially relevant tasks such as recommendation systems have similar properties, but these comprise a graph as well, albeit implicitly, constructed from users, items, and their interactions [1,2].

We feel as if we have addressed your questions and the weaknesses that you have pointed out. If we have not addressed them to your satisfaction, please do let us know. Otherwise, we would kindly request that you consider raising your score.

[1] Aditya Pal et al. PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest

[2] Ahmed El-Kishky et al. TwHIN: Embedding the Twitter Heterogeneous Information Network for Personalized Recommendation

We thank you for your detailed review of our work. Your suggestions have helped us identify areas where we can improve both the clarity and depth of our work, and we are committed to addressing these points in our revision.

W1: We believe that the paper is link prediction focused in at least two ways. The first is that, in the theoretical analysis, we consider the case where our number of negatives drastically outweights our positives (eg $N^2$ vs $N$), as is common in link prediction. Furthermore, our theoretical analysis that follows in Section 5 turns on some of the implicit assumptions of link prediction. Namely, there exist "easy" and "hard" samples, with "easy'' samples far outweighing the hard ones. Beyond this, we note that the intuition the construction of RANS is based in link prediction as well. $\eta$ controls how many negatives need to be easy before we re-sample. An $\eta$ near one corresponded to a situation where most of the information had been "extracted" from the negatives. The intuition for $\delta$ is more link prediction inspired. Essentially, once the positive and negative edges have been separated, there is limited predictive benefit to "run up the score" by becoming even more confident about edges you already accurately categorize.

W2: We thank the reviewer for pointing out these mistakes, and have fixed them in addition to performing a thorough proof reading of the paper. We apologize for these oversights.

W3: There are no limitations in applying RANS to other methods. We opted to experiment with GCN due to its simplicity, the industrial relevance, and the desire to not overly complicate Table 1 by considering the Cartesian product of multiple GNN backbones and multiple sampling strategies. Additionally, we believe that our theoretical analysis is more general than just applying to GCNs. While Section 4 makes heuristic arguments with a GCN, this is to make our intuitive arguments for the importance of negative samples clear. Section 5 assumes, simply, that one has a class of learnable predictors. With that being said, we are running experiments HL-GNN+RANS [2] and will update the revision with those results if time permits.

W4: Thank you for pointing this out. While both, $\eta$ and $\delta$ are fixed at runtime and we have performed no formal hyperparameter tuning over them. However, we believe that better understanding their influence on our algorithm is quite important. To this end, we have performed a scan of $\eta$ and $\delta$ and plotted the resulting surface in the appendix. We observe a broad region of good performance, indicating that our method does not require extensive hyperparameter tuning for use.

W5: We agree that while the presented results are promising, the datasets are small. We have added results for both ogbl-ddi and ogbl-collab, and have included them in Table 1. For both datasets we observe meaningful lifts.

We feel as if we have addressed your questions and the weaknesses that you have pointed out. If we have not addressed them to your satisfaction, please do let us know. Otherwise, we would kindly request that you consider raising your score.

We thank you for your detailed review of our work. Your suggestions have helped us identify areas where we can improve both the clarity and depth of our work, and we are committed to addressing these points in our revision.

W1/Q1: Many existing hard negative sampling methods are GAN based, which can be difficult to stabilize during training. The only hard negative sampling strategy that we know of that enjoys industrial adoption is MCNS, which we have included as a baseline. Compared to MCNS, we observe performance improvements across the board without significant model complexity, and those results are found in Table 1. Additionally, MCNS has been shown to outperform GAN based hard negative mining systems [1], and therefore we believe that it is a fair baseline to compare against for hard negative sampling.

W2/Q2: The text from 213-239 was intended to be an illustrative example to provide some intuition as to why negative sampling might matter. With this in mind, we have added citations where appropriate. For example, we have cited the structurally isomorphic node problem. For the claim that negative sampling does not change the expressivity of the hypothesis space, we have added citations to indicate that the expressivity of the hypothesis space is data independent. In this context, expressivity specifically refers to what a model structure can represent. Our negative sampling procedure does not change that -- it simply helps improve the final model that is learned.

W3/Q3: We thank the reviewer for pointing this out. We believe that there may have been a misunderstanding about how RANS works algorithmically, and have updated the paper to make this point more clear. In particular, during each RANS resampling procedure, we draw a fixed number of negatives. If we ultimately desire $N$ negatives, we draw $kN$ negatives where $k>1$. These negatives can be drawn from any distribution, and in our case that distribution is the uniform distribution. In practice, $kN << N^2$. RANS does require $kN$ model calls, but graph models tend to be quite small. The linear number of model calls is similarly shared by MCNS, one our of baselines, that has enjoyed industrial usage. We have updated the algorithmic discussion to make this point more clear. We have additionally included Table 5 in the appendix, which captures the total training time for all methods across all presented datasets. We observe that RANS is competitive with other dynamic sampling techniques in terms of runtime cost.

W4/Q4: We have added results for both ogbl-ddi and ogbl-collab, and have included them in Table 1. For both datasets we observe meaningful lifts.

W5/Q5: There are no limitations in applying RANS to other methods. We opted to experiment with GCN due to its simplicity, the industrial relevance, and the desire to not overly complicate Table 1 by considering the Cartesian product of multiple GNN backbones and multiple sampling strategies. With that being said, we are running experiments HL-GNN+RANS [2] and will update the revision with those results if time permits.

We feel as if we have addressed your questions and the weaknesses that you have pointed out. If we have not addressed them to your satisfaction, please do let us know. Otherwise, we would kindly request that you consider raising your score.

[1] Zhen Yang et al, Understanding Negative Sampling in Graph Representation Learning

[2] Juzheng Zhang et al, Heuristic Learning with Graph Neural Networks: A Unified Framework for Link Prediction

1. Thank you for bringing this to our attention. We will include it in our literature review, and will describe any differences/advantages tomorrow.

2. $D^{n'}{hardest}$ denotes the set of negatives in $D^{n'}$ that are most challenging for the current model, specifically those negative samples that receive the highest model scores (indicating where the model is most incorrect). Conversely, $D^{n}{easiest}$ represents the negative samples that the model classifies most accurately. The model's score is denoted by $p$.

Regarding RANS's relationship to risk: Our method was developed to minimize $\tilde{R}$, which theoretically requires evaluation on the complete dataset $D$. However, this is computationally infeasible for all but the smallest graphs. Therefore, we must sample $D$ to obtain $\hat{D}$ and consequently $\hat{R}$. This sampling introduces a fundamental challenge: minimizing $\hat{R}$ does not guarantee minimization of $\tilde{R}$. Consider a scenario where $\hat{D}^n$, where the superscript indicates the negative subset of the dataset, consists solely of trivial negatives—the risk gap could be substantial. The optimal scenario would be the opposite: if we constructed $\hat{D}^{opt, n}$ exclusively from the hardest negatives for the Bayes classifier $f^*$, then finding $\hat{f}$ that minimizes $\hat{R}$ would yield the best possible estimate for $f^*$ (Theorem 5.2). While this assumes access to $f^*$, which is generally unavailable in practice, we address this limitation by using $f^{(n)}$ (where $n$ is the SGD index) as our current best estimate of $f^*$. This allows us to systematically replace "easy" negatives with "hard" ones, approximating $\hat{D}^{opt, n}$. By minimizing $\hat{R}^{opt}$ over $\hat{D}^{opt, n}$, we provide the most robust estimate possible for $f^*$.

3. Thank you for pointing out this concern. We would direct your attention to Table 6 in the appendix of the revised paper which reports the results for HLGNN. HLGNN was published at KDD this year and performed extremely well. We believe that HLGNN is a much more complicated backbone than a GCN, and hope that it addresses this point.

4. The performance differences can be attributed to several key factors. First, our experimental protocol differs in that we excluded validation edges from the testing phase, whereas HLGNN incorporated them. HLGNN's architecture learns fine-grained structural heuristics and exhibits sensitivity to edge count variations. Additionally, HLGNN features numerous hyperparameters beyond the core model architecture, including loss functions[1], learning rate schedules, and optimizer configurations. Given the time constraints of the rebuttal period, we maintained the default model hyperparameters from the provided codebase, implementing it within our experimental framework derived from the OGBL codebase, using standard BCE loss, Adam optimizer, and a fixed learning rate schedule.

[1] AUC, HingeAUC, WeightedAUC, AdaptiveAUC, AdaptiveHingeAUC, logloss, CrossEntropyLoss, InfoNCE

W5/Q5: We have added Table 6 in the appendix that reports our experiments with HLGNN+RANS, and on 5/6 datasets we find that RANS provides lifts above other baselines. We hope that this addresses your concerns about the lack of evidence to support RANS as a general training augmentation. With the inclusion of Table 6 in addition to the other additions to the work, we feel as if we have addressed your questions and the weaknesses that you have pointed out.

We feel as if we have addressed your questions and the weaknesses that you have pointed out. If we have not addressed them to your satisfaction, please do let us know. Otherwise, we would kindly request that you consider raising your score.

We thank reviewer AAXD for their thorough and thoughtful review of our work. We feel that by addressing their points, our work has become stronger and clearer. Specifically:

W1: We agree that while the presented results are promising, the datasets are small. We have added results for both ogbl-ddi and ogbl-collab, and have included them in Table 1. For both ogbl-ddi and ogbl-collab, we observe statistically significant lifts.

W2: The results in Table 3 for GCN+UNS, SEAL, BUDDY, ELPH, and Neo-GNN are replicated [1], and as such they correspond to the optimal hyperparameters for the optimal models. For GCN+RANS, we have performed no such hyperparameter tuning. We have added citations and prose to make this more clear.

W3: There are no limitations in applying RANS to other methods. We opted to experiment with GCN due to its simplicity, the industrial relevance, and the desire to not overly complicate Table 1 by considering the Cartesian product of multiple GNN backbones and multiple sampling strategies. With that being said, we are running experiments HL-GNN+RANS [2] and will update the revision with those results if time permits.

Q1: Thank you for pointing this out. Yes, $\eta$ and $\delta$ are fixed at runtime and we have performed no formal hyperparameter tuning over them. However, we believe that better understanding their influence on our algorithm is quite important. To this end, we have performed a scan of $\eta$ and $\delta$ and plotted the resulting surface in the appendix. We observe that there is a wide region of stability for our method, which means only limited tuning is required.

Q2: We selected $\eta$ to be 0.95 because we thought that this corresponded to a situation where most of the information had been "extracted" from the negatives. The intuition for $\delta$ is more link prediction inspired. Essentially, once the positive and negative edges have been separated, there is limited predictive benefit to "run up the score" by becoming even more confident about edges you already accurately categorize.

Q3: We thank the reviewer for pointing out this article, as we had missed it and have added it to our literature review. We have updated our literature review to include this work.

We feel as if we have addressed your questions and the weaknesses that you have pointed out. If we have not addressed them to your satisfaction, please do let us know. Otherwise, we would kindly request that you consider raising your score.

[1] BP Chamberlin et al, GRAPH NEURAL NETWORKS FOR LINK PREDICTION WITH SUBGRAPH SKETCHING

[2] Juzheng Zhang et al, Heuristic Learning with Graph Neural Networks: A Unified Framework for Link Prediction

First, we would like to thank the reviewer for being unusually active during the discussion period. We feel that the reviewers suggestions have resulted in a stronger paper.

W3: We have added Table 6 in the appendix that reports our experiments with HLGNN+RANS, and on 5/6 datasets we find that RANS provides lifts above other baselines. We hope that this addresses your concerns about the lack of evidence to support RANS as a general training augmentation. With the inclusion of Table 6 in addition to the other additions to the work, we feel as if we have addressed your questions and the weaknesses that you have pointed out. If we have not addressed them to your satisfaction, please do let us know.