Logical Message Passing Networks with One-hop Inference on Atomic Formulas
Authors: Zihao Wang
Yangqiu Song
Ginny Wong
Simon See
Venue: ICLR 2023 poster (2023)
Keywords: knowledge graph
complex query answering
graph neural network
representation learning

Abstract: Complex Query Answering (CQA) over Knowledge Graphs (KGs) has attracted a lot of attention to potentially support many applications. Given that KGs are usually incomplete, neural models are proposed to answer the logical queries by parameterizing set operators with complex neural networks. However, such methods usually train neural set operators with a large number of entity and relation embeddings from the zero, where whether and how the embeddings or the neural set operators contribute to the performance remains not clear. In this paper, we propose a simple framework for complex query answering that decomposes the KG embeddings from neural set operators. We propose to represent the complex queries into the query graph. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning for complex query answering. We leverage existing effective KG embeddings to conduct one-hop inferences on atomic formulas, the results of which are regarded as the messages passed in LMPNN. The reasoning process over the overall logical formulas is turned into the forward pass of LMPNN that incrementally aggregates local information to finally predict the answers' embeddings. The complex logical inference across different types of queries will then be learned from training examples based on the LMPNN architecture. Theoretically, our query-graph represenation is more general than the prevailing operator-tree formulation, so our approach applies to a broader range of complex KG queries. Empirically, our approach yields the new state-of-the-art neural CQA model. Our research bridges the gap between complex KG query answering tasks and the long-standing achievements of knowledge graph representation learning. Our implementation can be found at https://github.com/HKUST-KnowComp/LMPNN.

Published as a conference paper at ICLR 2023
LOGICAL MESSAGE PASSING NETWORKS WITH ONE-HOP INFERENCE ON ATOMIC FORMULAS
Zihao Wang & Yangqiu Song CSE, HKUST
Ginny Y. Wong & Simon See
NVIDIA AI Technology Center (NVATIC), NVIDIA Santa Clara, USA {gwong, ssee @eeeeiiiii...m
Hong Kong SAR
{zwangge, y @csecceeeeoo..o hk
ABSTRACT
Complex Query Answering (CQA) over Knowledge Graphs (KGs) has attracted a lot of attention to potentially support many applications. Given that KGs are usually incomplete, neural models are proposed answer the logical queries by parameterizing set operators with complex neural networks. However, such meth- ods usually train neural set operators with a large number of entity and relation embeddings from the zero, where whether and how the embeddings the neural set operators contribute to the performance remains not clear. In this paper, we propose a simple framework for complex query answering that decomposes the KG embeddings from neural set operators. We propose to represent the complex queries into the query graph. On top of the query graph, we propose the Logi- cal Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas the global logical reasoning for complex query answering. We leverage existing effective KG embeddings to conduct one-hop inferences on atomic formulas, the results of which are regarded the messages passed in LMPNN. The reasoning process over the overall logical formulas is turned into the forward pass of LMPNN that incrementally aggregates local in- formation to finally predict the answers' embeddings. The complex logical infer- ence across different types of queries will then be learned from training examples based on the LMPNN architecture. Theoretically, our query grapp representation is more general than the prevailing operator- tree formulation, so our approach applies broader range of complex KG queries. Empirically, our approach yields a new state-of-the-art neural CQA model. Our research bridges the gap between complex KG query answering tasks and the long-standing achievements of knowledge graph representation learning. Our implementation can be found at https::/githunn cww HKUST KnowComp/ LMPNN
INTRODUCTION
Knowledge Graphs (KG) essential sources of factual knowledge supporting downstream tasks
such as question answering (Zhang et al. 2018 Sun et al.) 2020 Ren et al. 2021). Answering logi-
cal queries is a complex but important task to utilize the given knowledge Ren & Leskoved
2020
Ren et | 2021). Modern Knowledge Graphs (KG) (Bollacker et al. 2008 Suchanek et al. 2007
Carlson al. 2010). though on great scale, is usually considered incomplete. This issue well known as the Open World Assumption (OWA) (Ji et al. 2021). Representation learning methods mitigate the incompleteness issue by learning representations from the observed KG triples and generalizing them to unseen triples (Bordes et al.) 2013: Trouillon et al. 2016 Sun al. 2018: Zhang et al. 2019) CCamii al. 2020). When considering logical queries over incom- plete knowledge graphs, the query answering models are required to not only predict the unseen knowledge but also execute logical operators, such as conjunction, disjunction, and negation (Ren Wang et 2021b).
are employed
& Leskovec 2020
Recently, neural models for Complex Query Answering (CQA) have been proposed to complete the unobserved knowledge graph and answer the complex query simultaneously. These models aim to address complex queries that belong to an important subset of the first-order queries. Formally speaking, the complex queries Existentially quantified First Order queries and has single free

---

Published as a conference paper at ICLR 2023
variable (EFO-1) Wang et al. 2021b) containing logical conjunction, disjunction, and negation (Ren & Leskovee 2020 The EFO- queries are transformed in the forms of operator trees, c.g., relational set projection, set intersection, set union, and set complement (Wang et al., 2021b). The key idea of these approaches is to represent the entity set into specific embedding spaces (Ren & Leskoved 2020 ZZhang al., [02T]] Chen et al. 2022). Then, the set operators are parameterized by neural networks (Ren & Leskovec 2020] Amayuelas et al., [2022) Bai et al. (2022). The strict execution of
the set operations can be approximated by learning and conducting continuous mappings over the
embedding spaces.
is observed by experiments that classic KG representation (Trouillon et al. 2016) can easily out- perform the neural CQA models in one-hop queries even though the neural CQA models model the
one-hop projection with complex neural networks (Ren & Leskovee 2020 Amayuelas et al. 2022 Bai et al. 2022). One possible reason is that the neural set projection is sub-optimal in modeling the inherent relational properties, such as symmetry, asymmetry, inversion, composition, etc, which are sufficiently discussed in KG completion tasks and addressed by KG representations (Trouillon al.) Sun et al. 2018). On the other hand, Continuous Query Decomposition (CQD) (Arakelyan 2021) method searches for the best answers with a pretrained KG representation. The log- ical inference step is modeled as an optimization problem where the continuous truth value of an Existential Positive First Order (EPFO) query is maximized by altering the variable embeddings. However, the speed and the performance of inference heavily rely on the optimization algorithm. It also assumes that the embeddings of entities and relations can reflect higher-order logical relations, which is not generally assumed in existing knowledge graph representation models. Moreover, it is unclear whether CQD can achieve good performance on complex queries with negation operators |
2016
et al.
In this paper, we aim to answer complex EFO-1 queries by equipping pretrained KG representations with logical inference power. First, we formulate the EFO- KG queries as Disjunctive Normal Form (DNF) formulas and propose to represent the conjunctive queries in the form of query graphs. In the query graph, each edge is an atomic formula that contains a predicate with a (possible) negation operator. For each one-hop atomic formula, we use the pretrained KG representation to infer the intermediate embeddings given the neighboring entity embedding, relation embedding, direction information, and negation information. We show that the inference can be analytically derived for the KG representation formulation. The results of one-hop atomic formula inference are interpreted propose
as the logical messages passed from node another. Based this mechanism, a Logical Message Passing Neural Network (LMPNN), where node embeddings are updated by one Multi-Layer Perceptron (MLP) based on aggregated logical messages. LMPNN coordinates the local logical message by pretrained knowledge graph representations and predicts the answer embedding for a complex EFO-1 query. Instead of performing on-the-fly optimization over the query graph as CQD (Arakelyan et al. (021). we parameterize the query answering process as the forward pass of LMPNN which is trained from the observed KG query samples.
Extensive experiments show that our approach is a new ofate-of-the-arr neural CQA model, in which only one MLP network and two embedding vectors are trained. Interestingly, we show that the optimal number of layers of the LMPNN is the largest distance between the free variable node and the constant entity nodes. This makes it easy to generalize our approach to complex queries of arbitrary complexity. Hence, our approach bridges the gap between complex KG query answering tasks and the Long-standing achievements of knowledge graph representation learning.
RELATED WORKS
Knowledge graph representation. Representing relational knowledge is one of the long-standing topics in representation learning. Knowledge graph representations aim to predict unseen relational triples by representing the discrete symbols in continuous spaces. Various algebraic structures (Bor-) des et al., 2013 Trouilon et al., 2016)) Sun et al.) 2018 Ebisu & Ichise 2018 Zhang et al. 2019) are applied to represent the relational patterns (Sun et al., 2018) and different geometric spaces (Chami al. 2020 Cao et al. (002)) are explored to capture the hierarchical structures in knowledge graphs. Therefore, entities and relations in large knowledge graphs can be efficiently represented in a con- tinuous space.
Existing empirical evaluations all conducted queries without negation Arakelyan et al.
2021
2

---

Published as a conference paper at ICLR 2023
Neural complex query answering. Most existing works treat the complex queries as operator
trees (Ren et al.
2020 Ren & Leskoved 2020; Wang et al. 2021b). The query types that can
be answered are extended from existential positive first-order (EPFO) queries (Ren et al. 2020
Choudhary et al.
2021 Arakelyan et al. )02T) to the existential first-order (Ren & Leskovec
2020
Zhang et al. 2021 Bai al. (022). more specifically EFO-1 queries (Wang 202TTb. In
neural CQA model, the entity sets are represented by various forms, including probabilistic distri-
butions (Ren & Leskovec 2020 Choudhary et al., [021] Bai et al. 2022), geometric shapes (Ren
et al., 2020; Zhang et al. 2021), and fuzzy-logic- inspiied representations (Chen et al. 2022) In
contrast to knowledge graph representations, the relation projections between sets are usually mod-
eled by complex neural networks, including multi-layer perceptron (Ren & Leskoved 2020). MLP-
mixer (Amayuelas et al. 2022), or even transformers (Bai et al. 2022). However, their performances on one-hop queries are shown to be worse than the tfte-of-the-ar but simple knowledge graph rep- resentation (Trouillon et al., 2016). Other works compiled the queries into the graphs and then solve queries with graph neural networks (Daza & Cochez 2020; Liu et al. 2022). In contrast to this work, existing investigations only focused on EPFO queries and require to train the entire GNN from zero. Notably, knowledge graph representations also provide effective signals when answering complex queries. Specifically, CQD (Arakelyan et al. 2021) uses the KG representation to calculate the continuous truth value of an EPFO logical formula with the logical I-norms. Then, the embed- dings are optimized to maximize the continuous truth value. The optimization can be applied in the embedding space as well as the symbolic space. Our experiments show that this method performs badly on complex queries with logical negation, see Section 4.3
3 PRELIMINARIES
In this section, we formally introduce the knowledge graph and related model-theoretic concepts. These concepts are helpful when we define the DNF formulation of EFO-1 queries in Section [ Then, we introduce the abstract interface of knowledge graph representation. which is useful in defining one-hop inference in Section
Model-theoretic concepts for knowledge graphs. A first-order language L is specified by a triple (F, RRC)) C)) where F, R. and C are sets of symbols for functions, relations, and constants, respectively. A knowledge graph is specified under the language Lxg. where function symbol set F = 0 and relation symbols in R denote binary relations. A knowledge graph KGG is an Lxg-structure given the entity set V. where each constant E C V is also an entity and each relation E R is a set r VV V. We say r(t1, f2) = True when (f1, t2) E r. A knowledge graph is usually defined by the relation triple set ε = {(h, r, t)). where h and are entities such that (h, t) E r. The Open World Assumption (OWA) means only a subset of & can be observed. The observed knowledge graph is denoted by K.Go A ferm is either constant or or 12) where 1 and to are terms and r is a relation. In the following parts, we use a. to denote an atomic formula. Then the first order formula can be inductively defined by adding connectives (conjunction A, disjunction V. and negation -) to atomic formulas and quantifiers (existential and universal Y) variables. The formal definition of first-order formulas can be found in Marker (006). A variable is bounded when associated with a quantifier, otherwise, it is free.
variable. And atomic formula is either r(t1, t2)
3.1 KNOWLEDGE GRAPH REPRESENTATIONS
Our approach relies upon the following abstract interface of knowledge graphs. Given the head entity embedding h, relation embedding r, and tail entity embedding t, knowledge graph representation is able to produce a continuous truth value wh( r,t) in [0, 1] of the embedding triple (h, r, t). In the symbolic space, whether (h, E is indicated by the {0, 1} truth value of r(h, f). In the embedding space, (h, r, t) indicates the "probability" that (h, t) E r. Hence, this definition is a continuous relaxation of the {0. 1} truth value.
Each knowledge graph representation has a scoring function @(h, r, (). which can be based on a similarity function or a distance function. It is easy to convert such functions into &e by applying the Sigmoid function with necessary scaling and shift. For example, the scoring function of Com- plEx (Trouillon al. 2016) embedding is.
Φ r,t) RRe((h @ rr r)))
(1)
3

---

Published as a conference paper at ICLR 2023
(a) Operator Tree
(b) Query Graph
1
T3
The operator tree representation (a) and query graph representation (b) of an examplar complex query Ren & Leskovec (2020). The logical formula of this query given by r1 (1 (1) A (22 x) A (y., 2). For shorthand, this query is denoted as INP. The symbols about relations and terms are consistent in the query graph representation. In the operator tree representation, are represented by anchor node operators 61 and 62. Relation 111 and r3 are represented by projection node P1 and Ps. Relation r2 is jointly represented by projection node Pa and negation node Pn- The fact that connected to all other nodes represented by intersection operator i.
Figure 1:
and C2
where X denotes the element wise complex number multiplication and (r, y) is the complex inner product. Re extracts the real part of a complex number. Then, the truth value of which can be computed by
(h, r, r,,) = (( r,t)):
(2)
where is the sigmoid function. This truth value function is used in Arakelyan et al. (2021) with logic I-norms. In the context of knowledge graph representation learning, the entity embeddings h. t usually related specific entity symbols in look-up table. In this work, we assume the emhedding vector related to not only specific entities but also variables.
4 EFO-1 QUERIES AND QUERY GRAPHS
Without loss of generality, we consider the logical formulas under the disjunctive normal form. Then, define the Existential First Order queries with single free variable IEFO-1).
Definition 1. Given a knowledge graph KG, an EFO-1 query Q is formulated as the first-order formula in the following disjunctive normal form,
Q Ii, Im) = iz....., 3mm Ja1 A 41 A Gim, V.... V...
[ap1 A ape A ^ A apr, (3)
where y is the only free variable and F,, S < m are m existential variables. aij, ki p. j S up are atomic formulas with constants and variables y, æ1...... Em. aij can be either negated or not.
To answer the EFO-1 queries, one is expected identify the answer set A[Q,AG)] A[Q is the set of entities such that E A XCG if and only if Q(y = a, I fi..... Fm) = True.
Moreover, since Q is given in the disjunctive normal form, let consider
Qy,, F1, xm) = CQ1 I1, Rm) V ... v (I, Fmn,
(4)
where CQ; 3r 3.. a,1 A a2 ... Oin; is conjunctive query. It is easy to that A[Q, Xgg] = -ー_ ACC, KGG. Therefore, solving A(Q, KGG is equivalent to solving the answer sets for all conjunctive queries.
4.1 QUERY GRAPH FOR CONJUNCTIVE QUERIES
For each conjunctive query, the constant entities and variables are closely related by the atomic formulas. To emphasize the dependencies between entities and variables, we propose use the query graph where the terms are nodes connected by the atomic formulas. Each node in the query graph is either constant symbol or a free or existential variable. Each edge in the query graph represents atomic formula containing both relation and negation information.
Figure D shows our query graph representation and the operator tree representation (Wang et al., bb for typical query type defined in Ren & Leskoved (2020). We see that the query graph is more concise than the operator tree. First, we can see that the nodes and edges have different meanings in operator trees and query graphs. In the operator trees representation, each node is an operator denoting a set operation, whose output can be fed into other set operators. When using the complex query answering models with the operator tree, the information flows from leaf to root,
4

---

Published as a conference paper at ICLR 2023
which is unidirectional. However, for the query graph, the messages passed bi-directionally through each edge as we will show in Section In Figure I the central node x receives messages from all neighbor nodes.
4.2 EXPRESSIVENESS OF DEFINITION
Our definition is theoretically broader than all existing discussions. The definition in (Wang al, 2021b), though widely adapted and discussed in the existing literature, has implicit assumptions because they are proposed to predict the answers by neural operators. It is assumed that (1) the Skolemization process can always convert the query into tree of set operators, and (2) all leaves of the operator tree are entities rather than variables. counterexample that can be expressed by Definition but cannot be represented by operator trees is shown in Appendix
4.3 LIMITATION OF OPTIMIZATION BASED METHODS FOR NEGATED QUERIES
Our definition accepts the atomic formulas with negation operation. Therefore, It can be natural extension of the definitions in CQD (Arakelyan et al. (022].. Moreover, we extended CQD
negation queries with the continuous truth value with fuzzy logical negator (see Appendix B
The extended method is named CQD(E), and the results are compared in Table [] We could see that the performance CQD(E) much less effective on negation queries. We conjecture that the landscape of the objective function, i.e., the continuous truth values of the complex formula with negation, can be non-convex. So the optimization problem is inherently harder. The non-convexity objective function is discussed in Appendix B.1
ONE-HOP INFERENCE ON ATOMIC FORMULAS
As shown in F each edge in query graph is an atomic formula containing the information of neighboring entitics, relation, and logical negation, which are all crucial for predicting the answers. We propose to encode such entity, relation, and logical negation information by one-hop inference that maximizes the continuous truth value of the (negated) atomic formula. Let be the logical mes- sage encoding function of four input parameters, including neighboring entity embedding, relation embedding, direction information (l2t or t2h), and logical negation information (0 for no negation and for with negation). The goal of this section is properly define p.
Moreover, inference on one-hop atomic formula is much easier compared to that on the entire com- plex EFO-1 query graph, discussed in Section 4.3 We also provide the closed-form expression of for the knowledge graph embedding we used in this paper.
5.1 ONE--OP INFERENCE IN NON-NEGATED ATOMIC FORMULAS
The first situation is infer the head embedding h given the tail embedding t and relation embed- ding r on a non-negan non-negated atomic formula. We formulate the inference task in the form of continuous truth value maximization:
h p(t, r, 12,,2 0) arg max (1x r, t),
(5)
RED
where 'D is the search domain for the embedding. Similarly, the tail embedding & can be infered given head embedding h and relation embedding r, that is,
p(h, r, h2t, 0) arg max (h, r, 2)). MED
(6)
5.2 ONE- ONE-HOP INFERENCE IN NEGATED ATOMIC FORMULAS
To extend the definition for non-nege negated atomic formulas to negated formulas, one only need to compute the continuous truth value of negated atomic formula by the fuzzy logic negator (Hájek
5

---

Published as a conference paper at ICLR 2023
(a) Logical Message Passing with One Hop Inference (Query Graph View)
(b) oogical Message Passing Networks
(Node Embedding View)
ple 02
p(x, V...y., r2,,2,,,0,00 0)
p c2.,
MLP
20
pbx, 12,,2,, 1)
ply,Ta, Coy,T,,h2t, h2t, 0)
pl R2t, 1)
Aggregate Logical Messages
Update with Equation (9)
Figure 2:
An illustration of the two-stage procedures of logical message passing neural networks: (a) passing the logical messages across the graph; (b) updating the node embedding with the aggregated information with an MLP network.
2013). that is, (h, = related to the following inference problems
a (h, r. t). Then the estimation head and tail embeddings is
h = p(t,r, r, 12h, 1) = arg max (2 r, t) = arg max [1 (b(,,, r, [)] #ED
(7)
=ED
p(h, r, h2t, 1) arg max (h, .. arg max [1 (h, r, x)]]
(8)
RED
DgD
This optimization-basee approach is similar to CQD discussed in Section 4.3 but it is more reliable since atomic formulas are what we used to train the knowledge graph representation. Specifically, the objectives Eq. (5) and Eq. 6 are eventually the likelihood of positive samples and those in Eq. 47) and Eq. ( are the likelihood of negative samples. These objectives are widely used to learn the representations with negative sampling.
Closed-form message encoding function with pretrained KG representation. We have already defined p with optimization problems. Moreover, the closed-form expression of p can be (approx- imately) derived in many cases given two facts about the knowledge graph representations: (1) the scoring function of knowledge graph representation is usually as simple as the inner product dis- tance. More details about constructing closed-form for these two types of scoring functions are discussed in Appendix D.I] (2) the sigmoid function outside the scoring function & makes the final truth value zero identify the closed-form approximation of p for ComplEx (Trouillon et al.] (016) and other five different KG representations in Appendix ([and]) D which allows fast computation logical messages used in Section 6
only if the output of the scoring function is sufficiently small or large. We
6 LOGICAL MESSAGE PASSING NEURAL NETWORKS
In this section, we propose Logical Message Passing Neural Network (LMPNN) to bridge the one-hop inference proposed in Section 5 and complex query answering defined Section 4 As variation of the message-passiinn
neural network (Gilmer al. 2017 Xu et al. 2018). LMPNN has two stages: (1) each node passes a message to all its neighbors; (2) each node aggregates the received messages and updates its latent embedding. Figure 2 illustrates how those two stages work.
Then the final layer embedding for the free variable node can be used to predict the answer entities.
6.1 LOGICAL MESSAGE PASSING OVER THE QUERY GRAPII
We the message encoding function p compute the messages passed from node node. Fig- ure demonstrates the logical message passing with blue arrows. Each node receives the message from all its neighboring nodes.
6.2 NODE EMBEDDINGS IN QUERY GRAPH AND UPDATING SCHEME
Let n be node and z be the embedding of n. at the /-th layer. We discuss how to compute the ( from the input layer 0 to latent layers 1 0. When (0) falls into of three situations.

---

Published as a conference paper at ICLR 2023
(I) For entity node e, 2 is looked up from the pretrained knowledge graph representation. (2) For an existential variable node 2i, we assign an learnable embedding z Vr. (3) For a free variable node y, we assign another learnable embedding zω Byy. We set that all existential variables 2; share one Uz. for simplicity.
(0))
At the /-th layer, 2 can be computed by updating the aggregated information from the (1 - 1) layer. Specifically, let (n)) be the neighbor set of node n the query graph. For each neighbor node E (n)), one can obtain its embedding 2 (1-1) E DD the relation Tv-x E R, the direction De-t= {h2t, t2h), and the negation indicator Neg {0, 1}. Then, the embedding z!=² , is computed by an MLP network after the summation of the aggregated information, that is,
MLP())
11-1) E
Σ (EV(n)
(L-1) (0( Fomnn Du- Nego.m)
where c is hyperparameter. To feed the complex vector of ComplEx Trouillon et al. 2016) into the MLP network, the real and imaginary vectors one complex embedding are concatenated and regarded as one feature vector. The formulation in Eq. (9) is similar to the Graph Isomorphic Net- works etu al. 2018) except that the logical messages passed are encoded by from the pretrained KG representation. Trainable v2 and By are unrelated any specific entity.
6.3 LEARNING LMPNN FOR COMPLEX QUERY ANSWERING
To train the neural network, we apply the Noisy Contrastive Estimation (NCE) loss for ranking tasks proposed in (Ma & Collins 2018). Let {(a; q))}== {(),,)));- be the positive data samples, where a; E A(a, K. Our optimization involves K uniformly sampled noisy answers from the entity set. The NCE objective is:
1
exp [cos(a;; x(4))/T]
LNCE
log
(10)
exp (o0s(a;;(()))) Σx= exp [cos(Zt, x44))/TT]
where a; is the embedding of positive answer a; and 25: is the embedding of the noisy entity sam- ples. 2(1)) indicates the embedding of the free variable qi at the final layer of LMPNN. T is a hyperparameter. This objective is optimized by stochastic gradient descent.
6.4 ANSWERING COMPLEX QUERIES WITH LMPNN
We discuss two ways to retrieve answers for general DNF queries in Definition T (a) A two-step approach the previous works (Ren et al.) 2020; Ren & Leskovee, 2020). where the free variable emhedding for each sub conjunctive query are estimated, the answer entities are then ranked by the minimal distance (or maximal similarity) against free variable embeddings from multiple sub conjunctive queries. (2) We transform all disjunctions the formula to conjunctions, then one query graph is sufficient for solving the transformed query. The answer set of a transformed query is a strict subset of the originanl answer. For simplicity, we use the second way to solve disjunctive queries in this paper, though may lead to sub-optimal performance. Then, we discuss how to answer conjunctive queries with LMPNN.
Conjunetive query graph of arbitrary size. We apply LMPNN to the query graph of given conjunctive query Q. A sufficient condition to produce a correct answer is that the free variable node has received messages from all the entity nodes after the forward passing through LMPNN layers. Let the largest distance between entity nodes and the free variable node be L. Then, apply the LMPNN layers times to ensure all messages from entity nodes are successfully received by the free variable node. The prediction of answer embedding =(Q) is given by the free variable
embedding at the final layer, i.c., xQQ) = = (I.). We propose to use the cosine similarity between x()) and the pretrained entity embeddings to rank the entities and then retrieve answers.
Since L is not determined, we assume all L layers share the same MLP layer. Hence, the only trainable parameter in LMPNN is one MLP network and two embeddings for existential and free variables. Our experiments on different query types show that the single MLP network has strong generalizability LMPNN of different depths.
7

---

Published as a conference paper at ICLR 2023
Table 1: MRR results of different CQA models on three KGs. Ap represents the average score of EPFO queries and AN represents the average score of queries with negation. The boldface indicates the best results for each KG.
KG
Model
2P
3P
21
31
IP
20
21N
3IN
INP
PIN
PNI
Ap
An
BetaF.
65.1
25.7
24.7
55.8
66.5
43.9
40.1
25.3
14.3
14.7
11.5
6.5
12.4
41.6
11.8
CosE
73.3
3388
29.2
64.4
73.7
50.9
35.7
55.7
31.4
17.9
18.7
12.5
9.8
15.1
49.8
14.8
FB15K
Q2P
82.6
30,8
25.5
65.1
74.7
49,5
34.9
32.1
26.2
21.9
20.8
12.5
8,9
17.1
46.8
16.4
(Uling pentriined KG reprosettation)
CQD(F)
89.4
27.6
15.1
63.0
65.5
46.0
35.2
42.9
23.2
0.2
0.2
4.0
0.1
18.4
45,3
4.6
IMPNN
85.0
29.4
16.4
Betali
39.0
10.9
28.8
42.5
22.4
12.6
12.4
5.1
7.9
3.6
20,9
5.4
ConEi
41.5
32.6
25.5
14.0
10.8
5.4
4.0
FBISK 237
Q2P
39.1
11.4
10.1
32.3
47.3
24.0
14.3
8.7
9.1
4.4
9.7
7.5
4.6
3.8
21.9
6.0
(Using pestriined representation)
CQD(F)
46.7
10.3
6.5
23.1
29.8
22.1
16.3
14.2
8.9
0.2
0.2
2.1
0.1
6.1
19.8
1.7
LMPNN
45,9
13.1
10.3
34,8
48.9
22.7
17.6
13.5
10.3
8.7
12.9
7.7
4.6
5.2
24.1
7.8
Betal:
$3.0
13.0
11.4
37.6
47.5
24.1
14.3
12.2
8.5
5.1
7.8
10.0
3.1
3.5
24.6
5.9
ConE
53.1
16.1
13.9
10.0
50.8
26.3
17.5
15.3
11.3
5.7
8.1
10.8
3.5
27.2
6.4
NELL
56.5
35.8
22.6
10.4
5.1
10.2
3.3
(Using peetrained KG seprrscntatioon))
CQDIE)
60.5
36.5
43.0
22.5
13.7
0.1
0.0
28.4
1.9
LMPNN
60.5
22.1
17.5
40.1
50.3
28.4
24.9
17.2
15.7
8.5
10.8
12.2
3,9
4.8
30.7
8.0
7 EXPERIMENTS
In this section, we compare LMPNN with existing neural CQA methods and justify the important features of LMPNN with ablation studies. Our results show that LMPNN very strong method for answering complex queries.
7.1 EXPERIMENTAL SETTINGS
Baselines. We consider the neural complex query answering models for EFO- queries in recent three years, including BetaE (Ren & Leskovec, 2020), ConE (Zhang et al. (021). and Q2P (Bai) jet al. 2022). The baseline results are obtained by training models with the code released by the authors under the suggested hyperparameters. Neural-symbolic ensemble models are implemented with the negation. Moreover, we also implement and report CQD (Arakelyan et al. (021) with the
same pretrained knowledge graph representation. We also compare more neural CQA models in Appendix E
Datasets. We consider the widely used training and evaluation dataset in (Ren & Leskovee 2020 allows us to compare our results with existing methods directly. We compare the results on FB15k (Bordes et al. 2013), FB15k-237 (Toutanova et al. 2015). and NELL (Carlson et al. 2010).
The evaluation metric follows the previous works (Ren & Leskoved 2020). For each query instance, we first rank all entities except those observed as easy answers based on their cosine similarity with the free variable embedding estimated by LMPNN. The rankings of hard answers are used compute MRR for the given query instance. Then, we average the metrics from all query instances. In this paper, MRR is reported and compared.
Evaluations.
LMPNN Setting. We use the ComplEx (Trouillon et al. 2016) checkpoints released by Arakelyan et al. (202T) in LMPNN to make a fair comparison to CQD (Arakelyan et al. 2021). More results about LMPNN with other six kinds of pretrained KG representations are also presented in the Ap- pendix D The rank of ComplEx is 1.000, and the epoch for the checkpoint is 100. For IMPNN, we use AdamW to train the MLP network. The learning rate is le-4, and the weight decay is le-4. The batch size is 1,024, and the negative sample size is 128, selected from {32, 128, 512). The MLP network has one hidden layer whose dimension is 192 for NELL and FB F51, and 4,096 for FB15k-237. T in the training objective is chosen as 0.05 for FB 15k-237 and FB 15k and 0.1 for NELL. e in Eq 9 is chosen to be 0.1. Reported results are averaged from 3 random experimental trials. All experiments of LMPNN are conducted on single V100 GPU (16GB).
7.2 MAJOR RESULTS
T the MRR results of LMPNN and neural CQA basclines on answering EFO-1 queries over three KGs. is found that LMPNN reaches the best performance average for both EPFO and
8

---

Published as a conference paper at ICLR 2023
Table MRR results different hyperparameter settings compared to the best combination.
Model
IF
2P
3P
21
31
w
2U
UP
21N
JUN
INP
PIN
PNI
Ap
Ax
KGB
7.8
6.3
2.8
5.6
2.3
1.7
9.7
12.6
(7.1
14.0
7.3
3.5
2.7
22.3
0.5
43.9
11.9
9.7
20.5
42.3
18.2
14.8
13.8
9.5
7.3
10.3
7.0
3.8
5.4
21.6
6.7
45.5
34.1
43.5
11.6
13.9
11.7
5.6
2.9
3.9
20.0
L 1
45.3
12.6
10.1
33.1
46.4
20.4
16.3
13.7
10.3
5.0
10.9
7.5
4.3
5.2
23.1
1++ 2
45.6
13.0
10.1
32.9
45.8
21.3
17.7
13.4
10.0
7.9
10.9
7.7
4.2
5.2
23.3
7.2
3
10.1
32.4
17.4
13.3
T= 0.01
43.9
12.1
9.7
31,9
46.5
18.3
15.2
13.5
10.2
6.9
11.2
7.2
4.6
4.3
22.4
688
23.7
17.1
1.3
4.4
5.4
BIST CHORE:
10.3
34,8
17.6
4.6
5.2
negation queries. Our negation queries indicate that the embedding estimation formulation with negated atomic formula proposed in Section produces meaningful features.
Interestingly, LMPNN performs much better than the CQD on both EPFO and negation queries with the same pretrained knowledge graph representation. Our results show that the LMPNN is stronger than CQD in more complex queries, especially those with logical negation. Notably, approach does not require any optimization in the inference time as in Arakelyan et al. (202T). It confirms again that LMPNN successfully leverages the representation power of knowledge graph representation simply by training an MLP.
7.3 ABLATION STUDY
In the ablation study, conduct extensive experiments to justify the effects of four key factors of LMPNN, including (1) the logical message passing by one-hop inference; (2) the hyperparameter e at each LMPNN layer; (3) the depth of LMPNN; (4) the hyperparameter T at the noisy contrastive learning loss. All experiments of the ablation study are conducted on queries at FB15K-237.
To justify the effect of nop inference, compare baseline with logical messages computed by a linear transformation of the concatenation of the entity embedding, the relation embedding, a binary indicator for h2t and f2h, and binary indicator for negation. For example, for ComplEx embedding in 1.000-dimensional complex vector space, there are 2,000 parameters for entity embed- ding and 2,000 for relation embedding. The concatenation produces a feature of 4,002 dimensions. Then we use a linear transformation to transform this feature to 2000 dimensions so that the logical message can be used Eq. (9) This baseline is denoted KGE CAT. To justify the effect of the depth of LMPNN, we alter the depth of LMPNN based on its original depth L into L 1, L + 1, L+ 2, and L + 3. The value L is computed from the maximal distances between the free variable node and constant entity nodes in the query graph. Even in the I, case, we keep the depth of LMPNN at least to ensure the logical message passed between nodes.
Table 2 shows the results of the ablation study, where the setting reported in Table is indicated by BEST CHOICE. We note that BEST CИOОCE uses one-hop inference on atomic formulas, L 0.1, and T = 0.05 for FB15k-237. We find that KGE CAT performs poorly even though contains the pretrained KG information. which indicates that one-hop inference is essential to answer complex queries. Meanwhile, L 11 performs worse than BEST CHOICE since the information is not fully passed to the free variable node. And the worse performances of T. + 1, T.+22 2, and T, cases indicate that our definition for L. is reasonable. Moreover, and T are also important to the best performance. Overall, one-hop inference on atomic formula is the most critical factor in the learning and inference process of LMPNN.
LMPNN layers,
8 CONCLUSION
In this paper, we present LMPNN to answer complex queries, especially EFO-1 queries, over knowl- edge graphs. LMPNN achieves a strong performance by training one MLP network to aggregate the logical messages passed over the query graph. In the ablation study, we identify that the one-hop inference on atomic formulas based on pretrained knowledge graph is critical to answering com- plex queries. Our research effectively bridges the gap between EFO-1 query answering tasks and the long-standing achievements of knowledge graph representation. In future work, method can be combined with stronger knowledge graph representation techniques, as well as with neural- soubol-yymbolic ensembles.

---

Published as a conference paper at ICLR 2023
9 ACKONWLEDGEMENT
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 (16211520 and 16205322) from RGC of Hong Kong, the MHKIFS (MHP/001/19) from ITC of Hong Kong and the National Key R&D Program of China (2019YFE0198200) with special thanks to HKMAAC and CUSBLT, and the Jiangsu Province Science and Technology Collaboration Fund (BZ2021065). We also thank the support from NVIDIA Al Technology Center (NVAITC) and the UGC Research Match- ing Grants (RMGS20EG01DD, RMGS20CRII, RMGS20CR12, RMGS20EG19, RMGS20EG21, RMGS23CROS, RMGS23EG08).
REFERENCES
Alfonso Amayuelas, Shuai Zhang, Xi Susie Rao, and Ce Zhang. Neural methods for logical reason- ing over knowledge graphs. In International Conference on Learning Representations, 2022.
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. International Conference on Learning Representations, 2021.
Jiaxin Bai, Zihao Wang, Hongming Zhang, and Yangqiu Song. Query2particles: Knowledge graph reasoning with particle embeddings. Findings of the Association for Computational Linguistics: NAACL 2022, 2022.
Kurt D. Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250, 2008.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information pro- cessing systems, 26, 2013.
Zongsheng Cao, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. Geometry interaction knowledge graph embeddings. In Proceedings of the AAAI Conference on Arlificial Intelligence, 2022.
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka Jr., and Tom M. Mitchell. Toward an architecture for never-ending language learning. In Proceedings of the AAAI conference on artificial intelligence. AAAI Press, 2010.
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low- dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 6901-6914, 2020.
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.
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 Cohen, Fan Yang, and Kathryn Rivard Mazaitis. Tensorlog: A probabilistic database im-
plemented using deep-learning infrastructure. Journal of Artificial Intelligence Research, 67: 285-325, 2020.
Daniel Daza and Michael Cochez. arXiv:2002.02406, 2020.
Message passing query embedding. arXiv preprint
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
10

---

Published as a conference paper at ICLR 2023
Takuma Ebisu and Ryutaro Ichise. ceedings of the AAAI conference on artificial intelligence, 2018.
Toruse: Knowledge graph embedding lie group. In Pro-
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Petr Hájek. Metamathematics of fuzzy logic, volume 4. Springer Science & Business Media, 2013.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, 33(2):494-51, 2021.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pp. 2863-2872. PMLR, 2018.
Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang. Qi Ju, Haotang Deng, and Ping Wang. K-bert: Enabling language representation with knowledge graph. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 2901-2908, 2020.
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. 1120-1130, 2022.
Zhuang Ma and Michael Collins. Noise contrastive estimation and negative sampling for condi- tional models: Consistency and statistical efficiency. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3698-3707, 2018.
David Marker. Model theory: an introduction, volume 217. Springer Science & Business Media, 2006.
Maximilian Nickel, Volker Tresp. and Hans-Peter Kriegel. three-way model for collective learning on multi-relational data. In International Conference on Machine Learning, 2011.
Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. Language models as knowledge bases? In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-ICCNLP), pp. 2463-2473, 2019.
H Ren, W Hu, and Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference Learning Representations, 2020.
Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 13:19716-1977777 1977226, 2020.
Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Michihiro Yasunaga, Haitian Sun, Dale Schuur- mans. Jure Leskovec, and Denny Zhou. Lego: Latent exccution- guiiood reasoning for multi-hop question answering on knowledge graphs. In International Conference on Machine Learning, pp. 8959-8970. PMLR, 2021.
Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Denny Zhou, Jure Leskovec, and Dale Schu- urmans. Smore: Knowledge graph completion and multi-hop reasoning in massive knowledge graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1472-1482, 2022.
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations, 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne den Berg. Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.

---

Published as a conference paper at ICLR 2023
Fabian M Suchanek, Gjergii Kasneci, and Gerhard Weikum. Yago: core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pp. 697-706, 2007.
Haitian Sun, Andrew Amold, Tania Bedrax Weiss, Fernando Pereira, and William W Cohen. Faith- ful embeddings for knowledge base queries. volume 33, pp. 22505-22516, 2020.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference Learning Representations, 2018.
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 conference on empirical methods in natural language processing, pp. 1499-1509, 2015.
Théo Trouillon. Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In International conference on machine learning, pp. 2071-2088 PMLR, 2016.
Hongwei Wang, Hongyu Ren, and Jure Leskovec. Relational message passing for knowledge graph completion. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1697-1707, 2021a.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In Proceedings of the 16th international conference on World Wide Web, pp. 2022-2032, 2019.
Zihao Wang, Hang Yin, and Yangqiu Song. Benchmarking the combinatorial generalizability of complex query answering on knowledge graphs. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021b.
Ruobing Xie, Zhiyuan Liu, Jia Jia, Huanbo Luan, and Maosong Sun. Representation learning of knowledge graphs with entity descriptions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016a.
Ruobing Xie, Zhiyuan Liu, Maosong Sun, et al. Representation learning of knowledge graphs with hierarchical types. In Proceedings of the Twenty-Fiff Fifth International Joint Conference on Artificial Intelligence, volume 2016, pp. 2965-2971, 2016b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Zezhong Xu, Wen Zhang, Peng Ye, Hui Chen, and Hua zeng Chen. Neural-symbolic entangled framework for complex query answering. In Advances in Neural Information Processing Systems, 2022.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. International Conference on Learning Representations, 2014.
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. Advances in neural information processing systems, 32, 2019.
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. Variational rea- soning for question answering with knowledge graph. In Proceedings of the AAAI conference artificial intelligence, 2018
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-19185; 2021.
Zhaocheng Zhu, Zuobai Zhang, Lauis-Pascal Xhonneux, and Jian Tang. Neural bellman-fort ford net- works: general graph neural network framework for link prediction. Advances Neural Infor- mation Processing Systems, 34:29476-29490, 2021.
Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. Neural symral-ymmbolic models for logical queries knowledge graphs. In International Conference Machine Learning, 2022.
12

---

Published as a conference paper at ICLR 2023
A A COUNTEREXAMPLE FOR THE EXPRESIVENESS OF OPERATOR TREE REPRESENTATION
Example 1. Given citation network with authors, papers, and conferences, one query wants to find ICLR authors with at least one collaborator. It can expressed in the format Definition
((1,, a2 Po,P1.P2 P2) By A InCon((pI,ICLB
A IsAuthor(a1: P2) A IsAuthor(a2,p9) -(a1 02)-
We see that we take d as the answer node. 42 and are leaves but not anchor entities. In this way, this query cannot be represented by the operator tree anchor nodes. However, this query be represented in the query graph, see Figure 3
Pt
InConf
IsAuthor
ICLR
IsAuthor
Pa
IsAuthor
a2
Figure 3: The query graph for the query in Example !
Then we discuss how to answer this query with LMPNN. It is easy to see that LMPNN can be applied to the query graph Figure once the & is considered as the combination predicate eq (equality) and negation
To include eg, we only need to define the logical messages p(aj, eq, 1) and p(a2, eq. 1). According to the Proposition 2 in Appendix D.I these two problems boil down to defining p(a. eq, 0) f(a, eq). By the semanties of "equality", equal terms shares the equal embedding. Therefore, the entity embedding which is equal
Then, p(a, eq, 0) f(a eq) a and p(a1, eq, 1) -a1, p(a2, eq, 1) -02. In this way, LMPNN is the first actionable approach to address the queries in Example 1
given embedding a is just f(a, eq)
B
A NATURAL EXTENSION OF COMPLEX QUERY DECOMPOSITION (CQD) TO ANSWER NEGATION QUERIES
In this paper, we compare the optimization-based approach CQD (Arakelyan et al.) 2021 by ex- tending existing CQD with fuzzy logic negator. The extended version is denoted as CQD(E). For example, consider the logical formula INP query in the Figure I we could estimate the continuous truth value the given logical formula rı (z c1) A -T2(C2, x) A ra(y, x) as follows
VVCQDEE (x, y INNP) th, (ax e1 T
vrr, (c2, x)] T Ttby (y,
(11)
where Φ. are the continuous value of relations imizes the continuous truth value (VCQD(E) (ær, y INP) to obtain the "best" variable embeddings a and y as Arakelyan et al. 2021).
and I's and T is t-norm. Then CQD(E) max-
B. NON-CONVEX LANDSCAPE OF NEGATED COMPLEX QUERIES
this part, we show that the negator in fuzzy logic introduces non-convexity. Let x be an optimiz- able variable in the 1D interval / and (a:) and dh (2)) be two continuous truth value of two atomic
13

---

Published as a conference paper at ICLR 2023
formula d1 and dg. respectively. They convex functions over I. Consider the conjunctive query a1 A 02. The continuous truth value
[xx + T[ 62(2)).
(12)
Consider example with convex Φ (a:) and (z))). Let T is the product t-norm, and Φ (z) 1 x² and 62 (2) = - (I - 0.3)² for æ E [0, 1]. Then (xx turns to be non-convex as shown in Figure
C CLOSED-FORM LOGICAL MESSAGE BY COMPLEX
In this section, we derive the closed-form logical message encoding function for ComplEx embed- ding (Trouillon et al. 2016). The scoring function of ComplEx is
Φ(h, r, t) Re( @ r, t)).
(13)
We expand the complex embeddings to real vectors h = h, + ih; r T. ir. t = t, + it, Then the scoring function is
@hh, t) = Re( (1 3 E,)
(14)
= (r, @ h, - r; h b,) + (r, 8 h. h,, 4i)
(15)
(r, @ +r, @ ti, hp) + (r, 8 tr h.). Since -7; = T; under the complex conjugate, then,
(16)
o(h, r. (r, @ t, F, @ t4, hr) + (r, @ t, +r, t, h4)
(17)
Re(( h)).
(18)
Then, we optimize the continuous truth value ComplEx given in Eq. to derive the closed-form estimation of Eq. (5). We note that the embedding used in ComplEx is not strictly restricted in domain set 'D. Instead, the N3 regularization (Lacroix et al. 2018) is applied to the embedding a soft constraint. Therefore, in derivation of the close form solution, also employ N3 regularization rather than hard constraint. Our first result is the following proposition.
Proposition 1. For ComplEx embedding, the logical message encoding function has the following closed form with respect to the complex embedding r and t,
F 8 t
ptt, r, t2h, 0) = /3 8 E]
(19)
Proof. We expand the optimization problem follows, ptt,r, t2h, 0) = arg max [Re( @ t, x)) \||=1|
(20)
#EC*
(rr 8 -r 2,) + (rr 2 t, r. 4,, - ->(Varr, xr)) (xi, xx,)
arg max REC
(21)
0.08
0.06
0.04
0.02
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Figure 4: The landscape of continuous truth value becomes non-convex after negation.
14

---

Published as a conference paper at ICLR 2023
Notice that Tr @ t, T; @ t and Ty @ t; + @ tr are the real and imaginary part of f t. Let s = [r, @ t, F2 & t, Tr @ t + F. @ ty_ be the real vector concatenated by the real and imageinary part of Also, let ø [, be the real vector concatenated by the real and imageinary part of æ. Then the Eq. 21 is equivalent to the following optimization problem in the real space:
max (8, 2 DE 2d
x|
(22)
We note that J is convex function over E. To optimize ă,, we optimize the unit direction e and length n of æt with rewriting ž 17v. When 7j fixed the second term also fixed. easy to see that the v² = s/||a|/2 maximizes the first term. Then we find the optimal 1y by minizing the following objective for 1) >
| Any
(23)
By letting dJ dy
||s||2 32n²² derive the optimal vi"
|**|| 3X
Then, we have
a" --"""""
(24)
/3A1|0112
Then, we identify the optimal real and imaginary part of xt from H", and thus recover the optimal x².
Similarly, we derive the optimal closed- form expression of in all other cases:
p(h, het,, 0)
(25)
/3X h -F 8 t
ptt,r, 1) =
(26)
/3 t||
-r & h
ohhr,h22
(27)
v / s h
We note that the value of À not determined, On the one hand, it can be of course a hyperparameter to discuss. In LMPNN application, we just let 3λ|1 || = 1 and then all denominators in the closed- form expression are 1.
D CLOSED-FORM LOGICAL MESSAGES FOR KG REPRESENTATIONS
We demonstrate two general ways to construct closed-form logical messages function p for LMPNN in the Appendix D.I Then, we show six examples to illustrate how our approach constructs the closed form p for varous KG representations in the Appendix D.2
Specifically, our constructions apply to two types of KG representations characterized by their scor- ing functions. The first type of KG representations uses puner-product-bused scoring functions while the second type of KG representations uses distance-bass scoring functions. Moreover, we pro- vide six examples of KG representations, including RESCAL (Nickel 2011), TransE (Bordes) et al. 2013), DistMult (Yang et al. 20114), ComplEx (Trouillon et al. 2016). ConvE (Dettmers et al.
fcnrtinffunctions
2018 and RotatE (Sun et al. 2018).
D.1 Two CONSTRUCTIONS
As discussed in Section 5 the closed-form logical message encoding function is the result of the closed-fome solution of four one-hop inference problems (estimating the head tail entity embed- ding with or without logical negation, see Eq. 85. This leads to four construction tasks. The major result of Appendix D.I is Proposition 2 It shows that, with constructions of two types of scoring
15

---

Published as a conference paper at ICLR 2023
functions, closed-form solutions for four one-hop inference problems actually dependent. Once one of four one-hop inference problems are approximately solved in the closed form, the other three one-hop inference problems are also solved upproximately in the closed form.
Simplification with reciprocal relations. We simplify the four construction tasks into two tasks by introducing reciprocal relations. For each relation r E R. the reciprocal relation is r-1 E R-1 but in the reversed direction. By introducing reciprocal relations r- and training their embeddings r-1 the one-hop inference in the tail-to-head direction can be rewritten in the head-to-tail direction. Specifically, we have
pt,, r, 12h, 0) = p(t, r ,,2,,, 0): ptt,r, n.tr,f21 f2h, 1) = p(t,r=1,h21 1).
(28)
(29)
Introducing reciprocal relations is shown to improve the performances of the link prediction tasks (Ruffinelli et al. 2020). We assume that the reciprocal relation embedding can be obtained, irrespective of being separately trained or analytically derived from the original relation embedding, such as ComplEx discussed in Appendix(C] Then, it suffices to construct the closed-form solution for p(h, r, h2t, 0) and p(h, r, h2t, 1). and the rest two types of logical messages are naturally defined with reciprocal relation embeddings.
Then we construct the closed-form p(h, r. h2t, 0) and p(h, r. h2tt 1) for two types of KG embed- dings, characterized by their scoring functions. We emphasize that the derivations below are only approximate estimations keep the closed-form expression as simple as possible. However, em- pirical results show that these simple and approximate closed-form solutions can already be used in LMPNN.
Type I: inner-product-bee based scoring function. The inner- peeeer-poouut-bbbccee scoring function for a triple of embeddings (h, r, t) is (f,, r), t). where f is binary function of the entity and relation embeddings and (.-)) is the inner product. The inner-product (-.-) can be defined in real or complex vector spaces. This scoring function is used in RESCAL (Nickel al. 2011) DistMult (Yang al.
2014), ComplEx (Trouillon et al. 2016). ConvE (Dettmers et al. 2018). etc.
When optimizing the embeddings. i regularizations (q 2, 3) are usually applied (Ruffinelli al. 2020 Then we consider the following optimization problem:
p(h, h2t, 0) arg max ( (1,(h, x)) A|| 2
(30)
a
where hyperparameter À > 0 is regularization coefficient, a is the sigmoid function.
We note that J1 is just the Lagrangian of the following maximization problem, and the X is the Langrangian multiplier
max o r(,
(31)
where æ is restricted inside a a ball. Then we could conclude that
arg o ((f(h, r), x)) = arg mf r), = 84 f(h,r) |<<|5<6
(32)
||
[[(h,r))l
By altering the hyperparameter 8 = [l, TI). we could derive simple result arg max or (h, A||==| N f(hrr).
(33)
x
Therefore, we define
r, 1) := r).
(34)
Similarly, for the p(h, nrrr,h2 h2tt 1), we have
p(h, r, h2t, 1) arg max [1 - σ ( ((f(h, r), x))] -A 1|221
(35)
m
arg m ((-f(h, r), x)) >||=||/
(36)
arg max max x))
(37)
16

---

Published as a conference paper at ICLR 2023
We conclude the closed-foo form solution
p(h, h2, 0) :- -f(h, r).
(38)
Type 2: distance-based scoring function. Another type of scoring functions for a triple of embed- dings (h, r. t) is y - If. r) t|l where f follows the definition above and y is a margin. This scoring function is used in TransE (Bordes et al., 2013). RotatE (Sun et al. 2018), etc. Similarly, the ||=:11 regularizations can also be considered (Ruffinelli et al. 2020).
p(h, r, h22 0) can be computed by p(h, r, h2t,, 0) arg max (r (h. ==1) \| x
(39)
With similar tricks, we transform the "soft" regularization into the "hard" constraint.
arg max a (y (h, - æ=)) >||> arg max (y - (l, r) xi1],
(40)
where d is another hyperparameter. We set 8 > [l, ll2,
then the optimal solution is f(h,
which summarizes
p(h, r, h2,, 0) == fh, r).
(41)
For the negated head-to-tail direction, the one-hop inference problem is
arg max [1 o (7 f - x+1)
(42)
||>1|<<
arg max (l, xe|| - s(,
(43)
||
For simplicity, we choose
(h,, r, h21, 1) == -f(hrr)
(44)
Our constructions for two types of KG representations share a unified closed-form logical message once the function f(h, r) is given. In the following part f is named as "forward" estimation function since it estimate the tail embeddings based on head and relation embedding forward direction. Therefore, we summarize the four types of logical messages used in LMPNN in the following propo- sition:
Proposition 2. For KG representation of either Type and Type 2, we could define four closed- form logical encoding functions with (1) relation embedding r and the corresponding reciprocal relation embedding r and (2) the forward estimation function f as follows:
p(h, r, h2t, 0) = f(h, r),
(45)
p(h,r r, h2t, 1) -h(hrr) r); p(t, r, 12h, 0) s(t,r ) p(t, r, 12h, 1) -tttr r
(46)
(47)
(48)
D.2 SIX KG REPRESENTATION EXAMPLES
Now is ready to apply the Proposition six KG representations. For each KG representation, it is important to state its scoring function for triple (h, r, t) and the relation parameterization. We assume the reciprocal relation embeddings are already trained.
Table summarzzzs the information for RESCAL Nickel et al. 2011) TransE (Bordes et al. 2013).
DistMult (Yang et al.] 2014), ComplEx (Truillon et al.) 2016). ConvE (Dettmers al. 2018), 3), and
RotatE Sun et al. 20188. We list the relation parameter the essential one-hop inference function =f f(, r), and the scoring function for each KG representation.
p(h, r, 222t 0) =
The scoring function of ComplEx (Trouillon et al. 2016 is not the exact inner-product in the com- plex vector space, but it can be reduced to the inner product in the real vector space and has already been discussed in Appendix C We see that the Proposition 2 and Table 3 covers the results in Ap- pendix C by letting the reciprocal embedding of r be the complex conjugate of the original embedding r.
17

---

Published as a conference paper at ICLR 2023
Table Closed-form forward estimation function f for six KG representations. Closed-form logical
message encoding function can be easily constructed with the closed-fore
KG Embedding
parameters
f(h, r)
Scoring function
RESCAL (Nickel al
2011
W
W.h r r
(f(,, 1)
TransE [Bordes
2013
2- (I) t
DistMult Yang ct al
2014
r
r
rf(h.r),t)
ComplEx (Trouiloon et (0116)
r & RcLU(vec(ReLU((e: w))
Re(f(h,r), (h,,r),t) (l,(h,
ConvE Dettmers 2018
W
RotatE Sun 2018
isin
(cos + isin 0) @
Table 4: Properties of six backbone KG representations on FB15-237. The data released
by Ruffinelli et al. (2020) on https: / com /una wttuuaaaapppli ppil/ke The dimension of each KG representation is listed in the bracket. We note that the dimensions for the complex vector em- beddings indicates the trainable parameters. For example, each ComplEx embedding of 256D is complex vector in 128 with 256 trainable parameters.
KG Repr.
MRR
@its@1
Hits@3
Hits @ 10
Config file
Checkpoint
RESCAL (128D)
0.356
0.263
0.393
0.541
[download link
downlood link
TransE (128D)
0.313
0.221
0.347
0.497
[download link
download link
DistMult (256D)
0.343
0.250
0.378
0,531
download link
download lank
ComplEx (256D)
0.348
0,253
0.384
0,536
ddwnloodd link
download link
ConvE (256D)
0.339
0.248
0,369
0,521
download link
download link]
RotatE (256D)
0.333
0.240
0.368
0.522
[download link]
download link]
D.3 PERFORMANCES OF LMPNN WITH DIFFERENT BACKBONE KG REPRESENTATIONS
The performances of LMPNN with six backbone KG representations presented in Table 5 The LMPNN is trained in the suggested setting the Section 7.3 The pretrain checkpoints of six backbone KG representations performances of each KG representation listed in Table
obtained from Ruffnneli et al. (2020). The information of the
It could be found that, LMPNN achieves descent performances with simple KG backbones of relatively low dimensions (128I) and 256D). ConvE (256D) (Dettmers et al.) 2018), DistMult (256D) (Yang al., 2014), and ComplEx (256D) Trouillon al. (2016) outperform BetaE (800D) on both EPFO and negation queries. All KG representation except TransE (I28D) (Bordes et al., 2013) could outperform BetaE (800D) (Ren & Leskovee 2020) on negation queries. We note that adjust the hyperparameters, i.e., embedding dimensions, to obtain more powerful KG representa- tions could improve the results. However, this beyond the scope of this paper.
E NEURAL CQA BENCHMARK
In this section, we show that LMPNN (with ComplEx 2000D pretrained by (Arakelyan et al. 2021) the new state-of-the-an method among all neural CQA models. We include the following neural CQA baselines that can address the EFO-I queries. Other models that cannot answer EFO-1 queries
Table Comparison of LMPNN with different pretrained backbone KG representations on FB15k- 237 queries.
Model
IP
2P
3P
21
31
PL
IP
2U
UP
21N
JIN
INP
PIN
PN1
Ap
Ax
Trans:: (1280)
30.9
9.2
8.4
23.5
36.2
8.2
13.0
10.1
5.4
3.4
6.9
5.8
3.0
2.2
16.8
(1280))(
43.6
11.9
9.9
33.7
48.0
9.8
16.2
12.1
9.9
42
10.3
7.0
3.5
2.5
21.7
5.5
Comfi (2568)
10.5
13.0
9x8
(256D)
15.0
3.7
3.2
DiaMall (25eD)
43.6
11.2
9.5
32.2
46.3
18.1
15.1
13.0
9.3
6.1
10.5
66
4.1
4.2
22.0
6.3
ComplEs (256D)
44.4
11.7
9.3
32.4
46.4
18.1
15.7
13.0
9.4
600
10.7
68
4.1
4.0
22.3
18

---

Published as conference paper at ICLR 2023
Table 6: Benchmark comparison with neural CQA models on FB1 1B15k-237 queries.
Model
31N
PIN
Ap
Ax
10.9
22.4
12.6
5.1
3.4
20.9
25.5
54
22,4
MLP-Mix
43.4
12.6
10.4
33.6
47.0
149
25.7
14.2
10.2
6.6
10.7
8.1
4.7
4.4
23.6
6.9
Q2P
59.1
11.4
10.1
32.3
47.7
24.0
14.3
8.7
9.1
4,4
9.7
7.5
4.6
388
21,9
6.8
10.3
22.1
16.3
8.9
022
2.1
6.1
19.8
1.7
13.1
87
Table 7: Benchmark comparison with neural CQA models on FB15k queries.
Model
2P
3P
21
P1
IP
2U
UP
21N
31N
INP
PIN
PNT
Ap
BETAR
65.1
25.7
24.7
55.8
66.5
43.9
28.1
40.1
15.2
14.3
14.7
11.5
6.5
12.4
41.7
11.9
CooF
33.8
50.9
17.9
9.8
49.8
32.1
27.1
33.7
11.2
15.2
Q2P
82.6
308
25.5
65.1
74.7
49.5
34.9
32.1
26.2
21.9
20.8
12.5
8.9
17.1
46.8
16.2
COD
99.4
27.6
15.1
63.0
65.5
46.0
35.2
42.9
23.2
0.2
0.2
4,0
0.1
18.4
45.3
4.6
LMPNN
not compared (Ren et al. 2020) Choudhary et al. 2021
Liu al. 2022). We tried reproduce
the results reported, and we note that different model applies to different knowledge graphs.
BetaE RRen & Leskovee 2020): Results are reproduced for FB 15k-377, FB 15K, and NELL.
ConE (Zhang et al., 2021): ): Results are reproduced for FB15k-231 FBI5K and NELL.
MLP-Mix (Amayuelas
al. 2022): Results are reproduced for FB15k-237, FB15k, and NELL.
Q2P (Bai et al., ) Results are reproduced for 18155-2337 FB 15k, and NELL.
FuzzQE (Chen et al., 2022): Results on FB15k are missing. Results on FB15k-237 are not repro- ducible with the given code and suggested hyperparameters. Results on NELL are partially reproduced, so we report the results in the paper and reproduced by us.
CQD (Arakelyan et al.) 2021): Results reproduced on FB15k-237, FB 15K,, and NELL.
The results of FB 5372 FB and NELL are shown Table 6 Table 7 and Table respec-
tively. We can see that LMPNN achieves the best performance among all neural complex query answering models.
F COMPARE TO SYMBOLIC INTEGRATION METHODS
Contextualized and symbolic information are shown to be effective to improve the neural models for both knowledge graph representation and complex query answering. For knowledge graph repre- sentation, neighboring information (Schlichtkrull et al.) 2018) Wang et al.
2019
2021a
Zhu et al.]
2021] aggregated by graph neural networks KG, external information (Xie al. 20 6a by annotations, or even information from language models (Petroni et al. 2019 Liu et al. 2020) are also leveraged make the knowledge graph representation
informative and effective. For
complex query answering, neural models are enhanced with symbolic resoning (Zhu et al. 2022 Xu 2022) that heavily search over the original symbolic space (Zhu al.) (022) or ap- proximations (Cohen et al. 2020 Xu et al., 2022). Unlike neural CQA models whose operations are always in the embedding space of fixed size, the size of the intermediate states for symbolic reasoning grows with the number of the entity sets, such the fuzzy sets used in (Zhu et al. 2022 Xu et al. 2022), and the beam-searte variation of CQD (Arakelyan et al. 2021).
We refer two methods with symbolic integration. We cannot reproduce the results since the codes for those two methods have not been released. However, since symbolic integration can also be applied to improve the LMPNN, we also list their results show the potential.
GNN-QE Zhu et al. (002)): This requires V100 GPU (32G), which is 8 times larger than the resources required by LMPNN. The official implementation has not been released.
ENeSy (Xu et al. 2022): The official implementation has not been released.
Table 9 shows that LMPNN is also compatible
with the symbolic integrated models EPFO queries with only 1% trainable parameters at NELL and 10% trainable parameters at FB15k-237. For FB15k-233 there still gaps between the neural CQA models and the models with symbolic
19

---

Published as a conference paper at ICLR 2023
Table 8: Benchmark comparison with neural CQA models NELL queries.
Ax
BETAE
13.0
11.4
14.3
3.1
3.5
246
17.5
MLR-Mix
55.6
16.3
14.9
38.5
49.5
17.1
23.7
14.5
11.8
5.1
8.D
10.0
36
3.6
26.8
6.1
Q2P
56.3
15.2
12.5
35.8
48.7
22.6
16.1
11.1
10.4
5.1
7.4
10.2
333
3,4
25.4
5.9
FuzQQE
14.4
37.3
7.3
FuzzQE (reposted)
15.7
39.8
21.8
29.3
CQD
00.8
18.3
13.2
36.5
43.0
30.0
22.5
17.6
13.7
0.1
0.1
4.0
0.0
5.2
28.4
1.9
IMPNN
60.6
22.1
17.5
40.1
50.3
28.4
34.9
17.2
15.7
8.5
10.8
12.2
39
4.8
30.7
8.0
Table Comparison between LMPNN and symbolic integration methods. The number brackets
indicate the order of trainable parameters.
Model
2P
3P
21
P1
IP
2X1
UP
21N
3IN
INP
PIN
PNT
Ax
IRB1SK-257 237)
LMPNN (10
13.1
22.7
(10")
42.8
14.7
118
38.3
54.1
31.1
18.9
16.2
13.4
10.0
16.8
9.3
7.2
7.8
26.8
10.2
ENeSy
27.6
LMPNN (107)
60.6
22.1
17.5
40.1
50.3
28.4
24.9
17.2
15.7
8.5
10.8
12.2
3.9
4.8
30.7
8.0
(E(D
18.9
20,8
ENeSy (10")
59.0
18.0
14.0
39.6
49.8
29.8
24.8
16.4
13.1
11.3
8.5
11.6
8.6
8.8
29.4
9.8
These results suggest that neural models can be potentially improved with symbolic integration. The additional cost the larger computational cost.
integrations.
We noticed that the task of answering logical queries are investigated over larger knowledge graphs (Ren al. 2022). When considering larger knowledge graphs, neural CQA methods (dis- cussed in the Appendix and symbolic integrated methods (discussed in this part) have different scalabilities. For neural CQA models, the intermediate embeddings are of fixed dimensions, while the sizes of intermediate fuzzy sets used in the symbolic integration methods grow linearly with the size of the knowledge graph. Such difference makes neural-symbolic methods more resource demanding and they may suffer from the scalabilities issues.
The differences between NELL and FB 15k-237 can be explained by the quality of the ground knowl- edge graphs. However, integrating the symbolic method into neural CQA models and investigating fundamental impact of ground KGs are beyond the scope of this paper. Our work connects KG representation and neural CQA, which could also be combined with context and symbolic infor- mation. These extensions are left for future work and are expected to bring additional improvements.
20


Reviews:
[{"review_id": "cC4uLRzBG-p", "reviewer": "Reviewer_NhRN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a Logical Message Passing Neural Network (LMPNN), which relies on pre-trained knowledge graph embeddings and MLP-based local one-hop inference to perform the Complex Query Answering (i.e., EFO-1) task. Compared to the prior work CQD [1], which formalizes the KG reasoning as an optimization problem, this paper proposes to use the closed-form solution of ComplEX to approximate the single-hop inference and use an MLP-based multi-layer GNN to perform the multi-hop reasoning.\n\n[1]: Arakelyan, Erik, Daniel Daza, Pasquale Minervini, and Michael Cochez. \"Complex Query Answering with Neural Link Predictors.\" In International Conference on Learning Representations. 2020.", "summary_of_the_review": "The proposed LMPNN is 1) parameter-efficient, 2) inference-efficient (compared to optimization-based methods like CQD), and 3) achieves competitive or better performance on three EFO-1 datasets. My main concern is about the fair comparison with optimization-based methods with negations. Therefore, I can only recommend a weak accept for the paper.", "strength_and_weaknesses": "Strength:\n\n1. LMPNN is quite parameter-efficient, where only MLP and the embeddings of existential variable and free variable are learned.\n\n2. Due to the novel design of closed-form approximation of single-hop ComplEx, LMPNN is inference-efficient (in a GNN manner) compared to optimization-based methods like CQD [1].\n\n3. LMPNN achieves competitive or better performance on FB15k, FB15k-237, and NELL datasets.\n\n4. Compared to previous work CQD, LMPNN can additionally model the negation operation.\n\n\nWeaknesses:\n\n1. My main concern is on the comparison with the optimization-based method (i.e., CQD). The author claims that \"Moreover, it is unclear whether CQD can be applied to complex queries with negation operators\". Could I interpret it as the CQD is evaluated without the negation operations for INP, PIN, PNI, etc settings? Would it be possible to just use Eq. 7&8 in the paper to get an optimization-based baseline? Since one of the contributions in the paper is a GNN-like inference, I believe a fair comparison with optimization-based methods is necessary.\n\n2. The method is motivated by how to better perform one-hop queries, however, the experimental results show that LMPNN is usually outperformed by CQD in the 1P setting. Since in 1P, the one-hop ComplEx closed-form approximation should lead to the same solution as CQD, could the author explain the reasons?\n\n3. I feel the claim of bridging the gap between EFO-1 query answering and \"the long-standing achievements of KGR\" is a little over-claimed, given that previous work like CQD already uses the exactly same pre-trained KGE model (ComplEx).\n\nTypos:\n\nPage 5, \" In Figure 1, the central node x receives messages from all neighbor nodes, suo.\" what does \"suo\" mean?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HgoTL7vTEkf", "reviewer": "Reviewer_zhhh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose to represent first-order logical queries as query graphs and then design a novel message passing-based framework LMPNN on the graphs to answer given queries. This is a successful attempt to combine the power of pretrained knowledge graph embeddings and message passing to perform logical reasoning. The proposed LMPNN is quite simple (a virtue) but experiments demonstrate its superior performance.", "summary_of_the_review": "This paper proposes a novel and interesting model for logical reasoning. The proposed model is simple and shows strong performance on standard benchmarks. The submission will be more solid if analyses and experiments for more KGE models can be provided.", "strength_and_weaknesses": "## Strength \n1. This paper manages to answer complex EFO-1 queries by exploiting the potential of pretrained knowledge graph embeddings, showing that pretrained embeddings also contain abundant semantic information for logical negation.    \n2. The proposed LMPNN is simple but effective, attaining new SOTA results on benchmark datasets.    \n3. The authors conduct extensive ablation studies to evaluate the influence of different hyper-parameters.    \n4. This paper is clearly written and easy to follow.\n\n## Weakness\n1. The proposed framework is dependent on the underlying knowledge graph embeddings. The authors may want to provide more results using other KGE models (e.g., DistMult, TransE, RotatE, etc).   \n2. To perform efficient logical message passing, it seems that a closed-form message encoding function is necessary. If the underlying KGE is TransE or ConvE, then how to implement PMPNN?    \n3. The authors define a class of more expressive logical queries in Definition 1 and show that it can represent more queries compared with operator trees. However, there is no such kind of query in the current benchmark datasets.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GhZugcudRRg", "reviewer": "Reviewer_5THt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper focuses on query answering over knowledge graphs. The idea is to use standard link prediction knowledge graph embeddings to model each triplet or atomic formula, create a message and spread it out to do a message passing over the query graph. Experiments on standard benchmark shows the proposed method achieves better or comparable results than prior state-of-the-art methods.", "summary_of_the_review": "Please find the details above.", "strength_and_weaknesses": "The paper proposes a simple and effective method for query answering over knowledge graphs. It seems a combination of the ideas of CQD and MPQE. The authors perform extensive experiments and ablation studies to evaluate the proposed method. However, they did not seem to include the results of other recent baselines. Please find some more questions below.\n- It misses some words in the first paragraph on page 4. “is able to produce a continuous truth value…”\n- What does “suo” mean at the end of Sec 4.1?\n- In Eq.5, what is the search domain for the embedding? \n- How is the logical message passing neural network different from a regular message passing NN? The update function is almost exactly the same.\n- The paper does not say how to handle the union operator. But I assume the way is to do a form of aggregation at the end. I suggest the authors add one paragraph about this.\n- The paper mentioned one form of query that cannot be handled by the other methods? Does the proposed method handle such queries? How would you handle an atomic formula $\\neg(a_1=a_2)$?\n- How does the model perform on larger benchmarks in [1]?\n- The baselines are not fully considered, there are GNNQE, kgTransformer and some other recently proposed query reasoning methods that are not compared in the main result.\n\n[1] SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster