Unified Interpretation of Smoothing Methods for Negative Sampling Loss Functions in Knowledge Graph Embedding

Response to Reviewer @8iQT

Dear 8iQT, we highly appreiciate your valuable comments on our work. Based on feedbacks from you, we have carefully made revisions to our paper, and we are more than committed to following your suggestions and enhance our work more.

Weaknesses:

The motivation of this study is a little bit confusing. And the contribution is not clearly articulated.

• Our motivation is to solve the problem in KGC caused by the sparsenes of KGs with our propsed theoretically appropriate smoothing method, T-SANS.
• As stated in Section $\S1$, for doing that, we mainly contributed in:
  • By focusing on the smoothing targets, we theoretically reveal the difference between SANS and subsampling and induce a new NS loss, Triplet-based SANS (T-SANS), that can cover the smoothing target of both SANS and subsampling.
  • We theoretically and empirically verify how our proposed method can potentially cover the conventional methods and improve KGC performance on sparse KGs.
• To suport the explanation of the above motivation, we added the explanation to $\S3.1$ in the updated version of our paper. Besides, the difference of T-SANS and conventional subsampling methods are discussed in $\S3.3$

Questions:

Is the focus of this study to improve interpretation or model performance of KGE?

• The main focus is to provide a systematic interpretation, by doing this, we propose the T-SANS and the unified loss function from the viewpoint of smoothing methods that formulate our findings and even help improve the performance of KGC.

We appreciate your insightful review and feedback comments. Now, the deadline for the discussion period only left 18.5hours. To clarify what part of your concerns remains, would it be possible for you to state them?

Dear 8iQT,

To further refine our manuscript and address the insightful feedback from all reviewers, we have made several meaningful enhancements that we hope will not only meet but exceed your expectations:

1. We've expanded Appendix B.2 to include a comprehensive analysis of the training loss and validation MRR curves for each method to provide a clearer, more nuanced understanding of our methods.
2. In an effort to robustly validate our approach, we've conducted additional experiments using the recent Knowledge Graph Embedding model, HousE (Li et al., 2022). These experiments yielded consistent conclusions with that in our current paper, where our T-SANS method achieving significant improvements in MRR on the FB15k-237 dataset: 24.4% over SANS and 28.6% over NS. This not only reinforces the findings in our paper but also broadens the scope of our method's applicability. We're in the process of finalizing these results, post the completion of experiments with various random seeds, and plan to incorporate them into the updated version of our paper. We anticipate that this comprehensive suite of experiments will take about one more week.
3. To enhance the reader's experience and understanding, we've carefully revised $\S3$, which outlines our proposed method. These revisions include not only textual improvements for better flow and comprehension but also examples to aid in grasping the concepts for researchers in other fields.

Our goal with these revisions is to not only address the valuable feedback from reviewers but also to contribute a paper that is engaging, informative, and a pleasure to read. We believe these updates will substantially elevate the quality of our work and hopefully resonate positively with you.

(Continuing the Response to Reviewer @4kKk)

Some parts of the paper is not clearly explained or inaccurate and need further improvement, such as: (1) the $-\alpha$ in Equation (4) is unexplained; (2) statement in page 5 that "using Eq. (11) causes an imbalanced loss between the first and second terms since the sum of $p_\theta(x,y_i)$ on $\nu$ number of negative samples is not always 1" is not accurate, since in the implementation of the model, there usually is a softmax function among over all the negative samples for a positive triple, which will make the sum of $p_\theta(x,y_i)$ to $\nu$ number of negative samples to 1. (3) the caption of Figure 4 is the same as Figure 3.

• As explained in the first version of our paper, $\alpha$ is a temperature term to adjust the frequecy of triplets and queries. Note that we incorporate $\alpha$ into Eq. (3) to consider various loss functions even though Kamigaito & Hayashi (2022a;b) do not consider $\alpha$. Eq. (4-7) shows several assumptions for deciding Eq. (3), thus the annotation of $\alpha$ holds the same meaning as explained by us when introducing Eq. (3).
• In Eq. (11), we mean directly calculating $p_\theta(x,y_i)$, because the score function in KGE model aims to approximate the plausibility of an example, so the most direct way to calculate plausibility in KGE models is using $p_\theta(x,y_i) = s_{\theta}(x,y_i)$, where softmax function is not applied. Instead, as we stated below Eq. (11), we choose to calculate this probability using the decomposition $p_{\mathbf{\theta}}(x,y)=p_{\mathbf{\theta}}(y|x)p_{\mathbf{\theta}}(x)$ so that the sum of $p_{\mathbf{\theta}}(y|x)$ of all negative samples is always 1 but the sum of $p_{\mathbf{\theta}}(x,y)$ is not always 1 by $p_{\mathbf{\theta}}(x)$.
• Following your reminding, we have modified the captions for Figure 3 and 4.
• Considering your first review is not by the accurate understanding in our paper, would it be possible to increase the score based on the updated information? Also, we hope to have the opportunity to hear more of your feedback.

Response to Reviewer @4kKk

Dear 4kKk, I appreciate you spending time reading our work and I am dedicated to enhancing my paper for readers. Would you allow me to draw your attention and ask for your additional consideration of this paper? Because your valuable insights are greatly cherished, and I believe revisiting certain aspects of our hard work could bring further clarity and great value to you too. Additionally, based on feedback from all reviewers, the paper has been enhanced by further meticulous revisions. I assure you that our current paper has the potential to earn your approval.

Weaknesses:

My main concern of the paper is limited novelty contribution. T-SANS adds the subsampling based on SANS, referring to $p_\theta(x;y)$ in Equation (12), which is the key difference between T-SANS and SANS. While as mentioned by the author in the footnote, Sun et al. (2019); Zhang et al. (2020b) use subsampling in their released implementation without referring to it in their paper. Thus, if I understood correctly, I would like to say the actual implementation of methods of Sun et al. (2019); Zhang et al. (2020b) is very similar to T-SANS. Thus the novelty of this paper is limited.

• T-SANS does not applied the subsampling implemented by previous work and is completely different from SANS. Please allow me to explain the differences as below:
  • As discussed in $\S2.2$ and $\S2.3.1$, respectively, Eq. (2) denotes NS loss: $\ell_{\text{NS}}(\mathbf{\theta}) = -\frac{1}{|D|}\sum_{(x,y) \in D} \Bigl[\log(\sigma(s_{\mathbf{\theta}}(x,y)+\tau)) + \frac{1}{\nu}\sum_{y_{i}\sim U}^{\nu}\log(\sigma(-s_{\theta}(x,y_i)-\tau))\Bigr],$ Eq. (3) denotes conventional subsampling methods: &\ell_{\text{SUB}}(\mathbf{\theta}) \\ =&-\frac{1}{|D|}\!\!\sum_{(x,y) \in D} \!\!\Bigl[A(x,y;\alpha)\log(\sigma(s_{\theta}(x,y)\!+\!\tau)) \!+\!\frac{1}{\nu}\!\sum_{y_{i}\sim U}^{\nu}B(x,y;\alpha)\log(\sigma(-s_{\theta}(x,y_i)\!-\!\tau))\Bigr], where Eq. (4) Eq. (6) Eq. (7) denotes different conventional subsampling strategies based on count in Eq. (5). From above, we can understand conventional subsampling methods mean applying term $A$ and $B$ on NS loss using counted triplets and queries frequencies. While T-SANS does not apply these couting strategies.
  • As discussed in $\S2.3.2$ and $\S3.2$, respectively, Eq. (8) denotes SANS loss: &\ell_{\text{SANS}}(\mathbf{\theta}) =-\frac{1}{|D|}\sum_{(x,y) \in D} \Bigl[\log(\sigma(s_{\theta}(x,y)+\tau)) +\!\! \sum_{y_{i}\sim U}^{\nu}p_{\theta}(y_i|x;\beta)\log(\sigma(-s_{\theta}(x,y_i)-\tau))\Bigr], Eq. (12) denotes T-SANS loss, and Eq. (13) denotes the detailed calculation for $p_{\mathbf{\theta}}(x;\gamma)$ which is innovated by us:

$

&\ell_{\text{T-SANS}}(\mathbf{\theta}) \nonumber\ =& -\frac{1}{|D|}\sum_{(x,y) \in D} !!!p_{\theta}(x;\gamma)\Bigl[\log(\sigma(s_{\theta}(x,y)+\tau)) +!! \sum_{y_{i}\sim U}^{\nu}p_{\theta}(y_i|x;\beta)\log(\sigma(-s_{\theta}(x,y_i)-\tau))\Bigr],\ &p_{\mathbf{\theta}}(x;\gamma) = \sum_{y_{i}\in D} p_{\mathbf{\theta}}(x,y_{i};\gamma),:::::p_{\mathbf{\theta}}(x,y_i;\gamma) = \frac{\exp{(\gamma s_{\theta}(x,y_i))}}{\sum_{(x',y')\in D}\exp{(\gamma s_{\theta}(x',y'))}},

$From above, we can understand that T-SANS and SANS are completely different, with SANS only taking into account the conditional probability of negative samples and T-SANS being a loss function that considers the joint probability of the pair of queries and their answers. - Thus, our proposal is novel, with the key innovation in weighting through$p_{\mathbf{\theta}}(x;\gamma)$.

• We also conducted additional experiments and illustrated the performance of T-SANS compared with conventional subsampling methods and SANS in Figure 3(a) to show their difference in essence.
• Since the first version of our paper did not emphasize the difference between T-SANS and SANS, we added the explanation to $\S3.1$. Besides, the difference of T-SANS and conventional subsampling methods is discussed in $\S3.3$.

The work is motivated by that conventional works use SANS and subsampling with no theoretical background, and authors believed there is room for further performance improvement. It is unclear the why the lack of the theoretical background lead to potential performance improvement.

• Since the previous smoothing methods are not comprehensive, the lack of theoretical background will lead to mistakes in applying a proper conventional smoothing strategy. If the smoothing strategy is not proper, the performance is not optimized. Besides, the SANS does not consider the query probability thus is weak to sparse KGs. On the contary, our proposed method are built upon a comprehensive theoretical foundation that combines both subsampling and enhanced SANS, thus can help improve the KGC performance. The experimental results showing the improvement can be seen in Figure 3,4.

We appreciate your insightful review and feedback comments. Now, the deadline for the discussion period only left 18.5hours. To clarify what part of your concerns remains, would it be possible for you to state them?

Response to Reviewer @s2ka

Dear s2ka, we would like to express our sincere appreciation for your invaluable feedback on our paper. We have made improvements to our paper based on your valuable input. Would it be possible to increase the score based on our additional work?

Weaknesses:

W1 While T-SANS aims to improve upon existing methods, the computational overhead, especially in terms of memory usage and processing time, might not be thoroughly addressed.

• Following your suggestion, we are trying to demonstrate the actual memory usage and processing time now.

W2 While the paper provides a comprehensive theoretical understanding of smoothing methods for NS loss in KGE, it might be too dense for a broader audience. The depth of the theoretical content might make it less accessible to practitioners or researchers from adjacent fields.

• Please allow me to cite an example to show the difference between our T-SANS and conventional smoothing mothods: Our T-SANS can work even when the entity or relations included in the target triplet appear more than once, which is theoretically different from conventional approaches.
• Following your suggestions, we acknowledged the importance of accessibility and added this example in $\S3.3$ to make it easier for a wider audience to comprehend and apply our methods.

Questions:

W3 How does T-SANS handle extremely sparse datasets compared to other methods? Is there a threshold of sparsity beyond which T-SANS might not be as effective?

• T-SANS can effectively leverage model-predicted probabilities, enabling it to handle both normally distributed and extremely sparse datasets. In contrast, baseline methods struggle to adequately consider the frequency of sparse triples, resulting in sub-optimal performance on such challenging datasets.
• To thoroughly evaluate T-SANS, we conducted experiments on three extremely sparse datasets derived from FB15k-237, WN18RR, and YAGO3-10. As outlined in $\S6$ and illustrated in Figure 4, T-SANS consistently demonstrates improved Knowledge Graph Completion (KGC) performance in scenarios where KGs are extremely sparse. Further, by comparing with the results showcased in Figure 3, we can understand the trend that the greater the dataset sparsity, the more T-SANS outperforms conventional methods.
• Following your viewpoint, we have added a concise comparision when analyzing in $\S6$ and moved the picture positions for better accessibility.

W4 How generalizable is T-SANS to other related tasks beyond KGC? Has it been tested on tasks other than KG embedding?

• Regarding generalizability, since word embeddings and item recommendations are similar to the special case of KGs whose triplets have the same relationships, our work may inspire researchers in these fields. Test in a new task would need much more work, so we planned to put it into future work.
• Following your viewpoint, we added this note in $\S8$ to provide more value of our work and to inspire other researchers.

Dear s2ka, for your first suggestion, we have conducted detailed analysis in the appendix of our paper.

W1 While T-SANS aims to improve upon existing methods, the computational overhead, especially in terms of memory usage and processing time, might not be thoroughly addressed.

• Following your point of view, we have updated our paper by doing supplementary work: we analysed memory usage in $\S3.2$, and illustrated convergence curves for actual training loss and validation MRR in Appendix $\S B.2$ for each setting. By doing this, we can understand that the T-SANS has the same memory and time cost as SANS and NS.

We appreciate your insightful review and feedback comments. Now, the deadline for the discussion period only left 18.5hours. To clarify what part of your concerns remains, would it be possible for you to state them?

Response to Reviewer @fiTR

Dear fiTR, we greatly appreciate your reviewing our paper, and we are committed to improve following your insightful suggestions.

Weaknesses:

1. In my view, the proposed method is incremental work based on previous studies. It is an extension of SANS.

• Although the name T-SANS gives the impression that it is just an extension of SANS, this name was given out of respect for SANS. In fact, they are completely different, with SANS only taking into account the conditional probability of negative samples and T-SANS being a loss function that considers the joint probability of the pair of queries and their answers. This difference is large from the viewpoint of loss functions [1].
  • [1]: Zhuang Ma, Michael Collins. "Noise Contrastive Estimation and Negative Sampling for Conditional Models: Consistency and Statistical Efficiency", https://aclanthology.org/D18-1405/
• We conducted experiments and illustrated the performance differences of T-SANS compared with SANS in Figure 3, which verified their difference in the actual data.
• However, Reviewer @4kKk also misunderstood this point, so we added a concise explanation emphasizing the difference in $\S3.1$.

2. Another weakness is that the selected KGE models in the experiments are old. Some popular or recent models, such as TuckER [1] and HousE [2], are not included, which, in my view, may weaken the soundness the work.

• Following your suggestion, we are trying to implement TuckER and HouseE now. Would it be possible to increase the score based on the results of the additional experiments?

Questions:

1. Why are some results on YGAO3-10 missing? I think it would be better to produce the results using open-source implementations.

• Since YAGO3-10 is larger than FB15k-237 and WN18RR, it requires a lot of computational resources. To deal with this problem, we made the decision not to train the YAGO3-10 dataset on all models but only on two best-performing models whose efficient hyperparameters on YAGO3-10 are provided by previous work.

2. Is it possible to provide any analysis or experimental results to assess the effect of negative sampling on the convergence rate?

• Following your valuable suggestion, we believe that this analysis will further provide valuable insights and enhancing the credibility of our work, thus we are wholeheartedly committed to conducting this analysis. Would it be possible to increase the score based on the results of the additional analysis?

Dear fiTR, for your second qustion, we have conducted additional analysis.

Is it possible to provide any analysis or experimental results to assess the effect of negative sampling on the convergence rate?

• By following your valuable suggestion, as is refered to in $\S5.2$ of the updated revision of our paper, we conducted convergence analysis in Appendix $\S B.2$ using Figures 5,6, and 7 of training loss curves and validation MRR curves for each smoothing method for each experimental setting.
• From Figure 5,6,and 7, we can understand that the convergence of our T-SANS loss is as well as SANS and NS loss on datasets FB15k-237, WN18RR, and YAGO3-10 for each KGE model.
• We believe that this analysis will further underscore our dedication to providing valuable insights and enhancing the credibility of our work. Thank you again!

Dear fiTR, for your second suggestion, we have verified our method by conducting addtional expeirments for HousE.

Another weakness is that the selected KGE models in the experiments are old. Some popular or recent models, such as TuckER [1] and HousE [2], are not included, which, in my view, may weaken the soundness the work.

• We would like to share with you that we have verified our method for the most recent KGE model HousE (Li et al., 2022), and that the experimental results show that our T-SANS gains 24.4% and 28.6% improvement in MRR on dataset FB15k-237 compared with SANS and NS, respectively. Thus, the conclusion is consistent with that in our paper.
• We are also conducting implementation for TuckER (Balazevic et al., 2019).
• However, because of the computing resource limitation, we will need one more week to finish all the experiments. If our paper is accepted, I am sure that we will show all the experimental results expected. Would it be possible to increase the score based on the results of the additional experiments?

We appreciate your insightful review and feedback comments. Now, the deadline for the discussion period only left 18.5hours. To clarify what part of your concerns remains, would it be possible for you to state them?