Embeddings as Probabilistic Equivalence in Logic Programs
Authors: Jaron Maene
Efthymia Tsamoura
Venue: NeurIPS 2025 poster ()
Keywords: probabilistic programming
neurosymbolic AI
logic programming
knowledge graph embeddings
soft unification
Primary area: probabilistic_methods
TL;DR: We introduce a distribution semantics on logic programs using probabilistic equivalence.

Abstract: The integration of logic programs with embedding models resulted in a class of neurosymbolic frameworks that jointly learn symbolic rules and representations for the symbols in the logic (constant or predicate). The key idea that enabled this integration was the differentiable relaxation of unification, the algorithm for variable instantiation during inference in logic programs. Unlike unification, its relaxed counterpart exploits the similarity between symbols in the embedding space to decide when two symbols are semantically equivalent. We show that this similarity between symbols violates the transitive law of equivalence, leading to undesirable side effects in learning and inference. To alleviate those side effects, we are the first to revamp the well-known possible world semantics of probabilistic logic programs into new semantics called equivalence semantics. In our semantics, a probabilistic logic program induces a probability distribution over all possible equivalence relations between symbols, instead of a probability distribution over all possible subsets of probabilistic facts. We propose a factorization of the equivalence distribution using latent random variables and characterize its expressivity. Additionally, we propose both exact and approximate techniques for reasoning in our semantics. Experiments on well-known benchmarks show that the equivalence semantics leads to neurosymbolic models with up to 42% higher results than state-of-the-art baselines.

Embeddings as Probabilistic Equivalence in Logic Programs
Jaron Maene KU Leuven Leuven, Belgium jaron www..eeeeeeeleeeenn... be
Efthymia Tsamoura
Huawei Labs"
Cambridge, United Kingdom
efthymia, tsamoura@huawei. com
Abstract
The integration of logic programs with embedding models resulted in a class of neurosymbolic frameworks that jointly learn symbolic rules and representations for the symbols in the logic (constant or predicate). The key idea that enabled this integration was the differentiable relaxation of unification, the algorithm for variable instantiation during inference in logic programs. Unlike unification, its relaxed counterpart exploits the similarity between symbols in the embedding space to decide when two symbols are semantically equivalent. We show that this similarity between symbols violates the transitive law of equivalence, leading undesirable side effects in learning and inference. To alleviate those side effects, the first revamp the well-know possible world semantics of probabilistic logic programs into new semantics called equivalence semantics. In our semantics, probabilistic logic program induces probability distribution over all possible equivalence relations between symbols, instead of a probability distribution over all possible subsets of probabilistic facts. We propose factorization of the equiva- Ience distribution using latent random variables and characterize its expressivity. Additionally, we propose both exact and approximate techniques for reasoning in our semantics. Experiments on well-known benchmarks show that the equiva- lence semantics leads neurosymbolic models with up 42% higher results than state-of sfate-of-the-arr fi--hh--rt art baselines.
Introduction
Probabilistic logic programs offer a principled way reason in the presence of uncertain knowledge (De Raedt and Kimmig, 2013). In neurosymbolic AI, this uncertain knowledge is provided by neural models [Marra et al. [2224] Feldstein
2024]. Probability can hence be the "glue" between symbolic background know knowledge and neural networks, leading to end-to-end differentiable architectures [Rocktäschel and Riedel 2017 Manhaeve et al. 202T].
The most straightforward way to reason symbolically over the outputs neural networks is by treating them probabilistic facts [Manhaeve et al. [021]. A second alternative is map the constants and predicates of the logic program into representation space, achieving a tighter integration. The question hence arises, how can we apply symbolic rule over elements an embedding space? ? The answer is via adopting the simple, yet powerful notion of soft unification [Rocktäschel and Riedel 2017], which relaxes the unification algorithm in logic programming [Sessa) 2002 Instead of requiring two constants and predicates to be syntactically the same, they need to be "semantically equivalent" some extent. We demonstrate the notion of unification and its soft counterpart below.
Example 1. Consider the rule isln(X, Y) + isln(X, 2) A isln(2, Y) and the following three facts: locatedln (eifeel. tower, paris), (paris,,, france), isln (france, europe). In the context of logic pro-
"ork started before Efthymia Tsamoura joined Huawei Labs.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Possible world semantics
Probabilistic equivalence semantics
0.9
W.
0.1 :: b.
h.
b W.
AA Aw W.
p(w -b) 0.81
p(w A b) 0.09
p 0.34
W
p
w h
0.01
w.
W.
W.
a.
b.
h.
a.
a bAW.
+ bAw.
a - b A W.
t- A a.
p(-W -b) 0.09
p A b) 0.01
p 0.51
W
W. b.
b. t b. b.
b
a a bA
Figure 1: Example probabilistic logic programs, under the possible world (left) and the probabilistic equivalence semantics (right). The top row displays the probabilistic programs, while the rows below are the discrete programs in the corresponding program distributions. Above each different program, we write its probability according to the distribution.
gramming, unification is the mechanism to derive new facts by establishing a mapping a from variables to constants. This mapping aims instantiate the premise of a rule using the existing facts. In our example, applying the mapping a = {X paris, Y europe, Z + france) ) to our rule,
derive the new fact isln(paris, europe) using the existing facts isIn france) and isln(france, europe). Establishing a is only possible because is france) shares the same predicate isln with the atom isln X, 2) and the fact isin(france, europe) shares the same predicate with the atom isln Z2 Y). The fact isln(eiffel Ntwerr france) cannot be derived: unification fails as the predicate locatedIn distinct from isln. To support such cases, soft unification extends unification by allowing us to consider as being the same symbols (constants or predicates) that are different from each other, yet semantically equivalent. In our example, soft unification does identify a, subject to isln being equivalent to locatedIn. The probability that two symbols are equivalent is determined by their proximity the underlying representation space.
Motivation. Soft unification has been particularly appealing. as it enables simultancously learning symbolic rules and symbol embeddings in an end-to-end differentiable fashion [Campero et al. 20118 Weber al. 2019 Minervini et al. (2020a b) Maene and De Raedt 2023). The common characteristic of all these techniques is that they all use similarity between symbols, disregarding that equivalence transitive. However, abusing the semantics of equivalence in probabilistic logic programming has problematic consequences in learning and inference. More precisely, we show that soft unification leaks probability mass and suffers from local optima.
Contributions. To overcome the above consequences, we revamp the semantics of probabilistic logic programs, so that they induce distribution P: over all possible equivalence relations rather than a distribution over all possible worlds (all possible subsets of facts in the program). Figure ] visualizes how placing uncertainty on equivalence between constants compares the usual possible world semantics. Our semantics, referred to as probabilistic equivalence, allows us to treat symbol embeddings as a factorization of Ps and to reason over them. Additionally, we re-purpose existing inference techniques developed for reasoning under equivalence for the probabilistic setting. We propose an exact inference pipeline based on singularization [Marnette] 2009] and the magic sets transformation [Beeri and Ramakrishnan 1987]. as well as a Monte- Conte-Carlo Carlo estimator for approximate inference. Our empirical analysis against state-of-the- -he---rrttt--tttte techniques that learn and reason over symbol embeddings relying on soft unification [Rocktäschel and Riedel| 2017 Minervini et al.) 2200a Maene and De Raedi] 20233 shows that our semanties leads to models with up to 42% higher accuracy over the ffate-of-the-rte In summary, make the following contributions:

---

we show that soft unification violates the semantics of equivalence in probabilistic logic programming and investigate its side-effects for learning and inference. We propose a sound distribution semantics over probabilistic logic programs under equiv- alence relations called equivalence semantics Section 4 Our semantics overcomes the independence assumption in probabilistic logic programming [Van Krieken et al., (024). In Section [4.] we propose a factorization of the program distribution induced by our semantics using latent random variables and characterize its expressivity. In this factorization, we realize the latent random variables as symbol embeddings enabling reasoning over them.
In Section 3.1
We introduce exact and approximate inference techniques for our semanties, in Section [ We empirically assess our proposed technique in link prediction and structure learning and compare it against state-of of-e--of-hh-att the-art art neurosymbolic approaches that employ soft unification. Our results show that our equivalence semantics improves performance up to 42%.
Supplementary material, including all code and proofs, is available at https: // thub. com/ ML- wWUTaauvennepalltyyrrraaaoom
2 Preliminaries
We first briefly introduce (probabilistic) logic programs and equivalence relations. For a more extensive introduction to probabilistic logic programming, refer to De Raedt and Kimmig 2015
or Riguzz 2023]. We adopt probabilistic Datalog, which is a subset of more general probabilistic
programming languages such ProbLog (Fierens al. 2013 or dPASP [Geh et al. 2024 Although our technical presentation focuses on Datalog, it largely carriss over to these more general languages.
All notation used in the paper is summarized in Table in the Appendix.
Logic programming. An atom an expression of the form r(tı...., t,) where an n-ary predicate and each t; is a variable or constant. A symbol is a predicate or constant. A Datalog rule, or simply rule, is an expression of the form 6- b --- A bn, where the conclusion h is an atom and the premise bj -.. A bn is conjunction of n atoms. A ground (or non-ground) atom includes no variable (or no constant) argument. rule is goroun when each occurring atom is (non-)ground. A ground rule with an empty body is also called a fact. A Datalog program, or simply program, P is a tuple (F. R). where F is a set of facts and R is a set of non- non-ground rules. The Herbrand universe U of P is the set of all constants that occur in F. The Herbrand base B of P is the set of all ground atoms constructed using the relations and constants in P. Throughout the text, we fix a (probabilistic) logic program P. All formal statements that will follow are w.r.t. this program.
Example 2. Consider the program Per including the facts Fez {r(a, b), r(b, c)} and the rules Res = fr(X, Y) +- r(x, Z) A r(z Y))). The Herbrand universe Pex is U = (a. b, and its Herbrand base B (r(a. a), r(a, b), r(a, r(b, a), r(b, r(b c), r(c, a), r(c, r(.
A set of ground atoms I C B satisfies a ground rule h + bi.... b, if h E holds when each b; is in I. The grounding of a rule in P is the rule that results after consistently replacing each variable with constant from U. The least model M(P) of P is the smallest superset of F that satisfies each possible grounding of each rule in R. Every program has unique least model (Ceri et al.. 1989]. In Example 2 we have M(P.z) Fen U {r(a, c)). The program P entails an atom o, written as P = ox, or is an element of the least model M(P).
Probabilistic logic programming. Probabilistic logic programs extend traditional logic programs by treating each fact f E F as an independent Bernoulli random variable that becomes true with probability (f), where Py : J + [0, 1]. As such, a probabilistic logic program Pp = (F, R, Py) induces a distribution over all (non-pra proobabbbaillistcc) logic programs (w: R), each formed by taking a subset of facts from F. Each such subset w C F is called possible world. This semantics is known as the possible world semanties [Sato] 1995). The probability P(a)) a fact is true in Pp is defined as the probability possible world w leads to the entailment of oc:
P=(w)= = II (f())
II (1 - (())) FEFi
and P(a) = Ewnp, [w R) } a].
(1)
FEW
Example 3. The program from Example 2 has four possible worlds: 0. b)], [r(b, c)}, and (r(a, b), r(b, c)). Only the last one derives r(a, c). By setting P, = (r(a,b) + 0.5, r(b,c) + 0.1). we have P(r(a, = P))r(a,b)) Px(r(b, c)) 0.05.
3

---

Equivalence. A relation is set of n-ary tuples over a domain of elements. An equivalence relation e over a set S is a binary relation e - S S that is reflexive, i.c. V' E S e(x, x), symmetric, i.e. y E S e(x, y) = e(y, x), and Irunsitive, i.e., Vx, y, e(x,y) A e 2) + e(x, z). Equivalence relations are isomorphie to set partitions, and, hence, we use them interchangeably. We write Eg to denote the set of all equivalence relations over the set S.
We use equivalence relations both over the Herbrand universe (constants) and the Herbrand base (ground atoms) of program. Following Maene and De Raedi [2023), we define equivalence relations over the constants of the program and not over the atoms. However, each equivalence relation ey over the Herbrand universe U implies an equivalence relation eg over the Herbrand base B. In particular,
cr(( an), r(bi,,.., bn)) holds in B if and only if A eu(ai, b,) holds in U.
(=1
The above definition might seem restrictive as atoms with different predicates can never be equivalent To support such cases, we can simply take predicates as arguments. For example, rı (x1. and 12 (2() become t(r1, Y1) and t(r2, X2),, where is a fresh dummy predicate.
3 Equivalence in Logic Programming
Intuitively, equivalence creates exchangeability between the facts in the program, meaning that the semantics of the program should remain the same if we replace fact with equivalent one, also Figure I (right). For example, if under an equivalence relation is equivalent to c, there should be no difference between the rules <- b and <- We formalize equivalence in logic programs using the notion of saturation in Definition 2 Then, we formalize soft unification in Definition 3 and show that soft unification violates the semantics of equivalence in probabilistic logic programming and conclude with the impact on learning and inference in Theorems and
Definition I (Set Saturation). Consider set T and equivalence relation ET over T. The saturation S/e of a set SCT subject to is the smallest superset of S that is union of partitions of e.
S/c {y (2r,)) e, E S}
(3)
When set its own saturation, i.e.. S S|c, we also say that S is saturated subject to e. We next expand this definition of saturation from sets to programs.
Definition 2 (Program Saturation). For an equivalence relation ey Ey, the program Plau is the saturation of the program P subject to eu if M(P(eu) O B is the smallest model of P that is saturated subject to eB.
Based on Definition 2 if a saturated program entails a fact a, it also entails the fact a' if the two facts are equivalent. We provide an example of saturation below.
Example 4. Consider the equivalence relation ey {(a,a), b). (a, b), (b, a)} and the pro-
gram P Pen from Example 2 The program Pez is not saturated subject to eu, since (r(a, a), r(a, b)) e en and P 1 r(a, b), but P if r(a, a). The saturation of the set Fez = (r(a, b), r(b, c)} subject to eb is Fen en = Fex U {r(a, a), r(,, b), r(b, a), r(a, c)}.
A standard way to saturate a program is to explicitly axiomatize the equivalence relation and add the corresponding axioms the program Fitting 1996 Chapter 9]. Specifically, for given equivalence relation eu. the axiomatization requires introducing (i) a fresh binary predicate 20, (ii) all facts in F(eu) = (a 2 (a, b) E Ev} and (3) set of congruence rules Coy (R):
Ceu (R) = ((X.,...,, + p( X
Xi
X is n-ary predicate in P}
(4)
i=1
In Example 2 there one congruence rule for each equivalence relation ev. namely Cry (Rex)
=
(r(X, Y) < rX', Y") A 2 x' A z Y'). We have the following result. Theorem 1. For any equivalence relation eu E Ev, the program (F F(eu), RU Cay (R) saturation Pies Pleu& of the program P subject to eu-
Unlike previous work on question answering over logical theories with equality, we do not axiomatize the symmetry and transitivity properties. This is because the facts in F(eu) are already an equivalence relation in Benedikt et al. [2018), the basic assumption is that the input facts F include no sacts.

---

3.1 Soft Unification
Before formalizing soft unification, we will introduce some key notions. Let p = U x U be the equivalence relation where all constants are equivalent. We use = as predicate to denote equivalence C1, C2 E U3.
under and define the set F(p) == {cI R C2
We now introduce soft unification using the notions from Section 3 Let CR( be the set of rules defined as in 4 however, these rules are defined based on R. By associating Bernoulli random variable with each fact in F(p), we can capture the semantics of soft unification using class of probabilistic logic programs referred to as soft unification programs.
Definition 3 (Soft Unification). Let d TR* x R - [0. 1] be function that returns the similarity between the embeddings Ua 0. E R of two symbols and b in U. A soft unification program Ps over a set of rules R. a set facts F, and the similarity function is defined as the tuple:
Pg = (FUF(P), RU (R), Pa)
(5)
The probability fact R b E F(p) is true in Ps is defined Pala b) = d(Ts, Ro). The probability that a fact in F is true in Ps is simply ond
According Definition each possible world of soft unification program is set of factss,, where the probability of each such fact is computed using the constant embeddings. We give an example:
Example 5, The soft unification program given the rules and the facts in the running example in- cludes the facts {r(a. b). r(b, c), a a. b. c, a. b.b ze b. c, a.c b, c} and the rules fr(X, Y) t r(x, Z) A r(z Y), r(X,Y) + r(X', XX world of this program {a a, c..
One possible
In the appendix, we discuss how Definition 3 can represent different soft unification techniques [Rocktäschel and Riedel 2017 Minervini et al. 2020a Maene and De Raedt 2023
Do soft unification programs adhere to the properties of equivalence relations? From Definition 3 it follows that enforce soft unification program to treat equivalence a reflexive relation, it suffices to choose the similarity function d such that d( (e, t = 1 for every embedded symbol U.. Symmetry can similarly be enforced, e.g. by defining as an unordered predicate. However, soft unification programs do not treat equivalence as a transitive relation. failing to capture the true semantics of equivalence. Returning to Example there are possible worlds which the facts a Ro b and b Rz hold, but the fact a R с does not hold. Nonetheless, under mild assumption on the similarity function d, we get weak kind of transitivity due to the use of embeddings.
Theorem For each possible world w F(p) of a soft unification program Pa and each similarity function d satisfying
d(ū T2) = if and only if = 822 VU 2U,, U2 RR.
(6)
P(w) = implies that the Re-facts in satisfy the semantics of transitivity.
Theorem 2 implies that a soft unification program distribution can only place arbitrarily high proba- bility mass on possible worlds where the fa-ts satisfy the semanties of transitivity. For example, there exists no embedding of the constants a, b, and с that satisfies the following probabilities: and P(a R c) 0. From Bayesian viewpoint, the probability mass on the possible worlds whose su-facts do not satisfy the semantics of transitivity is essentially "leaked"" Indeed, after training convergences, these possible worlds need to have probability zero, see also Van Krieken et al. 2024
P(a 2 b)
P(b c)
Soft unification also poses challenges in learning. It is known that any distribution over Boolean variables is a multilinear polynomial function [Darwiche] 2003).. Hence, all optima are global, making it straightforward learn neurosymbolic models computing the gradients of those functions, such as DeepProbLog [Manhaeve et al.) (022). The above does not hold when using soft unification.
Theorem 3. The probability P(ax) a ground atom a & J is true a soft unification program Pa is not a multilinear polynomial function in the embeddings.
CCovennionally, the facts in soft unification program are non probabiliisticc However, it is also possible to associate probability to them in probabilistic logic programming, II]
5

---

Semantics of Equivalence in Probabilistic Logic Programming
This section introduces our semantics, referred as probabilistic equivalence semantics. Our semantics relies on a distribution over the equivalence relations Ps Eu 7 [0, 1]. Recall that possible world semantics relies distribution over the possible worlds PF 2 + [0, 1]. Section 2 As in soft unification, we use = as predicate to denote equivalence in p and assume no z-atom occurs in R or F.
Definition 4 (Probabilisticc Equivalence Semantics). A probabilistic equivalence program Pe over set of rules R, a set of facts F, and distribution Pe Eu + [0, 1] is defined as the tuple (R, F, Pε). The probability fact xe b E F(p) is true in Pe is defined as the probability (a.b) belongs to some
ey E Ey:
P(a = b) = Eeu-PP [(a,b) eul
(7)
The probability a non-= fact a is tree in Pe is defined as the probability a is entailed by a saturation Plou of FR. subject some ey Ey:
P(a) == Bey-Ps [P|cu F
Section 4.1 provides definition of Pg based an embedding model of constants. We provide an example of Definition 4 below.
Example 6. Consider the rumning example with a distribution over the five possible equivalence relations on U = {a, b, c).
Pe
a ab
0.4,
b + 0.3, C
0.0,
2 0.2,
b + 0.1
The probability of r(b,a) a) under Definition 4 is P(r(b, a)) 0.3 0.0 0.1 0.1 0.4, since either a Rs or a Rs c must hold to derive r(b, a) from the least model M(P.a.) = (r(a. b), r(b, (), c), r(a, c)}.
The probabilistic equivalence semantics (Definition 4 can be seen as the possible world semantics (Definition I by defining P(w) == EeuxPe [w = -egl However, unlike in the possible world semantics, the facts in each possible are no longer independent. We further discuss this in Appendix
4.1 Factorizing the Distribution Over Equivalence Relations
We now discuss how to represent equivalence distribution Ps Eu - (0, 1] (see Definition 4 over embeddings of constants. Similarly to representing the full joint distribution Py over all possible worlds, we need to make additional assumptions on Pg make the representation of Pe tractable, as the size of Ey, known as the Bell number, grows exponentially in the size of U. Inspired by probabilistic clustering [Deng and Han 2018), we associate an independent latent random variable Ve with each constant c E U. Hence, the probability belongs to the 7th partition is P(Ve = z). We can treat the probability vector of the categorical Ve as embedding for the constant c.
Pε(eu) EII P(V. = (c))
Fo
Here, Te U- (1....,k] .} is any function such that V(a, b) E eu: (a) (b), with 1 being the embedding dimension. Although T, is required for the above definition of (e(cy) to marginalize away the possible orderings of the partitions, it never needs to be computed in practice. An advantage of this factorization that we can trivially calculate the expectation of two atoms being equivalent.
Corollary 1. When Pe is defined in (9. the probability equivalence atom b is true in probabilistic equivalence program Pe = =R,, F, P&) is given by:
P(a
Σ [[(a,b) Eeu]
ΣI P(V. = CEU
Σ iE (E(I.....)
P(V= - iP =
CuEEu
Our factorization assumes that the probability constant is part of partition is independent, reducing the expressivity. Specifically, we prove below that it can no longer represent any combination of marginal probabilities between constants.

---

Theorem 4. Consider matrix M that contains all the marginal probabilities of constants being equivalent under the probabilistic equivalence semantics, i.e., Mi.5 P(c = G) with C, 9 E U. If Pe is factorized as in ( M is positive semi-defiiite
According to Theorem 4 the marginals of equivalence facts should always form positive semi- definite matrix M, or they cannot be expressed by our factorization
5 Inference & Learning
This section discusses exact and approximate techniques for inference using probabilistic equivalence programs over a constant embedding space. We start by briefly discussing probabilistic Datalog inference. Then, we discuss the changes required to support our semantics.
Probabilistic Datalog. Datalog inference is typically based on the -oint semantics (Ceri et al. 1989]. Starting with a given set of facts F, at each inference step, we apply the rules in R to the existing facts until no new facts can be derived. Modern Datalog engines rely on techniques such as semi-naive evaluation [Bancilhon] 1986) and Trigger Graphs (Taamuraa et al. 202T] to reduce the number of rule applications deriving no new facts. By keeping track of the rules applied to derive a targetfact, we can compute the lineage of the fact, i.e., the Boolean formula representing the possible worlds that lead to its derivation. Calculating the probability of the target fact then reduces to calculating the probability of this Boolean formula [Fierens et al., 2015 Vlasselaer et al. 2016).
problem known as weighted model counting (Sang et al. 2005].
Singularization. Consider a single equivalence relation. The naive approach to reason under this relation is to introduce a special predicate and add the congruence rules C(R) in (4) to the program. Theorem I More advanced techniques deal with equivalence by taking advantage of the symmetry between elements in the same partition [Fitting] [996] Chapter 9]. This idea was implemented as
paramodulation [Robinson and Wos [983] and singularizttonn [Marnette] 2009]. We briefly explain the latter technique below, as is most suited to Datalog.
Definition 5 (Singularization [Mannette| 2009)). The singularization Sg(R, p) of a set of rules R with respect to a target predicate p is the set that includes each rule r R transformed as follows: for each variable X that occurs more than once in an non-z-atom in the premise of r, X is replaced with a unique variable Xj and the atom X = X; is added to the premise of.. In addition, Sg(R. p)
includes the congruence rule p(Xi..... X,) + p(X1...., Xx)) A X1 = X AX...X, = =X,
In Definition 5 the predicate p different from ss, is defined by exactly rule and cannot occur in the body of any rule in R. This assumption is without loss of generality, as it can always be enforced by introducing fresh predicates. In our running example, singularization turns the transitive rule r(x. Y) + r(x, Z) A r(Z, Y) into r(X, Y) t r(X, Z,) A (Zz, Y) A Z z= Zz. Singularization alters the least model and does not preserve probability in general. However, it leads sound inference under our semantics (see Theorem 5 below).
Magic sets transformation. A further well-known optimization in Datalog inference is goal-driven inference. Throughout the rest of this section, consider a target predicate as in Definition [ and a ground atom p(c). where с is tuple of constants. The goal is to find whether the program entails P(c). To do that, instead of computing the least model entirely, specific atoms, called magic atoms, prevent the application of rule until it necessary for the derivation of p(c). This approach is known as the magic sets transform [Beeri and Ramakrishnan 1987), which we denote as Mag(R, p(c)). Appendix D demonstrates the magic transtorm the running example. As we have regular Datalog program after singularization, we can apply magic sets out of the box, bringing us to the final program. Theorem 5. For each distribution Pe: : Eu - [0, 1] and each target ground p-atom a, we have [Pleu t a: Ee Ps [(F U F(eu), Mag(S Fo].
Eey-Pe Pe
The exact inference procedure is summarized in Algorithm I We assume that distributions Ps are represented over constant embeddings as in Section 4.1 The function Lin computes the lineage of the target. The lineage of the Datalog program contains only factss due to the latent variable representation (see Section 4.1 These ss-facts are encoded into a Boolean formula whose variables have probabilities encoded in vector W using the function BooleanEnc, see Cao et al. (002)) De Smet and Zuidherg Dos Martires 20044. Finally, WMC computes the weighted model counting of the resulting formula subject to the weights.
7

---

Algorithm 1: Exact Inference
Algorithm 2: Approximate Inference
Input: Program P (F,R), equivalence distribution P3 as in (). target p-fact a.
Input:
Program (F, R)),
equivalence distribution P& as in 9
target p-fact a, and number of samples k.
Output: Probability P(a)
Output: Approximation of P(a).
Step 1: Singularization
Step 1: Magic Sets
R' Sgg(R. p)
R' := Mag(RR, a)
Step 2: Magic Sets
Step 2: Sampling the Latents
R" := Mag(R', ox)
V PP
Step 3: Lineage Computation
Step 3: Constant Abstraction
lineage == = F(UXU), R",a)
F := =ns V)
Step 4: Boolean Encoding
Step 4: Forward Inference
oo. == EboleanEnc(lineagee.o
I == CheckEntails R', Inst(a, V))
Step 5: Weighted Model Counting
Step 5: Repeat steps 2-4, collecting k
P(a) == WMC(0a, W)
samples [2], ;2,...,,44 vk)]-
return P(a)
return mean( T2, ok))
Approximate Inference. As exact probabilistic inference is often intractable, we also include straightforward Monte-Carlo approximation, similar to Gutmann et al. [2011]. In our case, the probability of a ground atom is estimated as the average number of times the is entailed (i.e., Pla, += a) under the sampled equivalence relations ey. In particular, let Inst(F, V) be the set of facts that results after replacing each constant E U in each fact in J. with the value of its latent V. V. Here, we write V for an assignment all the latent variables of the constants U. After applying the instantiation Inst, we obtain regular Datalog program. So applying singularization is no longer necessary.
In Lemma 4 we prove that such an instantiation a valid saturation of the program. Algorithm contains the pseudo-code and prove the soundness of our sampling technique below.
Theorem 6. For each distribution Pe Ey - [0, and each target ground p-atom a, we have
1 k
BeuwPe [Piou [a]
-lim R-+00
Σ k 1m1
[(Int((F V)), (ag(RR } Inst(a, Vo) where V, ~ Pe.
(10)
Learning, Using exact inference, the computation for P(a) is end-to-end differentiable, and we can hence learn the embeddings from entailment using gradient descent on negative log-likelihood lolog P(a)). When sampling for approximate inference, we lose differentiability and require gradient estimator. Our experiments use the score function estimator (also known as REINFORCE) in combination with the leave-one-out baseline for variance reduction [Kool et al. 2019
Experiments
We assess the effect of semantics settings where embeddings and rules need to be learnt jointly. First, we consider link prediction knowledge graphs. Second, we consider differentiable finite state machines, where the structure of finite state machine needs to be learned from sequences of subsymbolic data.
6.1 Link Prediction in Knowledge Graphs
Benchmarks. We use two well-known small knowledge graphs: countries [Bouchard et al. 2015 and nations [Rummel] 1992). Countries contains the locations of countries and regions in the world and comes in three variants with increasing difficulty (S1, $2, and S3). Nations contains geopolitical relations between countries. There are no standard data splits for nations, which complicates the comparison with prior results. We adopt the same splits as Rocktäschel and Riedel 20177 and Minervini et al. 2000bb].
8

---

Table 1: Link prediction results the countries and nations knowledge graphs. We report the mean and standard deviation over 10 seeds. Baselines are taken from Minervini et al. [2020b a Maene and
De Raedt [2023]. Tables and 6 in the appendix show the used hyperparameters.
Dataset
Metric
NTP
GNTP
CTP
DeepSoftLog
Ours
S1 Countries S2
AUC-PR
90.83 + 15.4
99.98 = 0.05
100.0 + 0.00
100.0 = 0.00
100.0 + 0.00
AUC-PR
$7.40 11.7
90.82 = 0.88
91.81 + 1.07
97.67 + 0.98
100.0 + 0.00
AUC-PR
56.68 17.6
87.70 = 4.79
94.78 + 0.00
97.90 1.00
99.89 + 0.31
MRR
0.61
0.658
0.709 + 0.03
timeout
0.724 + 0.01
Hits@1
0.45
0.493
0.562 + 0.05
timeout
0.591 + 0.02
Nations
Hits@
0.73
0.781
0.813 + 0.03
timeout
0.819 + 0.01
Hits@
0.87
0.985
0.995 0.00
timeout
0.988 0.01
Evaluation. As is standard in the literature, we report the area under the precision-recad curve (AUC-PR) for the countries knowledge graph and use filtered ranking [Bordes et al. 2013) for nations. For each fact p(a, b) in the test dataset, we take all possible corrupted facts by replacing one of the two arguments, creating p(a', b) and p(a, b'), and filter out any corrupted facts that appear in the knowledge graph. We then rank the probability of the test fact compared to all these corrupted facts. When different facts have the same probability, previous works often rank ties in their favor. This is known to skew results [Sun et al. 2020 and we instead do random tie-breaking. Using the ranks, we report the mean reciprocal rank and hits @ (with & E (1, 10)).
Setup. We train with the same rule templates as prior work (c.f. Appendix B) and set the embedding dimension to the vocabulary size avoid limiting the expressivity. We use approximate inference as described in Section 5 with the GLog Datalog engine (Tsamoura et al. [021]. The only biased aspect of optimization is that we truncate the fixed-point iteration the Datalog engine, meaning the derivation of each fact can take at most 8 steps. This was found to speed up training with no significant performance penalty. We train for epochs with the Adam optimizer. All hyperparameters summarized in Appendix [ As baselines, we compare with prior work that reasons on embeddings in logic programs. Namely, the Neural Theorem Prover (NTP) [Rocktäschel and Riedel, 2017], the Greedy Neural Theorem Prover (GNTP) [Minervini et al. 2020b]. the Conditional Theorem Prover (CTP) Minervini et al. 2020b). and DeepSoftLog Maene and De Raedt 2023).
Results. The results are summarized in Table I On every tested knowledge graph, we outperform existing soft unification models. Notably, this still the case for CTP, which not restricted to a specific set of rule templates, as all other tested methods are.
6.2 Differentiable Finite State Machines
Differentiable finite state machines classify an input sequence of MNIST images into accepting and non-accepting sequences. For example, in the language (01)*, o and Ø i 0 are accepting sequences while and o o I network, in this case digit classifier, and the transition rules of the state machine.
are non-accepting sequences. The goal is to jointly train a neural
We follow the same experimental setting as Maene and De Raedt 2023), using three different binary languages: the language of 01 repetitions, the language of sequences with exactly one 1, and the language of sequences with even number of I's. In each case, 20 example digits are given as concept supervision to provide a non-random baseline accuracy to the neural network. After this, the models are trained on sequences of length 4. To test generalization, the test sequences have double the length and use images disjoint from the training split. Table displays the results. As a baseline, we include both DeepSoftLog and a simple RNN. On each language, the introduction of transitivity greatly improves the results of DeepSoftLog, to the point of saturating this benchmark.
7 Related Work
Equivalence logic. Equivalence logic has been studied extensively NNilsson and Maluszynski 1995] Chap. 13: Fitting 1996) Chap. 9], going back to Jaffar et al. [1984]. Logic with equivalence relations has been used in the context of database dependencies Marnette 2009 Benedikt et al..
2018), the semantic web [Motik et al. 2015), compiler optimizations Zhang et al. 2023]. or second-

---

Table 2: AUC-PR on sequence classification with differentiable automata for three grammars. We report the mean and standard deviation over 10 seeds. Baselines are from Maene and De Raedt (2233
Language
(01)*
10
(0 10*
RNN
77.63 + 15.05
61.59 + 10.09
50.14 = 1.36
DeepSoftLog
83.93 + 25.87
87.01 + 7.18
56.12 = 15.98
Ours
99.60 = 1.02
97.46 5.87
99.61 + 0.54
order theories (Tsamoura and Motik 2024]. To the best of our knowledge, we are the first to place uncertainty on the equivalence. Exchangeability in probability distributions was also studied under the name of lifted inference [Niepert and Van den Broeck 20144). In lifted inference, there is exchangeability between the variables of the probability distribution, while in our work, we have a probability distribution on the exchangeability between symbols.
Soft unification. Many extensions of logic have been proposed handle uncertainty vagueness. Similarity bbssed logies extend fuzzy logic with a similarity on symbols [Girrla and Sessa 1999 Fontana and Formato, 2002, Godo and Rodríguez 2008). This fuzzy matching between symbols has been variously called soft or weak unification, as it can be seen as a relaxation of the unification algorithm that matches symbols during SLD-resolution. A key difference between the similarity used in soft unification and the equivalence we consider is the former does not respect transitivity. Further works have studied the model-based semantics of soft unification [eesa 2002 Medina al. 2004 and the use of similarities or proximities (Medina et al. [2004] Julián Iranzo and Rubio-Manzan
2013) and introduced practical implementations such as Bousi--Poooog -Jliáá-Iranzo al. 2009
Related to soft unification, (ohhen 2000a b) relaxed database joins using similarity. |Rockääschel and
Riedel| (017) took neurosymbolic view soft unification with the Neural Theorem Prover (NTP)
by learning the embeddings in an end-to-end differentiable way. Minervini et al. (2020a] improved the scalability of the NTP using greedy approximations. Maene and De Raedt 2023 argued for using probabilistic logic instead of the fuzzy semantics, as the fuzzy inference leads to poor optimization
de Jong and Sha 2019]. All these works still rely similarity and do not use full equivalence.
Lastly, relational graph neural network architectures may approximate the behaviour of NTPs through message passing [Barbiero et al. 2024).
Knowledge graph embeddings. Embeddings are the standard approach in knowledge graphs to handle incompleteness [Bordes et al., 2013). From probabilistic view, embeddings can be seen low-rank decomposition of the distribution over triples [Loconte et al.] [203]_ contrast to our work, the probability of an atom here only relies on its own embeddings (up normalization). Moreover, these probabilistic semantics of embeddings do not allow rule learning. Several recent knowledge graph methods have proposed neurosymbolic rule learning [DeLong al. 2024). Unlike our work, these are typically not end-to-end differentiable and do not have sound probabilistic semantics.
8 Conclusion & Limitations
We investigated the semantics of soft unification for learning and reasoning over embeddings. We showed that soft unification does not adhere to the properties of logical equivalence causing issues in inference and learning. To overcome those issues, we introduced the equivalence semanties in logic programming. We linked our semantics to reasoning over constant embeddings by associating each constant with a category corresponding to the partition the constant belongs. We also adapted existing techniques for inference in the presence of equality reason under semantics. Lastly, we experimentally confirmed that enforcing transitivity can considerably improve performance on neurosymbolic tasks, where the rules and embeddings are learned jointly.
Several open questions and limitations remain. First, developing lower variance methods for gradient estimation is necessary for effective training with large number of rules. Full grounding is often infeasible when learning rules, so many existing approximation strategies are not applicable. Second, our approach still relies on templates for rule learning, so either considerable language bias is incurred or inference becomes challenging. Third, the extension to other languages, such as non- non-monotoiic logic programming declarative probabilistic languages, is left to future work.
10

---

Acknowledgements
Jaron Maene received funding from the Flemish Government (Al Research Program). We thank Luc De Raedt for his valuable feedback.
References
Francois Bancilhon. Naive evaluation of recursively defined relations. In On knowledge base management systems: integrating artificial intelligence and database technologies, pages 165-178. Springer, 1986.
Pietro Barbiero, Francesco Giannini, Gabriele Ciravegna, Michelangelo Diligenti, and Giuseppe Marra. Relational concept bottleneck models. Advances in Neural Information Processing Systems, 37:77663-77685, 2024.
Catriel Beeri and Raghu Ramakrishnan. On the power of magic. In Proceedings of the sixth ACM SIGACT-SIGMOD MOGGGRR---RATTTT symposium on Principles of database systems, pages 269-2269992 2844, 1987.
Michael Benedikt, Boris Motik, and Efthymia Tsamoura. Goal-driven query answering for existential rules with equality. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Antoine Bordes, Nicolas Usunier, Alberto Carcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
Guillaume Bouchard, Sameer Singh, and Theo Trouillon. On approximate reasoning capabilities of low-rank vector spaces. In AAAI spring symposia, 2015.
Andres Campero, Aldo Pareja, Tim Klinger, Josh Tenenbaum, and Sebastian Riedel. Logical rule induction and theory learning using neural theorem proving, arXiv preprint 1809::800.021111 2018.
William X Cao, Poorva Garg, Ryan Tjoa, Steven Holtzen, Todd Millstein, and Guy Van den Broeck. Scaling integer arithmetic in probabilistic programs. Uncertainty in Artificial Intelligence, pages 260- 160-270. PMLR, 2023.
Stefano Ceri, Georg Gottlo, Letizia Tanca, et al. What you always wanted to know about Datalog (and never dared to ask). IEEE transactions on knowledge and data engineering, 1(1):166-166, 1989.
William W Cohen. Data integration using similarity joins and a word-based information representation language. ACM Transactions Information Systems (TOIS), 18(3):288 321, 2000a.
William W Cohen. Whirl: A word-based information representation language. Artificial Intelligence, 118(112):63-196, 2000b.
Adnan Darwiche. A differential approach inference in bayesian networks. Journal of the ACM
(JACM), 50(3):200330 May 2003. ISSN 0004-5411, doi: 10.1 10.11455765568.7555777.
Michiel de Jong and Fei Sha. Neural theorem provers do not learn rules without exploration. arXiv preprint 1906005906.06805, 2019.
Luc De Raedt and Angelika Kimmig. Probabilistic (logic) programming concepts. Machine Learning, 100:5-47, 2015.
Lennert De Smet and Pedro Zuidberg Dos Martires. A fast convoluted story: Scaling probabilistic inference for integer arithmetic. In Conference on Neural Information Processing Systems, 2024,
Lauren Nicole DeLong, Ramon Fernández Mir. and Jacques D Fleuriot. Neurosymbolic Al for reasoning over knowledge graphs: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2024.

---

Hongbo Deng and Jiawei Han. Probabilistic models for clustering. In Data Chustering, pages 61-86. Chapman and Hall/CRC, 2018.
Jonathan Feldstein, Paulius Dilkas, Vaishak Belle, and Efthymia Tsamoura. Mapping the neuro- symbolic AI landscape by architectures: A handbook on augmenting deep learning through symbolic reasoning. arXiv preprint arXiv:2410. 22077, 2024.
Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. Inference and learning in probabilistic logic programs using weighted boolean formulas. Theory and Practice of Logic Programming. 15(3):358 401, 2015.
Melvin Fitting. First-order logic and automated theorem proving.. Springer, New York, NY, 1996. ISBN 10--1--611-22660--
Francesca Arcelli Fontana and Ferrante Formato. A similarity-basee resolution rule. International Journal of Intelligent Systems, 17(9):853-877 872, 2002.
Renato Lui Geh, Jonas Gonçalves, Igor C Silveira, Denis Mauá, and Fabio G Cozman. dPASP: probabilistic logic programming environment for neurosymbolic learning and reasoning. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 21, pages 731-742, 2024.
Giangiacomo Gerla and Maria I Sessa. Similarity in logic programming. In Fuzzy Logic and Soft Computing, pages 19-31. Springer, 1999.
Lluís Godo and Ricardo O Rodríguez. Logical approaches to fuzzy similarity-based reasoning: an overview. Preferences and similarities, pages 75-128, 2008.
Bernd Gutmann, Ingo Thon, Angelika Kimmig, Maurice Bruynooghe, and Luc De Raedt. The magic of logical inference probabilistic programming. Theory and Practice of Logic Programming, 11 (4-5):663-680, 2011.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2 edition, 2012.
Joxan Jaffar, Jean-Louis Lassez, and Michael Maher. theory of complete logic programs with equality. The Journal of Logic Programming, 1(3):211-223, 1984.
Pascual Julián-Iranzo and Clemente Rubio-Manzano. Proximity-based unification theory. Fuzzy Sets and Systems, 262:21 433, 2015.
Pascual Julián-Iranze Clemente extension language for flexible query answering. Electronic Notes in Theoretical Computer Science, 248: 131-131, 2009.
and Juan Gallardo-Casers Bousi prolog: prolog
Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 reinforce samples, get a baseline for free! 2019.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pages 2863-2872. PMLR, 2018.
Lorenzo Loconte, Nicola Di Mauro, Robert Peharz, and Antonio Vergari. How to turn your knowledge graph embeddings into generative models. Advances Neural Information Processing Systems, 36.77713-777444 2023.
Jaron Maene and Lue De Raedt. Soft-unification in deep probabilistic logic. Advances in Neural Information Processing Systems, 36:60804-60820, 2023.
Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Neural probabilistic logic programming in deepproblog. Artificial Intelligence, 298: 103504, 2021.
Bruno Marnette. Generalized schema-mappings, from termination to tractability. In Proceedings of the twenty-eighth ACM VIGMOD-SIGACT-SSIC symposium on Principles of database systems, pages 13-22. 2009.
12

---

Giuseppe Marra, Sebastijan Dumančić, Robin Manhaeve, and Luc De Raedt. From statistical relational to neurosymbolic artificial intelligence: survey, Artificial Intelligence. 128:00462.. 2024.
Jesús Medina, Manuel Ojeda-Aciego, and Peter Vojtáš. Similarity- based unification: multi-adjoil approach. Fuzzy sets and systems, 146(1):43-o0) 62, 2004.
Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5182-5190, 2020a.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In International Conference on Machine Learning, pages 6938-6949 PMLR, 2020b.
Boris Motik, Yavor Nenov, Robert Piro, and Ian Horrocks. Handling owl:sameAs via rewriting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Mathias Niepert and Guy Van den Broeck. Tractability through exchangeability: A new perspective on efficient probabilistic inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Ulf Nilsson and Jan Maluszynski. Logic, Programming, and PROLOG. John Wiley & Sons, Inc., USA, 2nd edition, 1995. ISBN 0471959960.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. (RNNL]ogic: Learning logic rules for reasoming on knowledge graphs. In International Conference on Learning Representations, 2021.
Fabrizio Riguzzi. Foundations of Probabilistic Logic Programming: Languages, semantics, inference and learning. River Publishers, 2023.
George Robinson and Larry Wos. Paramodulation and theorem theorem-proving in first-order theories with equality. In Automation of Reasoning: 2: Classical Papers on Computational Logic 1967-1970, pages 298-313. Springer, 1983.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. Advances in neural information processing systems, 30, 2017.
Rudolph J Rummel. Dimensionality of nations project: attributes of nations and behavior of nation dyads, 1950-1965. 1992.
Tian Sang, Paul Beame, and Henry A Kautz. Performing bayesian inference by weighted model counting. In AAAI, volume 5, pages 475-82, 2005.
Taisuke Sato. A statistical learning method for logic programs with distribution semantics. Logic Programming, pages 715-730, 1995.
Maria Sessa. Approximate reasoning by similarity- based SLD resolution. Theoretical computer science, 275(1-2):889-426, 2002.
Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 5516 5522, 2020.
Efthymia Tsamoura and Boris Motik. Goal-driven query answering over first-and second-order dependencies with equality. arXiv preprint arXiv:2412.09//5,, 2024.
Efthymia Tsamoura, David Carral, Enrico Malizia, and Jacopo Urbani. Materializing knowledge bases via trigger graphs. Proceedings of the VLDB Endowment, 14(6):943-956, 2021.
Emile Van Krieken, Pasquale Minervini, Edoardo M Ponti, and Antonio Vergari. On the independence assumption in neurosymbolic learning. In Proceedings of the 41 41st International Conference on Machine Learning, pages 49078-49097, 2024.
13

---

Jonas Vlasselaer, Guy Van den Broeck, Angelika Kimmig, Wannes Meert, and Luc De Raedt. Tp- compilation for inference in probabilistic logic programs. International Journal of Approximate Reasoning, 78:15-32 2016.
Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. NLProlog: Reasoning with weak unification for question answering in natural language. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pages 6151-6161, 2019.
Yihong Zhang, Yisu Remy Wang, Oliver Flatt, David Cao, Philip Zucker, Eli Rosenthal, Zachary Tatlock, and Max Willsey, Better together: Unifying datalog and equality saturation. Proceedings of the ACM Programming Languages, 7(PLD)):468 492, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
All our claims are based on theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section g
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
All assumptions are formalized and detailed proofs are given in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide experimental details in Section and Appendix B The source code to replicate all experiments will be released upon publication.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification: Source code will be released upon publication. Every used dataset is available online, see Appendix B
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/ public/guidese howps///ooooduubsssssoooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/ppp wwwppcclccgguiecuceccccceooooope wet.ggddddee/eeebbnninnn httSSSbbmiiiiooooiiiiiooooii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report the standard deviation over 10 seeds for each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments in our paper do not require GPU resources and can be run on a personal machine.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///arrrr..ccccoo///cccaccca
Answer: [Yes]
Justification:
We foresce no specific potential harms nor specific ethical considerations.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work concerns fundamental research on probabilistic logic programming and neurosymbolic AI. We foresee no immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses particular risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release any new assets,
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our research does not involve LLMs, nor have they been used in the creation of this paper.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

Table 3: The notation used in paper.
Symbol
Ref.
Description
CEU
Sec.
A constant in U.
Sec.
The Herbrand universe of P.
X
Sec.
A variable ranging over the elements of U.
Sec.
A ground atom in
B
Sec.
The Herbrand base of P.
fe
Sec.
A fact F.
F
Sec.
Set of facts, i.c., ground atoms.
h + bi....,bu bn
Sec.
Datalog rule.
R
Sec.
Set of non-grount rules.
P = (R.
Sec.
Datalog program.
Por
Ex.
Program the running example.
M(P)
Sec.
Least Herbrand model of P.
P F
Sec.
Entailment, ground atom is entailed by P.
Eu
Sec.
The set of all equivalence relations over the set U. An equivalence relation over U. An equivalence relation over B.
eu
Sec.
EB
Sec.
2
Sec.
Predicate to denote equivalence under ey-
p= X
Sec.
3.1
The equivalence relation in which all elements are equivalent.
Sec.
3.1
Predicate denote equivalence under p. Saturation of the set S subject to the equivalence relation ey-
Sjeu
Def.
Pleu
Def.
Saturation of the program P subject to the equiva- lence relation eu-
Py : F + [0.1]
Sec.
Probability for each fact in F.
Pa F()) 1
Def.
Probability for each equality fact in F(p).
Pp:=1 (F, R3)
Sec.
Probabilistic logic program.
W F
Sec.
Possible world, subset of the facts F.
2F
Sec.
Set of all possible subsets of F.
PF:2" + [0,
Eq.
Probability distribution over all possible worlds of the probabilistic logic program P. Probability distribution over Ey-
ps: + [0
Eq.
F(cy) {a 20 (a. cu]
Sec.
Set of equivalence facts for eu-
C., (
Eq.
Set of congruence rules subject to cy-
PA = (FUF(p), (R), Pa)
Det.
Soft unification program.
P. = FRF,PPo
Def.
Probabilistic equivalence program.
V.
Sec.
Latent categorical variable for the constant e U.
Sg,
Def.
Singularization of the rules in R with respect to target predicate p. Magic sets transformation of the rules in R subject to the fact a.
Mag(R, a)
Sec.
V
Sec.
Assignment to all latent variables Ve, for E U. The set of facts that results after replacing each in each fact in F with the value of the latent Ve2 w.r.t. V.
Inst(F, V)
Sec.
constant
A Proofs
We first establish some preliminary definitions and theorems regarding lattices, fixed points, and monotone logic programming. We then use this background to establish that both models and saturated models of Datalog programs form lattices. These results are later used to prove the main theorems from the paper.
22

---

Table 4: The additional notation used in appendix.
Symbol
Description
0
Grounding substitution, i.e., mapping of variables to constants.
Ground atom that results after replacing each variable with 0(X).
M(P)
Set all models for a Datalog program P.
Partial order.
(S,E)
Partially order set (poset) for set S. The greatest lower bound of (T', E).
inf
Tp 2 + 2B
The immediate consequence operator. Fixed point operator over set Set of all saturated models of P subject to ev. Least saturated model of P subject to ev-
Fix: 5) + 22
May (P)
inf May (P)
A.1
Preliminaries
Definition 6 (Partial Order). A partial order over sel S is binary relation E that is reflexive, Le., Va E S a [ a, antisymmetric, ie., Va, S: b E a = a = b, and transitive, i.e. Va, b, E S E AbAbC c E A partially ordered set poset is tuple of the form (S, E), where S is a set and _ is partial order.
For our purposes, assume all sets finite.
Definition 7 (Lower Bound & Infimum). Let (S,E) be poset and T C S be subset of S. An element E S is lower bound of T if [ t, for each E T. The lower bound Tf for which l' [ t holds for every other lower bound l' of T is the infimum the greatest lower bound Tf denoted by inf T.
When they exist, infima are unique by antisymmetry.
Definition 8 (Semilattice). A poset (I,, [) is semilattice, for each S C T,, S has an infimum.
Definition 9 (Subsemilattice). For semilattice (L, 5) and set S C L, the poset (S,5) is subsemilattice if S is closed under infima, i.e., inf T S for each subset T S.
We next formalize Datalog inference using the immediate consequence operator. Here, write 0 for a substitution, i.c., a mapping from variables to constants in U. The application at of the substitution 0 to the atom a replaces each variable X in with the constant 0(X).
Definition 10. The immediate consequence operator Tp 2B - 2 adds the facts and all atoms that can be derived from interpretation to that interpretation.
Tp(T) = TUFF (h0 h <- bı....,b, R.
is a substitution, b,0 e for all i}.
We slightly deviate from the standard definition by also including in (T). But this will be useful later. Next, we define the fixed point operator, as we later use the fixed points of the immediate consequence operator.
Definition 11 (Fixed Point Operator). Given S, the fixed point operator Fix (S - S) 2 maps a function f S + S to to the set of fixed points of f.
Fix(f)
{s f,)(s) s}
Besides regular Datalog models, we are interested saturated models. Observe that the least model in Definition 2 is saturated model.
Definition 12 (Saturated Model), For an equivalence relation eu E Ev. set of ground atoms M C B saturated model of subject to eu if the following two conditions hold:
1. M is model, i.e., M P.
23

---

2. M is a saturated set subject to eg-
Finally, we also introduce Gram matrices, as they relate to our choice factorization Section 4.1
Definition 13 (Gram matrix), Given n vectors U1, u2,..., Sy the Gram matrix G is the matrix with as elements the inner products Gū (Ug kz)-
Every Gram matrix is symmetric and is positive semi-definite (Horn and Johnson 2012 Theorem 7.2.10.. For real symmetric matrices, positive semi-definite means all eigenvalues are positive.
A.2 Fixed point Semantics of (Saturated) Programs
We now use the above terminology to show that the models M(P) of a Datalog program P form semilattice.
Lemma 1. For any Datalog program P, (M(P), C) is a semilattice, where C denotes set inclusion.
poset and (2) for each S M(P), the poset (S, =) has an infimum. Regarding (1), (M(P), 9) is a poset since is reflexive, antisymmetric, and transitive binary relation. To complete our proof, we need to show that (2) holds as well. The proof continues as follows. The intersection M N M, of any set of models {.M.) C. M(P) is also model. This is because for any rule + b b, E R and any mapping 8, if all by0 M, then all b,0 E M; for all Since each M, is model, h6 M, for all i, thus
Proof.
According to Definition (M(P), 9) a semilattice if (1)
h0 E M. Therefore, M a lower bound for {M;}
M is the greatest lower bound, as for any lower bound M' for [M:} it holds that M' C M; for each So M' SN; M; = M. This proves that every set of models has an infimum and hence M(P) is semilattice.
As is typical in the Datalog literature [Ceri et al. 1989 we characterize the models a Datalog program the interpretations where nothing new derived by the immediate consequence operator Tp. The lemma below is a variant of the Knaster- -haster-Tarski theorem.
Lemma 2. The set of fixed points of the immediate consequence operator Fix(Tp) equals the set of models M(P).
Fix(Tp) = M(P)
Proof. We prove the two directions Fix(Tp) S M(P) and Fix(Tp) 2 M(P) separately.
(C) Let I E Fix(Tp), so (I( = T. By Definition 10 F C TP() = J. Moreover, for any rule h bi....,bu bn R and grounding 0, if b,0 for all have hō E (T)()) T. It follows that
TE M(P).
J.. As M is model, FC M. Moreover, for any rule <- bi...., bn E R and grounding 0, if b,0 E for all i, we have h0 E M as M is model of P. Thus we have Tp (M) M.
Let E M(P). Again by Definition 10 (p(M) M MUFU (h@ ......
We denote the set of all saturated models subject to as Meu By the above definition, every saturated model is also model. Hence, follows immediately that Meu (P) C MPP).
Next, we clarify the relation between the regular models of a Datalog program and the saturated models of program.
Lemma 3. Let P be Datalog program and eu Ey be an equivalence relation. Then (Mey (P), S) a subsemilattice of (M(P),
Proof. Let (M.) S May (P) be subset. We prove that the intersection M N M, is saturated
model and hence Ma, is closed under infima. To do so, we verify the two conditions of
Definition 12 1) Due Lemma ! M is model of 2) Consider a ground atom M n B and EB (a, a') where a' E B. Then E M, for all i. Since each M, is saturated, a' E M, for all i. Therefore, a' M.
As corollary, the saturated program of Definition 2 always exists.
24

---

Corollary 2. For each Datalog program P and each equivalence relation ey E Ev, there exists unique least saturated model:
inf (P)
M (EMay(()
(11)
Proof. Since Meu (P) a subsemilattice (Lemma 3). the infimum of the set of all saturated models is also a saturated model. Uniqueness follows from antisymmetry of =.
Finally, we show that the models saturated program correspond with the models of a program where the constants get instantiated.
Lemma 4. For any equivalence relation eu E &y and any program P = (F, RR), the semilattice Mey (P) is isomorphic to the semilattice M((Inst(F, V), R)).
Proof. Let P' = (Inst(F, V), R.) be the instantiated program and Inst U U/eu denote the map sending each constant to its equivalence class under cy. which we extend pointwise to atoms and sets of atoms:
Inst(p(ti...... tn), V) p(Inst(tı, V).... Inst(t V)). Inst(L, V) [nst(a V) a I.
To prove the isomorphism, first show that Inst is a bijection between May (P) and M(P') (by showing injectivity and surjectivity) and second show that infima are preserved by Inst.
Injection. Let M1, M2 &Meu (P) such that Inst(M V) Inst(M2, V). Take any atom By construction, Inst(a, V) E Inst(M,, V) = Inst (2.. V). This means that there is an atom a' M2 such that Inst(a', , V) Inst(a, V). By the definition of instantiation, this implies that (a,a') E сB- But M2 is saturated subject to ég, so it also holds that a E M2. We can analogously prove that any atom
M1
M2 is also element of M1, proving that M1 = M2.
Surjection. Take any instantiated model M' E .MP'). Then define the model = {a Inst(a, V) E M'. Now it holds that Inst(M, V) = (Inst(a, V) Inst(as, V) M' = M' meaning Inst is surjective.
Preservation of infima. Consider two saturated models M2 E Meu (P). Inst commutes with intersections as
Inst(M M2, V) (Inst(as, V) a E M1 n M2) (Inst(a, V) a E Mi) fInst(a, V) a M2] Inst(M,, V) n Inst(M,, V).
Hence Inst is bijection that preserves infima, so (May (P), S) and (M(P'), are isomorphic semilattices.
A.3 Main results
Theorem 1. For any equivalence relation eu E Ev, the program (FuF(ee) R Cey (R)) is saturation Pleu of the program P subject to eu-
Proof. Let Pleu (Fu)()e)) RU Cey (R)). According to Definition to prove that Pleu is saturation of we need to show that M(P ((P)ey) BB is the smallest model P that saturated subject éB. To prove this, we first show that (M n B M E M(P)e.)) MMay (P), by checking the two directions (C and 2).
Let M M(P]eu). We show that M B BBB (P) by verification of the two conditions of Definition 12
Given that FC FUF((e) and R C R Cay (R), every atom entailed in also entailed in Pee due to monotonicity. Therefore, M O B is also model of P.
25

---

2. Let a p(t....... .t)) E M n B and suppose e a') where a' = p(t t2) B. The congruence rule 4 for predicate p grounded by X; + tj and X; + +
p(t p (y) - p(4,, tn) A A
i=1
By Equation 2 cB(a, a') implies eu(ti, t/) for all i E {I,.... n... Since eu(ti, t(), we have t 1 E F(eu) S M. So as M model, p(tí..... E M. Therefore, M is saturated.
Let M MAReMEAA (cu We show MU MUF(e)) E (M(Pioy). by verifying that M satisfies all rules in C. (R) and contains all facts FUF(ee). First, since . a model of P, we have contains all facts F and satisfies all rules R. Lastly, consider congruence rule in Ceu (R)
P ................................ Xn) P(X X²)
X
and grounding 9 with X; + and X + t/. Suppose all body atoms are in M: p(ti:-..,,t5) MnB and t; 2u t. E M for all i. Since t; means (p(p(t)..... p(t,( .,)), Since ptt 12)) M B and M is saturated, we have tt) E M. Therefore, M is closed under all congruence rules.
2 t. F(eu), we have eu(t, t)) for all i. By Equation 2 this
Me,, We have shown {M nB M E - the equality facts are precisely the saturated models of P. The theorem by Corollary 2 as the least saturated model inf Mey (P) exists and equals the least model of P'.
In other words, the models of Pleu without
Theorem 2. For each possible world w C F(e) of soft unification program Ps and each similarity function d satisfying
d(ū 02) if and only if 822 YŪ,, U2 E
(6)
P(w)= = implies that the Re-facts in w satisfy the semantics of transitivity.
Proof. Consider three constants b, U, such that (a ss b) E and (b R Because P(w) 1, it follows that P(a R b) = and P(b RS c) 1, meaning that V. = Vb and o Uc.
Since P(w) = 1, it follows that P(a c) 1 and hence, (a c)
Theorem 3. The probability P(a) a ground atom a & F is true in soft unification program Pe is not a multilinear polynomial function in the embeddings.
Proof. As defined in I the probability atom in probabilistic logic program Pp is
P(a)
Σ WE2 (wa
((
II (1 Py(f)) fEFlw
In the case of soft unification program Ps. this becomes
P(a)=
Σ
II ambEw
d(F,,
II a
(1 d(C,, ()).
WE2
(FU,,
As soon as there are more than two constants in the Herbrand universe, the vector ūद for each constant с occurs multiple times in the above product. This implies P(a) is not multilinear.
As an example, consider a program with facts {p(a), q(b)} and the rules (r(X) :- p(X), (X)). If query r(c) in this program get P(r(c)) d(T,, (c) d( d(,, (T)), because b and b R allow us to conclude p(c) and qc)), respectively. If the function d is for instance the inner product, then follows that P(r(c)) (Ta, Ue) (ūb, Ue), which is not linear in Jc.
Theorem 4. Consider matrix M that contains all the marginal probabilities of constants being equivalent under the probabilistic equivalence semanties, iee. Mr, P(c, RS G) with c, Gj U. Pe is factorized as in (9, M is positive semi- defintef.
26

---

Proof. As shown in Section 4.1 under the factorization of Equation 9 every element Mi.j is an inner product between the probability vectors of G, and Cj. In other words, M is Gram matrix, which is positive semi-definite Hoorn and Johnson 2012 Theorem 7.2.10).
Theorem 5. For each distribution Pe Eu - [0, 1] and each target ground p-atom a, we have
Es [Plc = ax] Eeu-Ps [(F U F(eu), Mag p), F a).
Proof. To prove this theorem, it suffices to show that for each eu E Pe. (F F(eu), Mag(Sg(R, p), a)) entails if and only if Play entails a.
We start be recalling Theorem T which says that
F (FUF(ee). R U C(R)) Fa.
On the right side, have regular Datalog program. So singularization preserves entailment MMannttte 2009], it holds that
Po (F Sg(R
Furthermore, due to the soundness of the magic sets transformation [Beeri and Ramakrishnan 1987 Theorem J. also holds that
Pleu F a + (FUF(ee), Mag(SS(R,,),.a))
As the above equivalence holds for any equivalence relation eu, it also holds in expectation, and the theorem follows.
Theorem 6. For each distribution Pe Eu - [0, and each target ground p-atom o, we have
Beu~Pe [Picu F a]
lim
[[[nst((F, V:), Mag(R, }= Inst(a, V:)] where V, ~ PE.
k-000
(10)
Proof. From the isomorphism Lemma follows that
Play Fa a (Inst(F, V), } Inst(a, V).
Furthermore, due to the correctness the magic sets transformation [Beeri and Ramakrishnan 1987
Theorem 4.1], it also holds that
Plau Fa
(Inst(F, V), Mag(R, a)) Inst(a, V).
Hence, expectation, we also get
Eru [P|eu = a] Eny [Inst(F, V), Mag(M, o:) - Inst(a, V)).
Finally, we can apply the law of large numbers arrive at the theorem.
Ezg (Plo } a)
lim
[[nnt([ V.). Mag(R, } Inst(a, V.)..
k +
B Experimental Details & Hyperparameters
Hyperparameters. For the countries knowledge graph and the differentiable finite state machines, we use similar hyperparameters as DeepSoftl.og Log, see aad Table In all experiments, we used 100 samples for the gradient estimation and batch size as this provided sufficient training signal. For the nations knowledge graph, we performed Bayesian tuning on the validation set, optimizing for the MRR (see Table 6).
27

---

Program Templates
The same program templates as the NTP and DeepSofiLog are used. For
Countries S1, we have
n nX,, Y) r2 X)
r [x Y) - r2(X, Z) A (2)
For Countries S2, we have [X, Y) - r2 X)
(X, Y = (2(, Z) A (2))
(X, Y) E r2(X, (z.
For Countries S3, we have (X. Y) r2(Y. X)
(X, - r2(X, Z) A (2
Y) T2(X, (r,
1 (X, Y) - r2(X, A) A r3 (A,
For nations, the following templates repeated 20 times each.
r (X,, Y) = r2(X, Y)
1 (X,Y
1 (XX,), - r2(X, A rr
For the differentiable finite state machines, we simply implement finite state in datalog. Datalog does not support functors, meaning that the finite state implementation has fixed max length on the inputs it accepts. As we only test on inputs of max length 8 this is not problem, however.
accepts(S1, S3, S4, S6, 56, S7, 58, S9) run(end_sstae _tate, S1, 53, 54, S6, 58,
run(STATE, SYMBOL,11,, 52, S3, S4, S5, 56, S8) <
run(OLDSTATE, S2, S3, S4, S5, S6, S8, -1) transition(OLDSSTTEE STATE, SYMBOL)
Regularization. The nations knowledge graph quickly exhibited overfitting. Proper regularization is often crucial to obtain competitive results on link prediction [Lacroix et 2018). As we have probabilistic model, we can simply regularize the entropy, meaning we minimize the entropy the latent random variables. In the differentiable finite state machines we regularize the neural network using weight decay.
Data License.
The countries (ODbL licence) and nations (CCO license) knowledge graphs, gram- mars (CCO license), and MNIST dataset (MIT license) all publicly available.
Compute. We performed the experiments servers with Intel 17-12700 CPU and 64GB RAM, although lower resources may suffice. No GPU or TPU compute was used. Roughly speaking, one differentiable finite state machine experiment takes 3 minutes, one countries experiment takes 3 to hours (depending on S1/S2/S3), and one nations experiment takes about hour.
Learned Rules
Some example of learned rules, for countries (S2):
neighborOf(X, Y) neighborOf(Y X)
locatedIn(X, XX, Y) <- locatedIn X, Z), locatedIn(Z, Y)
And for the nations knowledge graph:
relexports(X X, Y) < booktranslations(2 Y)
conferences(X XX, Y) + conferences(Y, X)
embassy(X, Y) warning(X, Z), commonbloc2(z.
Additional Experiments. Table we repeat the knowledge graph experiments on the Kinship and UMLS datasets. We apply the same evaluation protocol and use the dataset splits from Qu et al. [202T]. Hyperparameters are again selected by tuning on the validation MRR for the UMLS dataset. For the Kinship dataset, simply reuse these hyperparameters.
28

---

Table 5: Hyperparameters used in the countries experiment (c.f. Table DT. Identical hyperparameters are used for the three different variants (S1, S2, and S3).
Hyperparameter
Value
Optimizer
AdamW
Learning rate
0.1
Number of samples
100
Number of epochs
Batch size
Table 6: Hyperparameters used in the nations experiment (c.f. Table 1.
Hyperparameter name
Value
Optimizer
AdamW
Learning rate
0.0013
Number of samples
100
Number of epochs
2
Batch size
Gradient Clipping
0.000093
Entropy regularization
0,0000025
Max fixed-point iterations
5
C Linking Equivalence and Possible World Semanties
The probabilistic equality and possible world semantics that have been described in the main paper are orthogonal each other and can combined by having a distribution both over the facts and over equivalence relations.
P(a) Eny. an (w, R)leu T a]
For example, consider a program with the facts {r(a), r(b)} and with no rules. Now, we both impose a probability distribution on the facts {r(a) + 0.2. r(b) 0.8} and the equivalence P(a b) 0.5.
Then, if we query r(a), we get
P(r(a)) ((a b) (P(r(a)) (1- P(r(a))) P(r(a))) P(r(b)) (1 P(a = b)) P(r(a))
0.5 - (0.2 0.8 0.8) + 0.5 0.2
0.52
On the other hand, we can also interpret the equivalence as a specific low-rank parameterization of the possible world semanties.
Table Hyperparameters used in the differentiable finite state machines experiment (c.f. Table 2). Identical hyperparameters are used for the three different languages.
Hyperparameter name
Value
Optimizer
Adam
Learning rate (embeddings)
0.1
Learning rate (neural network)
0.0001
Number samples
100
Number of epochs
25
Batch size
1
Weight Decay
0.01
29

---

Table 8: Link prediction results the UMLS and Kinship knowledge graphs. Hyperparameters selected by tuning on the validation MRR, and we report the mean and standard deviation over 10
random seeds. Splits and CTP baseline results taken from Qu et al. [2021]
Datasets
Metrics
CTP
Ours
MRR
0.335
0.408
Hits 1
0.177
0.234
Kinship
Hits @
0.376
0.483
Hits @ 10
0.703
0.795
MRR
0.404
0.557
Hits 1
0.288
0.392
UMLS
Hits@3
0.430
0.666
Hits @ 10
0.674
0.880
P(a) = Eay-Pe [Pleu Fa]
By Definition
EeumPe (Feu), U (R)) a
By Theorem
= Ew [(FUw, R (UC(R) aa]
In the last line, the possible world distribution is defined such that P(w) = P(eu) when there exists ey with w F(ee) and 0 otherwise. Observe that this distribution is not factorized into independent facts, as is usual in probabilistic logic programming.
D Magic Sets Transformation
As the equality atoms do not appear any rule heads, there is no need to specialize the magic towards equality as was done by [Benedikt et al. 20188) Instead, we perform standard magic sets transformation We demonstrate this on the running example below, without differentiating between the free and bound adornments.
Example 7. We present the program transformation Mag(Sg(Re:: q), q(a, c)) of the rules in the example program P of Example We introduce the special relation magic to guard the execution of and q as the target relation. To query atom of for instance r(a, c). we simply add the fact magic(a, c) to the program and query q(a, c). Note that the magic and singularization transforms are not unique, due to the different possible orderings of atoms.
r(X, Y) magic(X, Y) A rx, Z Z2 r(Z2, Y)
magic Z1) < r(X, Y).
magic Zz, r(X, A (X. Z,) A Z
q(X, Y) + magic(X, Y) AX Y Y1)
30


Reviews:
[{"review_id": "LohGgf54iW", "reviewer": "Reviewer_FcSA", "summary": "This paper argues that the use of embedding similarity in place of equivalence in neurosymbolic models is fundamentally problematic. That is, similarity violates transitivity, which ultimately hinders learning. In contrast to existing work on probabilistic programming which use a probability distribution over possible worlds (sets of facts), the authors introduce probability distributions over equivalences of constants. They propose using a latent variable to represent the equivalence distribution and make it tractable. Experiments on two tasks show consistent improvements over baseline methods.", "questions": "1. Where exactly am I misunderstanding section 3.1? While I am able to follow the proof of theorem 2 and believe I did my due diligence in checking the details, I fail to see how this supports the paper's main claim.\n\n    - Would it be possible to include at least a summary of the proof of theorem 2 in the main text? I feel with the clarification I requested regarding this theorem, the proof would be helpful. \n\n3. While the improvements of your method over the baselines in the experiments are an *indicator* that enforcing transitivity is helpful, I feel that additional experimentation or analysis would be helpful to support your claim. That is, just reporting higher AUCs is insufficient. Can you describe the extent to which each of these tasks depends on transitivity? Can you provide example failures of the other models that are caused by a lack of transitivity? Better yet, is it possible to, for example, quantify the number of links in experiment 1 that *require* rule learning in order to be predicted correctly?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n * The explanations and definitions  provided throughout, especially in the preliminaries where they are most needed, are very clear.\n * The factorization introduced in section 4.1 is quite clever.\n * The paper is overall very well-written and well-structured.\n\n\n**Weaknesses**\n\n* Section 3.1 was somewhat difficult for me to follow. This may be related to the notation confusion regarding $x$ in example 7, which I mention in the formatting concerns. I don't really see how theorem 2 supports the paper's main contribution of showing that soft unification does not adhere to the laws of equivalence. The proof supplied in the supplementary material did not offer clarification for me. What exactly is bad about requiring embeddings to be equal? Ultimately it is this section that drops my evaluation of the paper to \"2: fair\" for clarity and significance. Ensuring that this section is extremely clear to audiences with ranging understandings (i.e., not just experts) of neuro-symbolic methods, probabilistic logic programming, etc. would be a massive improvement.\n  - I am unclear what exactly you are referring to by \"nontransitive possible worlds\" on line 156 and 161. Are they the \"possible worlds not in an equivalence relation\" mentioned on line 148? This makes Theorem 2 very unclear to me.\n  - I assume a negative fact is a falsehood, e.g., $a \\neq b$? This should be defined.\n * Similar to the above, I don't feel that the description of the experiments clearly address the research question \"does transitivity matter\".\n * The notation $e$ and $e'$ to denote equivalence relations in the Herbrand Universe and Base, respectively, was somewhat difficult for me to keep track of. Perhaps $e_u$ and $e_b$? This is a minor point and I understand that the authors may be using established notation here.", "was_revised": true, "final_justification": "Based upon the author rebuttal, I am confident that my concerns regarding clarity and accessibility of the paper will be resolved in the updated version.", "rebuttal": "We sincerely thank the reviewer for their feedback and taking the time to review our paper. We have split our answer into the two main points of concern.\n\n## Concerning Section 3.1. (Equivalence vs Soft Unification)\n\n> Section 3.1 was somewhat difficult for me to follow. [...] Ensuring that this section is extremely clear to audiences with ranging understandings (i.e., not just experts) of neuro-symbolic methods, probabilistic logic programming, etc. would be a massive improvement.\n\nTo address this concern, we reworked Section 3.1 to provide more discussion and make it more accessible. As we cannot upload a new pdf, we summarize the main points below before moving to the specific questions.\n\nThe overall goal of Section 3.1 is to show that using soft unification with embeddings is problematic, motivating the need for our new semantics. First, there is the __optimization__ perspective. It is well-known that marginals of probabilistic logic (or indeed any distribution over discrete variables) are multilinear polynomials (see e.g. [1] or [2]). This implies all optima are global, making it relatively easy to optimize neurosymbolic models based on probabilistic logic. However, by using soft unification, the model is no longer multilinear in the parameters (e.g., the embeddings), and local optima may appear. This problem was already noticed by [3].  Example 7 was an indication of this, where following the gradient moves you away from the global optimum. We have replaced the old Example 7 with the following to demonstrate these ideas more explicitly, without needing a program with rules.\n\n_Example 7_. _Consider a soft unification program where embeddings are compared using a radial basis function, as done by the Neural Theorem Prover [4]. In other words, $P_f(a\\approx b) =\\phi(d(a,b))$, where $d(a,b)$ is the distance between the constants $a$ and $b$ in the embedding space and $\\phi$ is a monotone function, typically a Gaussian.  Suppose now that we have a query whose probability is given by $(1 - P_f(a \\approx b)) (1 - P_f(a \\approx c))(1 - P_f(b \\approx c)) + P_f(a \\approx b) P_f(a \\approx c)(1 - P_f(b \\approx c)) + P_f(a \\approx b)) P_f(b \\approx c)(1 - P_f(a \\approx c))$. Under the probabilistic semantics, the probabilities $P_f(\\dots)$ are free parameters and hence this multilinear polynomial only has global optima. However, when soft unification is parameterized by embeddings, the probability of the query is computed by \n$(1-\\phi(d(a,b))) (1-\\phi(d(a,c)))(1-\\phi(d(b, c)))+\\phi(d(a, b)) \\phi(d(a, c))(1-\\phi(d(b , c)) + \\phi(d(a, b))) \\phi(d(b,c))(1-\\phi(d(a, c)))$. This has a local maximum (e.g., using $\\phi(x) = e^{-10x^2}$), because the vector space constrains the distances: $\\vert d(a, b) - d(b, c)\\rvert \\leq  d(a, c) \\leq d(a, b) + d(b, c)$._\n\nA second perspective is the __Bayesian__ one. Consider three symbols $a$, $b$, and $c$.\nThere exists no embedding of those symbols that satisfies the following nontransitive probabilities: $P(\\mathsf{a} \\approx \\mathsf{b}) = 1$, $P(\\mathsf{b} \\approx \\mathsf{c}) = 1$, and $P(\\mathsf{a} \\approx \\mathsf{c}) = 0$. Indeed, to satisfy the previous probabilities, the symbols $a$, $b$, and $c$ need to map to the same elements in the embedding space, implying an inherent transitivity (c.f. Theorem 2). Since, this nontransitive property cannot be represented by embeddings, by assigning mass to these probabilities, i.e., by setting $P(\\mathsf{a}\\approx\\mathsf{b})=1$, $P(\\mathsf{b} \\approx \\mathsf{c})=1$, and $P(\\mathsf{a} \\approx \\mathsf{c})=0$, we leak probability mass, adversely impacting uncertainty quantification.  \n\n[1] Darwiche, Adnan. \"A differential approach to inference in Bayesian networks.\" _JACM_ (2003).  \n[2] Roth, Dan, and Rajhans Samdani. \"Learning multi-linear representations of distributions for efficient inference.\" _Machine Learning_ (2009).  \n[3] de Jong, Michiel, and Fei Sha. \"Neural theorem provers do not learn rules without exploration.\" (2019).  \n[4] Rocktäschel, Tim, and Sebastian Riedel. \"End-to-end differentiable proving.\" _NeurIPS_ (2017).\n\n> I don't really see how theorem 2 supports the paper's main contribution of showing that soft unification does not adhere to the laws of equivalence.\n\nThe fact that soft unification does not adhere to transitivity (one of the laws of equivalence) is known and follows from its Definition (see lines 140-148). In contrast, Theorem 2 relates to _why_ it is problematic not to adhere to transitivity (see the previous discussion on the Bayesian perspective).\n\n> What exactly is bad about requiring embeddings to be equal?\n\nRequiring embeddings to be equal is definitely not a problem on its own. However, doing so on the probabilistic level without enforcing the same structure in the logic semantics is what leads to issues (see the previous discussion about Section 3.1).\n\n> I am unclear what exactly you are referring to by \"nontransitive possible worlds\" on line 156 and 161. Are they the \"possible worlds not in an equivalence relation\" mentioned on line 148? This makes Theorem 2 very unclear to me.\n\nWith nontransitive possible world, we mean a possible world $w$ of the soft unification program $\\mathcal{P}_{soft}$ where transitivity does not hold. For example, a possible world with $a \\approx b$ and $ b \\approx c $ but not $a \\approx c$.\n\n> I assume a negative fact is a falsehood, e.g., $a \\neq b$? This should be defined.\n\nYes, we will define this in the text.\n\n> The notation $e$ and $e’$ to denote equivalence relations in the Herbrand Universe and Base, respectively, was somewhat difficult for me to keep track of.\n\nWe will modify this notation to $e_\\mathsf{U}$ and $e_\\mathsf{B}$, respectively.\n\n## Concerning Experiments on Transitivity\n\n> I don't feel that the description of the experiments clearly address the research question \"does transitivity matter\". [...] While the improvements of your method over the baselines in the experiments are an indicator that enforcing transitivity is helpful, I feel that additional experimentation or analysis would be helpful to support your claim. That is, just reporting higher AUCs is insufficient. \nCan you describe the extent to which each of these tasks depends on transitivity? \n\nThe DeepSoftLog baseline is essentially an ablation of our method where transitivity is not enforced. So the (considerable) performance improvements over this baseline can be attributed to the addition of transitivity.\n\n> Can you provide example failures of the other models that are caused by a lack of transitivity? \n\nAn example is in the differentiable finite state machine experiment, where the symbols represent states in an automaton. Consider the following transitions between states: $a\\rightarrow b$, $c\\rightarrow d$, and $e\\rightarrow f$. Assuming we have that $b=c$ and $c=e$, it should be possible to transition $a\\rightarrow b (=c) \\rightarrow d$ and $a\\rightarrow b (=e)\\rightarrow f$. However, the latter derivation cannot be found without transitivity. This is the reason why DeepSoftLog often fails to optimize and has a large variance between experiments (c.f. Table 3).\n\n> Better yet, is it possible to, for example, quantify the number of links in experiment 1 that require rule learning in order to be predicted correctly?\n\nIn the Countries (Table 1) and differentiable automata (Table 3) experiments, rules are necessary in each query. In other words, without rule learning, the performance would be near random. In the Nations knowledge graph (Table 2), this is less drastic – hence also the more modest performance improvements.\n\n> Paper Formatting Concerns\n\nTypos have been fixed. Regarding line 150, $x$ is an element of the Herbrand universe, while $X$ is a variable."}, {"review_id": "TesAr036C5", "reviewer": "Reviewer_Qews", "summary": "The paper formalizes a new approach for soft unification that is based on defining probability distributions over equivalences between symbols. Typically, in existing neurosymbolic methods soft unification is approximate since they are typically not true equivalences but on similarity (e.g. between symbol embeddings). The paper shows that under such situations, we may run the risk that inference in such models may derive facts that may not be true under equivalence. As a consequence, learning which is based on inference as a sub-step may be biased in such models. The paper adds equivalence semantics within probabilistic logic programming. Further, they show that a factorization of a distribution defined with the proposed framework can be realized through embeddings over the symbols. An exact inference pipeline is proposed for this model that uses optimizations based on symmetries along with a simple sampling-based approximation.", "questions": "Is there a reason why only transitivity was chosen within the experiments. Of course, it is true that transitivity occurs more naturally in real-world cases, but perhaps it would have helped to demonstrate enforcing other constraints.\n\nIf the embeddings are approximate (i.e. does not have dimensionality of the full vocabulary), does the proposed method reduce to other existing approximate approaches of soft unification using similarity?", "limitations": "Mentioned adequately.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n+ The paper formalizes novel probabilistic semantics for soft unification that is a central step in Neurosymbolic learning and inference. \n+ The idea of equivalences/symmetries which has been used previously within relational models is applied in a novel setting that seems to be an interesting direction for Neurosymbolic AI.\n+ The paper is well-written and rigorous in its approach.\n+ The results show that when compared with soft unification that a lot of the other state-of-the-approaches typically perform, the probabilistic semantics over equivalences helps us enforce transitivity during learning which translates to better performance during inference.\n\n\nWeaknesses\n- While the proposed work is more general, the experiments enforce a single rule of transitivity. \n- In more general cases, is the proposed learning method scalable? It seems like the singularization to be performed for exact weighted model counting will be computationally expensive.\n- Regarding the comparison as such, it seemed to me like the proposed “exact” inference/learning method is being compared to approximate soft unification methods. In that sense, the approximate inference methods seem to be doing reasonably well it looked like in the graph benchmark at least.\n- For the factorization, in the experiments, it is mentioned that the embedding dimension is as large as the vocabulary. This would seem like a limiting factor for many practical cases as such. What happens with a smaller embedding, I assume the distribution will not be expressive enough. But maybe this trade-off is important to address through some empirical results.\n\nOverall, this seems to be a good, well-written paper that defines an important problem in Neurosymbolic models precisely and proposes novel probabilistic semantics for it.", "was_revised": true, "final_justification": "The paper separates itself from other neuro-symbolic AI models by performing inference in the presence of exact equivalence as opposed to soft unification methods. This can have impacts in several application domains where we need to add domain knowledge that needs to be strictly enforced. The experiments show the benefit of this approach compared to existing neuro-symbolic methods that only allow approximate equivalences. Overall, this seems to be a good paper that merits acceptance.", "rebuttal": "We sincerely thank the reviewer for taking the time to review our paper and providing useful feedback.\n\n> While the proposed work is more general, the experiments enforce a single rule of transitivity. [...] Is there a reason why only transitivity was chosen within the experiments. Of course, it is true that transitivity occurs more naturally in real-world cases, but perhaps it would have helped to demonstrate enforcing other constraints.\n\nThe experiments use logic programs that may include dozens of rules, not just a transitive constraint (see Appendix B). Our work focuses on transitive equivalence because its importance has not yet been established in the context of differentiable proving and rule learning. Imposing such transitivity in an efficient fashion is nontrivial and required rethinking the prevailing probabilistic semantics of logic programming.\n\n> In more general cases, is the proposed learning method scalable? It seems like the singularization to be performed for exact weighted model counting will be computationally expensive.\n\nSingularization itself is a very efficient program transformation step that can be done in linear time in the number of rules. On the other hand, the weighted model counting step is \\#P-hard, and hence faces scalability limitations. Notice that the latter is a challenge faced by every sufficiently expressive probabilistic programming language, and we have an approximation technique (c.f. lines 240-250) to keep the experiments reasonably fast.\n\n> Regarding the comparison as such, it seemed to me like the proposed “exact” inference/learning method is being compared to approximate soft unification methods. In that sense, the approximate inference methods seem to be doing reasonably well it looked like in the graph benchmark at least.\n\nWe are not sure we understand this point. Both our experiments as well as all the baselines use approximate inference (c.f. lines 240-250 for our approximation strategy). Indeed, exact inference is \\#P-hard in the size of the ground program (which can grow very quickly due to the use of templates in the experiments) and hence usually not feasible.\n\n> For the factorization, in the experiments, it is mentioned that the embedding dimension is as large as the vocabulary. This would seem like a limiting factor for many practical cases as such. What happens with a smaller embedding, I assume the distribution will not be expressive enough. But maybe this trade-off is important to address through some empirical results.\n\nSetting the embedding dimensionality to the vocabulary size can indeed become problematic for large programs. However, in these cases one can just take a smaller embedding dimension. If expressivity is a concern, the parameter count can be increased independently of vocabulary size with hierarchical mixtures without affecting tractability. In our experiments, the embedding dimensionality never was an issue, which is why we did not explore it further.\n\n> If the embeddings are approximate (i.e. does not have dimensionality of the full vocabulary), does the proposed method reduce to other existing approximate approaches of soft unification using similarity?\n\nNo, it does not. The embeddings are only approximate in the sense that they limit the potential distributions over equivalence relations (in favour of tractability for certain queries). Further restricting expressivity by reducing the embedding dimensionality has no impact on the semantics. More specifically, transitivity is always guaranteed, and hence there cannot be a reduction to soft unification (which violates transitivity)."}, {"review_id": "afo8CJ8h1N", "reviewer": "Reviewer_z1So", "summary": "The paper proposes a different learnable approach to probabilistic logic programming. Commonly for both prior and this work, the probability of a ground atom is defined by marginalizing over all possible words. In prior work the possible worlds include all possible similarity facts a \\sim b, and the probability of each similarity fact is determined independently based on the similarity of embeddings for a and for b. Some sampled possible worlds can thus lack a proper transitive equivalence between constants. This work proposes to instead have every possible world defined as a well-defined equivalence relation. The distribution over such worlds is defined by a probability vector for each constant c that defines the probability of c belonging to each equivalence cluster. The paper discusses how to adapt inference engines for inference and learning with this new equivalence-based possible world distribution. Strong empirical results confirm the effectiveness of the proposed method.", "questions": "- Can you elaborate “even though in the global optimum we have P_f (y \\sim z)=0.” in line 155? \n- In the proposed approach every constants also has an embedding. Can you elaborate the difference in how embeddings are used in your work and in the prior similarity-based approaches?", "limitations": "I'd like to see more discussion on whether inference/learning becomes harder with the proposed approach compared to prior work.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper tackles an important issue in an original and principled way. I’m not an expert in logic programming, so some parts were very hard to follow. In particular, the crux of argument about the deficiencies of the embeddings-based in approach in lines 150-155 was lost on me. I’d like to see the notion of “global optimum” to be better explained there. Also it was not clear how much harder/easier the inference and learning are in the proposed approach compared to prior work. \n\nOverall the exposition is very formal and abstract and hard to follow, but that is a common issue for logic programming papers.", "was_revised": true, "final_justification": "I expect the final revision of the paper to address the clarity concerns that I expressed in my review.", "rebuttal": "We sincerely thank the reviewer for their feedback and taking the time to review our paper.\n\n> In particular, the crux of argument about the deficiencies of the embeddings-based in approach in lines 150-155 was lost on me. I’d like to see the notion of “global optimum” to be better explained there. [...] Can you elaborate “even though in the global optimum we have P_f (y \\sim z)=0.” in line 155?\n\nWe have reworked Section 3.1 to improve clarity and accessibility to a broader audience. The overall goal of Section 3.1 is to show that using soft unification with embeddings is problematic, motivating the need for our new semantics. From the __optimization__ perspective, it is well-known that marginals of probabilistic logic (or indeed any distribution over discrete variables) are multilinear polynomials (see e.g. [1] or [2]). This implies all optima are global, making it relatively easy to optimize neurosymbolic models based on probabilistic logic. However, by using soft unification, the model is no longer multilinear in the parameters (e.g., the embeddings), and local optima may appear. This problem was already noticed by [3].  Example 7 was an indication of this, where following the gradient moves you away from the global optimum. We have replaced the old Example 7 with the following to demonstrate these ideas more explicitly, without needing a program with rules.\n\n_Example 7_. _Consider a soft unification program where embeddings are compared using a radial basis function, as done by the Neural Theorem Prover [4]. In other words, $P_f(a\\approx b) =\\phi(d(a,b))$, where $d(a,b)$ is the distance between the constants $a$ and $b$ in the embedding space and $\\phi$ is a monotone function, typically a Gaussian.  Suppose now that we have a query whose probability is given by $(1 - P_f(a \\approx b)) (1 - P_f(a \\approx c))(1 - P_f(b \\approx c)) + P_f(a \\approx b) P_f(a \\approx c)(1 - P_f(b \\approx c)) + P_f(a \\approx b)) P_f(b \\approx c)(1 - P_f(a \\approx c))$. Under the probabilistic semantics, the probabilities $P_f(\\dots)$ are free parameters and hence this multilinear polynomial only has global optima. However, when soft unification is parameterized by embeddings, the probability of the query is computed by \n$(1-\\phi(d(a,b))) (1-\\phi(d(a,c)))(1-\\phi(d(b, c)))+\\phi(d(a, b)) \\phi(d(a, c))(1-\\phi(d(b , c)) + \\phi(d(a, b))) \\phi(d(b,c))(1-\\phi(d(a, c)))$. This has a local maximum (e.g., using $\\phi(x) = e^{-10x^2}$), because the vector space constrains the distances: $\\vert d(a, b) - d(b, c)\\rvert \\leq  d(a, c) \\leq d(a, b) + d(b, c)$._\n\n[1] Darwiche, Adnan. \"A differential approach to inference in Bayesian networks.\" JACM (2003).  \n[2] Roth, Dan, and Rajhans Samdani. \"Learning multi-linear representations of distributions for efficient inference.\" Machine Learning (2009).\n\n> In the proposed approach every constant also has an embedding. Can you elaborate the difference in how embeddings are used in your work and in the prior similarity-based approaches?\n\nBoth our work and previous research associate embeddings with symbols. However, we differ in the logic semantics associated with these embeddings. For example, what does it mean for the symbol $\\mathtt{stop}$ of a logic formula $\\mathtt{redlight} \\rightarrow \\mathtt{stop}$ to have an embedding $[0.130, 0.341, 0.023, …]$? Prior work, in particular, soft unification, compared symbols in the embedding space to assess how likely it is for two symbols to be \"equivalent\". On the other hand, we see embeddings as a latent random variable in a distribution over programs (see also Figure 1).\n\n> I'd like to see more discussion on whether inference/learning becomes harder with the proposed approach compared to prior work.\n\nWe have added some more discussion on these questions in Section 5. \n(_On inference_) Firstly, from a basic complexity view, nothing changes: inference is still \\#P-hard. Furthermore, elementary ground queries (such as whether two atoms are equal) remain tractable through our choice of factorization (c.f. Section 4.1). In practice, the most substantial difference of enforcing transitivity for exact inference is that the size of the ground program may increase. We partially mitigate this by using singularization and magic program transforms (c.f. Section 5).\n(_On Learning_) As optimization in our approach is multilinear and does not contain local optima, learning is easier compared to prior methods (c.f. the previous discussion about Sec. 3.1). For example, the NTP baseline uses 100 epochs for the experiments of Table 2, while we only need 1 epoch to converge."}, {"review_id": "fOIXlXeyD7", "reviewer": "Reviewer_uR2S", "summary": "Soft unification has been used in neursoymbolic learning as a way to translate the symbolic comparison between symbols into an embedding space comparison. However, soft unification exploits symmetry, rather than equivalence, which can lead to facts being derived that cannot be true under equivalence (violating transitivity). This paper proposes a probabilistic semantics of equivalence for logic programming. In this new semantics, symbol partitions (groupings) can be learned, and transitivity allows new facts over the grouped symbols to be derived. The evaluation demonstrates that this approach generally leads to higher AUPRC, MRR, and HITS@m compared to the baselines across several benchmarks.", "questions": "- How does this new learning algorithm compare to DeepSoftLog on some of its scalability benchmarks, especially since this work is directly building on it? I would have liked to see a comparison for MNIST-Addition and Visual Sudoku. Even if the new notion of equivalence doesn’t improve results, it would be helpful to show whether there is any efficiency improvement or penalty, or any change in accuracy.\n- Other than isIn/locatedIn, what are other examples of equivalences that were exploited in the evaluated benchmarks, resulting in performance improvements?\n- What do the authors see as the  real-world application of this work? How does this work fit in with foundation models, which could likely eliminate the need for training the neural network?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- This paper was well-written and easy to follow. The running examples were helpful in understanding the problem and proposed solution.\n- The problem is well-motivated. This paper clearly outlines the weaknesses of prior work that reasons on embeddings in logic programs.\n- The experiments demonstrate that exploiting symmetries between equivalent symbols substantially improves performance, especially for the differentiable automata benchmark.\n\n**Weaknesses:**\n- There are no experiments to compare the training efficiency of the different approaches. Some analysis (such as Figure 2 in [1]) would have been useful.\n- This paper seems to be a direct improvement on DeepSoftLog, but several benchmarks from the DeepSoftLog paper were omitted, including MNIST-addition and visual sudoku classification.\n- Minor comments: \n    - Define “symbol” upfront. I have seen some neurosymbolic literature that uses “symbol” to mean the likely discrete neural network prediction. But this paper is using it to mean the name of a rule.\n    - Line 59: “First, formalize” -> “First, we formalize”\n    - Line 127: $P_ex$ -> $P_{ex}$\n\n[1] Differentiable Reasoning on Large Knowledge Bases and Natural Language, AAAI 2020", "was_revised": true, "final_justification": "After the rebuttal, the authors provided some insight into the runtime improvements of the proposed technique over the baselines. Additional information was provided about why equivalence is useful in some of the benchmarks. I can see the significance of this work in the field of neurosymbolic logic programming, but I am still at the borderline in terms of its general applicability.", "rebuttal": "We sincerely thank the reviewer for taking the time to review our paper and providing useful feedback.\n\n> There are no experiments to compare the training efficiency of the different approaches.\n\nOur experiments indeed focus on accuracy improvements, rather than runtime performance. However, the runtimes of our experiments are generally faster than those of baselines, such as DeepSoftLog. For example, for the Countries S3 runs, the runtime was on average two hours per experiment, while for DeepSoftLog, this was five hours. Moreover, DeepSoftLog cannot handle e.g. the Nations experiment, due to scalability issues.\n\n> How does this new learning algorithm compare to DeepSoftLog on some of its scalability benchmarks, especially since this work is directly building on it? I would have liked to see a comparison for MNIST-Addition and Visual Sudoku.\n\nThe MNIST-addition and Visual Sudoku experiments are less interesting in our setting as they are ground problems over linear arithmetic. Furthermore, the MNIST-addition encoding of DeepSoftLog does not fully use soft unification. So performing this experiment using our approach would give functionally identical results to DeepSoftLog.\n\nWe have included experiments beyond the scalability limits of DeepSoftLog, namely on the Nations knowledge graph. Below, we furthermore repeated this last experiment on two other knowledge graphs (UMLS and Kinship), which are further out of reach for DeepSoftLog.\n\n| Datasets   | Metrics  | CTP   | Ours   |\n|------------|----------|--------|--------|\n| **Kinship**| MRR      | 0.335  | **0.408** |\n|            | Hits@1   | 0.177  | **0.234** |\n|            | Hits@3   | 0.376  | **0.483** |\n|            | Hits@10  | 0.703  | **0.795** |\n| **UMLS**   | MRR      | 0.404  | **0.557** |\n|            | Hits@1   | 0.288  | **0.392** |\n|            | Hits@3   | 0.430  | **0.666** |\n|            | Hits@10  | 0.674  | **0.880** |\n\n> Define “symbol” upfront. I have seen some neurosymbolic literature that uses “symbol” to mean the likely discrete neural network prediction. But this paper is using it to mean the name of a rule.\n\nIn our context, a symbol is a constant in a Datalog program (i.e. an element of the Herbrand universe, see the second paragraph of Section 2). The outputs of a neural network can indeed be used as a distribution over symbols for a neurosymbolic model . In our work, however, symbols are embedded into a vector space.\n\n> Other than isIn/locatedIn, what are other examples of equivalences that were exploited in the evaluated benchmarks, resulting in performance improvements?\n\nAnother example is in the differentiable finite state machine experiment, where symbols represent states in an automaton. Now, consider the following transitions between states: $a\\rightarrow b$, $c\\rightarrow d$, and $e\\rightarrow f$. Assuming we have that $b=c$ and $c=e$, it should be possible to transition $a\\rightarrow b (=c) \\rightarrow d$ and $a\\rightarrow b (=e) \\rightarrow f$. However, the latter derivation cannot be found without transitivity. Table 3 demonstrates that the more faithful modelling of automata behaviour has major performance implications. More generally, this problem is encountered in any task where true equivalence is present (in this example, automata states).\n\n> What do the authors see as the real-world application of this work? How does this work fit in with foundation models, which could likely eliminate the need for training the neural network?\n\nAlthough our contribution is on the more fundamental side, we hope that it will enable future applications where symbolic and neural structures are jointly optimized, leading to models with interpretable reasoning traces that are critical in highly regulated domains (e.g., finance). Moreover, neurosymbolic models can provide formal guarantees about their behaviour, as previously demonstrated on applications with safety requirements (e.g., self-driving [1] or language model toxicity [2]). \n\nFoundation models have indeed altered the conventional machine learning paradigm, but still face limitations in these aspects. Furthermore, there are still questions about how far out-of-distribution foundation models can perform compositional reasoning (as a symbolic model can). For example, Yue et al. [3] argue that the currently popular RL-trained reasoning models do not fundamentally expand their capabilities beyond the pre-training distribution, and Hazra et al. [4] argue that foundation models still struggle with computationally hard inferences.\n\n[1] Giunchiglia, Eleonora, et al. \"ROAD-R: the autonomous driving dataset with logical requirements.\" _Machine Learning_ (2023).  \n[2] Ahmed, Kareem, Kai-Wei Chang, and Guy Van den Broeck. \"A pseudo-semantic loss for autoregressive models with logical constraints.\" _NeurIPS_ (2023).  \n[3] Yue, Yang, et al. \"Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model?.\" _ICML AI4Math workshop_ (2025).  \n[4] Hazra, Rishi, et al. \"Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition. _COLM_ (2025)."}]

Author rebuttal:

Meta-review: Summary: This paper proposes a new probabilistic semantics for equivalence in logic programs, arguing that enforcing transitivity resolves key optimization issues in neurosymbolic learning. The proposed method demonstrates strong performance on several benchmarks.

Strengths: Reviewers unanimously agreed that the paper is well-written and well-motivated, tackling an important problem in neurosymbolic AI with a principled and clever technical approach.

Weaknesses: The primary initial concern raised by several reviewers was the lack of clarity in the section motivating the work, specifically regarding the negative consequences of violating transitivity in soft unification. It was well addressed during rebuttal.

Reasons for Decision: The paper has novel and sound technical contribution, strong empirical results. And the authors' rebuttal successfully clarified the core motivation and resolved the reviewers' main concerns about the pitfalls of non-transitive similarity in neurosymbolic models.

Discussion Process: The authors provided a revised explanation for their motivation, focusing on how soft unification introduces local optima, which convinced initially skeptical reviewers and led to a strong consensus for acceptance.
Decision: Accept (poster)