Knowledge Graph Completion by Intermediate Variables Regularization

We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.

Q1: The first contribution, which is a detailed overview of a wide range of TDB models, is somewhat limited in its actual content.

A1: We propose a general form of tensor decomposition based (TDB) models for KGC, which serves as a foundation for further analysis and exploration of TDB models. The general form presents a unified view of TDB models and helps the researchers understand the relationship between different TDB models. Moreover, the general form motivates the researchers to propose new methods and establish unified theoretical frameworks that are applicable to most TDB models. Our proposed regularization method and the theoretical analysis in Section 3.3 are examples of such contributions.

Q2: The experimental results could benefit from a more comprehensive comparison involving additional metrics such as efficiency and time-related measures.

A2: We present more detailed experimental results in Appendix C. Since these regularizations are all composed of $L^p$ norms, which are all efficient, they do not affect the model efficiency significantly. The most important factor that affects the model efficiency is the number of parts $P$. Since models with different regularizations have the same value of $P$, we do not need to compare their efficiency.

As we discussed in Section 3.1 Paragraph “The Number of Parameters and Computational Complexity”, the computational complexity is related to the number of parts $P$. We further provide an efficiency analysis in Appendix C Paragraph “The Number of Parts”. The results show that the model performance generally improves and the running time generally increases as P increases. Thus, the larger the part $P$, the more expressive the model and the more the computation.

Q3: Could the authors further explain the difference between IVR and IVR-3 in Table 3?

A3: We defined IVR-3 and IVR as two variants of Eq.(4) with different constraints on the regularization coefficients $\lambda_{i}$ in Section 3.2. Specifically, IVR is Eq.(4) with the constraint $\lambda_{1}=\lambda_{3}, \lambda_{2}=\lambda_{4}$, while IVR-3 is Eq.(4) with the constraint $\lambda_{1}=\lambda_{2}=\lambda_{3}=\lambda_{4}$. Therefore, IVR has two degrees of freedom in choosing the regularization coefficients, while IVR-3 has only one.

Q4: Need to clarify the metrics in the experiments. What do the results mean, like accuracy, error, or anything else?

A4: We have provided more detailed experimental results in Appendix C, including the evaluation in the second paragraph of Appendix C. The evaluation metrices is commonly used in KGC. Besides, we analyze the impact of random initialization, the impact of the hyper-parameters and the number of parts in Appendix C.

Q5: Unclear meaning of the notation of (i, j, ?) above Section 3.3.

A5: We use the notation $(i, j, ?)$ to represent a query that asks for the most likely tail entities given a head entity $i$ and a relation $j$. This notation is commonly used in knowledge graph completion tasks. We will make the notation clearer in the revision.

We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.

Q1: The paper is not organized clearly, which is not friendly for understanding. For instance, there are lack of an intuitive explanation for how this method can mitigate the overfitting issue.

A1: We have explained the intuition of our regularization from two perspectives. Previous works only minimize the norms of the embeddings to prevent overfitting, while our proposed regularization IVR minimizes the norms of the intermediate variables involved in the processes of computing the predicted tensor, which can further reduce the complexity of the model to prevent overfitting.

From the perspective of theoretical analysis, we further propose a theoretical framework to explain how the model mitigate the overfitting issue. We prove that our regularization IVR can minimize the Frobenius norms of the intermediate variables to minimize the overlapped trace norm of the predicted tensor as shown in Section 3.3. The overlapped trace norm can be a measure of the complexity of the predicted tensor, and minimizing it can regularize the model and prevent overfitting. We first prove Lemma 1 in Appendix B, which relates the Frobenius norm and the trace norm of a matrix. Lemma 1 shows that the trace norm of a matrix is an upper bound of a function of several Frobenius norms of intermediate variables. Based on Lemma 1, we then prove that IVR serves as an upper bound for the overlapped trace norm of the predicted tensor, which promotes the low nuclear norm of the predicted tensor to regularize the model, which is known to reduce overfitting.

We will make this statement clearer in the revision. And we want to highlight that the other three reviewers appreciate the clarity of our paper. We welcome any suggestions to improve the organization of our paper further.

Q2: The regularization approach as shown in Eq.(4) is too complex to use.

A2: Our regularization IVR is not complex to use. First, IVR is composed of several Frobenius norms of variables, which are simple to compute. Second, we provide a pseudocode for computing IVR in Appendix C. The pseudocode shows that IVR can be computed incidentally during the process of computing the predicted tensor $X$. Third, we also provide a source code for IVR in the Supplementary Material. The model.py file shows that the implementation of IVR is concise and straightforward. In summary, IVR is not complex to use and implement.

Q3: This paper misses some strong baselines such as [1][2]. [1] Low-Dimensional Hyperbolic Knowledge Graph Embeddings. [2] ER: equivariance regularizer for knowledge graph completion.

A3: In this paper, we mainly focus on tensor decomposition-based (TDB) models, which have wide applicability and great performance in knowledge graph completion. Therefore, we mainly include the TDB models as baselines for fair comparison. We will make the baselines more complete in the revision.

We would like to emphasize the main contributions of our paper as follows:

1. We propose a general form for TDB models, which provides a unified view of existing TDB models and serves as a foundation for further analysis and exploration.
2. We introduce a novel regularization method for TDB models based on our general form to mitigate the overfitting issue. Our regularization method is notable for its generality and effectiveness, as it can be applied to most TDB models and can improve their performance significantly. Previous regularization methods either have poor performance (such as F2) or are not general enough (such as N3 and DURA), while our method overcomes both limitations. Table 1 shows the experimental results that demonstrate the effectiveness and generality of our method.
3. We provide a general theoretical framework for most TDB models in Section 3.3, which proves that our regularization method can promote low trace norm of the predicted tensor, which is known to reduce overfitting. In contrast, N3 and DURA only provide theoretical analysis for models based on CP decomposition, which limits their applicability.

Thanks again for your constructive comments. We appreciate your time and effort in reviewing our paper. As the discussion deadline is near, we sincerely look forward to your further feedback. If our responses do not address your concerns, we are prepared to provide more comprehensive responses if necessary. Alternatively, if you find that our responses have effectively addressed your concerns, can you give us feedback? Your feedback is crucial to us. We look forward to hearing from you.

Dear reviewer:

Thank you for your careful comments again. Since today marks the final day of discussion, we kindly request once again for your feedback and comments. We appreciate your time and effort in reviewing our paper. Since our response for your concerns is brief, it will not take up too much of your time. If you find that our responses have effectively addressed your concerns, can you give us feedback? Your feedback is crucial to us. We apologize for any inconvenience caused.

Thanks again for your constructive comments. We appreciate your time and effort in reviewing our paper. We would like to further emphasize two points of our paper:

1. Our paper is organized clearly as shown in the comments of other three reviewers. Reviewer TVtg comments "The paper is very well-written. The reviewer enjoys reading the paper." Reviewer Bhgm comments "Easy to read.". Reviewer YFRf comments "The article is well-structured with detailed analysis and clear logic. The language is fluent and reader-friendly."
2. Our regularization is easy to use and implement as shown in the pseudocode in Appendix C and the code in the Supplementary Material.

As the author-reviewer discussion period closes, we are unable to provide further explanation. We sincerely hope that the reviewer can read our rebuttal and raise our score at the AC-reviewer discussion period.

We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.

Q1: Could the authors explain in detail how the general form benefits the community?

A1: We propose a general form of tensor decomposition based (TDB) models for KGC, which serves as a foundation for further analysis and exploration of TDB models. The general form presents a unified view of TDB models and helps the researchers understand the relationship between different TDB models. Moreover, the general form motivates the researchers to propose new methods and establish unified theoretical frameworks that are applicable to most TDB models. Our proposed regularization and the theoretical analysis are examples of such contributions.

Q2: What if we increase the coefficients of regularization in the baseline models?

A2: We have shown the results of experiments with respect to the hyper-parameters in Appendix C. We analyze the impact of the hyper-parameters, the power of the Frobenius norm $\alpha$ and the regularization coefficient $\lambda_i$ in Appendix C (Table 6 to Table 9). The results show that the performance generally increases as $\alpha$/$\lambda_i$ increases and then decreases as $\alpha$/$\lambda_i$ increases. The results indicate the effectiveness of the hyper-parameters.

Q3: The proposed regularization lacks motivation. Why an upper bound of the regularization is better in the optimization?

A3: The motivation of our regularization IVR is that we can minimize the Frobenius norms of the intermediate variables (involved in the processes of computing the predicted tensor) to minimize the overlapped trace norm of the predicted tensor. The overlapped trace norm can be a measure of the complexity of the predicted tensor, and minimizing it can regularize the model and prevent overfitting. To establish a theoretical framework for IVR, we prove Lemma 1 in Appendix B, which relates the Frobenius norm and the trace norm of a matrix. Lemma 1 shows that the trace norm of a matrix is an upper bound of a function of several Frobenius norms of intermediate variables. Based on Lemma 1, we prove that IVR serves as an upper bound for the overlapped trace norm of the predicted tensor.

From another view, since computing the trace norm has a high computational complexity of $\mathcal O(n^3)$, which is impractical for large knowledge graphs, our regularization IVR is composed of several Frobenius norms, which are computationally efficient. We prove that minimizing IVR can effectively minimize the overlapped trace norm, and we also verify this experimentally in Section 4.4. Thus, IVR serves as a good surrogate of the overlapped trace norm.

Q4: What are the parameters in the loss function?

A4: We can substitute Eq.(1) into the loss function to see the parameters. The parameters come from two parts, the core tensor $W$ and the embedding matrices $H$, $R$ and $T$. Please refer to Section 3.1 Paragraph “The Number of Parameters and Computational Complexity” for more details.

Q5: The loss function should have a mask tensor to indicate the observed entries.

A5: We do not need a mask tensor to distinguish the observed and unobserved entries. We can treat every observed entry as a positive sample, and every unobserved entry as a negative sample. Then the loss function maximizes the score of the observed entries (i.e., $X_{ijk}$) and minimizes the score of the unobserved entries (i.e., $X_{ijk'}$, where $k'\neq k$). In other words, the loss function implicitly incorporates the mask tensor. Therefore, we do not need to explicitly use a mask tensor.

Q6: The contributions and the usefulness of the proposal should be elaborated.

A6: The main contributions of our paper are in 3 folds:

1. We propose a general form for TDB models, which provides a unified view of existing TDB models and serves as a foundation for further analysis and exploration. You can also refer to A1.
2. We introduce a novel regularization method for TDB models based on our general form to mitigate the overfitting issue. Our regularization method is notable for its generality and effectiveness, as it can be applied to most TDB models and can improve their performance significantly. Previous regularization methods either have poor performance (such as F2) or are not general enough (such as N3 and DURA), while our method overcomes both limitations. Table 1 shows the experimental results that demonstrate the effectiveness and generality of our method.
3. We provide a general theoretical framework for most TDB models in Section 3.3, which proves that our regularization method can promote low trace norm of the predicted tensor, which is known to reduce overfitting. In contrast, N3 and DURA only provide theoretical analysis for models based on CP decomposition, which limits their applicability. You can also refer to A3.

Thanks again for your constructive comments. We appreciate your time and effort in reviewing our paper. As the discussion deadline is near, we sincerely look forward to your further feedback. If our responses do not address your concerns, we are prepared to provide more comprehensive responses if necessary. Alternatively, if you find that our responses have effectively addressed your concerns, can you give us feedback? Your feedback is crucial to us. We look forward to hearing from you.

Dear reviewer:

Thank you for your careful comments again. Since today marks the final day of discussion, we kindly request once again for your feedback and comments. As shown in your comment "I am willing to raise the score for further explanations.", we sincerely look forward to your further feedback. If you find that our responses have effectively addressed your concerns, can you give us feedback? Your feedback is crucial to us. We apologize for any inconvenience caused.

Thanks again for your constructive comments. We thank you for your appreciation for our paper, as shown in your comments "The reviewer likes the paper" and "I am willing to raise the score for further explanations.". As the author-reviewer discussion period closes, we are unable to provide further explanation. We sincerely hope that the reviewer can read our rebuttal and raise our score at the AC-reviewer discussion period.

We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.

Q1: The main focus should be the regularization term they proposed instead of the general form.

A1: We agree that the main contribution of our paper is the regularization term, but we also argue that the general form is necessary, as it serves as a foundation for our further analysis. Without the general form, we cannot guarantee the generality of our regularization term and the theoretical analysis, as they depend on the unified view of the TDB models provided by the general form.

Q2: Their weight IVR norm is not theoretically novel and significant. Could the author clarify what is the unique hardness and novelty of this proposed IVR norm?

A2: Our proposed regularization is notable for its generality and effectiveness, as it can be applied to most TDB models and can improve their performance significantly. Although some of the theoretical analysis was established for F2, N3 and DURA, it is still challenging to design a regularization method that has both the properties of generality and effectiveness. As previous regularization methods either have poor performance (such as the F2 norm method, which achieves suboptimal results) or are not general enough (such as the N3 norm method and the DURA method, which are only suitable for CP and ComplEx models), while our method overcomes both limitations. Table 1 shows the experimental results that demonstrate the effectiveness and generality of our method. Our method can be applied to various TDB models, such as CP, ComplEx, SimplE, ANALOGY, QuatE, TuckER, etc., and achieve SOTA results. For example, TuckER with our method achieves new SOTA results on the WN18RR dataset.

Meanwhile, we provide a general theoretical framework for most TDB models in Section 3.3, which proves that our regularization method can promote low trace norm of the predicted tensor, which is known to reduce overfitting. Previous works only provide theoretical analysis for CP and ComplEx models, which limits their applicability. We discover the relationship between the overlapped trace norm and our proposed IVR regularization, and show that IVR serves as an upper bound for the overlapped trace norm. We also verify the validity of our theoretical analysis experimentally in Section 4.4. You can also refer to A3 of the rebuttal for Reviewer TVtg.

Q3: For the experiment side, as the author claimed in the paper, their method promotes low rank. Do you see the zero columns in the factors, compared to the existing methods?

A3: We argue that a low rank matrix does not necessarily imply sparse embeddings, as a low rank matrix can have non-zero columns. For example, consider a matrix $X$ whose entries are all 1. The rank of $X$ is 1, but $X$ has no zero columns. Therefore, a better metric to measure the rank of a matrix is the overlapped trace norm, which is a convex surrogate of the rank. We experimentally verify that minimizing our proposed regularization can effectively minimize the overlapped trace norm $L(X)$ in Section 4.4. To make the experiments more detailed, we further show the results of different regularizations in the following Table 1, which demonstrate that our method is better at promoting low rank than other methods.

Table 1: The results on Kinship dataset with different regularizations. Larger MRR and lower L(X) are better.

We further analyze the sparsity of embeddings induced by different regularizations as below. Generally, there are few entries of embeddings that are exactly equal to 0 after training, which means that it is hard to obtain sparse embeddings directly. To get sparse embeddings, we can set a proper threshold and set the absolute value of the embedding entries less than the threshold to be exactly 0. Denote the ratio of zero entries as $\alpha$, then we can compare the performance of different models under the same $\alpha$. The following Table 2 shows that our regularization CP-IVR can achieve better performance than other regularizations under the same sparsity circumstance.

Table 2: The MRR results of models with different sparsity. Larger MRR is better.

Thanks again for your constructive comments. We appreciate your time and effort in reviewing our paper. As the discussion deadline is near, we sincerely look forward to your further feedback. If our responses do not address your concerns, we are prepared to provide more comprehensive responses if necessary. Alternatively, if you find that our responses have effectively addressed your concerns, can you give us feedback? Your feedback is crucial to us. We look forward to hearing from you.

Thanks again for your constructive comments.

Q1: For the Q3, I believe for the CPD, since it's constraining rank-one tensors, you should see zero columns in the factors if you actually promote low-rank.

A1: Due to the optimization method we use, it is unlikely that we will obtain factors with $**exactly**$ zero columns. Our optimization method is based on the stochastic gradient descent (SGD) method, which works as follows:

1. We randomly initialize the factors.
2. We update the values of the factors based on the corresponding gradients.
3. We stop the optimization process according to the evaluation results on the validation set. We do not aim to minimize the loss to $**exactly**$ zero, as this would imply overfitting.

Therefore, after optimization, the factors may not have $**exactly**$ zero columns. However, we can show that our regularization method effectively promotes low trace norm from three aspects.

1. As we stated in the A3 of our previous response, the overlapped trace norm is a better metric to measure the rank, as it is a convex surrogate of the rank. Table 1 shows that our method CP-IVR achieves the lowest value of the overlapped trace norm. This indicates that our regularization method is more effective at promoting low trace norm than other methods.
2. As we stated in the A3 of our previous response, to obtain sparse factors, we can set a proper threshold and set the absolute value of the entries of factors below the threshold to zero. Then, we can compare the performance of different models under the same sparsity level. Table 2 shows that our regularization CP-IVR can achieve better performance than other regularizations under the same sparsity level.
3. To see the zero columns, we can set a proper threshold and set the columns of factors to zero if the norm of the columns is below the threshold. We can then calculate the ratio of zero columns for different thresholds. The following table shows that our regularization method CP-IVR has the highest ratio of zero columns.

In summary, our regularization method effectively promotes low trace norm.

Table: The ratio of zero columns for different thresholds.

We modify this comment as follows:

We do $**not**$ claim that our regularization promotes the low rank in our paper. We claim that our regularization term promotes the low trace norm. There is a slightly difference between these two claims. The trace norm is different to the rank, which is widely used as a convex surrogate for the rank.