Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors
Authors: Hang Yin
Zihao Wang
Yangqiu Song
Venue: ICLR 2024 poster (2024)
Keywords: complex query answering
knowledge graph
link prediction
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Reasoning on knowledge graphs is a challenging task because it utilizes observed information to predict the missing one. Particularly, answering complex queries based on first-order logic is one of the crucial tasks to verify learning to reason abilities for generalization and composition.
Recently, the prevailing method is query embedding which learns the embedding of a set of entities and treats logic operations as set operations and has shown great empirical success. Though there has been much research following the same formulation, many of its claims lack a formal and systematic inspection. In this paper, we rethink this formulation and justify many of the previous claims by characterizing the scope of queries investigated previously and precisely identifying the gap between its formulation and its goal, as well as providing complexity analysis for the currently investigated queries. Moreover, we develop a new dataset containing ten new types of queries with features that have never been considered and therefore can provide a thorough investigation of complex queries. Finally, we propose a new neural-symbolic method, Fuzzy Inference with Truth value (FIT), where we equip the neural link predictors with fuzzy logic theory to support end-to-end learning using complex queries with provable reasoning capability. Empirical results show that our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.

Published as a conference paper at ICLR 2024
RETHINKING COMPLEX QUERIES ON KNOWLEDGE GRAPHS WITH NEURAL LINK PREDICTORS
Hang Yin
Zihao Wang
Department of Mathematical Sciences Tsinghua University
Department of CSE HKUST
h-yin20 @ma 1s. tes inguau. edu. cn
zwanggelcse.. ust. .k
Yangqiu Song Department of CSE HKUST yasongEcse. .utccsssesse....................
ABSTRACT
Reasoning on knowledge graphs is a challenging task because utilizes observed information to predict the missing one. Particularly, answering complex queries based on first-order logic is one of the crucial tasks to verify learning to reason abilities for generalization and composition. Recently, the prevailing method is query embedding which learns the embedding of set of entities and treats logic operations and has shown great empirical success. Though there operations research following the same formulation, many of its claims lack has been much a formal and systematic inspection. In this paper, we rethink this formulation and justify many of the previous claims by characterizing the scope of queries investigated previously and precisely identifying the gap between its formulation and its goal, well as providing complexity analysis for the currently investigated queries. Morcover, we develop a new dataset containing ten new types of queries with features that have never been considered and therefore can provide a thorough investigation of complex queries. Finally, we propose a new neural-symbolic method, Fuzzy Inference with Truth value (FIT), where we equip the neural link predictors with fuzzy logic theory to support end-to-end learning using complex queries with provable reasoning capability. Empirical results show that method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset the same time.
INTRODUCTION
Knowledge graph (KG) is a mighty knowledge base that encodes relational knowledge into graph representation. However, due to the fact that modern knowledge graphs are often auto- generated (Toutanova & Chen 2015) constructed by crowd-sourcing (Vrandečić & Krötzsch 2014), they are considered noisy and incomplete, which is also known as the Open World Assumption (OWA) (Libkin & Sirangelo, 2009). Complex query answering (CQA) knowledge graphs is practical task that can support many applications (Ren et al. 2023a Wang et al. 2022). The CQA task requires answering the existential first order logic formula, involving logical operators, conjunction (A), disjunction (V), and negation (-), as well as the existential quantifier (3). In particular, as CQA based on KGs with OWA, should perform reasoning, which utilizes available knowledge to predict the missing one where traditional traversal methods are doomed to fail (Ren et al.) 2020).
To tackle this challenge, the query embedding method has been proposed (Hamilton et al. 2018). which aims to represent a set of entities by a low dimensional embedding. In addition to that, the log- ical formula is represented in an operator tree form (Ren et al. 2020 Wang et al.) 2021). J, in which the logic operations
replaced with corresponding set operations. Especially, the existential quantifier induces a new set operation, set projection, which corresponds to the logic skolemization (Luus et al.
2021). Though there has been line of research (Choudhary et al. 2021 Bai et al. 2022 Yang et al.

---

Published as a conference paper at ICLR 2024
2022, Wang al. 2023a Hu et al. 2024) following the same approach, this kind of methodology still lacks detailed inspection of its logic soundness or model expressiveness. Moreover, despite the operator tree form pushing strict constraint the solvable formulas, the real scope of the solvable logic formulas has never been estimated, and nowadays datasets are therefore highly restricted. In general, not much theoretical progress has been made inspect on nowadays CQA models.
In this paper, we first review the inherent drawbacks of the existing prevailing operator tree form representation of query embedding approaches and clearly characterize the query family that has been investigated as Tree-Form (TF) queries. Then we extend our scope of research to the whole family of Existential First Order queries with a single free variable (EFO1). Particularly, we represent queries as general multigraphs. Then we develop new dataset containing ten new formulas which can not be represented prevailing frameworks. Along with that, we propose a simple yet empirically effective algorithm which combines neural link predictors with strict fuzzy logic definition, and thus has strong theoretical guarantees. The algorithm is able to systematically infer EFO, queries of arbitrary complexity given any neural link predictor. Finally, we show that our algorithm is able to outperform existing methods in both our newly developed dataset and existing dataset. Our code and data can be found at http:: //tp::///ttttt com/ HKUST Kttp://nnno.CCo///ooeoe
2 PRELIMINARY
2.1 KNOWLEDGE GRAPHS
Given a set of entities & and a set of relations R, a knowledge graph G encapsulates real-world knowledge collection of factual triples G = {(a,, ri, b,),, in each triple, ag b, & is the head entity and tail entity correspondingly, and r; E R is the relation among them. Based on OWA, the observed knowledge graph Go is only part of the complete knowledge graph G, meaning 9o G.
2.2 EFO, QUERIES AND ANSWERS
Existing discussions emphasize logical queries without universal quantifiers (Ren & Leskoved 2020). Such queries are formally defined as Existential First Order queries with single free variable (EFO1) under the strict first-order logic theory. We provide minimum set of definitions to characterize the EFO, queries on knowledge graphs following standard logic theory (Marker) (006).
Definition 1 (Terms). A term is either variable
entity E.
Definition 2 (Atomic Formula). An atomic formula is of form o r(h, l). r E R, h and I are terms. Definition (Existential First Order Formula), The set of the existential formulas is the smallest set & that satisfies the following property:
(i) For atomic formula r(a, b), üseelf and its negation r(a, b), rr(ab) E + (ii) If db ib E & then (1 v), (6 V w) E +
(iii) If o E & and 24 is any variable, then 3x,0 E 4.
We say variable y is bounded if there is an associated quantifier, otherwise, it is free. We use dby) indicate the formula & contains a free variable y. Then we finish the definition of the EFO; formula.
Remark 4 (Query and sentence). When a formula contains least one free variable, it is also called query. Otherwise, the formula can be called a sentence.
Definition 5 (Substitution). For a EFO, formula Φly). for any entity a E E, we write ((a/)) or simply σ(a). for the result of simultaneously replacing all free occurrence of in ó by a.
Then, we are ready to define EFO; queries and the answer set.
Definition (The Answer Set of EFO, Query). The answer set of an EFO, query is defined by
A[o(y)) {a E 8l ((a) is True]
All BFO; formulas can be converted to Disjunctive Normal Form (DNF), specifically:
Definition (Disjunctive Normal Form). The disjunctive normal form ΦDNE of an EFO, formula is
(DNF(V) =y(() .... Tm (y)
(2)
2

---

Published as a conference paper at ICLR 2024
Simple Graph
Trvero,
r1
T2
N
TANEFO,
a
P2 P1
Cyclic Graph
Acyclic Graph
b
Multigraph
T'
EFO;
Figure 1: Representation of the tree form query "pni". We note that this kind of representation requires explicit operators the graph, the corresponding lines are dotted.
Figure 2: A diagram for the differences between the Tree-Form queries (orange blocks) and the EFO; queries (black box). EFO, queries are categorized by their query graphs. Some Tree- Form queries are not of EFO,
where Ny (v) 321,... 2g1 A... ajjny' j L...., where Ts, L,.... k are existential variables, y is the single free variable, aj are atomic formulas or the negation of atomic formulas.
There are many ways to represent a EFO, formula, however, the DNF has gained dominant priority in lines of previous research (Ren & Leskovec 2020) Wang et al.) 2021 Zhang et al. (021). Converting the original query (0y) into a DNF query ΦDNF (3) decomposes the answer set A (F (y) into union of the answer sets of ([n)(w), which has become a common practice in recent research (Wang
et al. 2023b). We consider EFO; queries in DNF throughout this paper.
THE LIMITATION OF PREVIOUS FORMULATION
In this section, we aim to answer the question: Can general EFO; queries be precisely represented by previous formulations in syntax? In recent years, huge number of research (Ren & Leskoved 2020 Wang et al. 2021 Zhang et al.] [2021] Ren et al.) 2023b) have all made such a strong claim. However, derived from the design of the previous method, we are able characterize the query family that has been investigated as Tree-Form (TF) queries and provide it with a formal definition. Our discussion even subset of EFO,, Therefore, our discussion justifies the limitation of previous works by showing their unrigorous formulation.
shows that the TF query family
3.1 THE SYNTACTICAL CLOSURE OF PREVIOUS FORMULATION: TREE-FORM QUERIES
The query types in the existing datasets (Rnn & Leskovec 2020 Wang et al. 2021), though targeted to EFO; query family, selected with bias when it comes to the empirical evaluation. The reason is that the dominating way of addressing logical queries is to simulate logical reasoning as the execution of operators on operator tree (Wang al. 2021| Xu al.. 2022), where each node represents set of entities corresponding to the answer set of sub-query. The logical connectives are transformed into operator nodes for set projections, intersection, union, and complement (Wang et al. 2021) Particularly, the set projections are derived from the Skolemization of predicates (Luus et al. 2021
We characterize the expressiveness of operator tree method by providing the formal definition of the TF query, instead of confusing them with EFO, queries as the previous practices (Wang et al. 2021).
Definition (Tree-Form Query). The set of the Tree-Form queries is the smallest set T such that:
(i) Ifo(y) r(a,y), where a E &, then ó(y) E &TTF;
(ii) If Φ(y) E dTF. <b(y) E TTF;
(ii) If (fo(), vi()) @TE, then (ø A (x) TTT and (Φb V ()) TTF:
(iv) If oly) E 2TF and of is any variable, then (///)) By.ryy, 3²) A A(y)) E 4TF-
Figure I is an example of a Tree-Form query that appeared in the widely used dataset (Ren & Leskovec 2020). The formal derivation of the definition of TF can be found in the Appendix
However, this biased selection of query types deviates from the original goal of complex query answering (Ren & Leskovee, 2020). It imposes strong assumptions for the formula (Wang al.) 202T). so a large part of first-order queries, even only with existential quantifiers, is ignored in both existing datasets and the solving strategies. Moreover, it is questionable whether existing query types
3

---

Published as a conference paper at ICLR 2024
indeed skip the universal quantifier. As we have pointed out in the following, the recursive definition may seem to neglect the universal quantifier but fails when the formula becomes more complex.
3.2 TF QUERIES DEVIATE FROM THE GOAL OF EFO, QUERIES
Proposition 9. In D the universal quantifier may exist in TF queries, thus the famity of TF query is not a subset of EFO;
Proof: We derive this proposition based on the Definition
8
Ti ri x)) E QTF
Ea.ri (a, 2) A (2, v) 4TF
- (a, x) A (2 y) E I
Yr. 0v.-ri(a;)) (a, V (22 (2. y) @TF
We note that in Definition 3 the negation defined only on the atomic formulas, while in Definition g the negation is defined on the whole formula, which leads to the occurrence of the universal quantifier. Example 10. Based on the above discussion, the original "pni" query proposed in Ren & Leskoved 2020 and shown in Figure 7 should have this kind of formulation in DNF (a, E &):
Vx. (ra(b, v) A (x, y)) V (ra(b, y) A (r)
By proposition and Example 10
we clearly show that both the methodology and dataset in previous research (Ren & Leskovec 2020) deviate from its original ambitious goal to answer EFO, query.
4 GAPS BETWEEN TF AND EFO, QUERY
In this section, we aim to further identify the gap between the EFO, query family and TF family. To this end, we first introduce the representation method for general EFO; query.
4.1 A TRARH-THEORETICAL DESCRIPTION OF EFO; QUERIES
We discuss EFO, queries by considering each conjunctive query 7j as a query graph. Graphs representation is already discussed in answering Tree-Form queries without negation (Daza & Cochez, 2020: Liu et al. 2022) and Tree-Form queries (Wang et al. 20236).
Definition 11 (Query Graph). Let y be conjunctive formula in equation 2 its query graph G(7) (h,r 1, {T/ each quadruple corresponds to an atomic formula or its negation, representing an edge with two endpoints h, and two attributes T/F, the relation and whether is positive.
We note nodes of different types represent the node be a constant entity, existential variable, or free variable. Logical conjunction is naturally presented in the query graph because the order of existentially quantified variables is exchangeable, indicating the main strength of the query graph representation. Then, all EFO, queries in DNF can be represented by set of query graphs (G(r))) We show an example of query graph in Figure
The concept of query graph is also similar to the Gaifman graph (Vardi 2000), which is well investigated in constraint programming. The key differences are (I) query graphs emphasize more node types for each term and (2) query graphs also encode logical negation.
4.2 SYNTATICAL GAP BETWEEN TF AND EFO, QUERIES
Figure briefly categorizes EFO; queries by whether their query graphs are acyclic or simple. We note previous research shows that Tree-Form queries are assumed be both acyelic and sim- ple (Hamilton et al., 2018). Then, the key to understanding the relationship between TF queries and EFO, queries is determine the gap between TF queries without universal quantifier (the bottom half orange box) and EFO, queries with an acyclic simple query graph (the top-right of the dark box). We characterize this gap by the following two properties.
Moore generally, this conclusion is true in every prenex normal form, which is a pre-requisite for query embedding method (Wagg et al. 202T
4

---

Published as a conference paper at ICLR 2024
Biy Bayla,, Award AwarddOOuttanddnngPPrr |or.CCrooooonnguuoooorrrro. Ci) Publishin 22, Authoriz,, A-Frsttt -FirstAuthorr(aa..
3 Publish In
222
Fortttrttu
Constant Entity
Author
Cite
y
Existential Variable
CuntspandingAuuhhr
Outstanding Paper
Free Variable
Award
Figure 3: A given query "Find someone who has such two papers: s/he is the corresponding author of the first paper which has been awarded Outstanding Paper, s/he is the author but not the first author of the second paper which has been published and been cited by the first paper." can be represented as such query graphs. The formal existential formula also given at the top.
Property 12 (Negation without Constants). There is negated atomic formula of the form -r(x1, x2) or (T1, y) where æ1, 22 are existential variables and y is the free variable.
Property 13 (Existential Leaves). For any spanning tree by using the free variable the root, the leaf node of the query graph can be an existential variable rather than a constant entity.
Assumption 14 (Reverse relation enrichment). For any relation v, there exists reversed r' such that (a, b) = r(b, a) for any pair of entities a, b.
Lemma 15. A query that has sentence as its subformula is trivial and should not be considered.
We note Assumption 14 is a common practice previous research (Lacroix et al. 2018), as well as the Lemma 15 (Ren et al., 2020 Ren & Leskovec 2020).
Theorem 16. With assumption and lemma 75 any EFO; query with a simple acyclic query graph
that does not have Property 12 and 13
is TF query.
In this way, we fill the syntactic gap by making it clear what kinds of queries are left to discussed, in order to achieve the ambitious goal of answering EFO, queries. The proof of Lemma 15 and Theorem is detailed in Appendix A.I
4.3 COMPLEXITY GAP BETWERN TF AND EFO, QUERIES
In this part, further rethink the complexity of the currently investigated queries, particularly, the traditional claim that "reasoning involves an exponential growth in computational time" " (Ren & Leskovee 2020 Chen et al.) 2022).
When discussing the complexity, we assume the knowledge graph G is complete for simplicity. For general EFO; queries, it has long been known to be NP-complete (Chandra & Merlin 1977).
However, TF queries discussed in previous literature are particularly simple. Queries in TF n EFO,, well-know special cases with structure- trrscture-based tractability in inference (Vardi) (000). Specifically, we adapt the complexity results from Dechter & Pearl (1877) on knowledge graphs.
Proposition 17 (Adapted from Dechter & Pearl (1987 ). The optimal complexity of answering TF
queries in previous datasets (Ren & Leskovec 2020 Wang el al. (202)) is O(nk2), where is the
number of terms and k is coefficient to characterize the sparsity of the knowledge graph
k = max FER
Ka E El3b,(a,r,b) G or (b, E GH
(4)
The more detailed proof is provided Appendix A.2 where we show we extend traditional results that only be applied to TF EFO, We found that the complexity grows linearly with the number of variables in the query. The complexity depends on the property of knowledge graphs (see the coefficient k) and is at most quadratic. Our theorem provides strict lower bound for previous optimization methods like QTO (Bai et al. 2023).
We note that the entire EFO; queries inherently harder than TF queries. To the best of our knowledge none of the existing methods have considered EFO, queries, and their models lack the ability represent those queries precisely in syntax.
5

---

Published as a conference paper at ICLR 2024
0.6
0.2
0.7
0.5
0.1
0 0.8
0.8
S
Figure 4: A toy example to show the process of FIT, the vector indicates the fuzzy set of the corresponding node has been updated in this step. The query graph follows Figure with the grounded entity and relation omitted.
METHODOLOGGY
This section presents Fuzzy Inference with Truth values (FIT) algorithm for answering EFO; queries on knowledge graphs. FIT a neural-symbolic method that fine-tunes neural link predictors to address the open-world assumption. Specifically, FIT accepts wide range of models long as they provide a "truth value" for a given triple (Trouillon et al., 2016: Cohen 2016 Zhu et al. 2021). Moreover, prove that our algorithm ensures faithfulness and perfectness with assumptions.
5.1 FUZZY TRUTH VALUE DEFINITION
For simplicity, we follow Cohen 2016 to conceptualize the neural link predictor as |R] matrices P. E [o, 1| where (a is the truth value of triple (a, b). We note that r, a, b can be treated integers by indexing all relations and entities.
is straightforward to use fuzzy logic theory, and define the truth value function as the following: Definition 18 (Truth value of existential formulas). Let ó and di be existential formulas, T and 1 are t-norms and t-conorms, 1 is another t-conorm, and r E R, a, E.
(i) T(r(a, b)) b)
(()) (iii) T( A wi) = TT)) =(v))) = ((O)LT(1))
(ii) T(-Ø)
(iv) Liee
For the introduction of the t-norm and t-conorm, please refer Appendix C the inductive definition of the existential formula Definition 3 so if the formula a sentence, has certain truth value. Moreover, note that 1 is commonly chosen to be Godel t-norm (Klir & Yuan 1995 Hajek 2013) but also extended to others in recent research (van Kricken et al. 2022).
This definition follows
Then, to answer EFO; query is to estimate the truth values of all possible answers the corre- sponding substitutions. The more plausible answers are expected to have higher truth value. We store the truth values in the answer vector goal.
Definition 19 (Answer Vector). For EFO, query, ((v), its answer vector A A(p(v)] [0, 1]|8| is given by (a) = =T(((a/)).
5.2 DIFFERENTIARIS NEURAL MATRIX CONSTRUCTION
Neural link predictor is differentiable model that provides scoring function for each possible triple (a.r,b). To fit into our definition and construct the neural matrices, we calibrate the real number score s(a, r, b) probability within [0, interval by using the softmax function:
exp(s(a,r,,))
P (b) Eeegeop(s(a, r,)
As the softmax outputs vector that has the sum of 1, we further compute the scaling:
(d((er.ddeg.)) Eeetataarabee.
if Hd (a, E GoHl > 0
Qa,b =
(5)
if [d (a, d) E G.H =
Therefore, the a-th row of r-th matrix is got by clamping the value for each element: Pr b) min(1, P: Pra(b) x Qa.b)
(6)

---

Published as a conference paper at ICLR 2024
2m
2il
pni
2nm
3mp
3il
im
3pm
3cm
Figure 5: Query graphs of each real EFO, formula. Naming convention: 1 "existential leaf", m "multi graph", for "circle". We also follow the previous convention: "I" for intersection, "p" for projection, and "n" for negation. The representation query graphs follows Figure In testing, the construction of the neural matrix is bit complicated, details in Appendix
5.3 FORWARD INFERENCE WITH TRUTH VALUE
We explain how to compute the answer vector given neural matrices by a toy example. Full detail of the rigorous derivation is in Appendix MaaadixxDanddd the analysis of its complexity is in Appendix[E] We infer fuzzy vector C, [0, 1] to represent the fuzzy set for every node in the query graph, with this help, we remove node and edge step by step and updating C., for corresponding nodes simultancously. keeping the answer vector the same on a smaller graph. Our techniques extend traditional symbolic search methods, like Yannakakis (198I) in database theory and Dechter & Pearl (1987) in constrain satisfaction problem, see more discussion in Appendix G.1
To illustrate our FIT briefly, we explain each step shown in Figure 4.3 1. We initialize the constant
entity by giving a one-hot vector as its fuzzy set. We remove the constant entity and update the fuzzy set of the nodes that are connected to the constant. 3. We remove a leaf variable and update the fuzzy vector of its neighbor. the fuzzy set of variable and make it a constant. 5. Similar to step 2, remove the constant. 6. The query graph contains only the free variable and the final answer naturally its fuzzy set. We note this example has included all three features that should be considered according to our Theorem 16 existential leaf, multigraph, and cyclic graph.
Since
a circle in the graph, we enumerate possible candidates in
Finally, all the computations in the FIT differentiable, the loss is defined as cross-entropy of the predicted answer vector A with the real answer A::
((AHHAAAA A) = -Ene. In(A(a)) + E(aee-A) In(1 - A(a))]
In this way, backward propagation helps fine-tune the neural link predictors using data of the complex query, rather than just one-hop queries.
5.4 THEORETICAL GUARANTEES
Definition 20 (Perfect Matrices), Given a knowledge graph G. we say the matrices (Pr)reR are perfect if Pr( + (h, r,) G, P,(h,t) = + (h, & G. Theorem 21 (Perfectness). the Mutrices(Pr]rer are perfect, then the FIT algorithm is perfect, meaning: A( = > E A(o(1)), (t) + a & Alø(y)).
Though there is perfect model in practice, can always assume the given model is "good", which admits the following consistency assumption.
Assumption 22 (Consistent matrix), For any observed triple (a,r,b) Go. Pr(a. for any unobserved triple (a, rr,)) b) & G.. P, (a, <
Definition 23. We say model is faithful if it is able retrieve deductible answers like traditional logical inference system like database query (Kroenke) 2002 Sun et al.) 2020).
Theorem 24 (Faithfulness). With assumption 22 for any EFO, query σ(y) without negation, FIT reaches perfect faithfulness. meaning that every answer a that can be deduced in the observed knowledge graph G.. (()())((a) =
7

---

Published as a conference paper at ICLR 2024
Table 1: MRR results( % of the new queries on the real EFO; dataset.
Knowledge Graph
Method
pni
3i1
2m
2mmn
3amp
3pm
3c
3em
AVG.
Betal:
9.0
25.0
40.1
8.6
6.7
8.6
6.8
12.3
25.2
22.9
16.5
LogicE
9.5
27.1
42.0
6.7
9.4
25.4
23.3
ConE
10.8
27.6
43.9
9.6
7.0
9.3
7.3
14.0
28.2
24.9
18.3
FB15K-237
QTO
12.1
28.9
47.9
10.7
11.4
6.5
17.9
38.3
35.4
21.8
CQD
7.7
29.6
46.1
6.0
1.7
6.8
3.3
12.3
25.9
23.8
16.3
LMPNN
10.7
28.7
42.1
9.4
4.2
9.8
7.2
15.4
25.3
22.2
17.5
Betal:
29.9
34.8
50.6
24.4
9.6
19.0
18.4
29.1
30.5
30.7
27.7
LogicI
30.7
39.3
53.0
24.1
10.5
20.5
15.5
30.7
31.8
31.7
28.8
ConE
37.0
40.1
57.3
33.3
11.5
23.9
27.6
38.7
35.0
36.3
34.1
QTO
CQD
24.2
47.6
65.44
23.2
1.6
11.0
8.7
36.3
31.3
32.9
28.2
LMPNN
43.2
57.8
40.3
7.9
32.2
FIT
57.9
70.4
77.6
73.5
39.1
57.3
64.0
79.4
63.8
65.4
64.8
7.5
64.6
5.3
8.7
36.1
Logicti
9.8
47.0
66.6
34.7
6.4
13.3
17.8
35.1
38.9
37.9
30.8
42.1
38.2
NELL
QTO
12.3
48.5
68.2
38.8
12.3
22.8
19.3
41.1
45.4
43.9
35.3
CQD
7.9
48.7
68.0
31.7
1.5
12.9
13.8
33.9
38.8
33.9
29.3
IMPNN
11.6
43.9
62.3
35.6
6.2
15.9
19.3
38.3
39.1
34.4
30.7
FIT
14.4
53.3
69.5
42.1
12.5
24.0
22.8
41.5
47.5
45.3
37,3
Bny Pa Hg.HHost[Japen my) Gradunteiz Host(Japan, (og) (aculty(r223)
Te. Host [Jppn xt) A Graduate(a, () Faculty(r,
Host
Grachatte
Graduate
Japan
Japan
Host
Faculty
Japan
Host
Faculty
I
322
Figure 6: Left: The EFO; version. Right: The Tree-Fort approximation. The original is split into T1,42 T2 the Tree-Form query, leading to a different semantic meaning. The formal first order logic formula is also given at the top.
The proof of the Theorem 21 and Theorem 24 provided in Appendix A.3
6 REAL EFO, DATASET
Based on our previous discussion of the limitation of query embedding methods in Section 4.2 we have crafted ten real EFO, formulas: pni, 2il, 3il, im, 2m, 2nm, 3mp, 3pm, 3c, 3cm. We note these formulas have included all possible new properties of the EFO; formulas: Property 12 pni). Property 13 3il, multi golti-graaph(m, 2m, 2nm, 3mp. 3pm, 3cm), and cyclic graph(3c, 3cm). Graphs with self-loop not included, explained in Appendix I Additionally, the formula "pni" has already been put forward by previous dataset (Ren & Leskovec, 2020), but it is answered as the universal quantifier version illustrated in Example 10) maintain the query but re-sample its answer according to our definition. The query graphs of our new formulas are presented in Figure 5 Its statisties given in Appendix[]
7 EXPERIMENT
7.1 SETTINGS
We evaluate our algorithm on various tasks. Firstly, we evaluate our algorithm on our new dataset of real EFO; queries developed in Section and show the failure of existing methods. Secondly, compare our algorithm with existing methods on the dataset of Tree-Form queries provided by Ren
Leskoved 2020). Thirdly, verify claims of Theorem 24 by evaluating also Frre-Form.
We follow the standard protocol, splitting the answer into two parts: deductible answers which can be found by the observed knowledge graph Go, corresponds to Section 7.4 predicted answers that need generalization which can be found the whole knowledge graph G but not from G., correspond to Section 7.2 and 7.3 All experiments use Mean Reciprocal Rank (MRR) the metric.
8

---

Published as a conference paper at ICLR 2024
Table 2: MRR results(%) %) of the Tree-Form queries. The average score is computed separately among positive and negative queries. The scores of CQD and LMPNN is directly taken from their
paper (Mmervini et al. 2022 Wang et al. 2023b).
KG
Method
1p
2p
3p
1p
2u
up
AVG.P)
2in
3in
inp
pin
AVG.NN)
COD
46.7
13.3
7.9
54.9
20.4
17.6
11.5
25.3
PRISL-257
IMPNN
45.0
17.6
22.7
8.7
12.9
4.6
46.7
21.9
27.4
9.5
COD
89.2
65.3
29.7
77.4
30.6
71.6
70.6
72.3
59.4
68.5
HB1S
LMPNN
85.0
43.0
36.7
29.1
10.2
71.8
73.9
29.0
40.2
COD
60.4
22.6
13.6
43.6
53.0
25.6
31
19.9
16.7
31.8
NELL
LMPNN
24.9
30.8
8.5
10.8
3.9
Table 3: MRR results( 9) of the deductible answers in the BetaE dataset.
Formula
1p
2p
21
3i
2in
3in
pin
pni
2n
up
100
100
65.3
65.2
The discussion of the choice of hyperparameters, including the t-norm/conorm, Appendix H
7.2 EXPERIMENT ON REAL EFO, DATASET
Here we present our result on our new proposed dataset, shown in Table As explained in Section 3 the Tree-Form query fails to represent the same syntax as our newly developed real EFO, queries so can only syntactically approximate the desired real EFO, query. We offer a detailed example of our new "2m" query Figure where the semantics of the left is "Find someone who is a graduate of a J Japanese University and also a faculty of the same university" while the right means "Find someone who is a graduate of Japanese University and is also faculty of a Japanese university", The apparent difference illustrated by this example explains why the previous method falls far behind our FIT, in all types of query and all knowledge graphs. For more details on the implementation of the baseline methods, please refer to Appendix K
7.3 EXPERIMENTS ON EXISTING BETAE DATASET (TREE-FORM)
As FIT utilizes a pretrained neural link predictor, for fairness, provided by CQD (Minervini et al. (2022) to compare. We note that LMPNN (Wang et al.. (002bb) also builds its model by the same checkpoint and adds its own new learnable parameters, thus LMPNN is also added as baseline. Additionally, the connection to QTO is explained in Appendix G.2 where we show how FIT a pure extension to QTO.
the checkpoint
Since CQD is not able to answer queries with negation, we split the experiment result into the positive part and the negative part. The result of the positive queries is shown in Table We have found that our FIT algorithm surpasses both baselines in all knowledge graphs. Most significantly, when the diameter of the query graph gets bigger, like 3p queries, the advantage of our FIT are enormous. As for the result of negative queries, FIT outperforms LMPNN by large margin in all query types.
7.4 EXPERIMENTS ON FAITHFULNESS
To verify our Theorem 2
evaluate algorithm by the deductible answers. The result is shown T To the best of our knowledge, (Sun et al. (2020) is the only one that considers faithfulness, omit its result since it only infer positive queries in which have reached perfect faithfulness.
8 CONCLUSION
We reviewed the limitations of current query embedding methods and extended the scope of complex query answering to the whole family of EFO, formulas. We also developed a new dataset containing ten formulas and analyzed the new difficulties coming with these formulas. Finally, based strict fuzzy logic theory, we present a new neural-symbolic method, FIT, which can fine-tune pretrained neural link predictor to infer arbitrary EFO, formula and outperform existing methods significantly.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors of this paper were supported by the NSFC Fund (U20B2053) from the NSFC of China, the RIF (R6020-19 19 and R6021-20) and the GRF (1621 1520 and 16205322) from RGC of Hong Kong. We also thank the support from the UGC Research Matching Grants (RMGS20EG01-D, RMGS20CR11, RMGS20CR12, RMGS20EG19, RMGS20EG21, RMGS23CR05, RMGS23EG08).
REFERENCES
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex Query Answering with Neural Link Predictors. In International Conference on Learning Representations, 2020.
Jiaxin Bai, Zihao Wang, Hongming Zhang, and Yangqiu Song. Query2Particles: Knowledge Graph Reasoning with Particle Embeddings. In Findings of the Association for Computational Linguisties: NAACL 2022, pp. 2703-2714, 2022.
Yushi Bai, Xin Lv, Juanzi Li, and Lei Hou. Answering Complex Logical Queries on Knowl- edge Graphs via Query Computation Tree Optimization. In Proceedings of the 40th Interna- tional Conference on Machine Learning. pp. 1472-1491. PMLR, July 2023. URL https ISSN: 2640-3498.
//proceedings mlr prwss wwwpp/wwweeeeepppppppppppp. /ttp////2////a//b//////aa html
Ashok K Chandra and Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium Theory of computing, pp. 77-90, 1977.
Xuelu Chen, Ziniu Hu, and Yizhou Sun. Fuzzy logic based logical query answering on knowledge graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3939- 3948, 2022. Issue: 4.
Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan Reddy. Prob- abilistic entity representation model for reasoning over knowledge graphs. Advances in Neural Information Processing Systems, 34:23440-23451, 2021.
William W. Cohen. TensorLog: A Differentiable Deductive Database, July 2016. URL http arXiv:1605.06523 [cs].
/aaxiiv. //wxiv.org//aabb......
Daniel Daza and Michael Cochez. Message Passing Query Embedding. February 2020. doi: 10. 00448500/rxXiv22002004400 URL /R./
Rina Dechter and Judea Pearl. Network-based heuristics for constraint-saatiisctiinn problems. Artificial intelligence, 34(1):1-38, 1987. Publisher: Elsevier.
Weizhi Fei, Zihao Wang, Hang Yin, Yang Duan, Hanghang Tong, and Yangqiu Song. Soft Reason- ing on Uncertain Knowledge Graphs, March 2024. URL htttt:://arratt http/aaiii...rr/a//// hatg///b/400 /4003 01508 arXiv:2403.0155 [cs].
Jean Gallier. Discrete mathematics. Springer Science Business Media, 2011.
Petr Hájek. Metamathematics of fuzzy logic, volume 4. Springer Science & Business Media, 2013.
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. Advances in neural information processing systems, 31, 2018.
Qi Hu, Weifeng Jiang, Haoran Li, Zihao Wang, Jiaxin Bai, Qianren Mao, Yangqiu Song, Lixin Fan, and Jianxin Li. FedCQA: Answering Complex Queries on Multi-Source Knowledge Graphs via Federated Learning. February 2024. URL pectp::/arxiw..rr//aabette arXiv:2402. 14609 [cs].
George Klir and Bo Yuan. Fuzzy sets and fuzzy logic, volume 4. Prentice hall New Jersey, 1995.
David M Kroenke. Database processing: Fundamentals, design implementation. Pearson Educación, 2002.
10

---

Published as a conference paper at ICLR 2024
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical Tensor Decomposition for Knowledge Base Completion. In International Conference on Machine Learning, pp. PMLR, June 2018. doi: 1155000rXXX.1886.7722,,, URL http::/ataaaaaa orq als//bb///// 1806 [es, stat].
07297 1rXiv:1806.000 1806.07297
Leonid Libkin and Cristina Sirangelo. Open and Closed World Assumptions in Data Exchange. Description Logics, 2009.
Xiao Liu, Shiyu Zhao, Kai Su, Yukuo Cen, Jiezhong Qiu, Mengdi Zhang, Wei Wu, Yuxiao Dong, and Jie Tang. Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logical Queries. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1 120-1130, August 2022. doi: 10. 145/3534678.35394722
http
//arxiv. org. abc /208 07638 arXiv:2208.07 07638 [cs].
Francois Luus, Prithviraj Sen, Pavan Kapanipathi, Ryan Riegel, Ndivhuwo Makondo, Thabang Lebese, and Alexander Gray. Logic embeddings for complex query answering. arXiv preprint arXiv:2103.0041 2021.
David Marker, Model theory: an introduction, volume 217. Springer Science & Business Media, 2006.
Pasquale Minervini, Erik Arakelyan, Daniel Daza, and Michael Cochez. Complex Query Answering with Neural Link Predictors (Extended Abstract)*. In Lud De Raedt (ed.). Proceedings of the Thirty-Firsi International Joinl Conference on Artificial Intelligence, IJCAI-22, pp. 5309-5313. International Joint Conferences on Artificial Intelligence Organization, July 2022, doi: 10.24963/ ijcai.2022/744 URL httttt///dooi org.///00..rro0../// 24923/2ic3ii..... 2022 741
H Ren, W Hu, and Leskovec. Query2box: Reasoning Over Knowledge Graphs In Vector Space Using Box Embeddings. In International Conference on Learning Representations (ICLR). 2020.
Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33:197 19119966-9726, 2020.
Hongyu Ren, Mikhail Galkin, Michael Cochez, Zhaocheng Zhu, and Jure Leskovec. Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases, March 2023a. URL http:://rxx
http:/bb//23333 14617 arXiv:2303. 14617 [cs].
Hongyu Ren, Ali Mousavi, Anil Pacaci, Shihabur R Chowdhury, Jason Mohoney, Ihab F Ilyas, Yunyao Li, and Theodoros Rekatsinas. Fact Ranking over Large-Scale Knowledge Graphs with Reasoning Embedding Models. Data Engineering, pp. 124, 2023b.
Haitian Sun, Andrew Arnold, Tania Bedrax Weiss, Fernando Pereira, and William W Cohen. Faithful embeddings for knowledge base queries. Advances in Neural Information Processing Systems, 33: 22505-22516, 2020.
Helmut Thiele. On T-quantifiers and S S-quantifierss In Proceedings of 24th International Symposium on Multiple-Valeee Valued Logic (ISMVL '94), pp. 264-269. IEEE, 1994.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pp. 57-66, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference on machine learning, pp. 2071-2080. PMLR, 2016.
Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing differentiable fuzzy logic operators. Artificial Intelligence, 302: 103602 2022. Publisher: Elsevier.
Moshe Y. Vardi. Constraint satisfaction and database theory: tutorial. In Proceedings of the nineteenth ACM SIGMOD-SIGE SIGACT-SIGARR symposium on Principles of database systems, PODS '00. pp. 76-85, New York. NY, USA, May 2000. Association for Computing Machinery. ISBN 978- 186-1-58113211444 doi: 10. 10.1145/335168.3333 1145/3351 68 2115/3335168.335203
URL https: //11, acm. doo//

---

that has the same Published as a conference paper at ICLR 2024
Denny Vrandečié and Markus Krötzsch. Wikidata: free collaborative knowledgebase. Communica- tions of the ACM, 57(1)):78 85, 2014. Publisher: ACM New York, NY, USA.
Zihao Wang, Hang Yin, and Yangqiu Song. Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs. Proceedings of the Neural Infor-
mation Processing Systems Truck on Dalasets and Benchmarks, 1, December 2021. URL
htw.eeeeedddnne..eeeeeee.eeee neur round2. -roto
Zihao Wang, Hang Yin, and Yangqiu Song. Logical Queries on Knowledge Graphs: Emerging
Interface of Incomplete Relational Data. Data Engineering, pp. 3, 2022.
Zihao Wang, Weizhi Fei, Hang Yin, Yangqiu Song, Ginny Y Wong, and Simon See. Wasserstein- Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport. arXiv preprint ar arXiv:2305.0400 2023a.
Zihao Wang. Yangqiu Song, Ginny Wong, and Simon See. Logical Message Passing Networks with One-hop Inference on Atomic Formulas. In The Eleventh International Conference on Learning Representations, 2023b. URL http:////pppeeeeeeeeeeeeeeerrraa
Zezhong Xu, Wen Zhang, Peng Ye, Hui Chen, and Huajun Chen. Neural-Symbollc Entangled
Framework for Complex Query Answering, September 2022. URL http::/arxiv..tt
abs/ 2ttp:/209.088 08779 arXiv:2209.08779 [cs].
Dong Yang. Peijun Qing, Yang Li, Haonan Lu, and Xiaodong Lin. GammaE: Gamma Embeddings for Logical Queries on Knowledge Graphs, October 2022. /tL/::tt////rr /bs/
2210. 15578 arXiv:2210.1555 [cs].
Mihalis Yannakakis. Algorithms for Acyclic Database Schemes. January 1981. Journal Abbreviation: Very Large Data Bases, International Conference on Very Large Data Bases Publication Title: Very Large Data Bases, International Conference on Very Large Data Bases.
Hang Yin, Zihao Wang, Weizhi Fei, and Yangqiu Song. Steex(EFO) (K))CCA): Towards Knowledge Graph Complex Query Answering beyond Set Operation, July 2023. httht
1/arxiv.orq/ abs/ 220./ arXiv:2307.13701 [cs].
Hang Yin, Zihao Wang, and Yanggiu Song. Meta Operator for Complex Query Answer- ing on Knowledge Graphs, March 2024. URL httpt:://aaxiv.orggp/pooo/ wbwp://20ggab//223.3... 10110 arXiv:2403. 10110 [cs].
Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. Advances in Neural Information Processing Systems, 34:19172-19183, 2021.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascas Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 11-29776-29490 2021.
A MISSING PROOFS IN THE MAIN PAPER
We offer all the proof of the results the main paper in this section.
A. PROOF OF LEMMA 15 AND THEBRREM 16
Firstly proof the lemma 15 by stating it very clearly the following:
Lemma 25. A query that has sentence as its subformula is trivial and should not be considered. To be specific, suppose the formula reads ((y), Yn). then it falls into one of the two situations: 1. Ø(v1.- Yn) has a certain truth value of 1 O. irrelevant of the choice of y.. yuu therefore trivial. 2. There is a subformula (hy,. Vn) of the original "......., Vv) answer set, meaning the original d'y)," ya) is redundant and should not be considered.
12

---

Published as a conference paper at ICLR 2024
Proof. We prove that recursively.
Given a sentence we call X, w.r.ot,, we assume its truth value 1.
For another query 1 v A has the same answer set with bb which falls into the second situation.
For another query b. & V always has truth value 1, which falls into the first situation.
X has a certain truth value of O, which falls into the first situation.
Fax and Vax both have certain truth value of 1 (assume the knowledge graph is not empty), which falls into the first situation.
By the recursive definition of first order logic formulas, this lemma is proved.
We apply this lemma acyclic queries:
Lemma 26. With lemma 15 if EFO, query Φ(y) has an acyclic query graph, then each of its constant entities should be a leaf node in the query graph.
Proof. We prove by contradiction: if there exists node which is non-leaf node but it is also a constant entity. Then we consider the sub-tree whose root is a, which represents an existential formula d without free variable (recall that the only free variable y is the root of the whole tree), thus is a sentence. By lemma 15
we exclude this kind of query.
Then we give the proof of Theorem 16
Proof. Considering query o(y) whose query graph is acyelic, we compute the spanning tree of by using the free variable its parent node. With this representation, we prove the theorem by mathematical induction on the number of nodes in the query graph.
the root. Assumption [4Jensures that each edge is from the child node to
We start when there are two nodes in the query graph as one node can not construct an edge. Then the query must have form of r(a, y) or -r(a,)) y) by it does not have property [3] Either way, it is TF query by definition g
Assuming this holds for query graphs with no more than n 2 2 nodes, then we prove it for graphs with n nodes.
Find the root y, using lemma 26 we know it only connects to existential variables or leaf nodes.
connects to a leaf node u, we know u must be an entity a by not having property [3 Then σ(v) r(a, v) A (yy), where (1() is an TF query by induction. Then using the third part of definition [ finishes the proof.
If only connects to existential variables, find one child node u with the edge we note the edge must be positive because of not having property 12 Then Φ(y) can be decomposed as d(y) = r(u, y) A (b))) A x(y), where (u)) and ( are both TF query by induction (If only connected to u, x x(y) is omitted). Then using the third and fourth part of definition finishes the proof.
Then, the proof is finished by induction.
A.2 PROOF OF THE COMPLEXITY TREE FORM QUERY
To begin with, note that in the construction of the current dataset, there is another assumption called "bounded negation" that has been proposed by Ren & Leskovee (2020) and inherited by Wang al. (202T), which makes sure that set complement is "bounded" by set intersection:
Proposition 27 (Bounded Negation). In every operator tree of the previous datasets (Ren & Leskovec 2020 Wang et al. 202I), every node representing "N" must have a parent node "I", which must have another child node that does not reprexent "N"
13

---

Published as a conference paper at ICLR 2024
Then, follow the algorithm proposed in Dechter & Pearl (1987), after sorting the query the operator tree in the DNF, which is just ((n) ( time, as there are n variables in the operator tree, there only n 1 projection edges in the operator tree. We just need to prove that in computing the answer set for every variable in the operator tree, each projection edge has the complexity of O Specifically, we prove different lemma using the mathematical induction:
Lemma 28. For every variable node in the operator tree, as we have pointed out in Appendix B represents the answer set of sub Tree-Ford query d(u), prove its answer set A(o(u) S k.
Proof. For the leaf variable, since they are all constants, each one just needs (11) time to start with.
For a variable v, assuming all its child nodes in the operator tree have been computed. By the Proposition 27 we know that there is always child node such that there is positive edge linked from u to v in the operator tree.
has the complexity of O(k2): We check the set projection from
Given the answer set U corresponding to node u and satisfying that [8] S k. given the relation r, we prove that the set projection of U satisfies that {v[Ju U. s.t. r(c, b) 9) k. this is immediately right because of the definition of k.
Then by the nature of the set intersection, the size of the answer set of node is at most k(set union is omitted since the query is in DNF). In this way, we finish the proof by induction.
Then, we restate the original proposition here and prove it:
Proposition 29 (Adapted from Dechter & Pearl (1987)) The optimal complexity of answering TF queries in previous datasets (Ren & Leskovec 2020 Wang et al. (2021) is Onk??), where n is the number of terms and k is coefficient defined by the knowledge graph
k = max Ka E &8]b.a,,r, r, E or (b, (b, E GH TER
(8)
Proof. By the lemma above, we show that every projection edge is answered in O(k2) time. Since set complement, intersection, and union only takes ((k) time and the number of these operations also (n), finish the proof that solving the whole Tree-Form query in the Constraint Satisfaction Problem way has the complexity of (nkk²)
A.3 PROOF OF THE THEORETICAL GUARANTEES OF FIT
In this part, we give proof of the theoretical guarantees of FIT.
Theorem 30 (Perfectness). If matrices Pr JreR are perfect, then the FIT algorithm is perfect, meaning: A(p(y))(a) =1 = Alo(y)), Alo(v)((a) =0 > a & Alp(y))
Proof. Our definition of fuzzy truth value coincides with conventional truth value when the truth value of any atomic formula is in (0, }} (Thiele 1994). Thus, if the given matrices are perfect, our computed truth value coincides with the conventional truth value defined in first order logic.
Theorem 31 (Faithfulness). With assumption 22 for any EFO; query Φ(y) without negation, FIT reaches perfect faithfulness, meaning that every answer that can be deduced in the observed knowledge graph G.. A[o(v)[(a) =.
Proof. We create perfect matrices by the observed knowledge graph Go in Definition 20 the
truth value function induced by it is TV. By Theorem 21 answer a is deductible in G, and only if (a) 1. We note that T(r(b.c) c)) 2 (r) for any R. E, then by the non-decreasing t-norm and t-conorm, we know that T(ò(a)) 2 T'((())) = 1. Thus A (a)())((a) = T(?(a))
14

---

Published as a conference paper at ICLR 2024
B TREE FORM QUERY DERIVATION
In this section, we explain the derivation of the tree form query which we introduce in Definition Given relation r, the set projection of set B is {c|3b B. s.t. r(b, c) g).
For (bv) = r(a, y). A[o(u)] = [b|r(a, b) E 9}, which is projection of a single entity.
For general projection.
a E ABg.r(y, 8/) Avv)
3b E. a)) = =) (T((6)) 1)
3b E.r(b,a) E GADE Alø(y)
Thus we know that A[y.r((, v') A d(v)) is projection of set A(o(v)) with relation
The derivation of negation:
a(A(0(()) T(>((auu))= =1
T(o(a/u)) =0
- a & A(o(v))
A(o(y)
where A()(y) represents the complement set of A(o(y)). And we know A(-o(u) A(b(u))
The derivation of conjunction is given follows:
E Al(o A ())
= ())) =
= (T(o(a)) =) 1) (T(Ma)) 1)
a Alo(y) Aa E
Thus know Al( ())) = A(o(v) A A( (v)) The derivation of disjunction is the same.
C 1-NORM INTRODUCTION
Definition 32 (t-norm). A t-norm T is function: x0.1] [0,1] + [0.1] that satisfies the following properties:
Communitavity: aTb = bTa
(i) Monotonicity: (aTb) S fase
(iii) Associativity: (b aT(Tc)
(fv) Neutrality: a = a
Then the f-conorm is directly defined by a.l - T) b), which follows the De
Morgan's 's law.
Finally, we introduce some common (-norms which are of interest:
Godel: a c min(a,
iii Product: a T
(iii) Eukasiewicz: a T max(a b- 1,0)
In the main paper, mainly foeus the Godel and Product t-norm.
15

---

Published as a conference paper at ICLR 2024
D FIT METHODOLOGY DETAILS
In this section, we give the details of the proof used in Section 5 We elaborate the Fuzzy Inference with Truth Value (FIT) algorithm by the direct derivation from our previous truth value definition. discuss how to derive the answer vector of conjunctive queries 7, (v). The answer vector of the whole formula can then be computed by Definition 18] The main idea to cut node and edge step by step and infer on a smaller and smaller query graph.
To begin with, define new membership predicate (denoted ()) between variable and vector C. representing its fuzzy set, which leads to the truth value whether entity a belongs to a fuzzy set.
Definition 33. Given an entity a and a vector C' E [0, 1]lel, the truth value of membership predicate J is T(u(a, C)) C(a), namely, the a-th coordinate of the vector C.
Equipped with those definitions, we are allowed build our algorithm on solid fuzzy logic background (Klir & Yuan 1995).
D.1 STEP 1: INITIALIZATION
We initialize the fuzzy vectors for every non-entity node in the query graph G(1y): for node indicates either an existential variable or the free variable, we initialize C. = 1 by an all-one fuzzy vector. The original query is updated as (u)) A p(u, C.).
Let the derived query be d(y), which is >vv) conjuncted with membership predicates from all non-entity nodes.
D.2 STEP 2: REMOVE SELF-LOOPS
For any node that has self-loop, we discuss two situations, (I) is the answer node, and (2) u is not answer node. We note that the self-loop constant entity makes no sense.
Casel:Node is the answer node. In this case, we randomly select one of its self-loop edges, if it is positive, representing r(y.y) y)) putting every formula that contains y forehead, the query formula ((v) reads
(bv) = m(y, C2) A Ar( (by)
where (y) is a sub formula.
The answer vector A (d((y) is inferred by evaluating the truth value (((aa/)), then for all a E E,
A(o())((a) T(((a)) T(u(,, C2) A (() v()))
= (C.
By introducing T applying t-norm T element-wise, have the following vector form:
A(o(v) (C, o diag T A(((()))
ply. Cy To diag(P.)) p(y)
By this, we show that the self-loop edge can be removed as long as we update the corresponding fuzzy vector simultaneously.
the edge is negative, meaning it represents a formula -r(y, y), the derivation is similar:
A[o()){(a) = a( ((a)) (y( P,(a, ((( A(o(v)) Alp(V, C. T (1 diag P.))) v(v)]
16

---

Published as a conference paper at ICLR 2024
Thus, A(ø(y)) can be derived once we infer the answer vector of ((b(,)), where eb(y) is the simplified, inner formula.
Case 2:1f u represents existential variable Without loss of generality, assume there is only n positive self-loops ri (x,,x),... Tn (z, æ). Then, the formula reads d(y) = Zx, C²)) A (2c, 2) A... A (2, æ) x); where (y;; x:) is existential formula with the free variable and existential variable x which does not have sekf-loop anymore. For a E &, we have:
T(((a))
Lies (T(u(b, C+) A (1b,b))) A... (r, Ab(abbb L (b,6)T (T. TP, (
(U) b))
-T(Br.uu C2) A (a/y;
where C² = C2 TT diag(Pr,) @ TT diag(Pr..) Therefore, we can remove multiple self-loops similarly.
By the end of this step, all self-loops are removed.
D.3 STEP 3: REMOVE CONSTANT ENTITY
there node that represents an entity a, we can cut these edges from other nodes easily.
Considering all nodes that are connected to a, there are two situations:())) connects to the free variable y, and (2) connects an existential variable x.
Case 1: The edge connects a to the free variable
As the scenario of negative edge and multi-edge has been discussed, without loss of generality, we can assume there is only one edge from a to y and one edge from to a, which are both positive. We note that we get rid of the Assumption 14 naturally. The query formula p(v) reads
Φ ply, C.)) A (a, v) r2(y, A (vy)
where (3)) is sub formula.
([b(v)](b) = T(m(b, Cg) (n, (2 A vbb))
= -C,(b)TP, (2) =C(())T(((()) = A(C A (vy)(
where Cy Cy O TT (a) T (a). We also show that the inverse relations can be naturally tackled by the transpose of the predicate matrix.
Case 2:The edge connects to an existential variable
W.r.o.t, we can assume there only one edge from to x, the derivation similar with the one before:
((y) = μ(x, Cz) A ((,,
Al)())](b)
LieelI A2) (b;c))) L
= Alu(x, A (b))
In this way, all edges connected with a removed, and then node a is also removed. By the end of this step, all nodes in the query graph represents constants are removed well as these corresponding edges.
D.4 STEP 4: CUTTING LEAF NODE
In query graph, say node is leaf if it only connects other node v. If there is leaf node u in the query graph, We show that we are able efficiently cut the leaf node and do the inference the remaining graph, w.r.o,t, assume there is only one positive edge from
17

---

Published as a conference paper at ICLR 2024
There three cases in this step: Case 1:u and e represent two existential variables.
Similarly, w.l.o.g., assume the formula reads:
< 42 C.2) A (2),, A m(22, Cag) A v0
We want to update the candidate vector Cze instead of really enumerating all possible assignments of F1. That is say, we want to find C₂2y such that for every possible &, it satisfies:
T(((a)) = T(3x2-u422 Cz2) ((22, a))
For simplification, define an operation o that for matrix M, N and vector v, M o v _ N + (i.jj) = (i. (j),, let C* = [P, o To Cz, IT, and use the commutativity of t-conorm, the original formula can be reformulated as:
T()(a)) -1 - -10
(9)
And the desired form
T(r2,pu22 C₁ ()), = = (C
(10)
Compare equation and 10 since (1b((c, a)) is completely unknown, want it hold for every a, that:
We note this can not be done by arbitrary t-conorm. However, if the 1T is Godel, namely max, then by the nondecreasing of t-conorm have important conclusion:
max(C*(b, (B.c)
(bx
(1I)
b
Then we finally get desired C² (c) = max; [C* (b, c)}.
Case 2:u is the free variable y, is existential variable Then, the formula (gy) reads:
<ly) ply, Cy) (arr(a, vx))
where (xr) a formula with æ being the only free variable.
(()(v))(a)
TT (z)z)
If we define
A = o A[}(a))
where T is defined samely as main paper. We can have the simplification:
(a) =
In this way, can derive the final answer vector A(d(y) by computing the answer vector ((p((a)) first.
Case 3:If is an existential variable and is the free variable y. We also assume there is only one edge from u to u:
The formula ((y) reads:
(6v) Ar.u((,, Cr (r(a.)) ply. Cy) (4))
18

---

Published as a conference paper at ICLR 2024
FIT algorithm on any EFO, formulas, where FITC is FIT computed on query graph, explained in Algorithm(2
Algorithm 1:
Input: EFO; query ( Relation matrices [PrYreR
Change the EFO1 query to DNF, ΦDNF (v) = 7 (v) V .... V (m)));
for Y in (DNF(U) do
For the conjunctive query myyy,, create its query graph Gy;
Do the initialization, get [ErJ.EG. Compute each answer Ay, =FICC (Gyy {CuJueG,,): end
Aggregate the sub answers and get the final answer A(ø(v)) Li(An,] Output: A[o(y)]
The derivation is as follows:
(a)(v)((a) =
= ( =
where C [(P, T C2) T C.
Then we found that this is the same as the situation in equation 11 which we have explained already.
To be specific, provided 1 is Godel, we have the following derivation;
A (a
max (C (b, (((()))
z=b
max (Z7 z=b
Let C² (a) max a)] do the trick.
By the end of this step, all leaf nodes are removed.
D.5 STEP 5: ENUMERATION ON CIRCLE
We deal with the circle the query graph: the only technique cutting one node æ and doing the enumeration: T(3r.6(z)) T(o(a()(a)),
We choose a node u that cutting can still keep the remaining graph connected, whose existence is guaranteed by graph theory (Gallier 2011).
In practice we can set a hyperparameter to limit the maximum number of enumerations, by the assumption 22 we can distinguish observed nodes from predicted ones. For node u, sort all its candidates and enumerate {a (lC.((a) = 13 + M the most possible ones.
In this step, we choose node in the query graph to become constant entity, which allows for returning back to step 3 again. In this way, the query graph becomes smaller and smaller.
D.6 STEP 6: GETTING ANSWER VECTOR
As all steps assure the connectivity of the query graph, finally, the query graph will only contain the free variable with the only remaining formula being p(y, C.), then by definition, its answer vector will be Cy.
Additionally, we offer the pseudo-code for our FIT algorithm in Algorithm I and Algorithm 2 We also note that the design of the FIT algorithm is versatile and can extended a more complicated version (Fei et al. 2024).
E COMPLEXITY OF FIT ALGORITHM
We discuss the complexity of FIT algorithm here. For FIT on a general query graph, it clearly NP-complete due discussion in Section 4.3 Specifically, FIT has the complexity of O((E)),
19

---

Published as a conference paper at ICLR 2024
Algorithm 2: FIT on a conjunctive query, which is represented by query graph. We name it FTTC for short.
FITC (G, (EEG)
if G contains only one node then return Cy end
contains a node with self loop edges. then
Remove the self loop edges and changes C, simultancously explained in Step 2;
end
contains constant entity node, then Remove the constant entity node explained in Step 3;
10 end
if G contains a leaf node which only connects to node then u represents free variable, represents an existential variable. then Change to free variable, removing the node the new query graph is G' sub answer FITC (G', (CuJae))
12
14
final answer is computed by sub answer Step case 2: return final answer end else if u represents existential variable, represents the free variable. then Update C. according to Step 4, case 3, getting C" Remove the node u, the query graph is G"; return FITC (G', (Cr)))))))
16
17
19
21
22
end else
24
Update C. according to Step 4, case 1, getting C"; Remove the node u, the query graph is G"; return FTTC (G', (Cr)herr
26
27
end
28
end
else
30
Find a node u to enumerate, according to step
Construct the candidate list for node namely the top N biggest index of C., where
= M {a E (a) = 1}:
Create matrix E [0, 1] No to store enumerate answer;
32
33
for The ith candidate of node u. do Store the original truth value of (a) Change the C, to the one-hot vector C₁ 1 (==a)
34
35
36
Change the node u represent a constant entity query graph, creating G';
37
Enumerate answer A = FITC E[i] = x (a)
38
39
end
40
return (i,,(i
41 end
where the number the variable in the query graph. the worst case, the query graph has no constants and is complete graph and FIT degrades to enumeration because of circles.
However, have also discussed in Section 4.3 Tree-Form queries are known be tractable and we would like to discuss FIT complexity in the TF n EFO, queries, the result is given as the following:
Lemma 34. For query graph with variables, brutal-force implementation of FIT has complexity of 0( x 18(2).
*Complete graph means that every node in the graph connects every other node in the graph.
20

---

Published as a conference paper at ICLR 2024
Proof. We prove this lemma easily by noticing that the complexity in Step 3 and Step 4 is all we need to consider. We note that the bottleneck the complexity comes from the computation of C [P, o C2)T of C2]T, which is O(EE?), while the other computations have no larger complexity, Because takes O((E)²) to remove one node in the query graph, the total complexity is On x (
Proposition 35. For a query graph with n variables, an efficient implementation of FIT has complexity On x ) where is coefficient defined by the sparsity of the matrix.
t= max {a E (,,b,P((a,b) 0 or P. a) > 0H reR
(12)
Proof. The proof is straightforward by the same proof technique used in Appendix A.2 By the definition of t, every matrix of relation r can be simplified as an t * t dense matrix, and every Cn in the computation process is guaranteed to have no more than elements that larger than 0. Then, the optimal complexity of FIT is On x e.).
F TRAINING AND TESTING DETAILS
We utilize pretrained neural link predictors provided by Minervini et al. (2022), who followed previous knowledge graph embeddings method (Trouillon al. 2016) which gives score s(h, a, b) for every possible triple(a,
(a, r, b), where a, b E &,r E R. To convert real number scores to truth value that falls into [0, 1), we use the softmax function:
exp(s(a,r,b)
7.a (b)
E Exegerp(s
However, we notice that this implies that there's only one tail node for (a, r). thus we compute the scaling factor by utilizing the observed edges in the observed graph Go. We define the Ear (b (a, b) E G.).
E Ear Pr Palo) (e))
if Ea,rl >>
Qa,b
1,
if Ea,rl 0
For training, we just clamp the value for each triple:
(r b) min(1, P; (b) * Qa,b)
However, in testing, we compute the final truth value by combining the computed probability with the required property in Assumption 22
1,
if E Ear P:t (b) Qa,b <e
()
0.
if P
(13)
min(Pr; (b) Qa,b, -),
otherwise
We note that c, are hyper-parametern acts as threshold which ensures for every r, P, a sparse matrix and 8 > 0 is required to meet our Assumption 22
Once the P, is sparse matrix, our complexity discussion in Appendix E applies. However, there are some query types that do not require the matrix to be sparse, namely the 1p. 2i, 3i, 2in, and 3in, since there no existential variable them. Therefore, the computation becomes simple as we only need to compute one in the whole matrix.
Therefore, when dealing with these five query types, we just use the dense matrix:
[1, Imin(P:.. (6) * Qa,r 1 8), otherwise
if Ear
(,
(14)
21

---

Published as a conference paper at ICLR 2024
For the training, only 1p, 2i, 3i, 2in, and 3in query types for efficiency, the reason is explained above. The learning rate set to 0.0001, the batch size set to 64, the maximum training step is set to 5,000 steps and choose the best checkpoints by the scores in the validation set. The choice of the hyperparameter is Appendix H
G CONNECTIONS TO PREVIOUS METHODS
In this section, we discussion the connections between FIT and previous methods.
G.1 CONNECTION TRADITIONAL METHOD
It has been traditionally found that acyclicity is the key to tractability: researchers from two dif- ferent backgrounds, namely the databases theory (Yannakakis) 1981) and constraint satisfaction problem (Dechter & Pearl 1987) has all found out that conjunctive queries can be evaluated in polynomial time it is acyclic. However, their results are both classical settings, where the truth value can either be 0 or 1, while our setting extremely general, not only do we have a probabilistic value for each triple, but our Definition T8 is the most general one which allows for two arbitrary t-norms be included in the computation. Moreover. we offer efficient computation that is purely vectorized, which is provided in detail in Appendix [ Most significantly, FIT is a neural-yymbolic method, the neural link predictor can be fine-tuned by complex query further address the OWA, while the traditional methods can never predict any answer that is not observed in Go. which is why machine learning techniques should step in.
G.2 CONNECTIONS TO QTO
We note that QTO (Bai al. 2023) only a simplified version of FIT, in other words, FIT is a natural extension of QTO in the sense that FIT is capable of solving EFO, queries that QTO fails to represent syntactically because QTO relies on the operator-tres method. Moreover, please see the proposition below for the inference of queries within TF n EFO,
Proposition 36. FIT can coincide with QTO when answering queries within the TF EFO, family,
Proof. Since QTO also converts all formulas in DNF, we are allowed to consider only conjunctive queries. Consider a conjunctive query
1
.n A A
where a; is and atomic formula or its negation. Then, we note that for the objectives of QTO, it aims find free variable y such that it maximizes:
(ly) max T(a)) TT(am) -. [T(o) TT((m
(15)
where the 1 is Godel I-conorm, and the truth of value is negation is also defined by T(-Ø)
1 - (o)) in QTO (Bai et al. 2002).. By the analysis, we show that these optimization objectives naturally coincide with the definition of truth value proposed systematically in Definition [8] Thus, QTO and FIT yield the same result in TF n EFO; queries as long as these requirements are met: 1. The same learning-base matrix is given with no further fine-tuning, 2. FIT chooses Godel to be its existential t-conorm and product to be its conjunctive f-norm, and 3: In queries with no existential variable, FIT also uses a sparse matrix rather than the dense ones.
We have also done experiments to verify this proposition, we show the result in Table in which we show they coincide with each other. In this way, we show that QTO is best a special case of FIT, and FIT serves as superior alternative to QTO in all EFO, queries.
H HYPERPARAMETER IMPACT
In this section, we discuss several hyperparameters used in the FIT algorithm.
22

---

Published as a conference paper at ICLR 2024
Table 4: The MRR results(%) of FIT versus QTO on the TF BFO, queries (BetaF dataset) FB 1513--337.
1p
2p
3p
1p
pi up
3im
inp
pin
AVG.
FIT QTO
0
Table 5: Matrix related hyper parameter impact on the MRR results(%) on the BetaE dataset on FB15k-237.
1p
22
.p
1p
pt
u3p
pin
up
AVG
0,002, 0.001
19.99
0.005, 0.001
46.70
14.61
12.80
37.52
$1.55
21.83
30.10
13.99
19.99
10.18
9.55
18.04
13.08
23.08
0.05,, 0.01
46.70
14.02
12.80
37.54
51.54
21.88
30.10
13.99
38.01
10.17
9.53
18.04
13.09
23.00
0.001
51.55
13.99
13.07
22.98
For the threshold 6, we use 0.005 for both FB15k-237 and FB15k, 0.0002 for NELL. For the 8, is 0.001 in all datasets. For M, is 10 in all datasets. As for the tnorm, We choose Godel (maximum) to represent the existential quantifier as discussed in equation [1 and we choose the product to represent logic conjunction because of its clear probability interpretation, which also follows the previous research (Arakelyan et al. 2020). Then we study the impact of each hyper-parameter one by one.
Here present the impact of the hyperparameter, the result is shown in Table 5
As shown, the impact of 5 is vert marginal, because very few predicted answers have comparable scores with the observed answers. As for the the smaller, the better, which kind of obvious because the larger threshold monotonically leads to sparser matrix that loses more information about the sorting of the predicted tail variables. Moreover, note when inferring 2p,2i,3i,2in, and 3in queries, we do not use the sparse matrix, therefore have no impact on these query types.
Then we also discuss the impact of setting the maximum number of enumerations, the result shown in Table where we can see that bigger M leads to better performance, which is intuitively true because taking more possible candidates for inner variables into consideration beneficial for getting the final answer.
Finally, we show that it's also possible to choose other t-norms for the conjunction, using Godel as the conjunction (-norm also has its own advantage in some queries though it is slightly worse than the product on average, shown in Table 7 However, as our computation in equation Ishows, using Godel the existential t-norm is the only practical way for allowing FIT to compute efficiently.
I
SELF LOOP
Though this circumstance is allowed in logic and explained in our Section 5
we find that it is rare real-world KG like NELL. In fact, there are only four relations in NELL that have self-loop. In FB 15k and FB 1B15--237, most of the self-loop triples are redundant like "New York is located at New York". Thus, we do not sample formulas with self-loop, which is also inherited by other work (Yin) et al.
2023 2024).
J DATASET STATISTICS
The number of queries in the newly developed real EFO; dataset shown Table We note that the "pni" data retains the previous queries sampled by Ren & Leskovec (2020). thus, retain the number of queries to be different different datasets. For those brand new queries proposed by ourselves, sampled 5000 for each query type in each dataset.
For the formal first order formulas of our newly developed real EFO, dataset, we also offer them in the following Table
23

---

Published as a conference paper at ICLR 2024
Table 6: Max enumeration impact the MRR results(%) the circle query FB15k-237.
M
3c
3om
AVG.
19.2
37.1
38.2
20
39.5
37.5
38.5
Table 7: The impact of changing conjunction t-norm on the MRR results %) on FB 153-22337
Method Product
Queey Type
pai
2d
2m1
2nm
3eap
3gen
im
3c
Scm
AYG.
EFOI
14,9
34.2
51.4
9.9
12.7
19.6
11.9
7.7
39.4
37.3
23.9
33.6
49.3
5.4
14.9
6.0
33.3
Method
Query Type
1p
3p
1p
2in
3in
pin
2x
AVG.
Codel
14.1
12.0
35.1
19.7
28.3
20.3
10.0
21.9
K BASELINE IMPLEMENTATION
In this section, illustrate the implementation of the baseline method, as have explained in Section 3 previous methods can not directly represent our newly developed dataset. One example in Figure illustrates how the Tree-Form queries approximate newly developed queries to their best.
For those methods that depend the operator tree, which include BetaE (Ren & Leskovec 2020), LogicE (Luus et al. 2021), ConE (Zhang et al. [222]) and QTO (Bai et al. (023). similarly with the example Figure
manually create a new operator tree approximate each of our formulas, which is explained in Table and and Table [T Because of the limitation of the operator tree form, these formulas are only approximations, we also offer the real logical formula it represents, making the difference with the real EFO; formulas in Table 9 more apparent. For the method that utilizes query graph (Minervini et al. 2022 Wang al. 2023b), we use our query graph with their provided checkpoint directly.
24

---

Published as a conference paper at ICLR 2024
Table 8: Statistics of our new proposed real EFO, dataset.
Knowledge Graph
pni
2il
2nm
5mp
3pm
im
3c
3cm
FB15k-237
10a
x 10a
5 10a
5 x 10a
5 x 10a
5 x 10a
5 10a
5.x 102
x 10a
x 10a
FBI 15k
x 10a
5 10a
5
5 x
5 x 10
5 10a
5 10a
5 10
x 10
x
10
10
5 10
x 10a
5 x 10
10
10
5 10
x 10
x 10
Table Formal definition of the new proposed dataset, where a, E & are entities from knowledge graph, 24 are bounded existential variables, and y is the single free variable.
Name
EFO; Formula
pai
32.r1 a) -ra y) (2(22.))
2i1
3z.r1(..)) A
3i1
Rz.ri(11.3) r2(22. Arg(a,
3z.r1(0,2]) (.. (aa())))))
2nm
3z.ri(a,2)
3mp
( (ra((22))
3pm
(0, (21. Arg(222)) Ar(22.)))
in
3z.ri(a1. r2 (a.. Ar(z).)
3c
521.
(2 A A Ararrzy)) Ars(ni
Jem
12 (01,2)) (2 Aalgg, A Ara(22 A ra(m1, A (e(m))))
Table 10: The lisp-like formula for the approximation of our newly developed dataset, it invented by Wang et al. (202T) express any kind of Tree-Foree query.
Lisp-like
pni
G.t..p..p..cllM.p...ce)
(p.te)
3il
(.dp.ee)).p.e))))
(.Ip<p.ee))Mmm.p.eell)
2nm G.dm.pp..p.cm)...ppp4.00))
3mp
(p.t.pp.pp.e)l...ppp..e))
3pm
(iprpp.peeelMMpppppppee)))
im
3em
Table 11:
The formal first order logic formula for the approximation of our newly developed dataset.
Name
Tree Form formula
pni
Va.ra(b,, y) (-,1 -)s(a,)) r(a, v)
2il
r1(0, v) (2(bgg)
2m
3ei, 82. (a) A (2(1 g) ri(a, A Arsezzy)
2am
An, Vana. (a, A ra(21.9) A (-mi (a) -ra(m,
221.22.03.
(2(21, (2) (1(e, (rl(aa,01)) rs(aar))
3pm
R2,, (a, 21) rafan. As(e2. An (n 12(23, Ar((2.
Bey, (an, (1) raldg, 22(21.0) Amla, mg) ra Ar
3e
(a- (2(21.)) (ra(ag. (a) ag) n2(3s. (4(22,
3em
321 82i Ra. (2
rala (0 24) ra(2a, W)] Ara(O2, (02))22) 22) ri(a1, aa) (sss,, a2) A r4(22, 8)
25


Reviews:
[{"review_id": "8nNtgNZH88", "reviewer": "Reviewer_sXg1", "summary": "The paper addresses neuro-symbolic execution of knowledge graph queries. The authors use a graph representation of a symbolic (first order logic) query, and for potentially incomplete knowledge graphs, the authors propose FIT, an algorithm to compute the answer to a query in a message-passing type of algorithm over the query graph, with probabilities of all possible relations. They argue that tree-form queries cannot represent queries with existential leaves, so they cannot cover the full space of first order logic. They show experiments where FIT outperforms existing query graph execution approaches on 10 sampled query types from 3 KGs.", "questions": "See weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. For incomplete knowledge graphs, proposed algorithm FIT is essentially a custom message-passing algorithm over nodes and edges computing the probability of every possible relation and updating the neighboring node probabilities accordingly to reach the answer set. It may have the advantage of staying faithful to the allowed relations or combinations from the query graph and KG, since it builds the solution by exploring only those combinations, and using back-propagation to update the values from the actual answer.\n\n2. The experiments confirm improvements over existing first order logic neuro-symbolic methods for computing the answer set.", "weaknesses": "1. Baselines - Graph neural networks (based on message passing and backprop over the query graph) is likely a baseline to consider, since this follows a more controlled message passing approach to the solution. This was not considered in the paper. The overall performance in mean reciprocal rank is still low (~30) in two of the datasets. What would explain the difficulty or effectiveness in those cases?\n\n2. Presentation - The computation of the Cu(node) from the probability of the relations, is not provided in the paper (It should be in the main paper, not the appendix, to allow for key aspects to be presented as a whole). The introduction could be clearer about how or why this fuzzy approach (or neural symbolic approach) is required for incomplete KGs. Are there other benefits of it?\n\n3. The proof for tree-form not capturing all first order logic queries I am not sure about. The authors suggest that existential leaves cannot be represented, but that does not prove that any FOL query could not be converted into a potentially different tree form structure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i5gl40fMsx", "reviewer": "Reviewer_TtwJ", "summary": "The paper has 2 main contributions:\n\n1. Describing the gaps in EFO1 queries studied by past work\n- Past work [1] has studied a subset of existential first-order logic queries on knowledge graphs (KGs). In particular, past work has studied tree-form queries with negated atomic relations\n- Authors point out that the studied query types do not entirely cover the EFO1 query family and describe the missing families of query structures\n- They create a dataset Real-EFO1 that consists of EFO1 query structures not studied by past work and benchmark competitive graph query execution approaches\n\n2. Proposing a fuzzy-logic based approach for executing EFO1 queries on knowledge graphs\n- Authors propose a fuzzy-logic based query execution algorithm Fuzzy Inference with Truth values (FIT)\n- The algorithm extends QTO proposed by [2] in the following ways:\n    - It extends QTO to handle cycles in the query graph\n    - It sparsifies the neural link prediction matrices to improve the run-time complexity of the algorithm for certain query types\n    - It demonstrates that the link predictor can be trained end-to-end directly with the query execution training data\n\n[1] Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. NeurIPS 2020\n[2] Yushi Bai, Xin Lv, Juanzi Li, and Lei Hou. Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization. ICML 2023", "questions": "Questions\n---\n1. I would like to reiterate Weakness 1 described above. I believe that the definition of tree-form queries used in this work differs from the definition used by past work and that the mismatch makes Section 3 obsolete. Please comment.\n\nTypos\n---\n1. (Important) Definition 6: Missing definition of EFO1 query family\n\nSuggestions\n---\n1. Eq 4: It would be good to have an intuitive definition of k here\n2. Overall, the paper pushes a lot of context to the Appendix. It would be helpful if the main paper summarized the corresponding Appendix section rather than just point to it", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 4, "strengths": "1. The paper clearly describes differently query families and establishes the query structures that are missing from past work\n2. The proposed Real-EFO1 dataset extends the family of query structures studied in the query execution literature with intuitive examples and connections to past work\n3. The proposed FIT approach shows consistent improvement over the baseline approaches and is properly ablated\n    - Experiments show that FIT reduces to QTO under the appropriate conditions and that the additional differences lead to performance improvements across all settings\n    - Examples show how past approaches (designed for tree-form queries) cannot easily handle the new query structures while fuzzy inference can handle them", "weaknesses": "1. I believe that the paper misunderstands the definition of tree-form queries used by [1]\n    - [1] explicitly limit their definition of tree-form queries to only consider the negation of individual atomic formulae (i.e. they consider queries can by build from a query tree using $r(x, y)$ and $\\neg r(x, y)$. Therefore, the problem of introducing universal quantifiers is avoided by [1]\n    - However, definition 8 in this paper uses a different (broader) definition of tree-form queries. Under this new definitions, tree-form queries could require universal quantification and fall outside the EFO1 category\n    - I believe this mismatch shakes some of the grounded for Section 3 (Section 4 is still valid in my opinion, since it tries to describe EFO1 - TF)\n2. The connections between FIT and QTO are not sufficiently stressed in the main paper (and this analysis is pushed to the Appendix)\n    - I believe that making this connection is important for a fair comparison to QTO\n\n[1] Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. NeurIPS 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LZfOl0bItH", "reviewer": "Reviewer_Z6xA", "summary": "This paper shares author's rethinking over complex queries on knowledge graph with neural link predictor especially towards answering EFO_1 queries. Authors discussed the difference between previous widely researched tree-form queries and EFO_1 queries and their relationships, and pointed out that the tree-form queries are with unrigorous formulations. Thus they propose to pull the complex query answering research back to answering EFO_1 queries with rigorous formulations, and propose a method with neural link predictor based on fuzzy logic theory, called FIT. FIT outperforms baselines significantly in the new EFO_1 query dataset and also surpasses baselines in the existing dataset at the same time.", "questions": "1. Should the $r_1$ and $r_2$ be exchanged in Equation (3)? i.e. Should Equation (3) be $\\forall x. (r_3(b, y) ∧ ¬r_2(x, y)) ∨ (r_3(b, y) ∧ ¬r_1(a, x))$ ?\n2. What is main difference between FuzzQE and FIT?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Authors rethink complex queries on KGs with theoretical analysis. \n2. A new EFO_1 dataset are created to evaluate the EFO_1 query answering task. \n3. And the proposed method FIT shows good performance over EFO_1 datasets and existing tree-form datasets.", "weaknesses": "The basic idea of the new proposed method is based on fuzzy logics and neural link predictor. This general idea is also introduced in FuzzQE[1]. But the key difference between FIT and FuzzQE is not clearly discussed and FuzzQE is not compared in Table 2.  \n\n[1] Xuelu Chen, Ziniu Hu, Yizhou Sun. Fuzzy Logic Based Logical Query Answering on Knowledge Graphs.  AAAI2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "06zc4YycKG", "reviewer": "Reviewer_QmUh", "summary": "The paper addresses the challenging task of reasoning on knowledge graphs using neural link predictors. The prevailing method in this field is query embedding, which treats logic operations as set operations and has shown empirical success. However, the paper argues that many claims made in previous research lack a formal and systematic inspection. To address this, the authors characterize the scope of previously investigated queries, identify the gap between the formulation and the goal, and provide complexity analysis for the queries. They also introduce a new dataset with ten new types of queries and propose a new neural-symbolic method called Fuzzy Inference with Truth value (FIT) that combines neural link predictors with fuzzy logic theory. The empirical results demonstrate that FIT outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset.", "questions": "The paper could benefit from providing more examples and illustrations to aid in understanding the concepts and methodologies discussed.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper shows many different opinions against previous series of works. The discussion firmly supports that TF query family is not even a subset of EFO1. In addition, the paper rethinks the traditional claim that “reasoning involves an exponential growth in computational time”. The proposition and analysis finally found that the Tree-Form EFO1 reasoning complexity is linear to the number of variables in the query.\n2. The paper provides a comprehensive analysis of the prevailing method of query embedding and its limitations. It identifies the gap between the formulation and the goal, which adds clarity to the field and helps in understanding the limitations of existing approaches.\n3. The introduction of a new dataset with ten new types of queries is a significant contribution. This dataset allows for a thorough investigation of complex queries and provides a benchmark for evaluating future methods.\n4. The proposed method, FIT, which combines neural link predictors with fuzzy logic theory, is a novel approach. It addresses the limitations of previous methods and demonstrates improved performance in both the new and existing datasets.\n5. The paper presents empirical results that support the superiority of FIT over previous methods. The significant improvement in performance in both datasets strengthens the credibility of the proposed method.", "weaknesses": "Lack of introduction to related works: The paper lacks a section on related works, making it difficult for readers who are not familiar with the definitions and concepts in previous research. This can hinder the understanding of the paper and limit its accessibility to a broader audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)