Improving Soft Unification with Knowledge Graph Embedding Methods
Authors: Xuanming Cui
Chionh Wei Peng
Adriel Kuek
Ser-Nam Lim
Venue: ICML 2025 poster (2025)
Keywords: Neuro-Symbolic Systems
Knowledge Graph Embedding
Primary area: deep_learning->everything_else

Abstract: Neural Theorem Provers (NTPs) present a promising framework for neuro-symbolic reasoning, combining end-to-end differentiability with the interpretability of symbolic logic programming. However, optimizing NTPs remains a significant challenge due to their complex objective landscape and gradient sparcity. On the other hand, Knowledge Graph Embedding (KGE) methods offer smooth optimization with well-defined learning objectives but often lack interpretability. In this work, we propose several strategies to integrate the strengths of NTPs and KGEs, and demonstrate substantial improvements in both accuracy and computational efficiency. Specifically,  we show that by leveraging the strength of structural learning in KGEs, we can greatly improve NTPs' poorly structured embedding space, while by substituting NTPs with efficient KGE operations, we can  significantly reduce evaluation time by over 1000$\times$ on large-scale dataset such as WN18RR with a mild accuracy trade-off.

Improving Soft Unification with Knowledge Graph Embedding Methods
Xuanming Cui Chionh Wei Peng?
Adriel Kuek? Ser-Nam Lim
Abstract
differentiability (Rocktäschel & Riedel, 2017; Minervini et al., 2019; Badreddine et al., 2022). Neural Theorem Prover (Rocktäschel & Riedel, 2017) (NTP) is represen- tative of such approach. It introduces the concept of soft unification during backward chaining process, where the uni- fication operation is on the learnt embedding space instead of between discrete symbols. Subsequent works Greedy Neural Theorem Prover (GNTP) (Minervini et al., 2019) and Conditional Theorem Prover (CTP) (Minervini et al., 2020) implement top-k rule retrieval and rule reformulation to improve NTP's scalability and performance.
Neural Theorem Provers (NTPs) present a promis- ing framework for symbolic reasoning, combining end-to-end differentiability with the interpretability of symbolic logic programming. However, optimizing NTPs remains a significant challenge due to their complex objective land- scape and gradient sparcity. On the other hand, Knowledge Graph Embedding (KGE) methods of- fer smooth optimization with well-defined learn- ing objectives but often lack interpretability.. In this work, we propose several strategies to in- tegrate the strengths of NTPs and KGEs, and demonstrate substantial improvements in both accuracy and computational efficiency. Specif- ically, show that by leveraging the strength of structural learning in KGEs, we can greatly im- prove NTPs' poorly structured embedding space, while by substituting NTPs with efficient KGE operations, we can significantly reduce evaluation time by over 1000x on large-scale dataset such as WNISRR with mild accuracy trade-off.
Although there are numerous NeSy frameworks (Co- hen, 2016; Das et al., 2018; Minervini et al., 2017) and knowledge-base reasoning methods, we are particularly in- terested in NTPs due to their straightforward reasoning process based similarity. This simplicity brings bet- ter scaling potential compared to complex tensor opera- tions employed in other NeSy frameworks and GNN-based approaches. Moreover, such similarity- -based design also makes NTPs well-suited for leveraging pre-trained embed- dings obtained from the recent advances foundational models, thereby enabling multi-modal reasoning and po- tential zero-shot capabilities. This is crucial, as most ex- isting NeSy (Maene & De Raedt, 2023; Yang et al., 2017; Minervini et al., 2017) and Knowledge Knowledge-Graph-eeinn Graph-related meth- ods (Trouillon et al., 2016; Han et al., 2023; Zhu et al., 2021) struggles to generalize to unseen entities, significantly lag- ging behind the recent foundational and language models.
1. Introduction
Deep Learning (DL) methods have recently achieved tremendous progress various tasks such as language mod- eling (Touvron et al., 2023; Liu et al., 2023) and content generation (Rombach et al., 2022; Kerbl al., 2023). How- ever, when compared with symbolic systems, they are still limited by the long-lasting problems of the lack of interpreta- tion, out-of-domain generalizability and reasoning abilities.
Although NTP has been shown be effective on various datasets, it is known to be hard to optimize (Rocktäschel & Riedel, 2017; Minervini et al., 2019; Maene & Raedt, 2023; de Jong & Sha, 2019). Specifically, as NTPs perform top-k retrievals for unification, only a fraction of retrieved embed- ding parameters will receive gradient updates. The model optimization is thus heavily dependent on the initialization, and can get stuck in local minima (de Jong & Sha, 2019). DeepSoftLog (Maene & Raedt, 2023) addresses the above limitation by using differentiable probabilistic semiring in- stead of fuzzy semiring, along with other proposed proper- ties to smooth out the back-propagation process. However, as it requires additional modules for knowledge compila- tion (Darwiche, 2011) and requires all possible proofs to be considered during training (as opposed to k-best approxima- tion), it is intrinsically hard to scale to larger datasets.
To address the above challenges, the concept of Neuro- Symbolic AI (NeSy) has been proposed to integrate DL and symbolic Al into one end-to-end differentiable system. A popular approach for such integration is to embed discrete symbols into continuous vector space to enable end-to-end
'Deparmeett of Computer Science, University of Central Florida "DSO National Laboratories. Correspondence to: Xu- anming Cui <xuanming.cum ucf.edu>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Instead of trying to improve NTPs from the sparse gradi- ent perspective which may inevitably face performance- efficiency trade-off, in this paper we take a different an- gle and tackle the problem from the embedding perspec- tive. We find the NTPs' embedding space is extremely poorly-structured. due to the sparse unification during train- ing (detailed discussion in Section 7). On the other hand, Knowledge Graph Embedding (KGE)s (Bordes al., 2013: Trouillon et al., 2016) strong structure learners with well-defined objectives and smooth optimization process. However, as KGFs are purely sub-symbolic algorithms, they lack the interpretability as compared to NTPs.
2021; Yang et al., 2023). This line of works train a neural network to output a probability distribution over symbols, which is then consumed by a differentiable logic solver. For example, DeepProbLog (Manhaeve et al., 2018) guides a neural network with probabilistic circuits constructed by Sentential Decision Diagram (Darwiche, 201 1) (SDD). Scal- lop (Huang et al., 2021) scales up DeepProbLog by only considering top-k possible worlds. NeurASP (Yang et al.. 2023) adopts the same strategy. but replace SDD with An- swer Set Programming solver. Under this regime, the neural component is completely separated from the reasoning mod- ule. (2)Soft logic programming (Cohen, 2016; Badreddine et al., 2022; Yang et al., 2017; Rocktäschel & Riedel, 2017). This line of works are continuous relaxation on top of logic programming, by learning mapping from symbols and logic operations into latent embeddings and differen- tiable tensor operations. Logic Tensor Network (Badreddine et al., 2022) extends First-Order I Logic (FOL.) with fuzzy semantics. NEURALLP (Yang et al., 2017) is a rule-based algorithm that extends TensorLog (Cohen, 2016) by learn- ing to soft select and compose rules. Neural Theorem Prover (Rocktäschel & Riedel, 2017) extends backward chaining algorithm with soft unification. Greedy Neural Theorem Prover (Minervini et al., 2019) and Conditional Theorem Prover (Minervini et al., 2020) improve the scalability of NTP by top-k retrieval and soft rule reformulation.
Motivated by the complementary properties of NTPs and KGEs, we conduct the first systematie study for integrating KGEs into the NTP framework. The rest of the paper is arranged as follow: in Section 3 provide brief introduc- tion for NTPs and KGFs, and discuss the deficit of NTPs from embedding perspective 7; In Section 8 we explain four strategies for the integration, and conduct detailed experi- ments in Section 9. Finally, we provide ablation studies to examine important components during the integration. We wish our work can serve as first step to future studies on such integration and improve upon existing NTPs.
Contribution:
1. We provide the first systematic study for the integration of KGEs into NTPs and propose four integration strate- gies, improving both performance and efficiency. Note that using KGE as auxiliary was originally proposed in (Rocktäschel & Riedel, 2017). However, it was only briefly mentioned without any further exploration, and is not used in any subsequent NTPs (Minervini al., 2019; 2020; Maene & De Raedt, 2023).
Knowledge Graph Embedding (KGE) are SOTA meth- ods for link prediction tasks over large-scale KGs. TRANSE (Bordes et al., 2013) and its extensions (Wang et al., 2014; Xiao et al., 2015) are translation- KGEs which minimize distance between subject and ob- ject, translated by the predicate. On the other hand, RESCAL (Nickel et al., 2011), COMPLEX (Trouillon et al., 2016), TUCKER (Balazevic et al., 2019) etc. use multi- linear maps combine subject, relation and object for score calculation. Besides traditional KGEs, recent advances such as GeKCs (Loconte et al., 2023) reformulate KGEs with valid probabilistic interpretation, LERP (Han et al., 2023) aggregates sub-graph information as entity representation.
2. We show that the integration noticeably improve the baseline NTP by a large margin and achieve SOTA results on multiple datasets. In particular, analyze the issue of NTPs from their learned embedding space perspective and show that it can be benefited from the integration of KGBs. We also show that by leveraging the properties of KGEs we could drastically improve the inference and evaluation efficiency of NTPs.
Path-based KG Algorithms explicitly learn the multi- hop paths over KGs. They can be applied directly on top of KGEs by handling multi-hop relation paths as composi- tions over embedding space such as in (Lin et al., 2015), or can be formulated as path-searching algorithms, opti- mized by Reinforcement Learning objectives such as in (Das et al., 2018; Zhu et al., 2023; Lin et al., 2018). Be- sides, GNN-based approaches (Schlichtkrull et al., 2017; Zhu et al., 2021) have also shown strong performance on link prediction tasks. For example, RGCN (Schlichtkrull et al., 2017) applies GNN to knowledge-graph learning task. NBFNet (Zhu et al., 2021) generalizes the Bellman-Fort algorithm with neural operators under the GNN framework to solve path formulation.
3. We provide detailed ablations to examine the key fac- tors in the integration. Interestingly, we find NTPs can achieve superior results with pure KGE objectives under several datasets, suggesting the synergy between the two distinct methods.
2. Related Work
Differentiable Logic Programming algorithms can be roughly divided into two categories. (1) Disentangled per- ception+reasoning (Manhaeve et al., 2018; Huang et al.,
2

---

Improving Soft Unification with Knowledge Graph Embedding Methods
W1R R1. 21)
R2
WyR 21
R₂
W2R 22.
Rs W.ll (2n-1, Russ 0)
Goal: : (8, R, o)
R2,
22)
Rg, 23) Topk
topk
Topk'
Figure 1. Illustration of CTP algorithm with a transitive rule template and depth 1. Given goal (s, R, o). it first transforms the goal predicate to list of predicates forming the proof path. Then it takes the known subject and predicate R, to predict the latent object x; with top-k retrieval; it then uses the predicted 2, as the next subject and predict Z441 to step through the proof path.
3. Background
and (s', r. r.) & G. The objective is then defined as the negative log likelihood of the aggregated unification score:
4. Neural Theorem Prover
In this section we define the syntax and briefly introduce the SLD resolution and NTP algorithm. We refer the reader to (Rocktäschel& & Riedel, 2017) for an in-depth explanation.
CNTP
Σ
-y ((og(NTT/((s,r,,)))
((s.no))) @
NTP (I)
Syntax. A term t can be either a constant c or a variable X An atom is defined as combination of a predicate symbol and a list of terms. Rules are in the form of H :- B, where the head H is atom, and the body B is a list of atoms connected by conjunctions. A rule with no free variables is called a ground rule, and a ground rule with an empty body is called a fact. A substitution, denoted as a = (X. Xy/ty) assigns variables X; to terms t, and applying a substitution to an atom replaces each occurrence of X, with the corresponding term t,. In this work, we only consider atoms with binary predicates in the form of (s, r, o). where s, r and denote subject, predicate (relation) and object respectively.
where NTPğ denotes NTP with KG g, parameterized by 0.
5. KGs and Embedding Methods
A Knowledge Graph (KG) G is a directed multi-graph, repre- sented as collection of triplets (facts) (s, x where& & and R denote the set of entities and relations in G. A KGE model defines function that maps triplets to scores &RGE : 3 x R x E + R. This score function ΦXGE can be translation-based as in TRANSE (Bordes et al., 2013); @TRANSE (s, r, 0) = - 1|s + rol, or similarity-
using
multi-linear function (Trouillon et al., 2016; Yang et al., 2015). For instance, COMPLEX (Trouillon et al., 2016) de- fines the score function as ΦcoMPI.F = Re( (s. r, o))), where (, " .) denotes the tri-lincar product, Re denotes the real part of the complex number, and - denotes the complex conjugate. KGEs are traditionally interpreted as energy- based models (EBMs), where the score is interpreted as the negative energy of triplets, and are trained with contrastive objectives and negative log likelihood loss, similar to LNTN- Besides treating KGEs as EBMs, existing works (Joulin et al., 2017; Lacroix et al., 2018; Ruffinelli et al., 2020) have shown that KGEs can be effectively trained using cross- entropy loss to predict missing object over E, given subjects and predicates, i.e. by maximizing:
Backward Chaining, Given the goal, backward chaining works backward to find supporting facts and rules from the Knowledge Base (KB). It can be seen as an iterative process of applying AND/OR: the OR operation looks for all rules with matching head to perform unification. The AND module is subsequently called to iteratively prove all atoms in the unified rule's body, where the OR module is again called recursively.
NTP and Soft Unification. NTPs provide a continuous relaxation of backward chaining by introducing soft unifi- cation. It calculates unification score 7 ΦNTP c2) over the embeddings of two symbols, where ΦNT refers to the predefined similarity function, C; and ej denotes two constant terms to be unified. In case of NTP, a Gaussian kernel is adopted for ΦNTT. The unification score 7 at each proof state are then aggregated following the min/max fuzzy semiring, also known as the Gödel t-norm. Specifically, the AND module performs min aggregation as all sub-goals have to be proved for the given rule, and OR perform max aggre- gation, since we only need one proof to be true to prove the goal. During training, given KG G, each fact (s, r, o) E g is corrupted to obtain negative samples (s', o), (8, (s,ro.
log p(o | s. = ØxxE (x.e(s,7,0) - log Σ exp Φxoz (s, (8, o'EE
6. NTPs as Memory-Augmented Path Algorithm
Inspired by Conditional Theorem Prover (CTP) (Min- ervini et al., 2020) we can implement NTP as a memory- augmented path- path-based algorithm. Instead of searching for all rules in the KB, CTP extends NTP by learning a goal transformation module that directly transforms each goal
We focus on function-free First Order Logic, and therefore does not consider structured terms.
3

---

Improving Soft Unification with Knowledge Graph Embedding Methods
predicate list of predicates following pre-set rule tem- plates (e.g. transitivity), thereby forming the proof paths. Given (sub)goal, the model steps through each atom formed by the transformed goal predicate until it reaches the end of the path. The above procedure is instantiated recursively for each atom (sub-goal) along the path until it reaches the depth limit. This formulation gives us more flex- ibility for integrating KGE methods comparing to original NTP. In Figure 1 we show simple example of CTP with depth- 1 and one transitive rule template of length n. At each step, the process can be viewed as sampling k plausible objects given the subject and predicate o ~ r), which shares similar formulation as in formula 2.
receive gradient updates due the fuzzy min/max oper- ations. In Figure 2 show the distribution of pairwise unification scores between entities, and we could observe the pairwise score distribution for CTP (blue) is mostly close to 0, suggesting only a handful of embedded symbols have interactions with each other. This lack of interaction can lead to an unstructured and suboptimal embedding space, negatively affecting the performance of NTPs.
Therefore, given the above challenge in training NTPs, in this work we explore different strategies for leveraging the strengths of KGEs to regularize and enhance the embedding space of NTPs, given the proven effectiveness of KGEs in learning structured representations.
7. Hardness in Training NTPs
8. Method
Previous works (Rocktäschel & Riedel, 2017; Maene & De Raedt, 2023; de Jong & Sha, 2019) have primarily fo- cused on analyzing and addressing the limitations of NTPs from the perspective of unsmooth optimization, particularly in relation to the sparse gradient problem. However, at- tempts to mitigate this issue often introduce additional com- putational overhead. For example, DeepSoftLog (Maene & De Raedt, 2023) tackles the sparse gradient problem in NTP training by employing differentiable probabilistic semantics, combined with a knowledge compilation step for probabilis- tic inference, and evaluates the entire proof tree (as opposed to using a top-k approximation) to ensure accurate gradient calculation. While this approach yields improved accuracy and provides more interpretable probabilistic framework, it struggles to scale beyond small KBs.
In this section we discuss the four variants considered for integrating KGEs with NTPs. In Table 1 we summarize how each variant are implemented on top of CTP.
KGE as an auxiliary loss model The most straightfor- ward strategy for leveraging KGEs to support NTP training is to use KGE as an auxiliary model for loss calculation. The overall loss for training NTPs then becomes:
C C= (1-
Σ
[ [ (=yoog(KGB((ss:r,00)
((ano)))) eg
- -(1- log(1 - KGE,((s; + x
where À is a parpee-e controlling the weight for the mixture. We denote this variant as CTP1. Note that using KGE an auxiliary loss term was briefly mentioned in the original NTP paper (Rocktäschel & Riedel, 2017). However, it was not further examined nor was it used in the subsequent works in GNTP and CTP.
FB122
WN18RR
NTP4 KGF
KGE as an auxiliary score function. Similar to CTP1, we again consider utilizing KGE score function. But rather than appending it as loss term at the very end, here we inject KGE score function dKGE into NTPs as an auxiliary score
Figure 2. Distribution of pairwise similarity from CTP (blue) and CTP combined with KGE (orange).
In contrast previous works, we try view the hardness in NTP training from the embedding perspective. Unlike KGEs, which compute triplet scores based on interactions between entities and predicates, NTPs derive embeddings solely from pairwise unification scores. This results em- beddings in NTPs being less structured. Furthermore, while KGEs typically sample a large number of negative exam- ples (e.g., 256) to learn the distribution of entities given subject/object and relation: (o ~ P(s, r)) or (s ~ P(r, o)). NTPs generally sample only a single negative example per entity and retrieve only the top-k facts from the KB for uni- fication, where l < [E). As a result, semantically similar embeddings in NTPs may end up in vastly different regions of the embedding space if they are never unified or do not
@mized AdwTe + (1 A)OKGE- In this way, we could provide additional regularization at each proof step, and force the model to learn interactions between entities and predicates along the proof path. We refer to this variant as CTP2, Despite the simplicity, we find this variant to bring the most consistent improvement across most experiments.
KGE for stepping through. For translation- based KGEs such as TRANSE and ROTATE, the tail object o can be effi- ciently calculated given (s. To leverage this translational property, we consider replacing the topk retrieval with a translation-batt operation to improve inference efficiency. Specifically, given a (s, r) pair, we use translational KGE to obtain corresponding object and then retrieve the closest
4

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Modules
CTP
VARIANTS
step
i = topk (3, r), k): -
CTP3: 2 = trans(s,
Score
7 = (NTT 2), (1
CTP2: y = A (,,,,,,,,,,)))) 2), (11) + (1 A) (8,7,
Scoreiinal
= kopk"((z, r, o). k); ONr ((2, o0)
CTP₁:
7= 7=0KaE (2, r.
loss
Cxte
CTP::
L A + (1 - A)
Table 1. Summary of the proposed four variants for integration. We consider four modules in CTP to inject KGEs: 1) step: Given (s, r) find o; 2) scoreats:: unification score along each proof path; 3) scorenal: unification score calculation at the last proof step, and 4) loss: the final loss calculation. Column CTP/VARIANT shows the original/moodifed algorithm by integrating KGEs with the corresponding modules. The variant only differs from the original CTP for the corresponding module (for instance, CTP, includes the KGE objective in the final loss function. This is the only difference between baseline CTP and CTP1, and all other variants do not include the KGE objective in their loss function). G denotes the KG, and G[i] refers to the i-th facts in the KG. trans denotes the translation function of KGEs, z refers to the tail entity predicted by (s, r). and topk denotes the top-k retrieval from G that returns the top-k indices í.
facts for score calculation. During inference we skip the retrieval and score calculation. This variant, referred to as 3TP3, is designed to improve the efficiency of NTPs. In this case, for each proof path, CTP3 is very similar to the path-ban based KGE method PTRANSE (Lin et al., 2015). They differ in (1) PTRANSE follows KGE training strategy, and utilize additional prior for handling spurious relations, while (2) 3TP3 3 calculates unification scores along the proof path, and uses NTP's retrieval-based score calculation.
A: = 10 we need to compute the pairwise distance between two matrices of shape (40, 943 10. 3d). This is done at the end of every proof path, leading to extremely slow evaluation compared to KGEs. Therefore, we try to replace the last proof step with KGEs, while keeping the previous steps with NTP. In this way. we wish to leverage the multi- hop reasoning ability of NTPs while using KGEs for local ranking at the final step. We refer to this variant as CTP4.
While it trivial to combine any variants together, we do not observe noticeable performance gain by doing so. Therefore we leave them separated for clarity.
The replacement of top-k with the 1-1 mapping by transla- tional KGE methods results in two drawbacks: 1. Limited expressiveness due to the top-1 retrieval. 2. Susceptible to spurious proof paths where subject and object are connected but logically irrelevant (Lin et al., 2015). For example, con- sider the path (s, born.nn, 01) - looclleeddiv 02) -> (o2, notable people, notable_peoplee o) where and are connected but ir- relevant. These issues become more obvious when the size and complexity of the dataset increase. Therefore, we fur- ther consider two approaches to mitigate these limitations. 1. Learnable entity expansion module. we add an additional learnable neural module W E ((d,k) which learns a map- ping from the resulting entity embedding s obtained from the translational KGE function to neighboring entities {-){- 2. Filtering spurious relation paths. We consider using the Path Constraint Resource Allocation (PCRA) for calculating the path reliability by measuring how much resource flows from the head to the tail entity following a path, as inspired by PTransEE (Lin et al., 2015).
9. Experiments
10. Experimental Setups
Dataset We conduct experiments on popular link predic- tion datasets including Countries, Nations, UMLS and Kin- ship (Kemp et al., 2006). Following GNTP (Minervini et al., 2019) we experiment on FB122 (Guo et al., 201 6a), WN18RR (Dettmers et al., 2018), and additionally CoDEx- S (Safavi & Koutra, 2020). FB122 consists of two test splits: T and Test-II, where Test-Il contains the set of triplets that can be inferred via logic rules, and Test-I denotes all other triplets. We follow the same evaluation protocol as in GNTP and CTP, and report Mean Reciprocal Rank (MRR) and HITS @ under the filtered setting. Besides, we also test systematic generalization capabilities on CLUTRR (Sinha et al., 2019) dataset, by testing on unseen relations between entities that requires more reasoning steps than the model is trained on, as done in CTP (Minervini et al., 2020).
KGE for final score calculation. We consider applying KGE the final step at each proof path. One drawback on NTPs' efficiency is their evaluation speed. During eval- uation of link prediction task, in order to rank all the entities in the KG, the model retrieves top-k facts for each combination of the missing entity and the known predicate- object/subject pair, followed by the unification score calcu- lation between two tensors of shape (()), k, 3d) where k is the retrieved & facts, and d is the embedding dimension. For example, WN18RR dataset contains 40,943 entities. With
Baseline. We compare our work with NTP-based meth- ods: NTP (Rocktäschel & Riedel, 2017), GNTP (Min- ervini et al., 2019) and CTP (Minervini et al., 2020), KGGE-based COMPLEX (Trouillon et al., 2016) and DIST- MULT (Yang et al., 2015), rule miner such as NEU- RALLP (Yang et al., 2017), MINERVA (Das et al., 2018), DIFFLOGIC (SHENGYUAN et al., 2023).LERP (Han et al., 2023), and GNN NBFNET (Zhu et al., 2021).
5

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Datasets
Metrics
cTP:
CTP2
3
CTP4
NTP
GNTP
CTP
NEURALLP MINERVA NBFNET DRUM LERP
99.3
100
98.1
97.8
90.8
100
100
100
100
100
Countries
AUC-PR
94.2
90.3
89.7
87.4
75.1
72.8
93.85
S3
93.2
96.5
92.8
90.4
56.7
91.3
94.8
92.2
90.0
95.74
MRR
0.75
0.71
0.5
0.59
0.35
0.71
0.62
0.72
0.80
0.53
0.64
HITS@ 1
61.6
57.5
49.1
48.9
24.0
58.6
56.5
47.5
60.5
63.2
36.7
50.0
Kinship
HITS@3
85.0
82,4
71.4
67.9
37.0
81.5
82.6
70.7
81.2
89.1
62.8
73.5
HITS@ 10
96.0
95.6
92.8
90.1
57.0
95.8
95.3
91.2
92.4
96.6
88.5
93.1
MRR
0.63
0.79
0.53
0.55
0.61
0.66
0.71
0.75
HITS@
44.4
68.9
31.84
34.2
45.0
49.3
56.2
63.3
Nations
HITS@3
85.6
51.92
52.8
73.0
HITS@ 10
98.9
99.7
83.06
79.4
87.0
98.5
99.5
95.1
MRR
0.82
0.85
0.65
0.70
0.80
0.84
0.81
0.78
0.82
0.82
0.69
HITS@1 1
69.9
75.2
54.6
62.7
70.0
73.2
69.4
64.3
72.8
72.1
54.6
64.6
UMI.S
HITS@3
93.2
94.6
77.4
84.4
88.0
94.1
89.8
86.9
90.0
89.6
80.8
85.5
HITS @ 10
98.7
98.2
92.6
92.2
95.0
98.6
95.3
96.2
96.8
97.1
93.5
94.2
Table Link prediction results on Countries, Kinship, Nations and UMLS datasets. HITS are reported as %.
Transfi
Rotall:
ComplEx
DistMult
NBENET
CTP3
fore, can be more effective at regularizing the embedding space compared to appending the loss outside the proving process in CTP1. Moreover, KGEs are usually trained with large numbers of negatives, directly adding KGE the loss term of NTP may not be ideal. This can be confirm where CTP1 performs reasonably well on small datasets such as Kinship (1 0.04 MRR compared to CTP2, but sig- nificantly lag behind on FB122 (4 0.12 MRR)
9.3
40
0.32
0.24
113
8.2
Table Inference speed (millisecond) comparison WNI8RR.
Implementation. We conduct our experiments primarily on CTP (Minervini et al., 2020). Since the original CTP did not evaluate on large-scale dataset 122 and WN18RR, we perform hyper parameter tuning to obtain the CTP base- line. By default, we use COMPLEEX for CTP1, CTP3 and CTP4, and ROTATE for CTP2 as we observe best overall performance under these settings. During training. we ob- tain negative samples by corrupting subject, entity, and both, each with n times, resulting in 3n negative samples gener- ated for each triplet. These negative samples will receive 0, and the model is trained according
Systematic Generalization. In Table 6 we show results on CLUTRR (Sinha et al., 2019) datasets, where we train the model on graphs with 2-3 edges and test on graphs with 4- 10 edges. We can observe CTP2 has smallest performance degradation the number of hops increases, with a 0.04 decrease from hops to 10 hops. On the contrary, NBFNet suffers from increasing edge length with accuracy de- crease of over 0.3. In particular, CTP2 shows noticeably stronger performance compared to CTP, which has little improvements against baseline CTP.
negative label to the NTP objective (Eq. 1). For CTP; and CTP2 we use = 0.5 as the default weight for combining KGE and NTP.
11. Results
Inference Time per Sample
Evaluation Time per Sample
Link prediction. In Table 2, 4 and 5 show link pre- diction results on the evaluated datasets. In most cases, can observe CTP2 performs the best among our proposed four variants, and outperforms other NTPs by large mar- gin, achieving SOTA results on Countries, Nations, UMI.S, FB122 and CoDEx-S datasets. While NBFNET achieves best performance on WN1SRR, it comes at the cost of ef- ficiency (Table 3), with the longest inference time, 13x more than CTP2. On the other hand, while CTP, is slower than some KGE-based models, we believe it is still a good compromise between speed and interpretability.
Seconds (Logescale
10-1
FB122
WN18RR
10a
FB122 WN19RR
10
10
10-2
CTP
CTP,
CTP
CTP
CTPs
CTP₂
Figure 3. Second/sample in log-scale on FB122 122 and WN1SRR dataset on NVIDIA V100 GPU with batch size 512.
Boosting NTP speed with KGE Despite having lower ac- curacy, CTP3 and CTP4 can significantly improve training and evaluation efficiency of NTP, especially on large-scale dataset. In Figure 3, we show par-s inference and eval- uation time under CTP, CTP, and CTP,, 4. For inference. CTP, requires 2x and less time compared to CTP on
We conjecture the advantage CTP2 over CTP, is the injection of KGEs into NTP's chaining process, effectively regularizing each latent subject along the proof path. There-
6

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Test-1
Test-II
Test-ALL
H@3 3
H@3
H@ 10
MRR
H@3
H@5 5
@@ 10
MRR
H@3
H@5
H@ 10
MRR
KALEp
38.4
44.7
52.2
0.32
79.7
84.1
89.6
0.68
61.2
66.4
72.8
0.52
With Rules
KALE,
36.3
40.30
44.90
0.33
98.0
99.0
99.2
0.948
70.7
73.1
75.2
0.67
ASRD
37.3
41.0
45.9
0.33
99.2
99.30
99.4
0.984
71.7
73.6
75.7
0.67
KBLRN
74.0
77.0
79.7
0.70
TRANSE
36.0
41.5
48.1
0.29
77.5
82.8
88.4
0.63
58.9
64.20
70.2
0.48
DISTMULT
36.0
40.3
45.3
0.31
92.3
94.7
0.874
67.4
70.2
72.9
0.63
COMPLEX
37.0
41.3
46.2
0.33
91.4
91.9
92.4
0.887
67.3
69.5
0.72
0.64
GNTP
28.6
31.2
35.8
0.28
94.2
95.8
96.0
0.92
61.5
63.2
64.5
0.61
Without Rules
CTP
31.2
34.7
39.51
0.30
96.1
97.0
97.9
0.94
64.5
65.1
68.3
0.63
NBENct
57.2
59.6
70.7
0.51
CTP1
30.6
33.1
37.8
0.29
95.0
95.9
96.6
0.89
60.4
61.3
62.9
0.56
CTP₂
34.4
38.2
43.1
0.32
99.1
99.2
99.4
0.98
69.9
71.32
73.0
0,68
CTP3
25.3
30.2
34.2
0.25
93.7
94.5
94.8
0.83
59.4
60.8
62.2
0.53
CTP3
30.2
32.7
37.1
0.28
94.5
95.4
95.9
0.85
61.1
64.6
67.4
0.61
Table 4. Link prediction result on FB dataset. Following GNTP (Minervini et al., 2019) we report accuracy on Test-I, Test-ll and
ALL..ALL. H@m are reported as %. KALEp and KALE, denote KALE-Pre and KALE-Joint from (Guo et al., 2016b). ASR denotes ASR-DistMult from (Minervini al., 2017). All the aforementioned models have access to the ground-truth logic rules.
Metrics ,TP, CTP, CTP3 CTP, GNTP CTP COMPLEX DISTMULT NEURALLP MINER. DRUM NBFNET DIFFLOGIC
WN18RR
MRR
0.39
0.51
0.37
0.33
0.38
0.44
0.41
0.46
0.46
0.45
0.43
0.55
0.50
H@1
36.4
46.2
35.2
31.8
37.1
38.6
38.2
41.0
37.6
41.3
49.7
H@3
37.9
56.6
36.6
33.5
38.5
41.2
43.3
44.1
46.8
45.6
57.3
@@
41.5
63.5
39.4
37.7
39.5
50.7
48.0
65.7
65.7
51.3
56.5
66.6
58.7
CoDExS
MRR
0.30
0.48
0.35
0.27
0.29
0.32
0,40
0.44
0.29
0.48
0.46
22.5
39.5
33.4
20.5
21.4
30.2
29.3
37.2
41.9
H 1@3
35.7
54.6
50.2
34.1
36.6
49.5
44.9
50.4
54.3
H@ 10
50.1
66.3
58.9
49.8
52.2
56.3
62.3
64.6
39.5
65.5
65.5
Table 5. Link prediction results on WN1SRR and CoDEx-S. H H@m is reported as %.
# of Hops CTP;
CTP2
CTP₁
LSTM MHA NBFNET
Kinship
Nations
UMLS
0.98
0.99
0.98
0.98
0.81
0.98
5
0.98
0.99
0.98
0.95
0.76
0.96
6
0.97
0.99
0.97
0.88
0.74
0.85
7
0.97
0.98
0.96
0.87
0.70
0.79
Figure 4. t-SNE visualization of embeddings for CTP (blue) and CTP2 (orange) with perplexity = 5.
8
0.94
0.98
0.94
0.81
0.69
0.78
0.90
0.96
0.89
0.75
0.64
0.73
10
0,90
0.95
0.89
0.75
0.67
0.67
clearly observe CTP2-COMPLEX also exhibits better global structures, whereas for CTP there only exists extremely local (pairwise) pattern. On the other hand, as shown in Figure 2, while baseline CTP (left, blue) exhibits extremely sparse connections between entities with unification score all gathered around O, CTP combined with KGE objec- tives (right, orange) shows smoother score distribution, suggesting a much denser connectivity.
Table Systematic generalization test on Clutrr, where we train on graphs with 2-3 edges and test graphs containing 4- 10 edges.
FB122 and WN18RR dataset, while CTP, reduces even further by 28x and 92x. For evaluation, CTP3 requires 2x less time than CTP on both datasets, while CTP, reduces 942x and 1452x on FB 122 and WN18RR. While perfor- mance of CTP, degrade noticeably, we show Table 12 (Append.) we can substantially improve its accuracy by incorporating more negative samples during training.
In Table 8 we show entity- paiity--pirsss with their similarity score. At top of the table we can observe CTP2's top- similar entity-pairs have much higher similarity score, and are more semantically correct as compared CTP, whose similarity score decreases drastically. At the bottom of Table 8 show three entity-pains which are not successfully unified during training of CTP2- We can observe even though they are never unified directly, their similarity scores still show their relevancy as compared to CTP. For instance, the entity pair Songer-songwriter Lyricist) has score of 0.22 for
12. Ablation Studies
Regularized Embedding space In Figure we show the t-SNE visualization of the embedding space of original CTP and CTP,-COMPLEX. For both methods, we could observe a few points being close to each other, suggesting the model are able to learn that they are unifiable. However, we can

---

Improving Soft Unification with Knowledge Graph Embedding Methods
UMLS
Kinship
FB122
Test-ALL
KGE
MRR
H@1
H@3
H@ 10
MRR
H@1
H@
H@ 10
MRR
H@3
H@5
H@ 10
CTP
0.80
69.4
89.8
95.3
0.70
56.56
82.64
0.95
0.63
64.5
65.1
68.3
DistMult 0.78
67.4
93.2
0.71
58.5
81.2
0,94
0.54
59.31
62.23
63.14
COMPLEX
0.81
68.9
93.1
98.7
0.74
61.6
85.0
95,94
0,56
60.4
61.3
62.9
СТР₁
TRANSE
0.74
61.1
83.9
96.0
0,43
32.3
47.5
64.15
0.51
57.42
60.04
62,43
ROTATE
0.67
53.1
77.5
92.6
0.61
46.6
68.9
91.52
0.50
57.34
61.47
62.85
DistMult
0.84
74.5
93.1
98.3
0.71
59.0
79.9
93.5
0.68
69.35
72.1
73.4
COMPLEX
0.85
75.2
94.6
98.2
0.72
57.0
82.3
95.3
0.68
69.9
71.3
73.0
CTP2
TRANSE
0.83
72.1
97.0
0.71
58.7
80.6
0.64
64.1
67.4
68.2
ROTATE
0.82
70.6
93.4
98.1
0.71
59.2
80.6
93.8
0.64
65.1
68.2
69.8
TransE
0.48
78.2
0.49
40.3
68.12
90.54
0.31
28.8
35.7
44.4
CTP3
ROTATE
0.65
54.6
77.4
92.5
0.54
45.2
71.47
92.84
0.53
59.4
60.8
62.2
DistMult
0.72
57.1
78.2
89.0
0.61
49.7
69.52
0.62
62.4
64.32
66.8
COMPLEX
0.76
62.7
84.3
92.1
0.59
48.9
67.9
90.1
0.61
61.1
64.6
67.4
CTP4
TRANSE 0.58
50.3
72.4
90.1
0.53
44.6
63.21
90.5
0.48
55.3
57.8
59.0
ROTATE
0.61
49.5
74.2
91.8
0.50
43.9
63.7
89.2
0.60
61.4
64.0
67.0
Table 7. Link prediction results on UMLS, Kinship and FB 122 dataset with different KGE models.
CTP₂
CTP
UMLS
KINSHIP
CTP2
0.99: (Baptists, Protestantimm)
0.92: (England.UK)
CTP
0.94: (Christianity, Latheronism)
0.72: (Musician Record. Record.producer) producer))
(Christianityy Catholicism)
(TV Direcctor -.reccerrTV-rrouuerr)
0.6
0.91: SinglishLLangg French Lang)
0.54: (Composer MussporerMusiciion Musiciam)
FB122
WN1 BRR
(England, United Kingdom)
(Composer Record producer)
0.89: (Lutheronism,, Catholicism)
0.51: (Film,
FFilm_Prriii Producer er. producer)
0.6
0.84: (Singer, Songwriter)
0.40: (Comedian TV producer)
0.81: (Singer-songurrigg Musician)
0.38: (Film Producer, TV Director)
0.4
0.80: (Writer, Author) (Methodism, Catholicism)
0.38: (Comedion,) Writer) Barniih.Bcceeorraee
Figure 5. MRR with different weight À
0.23: (Los Angeles, Malibu)
0.12: (Los Angeles, Malibu)
0.22: (Singer-songurrieer, Lyricist)
0.0003: (Singer-songwrice) Lyriciat)
0.25: (Ontario, Canada)
0.19: (Ontario, Canada)
dataset, CTP1's 's performance decreases noticeably when
Top-10 entity-pairs ranked by similarity score on FB122. Bottom: entities that never unified during training of CTP2. Green/Red denotes if entity-pair ever been unified or not.
Table Top:
À = 0. This suggests the limitation of purely relying on KGE objectives under NTP scheme on larger datasets.
CTP2, but only -4 for CTP when it never unified. This suggests CTP2 can interpolate between un-unified entities due to more structured embedding space.
Effect of using different KGEs In Table 7 we show the performance of CTP1, CTP2 and CTP4 using different KGE methods: ComplEx, DistMult, TransE and RotatE, and CTP3 with TransE and RotatE, With CTP, and CTP2, 2,, we can observe that the two similarity MUSTMULT generally yields the best performance, whereas translation-based KGE TransE and RotatE often lag back by large margin. For instance, CTP, achieves 0.81 MRR on UMLS with COMPLEX, but only 0.67 MRR under ROTATE, In general, we observe that CTP2 is mostly invariant to the choice of KGE methods, followed by CTP1, whereas CTP; and CTP,'s performance can vary largely with different KGE methods. This is expected, as CTP, and CTP2 are using KGE score functions regularization term, whereas CTP3 and CTP4 predict directly based on KGEs.
KGEs, COMPLEX
Effect of weight We find the weight for combining NTP and KGE loss/score function plays an important rule on the performance of CTP; and CTP2. Therefore, repeat experiments with different À on three tested datasets, with results visualized in Figure 5. We can observe as CTP2 tends to be invariant against X, performance of CTP; on UMLS and Kinship dataset increases when À decreases, yet decrease on FB122 and WNISRR with smaller X.
Interestingly, we find that for small datasets such as UMLS and Kinship, CTP, and CTP2 maintain decent performance when \ = 0, suggesting both model perform well even when the loss/score is fully substituted by the KGE loss/score. For example, CTP, achieves SOTA performance 0.87 MRR on UMLS when = 0.1, and 0.85 with À = 0. On the other hand, for bigger datasets such as FB122 and WN18RR
Improving CTP3 In Table 9, we show results on the effect of Path Constraint Resource Allocation (PCRA) filter- ing and the Entity Expansion (EE) module for CTP3. We can see both PCRA and EE bring noticeable performance
8

---

Improving Soft Unification with Knowledge Graph Embedding Methods
UMLS
Kinship
Nations
FB122
WNISRR
Codex-s
H@ 10
MRR
H@ 10
MRR
H@ 10
MRR
H@ 10
MRR
H@ 10
MRR
H@10
MRR
CTP3
92.6
0.65
92.8
0.5
83.0
0.53
62.2
0.53
39.4
0.37
58.9
0.35
+ PCRA
93.3
0.66
92.7
0.50
83.1
0,54
63.6
0.55
41.6
0.39
61.7
0.38
+ EE
94.1
0.67
93.6
0.52
83.9
0.54
65.7
0.60
43.6
0,41
64.2
0.42
Both
94.1
0.67
93.6
0.52
85.0
0.55
66.8
0.63
44.2
0.42
64.6
0.44
Table 9. Ablations on the Path Constraint Resource Allocation (PCRA) and the learnable Entity Expansion (EE) module for CTP3.
WHIBARR
the most stable and noticeable improvements across various datasets and configurations. Finally, we conduct detailed ablations and analyze on key components of the integration.
Impact Statement
may Chople
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Figure 6. t-SNE visualization of entity embeddings from trained CTP2-COMPLEX (left) and COMPLEX (right).
gain under most datasets. In particular, both PCRA and BE's performance gains are relatively marginal on smaller KGs such as Kinship and Nations, but are more effective on larer datasets such as FB 122 and WN1SRR. For example, with both PCRA and EE, CTP3 achieves 0.63 MRR on FB122, a 10% increase over baseline CTP3.
References
Badreddine, S., d' Avill Garcez, A., Serafini, L., and Spranger, M. Logic tensor networks. Artificial Intel- ligence, 303:103649, February 2022. ISSN 0004-3702. doi: 11t.://..11111/.... j.ttiii..a..i...a.m/aa 2021. 103649.
URL http: /xx.
doi 10.
13. Limitations
Balazevic, I, Allen, C., and Hospedales, T. Tucker: Tensor factorization for knowledge graph completion. In Pro- ceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Interna- tional Joint Conference on Natural Language Processing (EMNLP-IJCNLPP) Association for Computational Lin- guistics, 2019, doi: 10. 10.18663//1//11-15222 URL http:
While incorporating KGE objectives into NTPs improves the structural properties their learned embeddings and enhances performance, certain limitations remain. In Fig- ure we show i-SNE visualization of learned embeddings between CTP2 and COMPLEX. Although CTP2 exhibits denser pairwise similarity than the baseline CTP, shown in Figure 2, its embedding space on large-scale datasets like WN18RR lacks the clear global structure obtained through pure KGE training. We hypothesize two contributing fac- tors: (1) the significantly fewer negative samples used in NTPs compared to KGEs limit the model's ability to cap- ture global structures large datasets, and (2) the sparse gradient issue becomes more pronounced dataset size increases. While in this paper we focus on the embedding perspective of NTPs, the sparse gradient problem still re- mains as a bottleneck to the model performance.
//dx. doi 10tp:///1111101///10000011133130
Bollacker, K., Cook, R., and Tufts, P. Freebase: a shared
database of structured general human knowledge. In Proceedings of the 22nd National Conference on Artificial Intelligence Volume 2, AAAI'07, pp. 1962-1963. AAAI Press, 2007. ISBN 9781577353232.
Bordes, A., Usunier, N., Garcia- A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. In Proceedings of the 26th Inter- national Conference on Neural Information Processing Systems Volume 2, NIPS' 13, pp. 2787-2795, Red Hook, NY, USA, 2013. Curran Associates Inc
14. Conclusion
In this paper we propose to leverage KGE methods to im- prove NTP performance and efficiency. by enhancing NTP's embedding space to be better structured and regularized, and by replacing computationally expensive NTP components with efficient KGE operations. We explore four variants for integrating KGEs into the NTP, and show that by injecting KGEs into NTP's score calculation (CTP2) we can achieve
Cohen, W. W. Tensorlog: A differentiable deductive database, 2016. URL https::/aaxiv..tt abs/ 1
Darwiche, A. Sdd: a new canonical representation propo- sitional knowledge bases. In Proceedings of the Twenty-

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Second International Joint Conference on Artificial In- felligence- Volume Volume Two, 11 pp. 819-826. AAAI Press, 2011. ISBN 9781577355144.
National Conference on Artificial Intelligence Volume I, AAAL06, pp. 381-388. AAAI Press, 2006. ISBN 9781577352815.
Das, R., Dhuliawala, S., Zaheer, M., Vilnis, L., Durugkar, I., Krishnamurthy, A., Smola, A., and McCallum, A. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning, 2018. URL https:: //aaaxiivvvorr..a/aaa
Kerbl, B., Kopanas, G., Leimkühler, T., and Drettakis, G. 3d gaussian splatting for real-time radiance field render- ing. 2023. URL https: /arxivv.vv//.///////////////av// org/ /ab//b///// 2308. 04079.
/bs//711.... 05851.
Lacroix, T., Usunier, N., and Obozinski, G. Canonical ten- sor decomposition for knowledge base completion, 2018. URL peattps://axxi...oo
de Jong, M. and Sha, F. Neural thcorem provers do not learn rules without exploration, 2019. URL https:
/00...////...000 07297.
// //arxiv. org/ aaaaaabss19990 190699966... 06805.
Lin, X. V., Socher, R., and Xiong, C. Multi-hop knowl- edge graph reasoming with reward shaping, 2018. URL https:/ arxiv. www.i.www..................wwott abs/ / 1808. 10568.
Dettmers, T., Minervini, P., Stenetorp, P., and Riedel, S. Convolutional 2d knowledge graph embeddings. 2018.
URL https:::p//. // //arxivvv.////////////aa///aavvv org/ abs/1707 01476.
Lin, Y., Liu, Z., Luan, H., Sun, M., Rao, S., and Liu, Modeling relation paths for representation learning of knowledge bases, 2015. URtphtts://axxii.orrr abs /156. 00379.
Guo, S., Wang, Q. Wang. I.., Wang, B., and Guo, L. Jointly embedding knowledge graphs and logical rules. In Su, J., Duh, K., and Carreras, X. (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natu- ral Language Processing, pp. 192-202, Austin, Texas, November 2016a. Association for Computational Lin- guistics. doi: 10. 10.18653/1//116-100 URL https: //aclanthology wtw.oogyooog//1111111110
Liu, H., Li, C., Wu, Q., and Lee, Y. Visual instruction tun- ing, 2023. URL httpt:////eatt //tpsii//axvvv../ org/ argg/bs///0 ab///3/s///// 08485.
Loconte, L., Mauro, N. D., Peharz, R., and Vergari, A. How to turn your knowledge graph embeddings into gener- ative models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:
Guo, S., Wang, Q. Wang, L., Wang, B., and Guo, L. Jointly embedding knowledge graphs and logical rules. In Conference on Empirical Methods in Natu- ral Language Processing, 2016b. URL https::///// /api. semanticschole org/ wttppoooaa.....ooooooooo..aaa 7958862.
// //openeeview net [tr.m
Maene, J. and De Raedt, L. Soft-unification in deep prob- abilistic logic. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Han, C., He. Q.. Yu, C., Du, X., Tong, H., and Ji, H. Logi- cal entity representation in knowledge-graphs for differ- entiable rule learning, 2023. URL https://arxix: org/abs/ 2305. 12738.
Maene, J. and Raedt, L. D. Soft-unification in deep prob- abilistic logic. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: / /ooeerevieww net/ for.mmiddsssse 6M8naPSv. SMM
Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song. L., and Si, X. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. In Beygelz- imer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL httpt::///// http://ppperee.eeee/o// net/forum! id=ngdcAltIDvj.
Manhaeve, R., Dumančié, S., Kimmig, A., Demeester, T., and Raedt, L. D. Deepproblog: Neural probabilistic logic programming, 2018. URL https://arxiv.cr abs/1805.. 1///1805..0877
Johnson, J., Douze, M., and Jégou, H. Billion-scale similar- ity search with GPUs. IEEE Transactions on Big Data, (3):535-547, 2019.
Miller, G. A. Wordnet: a lexical database for english. Commun. ACM, 0001-0782. doi: 10. 10.1145/219717.2197488 URL https: //doi. 21t.0/9.211.111///297777..221119
41, November 1995. ISSN
Joulin, A., Grave, E., Bojanowski, P., Nickel, M., and Mikolov, T. Fast linear model for knowledge graph em- beddings, 2017. URL https:: http:://axvvvvvoo abs/ 1710. 10881.
Minervini, P., Demeester, T., Rocktäschel, T., and Riedel, S. Adversarial sets for regularising neural link predic- tors, 2017. http: httpp:::////xvv.oo/ wttp://.rrrraab/////////// 07596.
abs/1707.
Kemp, C., Tenenbaum, J. B., Griffiths, T. L., Yamada, T., and Ueda, N. Learning systems of concepts with an infinite relational model. In Proceedings of the 21st
Minervini, P., Bošnjak, M., Rocktäschel, T., Riedel, S., and Grefenstette, E. Differentiable reasoning on large
10

---

Improving Soft Unification with Knowledge Graph Embedding Methods
knowledge bases and natural language, 2019. URL https: /ww.ivvvvvvv//////v///e/////avvv org/ abs/ 10824.
reasoning from text. In Inui, K., Jiang, J., Ng. V., and Wan, X. (eds.), Proceedings of the 2019 Conference Empir- ical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNL.-IJCNIPP) pp. 4506-4515, Hong Kong, China, November 2019. Association for Compu- tational Linguistics. doi: 10. 10.11865/1//D1/// httss//aacaaatthooogg... https://aaaatttannna https:
Minervini, P., Riedel, S., Stenetorp, P., Grefenstette, E., and Rocktäschel, T. Learning reasoning strategies in
end-to-end differentiable proving, 2020. URL https: //arxiv. org/ abs /207 0477.
URL
Nickel, M., Tresp, V., and Kriegel, H.-P. A three-way model for collective learning on multi-relational data. In Pro- ceedings of the 28th International Conference on Inter- national Conference on Machine Learning, ICML'11, pp. 809-816, Madison, WI, USA, 2011. Omnipress. ISBN 97814 1784450306195.
Touvron, H., Martin, L.,, Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C.,, Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, Fu, W., Fuller, B., Gao, C.,, Goswami, V., Goyal, N., Hartshom, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Moly- bog, I., Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, M., Subra- manian, R. Tan, E., Tang, B., Taylor, R., Williams, A., Kuan, J. X., Xu, P., Yan, Z., Zarov, I, Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Sto- jnic, R., Edunov, S., and Scialom, T. Llama 2: Open foundation and fine-tuned chat models, 2023. URL /ttps://arxivve wwwaxiiv.rg//aae. abs///asaaa// http://b/////0/// 2w00200029220
Rocktäschel, T. and Riedel, S. End-to-end differentiable proving. In Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 Decem- ber 2017, Long Beach, CA, USA, pp. 3791-3803, 2017. URL http:/ http:/ppppssss..s.com 6969 19699-en--ee
-indd-dife witeedaiffffaaaaleeeee..e. proving.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models, 2022. URL httpp:://axii..... abs/2112. 10752..
Trouillon, T., Welbl, J., Riedel, S., Éric Gaussier, and Bouchard, G. Complex embeddings for simple link prediction, 2016. URL https: /aaaaaxivvv... org. /errg/al org/abs/ 1606. 06357.
Ruffinelli, D., Broscheit, S., and Gemulla, R. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations, 2020. URL https: http///pppeee....eeeeeepe..e.eee net/ (tt.:rummidBxxxxiee
Wang. Z., Zhang, J., Feng. J., and Chen, Z. Knowledge graph embedding by translating hyperplanes. In Pro- ceedings of the Twenty-Eighth AAAI Conference on Artifi- cial Intelligence, AAAI'14, pp. 1112-1119. AAAI Press, 2014.
Safavi, T. and Koutra, D. CoDEx: A Comprehen- sive Knowledge Graph Completion Benchmark. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 8328-8350, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1/ 2020.emnlp- m69..669. URL htt.t: httpwwwwwww.b....///..////../..b org/anthology 2020. emnlp-main 669.
Xiao, H., Huang, M., Hao, Y., and Zhu, X. Transa: An adaptive approach for knowledge graph embedding, 2015. URL https: / arxiv. .rgg /abergg/////////e/ee//eeeeeeaaee abs/ /000 05490.
Yang, B., tau Yih, W., He, X., Gao, J., and Deng, I.. Embed- ding entities and relations for learning and inference in knowledge bases, 2015. URL abs /41//1122 12. 6575.
Schlichtkrull, M., Kipf. N., Bloem, P., van den Berg, R. Titov, I., and Welling, M. Modeling relational data with graph convolutional networks, 2017. URL https:
//arxiv. org/ abs//a/3/ 02..06610 06103.
Yang. F., Yang, Z., and Cohen, W. W. Differentiable learning of logical rules for knowledge base reasoning, 2017. URL https::/arset
SHENGYUAN, C., Cai, Y., Fang, H., Huang, X., and Sun, M. Differentiable neuro-symbolic reasoning on large- scale knowledge graphs. In Oh, A., Naumann, T., Glober- son, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, vol- ume 36, pp. 28139-2111 2-1--92-544 Curran Associates, Inc., 2023.
org/ abs /ttbs//110 111//10022.0 08367.
Yang, Z., Ishay, A., and Lee, Neurasp: Embracing neu- ral networks into answer set programming, 2023. URL https: /ttp//aaxivvv/v.////////e//aaaaa www.rwiwwwv.rr.o.oooooo.ooo wttp://www.o..//////...7777
Sinha, K., Sodhani, S., Dong, J., Pineau, J., and Hamilton, W. CLUTRR: diagnostic benchmark for inductive
Zhu, Z., Zhang, Z., Xhonneux, L.-P., and Tang, J. Neural bellman-ford networks: general graph neural network

---

Improving Soft Unification with Knowledge Graph Embedding Methods
framework for link prediction. Advances in Neural Infor- mation Processing Systems, 34, 2021.
Zhu, Z., Yuan, X., Galkin, M., Xhonneux, S., Zhang, M., Gazeau, M., and Tang, J. A*net: scalable path-based reasoning approach for knowledge graphs. 2023. URL https://arxiv wtgg/bs//20eeseem 04798.
12

---

Improving Soft Unification with Knowledge Graph Embedding Methods
A. Complexity Analysis
Below we provide complexity analysis for the baseline CTP and the proposed variants. We particularly focus on the final step each proof path during evaluation, since it the computational bottleneck in the NTP framework.
Notations:
Let
|8| be the number of entities
k be the number of top facts retrieved per (s, r, pair.
d be the embedding dimension.
N be the number of proof path templates.
D be the depth of the recursive proof tree.
Baseline CTP retrieves top-k facts for each combination of the missing entity and the known predicate-object/subjet pair, followed by the unification score calculation between two tensors of shape (JE), k. 3d). We break down the time complexity for retrieval and score calculation. Retrieval: we use the Index index from FAISS library (Johnson et al., 2019), which has linear complexity w.r.t. number items. Since we are retrieving for each entity combination, the complexity of retrieval is O((E)) for the final step at each proof path. Score calculation: we employ the Gaussian RBF kernel as the similarity metric between embeddings. The RBF kernel is defined as
[
3il
RBF(2;, U:)
exp(
20
which has approximately linear complexity w.r.t. number of entities
||] and dimension d, í.c. O(E) kd).
Since this has to be done at each individual proof path, the complexity becomes O(ND(1E) + [8] kd)).
CTP, adds the KGE objective only as a loss term. Therefore the evaluation complexity same as baseline CTP1, which O(ND(EE)) | kx)).
CTP₂ adds the KGE scoring function top of baseline CTP's existing similarity function (RBF kernel). The exact additional time complexity depends on the underlying KGE function. However, find the additional KGE scoring function is only necessary during training and can be omitted during evaluation time, the evaluation complexity is the same as baseline CTP,, which is O
ONN D(LE)² + (E)-d)).
CTP3 replaces retrievals with translational KGEs to directly compute the next unknown tail entity. This reduces the retrieval complexity from quadratic to linear w.r.t. [ Therefore the complexity becomes O(ND(E) + (E)
CTP: replaces the final ranking step from baseline CTP's retrieval + unification score calculation with direct ranking based on the KGE score. Assume a linear complexity for the KGE function w.r.t. number of entities (e.g. ComplEx), the overall complexity is further reduced to O(NDEE))
B. CTP1 vs. CTP2, gradient perspective
Below we analyze the advantage of CTP2 over CTP, from gradient perspective.
Let's first derive the gradient for CTP; and CTP2-
Recall the loss function for CTP: is defined as
LCTP = A)
[-ylog(KGE<((sTT.o)) - (1 (1-y) log(1 (GEo((s, r()) + AC ((s.roo) g
Σ
(3)
To simplify notation, we omit and summation in the following derivations. Let 0 denotes the learnable embeddings, ON and Φx denote the score function of KGE and the similarity metic of NTP, we can rewrite Eq. 3 as
13

---

Improving Soft Unification with Knowledge Graph Embedding Methods
LCTP, (0) log (0) - (1 log(1 ox(()) yog Øx (0) (1 y) log(1 ox (x))
Applying the chain rule, the gradient of L with respect to is
VOLCTP: = [- (N(
y/ 1 y
VONN(O) + [-
y1
1 1- y/
Voox(()
1 @0)
xx
1 - xx(x(f)
(4)
1-y y
y Vook(())
1-
ΦN @N((0) VOON (0) + 1 (N(()) VodN +
V (0)
1- 6x(0)
For CTP2, the score function a combination (assume X = b)) of KGE and original NTP's similarity score, write as
@camb (0) ②20(0)
Φ (0)
2
and the loss becomes
LCTP, (0) -y log Deumb (0) (1 y) log(1 Deamb (0)).
By the chain rule, its gradient is
dL( (CCcmb))
VeCCTP2
V gcombb
docomb
where
d.(
y
1 y
docomb
Ocomb
Doomh
The gradient for @camb (f) is therefore, the gradient for each individual score calculation in CTP2 is
eeccmb (0) Vo)N(0)+ Vo)k(())
dL( (CCcon))))
VeLciP;
Ve Deombb (8)
docomb
y
1- y
(VodN(0) + Vo)x(())
@oom (0)
Dcamb
y
VodN (0) +
(oox(() + 1 Pcomb (
1-
Vodi((0) +
1
VOOK (0).
@comb (f)
dcamb (
Dcamb (0)
By comparing the gradient for CTP1 (Eq. 4) and CTP2 (Eq. 5), see that CTP, 's gradient only involve "self" terms, e.g. (0) Vodw (f), where the gradients of KGE and NTP are separately computed and then added. On the other hand, Voek (f), which could potentially
CTP2's 's gradient involves 'cross' terms, such as (0m
y
VodN (0) and Poon (0)
provide a more coherent gradient update.
can further consider the above implication from a gradient variance perspective. Assume both dx and Φx are noisy estimates of an underlying true signal
( + eN, ox(()= EK.
with independent zero-mean terms 6N, < each with variance o², Assume further
V (O) Vodk = Vod.
14

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Define
1 - and g' 6² (1 (1-
1
(
1
Using first-order Taylor expansion, we can approximate
((σN(0)) ~ ((0) g')ee s(xx(0)) ~ x(0)+ (o)ek
The gradient for CTP1 becomes:
VOLCTT, ~ g(0) + +'())N Vo + (((0) + (())) Vorl
= = + (e()((eN Vooo
The noise term is with variance For CTP2, the combined score is
ACT, (o'oo=g(((eeeee) +
Var[AcTP,] (g'(0))² Var(EN + (g'(0))² -202
(6)
Ocomb + + EN + CK
2
Linearizing,
CN + CK
g (1/com)) ~ g(()) + (0))
2
Thus, the gradient for CTP2 becomes
VoLCTP, g(0)) +'())
EN + EK
VeG.
2
The noise term is
CN + cK ACI. g06
Voc.
2
with variance
Var[AcrP,] x (g'( 2 Var
ceN tCk
(b'(1))2 20 = (o'(1)) o²
2
2
By comparing Var[Acre and Var Carr, (Eq. 6 and Eq. 7), we can see the variance of the gradient noise for CTP2 is reduced by a factor w.r.t. CTP,'s 's. This reduction could also lead to smoother and more stable optimization dynamic, which is also what we observed empirically.
C. Dataset Information
We conduct experiments three small-scale link prediction datasets: Kinship, Nations and UMLS (Kemp et al., 2006), well as two large-scale Knowledge Graph (KG) datasets: FB122 (Guo et al., 201 and WN18RR (Dettmers et al., 2018). FB 122 is a subset of Freebase (Bollacker et al., 2007) containing facts of people, location and sports. Its test set is splitted into two subsets, Test-I and Test-II, where Test-I contains all triplets that cannot be derived by deductive logic inference, and Test-Il denotes all the rest triplets. WN18RR is derived from WordNet (WN18) (Miller, 1995), where test triplets that can be obtained by inverting triplets the training set are removed. Table 10 we summarize the statisties of these datasets.
15

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Dataset
[3]
[R]
# Train
# Validation
# Test
Kinship (Kemp al., 2006)
104
25
8544
1068
1074
Nations (Kemp al., 2006)
14
55
1592
199
201
UMLS (Kemp et al., 2006)
135
46
5,216
652
661
FB122 (Guo et al., 2016a)
9738
122
91,638
9595
11243
WN18RR (Dettmers et al., 2018)
40,943
11
86,835
3,034
3,134
Table 10. Dataset statistics Statistics of datasets used in this work. Columns: number of entities (E)), number of predicates (R)), number of training, validation, and test samples.
Kinship
Nations
UMLS
FB122
WNISRR
associated with(X. Y):-
process_of(X.Y)
term21(X.V) Yy:
treaties(X.)) Yy:-
contains(X.Y) Y):-
hypernym(X,
process. process_of(Y.2)
lerm24(YZ)
treaties(Y.X) (Y.X)
capitallY, X)
hypernym(X.X))
occurs_int jin(, YYy):
term4(X, Y):
aidenemy(X.3 Y):
language lunguage_spokent Eppoken(X Yy:-
verb verb_group(X, (X.upp(XXY):
issue in(X,Y),
(Y,))
milituryactions(.. lostterritoryXX. Yy-
official Janguage(X. placeJiveedXy Yy:-
verb (yrb.grou((YXX)
process (Y.Z)
term9(X,Y)
has hasspaa Y):
interconmects(X, Y):-
I(Y2)
timesincewar((.XX)
place of of birth(X.Y)
par_of((YX))
(X,Y), result.of (Y.Z)
Table 11. Visualization of learnt rules under each dataset with CTP2
D. Experimental Settings
Indexing Library. In this work the FAISS search index (Johnson et al., 2019). We use the GPU version of the library and use the IndexFlatl.2 index, which performs exact search using I.2.
Rule templates CTP defines a number of rule templates for the model to explore. The template is defined as number of steps - how many steps to hop from the head to the tail entity, and whether it is a reverse relation, indicated by r, i.c. stepping from tail to head entity. For example, rule = means the model will try to directly unify the goal with facts the KB. rule means two steps from the head to the tail entity, e.g. R(s, o) :- Ry (s, 2). R2(2, o). rule 1R means a reverse relation: R(s,0) o) Ri (o,s) s). For Kinship, Nations and UMLS we follow the setting in CTP with Kinship= Ir). Nations= 1omtons=0,,,, 1r). and UMLS= 2}. For FB122 and WNI8RR we both use {0, 1r).
we follow CTP (Minervini et al., 2020) on Kinship and UMLS datasets for all the top-k=4, batch batch_size=tt size=8, learning.rate-O.1. trained 100 epochs with Adagrad optimizer. For each triplets we sample 3 negative sample per entity (a total of 9 negative samples per triplet). For Nations we use sice=25 with AdamW optimizer for the CTP2 variant, and the same as CTP for the rest of models. For FB122 we mostly follow the setting from GNTP (Minervini al., 2019), with embedding saabedding-szee1100 siss==iize0.,. top-k=10, and I negative sample per entity. We Adagrad optimizer and train 100 epochs. We find it necessary to keep large number of retrieval (e.g. 128) for larger datasets such WNISRR. To avoid GPU OOM during evaluation due to the large matrix operation, we only scale number of retrievals during training, while keeping the number of retrievals during inference or evaluation low.
Training For dyper-parameet
experiments. Specifically, we use embedding size=50, embeddiingssze==50,
For baseline CTP we find freezing the model entities in the first 25 epochs work well, while for all our CTP variants we receive better results by not freezing the model from the beginning. We also explore different score aggregation operations for aggregating scores along one proof path (AND operation). For baseline CTP and CTP; we find the original min generally work well, while mcan and multiplication work better for CTP2, CTP3 and CTP3- besides, considered using cosine similarity as the scoring metric, with using addition instead of concatenation for obtaining the embedding for the whole triplets. However, we do not observe it to perform better than using the Gaussian kemne.
Incorporating KGE objectives To ensure KGE score lies within and we add a Sigmoid function to its negative score function. To avoid small negative scores being pushed to zeros after Sigmoid, we first subtract the mean from the negative scores.
16

---

Improving Soft Unification with Knowledge Graph Embedding Methods
CTP:
CTP2
Metries
CTP
CTP3
CTP,
À =
X = 0.5
À = 0.8
A = 0
= 0.5
À = 0.8
MRR
0.64
0.40
0.56
0.59
0.64
0.68
0.65
0.53
0.32
1
HIT@3 3
64.50
46.24
60.40
62.43
0.65
69,43
65.83
59.40
34.80
HIT@ 10
68.30
50.07
62.90
63.75
67.50
73.01
68.76
62.20
41.52
MRR
0.61
0,43
0,59
0,57
0.63
0.65
0.49
0,55
0.45
16
HIT@3
62.50
47.62
60.17
59,49
64.25
67.03
50.03
60.84
48.90
HIT@
65.71
51.43
62.49
61,84
65.79
69.25
53.81
61.53
41.09
MRR
0.56
0.43
0.58
0.48
0.63
0.62
0.46
0.54
0.59
HIT@3
57.26
50.86
58 98.94
49.72
64.70
64.50
49.31
59.58
60.46
HIT@ 10
59.94
53.67
60.12
51.88
66.02
67.62
53.18
63.84
62.62
MRR
0.61
128
HIT@3
61.10
HIT 10
67.40
Table 12. Test results FB122 with different number of negative samples n. Due to the computational limit, only evaluate CTP4
when n = 128. Bold denotes column-wise best results.
E. Training Dynamics
Validation Accuracy (MRR) training FB122
Training Loss
Nations
CTP
0,0
3.0
CT2
0.4
8.5
2.5
0.6
-.8
MRR
0.11
0.6
0.22
CTP
1.5
0.4
CTP
CTPp-ComplE.
200
Epochs
Figure 7. Training loss on Nations with CTP (left, blue) and CTP>-CoMPLEX (right) with different X.
Figure 8. Validation MRR FB122 dataset with baseline CTP and CTP2 with DISTMULT and COMPLEX as integrated KGEs.
In Figure we show training loss on Nations dataset given different X. For CTP: we find the training loss tends to be much more stable with smaller À as shown in Figure 2, which is as expected as the non-differentiable operations in CTP is smoothed out by the differentiable KGE loss calculation. On the other hand, the training loss for baseline CTP always fluctuating without decreasing, even though the final test accuracy reasonable.
In Figure show validation MRR during training FB 122 dataset for baseline CTP (blue), CTP2 with COMPLEX (green) and DISTMULT (orange). We can observe that both CTP₂ converges quickly in the first 20 epochs, with CTP2- COMPLEX slightly higher than CTP:-DDSTMULL, and both have much higher accuracy than the baseline CTP.
F. Visualization of learnt rules
Table 11 we show visualization results generated under each dataset under CTP2. We can see it successfully learns logical rules such as place_iivedX, Y): place of interconnects(X. Y);- re Y), (Y..), and contains(X., Y) capitallY, X).
G. Training NTPs with more negatives
Since KGEs, under the energy- based-model interpretation, require large amount of negative samples, we want to see if such can benefit the integration of NTPs and KGEs, given NTPs' number negative samples is default to In Table 12 we show results where we increase number of negative samples during training our CTP variants. Interestingly, instead of
17

---

Improving Soft Unification with Knowledge Graph Embedding Methods
receiving better accuracy, we observe a drastic performance drop on CTP, cTP1 when À 0.8 and CTP₂ with À 0.5 and A 0.8. For example, the MRR of CTP, with À 0.8 drops from 0.59 to 0.48 when number of negatives is increased from 1 to 32, and the MRR for CTP2 with À = 0.8 drops from 0.65 to 0.46. Reversely, when À = 0, CTP1 's MRR increases from 0.40 to 0.438 as number of negatives increases. This implies increasing the number of negatives helps when À is low, i.e. when the KGE loss is contributing more to the gradient updates. However, even when À = 0 for CTP1, recovering a pure KGE optimization process, the accuracy with n = 32 is still far less than when À = 0.5 and all other variants. This suggests that the regularization of KGEs on NTPs still limited, and we conjecture the bottleneck is the sparse gradient problem introduced during training. As we do not focus on sparse gradient problem in this work, we will leave it for future exploration. On the other hand, we notice drastic increase in accuracy with CTP, from 0.32 MRR to 0.61 with n. increases from to 128.
H. Details for Improving CTP3's 's Performance
In this section we discuss why CTP3's 's performance could be drastically lagging behind other variants especially on large datasets, and propose two approaches to improve its performance. Recall for CTP3 we replace top-k retrieval by using translational KGEs (e.g. TransB) directly compute the unknown entity, which means we are effectively doing top-1 retrieval. This results in two main drawbacks: 1. Limited expressiveness due to the top-1 retrieval. 2. Susceptible to spurious proof paths where subject and object are connected but logically irrelevant. For example, consider the path (s. bornjin, 01), (01, located in, 02). (02, notable. notable.people, o), where s and are connected but irrelevant. These issues become more obvious when the size and complexity of the dataset increase.
To mitigate the above issues, we additionally propose two methods.
Filtering spurious relation paths. We consider using the Path Constraint Resource Allocation (PCRA) for calculating the path reliability by measuring how much resource flows from the head to the tail entity following a path, as inspired by PTransE (Lin et al., 2015).
Formally, for pair of and and path (r1, ................................ Tr). the flow path can be written as = S1 3 "ny Sn where S; are sets of entities, and E Sn, Following the notation in PTransF, given any entity m E St, the resource flowing to m is defined as
Rp(m)=
Σ (-.m
(5 -) Rp(n),
where Si-1(;, m) are its direct predecessors in S3-1, and (n,,,) -) is the direct successors of n E S;-1. By calculating (m) recursively from o, we can obtain the final resource (reliability) of the path p given and o. For more details please refer (Lin et al., 2015). During training, we then mask out the path with lowest 10% reliability score (we do not modify for evaluation stage).
Learnable entity expansion module. To alleviate the issue with top-1 retrieval, we consider adding an additional learnable module which expands the resulting entity embedding obtained from the translational KGE function to h neighboring entities. other words, we learn a linear layer W with shape (d, k) to encode a set of related entities {St}x given the calculated entity s. i.e. pusS W).
In Table 9 we show the results for incorporating PCRA and entity expansion module for CTP3. We can observe noticeable improvements, especially on larger datasets such as WNI&RR.
I. Settings for Inference speed Comparison (Table 3)
We run inference on the selected models on a V100 GPU with batch size of 8, embedding dimension 1000 for each KGE method (default), and CTP2 with dimension 100, and NBFNet with dimension=32.
18

---

Improving Soft Unification with Knowledge Graph Embedding Methods
J. Pseudo-code implementation
Neural Theorem Prover implements backward chaining algorithm by recursively instantiating AND/OR modules, where is called to prove each goal by unifying with each rule head in the KB. Then, the AND module is called to prove the rule body, where for each atom in the body the recursively called, until the algorithm reaches depth limit d. The pseudo-code for NTP can be found in 1.
K. Conditional Theorem Prover
Conditional Theorem Prover extends upon NTP by incorporating a trainable neural module for predicting plausible rules given goals. The pseudo-code for CTP can be found in 2.
Algorithm Python pseudo-code for NTP with top-k retrieval following implementation from (Minervini et al., 2019)
# KB: the Knowledge Base.
proof state
score: unification score
subs:
substitution
# sim: similarity function for unification topk: function that performs top-k retrieval
def or (goal, 8, k):
list [] for rule in xB:
head, body rule topk_ind
KB)
if max depth and no cy. rule):
8 head unify (head, goal, 5, todk_ind)
(goal, s_head)
S. body and (body, 6,
S s_list.appel aS
return #xoof_states
def and (goal, S):
S. list []
if len (goal)
list [S]
elif max depth:
goal, sub_goals goal
new goal substitute (goal, subs)
for new in or (new goal, 5, d+1):
S l_sts. appeed (and (end (eub_ggaals,___ S_new)
return list
unify (atom, goal, topk_ind)
grounded atom, groundad goal = [], []
for tatom_term goal_ttell term) in zip (atom, goal):
if is variable (atom. aatom_term).
if update (aattee((atomeeeee term: goal_term term) s.auba elif is variable (ooal_tggoalaeraaa term):
s.subs:
if grounded (atom_ term) and
goal, term not in s.subs:
s.subs (gdat term: stom_term
grounded (atom term)
is grounded grounded_ atom, (atom term) grounded goal. (gpal term)
(goal (g term):
acore sim (grounded goal, grounded (tcom(topk_in) [nd])
score min (S, score, score)
19

---

Improving Soft Unification with Knowledge Graph Embedding Methods
Algorithm 2 Simplified Python pseudo-code for CTP following (Minervini al., 2020)
KB: the Knowledge Base.
sim: similarity function unification topk: a function that performs top-k retrieval depth: maximum recursive depth
def cs, I, max_depth):
max depth
return (n, I, o) else:
for range (max (max_depth):
level None for rule_path templatse
path None
step_ind, transtrrm in rule_path:
is inverse relation:
latent score, =
st,p 8, max dex_hepth 1)
else:
latent score, = step (8, o, max_hepth 1)
path_ None: path_score latent_scoore
else:
aggregation all proofs need to hold.
path score = min(path_scoke score, latent_scomt
step_in ind len path) choose the max over the topk branches path_score.
max(path_score dim=-1)
if level score is None:
level_score path_score
else:
max aggregation
only proof path needs to hold.
level score max score, path_scord score)
if None:
score score
olse:
aggregation
only proof path
hold.
score max (score, level_score) score)
unify o=Nne)
if is not None: else:
ind top,([s,
topk ind top z]) [t(ook__idd] [-1]
score sim([s, o], KB[topk_ind) ind])
return
20


Reviews:
[{"review_id": "B3IyD3yikg", "reviewer": "Reviewer_Bi1c", "summary": "This paper investigates the integration of Neural Theorem Provers (NTPs) and Knowledge Graph Embeddings (KGEs) to enhance soft unification and reasoning efficiency. The paper systematically explores four strategies for integrating KGEs into NTPs:\nCTP1: Uses KGE as an auxiliary loss to support NTP training.\nCTP2: Injects KGE-based similarity scores score function into NTPs as an auxiliary score.\nCTP3: Replaces the topk retrieval with a translation-based operation to improve inference efficiency.\nCTP4: Replaces the final step of NTP’s proof evaluation with KGE-based ranking to  reduce computational overhead.\n\nThe paper demonstrates that these integrations can substantially improve NTPs in both accuracy and computational efficiency. Additionally, the paper provides detailed ablation studies. This work is the first systematic study of KGE integration into NTPs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ***Complexity Analysis:***\n\nBelow we provide complexity analysis for the baseline CTP and the proposed variants. We particularly focus on the final step at each proof path during evaluation, since it is the computational bottleneck in the NTP framework. \n\nLet $|\\mathcal{E}|$ be the number of entities, $k$ be the number of top facts retrieved per $(s, r,t)$ pair, $d$ be the embedding dimension, $N$ be the number of proof path templates, $D$ be the depth of the recursive proof tree.\n\n**Baseline CTP** retrieves top-k facts for each combination of the missing entity and the known predicate-object/subject pair, followed by the unification score calculation between two tensors of shape $(|\\mathcal{E}|, k, 3d)$. **Retrieval:** we use the IndexFlatL2 index from FAISS library, which has linear complexity $w.r.t.$ number of items. Since we are retrieving for each entity combination, the complexity of retrieval is $O(|\\mathcal{E}|^2)$ for the final step at each proof path. **Score calculation:** we employ the Gaussian RBF kernel as the similarity metric between two embeddings. The RBF kernel is defined as \n\n\\begin{equation}\\text{RBF}(x_i, y_i) = \\exp\\big(-\\frac{||x_i-y_i||^2}{2\\sigma^2}\\big),\\end{equation} which has approximately linear complexity $w.r.t.$ number of entities $|\\mathcal{E}|$ and dimension $d$, $i.e.$ $O(|\\mathcal{E}| \\cdot kd)$.\n\nSince this has to be done at each individual proof path, the complexity becomes $O(ND(\\mathcal{|E|}^2 + \\mathcal{|E|} \\cdot kd))$.\n\n**$\\textbf{CTP}_1$** adds the KGE objective only as a loss term. Therefore the evaluation complexity is the same as baseline $\\text{CTP}_1$, which is $O(ND(\\mathcal{|E|}^2 + \\mathcal{|E|} \\cdot kd))$.\n\n**$\\textbf{CTP}_2$** adds the KGE scoring function on top of baseline CTP's existing similarity function (RBF kernel). However, as we find the additional KGE scoring function is only necessary during training and can be omitted during evaluation time, the evaluation complexity is the same as baseline $\\text{CTP}_1$.\n\n**$\\textbf{CTP}_3$** replaces retrievals with translational KGEs to directly compute the next unknown tail entity. This reduces the retrieval complexity from quadratic to linear $w.r.t. \\mathcal{|E|}$. Therefore the complexity becomes $O(ND(\\mathcal{|E|} + \\mathcal{|E|} \\cdot kd))$.\n\n**$\\textbf{CTP}_4$** replaces the final ranking step from baseline CTP's retrieval & unification score calculation with direct ranking based on the KGE score. Assume a linear complexity for the KGE function $w.r.t.$ number of entities ($e.g.$ ComplEx), the overall complexity is further reduced to $O(ND(\\mathcal{|E|})$.\n\n> ***1.Theoretical analysis for why CTP2 is better***\n\nWe provide a theoretical analysis from the gradient perspective comparing CTP2 to CTP1 (since they are similar to each other compared to CTP3-4). Due to space limit, we kindly ask the reviewer to refer to the section named **Theoretical justification CTP1 vs. CTP2.** in our reply to Reviewer ck5p. We are only able to show essential steps in the derivation here, but we will add the full derivation to our manuscript.\n\n> ***2.why using similarity-based KGEs can achieve better performance***\n\nWe conjecture the score function of similarity-based KGEs align better with the similarity metric (RBF Kernel) used in NTP, as compared to translational KGEs, which use the negative distance between original and translated entity embedding as the score. \n\nSpecifically, similarity-based KGEs like ComplEx or DistMult generally use an inner product (or bilinear form) $\\langle \\cdot, \\cdot \\rangle$ to score triplets: \n\n$$s_{\\text{sim}} (s,r,o) = \\langle (s,r), o \\rangle,$$\n\nwhile translational-based KGEs (such as TransE) use the distance as metric\n\n$$s_{\\text{transE}} = -||s+r-o||.$$\n\nOn the other hand, since RBF kernel is defined as \n\n$$\\text{RBF}(x, y) = \\exp\\big(-\\frac{||x-y||^2}{2\\sigma^2}\\big).$$ \n\nFor simplification, assume the embeddings are normalized, we have \n\n$$||x-y||^2 \\approx 2 - 2\\langle x, y \\rangle,$$\n\ntherefore \n\n$$\\text{RBF}(x_i, y_i) = \\exp\\big(-\\frac{1 - \\langle x , y \\rangle}{\\sigma^2}\\big).$$ \n\nThis means RBF kernel is essentially a monotonic function of the inner product $\\langle x, y \\rangle$, and therefore the gradient of the similarity-based KGE score is directly tied to inner product-based KGEs ($e.g.$ ComplEx and DistMult). In experiments, we also observe faster convergence and higher accuracy when using ComplEx and DistMult. \n\n> ***Other Comments: bolding and capitalization errors***\n\nThank you for pointing them out! We will correct them in our final manuscript.", "claims_and_evidence": "The paper makes several key claims, including:\n1. Leveraging the properties of KGEs can drastically improve the inference and evaluation efficiency of NTPs. The paper reports that CTP2 achieves higher accuracy than existing NTP-based methods on multiple datasets, including FB122, Nations, and UMLS.\n\n2. CTP3 and CTP4 significantly improve computational efficiency. This claim is well supported by experiments. The paper provides empirical runtime comparisons, demonstrating substantial speed improvements. However, a formal complexity analysis is missing.\n\n3. This is the first systematic study of integrating KGE into NTP. The paper “End-to-End Differentiable Proving” has proposed the method that integrates KGEs into NTPs, but this paper is the first systematic study for the integration of KGEs into NTPs.", "methods_and_evaluation_criteria": "Methods: The proposed methods which integrate KGEs with NTPs through different distinct strategies (CTP1–CTP4)—are well-motivated by the limitations of NTPs, such as the poorly  structured embedding space. The integration choices are reasonable, as they directly address these issues by leveraging KGE’s structured representation learning. However, a more formal theoretical justification for why CTP2 work better than others is missing.\n\nEvaluation Criteria: \nThe evaluation is conducted on standard knowledge graph reasoning benchmarks, including FB122, WN18RR, Nations, UMLS, Kinship, CLUTRR. These datasets are appropriate choices for evaluating reasoning tasks. The paper evaluates performance using standard metrics: Mean Reciprocal Rank (MRR) and Hits@m, which are widely used for knowledge graph completion tasks.", "theoretical_claims": "The paper does not provide formal theoretical proofs regarding the correctness of the proposed methods. The paper relies on experimental evidence to support its claims.", "experimental_designs_or_analyses": "The experimental using multiple benchmark datasets and standard metrics, including comparisons with baselines, efficiency evaluation, visualization, hyperparameter analysis and effect of using different KGEs. The experimental design is generally sound, lacks theoretical analysis for performance differences. In addition, there appears to be an error in the bolding of values in Table 2. For the HITS@10 metric on UMLS, the best result should be CTP1 rather than CTP2.", "relation_to_broader_scientific_literature": "This paper is the first systematic study for the integration of KGEs into NTPs and propose four integration strategies, improving both performance and efficiency. Using KGE as auxiliary was originally proposed in “End-to-End Differentiable Proving”, but it was only briefly mentioned without any further exploration, and is not used in any subsequent NTPs. Compared with NTPs: NTP, GNTP, CTP, and link predictors: ComplEx, DistMult, NEURALLP, MINERVA, DIFFLOGIC, LERP and GNN NBFNET, the method proposed in this paper achieved better results in most cases.", "essential_references_not_discussed": "To the best of my knowledge, the paper discusses the most relevant prior work, and I did not identify essential references that are missing.", "other_strengths_and_weaknesses": "Strengths：\n1. The paper is well-written and clearly structured, making the key contributions and technical details easy to follow. The motivation for integrating KGE with NTPs is well-explained.\n2. The authors have conducted comprehensive experiments, including comparisons with baselines, efficiency evaluation, visualization, hyperparameter analysis and effect of using different KGEs.\n\nWeaknesses:\n1. There is no theoretical analysis for performance differences. Specifically, the experimental results indicate that CTP2 achieves the best performance, but the paper does not explicitly discuss why CTP2 can achieve the best performance? Can it be theoretically explained?\n2. The “Effect of using different KGEs” part of experimental results indicate that similarity-based KGEs, ComplEx DistMult generally yields the best performance, whereas translation-based KGE TransE and RotatE often lag back by a large margin. The paper lacks an explanation for this phenomenon. Would it be possible to further analyze why using similarity-based KGEs can achieve better performance?", "other_comments_or_suggestions": "1. There appears to be an error in the bolding of values in Table 2. For the HITS@10 metric on UMLS, the best result should be CTP1 rather than CTP2.\n2. The capitalization of model names such as ComplEx and RotatE is inconsistent in the paper. For example, \"COMPLEX\" and \"ComplEx\" are both used.", "questions_for_authors": "Please see the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5fuI1kWVG1", "reviewer": "Reviewer_8H6v", "summary": "The paper proposes to integrate Knowledge Graph Embedding (KGE) methods with Neural Theorem Provers (NTPs) to enhance neuro-symbolic reasonings, and hence. The author proposes 4 ways to use KGEs and explain the methodology, the most intuitive variant seems to be use the kge at each proof step. Then the paper uses extensive experiments to show the performance of newly proposed methodology in different datasets, the ablation studies is also provided.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ***The paper is dense with technical details as one can observe the paper uses a lot of spaces to talk about existing research and methods, make it less accessible to readers not familiar with the specific fields of NTPs or KGEs. In contrast, the newly proposed CTP may require more room for further illustrations.***\n\nThank you for your advice. We will incorporate more description on CTP and modify the introduction/method section to be easier to follow.\n\n> ***The improvement of the method seems to be marginal, as the CTP generally falls behind previous methods like NBF-net, though the paper has argued it has stronger efficiency.***\n\nFirst, out of the seven Knowledge Graph Completion datasets tested, we are only slightly behind NBFNet for 2 of them (Kinship and WN18RR). While CTP2 lags behind NBFNet on Kinship for 0.09 MRR, we note that Kinship is a special case where CTP2 has little effect as the dataset has little multi-hop proof paths, yet for CTP2 we specifically add KGE priors along the proof path. In addition, we show that CTP2 clearly outperforms NBFNet and all the other baselines on Cluttr dataset (Table 4). \n\nSecond, we show that by incorporating KGE priors, we can achieve consistent performance improvement across most if not all (excluding Kinship) datasets (CTP2), without introducing any new parameters and with negligible additional computational overhead. While the improvements of CTP2 over baseline CTP on small statistical learning datasets (e.g. Nations, UMLS) are less significant (since the baseline CTP’s accuracy on these datasets is already relatively high). The improvement becomes much more obvious on WN18RR and CodEx, with an improvement on MRR of 0.07 and 0.16, respectively. \n\nLastly, NBFNet has been a SOTA KGC method, and many more recent KBC works’ performances also do not surpass it (e.g. DiffLogic, LERP). \n\n> ***I recommend adding more grounded examples for illustrations at the start of the paper instead of just Figure 1.***\n\nThank you for the suggestion! We will modify the manuscript to incorporate a grounded CTP inference illustration.\n\n> ***Why NBFNet is not included in Table 5.***\n\nThank you for the question. We initially tried to run NBFNet on FB122 with various hyperparameters but the accuracy was all low compared to its performance on other datasets and we were uncertain if we missed something, therefore we did not include it. \n\nBelow we show results on FB122 with NBFNet included. Additionally, we rerun Table 5 with larger retrieval size ($k=128$). This was done on WN18RR and CodEx datasets (L648-653) but not FB122 because the baseline GNTP was run on FB122 with $k=10$, and we want to draw a fair comparison with it. Due to space limit, we are only showing the Test-ALL split of FB122.\n\n||| H@3  | H@5  | H@10 | MRR  |\n|-|----------------------|------|------|------|------|\n|With Rules||||||\n|| KALE-P               | 61.2 | 66.4 | 72.8 | 0.52 |\n|| KALE-J               | 70.7 | 73.1 | 75.2 | 0.67 |\n|| ASR-D                | 71.7 | 73.6 | 75.7 | 0.67 |\n|| KBLRN                | 74.0 | 77.0 | 79.7 | 0.70 |\n|Without Rules||||||\n|| TransE               | 58.9 | 64.2 | 70.2 | 0.48 |\n|| DistMult             | 67.4 | 70.2 | 72.9 | 0.63 |\n|| ComplEx            | 67.3 | 69.5 | 0.72 | 0.64 |\n|| GNTP                 | 61.5 | 63.2 | 64.5 | 0.61 |\n|| CTP                  | 69.1 | 70.5 | 71.2 | 0.68 |\n|| NBFNet             | 57.2 | 59.6 | 70.6 | 0.51 |\n|||||||\n|| CTP₁                 | 65.4 | 64.3 | 65.0 | 0.62 |\n|| CTP₂                 | **76.1** | **76.4**| **78.3** | **0.75** |\n|| CTP₃                 | 59.4 | 60.8 | 62.2 | 0.53 |\n|| CTP₄                 | 65.7 | 66.3 | 69.6 | 0.64 |\n\nAs we can see, CTP2 achieves the best accuracy overall. NBFNet's accuracy, however, is significantly lower. Due to time limit we are not able to further search for hyperparameters as it takes more than a day to train NBFNet on FB122 with a V100 GPU. However we will keep experimenting and will update in the followup reply if we find better accuracy with NBFNet.\n\n> ***Replies to other reviewers***\n\nHere we would like to refer to some questions from other reviewers and our replies that could potentially be of your interest. \n\n**Theoretical justification of why CTP2 is better.** We provide a theoretical justification for the better performance of CTP2 over CTP1 under the *Theoretical justification CTP1 vs. CTP2.* section under our reply for Reviewer ck5p.\n\n**Explanation on why similarity-based KGEs perform better than translational KGEs on NTPs.** Please refer to the section named *why using similarity-based KGEs can achieve better performance* in our reply to Reviewer Bi1c.\n\n**Explanation on why CTP3-4's accuracy drop sharply on large-scale dataset, and methods of improvement.** Please see our reply to Reviewer H1qZ, section *The reasons for the accuracy drop in CTP3 and CTP4 on large-scale datasets, and propose corresponding improvements*.", "claims_and_evidence": "Generally speaking, the paper provides empirical results as evidence for their claims.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "This paper has no proofs.", "experimental_designs_or_analyses": "I think it's valid.", "relation_to_broader_scientific_literature": "The paper studies Neural Theorem Provers.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths\n\n1.\tThe approach to integrate KGEs to improve the NTPs is novel and reasonable for advancing the capabilities of neuro-symbolic systems. The four variants of CTPs shows the paper also offers detailed analysis on how to utilize the KGEs.\n\n2.\tThe paper provides extensive experimental results that not only compare them against a variety of benchmarks but also includes ablation study and case-study for detailed discussion of the empirical results.\n\nWeaknesses\n\n1.\tThe paper is dense with technical details as one can observe the paper uses a lot of spaces to talk about existing research and methods, make it less accessible to readers not familiar with the specific fields of NTPs or KGEs. In contrast, the newly proposed CTP may require more room for further illustrations.\n\n2.\tThe improvement of the method seems to be marginal, as the CTP generally falls behind previous methods like NBF-net, though the paper has argued it has stronger efficiency.", "other_comments_or_suggestions": "I recommend adding more grounded examples for illustrations at the start of the paper instead of just Figure 1.", "questions_for_authors": "Why NBFNet is not included in Table 5.\n\n\nThanks author, I have read your response and changed my ratings corrspondingly.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d6bjUjx8r1", "reviewer": "Reviewer_H1qZ", "summary": "This paper proposes integrating Knowledge Graph Embedding methods into Neural Theorem Provers to address challenges in optimization and efficiency.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ***The reasons for the accuracy drop in CTP3 and CTP4 on large-scale datasets, and propose corresponding improvements***\n\nFor CTP3, we recognize two issues that limits its performance particularly on large-scale dastasets, and propose two approaches to improve its performance. Recall for CTP3 we replace top-$k$ retrieval by using translational KGEs ($e.g.$ TransE) to directly compute the unknown entity, which means we are effectively doing top-1 retrieval. This results in two main drawbacks: 1. Limited expressiveness due to the top-1 retrieval. 2. Susceptible to spurious proof paths where subject and object are connected but logically irrelevant. For example, consider the path $(s, born\\_in, o_1)$, $(o_1, located\\_in, o_2)$, $(o_2, notable\\_people, o)$, where $s$ and $o$ are connected but irrelevant. These issues become more obvious when the size and complexity of the dataset increase.\n\nTo mitigate the above issues, we additionally propose two methods.\n\n**Filtering spurious relation paths.** We consider using the Path Constraint Resource Allocation (PCRA) for calculating the path reliability by measuring how much resource flows from the head to the tail entity following a path, as inspired by PTransE [1]. \n\nFormally, for a pair of $s$ and $o$ and a path $p = (r_1, r_2, \\dots, r_n)$, the flow path can be written as $s \\xrightarrow{r_1} S_1 \\xrightarrow{r_2} \\dots \\xrightarrow{r_n} S_n$, where $S_i$ are sets of entities, and $o \\in S_n$. Following the notation in PTransE, given any entity $m \\in S_i$, the resource flowing to $m$ is defined as\n\n$$R_p(m) = \\sum_{n \\in S_{i-1}(\\cdot, m)} \\frac{1}{|S_i(n, \\cdot)|}R_p(n),$$\n\nwhere $S_{i-1}(\\cdot,m)$ are its direct predecessors in $S_{i-1}$, and $S_i(n, \\cdot)$ is the direct successors of $n \\in S_{i-1}$. By calculating $R_p(m)$ recursively from $s$ to $o$, we can obtain the final resource (reliability) of the path $p$ given $s$ and $o$. For more details please refer to~\\cite{ptranse}. During training, we then mask out the path with lowest 10\\% reliability score (we do not modify for evaluation stage). \n\n**Learnable entity expansion module.** To alleviate the issue with top-1 retrieval, we consider adding an additional learnable module which expands the resulting entity embedding obtained from the translational KGE function to $k$ neighboring entities. In other words, we learn a  linear layer $\\mathbf{W}$ with shape $(d, k)$ to encode a set of related entities $\\\\{S\\\\}_k$ given the calculated entity $s$, $i.e.$ $p(\\\\{S\\\\}_k|s, \\mathbf{W})$. \n\nIn the table below we show the results for incorporating PCRA and Entity Expansion (EE) module with $k=10$ for CTP3. We can observe noticeable improvements, especially on larger datasets such as FB122 and WN18RR. \n\n||UMLS|Kinship|Nations|FB122|WN18RR|Codex-s|\n|-|-|-|-|-|-|-|\n|MRR |0.65|0.5|0.53|0.53|0.37|0.35|\n|w/ PCRA|0.66|0.50|0.54|0.55|0.39|0.38|\n|w/ EE|0.67|0.52|0.54|0.60|0.41|0.42|\n|w/ both|0.67|0.52|0.55|0.63|0.42|0.44|\n\nFor CTP4 the performance drop on larger dataset is mainly because of lack of negative samples during CTP training. Since in CTP4 we utilize KGE to rank entities, we rely heavily on the quality of the conditional probability $p(s,r|o)$ learned through the KGE function. This is discussed in Section A.5 and Table 11 of the appendix. We show that by increasing the number of negative samples, we can dramatically improve the performance of CTP4 to be close to CTP (<0.01 difference on HITS@10 on FB122) despite being 1000x faster during evaluation. \n\n[1] Modeling Relation Paths for Representation Learning of Knowledge Bases, ACL 2015\n> ***Conduct a thorough analysis of why different KGE methods perform variably in CTP3 and CTP4***\n\nWe provide an explanation on why similarity-based KGE methods work better with NTPs than translational KGEs because of the better alignment in their score function. Due to space limit, please refer to the section named *2.why using similarity-based KGEs can achieve better performance* in our reply to Reviewer Bi1c.\n\nAdditionally, we provide a theoretical justification for the better performance of CTP2 over CTP1 under the *Theoretical justification CTP1 vs. CTP2.* section under our reply for Reviewer ck5p.\n\n> ***Include a comparative analysis with multi-modal knowledge graph reasoning methods. How do you view the relationship between this paper's approach and multi-modal knowledge graph reasoning methods?***\n\nWe would like to clarify that we mentioned multi-modal KG reasoning in the introduction because it is one of our main motivations to study NTP and is our on-going research, yet it is **not** the focus in this work. Therefore, we feel it might be less coherent to conduct analysis regarding multi-modal KG reasoning in this work. \n\nHowever, since our proposed integration (in particular, CTP2) is a plug-and-play approach without introducing new parameters or significantly modifying model architecture, we believe it should be agnostic to the original modality behind the embedding.", "claims_and_evidence": "The claims made in the paper are well-supported by evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand.", "theoretical_claims": "The paper does not present theoretical claims that require verification. Its primary contribution lies in proposing a practical framework for integrating KGE methods with NTPs, rather than theoretical innovation. Therefore, this section is not applicable.", "experimental_designs_or_analyses": "The authors provided detailed descriptions of their experimental designs, including dataset selection, model implementation, and hyperparameter tuning. The results comprehensively demonstrate the performance differences among various methods.", "relation_to_broader_scientific_literature": "The authors mention most related work.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. The paper proposes an innovative framework for integrating KGE methods with NTPs to address the optimization challenges of NTPs.\n\n2. The experimental results demonstrate the effectiveness and applicability of the proposed methods across multiple datasets.\n\n\nWeaknesses:\n1. The reasons for the accuracy drop in CTP3 and CTP4 on large-scale datasets were not thoroughly analyzed.\n\n2. The relationship with emerging multi-modal knowledge graph reasoning methods was not fully discussed, potentially limiting the understanding of the paper's innovation and limitations.", "other_comments_or_suggestions": "1. Conduct a thorough analysis of why different KGE methods perform variably in CTP3 and CTP4, and propose corresponding improvements.\n\n2. Include a comparative analysis with multi-modal knowledge graph reasoning methods to further highlight the innovations and advantages of the proposed approach.", "questions_for_authors": "1. What are the main reasons for the significant performance differences of different KGE methods in CTP3 and CTP4?\n\n2. How do you view the relationship between this paper's approach and multi-modal knowledge graph reasoning methods? Is there potential for further integration?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IR4ZxoRoNq", "reviewer": "Reviewer_ck5p", "summary": "This paper presents the first integration of NTP and KGE, aiming to enhance the performance of NTP in terms of both effectiveness and efficiency. The experimental results demonstrate the synergy between these two lines of research.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ***1. In the Introduction ... raises the question of whether this approach is suitable for such domains.***\n\nThank you for your insights! While LLMs also transform discrete symbols to continuous space, the difference is NeSy approaches incorporate more explicit reasoning priors in their framework (e.g. backward chaining algorithm for NTPs), as compared to the generic next-token-prediction in LLMs. These structural priors allow NeSy models to have less hallucination and better interpretability (as one can trace the proof paths and localize errors).\n> ***2. The connection between NTP and KGE could be better introduced / include works of inductive KGE/KGFMs on unseen relations***\n\nWe will revise our manuscript to incorporate more corresponding details. Also, just to clarify, in this work we do not focus on inductive KGC, and hence we did not include these works initially.\n\n> ***More explanation of the 'sparse gradient perspective'***\n\nWe will rewrite the introduction to add more explanations.\n> ***3. potential reasons behind the observed improvements***\n\n**Improved Embedding space.** First, we empirically find integrating KGE (paricularly CTP2) can notably improve the structureness of NTP embedding space. This is discussed throughout the paper.\n\n**Explanation of why similarity-based KGEs work better with NTPs than translational-based KGEs.** Please refer to section *2.why using similarity-based KGEs can achieve better performance* in our reply to Reviewer Bi1c.\n\n**Theoretical justification CTP1 vs. CTP2.** We provide a theoretical justification from a gradient perspective of why CTP2 performs better than CTP1 (as CTP2 is different from CTP3 and CTP4 and mostly similar to CTP1). Due to space limit, we are only able to show essential steps.\n\nLet $\\theta$ denotes the learnable embeddings, $\\phi_N$ and $\\phi_K$ denote the score function of KGE and CTP, the loss for CTP1 is\n$$\\mathcal{L_1}(\\theta) = -y \\log \\phi_N(\\theta) - (1-y) \\log(1-\\phi_N(\\theta)) - y \\log \\phi_K(\\theta) - (1-y) \\log (1-\\phi_K(\\theta)).$$\nApplying the chain rule, the gradient of $\\mathcal{L_1} \\ \\text{with respect to} \\  \\theta$  is \n$$\\nabla_\\theta \\mathcal{L_1} = \\left[-\\frac{y}{\\phi_N(\\theta)} + \\frac{1-y}{1-\\phi_N(\\theta)}\\right] \\nabla_\\theta \\phi_N(\\theta) + \\left[-\\frac{y}{\\phi_K(\\theta)} + \\frac{1-y}{1-\\phi_K(\\theta)}\\right] \\nabla_\\theta \\phi_K(\\theta).\\quad(1)$$\nFor CTP2, the score function is a combination (assume $\\lambda = \\frac{1}{2}$) of KGE and original NTP's similarity score, write as \n$$\\phi_2(\\theta) = \\frac{\\phi_N(\\theta) +  \\phi_K(\\theta)}{2}, $$\nand the loss becomes \n$$\\mathcal{L_2}(\\theta) = -y\\log\\phi_2(\\theta)-(1-y)\\log(1 -\\phi_2(\\theta)).$$\nthe gradient for each individual score calculation in CTP2 is\n$$\\nabla_\\theta \\mathcal{L_2}=\\left[-\\frac{y}{\\phi_2(\\theta)} + \\frac{1-y}{1-\\phi_2(\\theta)}\\right] \\cdot(\\nabla_\\theta \\phi_N(\\theta) + \\nabla_\\theta \\phi_K(\\theta))\\quad(2)$$\nBy comparing Eq.1 and Eq.2 we can see that CTP1's gradient only involve \"self\" terms, where the gradients of KGE and NTP are separately computed and then added. On the other hand, CTP2's gradient involves `cross' terms, such as $-\\frac{y}{\\phi_2(\\theta)} \\cdot \\nabla_\\theta \\phi_N(\\theta)$, which could potentially provide a more coherent gradient update. \n\nFurther, assume both $\\phi_{N}$ and $\\phi_{K}$ are noisy estimates of an underlying true signal $$\\phi_N(\\theta) = \\phi + \\epsilon_N, \\quad \\phi_K(\\theta) = \\phi + \\epsilon_K,$$ with independent zero-mean terms $ \\epsilon_N, \\epsilon_K $ each with variance $\\sigma^2$. Assume \n$$\\nabla_\\theta \\phi_N(\\theta) \\approx \\nabla_\\theta \\phi_K(\\theta) \\equiv \\nabla_\\theta \\phi.$$\nDefine $$g(\\phi) = -\\frac{y}{\\phi} + \\frac{1-y}{1-\\phi} \\quad \\text{and} \\quad g'(\\phi) = \\frac{y}{\\phi^2} + \\frac{1-y}{(1-\\phi)^2}.$$\nUsing a first-order Taylor expansion, we can approximate$$g\\bigl(\\phi_N(\\theta)\\bigr) \\approx g(\\phi) + g'(\\phi) \\epsilon_N, \\quad g\\bigl(\\phi_K(\\theta)\\bigr) \\approx g(\\phi) + g'(\\phi) \\epsilon_K. $$ The gradient for CTP1 becomes:\n$$\\nabla_\\theta \\mathcal{L_1}\\approx 2g(\\phi)\\nabla_\\theta \\phi+g'(\\phi)(\\epsilon_N+\\epsilon_K)\\nabla_\\theta\\phi.$$\nThe noise term is $\\Delta_1 = g'(\\phi)(\\epsilon_N+\\epsilon_K) \\nabla_\\theta \\phi,$ with variance\n$$\\operatorname{Var}[\\Delta_1] \\propto \\left(g'(\\phi)\\right)^2\\operatorname{Var}(\\epsilon_N+\\epsilon_K) = \\left(g'(\\phi)\\right)^2 \\cdot 2\\sigma^2.\\quad(3)$$\nSimilarly, for CTP2, the noise term is\n$$\\Delta_2 = g'(\\phi)\\frac{\\epsilon_N+\\epsilon_K}{2} \\nabla_\\theta \\phi, $$\nwith variance\n$$\\operatorname{Var}[\\Delta_2] \\propto \\left(g'(\\phi)\\right)^2\\operatorname{Var}\\left(\\frac{\\epsilon_N+\\epsilon_K}{2}\\right) = \\left(g'(\\phi)\\right)^2\\frac{1}{4}\\cdot 2\\sigma^2 = \\left(g'(\\phi)\\right)^2\\frac{\\sigma^2}{2}.\\quad(4)$$\nBy comparing Eq.3 and Eq.4 we can see the noise variance for CTP2 is reduced by a factor of 4 compared to CTP1's. This reduction could lead to smoother and more stable optimization dynamic, which is also what we observed empirically.", "claims_and_evidence": "To some extent, yes. There are a few claims in the introduction that are not entirely accurate, which I have outlined in the 'Other Weaknesses' section below.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes, I believe the authors have provided sufficient details about the experiments, which are undoubtedly comprehensive. Additional comments can be found in the 'More Strengths' section.", "relation_to_broader_scientific_literature": "The integration of KGE to improve NTP is directly beneficial for scientific discovery, as NTP has become a key research focus for many logicians and mathematicians, particularly in areas like automated proof checking and broader scientific applications.", "essential_references_not_discussed": "### Inductive KGE/KGFMs on unseen relations\n[1]. Galkin, M., Yuan, X., Mostafa, H., Tang, J., and Zhu, Z. Towards foundation models for knowledge graph reasoning. In ICLR, 2024. \n\n[2]. Mao, H., Chen, Z., Tang, W., Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang, J. Position: Graph foundation models are already here. In ICML, 2024.\n\n[3]. Lee, J., Chung, C., and Whang, J. J. Ingram: Inductive knowledge graph embedding via relation graphs. In ICML, 2023. \n\n### Inductive GNNs on unseen nodes (there are more)\n[4]. Waikhom, Lilapati, Yeshwant Singh, and Ripon Patgiri. \"PO-GNN: Position-observant inductive graph neural networks for position-based prediction.\" Information Processing & Management 60.3 (2023)", "other_strengths_and_weaknesses": "## Strengths\n1. The paper is well-structured overall, and the integration of the two research areas is clearly demonstrated.\n2. The experimental section is thorough, evaluating four potential methods for integrating KGE, while also comparing different KGE variants. The results show an overall improvement when integrating KGE, aligning with the authors' claims. Additionally, the increase in inference time is presented.\n\n## Weaknesses\n1. In the Introduction, it is initially stated that DL is limited by poor interpretability. However, later it is suggested that the transformation of discrete symbols into continuous vector space combines the strengths of both DL and symbolic AI. I wonder whether LLMs also fall under the category of NeSy AI, yet they still struggle with explanation abilities. Moreover, theorem proofs require significantly more interpretability than natural language, which raises the question of whether this approach is suitable for such domains.\n2. The connection between NTP and KGE could be better introduced. Additionally, there are inductive KGE methods and GNNs that handle unseen entities or relations by defining local representations for unseen items. Knowledge graph foundation models also address such generalization issues [1-4].\n3. It would be valuable to explore the potential reasons behind the observed improvements and identify which types of proof structures could benefit most from KGE integration. This would provide further insight to the research community.", "other_comments_or_suggestions": "## Weaker suggestions\n1. More explanation of the 'sparse gradient perspective' in the Introduction is needed before shifting the focus to the embedding space.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper focuses on the integration of NTPs and KGEs for improving soft unification. The paper proposes several different strategies (the high-level idea of these strategies appear in the literature but the devil is often in the details of integration). The paper also provides an extensive empirical evaluation. 

one of the concerns of some of the reviewers was lack of theoretical explanation but it is understandable that theoretical justification don't come easy and it would be a loss for the community to not know the strategies that work (at least empirically). 

Given the extensive empirical evaluation, I recommend acceptance.
Decision: Accept (poster)