Learning First-Order Rules with Differentiable Logic Program Semantics

1 Introduction

Nowadays, knowledge discovery is an important technique for people acquiring knowledge from either large or complex realistic datasets. Relational data mining constructs a humanreadable representation from relational datasets. An explicit logic program (LP) can be a clear explanation to complex, incomplete, or noisy relational datasets due to the limitations of current techniques, especially in the datasets from business,

∗Contact Author

Full version available at https://arxiv.org/abs/2204.13570

biology, and medicine. However, learning high accuracy LPs from realistic relational datasets is still a hardcore problem in the field of machine learning.

Inductive logic programming (ILP) is firstly proposed by [Muggleton, 1991] as a combination of inductive learning and logic programming technique has contained several methods. The purely symbolic ILP methods [Muggleton et al., 2012] learning LPs typically support lifelong learning and have more explainability [Cropper et al., 2020]. However, some purely symbolic approaches fail in ambiguous realistic facts. By employing neural networks (NNs), differentiable ILP models generate explicit logic rules in a fast and precise manner from realistic relational facts. However, NNbased ILP models usually require many examples [Dong et al., 2019] to learn concepts, while symbolic ILP methods only need a few examples [Cropper et al., 2020].

In this paper, we propose a differentiable ILP method called differentiable first-order rule learner (DFOL), which generates first-order LPs from positive examples and background assumptions without logic templates. In DFOL, a novel propositionalization method transfers relational facts into NN-readable data, i.e., vector pairs representing interpretation pairs. Besides, the matrix embeddings of LPs are regarded as the trainable parameters in NNs. Based on the differentiable immediate consequence operator and the forwardchained format of LPs, we design some differentiable constraint functions to guide the NNs to find the correct embeddings of LPs. Finally, DFOL demonstrates a high degree of interpretability as the parameters in NNs can be decoded to human-readable symbolic rules. Simultaneously, the correct symbolic rules can be encoded to the fixed parameters in NNs to facilitate the training process.

The main contributions are summarized below: (1) A flexible, precise, fast, and robust differentiable first-order rule learning model is proposed. (2) The proposed model is interpretable. We can not only extract symbolic LPs from the model but also embed LPs into NNs. (3) We demonstrate that our method outperforms the baselines on most datasets, including small ILP datasets and large knowledge bases.

RelatedWork. Neuro-symbolic models have been focused on over the past decades. For learning propositional LPs, d'Avila Garcez et al. [2001] and Lehmann et al. [2010] designed algorithms to extract propositional LPs from NNs. On the other hand, Gao et al. [2021] generated propositional LPs using NNs from input-output pairs of the immediate consequence operator of LPs by making the symbolic method proposed by Inoue et al. [2014] be differentiable. However, compared with first-order LPs, propositional LPs have less ability to describe relational facts. For first-order LPs, the similar work includes [Evans et al., 2021; Evans and Grefenstette, 2018; Rockt¨aschel and Riedel, 2017; Sourek et al., 2018]. In their models, the explicit LPs are learned based on the given templates. These models need to learn the weights given rules or fill the predicates in rule templates. However, we construct LPs without any explicit templates but follow the forward-chained format. Thus, DFOL is able to find the correct rules in a flexible way, which means that we do not need any prior knowledge about the tasks, and the generated LPs may have more diverse forms than those generated from strongly biased templates. From the perspective of the representations of LPs, Qu et al. [2021] regarded LPs as latent variables. They developed an EM-based algorithm for extracting LPs through a rule generator and a reasoning predictor. Kaur et al. [2019] regarded a rule as a lifted random walk. In contrast to them, DFOL uses small matrix embeddings to encode LPs. Hence, with the help of the differentiable semantics of LPs, NNs can be adopted in DFOL to search the embeddings fastly and robustly. When adopting NNs to get LPs, Yang et al. [2017] used differentiable operations to learn the embeddings of LPs. However, the embeddings of LPs in DFOL are more interpretable, and we do not need any algorithms to transfer subsymbolic matrices into symbolic LPs. CILP++ proposed by Franc¸a et al. [2014] uses the bottom clauses propositionalization method and threelayer NNs to imitate the immediate consequence operator of LPs. However, CILP++ cannot be interpreted into symbolic LPs directly. Similarly, Teru et al. [2020] and Hohenecker and Lukasiewicz [2020] used embedding methods to perform relation prediction tasks, which are also induction tasks but do not generate explicit LPs as the results. Excepting these induction tasks, d'Avila Garcez and Zaverucha [1999] and Serafini and d'Avila Garcez [2016] considered deduction tasks with NNs and pre-defined LPs.

2 Preliminaries

We recall the concepts of LPs, ILP, propositionalization methods, and differentiable semantics of LPs in this section.

2.1 Logic Programs

A (definite) LP P consists of several rules, and each rule r is described as: αh ← α1∧α2 · · ·∧αn (n ≥ 0), where αh is the head atom denoted as head(r); αi's (0 ≤ i ≤ n) are the body atoms, and the conjunction α1 ∧α2 · · · ∧αn is the body of r. The set of all body atoms of a rule r is denoted as body(r). A set of rules with the same head atom αh called a same head logic program (SHLP): αh ← β1, αh ← β2, ..., αh ← βm, can be identified with a rule of the form: αh ← β1 ∨ β2 ∨ . . . ∨ βm, where each βi is the body of the i-th rule and β1 ∨ β2 ∨ . . . ∨βm is a disjunction of conjunctions of literals, i.e., a disjunction normal form formula. In first-order LPs, each atom α is a tuple p(t1, t2, . . . , tn), where p indicates n-ary predicate and t1, t2 . . . , tn are terms, and a term is either a variable or a constant. When an atom has no variable, the atom is a ground atom. A ground rule is derived based on substitutions, where all variables are replaced by constants. We use uppercase letters for variables and lowercase letters for constants. Let B be a Herbrand base, including all ground atoms, and an interpretation I is a subset of B. For an LP P and an interpretation I, the immediate consequence operator TP : 2B → 2B [Van Emden and Kowalski, 1976] describes the rules with interpretations: TP (I) = {head(r) | r ∈ g(P), body(r) ⊆ I}, where g(P ) is the ground LP based on P . Hence, given an interpretation I as the current state, TP (I) is regarded as an interpretation as the next state, which is the set of ground atoms that are derived from the rules of P under the condition that the atoms in I are true. A forward-chained format [Kaminski et al., 2018] usually governs the format of an LP, which specifies that the body of rules should satisfy that the variables in the head atom are connected by a binary atomic chain:

The variable depth indicates the number of variables not appearring in the head atom. For example, the variable depth is n in the rule (1).

2.2 Inductive Logic Programming and Propositionalization

An ILP task aims at generating an LP P headed by a target atom αt given a tuple (B, P, N). Let pt denote a target predicate; B is a set of ground atoms called background assumptions; P is a set of positive ground atoms, taken from the ground of the target atom; N is a set of negative ground atoms, taken outside the ground of the target atom. Formally, a solution P of an ILP task is:

When learning first-order LPs, the propositionalization method [Kramer et al., 2001] is an effective way to transform relational data into attribute-valued data. After applying propositionalization methods, we can use NNs to process the attribute-valued data and learn LPs from the relational facts. In [Franc¸a et al., 2014], the propositionalization method transfers relational facts to unground atoms with Boolean values. These unground atoms with values are called first-order features or features for short.

2.3 Differentiable Semantics of Logic Programs

In this section, we show the matrix representations and differentiable semantics of LPs. Let P be an SHLP with a head atom αh, n different body atoms, and m different rules. Then P is represented by an SH matrix MP ∈ [0, 1]m×n . Each element akj inMP is defined as follows [Gao et al., 2021]:

1. akji = li, where li ∈ (0, 1) and ∑ps=1 ls = 1 (1 ≤ i ≤ p, 1 ≤ ji ≤ n, 1 ≤ k ≤ m), if the k-th rule is αh ← αj1 ∧ · · · ∧ αjp ;
2. akh = 1, if the k-th rule is αh ←αh;
3. akj = 0, otherwise.

In fact, each row in MP corresponds to a rule in P, and each non-zero value in a row of MP corresponds to a body atom

Algorithm 1 The propositionalization method in DFOL

Input: A variable set V = {X, Y, V1, V2, . . . , Vd} with the variable depth d; target atom αt, e.g., binary predicate pt(X, Y ) or unary predicate pt(X); body features set PF ; training positive examples P and training fact set F .

Output: A trainable dataset T.

• 1: (Preparation Process)
• 2: Let X,Y,V1,V2, . . . , Vd represent the domains of variables X, Y, V1, V2, . . . , Vd.
• 3: If the target predicate pt is binary, then for each positive example pt(o1, o2) ∈ P, add o1 and o2 to the sets X and Y, respectively. Besides, add all entities in F to the sets V1,V2, . . . ,Vd. If pt is unary, for each positive example pt(o1) ∈ P, add o1 to the set X. Besides, add all entities in F to the sets Y, V1, V2, . . . , Vd.
• 4: (Generation Process)
• 5: Calculate the set S with all substitutions: S = X×Y× V1 ×V2 × · · · ×Vd.
• 6: for each θk={xk/X, yk/Y, vk 1 /V1, . . . , vk d /Vd} ∈ S do
• 7: Initialize that vki = 0 and vko = [0]. Under the current substitution θk, for each αj ∈ PF , vki [j] = 1 if g(αj) ∈ F; Then vko = [1] if g(αt) ∈ P. Next, add the pair of interpretation vectors (vki , vko ) to T .
• 8: end for
• 9: (Examination Process)
• 10: For each data in T, delete the data (vki , vko ) iff vki = 0.
• 11: Discard the m-th body feature and the corresponding values in all input interpretation vectors iff for all k ∈ [1, |T |], vki [m] = 0 (m ∈ [1, |PF |]) holds.
• 12: return T

in the corresponding rule in P. Example 1 of Appendix A shows the SH matrix corresponding to an SHLP. Let M[k, ·] and M′ [k, ·, ·] denote the k-th row in the matrix M and k-th matrix of the three-dimensional tensor M′ , respectively. Moreover, an interpretation vector v = {a1, . . . , an}T represents an interpretation in the vector space. If the Boolean value of αk is True, then ak = 1; otherwise, ak = 0. We also use v[k] to denote the k-th element in the vector v. Then, the immediate consequence operator can be represented in the vector space by Equation (2a) [Sakama et al., 2021]. When x ≥ 1, then the threshold function θ(x) = 1; otherwise, θ(x) = 0. To employ an NN to learn the SH matrix of an LP, a differentiable logic semantics used in [Gao et al., 2021] replaces the logical or operator with the product t-norm and uses the differentiable function ϕ(x - 1) in Equation (2b) to replace the θ(x) function. The hyperparameter γ controls the slope similarity between the functions ϕ and θ.

3 ANeural Network-Based Rule Learner

3.1 Propositionalization

In this section, we describe the propositionalization method in Algorithm 1. We follow the Closed-World Assumption

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

0

j

c

9

q

U

2

J

+

d

m

P

o

A

T

w

>

C

n

V

D

S

g

N

B

E

O

W

Q

y

r

Z

v

M

z

7

/

Y

X

K

F

R

I

u

L

8

k

G

5

3

f

H

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

G

2

v

T

z

E

B

Z

3

L

r

P

q

O

X

7

W

D

C

U

>

A

n

c

d

V

N

S

8

J

/

9

0

k

m

H

o

u

Q

+

g

j

F

I

M

p

K

5

R

Y

y

w

f

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

W

f

H

F

y

r

u

c

U

K

S

d

o

7

q

j

A

R

w

>

B

+

V

N

8

E

3

/

G

v

X

Z

I

n

k

L

Q

D

m

0

Y

C

2

O

p

g

P

z

J

T

5

M

9

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

9

r

R

U

z

u

Q

X

I

+

E

C

H

B

0

/

k

5

d

w

>

A

n

c

Z

D

L

S

N

F

Y

V

p

K

3

o

v

y

G

8

m

T

M

f

P

2

W

J

q

j

7

g

O

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

U

N

y

E

Y

I

2

0

7

Q

R

n

u

3

X

F

A

>

B

c

d

V

D

L

S

g

O

r

f

9

o

P

K

G

J

H

m

M

k

Z

5

W

+

v

T

8

q

p

j

w

z

/

C

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

2

J

v

P

G

8

c

A

q

d

3

Z

5

M

L

w

o

>

B

V

D

S

g

F

T

X

7

W

+

I

y

u

z

C

f

m

N

O

j

k

Q

/

0

Y

n

R

p

r

H

E

U

K

9

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

o

K

G

y

I

T

g

f

5

+

v

D

C

N

R

>

A

B

n

c

d

V

S

w

M

E

J

2

X

7

U

8

m

W

0

Y

H

k

3

j

Z

F

P

q

L

/

z

O

9

u

r

Q

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

o

K

G

y

I

T

g

f

5

+

v

D

C

N

R

>

A

B

n

c

d

V

S

w

M

E

J

2

X

7

U

8

m

W

0

Y

H

k

3

j

Z

F

P

q

L

/

z

O

9

u

r

Q

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

o

K

G

y

I

T

g

f

5

+

v

D

C

N

R

>

A

B

n

c

d

V

S

w

M

E

J

2

X

7

U

8

m

W

0

Y

H

k

3

j

Z

F

P

q

L

/

z

O

9

u

r

Q

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

C

c

q

d

X

g

0

B

T

2

7

N

Z

f

K

3

I

n

Q

>

A

V

S

w

M

E

J

+

R

U

9

k

Y

F

L

r

o

y

W

v

u

/

H

5

8

G

D

p

m

z

j

P

O

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

/

M

g

D

G

L

V

y

w

q

S

Z

9

v

m

H

8

>

A

B

7

X

c

N

E

J

3

W

O

Y

0

p

r

o

F

+

U

k

u

T

R

d

2

Q

I

n

K

5

j

f

z

P

C

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Q

9

z

U

J

/

7

O

P

S

T

R

f

d

X

E

o

>

A

B

n

c

V

N

8

3

r

q

L

0

m

k

M

F

W

y

2

p

Z

I

C

j

Y

u

+

g

H

G

D

w

5

v

K

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

/

K

X

+

Z

o

r

z

N

c

9

F

Q

C

u

g

R

H

d

Y

>

A

D

V

J

S

B

E

O

2

W

q

v

j

G

I

n

M

5

y

T

0

f

8

k

3

p

L

U

P

7

m

w

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

R

5

Q

+

8

n

z

Y

N

7

L

U

B

V

d

H

w

K

Z

c

>

A

3

S

E

r

q

/

9

I

v

g

G

P

O

D

0

m

k

J

C

j

T

X

W

M

u

2

p

o

y

F

f

<

l

f

J

u

L

+

K

T

N

P

D

S

Y

>

3

c

V

8

E

U

r

/

j

W

y

C

p

5

I

M

F

7

0

o

2

m

Z

9

z

H

X

w

Q

k

O

d

G

R

g

n

a

t

e

x

i

s

h

1

_

b

6

4

=

"

v

A

B

q

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

7

v

Q

T

9

S

8

J

o

z

n

A

P

M

p

g

2

L

d

E

>

B

3

c

V

N

U

r

q

/

0

G

R

K

O

j

w

m

k

I

C

X

W

Y

Z

H

+

F

u

y

f

5

D

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

F

E

3

L

M

Q

G

S

9

u

B

R

X

A

Z

j

O

z

g

8

>

c

V

N

J

U

r

q

/

0

m

k

7

o

W

y

2

p

I

d

P

C

Y

+

f

H

n

D

w

T

v

5

K

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

o

y

m

P

T

n

W

3

C

M

+

0

/

c

q

w

E

>

A

B

H

V

D

L

g

J

O

z

F

I

9

j

R

Y

N

U

k

Z

d

2

G

v

r

S

p

u

f

7

5

8

K

X

Q

h

1

_

b

6

4

=

"

S

n

Y

Q

M

9

K

q

m

d

y

E

3

C

+

L

w

>

A

B

H

c

V

D

T

g

J

O

z

F

I

j

R

N

U

k

Z

2

/

P

G

W

v

r

p

u

f

7

5

8

o

X

0

<

l

a

t

e

x

i

s

I

g

R

G

P

K

C

j

z

X

W

Y

m

H

O

2

+

f

n

p

Q

T

k

L

5

w

y

o

u

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

M

Z

A

B

U

v

0

D

F

d

E

>

7

3

c

V

N

S

8

J

r

q

/

9

k

L

5

w

y

o

u

0

D

F

d

E

>

7

3

c

V

N

S

8

J

r

q

/

9

I

g

R

G

P

K

C

j

z

X

W

Y

m

H

O

2

+

f

n

p

Q

T

4

=

"

M

Z

A

B

U

v

<

l

a

t

e

x

i

s

h

1

_

b

6

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

r

3

k

E

L

f

8

D

B

5

A

I

X

7

z

G

v

U

>

n

c

d

V

N

S

w

M

J

2

+

T

C

R

m

W

q

P

H

j

Z

K

F

/

O

9

Y

g

u

0

o

y

Q

p

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

M

Z

A

B

U

v

0

D

F

d

E

>

7

3

c

V

N

S

8

J

r

q

/

9

I

g

R

G

P

K

C

j

z

X

W

Y

m

H

O

2

+

f

n

p

Q

T

k

L

5

w

y

o

u

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

M

Z

A

B

U

v

0

D

F

d

E

>

7

3

c

V

N

S

8

J

r

q

/

9

I

g

R

G

P

K

C

j

z

X

W

Y

m

H

O

2

+

f

n

p

Q

T

k

L

5

w

y

o

u

that any example that does not appear in the set P is in the set N. The training fact set F includes training positive examples and training background assumptions. Assume that each predicate in a task is either binary or unary. By scanning the dataset once, the number of binary predicates nb and the number of unary predicates nu can be determined. When the body of a rule includes the target atom, the rule is a tautology, which we discard when describing relational facts. For generating an SHLP P headed by a target atom, the set of possible body features PF includes all possible binary and unary atoms except the target atom. Then, we have |PF | = A(|V | , 2) × nb + |V | × nu -1, where A(|V | , 2) is the number of arrangements of 2 items from |V | variables.

After the propositionalization, the relational facts are transformed into pairs of interpretation vectors (vi, vo). The features in each vi are considered as valid features, and let C represent |vi|. An input interpretation vector vi corresponds to Ii, which includes all the values of the valid body features in P. An output interpretation vector vo corresponds to Io, which determines the value of the head feature in the SHLP P. Example 2 of Appendix A under the predecessor (pre) relation illustrates the proposed propositionalization method.

We analyze the correctness of the propositionalization method as follows: In fact, if all the ground body atoms in the LP P describing a relational dataset are satisfied under a substitution θ, the Boolean value of the ground head atom under θ must be True. After applying all possible substitutions on all first-order features for a relation dataset, we can generate pairs of interpretations (Ii, Io) that correspond to interpretation vectors (vi, vo) and satisfy the relation Io = TP (Ii). Therefore, with the help of the robustness of NNs, we can learn the most important body features when the target feature is True. Moreover, the complexity of the propositionalization method is O(|S| × |PF |), where S is defined in Algorithm 1.

3.2 The Neural Networks in DFOL

In this section, we describe the proposed NNs and constraint functions depicted in Figure 1. Taking the training data (vi, vo) ∈ T as the input, an NN learns the SH matrix MP encoding an LP P. The LP P meets the forward-chained format described in the rule (1) and the immediate consequence operator Io = TP (Ii), where Ii and Io correspond to vi and vo, respectively. First, we use a matrix MSP ∈ [0, 1]m1×C as a trainable tensor to encode P, where m1 is a hyperparameter describing the number of logic rules. Besides, we use MAP ∈ [0, 1]m2×na×C as another trainable tensor to encode P, where m2 and na are hyperparameters. Then, we define the merge operation and concatenation operation as follows:

where tensors in the arguments of concat function are joined along the vertical dimension. Besides, MA′ P ∈ [0, 1]m2×C and MP ∈ [0, 1]m×C , where m = m1 +m2. We illustrate the merge and concat functions in Example 3 of Appendix A. We replace the immediate consequence operator of P with a differentiable inference and define an inference loss as follows:

where the activation function ϕ is defined in Equation (2b). The function H denotes the binary cross-entropy function. The symbol ˜∨ denotes the differentiable fuzzy or operation [H´ajek, 1998]. Compared with other fuzzy logic semantics, we use product t-norm as the fuzzy logic semantics in DFOL for avoiding a zero gradient [Evans and Grefenstette, 2018]:

Now, we analyze the roles of the tensor MAP . Compared with MSP , MAP has more parameters. Besides, the merge operation keeps the numbers of columns including the non-zero values fromMAP [k, ·, ·] toMA′ P [k, ·]. Thus, whenMA′ P [k, ·] encodes a correct rule rk headed by the target atom, the rows in the matrix MAP [k, ·, ·] have the opportunity to represent rules headed by auxiliary predicates [Muggleton et al., 2015]. The body of a rule headed by an auxiliary predicate may include a part of the body atoms that appear in the rule rk. Hence, the matrix MAP boosts the training process. Example 4 of Appendix A describes the process of auxiliary predicate invention. Hence, the parameters m2 and na indicate the number of rules headed by the target atom and the number of rules headed by auxiliary predicates, respectively.

Then, we describe other essential constraint functions to generate precise LPs. Firstly, we use a sum loss function LS according to the property described in Section 2.3 that the sum of each row in an SH matrix is equal to one:

where MSE is the mean square error loss function. To make the rules extracted fromMP meet the forward-chained format defined in the rule (1), we stipulate two spatial constraints:

1. Basic constraint: The body of each rule in an LP contains all variables that appear in the head atom.
2. Occurrence constraint: In the body of each rule, the number of occurrences of each variable that does not appear in the head atom is not one.

Then, we give each body atom a basic embedding and an occurrence embedding, and devise basic loss function and occurrence loss function to implement the above spatial constraints. Suppose that the arity of the head atom in an LP P is t, then the variable depth is |V |-t. Let Vh and Vo be the variable sets with elements appearing in the head atom and not appearing in the head atom, respectively. Let b(α) ∈ {0, 1}t and o(α) ∈ {0, 1}|V |-t be the basic and occurrence embeddings corresponding to the body atom α, respectively. If the i-th variable in Vh (or Vo) appears in α, then b(α)[i]=1 (or o(α)[i]=1); otherwise, b(α)[i]=0 (or o(α)[i]=0). Example 5 of Appendix A illustrates a basic embedding and an occurrence embedding. Then, we devise the following functions to implement the basic constraint:

where αi is the i-th valid first-order feature. The matrix Mkb ∈ [0, 1]C×t includes the occurrence information of all variables in Vh across all valid features for the k-th rule in an LP. Then, we use the fuzzy conjunction and disjunction operators to calculate the possibility that all variables in Vh appear in the k-th rule at once, and we define a basic loss function LB:

To implement the occurrence constraint, we use the following equation to concatenate all possibilistic occurrence embeddings across all valid features to Mko ∈ [0, 1]C×(|V |-t) :

Then, the possibility for each variable in Vo across all the valid features in the k-th rule are summarized into the matrix Vko = ∑Ci=1 Mko [i, ·]. Hence, Vko ∈ [0, 1]|V |-t includes the possibility of each variable in Vo in the k-th rule. Then, we set a measurement function F(x) : N → [0, a] to reflect the number of occurrences of each variable in Vo, and define an occurrence loss function LO as follows:

where a, b, c, and d are hyperparameters. As x gets closer to d, the value of F(x) gets larger; otherwise, F(x) gets closer to 0. Example 6 of Appendix A illustrates the operations related to a basic and occurrence embedding.

Next, we consider the cosine similarity, cos(u, v) = u·v |u||v| , denoting the similarity between two vectors. When two vectors have greater dissimilarity, their cosine similarity is close to -1; otherwise, their cosine similarity is close to 1. Since the parameter na in the matrix MAP indicates the number of rules headed by auxiliary predicates, we reduce the cosine similarity of each 2-combinations of all rows in the matrix MAP [k, ·, ·]

for generating more possible formats of rules headed by the auxiliary predicates. Then, we calculate the loss function LF :

where ([1,na] 2 ) is the set of all 2-combinations of the integer set [1, na]. To apply the curriculum learning: The system consolidates what it learns in one episode, storing it as background knowledge, and reusing it in subsequent episodes [Evans et al., 2021]. We devise a strategy to implement the curriculum learning that DFOL uses sound logic rules extracted in every few epochs as the prior knowledge to reduce the search space in the following epochs. We reduce the cosine similarity between the rows in the trainable matrix MP and a learned matrix Mprior ∈ [0, 1]mp×C corresponding to the sound rules described in Section 3.3, where mp is the number of extracted sound rules. The loss function LC is defined as follows:

In summary, the final loss is the weighted sum of the losses in L=[LI,LS,LB,LO,LF ,LC], i.e., loss = Θ · L, where Θ is a hyperparameter vector. We use the Adam algorithm [Kingma and Ba, 2015] to minimize the final loss.

3.3 Rule Extraction

In this section, we describe how to extract LPs from a trained SH matrix and the definition of the precision of a rule.

In a trained SH matrix MP , the element at the m-th row and n-th column represents the possibility of n-th valid body feature in the m-th rule rm in P . We use multiple thresholds called rule filters, denoted as τf , on MP to extract rules. Let rule filters range from 0 to 1 with step 0.05, and let T be the set with all rule filters. For a τf , we let the valid features in the k-th row of MP with values greater than τf be the elements in the body(rk). We iteratively apply each τf on the trained matrix MP , and a rule set ˜R with m×|T| rules is generated. Next, we describe the definition of the precision of a rule. Let nr be the number of the substitutions that satisfy both the body and the head atom of a rule, and let nb be the number of the substitutions that satisfy only the body of a rule, where the substitutions are computed based on the Datalog and seen facts. Then, we regard the ratio nr nb as the precision of the rule r. A rule is correct with the precision value 1, and a rule is incorrect with the precision value 0. If a precision value floats within the interval (0, 1), then the rule may also be correct due to the incompleteness of the seen facts. Therefore, we set another threshold called soundness filter τs. Rules with precision values no lower than τs are called sound rules and are added to P from the set ˜R. To use the curriculum learning strategy, we concentrate the trained rows in MP corresponding to the sound rules into Mprior after every few epochs. The matrix Mprior is considered as the prior knowledge to boost the training process in the following training epochs. When all training epochs are finished, the sound LP is stored in P.

4 Experimental Evaluation

In this section, we present the performance of DFOL and make comparisons with NTPλ [Rockt¨aschel and Riedel, 2017], ∂ILP [Evans and Grefenstette, 2018], and NeuralLP [Yang et al., 2017]. The ratio of positive test examples covered by an LP P to all positive test examples is regarded as the accuracy of P, which is also the recall value of P in the test dataset. Due to the small size of trainable matrices in DFOL and to demonstrate the efficiency of DFOL, all experiments are executed on 24GB of memory and an 8-core Intel i7-6700 CPU. We limited the running time to one hour when generating an SHLP. Besides, the variable depth in each task does not exceed two.

4.1 Learning from ILP Datasets

In this section, we present the results of DFOL on 20 classifications of ILP datasets [Evans and Grefenstette, 2018]. Most of the ILP datasets have small numbers of data. In these benchmarks, we set τs = 1. Hence, the precision value of each generated rule is 1. The accuracy values of all the generated LPs are 100% in this section. The task definitions and generated solutions are shown in Appendix C. We use the grandparent (g) relation as an example to show the results. The background assumptions include the facts with mother (m) and father (f ) relations, and the positive examples include the facts with g relation. The training facts, the learned matrix MP , and the extracted LP P with 100% accuracy are presented in Figure 2.

Based on the comparison with ∂ILP and NeuralLP, DFOL completes 20 of the 22 benchmarks and outperforms NeuralLP in 19 of all benchmarks. Since ∂ILP is a memory expensive model [Evans and Grefenstette, 2018], ∂ILP cannot generate correct LPs in the case of a large number of objects, e.g., in the even number (20), graph coloring (10) tasks, and knowledge base dataset considered in the paper. Besides, ∂ILP requires a logical template, a more specific prior knowledge than the forward chain format. Hence, DFOL is a precise rule learner for smaller ILP datasets. However, DFOL runs over the memory limit when producing all substitutions in the propositionalization on the husband and uncle tasks.

Table 1: The results on ambiguous datasets. The notations Con and DE represent connectedness and directed edge tasks, respectively.

	Lt	Pre	Member	Son	Con	DE
σ	3	3	3	3	2	3
µ	0.95	0.95	0.90	0.95	0.95	0.95

4.2 Learning fromAmbiguous Datasets

In this section, we test the robustness of DFOL and consider two cases: (1) learning from probabilistic facts; (2) learning from mislabeled facts. We set the soundness filter τs to 1 to obtain rules with precision values of 1.

For the first case, each ground atom in the training fact set F and training negative example set N has a probability. Let ϵ ∼ N(0, σ2 ), then the probability of fact in F satisfies the distribution p+i = min(1 - ϵ, 1), and the probability of ground atom in N satisfies the distribution p-i = max(ϵ, 0). The standard deviation σ ranges from 0.5 to 3 with step 0.5. We present the distribution of the positive and negative examples on lessthan (lt) and pre tasks when σ = 3 in Figures 4 and 5 of Appendix B. From the two distributions, we derive that the values of examples are sufficiently ambiguous when σ = 3. For the second case, both positive and negative training examples are mislabeled with the mutation rate µ ranging from 0.05 to 1 with step 0.05. In Table 1, we show the maximum standard deviation σ and mutation rate µ when the accuracy values of the generated LPs are 100%. From the results, we conclude that DFOL is robust when handling ambiguous data. When µ = 1, the semantics of head predicate in lt task is largethan relation, and the result is:

4.3 Learning fromKnowledge Bases

In this section, we test DFOL on three larger real knowledge bases, including Countries [Bouchard et al., 2015], Unified Medical Language System (UMLS), and Nations datasets [Kok and Domingos, 2007]. Let τs = 0.3 because the training facts are incomplete in realistic scenarios. We present each rule with the tuple ( nr nb ,nr,nb) in Appendix C. The descriptions of these datasets are presented in Table 3 of Appendix B. For the Countries dataset, training facts are split into S1, S2, and S3 sub-datasets. From the sub-datasets S1 to S3, the learning difficulty is increasing because the related relations are missing corresponding to the test cities [Rockt¨aschel and Riedel, 2017]. For the Nations and UMLS datasets, we divide each dataset into 80% training facts, 10% development facts, and 10% test facts. We compare LPs generated by DFOL, NTPλ, and NeuralLP, through the indicators of accuracy, mean reciprocal rank (MRR), and HITS@m [Bordes et al., 2013] in Table 2.

From the results in Table 2, we conclude that DFOL has better performance than other baselines in general. Thus, we show that DFOL guarantees the accuracy of the generated LPs, as well as the scalability and interpretability on larger relational datasets. In addition, in all sub-datasets of the Countries dataset, although facts with locatedIn and neighbor predicates related to the test countries are missing, these facts are still kept in the training facts that are not related to the test countries. Hence, we can extract the same LP from all tasks. The generated symbolic LP can describe all the test facts in both S1 and S2 sub-datasets. However, because of the missing related facts in the S3, the 100% accuracy logic rule needs at least four variables. DFOL runs out of memory when generating all substitutions for four variables in the propositionalization process on the S3 sub-dataset.

Table 2: Comparison on knowledge bases. The results in bold indicate the highest accuracy on the corresponding test datasets. The ACC@Sn represent the accuracy of the generated LP on the Sn subset of Countries. ACC@h represent the accuracy of LP with the head predicate h. Blo, int, neg, and intw denote the relations of blockpositionindex, intergovorgs3, negativecomm, and interacts with.

Dataset	Metrics	NTPλ	NeuralLP	DFOL
Countries	ACC@S1 ACC@S2 ACC@S3	100.00 100.00 100.00	100.00 100.00 -	100.00 100.00 -
Nations	MRR	41.79	56.49	78.88
	HITS@1	41.79	52.49	73.88
	HITS@3	41.79	60.95	84.58
	HITS@10	41.79	61.19	85.07
	ACC@blo	100.00	50.00	100.00
	ACC@int	84.62	84.62	84.62
	ACC@neg	37.50	75.00	75.00
UMLS	MRR	30.03	66.69	74.96
	HITS@1	29.95	61.27	71.41
	HITS@3	30.11	72.31	78.82
	HITS@10	30.11	72.31	78.97
	ACC@isa	65.96	63.83	91.48
	ACC@intw	83.67	86.67	100.00

5 Conclusion and FutureWork

In this paper, we proposed differentiable first-order rule learner (DFOL), which learns first-order logic programs in the forward-chained format from relational facts without logic templates. Through the proposed propositionalization method, DFOL translates relational data to the neural network-readable data. By applying the proposed constraint functions, DFOL can learn correct first-order logic programs with a few trainable parameters. We extract symbolic logic programs from the trainable matrices directly and apply prior knowledge as constraints to implement curriculum learning. Experimental results indicate that DFOL can learn first-order logic programs with both high accuracy and precision from several standard inductive logic programming tasks, probabilistic relational facts, and knowledge bases. Hence, DFOL can learn rules from relational facts in a flexible, precise, robust, scalable, and computationally cheap manner.

In the future, we will try a more efficient propositionalization method in order to learn relational tasks with larger entities. Besides, we will extend DFOL to an explainable deep neural network framework to generate logic programs with more variables. We also plan to support the function in the term and the negation in the body of a rule.