Improving Soft Unification with Knowledge Graph Embedding Methods

We thank the reviewer for the insightful comments. We are glad you find our work clear and extensive. We hope the following explanations will help address your concerns.

“the method that combines losses between NTP and KGE was already proposed in the first NTP paper”

We have changed “the first study” to “the first systematic study” in the updated manuscript. We are aware of the usage of ComplEx in the original NTP work and indeed mentioned it at L252-L254. However, we believe there are enough contents and findings that differentiate our work from the brief mention of KGE as auxiliary loss in the original NTP paper. Specifically:

• As we mentioned in the paper (L252-L254), while the original NTP did include a section mentioning the use of ComplEx as an auxiliary loss, it did not include any further technical details or ablation studies, and such an approach is never used in the subsequent works [1,2,3]. Furthermore, as mentioend in [1] (page 6, footnote 7, bottom right), results in original NTP work were calculated with incorrect evaluation function which caused the resulting accuracy to be inflated.
• On the other hand, in this work we aim at providing a systematic study of such integration. We show that using KGE as auxiliary loss ($\text{CTP}_1$) actually performs worse than baseline CTP on large-scale datasets (Table 3 and Table 4), where the other variant ($\text{CTP}_2$) performs noticeably better.
• Besides focusing on accuracy, we also provide two other variants ($\text{CTP}_3$ and $\text{CTP}_4$) with a focus on training and evaluation efficiency.
• Furthermore, we conduct extensive analysis on the key factors of the integration and analyze the integration from the embedding perspective.

“I believe that the equation in Line 108 is incorrect: the second term should be (1 - NTPxxx).”

We apologize for the mistake, and thank you for pointing out the error. We have corrected the formula in the updated manuscript.

“except for the CTP1, the others seem to be irrelevant in easing training difficulties. Why does changing the unification equation improve training?”

First, we would like to clarify that we are not only focusing on easing training difficulties ($\text{CTP}_1$ and $\text{CTP}_2$), but also efficiency ($\text{CTP}_3$ and $\text{CTP}_4$). The latter is not supposed to ease training difficulties.

Second, we would like to clarify that in this work we do not view the training difficulties of NTPs from the sparse gradient perspective, but from the less-structured embedding perspective caused by the nature of the soft unification algorithm, as we mentioned in Section 3.4 (L186-L246). The rationale is: if there exists better global structure over the learnt embedding space of NTPs, then for two semantically-similar entities which have never been unified due to sparse proof, there are higher chances that they could have a higher similarity than other non-related entities. This differentiates ours from previous works [3, 4] that focuses directly on the sparse gradient problem. Both $\text{CTP}_1$ and $\text{CTP}_2$ do not improve the sparse proof problem, but they do improve the embedding space of NTPs to be better structured, as we show in Figure 2 and Figure 5.

“There are more systemic methods to convert the sparse computation into dense ones: Logic Tensor Network (LTN) and LogicMP. They seem to be more promising in this direction.”

First, as we mentioned above, while sparse proof is the real problem in NTPs, we take a different angle and tackle the problem from the embedding perspective.

Second, LTN and LogicMP are very different neurosymbolic methods from NTPs. While they indeed do not have sparse computation problems as in NTPs due to different algorithm derivations, we do not see how to utilize them to improve the sparse proof problem that specifically resides in NTPs.

The reason we choose to study NTPs is we believe the pure similarity-based unification mechanism is simple and more scalable than other neurosymbolic frameworks with more sophisticated tensor operations. Moreover, we believe it has the potential to be used in conjunction with the recent advances of foundational models, thereby making it multimodal with zero-shot capacity. This is indeed our next work.

[1] Pasquale Minervini, Matko Bosnjak, Tim Rocktaschel, Sebastian Riedel, and Edward Grefenstette. “Differentiable reasoning on large knowledge bases and natural language” (AAAI 2020)

[2] Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktaschel. “Learning reasoning strategies in end-to-end differentiable proving” (ICML 2020)

[3] Jaron Maene and Luc De Raedt. “Soft-unification in deep probabilistic logic” (NeurIPS 2023)

[4] Michiel de Jong and Fei Sha. Neural theorem provers do not learn rules without exploration

Thank you for your question! Please see the resposne below:

Which method should be used for different problems?

We recommend $\text{CTP}_2$ in general, as we observe $\text{CTP}_2$ generally performs the best among the four variants (L364). One special case where $\text{CTP}_1$ outperforms $\text{CTP}_2$ is on Kinship where the length of proof paths is limited to 1, making $\text{CTP}_2$ less effectiv (L367).

As also mentioned by reviewer 6URk, how do you compare with the advanced KGE method, eg., NBFNet, in terms of performance?

First, we would like to clarify that NBFNet is not a KGE model, but is GNN-based. For KGE-based models we are comparing with three popular KGE models: TransE, ComplEx and DistMult (Table 3 and 4).

Below we show results with NBFNet included. For brevity we only include MRR here. We will add NBFNet to the table after we perform hyper-parameter search as NBFNet was not evaluated on the below datasets except WN18RR. We also include LERP, the other recent model that Reviewer 6URk mentioned.

We can see LERP performs exceptionally well on WN18RR, but is outperformed by $\text{CTP}_2$ on all other datasets by a large margin. On UMLS and Nations, $\text{CTP}_2$ performs better than NBFNet, while on large-scale dataset like FB122 and WN18RR, NBFNet outperforms CTPs by a large margin. However, we want to note that on one hand, given the relatively low baseline performance of NTPs, our goal is not to solely compete for the state-of-the-art, but rather to provide detailed analysis on the properties of NTPs. On the other hand, GNN-based models are known to generally hold better performance comparing to KGEs or neuro-symbolic methods, at the cost of efficiency and interpretability. Below we show the inference speed (in millisecond) under WN18RR dataset for some popular KGE models on a V100 GPU, a batch size of 8, embedding dimension 1000 for each KGE method (default), and CTP with dimension 100, and NBFNet with dimension=32. We can see NBFNet requires the longest inference time, $10 \times$ more than CTP. On the other hand, while CTP is slower than pure KGE-based models, we believe it is still a good compromise between speed and interpretability.

Below we show additional experiments on Countries, CoDEx-S on $\text{CTP}_2$ and NBFNet. We can see $\text{CTP}_2$ outperforms NBFNet on Countries, and performs on par with NBFNet on CoDEx-S, while outperforming recent neuro-symbolic method $\text{DiffLogic}^+$ [2].

Additionally, we also conduct a systematic generalization task on CLUTRR [1], where we train on graphs with 2, 3, and 4 edges, and test on graphs with 4, 6, 8, and 10 edges (hops). Results are summarized below. We can see $\text{CTP}_2$ outperforms baseline CTP by a noticeable margin, especially on $\text{Hops} = 8,10$, while outperforming NBFNet by a large margin, except when $\text{Hops} = 4$. This suggests CTP has much better systematic generation capacity, possibly due to its explicit rule-learning capacity, as compared to NBFNet.

We would like to summarize our view on the comparison between $\text{CTP}_2$ and GNN-based NBFNet:

1. $**CTP**_2$ and NBFNet has their own advantages in case of performance: $\text{CTP}_2$ generally performs better on smaller-scale statistical relational learning datasets, while NBFNet excels at large-scale KGs. Notably, $\text{CTP}_2$ outperforms NBFNet by a large margin on the systematic generalization task(CLUTRR) where the larger numbers of hops are unseen during training.
2. $**CTP**_2$ has better interpretability: while one can approximate the edges taken by the NBFNet to form an explanation, it lacks the logical interpretation, and it is hard to understand rules learnt by NBFNet, as compared to neuro-symbolic methods like $\text{NTPs}$.
3. $**CTP**_2$ has better efficiency: as we showed in our previous comment, NBFNet is much more computationally-expensive due to its adaptation of Bellman-Ford algorithm, and requires more than $10 \times$ time for inference as compared to $\text{CTP}$.

We would also like to re-emphasize that given the relatively low baseline performance of NTPs, our contribution in this paper is not only to provide the state-of-the-art results across all methods, but also 1) to provide a systematic study on the integration of NTPs and KGEs, 2) to provide a novel view on the hardness of training NTPs from the perspective of the embedding space, and 3) demonstrates that by integrating KGE objectives we can indeed improve such embedding space to be more structured, thus benefiting the performance.

Lastly, we hope that the reviewer will kindly consider the merits of our work. If there are any additional concerns that we can address or discuss before the author-reviewer discussion period ends to raise your score, please let us know. Thank you again for your time and advise!

[1] Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. 2019. CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text. (EMNLP 2019)

[2] Shengyuan Chen, Huang Fang, Yunfeng Cai, Xiao Huang, and Mingming Sun. 2024. Differentiable neuro-symbolic reasoning on large-scale knowledge graphs. (NeurIPS 2023)

Thank you for the constructive comments. We are glad you find our study thorough and well-organized. We hope the following explanations will help address your concerns.

“choice of parameters for λ and specific KGEs for each variant”

We apologize for the confusion. By default we use RotatE for $\text{CTP}_3$ and ComplEx for all other variants, because we observed empirically these configurations give the best overall performance. We use $\lambda = 0.5$ as default weight for combining NTP and KGE score/loss for all experiments except for Figure 6, where we conduct the ablation study on $\lambda$. We mentioned these specifications in the table captions in the original submission, but we have revised the Implementation section(L306-L307) and remove the redundant descriptions in captions in the updated manuscript to make this clear.

“FB122 vs. FB15K-237”

FB122 is a subset of FB15K-237 proposed in [1] and subsequently used in multiple works [2,3,4], including GNTP[4], a direct baseline of our method. It has two further subsets: Test-I and Test-II. Test-II denotes a subset of facts that can be inferred with logical rules, Test-I denotes all other facts. We use it instead of FB15K-237 because:

• FB122 was adopted in GNTP, one of our direct baseline. By using FB122 it allows us to have a fair comparison without the need to re-perform hyper-parameter search on the baseline which may be suboptimal. Also, since the code of GNTP and most models that it compares to are written in tensorflow while we primarily use torch, we wouldn’t need to translate their source codes.
• The NTP algorithms are still not as scalable as KGEs. We indeed tried FB15K-237 on baseline GNTP, however it took more than 70 hours on a V100 for both training and evaluation, which is far beyond the time and computation we could afford.

“the related work is entangled with the ablation study figures and tables ... Please add related work after introduction.”

We apologize for the bad formatting, and thank you for the suggestion. We have moved the related work section after introduction and updated the manuscript.

[1] Guo, S.; Wang, Q.; Wang, L.; Wang, B.; and Guo, L. 2016. Jointly Embedding Knowledge Graphs and Logical Rules. (EMNLP 2016)

[2] Minervini, P.; Demeester, T.; Rocktaschel, T.; and Riedel, S. 2017. Adversarial Sets for Regularising Neural Link Predictors (UAI 2017)

[3] Garcıa-Duran, A., and Niepert, M. 2018. KBlrn: End-to-End Learning of Knowledge Base Representations with Latent, Relational, and Numerical Features. (UAI 2017)

[4] Pasquale Minervini, Matko Bosnjak, Tim Rocktaschel, Sebastian Riedel, and Edward Grefenstette. “Differentiable reasoning on large knowledge bases and natural language” (AAAI 2020)

Dear Reviewer whZm:

We appreciate your valuable comments on our paper. We have prepared a rebuttal with an updated manuscript and tried our best to address your concerns. We notice that the author-reviewer discussion period is coming to an end, and we are willing to answer any unresolved or further questions that you may have regarding our rebuttal if time is allowed.

If our rebuttal has addressed your concerns, we would appreciate it if you would let us know of your final thoughts. Additionally, we will be happy to answer any further questions regarding the paper. Thank you for your time and consideration.

Thank you for the helpful and constructive comments. We are glad you find our study thorough, helpful. We hope the following explanations will help address your concerns.

“the proposed methods are clearly situational and not straightforwardly scalable to large/complex domains.”

Compared to baseline NTPs, while $\text{CTP}_1$ is situational which only performs well on small-scale datasets and does not scale to large datasets (FB122 and WN18RR), we find that $\text{CTP}_2$ generally outperforms baseline NTPs by a large margin across both small-scale and large-scale datasets.

Compared to state-of-the-art KGE models, we agree with the reviewer that $\text{CTP}_2$ is behind the state-of-the-art KGE on WN18RR(Table 4). However, it still shows large improvements against baseline NTPs. On the other hand, on FB122 (Table 3), $\text{CTP}_2$ outperforms both NTP baselines and KGE methods by a noticeable margin. We believe these show $\text{CTP}_2$ is not purely situational and can scale to large-scale dataset, and is a good compromise between the performance and scalability of pure latent models like KGEs, and neuro-symbolic NTP framework.

“the specifics of CTP , CTP and CTP could use more elaboration; it's unclear how the KGE negative samples are included in these cases.”

We apologize for the confusion. The negative samples are included in the same way in all cases: for each triplet, we corrupt subject, entity, and both together, each with n times, resulting in $3n$ total negative samples generated per triplet. These negative samples will receive negative label $y = 0$, and the model is trained according to the NTP objective (Equation 1). We have revised the Implementation section(L305-L306) to include the description in the updated manuscript.

“is the original KGE objective still optimized (it seems like it's not)?”

We apologize for the confusion. We do not optimize the KGE objective for $\text{CTP}_{2-4}$. We have revised the description in the method section(L227-L228) to make this clear in the updated manuscript.

Dear Reviewer 5dZR:

We appreciate your valuable comments on our paper. We have prepared a rebuttal with an updated manuscript and tried our best to address your concerns. We notice that the author-reviewer discussion period is coming to an end, and we are willing to answer any unresolved or further questions that you may have regarding our rebuttal if time is allowed.

If our rebuttal has addressed your concerns, we would appreciate it if you would let us know of your final thoughts. Additionally, we will be happy to answer any further questions regarding the paper. Thank you for your time and consideration.

Thanks for addressing my questions! I'm keeping my score the same.

Thank you for the insightful comments. We are glad you find our study systematic. We hope the following explanations will help address your concerns.

"focusing only on NTP given the existence of other technical solutions such as GNN-based link predictors like NBFNet, rule miners like LERP, and a large language model for knowledge harvesting”

We agree there are numerous approaches for link prediction. We choose to focus on the integration of Neural Theorem Provers (NTPs) and Knowledge Graph Embedding (KGE) methods because they are both embedding-based methods, where the similarity-based unification operation and the objective formulation in NTPs share interesting similarity with KGEs (L181), and their properties complement each other. Moreover, because of NTPs’ pure similarity-based unification operation, we believe it has the potential to be used in conjunction with the recent advances of foundational models, thereby making it multimodal with zero-shot capacity. This is indeed our next work.

On the other hand, while we acknowledge the diversity of available methods, we believe it is neither necessary nor feasible for a single work to cover findings relevant to all paradigms. Meanwhile, NTP represents a general neuro-symbolic framework derived upon backward chaining, rather than a specific algorithm, and several prior works [1, 2, 3] have also focused solely on the NTP framework.

Regarding the specific methods mentioned by the reviewer:

• NBFNet (NeurIPS 2021) is a GNN-based link predictor that parametrizes the Bellman-Ford algorithm using neural components. This approach is fundamentally distinct from both NTPs and KGEs, and we believe it would be challenging to integrate into the current framework without deviating from our focus.
• LERP (ICLR 2023) proposes a method to encode local subgraphs as additional context for each entity in the knowledge base. We do see the possibility of using it as an alternative for KGE under the NTP framework. However, as it is a recent work, we were unaware of it during our study. Also, since it is quite distinct from KGE methods, we are not sure if we should include it in parallel with other KGE methods in a single work. Therefore, we will leave it for future work.

"analyze the proof produced when conducting link predictions"

We appreciate the reviewer’s suggestion to analyze and visualize the proofs produced during link prediction. In our original submission, we did not include these visualizations because our work does not propose a new algorithm but rather focuses on the integration of NTPs and KGEs. Consequently, we prioritized visualizations of the learned embeddings, which we believed offered more direct insight into our contributions.

However, as per the reviewer’s suggestion, we have visualized the proofs generated by the model for each dataset under CTP2 as shown below. We have also included them in Table 8 in the updated manuscript.

From the above table, we can see the model successfully learns logical rules such as place_lived(X,Y):- place_of_birth(X,Y), interconnects(X,Y):- result_of(X,Y), result_of(Y,Z), and contains(X,Y) :- capital(Y, X).

"in terms of performance, what is the performance and speed of using KGE to make link predictions?"

Below we show the inference speed under WN18RR dataset for some popular KGE models on a V100 GPU, a batch size of 8, embedding dimension 1000 for each KGE method (default), and CTP with dimension 100. In general KGE models enjoy fast training/inference speed due to its relatively simple tensor operations. For accuracy for KGE methods, please refer to Table 3 and Table 4 in the paper.

[1] Pasquale Minervini, Matko Bosnjak, Tim Rocktaschel, Sebastian Riedel, and Edward Grefenstette. “Differentiable reasoning on large knowledge bases and natural language” (AAAI 2020)

[2] Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktaschel. “Learning reasoning strategies in end-to-end differentiable proving” (ICML 2020)

[3] Jaron Maene and Luc De Raedt. “Soft-unification in deep probabilistic logic” (NeurIPS 2023)

Dear Reviewer 6URk:

We appreciate your valuable comments on our paper. We have prepared a rebuttal with an updated manuscript and tried our best to address your concerns. We notice that the author-reviewer discussion period is coming to an end, and we are willing to answer any unresolved or further questions that you may have regarding our rebuttal if time is allowed.

If our rebuttal has addressed your concerns, we would appreciate it if you would let us know of your final thoughts. Additionally, we will be happy to answer any further questions regarding the paper. Thank you for your time and consideration.

Dear Reviewer 6URk,

We just want to bring your attention to our responses to iiQA's question, where we conduct more experiments and comparison between $\text{NTP}$s and NBFNet. To summarize:

1. $**CTP**_2$ and NBFNet has their own advantages in case of performance: $\text{CTP}_2$ generally performs better on smaller-scale statistical relational learning datasets, while NBFNet excels at large-scale KGs. Notably, $\text{CTP}_2$ outperforms NBFNet by a large margin on the systematic generalization task(CLUTRR) where the larger numbers of hops are unseen during training.
2. $**CTP**_2$ has better interpretability: while one can approximate the edges taken by the NBFNet to form an explanation, it lacks the logical interpretation, and it is hard to understand rules learnt by NBFNet, as compared to neuro-symbolic methods like $\text{NTPs}$.
3. $**CTP**_2$ has better efficiency: as we showed in our previous comment, NBFNet is much more computationally-expensive due to its adaptation of Bellman-Ford algorithm, and requires more than $10 \times$ time for inference as compared to $\text{CTP}$.

Let us know if our rebuttal has addressed your concerns, and please let us know if you have any further questions regarding the paper. Thank you for your time and consideration.