Query2Triple: Unified Query Encoding for Answering Diverse Complex Queries over Knowledge Graphs
Authors: Yao Xu
Shizhu He
Cunguang Wang
Li Cai
Kang Liu
Jun Zhao
Venue: EMNLP 2023 Findings (2023)
Keywords: Knowledge Graph
Complex Query Answering
CQA
TL;DR: We propose a novel method called Query to Triple (Q2T) to answer any complex query by transforming it to a unified triple form, which can be solved by pretrained Link Predictors, and achieve SOTA performance.

Abstract: Complex Query Answering (CQA) is a challenge task of Knowledge Graph (KG). Due to the incompleteness of KGs, query embedding (QE) methods have been proposed to encode queries and entities into the same embedding space, and treat logical operators as neural set operators to obtain answers.
However, these methods train KG embeddings and neural set operators concurrently on both simple (one-hop) and complex (multi-hop and logical) queries, which causes performance degradation on simple queries and low training efficiency.
In this paper, we propose Query to Triple (Q2T), a novel approach that decouples the training for simple and complex queries.
Q2T divides the training into two stages:
(1) Pre-training the neural link predictor on simple queries to predict tail entities based on the head entity and relation.
(2) Training the query encoder on complex queries to encode diverse complex queries into a unified triple form that can be efficiently solved by the pretrained link predictor. 
Our proposed Q2T is not only efficient to train, but also modular, thus easily adaptable to various neural link predictors that have been studied well.
Extensive experiments demonstrate that, even without explicit modeling for neural set operators, Q2T still achieves state-of-the-art performance on diverse complex queries over three public benchmarks.

Query2Triple: Unified Query Encoding for Answering Diverse Complex Queries over Knowledge Graphs
Yao Xu Shizhu Hel Cunguang Wang', Li Cai', Kang Liu Jun Zhao
The Laboratory of Cognition and Decision Intelligence for Complex Systems, Institute of Automation, Chinese Academy of Sciences, Beijing, China
2 School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing, China Meituan, Beijing, China
4 Shanghai Artificial Intelligence Laboratory, Shanghai, China
(yao.xu, shizhu kliu, jzhao @nlpr.ia.ccco,
(wangeunguang, caili03) @ @eeituan.cccm
Abstract
=
V4. swin seimmer((urniigguuuurd Vi)
Logical query
Affell(AAI, Vi) graduate(Vi, Vi)
Complex Query Answering (CQA) is a chal- lenge task of Knowledge Graph (KG). Due to the incompleteness of KGs, query embed- ding (QE) methods have been proposed to en- code queries and entities into the same embed- ding space, and treat logical operators as neu- ral set operators to obtain answers. However, these methods train KG embeddings and neu- ral set operators concurrently on both simple (one-hop) and complex (multi-hop and logical) queries, which causes performance degrada- tion on simple queries and low training effi- ciency. In this paper, we propose Query to Triple (Q2T), a novel approach that decouples the training for simple and complex queries. Q2T divides the training into two stages: (1) Pre-training neural link predictor on simple queries to predict tail entities based on the head entity and relation.
Where did the people who won the Turing Award Al graduate from?
Interpretation
Feld-1
graduate
Query graph
winner
Vi
V/
Turning Award
Figure 1: An example, along with its corresponding interpretation and query graph, in CQA.
logic (FOL) operators such as existential quantifi- cation (3), conjunction (A), disjunction (V), and negation (-) to be performed on entities, relations and triples, shown in Figure 1. As KGs usu- ally suffer from incompleteness (West et al., 2014), traditional query methods such SPARQL (Prud- hommeaux et al., 2013) cannot handle CQA well on real-world KGs such as Freebase (Bollacker et al., 2008) and NELL (Carlson et al., 2010).
(2) Training a query en- coder on complex queries to encode diverse complex queries into a unified triple form that can be efficiently solved by the pretrained neu- ral link predictor. Our proposed Q2T's is not only efficient train, but also modular, thus easily adaptable to various neural link predictors that have been studied well. Extensive experiments demonstrate that, without explicit model- ing for neural set operators, Q2T still achieves state-of the-art performance on diverse com- plex queries over three public benchmarks.
Recently, an alternative method called Query Embedding (QE) (Hamilton et al., 2018: Ren et al., 2020) has been proposed to complete the missing edges and answer the complex query simultane- ously (Wang et al., 2023b). The idea of these meth- ods is encode queries and entities into the same embedding space, and treats logical operators neural set operators (e.g. relation projection as set projection, queries conjunction as sets intersec- tion, query negation and set complement) to answer queries. QE methods embed a query by iteratively performing neural set operators according to the topological order of nodes in the query graph, and then obtain answers based on the similarity scores between the query embedding and all entity embed- dings. This process is shown in Figure (B). Despite QE-based methods achieving good per- formance on CQA, they still exhibit the following drawbacks: (1) Cannot perform well on both sim-
1 Introduction
Knowledge Graphs (KGs) organize world knowl- edge as inter-linked triples which describe entities and their relationships in symbolic form (Ji et al., 2020). Complex query answering (CQA), knowl- edge reasoning task over KGs, has been proposed in recent years (Wang et al., 2021). Compared with simple link prediction, which involves predicting a missing entity in a factual triple (Rossi et al., 2021), I),
CQA is more challenging as it requires first-order
*Corresponding Author

---

ple and complex queries simultaneously (simple queries refer to one-hop queries, complex queries encompass multi-hop and logical queries). One potential reason from the model perspective is that, QE-based models model the projection operator with complex neural networks to perform well on complex queries, however, these complex neural networks are incapable of effectively managing in- herent relational properties (Wang et al., 2023b), such as symmetry, asymmetry, inversion, composi- tion, which are sufficiently studied in KG comple- tion tasks and addressed by Knowledge Graph Em- bedding (KGE) (Wang et al., 2017), so KGE mod- els can easily outperform QE--based methods on simple queries. Another potential reason from the training perspective is that, the training for simple queries and complex queries coupled in these methods, as demonstrated in Figure 2 (A). There- fore, the entity and relation embeddings inevitably incorporate neural set operators information that is irrelevant for answering simple queries, leading to a decrease in performance. (2) Low training efficiency and not modular. From the model per- spective, as the KGE is coupled with the neural set operators in QE-based methods, shown in Figure 2 (A), these methods usually train KGE and neural set operators from scratch in each round of training, which inefficient. Furthermore, due to this coupling, these methods cannot directly ex- ploit other high- nigh-performance KGE models such as Complii (Trouillon et al., 2016). (3) Suffer from error cascading. These methods have to calculate all intermediate node representations step-by-step. demonstrated in Figure 3 (B), so errors will be cascaded along the path (Guu et al., 2015), which affects the quality of answers.
(A) QE based methods
Neural Sei Operators
Training ammple and compaiox quariies
Reasening simple and plo quaries
(8) QZT
Staget
KGE
Training simpll queries los
Frevrained Link Prodkctrr
Ressening simple cuarles
Stege2
Complex Query
Training
Reasoning
Figure 2: The different training strategies used in QE- based methods and Q2T. KGE denotes entity and rela- tion embeddinngs. (A) QF-based methods train KGE and neural set operators on both simple and complex queries. (B) Q2T train KGE and Query Encoder on simple and complex queries respectively.
which aims to fully reuse the pretrained model, in the second stage, Q2T utilizes a trainable encoder to transform any complex query graph g into a unified triple form (gh, Gr. f7), where Jh: Ir are representations of the whole query graph generated by the encoder, to are tail entities to be predicted. Then, we can obtain probability list of all entities by feeding these two representations and all pre- trained entity embeddings to the pretrained neural link predictor. That is, we transformer any complex query to a unified triple form which can be handled well by neural link predictors. In other words, as shown in Figure 3 (A), Q2T treats CQA as a spe- cial link prediction task where it learns how to generate appropriate inputs for the pretrained neural link predictor instead of reasoning in the embedding space step-by-step.
The advantages of Q2T are follows: (1) Good performance on both simple and complex queries, because Q2T can not only make full use of the well-studies KGE models but also decouple the the training of simple queries and complex queries from the training perspective. (2) High training efficiency and modular, because from the model perspective, Q2T decouples the KGE and the query encoder, so it only trains the encoder in each round of training (pretrained KGE is frozen) and also fully utilize various advanced KGE models. (3) Simple and accurate, as Q2T utilizes an end-to- end reasoning mode, which not only climinates the need to model complex neural set operators, but also avoids error cascading.
Aiming to handle the above drawbacks, in this paper, we propose Query to Triple (Q2T), novel approach that not only decouples the training of complex queries and simple queries from the train- ing perspective, but also decouples KGE and the query encoder from the model perspective. Q2T di-
vides the training into two stage: pre-training KGE for simple queries and training unified query en- coder for diverse complex queries, as shown in Figure 2 (B). In the first pre-training stage, we only train a KGE model as a neural link predictor on simple queries, such as DistMult (Yang al., 2015) and ComplEx (Trouillon al., 2016). Motivated by the prompt (Sun et al., 2022b; Liu et al., 2023) technology in Natural Languages Process (NLP),
We conducted experiments on widely-used benchmark such as FB15k (Bordes et al., 2013),

---

FB15K-237 (Toutanova and Chen, 2015), and NELL995 (Xiong et al., 2017). The experimental results demonstrate that, even without explicit mod- eling for neural set operators, Q2T still achieves state-of-the-art performance on diverse complex queries. The source codes and data can be found at https://gi thub. com/YaooXu//Q2T.
neural link predictor the one-hop reasoner and T-norms as logic operators to obtain the continuous truth value of an EPFO query. Then the embed- dings are optimized to maximize the continuous truth value. However, this method is time consum- ing and cannot handle negation queries well (Wang et al., 2023b). (2) LMPNN (Wang et al., 2023b), which is related to our work, also utilizes pretrained KGE conduct one-hop inferences on atomic for- mulas, the generated results are regarded as the messages passed in Graph Neural Network (GNN) (Wu et al., 2020). However, in the LMPNN, KGE and GNN are coupled, which means the KGE func- tion is invoked during every message propagation on each edge in the inference. Besides, LMPNN has to design of distinet logical message propaga- tion funetions for different types of score functions in KGE, as well as for different types of regular- ization optimization. Compared LMPNN, Q2T only requires a single invocation of the KGE score function for any type of complex query. There- fore, Q2T is better suited for leveraging KGE with higher complexity and larger parameters. Addition- ally, Q2T can be employed with any KGE without the need for additional code modifications, so it is more modular.
2 Related work
Knowledge Graph Embedding (KGE). KGE em- beds components of KG including entities and relations into continuous vector spaces, so as to predict unseen relational triples while preserving the inherent structure of the KG (Wang et al., 2017). According to the different scoring functions, KGE can be roughly categorized into two types: transla- tional distance models (Bordes et al., 2013; Wang et al., 2014) and semantic matching models (Yang et al., 2015; Trouillon et al., 2016). All these mod- els can be used in Q2T neural link predictors. Prompt-based Learning. In recent years, a new training paradigm called "pre-train, prompt, and predict" has achieved success in both NLP (Liu et al., 2023) and graphs (Sun et al., 2022a). Aim- ing effectively reuse the pretrained model, this paradigm targets reformulating the downstream task looks similar to pre-training task (Liu al., 2023). Based on the same idea, Q2T, we treat simple and complex queries as the pre-training and downstream tasks respectively. The difference is that we use trainable encoder to encode complex queries to the same triple form as simple queries. Neural complex query answering. Neural com- plex query answering can be divided into two cate- gories: with/without pretrained KGE. Query Em- bedding (QE) based models, without pretrained KGE, encode queries and entities into the same embedding space, then obtain answers by step-by- step reasoning, as shown in Figure 3 (B). In QE- based models, many methods have been proposed represent entity sets, such as geometric shapes (Ren al., 2020; Bai al., 2022), probability dis- tribution (Ren and Leskovec, 2020) and bounded histogram on uniform grids (Wang et al., 2023a). Neural networks like multi-layer perceptron and transformers (Vaswani et al., 2017) are used to model set operations. They are trained for simple and complex queries concurrently, they suffer drawbacks mentioned before.
SQE (Bai et al., 2023) is also related to our work, it uses a search- based algorithm to linearize the computational graph to a sequence of tokens and then uses a sequence encoder to compute its vector representation. Another related work is KgTrans- former (Liu et al., 2022). It also uses the Trans- former to encode queries, but it outputs the final node embedding directly. To improve transferabil- ity and generalizability, KgTrranffrrmer introduces a two-stage masked pre-training strategy, which requires more pre-training data and time. However, Q2T can outperform KgTransformer easily with much less parameters and training time.
3 Preliminary
In this section, we formally introduce knowledge graph (KG). Then, we use symbols of KG to define EFO-1 query and its corresponding Disjunctive Normal Form (DNF), Finally, we introduce neural link predictors.
3.1 Knowledge Graph and EFO-1 Queries
We represent a KG as a set of factual triples, i.e., G = (h, E V x R x V}. where h, E V denote the head and tail entity, r E R represents
Models with pretrained KGE are as follows: (1) CQD (Arakelyan et al., 2021) uses the pretrained

---

AP
Embedding
fiedd
Step 4
Simple
Li
Neural Predictor
Goodfallow
graduale
ESIEE
fleir
answers
Step 3
Paris
Edinburgh
Al
Hinton
graduasa
LeCun
Predicted
winner
Tumiing Award
Bh
g-
winner
Aho Metcalle
Compalx query
Encoder
Turning Award
Step
(A)
The end-to-end reasoning mode in Q2T
(B) The step-by-step reasoning mode in QF
The different reasoning mode for the query "Where did the person who won the Turing Award in Al graduate from?". " (A) Q2T adopts end-to-end reasoning mode: encoding the query graph to obtain two representation 9h- 9r. then the pretrained neural link predictor takes 9h- 9r inputs and output predicted tail entities, which is similar to answering simple queries. (B) QE-based methods utilize step-by-step reasoning mode: iteratively apply the neural set operators get answers. Step and Step 2 denote applying set projection from Al and Turning Award respectively. Step denotes applying set intersection the results of Step and Step 2. Finally, Step 4 denotes applying set projection to the result obtained in Step 3.
Figure 3:
the relation. We make r(h,r) = if and only if there is directed relation between h and t. Following previous work (Ren and Leskovec, 2020), we define the Existential First Order queries with a single free variable (EFO-1), and an arbi- trary EFO-1 logical formula can be converted to the Disjunctive Normal Form (DNF) as follows:
model that incorporates structural information, query encoder. Q2T utilizes the query encoder encode complex queries, producing representations that are used inputs in neural link predictors, as depicted in Figure 4.
4.1 The Pretrained Neural Link Predictor
/ [v]] = V, 3 V1 3V c1 V
Cm
(1)
As answers of complex queries generated by the pretrained neural link predictor finally, its per- formance directly affects the final performance.
where 1/2 the only free variable and Vú, < < are existential variables, each c₁ 1 < $ m
represents a conjunctive clause like & = en A Aea,, and each eij. 1 S k, indicates an atomic formula or its negation, i.e., Gij = r(a, b) or rr(a, b), where r E R, a, can be either a constant e E V or variable V.
Aiming to get neural link predictors with good performance, the training object we use contains not only terms for predicting the tail entity of a given triple, but also term for predicting the re- lation type, which has been proved to significantly improve entity ranking (Chen al., 2021). The training object is defined follows:
3.2 Neural Link Predictor
KGE is kind of neural link predictor, for simplic- ity, neural link predictors mentioned in this article refer to KGE models. Given the head entity em- bedding relation embedding r, and tail entity embedding t, KGE can compute the score Φ(h, r, t) the triple (h, r, t). where o(h, r, t) indicates the likelihood that entities and hold the relation r.
BIg DEB
Σ
log Po(()h,)) Alog (h)
(1...1)89
log Po(t)h,r) = r,t log Σ exp
(o(ho r,t')
Mee
log Po(r(h,)) = ((h,r,)) log
exp [o(h, r
4
Q2T: Transforming Query to Triple
where 0 E θ are the model parameters, including entity and relation embeddings. h, r, denote head entity, relation and tail entity, h, r, denote their corresponding embeddings under 0 is a scoring function, is hyper--paae parameter determining the contribution of the relation prediction objective.
There are main components in Q2T: (1) The Neural Link Predictor. (2) The Query Encoder. This section begins with an introduction to the pre- training of neural link predictors. Subsequently, we present QueryGraphormer, a Transformer based

---

Decadt with KGE soom Lunction
piEssI P
grourn
Encoder Lager
Mutla
vineer
A
Pretraines ned KGE
Sebrac
Origin query graph
Step
Vaskl
Step
QueryGraphormer (Encodier)
Divibee
PARKKT
(WAZKZ
Node embeddinn
intiaization
Tuminng Avaur
Node Perkie
Augmented query graph
Step
Figure 4: The framework of QZT. The steps of answering complex queries in Q2T are: (1) Transforming the origin query graph to a augmented graph without edge attributes. (2) Flattening the augmented graph to sequence, and initializing the sequence with the pretrained KGE. (3) Encoding the sequence representations with QueryGraphormer which considers the structural information of the graph. (4) Inputting the final representations of 9b, Gr. and other entity representations to the score function of the pretrained KGE to calculate the probability list of entities.
4.2 The QueryGraphormer
cial token [CLS] represent the sentence- feature, in QueryGraphormer, node: [9%] and [9+], which represent virtual head node and a virtual relation node respectively. In the view of graph, [9h] and [g>] can be regraded as two virtual nodes connected to all nodes in the query graph. We attach [an] and [g,] at the beginning of each sequence, then query graph is flattened into sequence, S [gh+ 9r, Vi,..., Un], where n is the number of nodes in the augmented graph, n,, i < is an entity node, relation node or MASK node. For each node, its imput representation bedding from the pretrained KGE if an entity node or relation node, or a trainable embedding otherwise. We denote the initial representation of S as S E Rmxxo, where m = n 2, do is the dimension of the pretrained KGE.
add two special
Transformer for CQA With the great success of Transformer (Vaswani et al., 2017) in NLP, Trans- former has also been proved to perform well for graph representation learning (Ying et al., 2021). KgTransformer (Liu et al., 2022) is the first work to apply Transformer on query graphs, which first turns relations into relation-nodes query graph into an augmented graph without edge attributes, then masks adjacency matrices (Hu et al., 2020) to self-attention. However, this limits recep- tive field cach node, which means each node can only obtain information from its neighbors.
transform the
frozen em-
Motivated by Graphormer (Ying et al., 2021), propose QueryGraphormer, which uses the di- rected distance between any two nodes as bias term in the attention mechanism, solve these drawbacks. This helps the model effectively cap- ture spatial dependencies within the augmented graph (obtained through the same transformation as KgTrrasformer).
Projection. After obtaining the initial represen- MLP to project features from
tations of $ high-dimensional to low-dimensional to reduce the parameter amount and calculation time of the QueryGraphormer, which described as follows:
The biggest difference between our proposed QueryGraphormer and KgTransformer is that out- puts of QueryGraphormer are inputted to pretrained neural link predictors to get the final predicted an- swers, while KgTransformer outputs the final pre- dicted answer embedding directly.
(3) where S E mmxdi and S E R.xxdo are the inital/projected representations of S, and dj < do-
S' = ML. (S0)
Handle negation queries. Aiming to make the input representations of negation queries different from positive queries. We apply a linear transforma- tion on node representation that represents nega- tion relation: hreg Ah; where IR xd1 h2 E d denotes the the i-th element (negation relation node) in 5
4.2.1 Input Representations Construction In this part, we introduce how to construct input sequence representations for QueryGraphormer.
Initial input representations. Similar to BERT (Devlin et al., 2019) model which introduces a spe-

---

4.2.2 Self-Attention with Distance Message
where MHA denotes Multi-Head Attention de- scribed before. FFN denotes Feed-Forward blocks, LN denotes layer normalization, W1 E R xd2 W2 E Rdoxd, and act is the activation function. In QueryGraphormer, we make dj = d2-
Directed Distance Encoding. Similar to the Spa- tial Encoding used in Graphormer (Ying et al., 2021), we employ a function Φ(v;, my) V V + R which measures the spatial relation between V; and bj in the query graph g. Unlike Graphormer which uses the distance of the shortest path to be the function, in this paper, we use the directed dis- tance of the shortest path, because the topological order is crucial in query graphs, that is, predeces- sors and successors of each node should be treated differently.
4.2.3 Training Object of QueryGraphormer
Finally, we feed the representations of and gr in the last layer, denoted as gh. E RRd into the pretrained neural link predictor to obtain predicted answers. Formally, given query graph g. the score of each tail entity is calculated as follows:
The directed distance of the shortest path is de- fined as follows:
s(4 <lgh' 'r', 9h. = MMPP (gh): gr' MLPrro (13)
(12)
olvi, U)) = dir * spd(us, 0j)
(4)
dir = sgn(layer(vy - layer(u;))
(5)
where MLPrew projects the representations from dj dimension back do dimension, 4 E Rd is the pretrained embedding of entity 1,, ø the score function of the pretrained KGE.
where spd(u;, vy) denotes the distance the short-
est path between &ú and U/. layer(n;) denotes the
layer number of vj (obtained by topological sort), sgn(2) is the sign function: sgn(x) if x 2 0. sgn(2) = 0 if x < O.
It is noteworthy that t; is from the pretrained en- tity embeddings, and they are not needed to updated in the training of QueryGraphormct which effee- tively reduces the number of parameters needed to be updated.
For each output value of o, we allocate a train- able scalar to be bias term in the self-attention. Then the attention aij between i and 0j is com- puted the following way (for simplicity, we only consider single-head self-attention here):
Our training object to maximize the log proba- bilities of correct answer t, the loss function (with- out label smoothing for simplicity) is defined as follows:
expaij
Oij ETh aik
(h; W (h, W + (((r)))
K L= --=(((t log Σ exp [s(4e g))) (14)
Oij-
Vdi
where WQ, WK C Rdixd; are Query and Key matrices, (w..),g)) is learnable scalar indexed by (1r,, 12). By doing this, each node in the query graph can not only aggregate the information of all other nodes, but also decide which nodes should pay more attention to based on distance messages.
where t and f4 are the answer entity and negative entity (random sampling), respectively.
Experiments
In this section, we conduct experiments to demon- strate the effectiveness and efficiency of Q2T and the necessity of decoupling the training for simple and complex queries.
The result of self-attention for i is obtained as follows:
12 Attn:- = Σ auy (h, 1=1
(8)
5.1 Experiment Setup
where WV E Idixdd xdi is Value matrix.
Datasets. To compare our results and previous works directly, we conduct our experiments on the widely used datasets generated by Ren and Leskovec. The logical queries in these datasets (9) are generated from FB15k (Bordes et al., 2013). FB15k-237 (Toutanova and Chen, 2015), and NELL995 (Xiong et al., 2017). More details about W2 b2 (11) these queries can be found in Appendix A.
Then we adopt the classic Transformer encoder to get the output representations of layer I, which is described as follows:
(0) = (M
+ ((-))))
() (NFF (() + (0)
(10)
FFN(2)) = act(x W1

---

Datasel
Model
1p
2p
pi
ip
2u
up
2/n
3in
inp
pin
pni
Ap
Ap
BetaE
65.1
25.7
24.7
43.9
28.1
40.1
25.4
14.3
14.7
12.4
41.6
11.8
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
ConE
73.3
33.8
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
EPFO queries (queries without negation) generated by Ren et al., we also compare these works the EPFO datasets in Appendix F. We also compare CQA models in (with pretrained KGE)
FB15k
CQD-CO
89.2
25.6
13.6
77.4
78.3
44.2
33.2
41.7
22.1
46.9
LMPNN
85.0
39.3
28.6
68.2
76.5
46.7
43.0
36,7
31.4
29.1
29.4
14.9
10.2
16.4
50.6
20.0
Q2T
89.4
44.3
33.6
72.1
79.4
55.3
47.7
65.8
38.2
19.5
21.3
16.2
10.2
16.7
58.4
16.8
Betaß
39.0
10.9
10.0
28.8
42.5
22.4
12.6
12.4
9.7
5.1
7.9
20.9
Q2P
39.1
14.3
87.0
ConE
41.8
12.8
11.0
32.6
47.3
25.5
14.0
14.5
10.8
5.4
8.6
7.8
23.4
FB15k
FuzzQR
42.2
13.3
10.2
33.0
47.3
26.2
18.9
15.6
10.8
9.7
12.6
7.8
24.2
8.5
-237
(with pretrained KGE)
CQD-CO
46.7
9.6
6.2
31.2
40.6
23.6
16.0
14,5
8.2
21.9
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
Q2T
48.4
15.6
12.4
37.8
51.9
28.6
19.4
21.8
12.8
6.1
12.4
8,4
4.5
4.1
27.6
7.1
Betal
53.0
13.0
11.4
37.6
47.5
24.1
14.3
12.2
8.6
5.1
7.8
10.0
3.1
3.5
24.6
5.9
Q2P
56.5
15.2
12.5
35.8
48.7
22.6
16.1
11.1
5.1
25.5
ConFi
53.1
17.5
15.3
11.3
5.7
FuzzQE
58.1
19.3
50.3
28.1
21.8
17.3
13.7
8.3
10.2
11.5
29.3
NELL
(with pretrained KGF)
CQD-CO
60.4
17.8
12.8
39.3
46.6
30.1
22.1
17.3
13.2
28.8
LMPNN
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
Q2T
61.1
22.1
18.0
41.1
52.3
30.3
23.4
19,5
15.3
5.8
7.5
11.3
3,7
4.3
31.5
6.5
Table 1: MRR results of different CQA models over three KGs. Ap and AN denote the average score EPFO and queries with negation (Zin//in/inp/pin//mi), respectively. The boldface indicates the best result each query type.
queries (1 htt/2/////i////ppppppppppp
Ap
An
Q2T (no structrual information)
30.2
5.6
Adjacency Matriccs Masking
30.5
6.4
Undirected Distance Encoding
31.0
6.5
our work with Appendix G.
Directed Distance Encoding
31.5
6.5
Table MRR models with different structural infor- mation encoding strategies the NELL dataset.
5.2 Comparison with Baselines
Table shows the MRR results of Q2T and base- lines on EFO-1 queries over three benchmarks. The experiment settings can be found Appendix B. find that Q2T
The evaluation metries follows the previous works (Ren and Leskovee, 2020), which aims to measure the ability of models to discover hard answers. That is, these answers cannot be found in the training KG by symbolic methods due to missing edges. Concretely, for each hard an- swer v of a query g. we rank it against non-answer entities and calculate the Mean Reciprocal Rank (MRR) evaluation metrics.
Evaluation.
From the table, achieve the state-of-the-an performance almost all positive queries over three datasets. Especially on FB 15k and FB15k-22 15k-273,, our Q2T has a signifi- cant improvement on EPFO performance, achiev- ing 15.4% and 14.9% relative improvement on Ap respectively. Furthermore, compared to the step- by-step reasoning mode, the end-to-end reasoning mode eliminate error cascading to tent, which is reflected in the better performance on multi-hop queries (2p/3p). More details about the model parameters can found Appendix C.
Baselines. We mainly compare our work with non symbolic-integrated CQA models for EFO-1 queries. The baselines can be divided into two types: (1) Without pretrained KGE, such as BetaE (Ren and Leskovec, 2020), ConE (Zhang et al., 2021), Q2P (Bai al., 2022) and FuzzQE (Chen al., 2022). (2) With pretrained KGE, such as CQD-CO (Arakelyan al., 2021), and LMPNN (Wang et al., 2023b).
This results show that, without the explicit modeling for neural set operators, our Q2T still perform well logical queries, one poten- tial explanation is as follows: Each pretrained neural link predictor can be regarded as a neu- ral knowledge base which record the structure
As some works (c.g. Kg KgTransformer (Liu et al., 2022)) do not support negation queries, they use the

---

20.0
19,59
13,98
19.5
29.34
19,77
19,68
19.5 19.38
19.0
18.67
A/ 47
47,00
46,72
46.6
46.63
46.4
Ag 6.75
6.76
6.65
6.71
6.70
6.6
6,70 6.67
6.67
6.4
6.37
21,20
Ao 31.2
31,10
3122
31.02
11.00
10,70
31.0
30.8
0.2
0.3
0.4
0.5
0.6
0.7
0.8
(A) label smoothing
(B) number layers
Figure 5: Hyperparameter analysis on NELL. Am: Ai, An, Ap denote average MRR of multi-hop queries, intersection queries, negation queries, and all positive queries. Since the performance is too low when the label smoothing is 0, they are not shown in the figure (A).
of KG, while learning to transformer complex queries into suitable inputs for the link predictor can be seen an end-to-end process of retriev- ing answers from this neural knowledge base. Compared to BetaE, Q2P and ConE, Q2T's strong performance on both simple and complex queries underscores the critical importance of sepa- rating their training processes.
can be found that models with structural informa- tion perform well consistently in CQA, indicating that structural information necessary. Besides, Distance Encoding that leverages global receptive field is better than Adjacency Matrices Masking that uses local receptive field. Besides, compared to undirected distance, directed distance can further improve performance by introducing extra topolog- ical information that help each node to treat their predecessors and successors differently.
Although Q2T cannot outperform previous mod- els on negation queries, still gets competitive per- formance. One potential explanation for this lies in the fact that the neural link predictor is exclusively pretrained on positive triples. The distribution of answer entities for positive triples tends to more concentrated, whereas queries containing negation operators result in a more dispersed answer entity distribution. For example, the "complement" oper- ator can yield numerous candidate answers, in queries like "Who is not the winner of the Tur- ing Award." Consequently, pretrained KGE models struggle to generate suitable answer embeddings for queries with dispersed answer distributions.
Label smoothing. Label smoothing crucial in Q2T, model without lahel smoothing suffer from severe overfitting, resulting bad performance on all queries. More details about label smoothing can be found in Appendix D. Figure 5 (A) shows how label smoothing influences performance, it can be observed that different types of queries pre- fer different label smoothing values, multi- hop and negation queries prefer high label smoothing value while intersection queries do the opposite, we think this difference is caused by the difference in the av- erage number answers, as shown Appendix A. More specifically, queries with more candidate answers prefer higher label smoothing value.
We also test the performance of Q2T with differ- ent pretrained KGE on the FB 15k-237 queries, and the results are shown in Appendix E.
5.3 Ablation Studies
In this section, we conduct further experiments to demonstrate the effectiveness of Directed Distance Encoding and investigate how hyperparameters af- fect the performance on each query type.
Number of layers. To justify how the number of layers affects Q2T, we test the performance of models with different number of layers differ- query types. Figure (B) demonstrates that (1) For intersection queries, model with layers can handle them well, more layers lead overfitting. (2) For multi-hop queries, more layers are needed to model long dependencies in the query graphs.
Structure Encoding. We compare our proposed Directed Distance Encoding two commonly used strategies: Undirected Distance Encoding and Ad- jacency Matrices Masking, which are deseribed in section 4.2. The results are reported in Table 2,

---

#params
A
Ac
Ap
A,
resource, we only test performance of Q2T with different KGE models on the FB15k-237 queries.
Q2T (NF)
56M
44.3
22.0
24.5
5.8
Q2T (F)
26M
48.6
25.1
27.7
7.3
8 Ethics Statement
Table 3: Impact of whether freezing KGE on perfor- mance. Q2T (NF) denotes Not Freezing KGE, while Q2T (F) denotes Freezing KGE. As, Ag denotes the av- erage MRR of simple queries and complex queries. The number of parameters of the KGE is 30M.
This paper proposes a method for complex query answering in knowledge graph reasoning, and the experiments are conducted on public available datasets. As result, there is no data privacy con- cern. Meanwhile, this paper does not involve hu- annotations, and there no related ethical concems.
5,4 Training with trainable KGE
Aiming to further prove the necessity of decou- pling the training for simple queries and complex queries, on the FB15k dataset, we conduct exper- iments on Q2T with frozen/not frozen pretrained KGE. The results are shown in Table 3, where Q2T (NF) means training KGE and encoder on simple and complex queries together, Q2T (F) means only training encoder for complex queries. Although Q2T (NF) has more trainable parameters, per- form worse than Q2T (F). Especially on simple queries, a neural link predictor trained on simple queries can already handle it well, however, a more complex model trained on more complex queries leads to worse performance. As the final results are predicted by the pretrained link predictor (KGE), the worse the performance simple queries, the worse the performance on complex queries.
Acknowledgment
This work was supported by National Key R&D Program of China (No.2022ZD01 18501) and the National Natural Science Foundation of China NN.66376270, No.U1936207, No.6197621 I). This work supported by the Strategic Prior- ity Research Program of Chinese Academy of Sci- ences (No.XDD27020100); Youth Innovation Pro- motion Association CAS.
References
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. 2021. Complex query answering with neural link predictors. In 9th International Con- ference on Learning Representations, ICLR 2021, Vir- tual Event, Austria, May 3-7, 2021. OpenReview.ned
6 Conclusion
Jiaxin Bai, Zihao Wang. Hongming Zhang, and Yangqiu Song. 2022. Query2Particles: Knowledge graph rea- soning with particle embeddings. In Findings of the Association for Computational Linguistics: NAACL 2022, pages ciation for Computational Linguistics.
this paper, we present Q2T to transform diverse complex queries into a unified triple form that can be solved by pretrained neural link predictors. Q2T not only decouples the training of complex queries and simple queries from the training perspective, but also decouples KGE and the query encoder from the model perspective. The experiments three datasets demonstrate that Q2T can achieve the state-of-the-ar performance on almost all positive queries.
Seattle, United States. Asso-
Jiaxin Bai, Tianshi Zheng, and Yangqiu Song. 2023. Sequential Query Encoding For Complex Query An- swering on Knowledge Graphs. ArXiv:2302.13114 [cs].
Ivana Balazevic, Carl Allen, and Timothy Hospedales. 2019. TuckER: Tensor factorization for knowledge graph completion. In Proceedings of the 2019 Con- ference on Empirical Methods in Natural Language Processing and the 9th International Joint Confer- ence on Natural Language Processing (EMNLP. IJCNLPP), pages 5185-5194, Hong Kong, China. As- sociation for Computational Linguistics.
7 Limitations
The limitations of our proposed Q2T are as follows: (1) Q2T cannot handle negation queries well. Us- ing more strategies to enable Q2T to answer nega- tion queries well is direction for future work. (2) We only use KGE our pretrained link predictors. the performance of Q2T highly dependent on the pretrained link predictors. Other type models (c.g. GNN based model) as pretrained link predic- tors may perform better. (3) Limited to time and
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collabo- ratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIG- MOD international conference on Management of data, pages 1247-1250.

---

Antoine Bordes, Nicolas Usumier, Alberto Gareia- Durán, Jason Weston, and Oksana Yakhnenko. 2013. Translating embedddings for modeling multi- relational data. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Pro- ceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2787-2795.
Representation, Acquisition and Applica- tions. ArXiv preprint, abs/2002.00388.
Graphs:
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. 2018. Canonical tensor decomposition for knowledge base completion. In Proceedings of the 35th International Conference on Machine Learn- ing, 1CML 2018, Stockhelmsmässun, Stockholm, Swe- den, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 2869-2878. PMLR.
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Sentle, Estevam R. Hruschka Jr., and Tom M. Mitchell. 2010. Toward architecture for never- ending language learning. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intel- ligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2023. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35.
Xuelu Chen, Ziniu Hu, and Yizhou Sun. 2022. Fuzzy logic based logical query answering on know wedge graphs. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty- Fourth Conference on Innovative Applications of Artificial Intelligence, TAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence. EAAI 2022 Virtual Event, February 22- March 1, 2022, pages 3939- 3948. AAAI Press.
Xiao Liu, Shiyu Zhao, Kai Su, Yukuo Cen, Jiezhong Qiu, Mengdi Zhang. Wei Wu, Yuxiao Dong, and Jie Tang. 2022. Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logi- cal Queries. volume abs/2208.07633.
Prudhommeaux, Steve Harris, and A SPARQL Seaborne. 2013. 1.1 query language. W3C recom- mendation. Mar, 21.
Yihong Chen, Pasquale Minervini, Sebastian Riedel, and Pontus Stenetorp. 2021. Relation prediction as an auxiliary training objective for improving multi- relational graph representations. arXiv preprint arXiv:2110.02834.
Hongyu Ren, Weihua Hu, and Jure Leskovec. 2020. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In 8th Inter- national Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
Jacob Devlin, Ming-Wei, Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume I (Long and Short Pupers), pages 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
Hongyu Ren and Jure Leskovec. 2020. Beta embed- dings for multi-hop logical reasoning in knowledge graphs. In Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural In- formation Processing Systems 2020, NewrIPS 2020, December 1-1 2020, virtual.
Andrea Rossi, Donatella Firmani, Antonio Matinata, Paolo Merialdo, and Denilson Barbosa. 2021. Knowl- edge graph embedding for link prediction: A com- parative analysis. ACM Trans. Knowl. Discov. Data, 15:14:1114:49
Kelvin Guu, John Miller, and Percy Liang. 2015. Traversing knowledge graphs in vector space. In Pro- ceedings of the 2015 Conference on Empirical Meth- ods in Natural Language Processing, pages 318-327, Lisbon, Portugal. Association for Computational Lin- guistics.
Mingehen Sun, Kaixiong Zhou, Xin He, Ying Wang. and Xin Wang. 2022a. GPPT: Graph Pre-training and Prompt Tuning to Generalize Graph Neural Net- works. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Min- ing, pages 1717-1727, Washington DC USA. ACM.
William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. 2018 Embedding log- ical queries on knowledge graphs. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Sys- lems 2018, NeurIPS 2018, December 3-8, 2018, Mon- tréal, Canada, pages 2030-2041.
Tian- Xiang Sun, Xiang- Yang Liu, Xi-Peng Qiu, and Xuan-Jing Huang. 2022b. Paradigm shift natural language processing. Machine Intelligence Research, 19(3):169-183.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020. Heterogeneous graph transformer. In WWW '20: The Web Conference 2020. Taipei, Tai- wan, April 20-24, 2020, pages 2704-2710. ACM / IW3C2.
Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Composi- tionality, pages 57-66, Beijing, China. Association for Computational Linguistics.
Shaoxiong Ji. Shirui Pan, Erik Cambria, Pekka Martti- nen, and Philip S. Yu. 2020. A Survey on Knowledge

---

Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016. Com- plex embeddings for simple link prediction. In Pro- ceedings of the 33nd International Conference on Muchine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Work- shop and Conference Proceedings, pages 2071-2080. JMLR.org.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2013. Embedding entities and relations for learning and inference in knowledge bases. In 3rd International Conference on Learning Represen- tations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. 2021. Do transformers really perform badly for graph representation? In Advances in Newral Information Processing Systems 34: Annual Confer- ence on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 28877-28888.
Ashish Vaswami, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9. 2017, Long Beach, CA, USA, pages 5998-6008.
Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji. and Feng Wu. 2021. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. In Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Process- ing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 19172-19183.
Quan Wang, Zhendong Mao, Bin Wang. and Li Guo. 2017. Knowledge Graph Embedding: A Survey of Approaches and Applications. IEEE TRANSAC- TIONS ON KNOWLEDGE AND DATA ENGINEER- ING, 29(12)220.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014. Knowledge graph embedding by trans- lating hyperplanes. In Proceedings of the Twenty- Eighth AAA! Conference on Artificial Intelligence, July 27- -31, 2014, Québec City, Québec, Canada, pages 1112-1119. AAAT Press.
Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. 2022. Neural-symbolic models for logi- cal queries knowledge graphs. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 27454 27478. PMLR.
Zihao Wang, Weizhi Fei, Hang Yin, Yangqiu Song, Ginny Y. Wong, and Simon See. 2023a. Wasserstein- Fisher-Rao Embedding: Logical Query Embed- dings with Local Comparison and Global Transport. ArXiv:2305.0400. [cs].
Zhaocheng 7hu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang. 2021. Neural menlman-ford networks: A general graph neural network frame- work for link prediction. In Advances in Neural Information Processing Systems 34: Anmual Confer- ence Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 29476-29490.
Zihao Wang, Yangqiu Song, Ginny Wong, and Si- mon See. 2023b. Logical Message Passing Net- works with One-hop Inference on Atomic Formulas. ArXiv:2301.0883 108859 [cs].
Zihao Wang, Hang Yin, and Yanggiu Song. 2021. Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs. ArXiv preprint, abs/2109.08925.
Robert West, Evgeniy Gabrilovich, Kevin Murphy, Shaohua Sun, Rahul Gupta, and Dekang Lin. 2014. Knowledge base completion via search- based ques- tion answering. In 23rd International World Wide Web Conference, WWW '14 Seoul, Republic of Korea, April 7-11, 2014, pages 515-526. ACM.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A com- prehensive survey on graph neural networks. IEEE transactions on neural networks and learning sys- tems, 24.
Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017. DeepPath: A reinforcement learning method for knowledge graph reasoning. Proceedings of the 2017 Conference on Empirical Methods in Nat- ural Language Processing, pages 564-573, Copen- hagen, Denmark. Association for Computational Lin- guistics.

---

size, 12 number of heads. We tune the hyperparam- eters of Q2T on the validation set for each dataset by grid search. We consider the batch size from (512, 1024, 2048), learning rate from { {1e-4, 2e-4, 4e-4, 5e-4), and label smoothing from [0.2, 0.4, 0.6, 0.8 Our experiments are conducted on GTX 3090 with PyTorch 1.11, and the random seed are fixed for each experiment. The best hyperparame- ters for each datasets are shown in Table 6.
Supervised Training Evaluation Query Types
O+0 O+0+ O+0+0+0
1p
2p
3p
3i
On
2in
3in
inp
pni
pin
Zero-Shot Query Types
C Model parameters and training time
Table 7 show the number of parameters for mod- els in Table 1. Although Q2T requires training KGE first and then training the query encoder, the overall training time is still shorter than that of other methods. This is due the high training effi- ciency achieved by decoupling the training process of K KEE and the query encoder.
ip
2u
up
Anchor node
Intermediate node
Target node
Figure 6: The illustration of all query types. The p, i, n, represent projection, intersection, negation, and union operations respectively.
BetaE (Ren and Leskovec, 2020), ConE (Zhang et al., 2021), Q2P (Bai et al., 2022) don't use pre- trained KGE, they train neural set operators with KG embeddings from the zero, which is very inef- ficient. Although these methods seem to have less parameters than the pretrained KGE used in Q2T, they have much longer training time (e.g. The train- ing times of BetaF and ConE are estimated to more than 20 hours under the official settings, while the training time for Q2T is less than 10 hours). Be- sides, the training for KGE on simple queries is efficient due to the simple structure of KGE, e.g., on the NELL queries, although ComplEx (Trouil- lon et al., 2016) model has I 110M parameters, its training can be done in one hour.
A
Data Details
The nine query types are shown in Figure 6. Specif- ically, there are five query types (1p/2p/3p/2i/3i) evaluated in supervised manner, five query types /t/n://///pppn/pnii evaluated in a few-shot man- ner, and four query types (2u/up/pi/ip) evaluated in a zero-shot manner. Given the query type, a sample is generated by random walking on the KG. The splitting of datasets are shown in Table 4. The av- erage number of answers of test queries are shown in Table 5.
It should be noted that the training queries and the test queries generated by random walking on Girain (containing training edges) and Grest (containing training, validation, and testing edges), respectively, which means that models need to pre- dict at least one missing edges by knowledge graph reasoning.
D Label Smoothing
Aiming to prevent models from overfitting, label smoothing uses soft one-hop labels, instead of hard ones, to introduce noise during training. The smoothed label yts is computed follows:
B Experiment settings
Vi
a a)yn K
For pretrained KGE model, we use the same set- tings as CQD (Arakelyan et al., 2021) and LMPNN (Wang et al., 2023b): ComplEx (Trouillon et al., 2016) model with rank 1000. The difference is that we use relation prediction as auxiliary training objective in the training of ComplEx, stated in section 4.1, our ComplEx model perform better on 1p queries. The MRR scores of baselines we use are reported by Wang et al..
where M is the smoothed label, yh the original label, a the parameter of label smoothing. is the number of sampling. Lastly, standard cross- entropy loss is applied to these smoothed labels.
E Performance of Q2T with different pretrained KGE
Table presents the MRR results of Q2T with dif- ferent pretrained KGE on the FB15k-237 queries
The default setting of Q2T is: 6 layer, 768 hidden

---

Training
Validation
Test
Dataset
1p/2p/3p/2i/3i
others
1p
others
1p
others
FB15k
273,710
27,371
59,097
8,000
67,016
8,000
FB 137
149,689
14,968
20,101
5,000
22,812
5,000
NELL
107,982
10,798
16,927
4,000
17,034
4,000
Table 4: Number of training, validation, and test queries generated for different query types.
Dataset
1p
2p
3p
2i
3i
ip
pi
2u
up
2in
3in
inp
pin
pni
FB15k
1.7
19.6
24.4
8.0
5.2
18.3
12.5
18.9
23.8
15.9
14.6
19.8
21.6
16.9
FB15k-237
1.7
17.3
24.3
6.9
4.5
17.7
10.4
19.6
24.3
16.3
13.4
19.5
21.7
18.2
NELL995
1.6
14.9
17.5
5.7
6.0
17.4
11.9
14.9
19.0
12.9
11.1
12.9
16.0
13.0
Table 5: Average number of answers of test queries in datasets generated by Ren and Leskovec.
Dataset
batchsize
dropout
Is
Ir
G
Comparison with symbolic-integrated model
FB15k
1024
0.1
0.4
4e-4
FB15k-237
1024
0.1
0.6
4e-4
In contrast to symbolic-integrated methods (e.g., BetaE (Ren and Leskovec, 2020), Q2P (Bai et al., 2022), CQD-CO (Arakelyan et al., 2021)), which use fixed-dimension intermediate embed- dings (c.g., 10²), symbolic-integratee methods (e.g., GNN-QE (Zhu et al., 2022)) employ inter- mediate fuzzy set sizes that scale linearly with the Knowledge Graph size (e.g., 10*). We select GNN-QE symbolic-integrated methods for comparison with our Q2T, the results are shown in Table 12. It should be noticed that, GNN-QE employs NBFNet (Zhu et al., 2021) which applies multi-layers GNN on the whole KGs for each projection op- eration. Besides, GNN-QE applies fuzzy logic operations to fuzzy sets of entities, so each node needs to obtain the probability list of all entities (a tensor with shape (IV), )). As result, GNN-QE requires much more training time and lots of GPU resources, it requires 128GB GPU memory to run batch size of 32, while Q2T only demands 12GB GPU memory to run batch size 1024. Even then this, Q2T also competitive with GNN-QE.
NELL
1024
0.1
0.6
5e-4
Table 6: The best hyperparameters of Q2T on datasets generated by Ren and Leskovec. The Is and denote label smoothing and learning rate respectively.
generated by Ren and Leskovec. CP (Lacroix et al., 2018), DistMult (Yang al., 2015) and ComplEx (Trouillon et al., 2016) are trained under the best hyperparameters settings provided by Chen et al., while Tucker (Balazevic et al., 2019) is trained un- der the best hyperparameters settings provided by Balazevic et al.. It can be observed that the perfor- mance of link predictors directly affects the final performance on complex queries. We also find that Q2T with different KGE models may be good at solving different queries.
representative of
F
Comparison with more baselinse on EPFO datasets
Table 10 shows the HIT@3 results of different CQA models on EPFO queries generated by Ren al.. KgTransformer (Liu al., 2022) utilizes two- stage pre-training The first stage aims to initialize KgTransformer with KGs' general knowledge, and the second stage refines its ability for small queries during inference. Although KgTransformer has more parameters (8 layers, 1024 hidden size) and spends more time performs worse than our Q2T. The potential reason that KgTrrnsformer perform better on pi/ip queries is that these type of queries may included in pre- training data, which are randomly sampled from KGs.
pre-trianing data, it still

---

FB15k
FB15k-237
NELL
Model
#pretrained
#trainble
#pretrained
#trainble
#pretrained KGE params
#trainble
KGE params
params
KGE params
params
params
BetaE
19M
20M
58M
ConE
28M
24M
63M
Q2P
11M
9.9M
29M
(with pretrained KGE)
CQD
35M
OM
30M
OM
128M
OM
LMPNN
35M
16M
30M
16M
128M
16M
Q2T
35M
26M
30M
26M
128M
26M
Table 7: The number of parameters for each model. CQD only use pretrained KGE to obtain answers with optimization-based method, so it doesn't have other trainable parameters.
KGE Model
1p
2p
3p
2i
3i
ip
2u
up
2in
3in
inp
pin
pni
Ap
An
TuckER
45.3
12.5
10.1
28.2
39.8
21.8
15.8
16.9
10.0
7.0
8.9
4.0
5.0
22.2
6.5
CP
46.3
14.9
12.1
37.1
51.3
28.6
17.8
17.4
12.0
6.0
11.7
8,8
4.7
3.9
26.4
7.0
DistMult
47.2
15.1
11.9
37.2
50.9
28.1
18.3
18.7
12.2
6.2
12.5
4.5
4.1
26.6
ComplEx
48.5
16.2
12.6
37.8
51.8
28.6
19.2
21.9
12.5
6.4
12.7
8.5
4.6
4,2
27.7
7.3
Table The MRR results of Q2T with different pretrained KGE on the FB15k-237 queries generated by Ren and Leskovec.
Dataset
Model
1p
2p
3p
2i
3i
ip
pi
2u
Avg
GQE
0.405
0.213
0.153
0.298
0.411
0.085
0.182
0.167
0.160
0.230
Q2B
0.467
0,240
0.186
0.324
0.453
0.108
0,205
0.239
0.193
0.268
EmQL.
0.389
0.201
0.154
0.275
0.386
0.101
0.184
0.115
0.165
0.219
FB15k-237
CQD (CO)
0.512
0.213
0.131
0.352
0.457
0.146
0.222
0.281
0.132
0.272
CQD (Baam)
0.512
0.288
0.221
0.352
0.457
0.129
0.249
0.284
0.121
0.290
Kg KgTransformer
0.459
0.312
0.276
0.398
0.528
0.189
0.286
0,263
0.214
0.325
Q2T
0.530
0.329
0.276
0.415
0.529
0.167
0.251
0.358
0.230
0.343
GQE
0.417
0.231
0.203
0.318
0.454
0.081
0.188
0.200
0.139
0.248
Q2B
0.555
0.266
0.233
0.343
0.480
0.132
0.212
0.369
0.163
0.306
EmQL
0.456
0.231
0.172
0.331
0.483
0.143
0.244
0.226
0.207
0.277
NELL
CQD CO)
0.667
0.265
0.220
0.410
0.529
0.196
0.302
0.531
0.194
0.368
CQD Beam
0.667
0.350
0.288
0.410
0.529
0.171
0.277
0.531
0.156
0.375
Kg Transfformer
0.625
0.401
0.367
0.405
0.546
0.203
0.306
0.469
0.270
0.399
Q2T
0.670
0.409
0.373
0.397
0.543
0.198
0.282
0.534
0.316
0.414
Table 10: HIT @3 results of different CQA models on EPFO queries generated by Ren et al.
Dataset
Model
Ip
2p
3p
3i
pi
ip
2u
up
2in
3in
inp
pin
pni
Ag
An
FB15k-237
GNN-QE
42.8
14.7
11.8
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
Q2T
48.4
15.6
12.4
37.8
51.9
28.6
19.4
21.8
12.8
6.1
12.4
8.4
4.5
4.1
27.6
7.1
NELL
GNN-QE
53.3
18.9
14.9
42,4
52.5
30.8
18.9
15.9
12.6
9.9
14.6
11.4
6.3
6,3
28.9
9.7
Q2T
61.1
22.1
18.0
41.1
52.3
30.3
23.4
19.5
15.3
5.8
7.5
11.3
3.7
4.3
31.5
6.5
Table 12: Comparison between Q2T and GNN-QE.


Reviews:
[{"review_id": "wUIgtx8aTb", "reviewer": "Reviewer_Tnh9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer Tnh9,\n\nThanks for your informative suggestions. Here is our feedback.\n\n> Q1: GNN-QE is trained on link-prediction (1p) queries and tuned with Complex queries with none/minor performance degradation on simpler queries occurring, which contradicts the claim in the abstract.\n\nA1: In this work, we aim to compare our work with Query Embedding (QE) based methods, such as BetaE, Q2P and so on. For these methods, the intermediate embeddings are of fixed dimensions. However, Graph Neural Network Query Executor (GNN-QE) belongs to symbolic integrated methods, For these methods, the sizes of intermediate fuzzy sets grow linearly with the size of the Knowledge Graph, which means they require significantly more GPU resources and do not scale well for large Knowledge Graphs. The claim in the abstract (line 003-013) refers to Query Embedding based methods, and only QE based methods include neural set operators (line 009).\n\nBesides, GNN-QE is not trained on link-prediction (1p) queries and tuned with Complex queries, it is trained on 10 query types concurrently (1p/2p/3p/2i/3i/2in/3in/inp/pni/pin)  without pretrained embedding models (as stated in section 2 and section 5.1 of  the GNN-QE original paper). \n\nAlthough GNN-QE utilizes more GPU resources and more training time to achieve higher performance on complex queries, simple Knowledge Graph Embedding (KGE) models (such as the ComplEx model used in CQD) can still outperform it easily on 1p queries (as shown in Table 1 of the GNN-QE original paper).\n\nIn summary, our claim in abstract refers to Query Embedding based methods, and GNN-QE,  as a symbolic integrated method, also confirms our claim.\n\n\n\n> Q2: The discrepancy that models cannot perform well on both link-prediction (1p) and more complex queries is not justified at all and should be further validated/elaborated\n\nA2: From an experimental perspective, we can find  from Table 1 that even QE based models such as BetaE, Q2P and ConE model the projection operator with complex neural networks, traditional Knowledge Graph Embedding (KGE) models, such as ComplEx model used by CQD and Q2T, can still easily outperform them on link prediction (1p) (line 071-076). \n\nFrom a theoretical perspective, there are two reasons:\n\n1. The complex neural networks employed in these studies for modeling the projection operator are incapable of effectively managing inherent relational properties, such as symmetry, asymmetry, inversion, composition, and more, which are sufficiently studied in KG completion tasks and addressed by KGE. However most QE methods don't make full use of the well-studied KGE.\n\n2. The training for simple queries and complex queries are coupled. Therefore, the entity and relation embeddings inevitably incorporate neural set operators information that is irrelevant for answering link-prediction queries (1p), leading to a decrease in performance (line 076-083).\n\nTo solve these drawbacks we use a competitive KGE model (ComplEx-N3-RP, ComplEx with N3 Regularizer and relation prediction, line 258-274) to handle link prediction, and combine it with an extra encoder to solve complex queries. \n\nThe experiment in section 5.2 (line 537-555) further validates our assumption as it proves the necessity of decoupling the training for simple queries and complex queries. Specifically,  if we do not freeze the KGE and tune the pretrained ComplEx model and the query encoder on link prediction (1p) queries and complex queries together, we get worse performance even introducing more parameters.\n\nWe will discuss this question in more detail in subsequent versions.\n\n\n\n> Q3: QE models are not the only ones suffering from error cascading. Methods such as CQD also compute intermediate candidates and are prone to error cascading.\n\nA3: Yes, CQD is prone to error cascading too, but we focus mainly on the general drawbacks of Query Embedding based methods in our paper. Due to page limitations, we only mention the two main disadvantages of CQD in the later part of the article (line 188-196), we will discuss the disadvantages of CQD in more detail in subsequent versions.\n\n\n\n> Q4: CQD does not handle negation at all. The original study does not include results with negations; thus, comparing CQD with negations is unjustified. \n>\n> Q5: The numbers of CQD in Table 1 are inconsistent with the original results.\n\nA4: As our work follows LMPNN, the baseline results in Table 1 are taken from the original paper of LMPNN. LMPNN extended CQD to negation queries with the continuous truth value with fuzzy logical negator and tested it on the dataset introduced by BetaE, while the original CQD is tested on the dataset introduced by Query2Box (doesn't contain negation queries). So the performance of CQD in Table 1 is different with the original results. \n\nIn order to clear up the misunderstanding, we will rename CQD to CQD (E)  in Table 1 in subsequent versions.\n\n> Please elaborate on why the method is \"time-consuming\"\n\nDue to page limitations, we didn't elaborate how CQD works. CQD utilizes the KG representation to calculate the continuous truth value of an EPFO logical formula with the logical t-norms. Then, the embeddings are optimized to maximize the continuous truth value. When the optimization is applied in the embedding space,  gradient-based optimisation methods (such as Adam and SGD) are used to update node embeddings multiple times until convergence or reaching the maximum number of iterations, which is time-consuming.\n\nWhen the optimization is applied in the symbolic space, it uses beam search, which requires more time for answering queries (Figure 4 of their original paper).\n\nWe will discuss more details of CQD in subsequent versions.\n\n\n\n> Q6:The current SOTA GNN-QE is completely omitted from the baselines, although it is the closest work in terms of components to this approach. \n\nA6: Firstly, LMPNN (ICLR 2023) is  closer to our work than GNN-QE (ICML 2022). Secondly, as stated in A1, in this work, we aim to compare our work with Query Embedding (QE) based methods with intermediate embeddings of fixed dimension (10^2). GNN-QE is a symbolic integrated method where intermediate fuzzy set sizes scale linearly with the Knowledge Graph size (10^4). Besides, GNN-QE employs NBFNet (Zhu et al., 2021) which applies GNN on the whole KG (training set) for each message passing iteration. So GNN-QE requires much more training time and lots of GPU resources (4 V100 GPU (32G), which is 10 times larger than the resources required by Q2T) . This means that GNN-QE suffers from the scalabilities issues. \n\nDespite this, Q2T can still outperform GNN-QE on EPFO queries over FB15k-237 and NELL, the results are as follows. \n\n|  **Dataset**  | **Model** |  **1p**   |  **2p**   |  **3p**   |  **2i**   |  **3i**   |  **pi**   |  **ip**   |  **2u**   |  **up**   |  **2in**  |  **3in**  |  **inp**  | **pin**  | **pni**  | $\\boldsymbol{A_p}$ | $\\boldsymbol{A_n}$ |\n| :-----------: | :-------- | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :------: | :------: | :----------------: | :----------------: |\n| **FB15k-237** | GNN-QE    |   42\\.8   |   14\\.7   |   11\\.8   | **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**      |\n|               | Q2T       | **48\\.4** | **15\\.6** | **12\\.4** |   37\\.8   |   51\\.9   |   28\\.6   | **19\\.4** | **21\\.8** | **12\\.8** |   6\\.1    |   12\\.4   |   8\\.4    |   4\\.5   |   4\\.1   |     **27\\.6**      |        7\\.1        |\n|   **NELL**    | GNN-QE    |   53\\.3   |   18\\.9   |   14\\.9   | **42\\.4** | **52\\.5** | **30\\.8** |   18\\.9   |   15\\.9   |   12\\.6   | **9\\.9**  | **14\\.6** | **11\\.4** | **6\\.3** | **6\\.3** |       28\\.9        |      **9\\.7**      |\n|               | Q2T       | **61\\.1** | **22\\.1** | **18\\.0** |   41\\.1   |   52\\.3   |   30\\.3   | **23\\.4** | **19\\.5** | **15\\.3** |   5\\.8    |   7\\.5    |   11\\.3   |   3\\.7   |   4\\.3   |     **31\\.5**      |        6\\.5        |\n\nRegarding the FB15k dataset, the performance of GNN-QE is exceptionally strong. We argue that this phenomenon stems from data leakage (stated in the orignal paper of FB15k-237), where a large number of test triples could be obtained by inverting triples in the training set. Consequently, GNN-QE might exploit these shortcuts while applying GNN on the whole KG (training set) to get answers.\n\nIn the later version, we will compare our Q2T and other symbolic integrated methods including GNN-QE in the appendix.\n\n\n\n> Q7: It is very peculiar and dubious to see that a method for complex query answering not only mitigates the effect of training for simple and complex query answering but also overperforms models that are particularly trained for link prediction on all the benchmarks.\n\nA7: The key idea of our work is: (1) First, train a KGE model on link prediction queries. (2) Then, train a query encoder for complex queries (the pretrained KGE is frozen) (line 098-126). \n\nFor link prediction queries, we just use the pretrained KGE model to solve them. For complex queries, we use the query encoder to transform them into a unified triple form which can be solved by the pretrained KGE model (Figure 3 (A)). \n\nThe KGE model and the query encoder of Q2T are decoupled (line 130-135). Therefore, we can make full use of the existing mature technology in the field of KGE to train our KGE model. In this work, we use ComplEx-N3-RP (ComplEx with N3 Regularizer and relation prediction, line 258-274), which is a very competitive model for link prediction, as our KGE model, so Q2T can perform well on link prediction. \n\nBesides, the test 1p queries generated by BetaE are slightly different from the standard KG test datasets, so the performance on 1p can not be compared directly with that of the standard KGE models that are tested on the standard KG test datasets.\n\n\n\n> Q8: Does the method include an interoperability component, as a portion of complex query-answering methods do? Most methods can assess error cascading through these means.\n\nA8: Q2T uses an end-to-end reasoning mode, which means Q2T doesn't need to obtain the intermediate embedding of each variable node (Figure 4 and Figure 3 (A)). So, there is no error cascading in Q2T, and that's the reason why Q2T can outperform other models on path queries (2p/3p) (line 457-461).\n\n\n\n> Q9: The contribution seems incremental compared to existing methods such as GNN-QE, CQD and BetaE.\n\nA9: Q2T is the first work to treat CQA as a special link prediction task where it learns how to generate appropriate inputs for the pretrained neural link predictor end-to-end (line 122-126), which is completely different from the existing QE-based methods (BetaE, Q2P),  symbolic integrated methods (GNN-QE) and CQD. \n\nThe results of this experiment demonstrate that Q2T, despite having fewer parameters and requiring less training time, can still outperform other baseline models. Furthermore, Q2T does not necessitate explicit modeling of neural set operators, making it a more concise model.\n\nWhat's more, Q2T further bridges the studies of KGE and CQA, as we are the first to prove that KGE models can be also used to answer complex logical queries directly without updating themselves. Specifically, each pretrained neural link predictor can be regarded as a neural knowledge base that record the structure of KG, while learning to transform complex queries into suitable inputs for the neural link predictor can be seen as an end-to-end process of retrieving answers from this neural knowledge base (line 471-477). \n\n\n\nBest regards,\n\nAuthors of Paper1769", "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": "1) The authors suggest a novel method for tackling complex query answering in knowledge graphs.\n2) The approach allows for faster inference and tackles the computationally expansive nature of query answering.\n3) The ablation w.r.t. label smoothing used in the method is solid.", "reasons_to_reject": "1) Methods such as GNN-QE also train on link-prediction (1p) queries and tune with Complex queries with none/minor performance degradation on simpler queries occurring. This directly contradicts the claim in the abstract (lines 007-013).\n\n2) (lines 068-071) The discrepancy that models cannot perform well on both link-prediction (1p) and more complex queries is not justified at all and should be further validated/elaborated.\n\n3) (lines 092-093) QE models are not the only ones suffering from error cascading. Methods such as CQD also compute intermediate candidates and are prone to error cascading.\n\n4) (lines 188-196) CQD does not handle negation at all. The original study does not include results with negations; thus, comparing CQD with negations is unjustified. Please elaborate on why the method is \"time-consuming\"?\n\n5) The numbers in Table 1 are inconsistent with the original results:\n@inproceedings{minervini2022complex,\n  title={Complex query answering with neural link predictors},\n  author={Minervini, Pasquale and Arakelyan, Erik and Daza, Daniel and Cochez, Michael}\n}\n\n6) The current SOTA GNN-QE is completely omitted from the baselines, although it is the closest work in terms of components to this approach. This baseline should be added and compared.\n\n7) It is very peculiar and dubious to see that a method for complex query answering not only mitigates the effect of training for simple and complex query answering but also overperforms models that are particularly trained for link prediction on all the benchmarks.\n\n8) Does the method include an interoperability component, as a portion of complex query-answering methods do? Most methods can assess error cascading through these means.\n\n9) The contribution seems incremental compared to existing methods such as GNN-QE, CQD and BetaE.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper present a novel method for complex query answering in Knowledge Graphs (KG). The approach is to decouple the training on simple one-hop (link-prediction) queries and complex queries into modular parts. The authors suggest the use of a complex query encoder to be used in conjunction with a pre-trained link predictior.", "excitement": 3, "reproducibility": 2, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "GNN-QE: Graph Neural Network Query Executor\n\n@inproceedings{zhu2022neural,\n  title={Neural-symbolic models for logical queries on knowledge graphs},\n  author={Zhu, Zhaocheng and Galkin, Mikhail and Zhang, Zuobai and Tang, Jian},\n  booktitle={International Conference on Machine Learning},\n  pages={27454--27478},\n  year={2022},\n  organization={PMLR}\n}"}}, {"review_id": "9sqBQPqO6K", "reviewer": "Reviewer_hmQo", "summary": "", "questions": "\n\n1. Missing baseline: FuzzQE [1] is a strong query encoding baseline without kg-embedding, it’s encouraged to add it into comparison.\n\n2. A contemporary work SQE [2] is highly related to this paper, it’s encouraged to add it to the discussion.\n", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer hmQo,\n\nThanks for your informative suggestions. Here is our feedback.\n\n\n\n> Q1: Lack of ablation study. The major proposed design (also the main difference between Q2T and KgTransformer) is the answer decoding approach. KgTransformer outputs the final node embedding directly, while Q2T outputs two vectors (head, relation) and then decodes with a link predictor. However, the paper didn’t provide an ablation study to prove the importance of this design. Is the improvement brought by the transformer backbone or the link predictor?\n\nA1: We have conducted the experiment that makes Q2T output the final node embedding directly in the early time, but the performance is extremely poor. We perceive that only if Transform-based models have more parameters and larger training data, can they fully record the structure of KGs, and this is what KgTransformer does. \n\nSpecifically, on the FB15k-237 dataset, **KgTransformer has more than 600M trainable parameters**, while Q2T has only 56M trainable parameters (30M for KGE, 26M for query encoder). Besides, KgTransformer uses two-stage pre-training (Initialization and Refinement) and then fine-tuning, which not only requires much more training time than Q2T but also needs to sample more data by random walking on KGs.\n\nBoth Q2T and KgTransformer use the transformer as backbone, but Q2T can outperform KgTransformer easily with much less parameters and training time. Therefore, we believe this improvement is brought by our decoding approach which only uses the transformer to generate embeddings for retrieving answers from KGE.\n\nIn the later version,  we will compare Q2T and KgTransformer in more detail.\n\n\n\n> Q2: As stated in the paper, the Q2T model does not outperform the previous state-of-the-art models on negative queries, despite its significant improvement on positive queries. This suggests the poor ability of Q2T to handle the \"complement\" operator. It is doubtful whether Q2T can maintain its performance when generalizing to more unseen query types.\n\nA2: We perceive the poor ability of Q2T to handle the \"complement\" operator is due to the KGE that is only trained on positive factual triples (line 488-492), because the distribution of answer entities of queries without negation operators is more concentrated, while the distribution of answer entities of queries with negation operators is more dispersed (as the \"complement\" operator may lead lots of candidate answers, such as \"Who is not the winner of the Turning Award\"). \n\nWe also computed the average 2-norm distance of candidate answer entity embeddings sets across different query types, denoted as $cdist$ (the higher the value of cdist, the more dispersed the distribution of embeddings within this set). Then we found that the $cdist$ of positive queries is smaller than its corresponding negative queries consistently, e.g., $cdist(ip)=9.08$, while $cdist(inp)=9.55$,  $cdist(2i)=7.73$, while $cdist(2in)=8.88$. The pretrained KGE models struggle to generate appropriate embeddings for queries with dispersed answer distributions, as they are only trained on positive factual triples with concentrated answer distributions. In the updated version, we will discuss this question in more detail \n\nBesides, Q2T also performs well on ip/pi queries, which are tested in zero-shot learning (described in Table 4). This means Q2T can generalize well on unseen query types without  \"complement\" operator.\n\n\n\n> Q3: For Missing References of FuzzQE and SQE \n\nA3: We have noticed these works,  due to page limitations, we didn't add them to Table1 although Q2T outperforms them, we will add them in the updated version.\n\n\n\n> Q4: Typo: what is “CQC” in table 7?\n\nA4: It should be Q2T, we apologize for forgetting to rename it in the appendix.\n\n\n\nBest regards,\n\nAuthors of Paper1769", "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": "1. As stated in “main contributions”, The paper introduces a novel perspective toward query encoding.\n\n2. The paper included the result from different KGE models, which substantiate the effectiveness of KG embedding in the whole CQA system. \n\n3. Also, The discussion on whether freezing the pre-trained KGE is quite insightful.\n", "reasons_to_reject": "1. Lack of ablation study. The major proposed design (also the main difference between Q2T and KgTransformer) is the answer decoding approach. KgTransformer outputs the final node embedding directly, while Q2T outputs two vectors (head, relation) and then decodes with a link predictor. However, the paper didn’t provide an ablation study to prove the importance of this design. Is the improvement brought by the transformer backbone or the link predictor?\n\n2. As stated in the paper, the Q2T model does not outperform the previous state-of-the-art models on negative queries, despite its significant improvement on positive queries. This suggests the poor ability of Q2T to handle the \"complement\" operator. It is doubtful whether Q2T can maintain its performance when generalizing to more unseen query types.\n\n\n", "questions_to_authors": "\n\n1. Missing baseline: FuzzQE [1] is a strong query encoding baseline without kg-embedding, it’s encouraged to add it into comparison.\n\n2. A contemporary work SQE [2] is highly related to this paper, it’s encouraged to add it to the discussion.\n", "paper_topic_and_main_contributions": "This paper proposes to embed the linearized query graph with KG embedding, then use a refined transformer-based model to encode it to head-relation representations. It achieved state-of-the-art results on three datasets in EPFO queries, with a relatively small number of parameters.\n", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "1. Typo: what is “CQC” in table 7?"}, "extra_text": {"Missing_References": "[1] Xuelu Chen, Ziniu Hu, and Yizhou Sun. Fuzzy logic-based logical query answering on knowledge graphs. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022\n\n[2] Jiaxin Bai, Tianshi Zheng, and Yangqiu Song. Sequential query encoding for complex query answering on knowledge graphs. Transactions on Machine Learning Research, 2023\n"}}, {"review_id": "colInatchq", "reviewer": "Reviewer_EuCv", "summary": "", "questions": "1. What is the explicit form of $b_{\\phi(v_i, v_j)}$? What does it mean by saying scalar indexed by $\\phi(v_i, v_j)$.\n2. How is label smoothing applied to the negative sampling loss.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer EuCv,\n\nThanks for your informative suggestions. Here is our feedback.\n\n\n\n> Q1: Some of the key technical details are missing. It is not clear how label smoothing is applied to the negative sampling loss.\n\nA1: Due to page limitations, we only represent our original loss function in formula 14, label smoothing utilizes soft one-hop labels instead of hard ones to add noise in the training, reduces the weights of true labels when calculating the training loss and thus prevents overfitting when training, the label after smoothing is as follows:\n$$\ny_{ls} = (1-\\alpha) y_h+\\frac{\\alpha}{K}\n$$\nwhere $y_{ls}$ is the smoothed label, $y_h$ is the original label, $\\alpha$ is the parameter of label smoothing, $K$ is the number of sampling. Lastly, standard cross-entropy loss is applied to these smoothed labels.\n\n> The coherence should be improved. For example, in Table 7, the model is named CQC but not Q2T as in the rest of this paper.\n\nIt should be Q2T, we apologize for forgetting to rename it in the appendix.\n\n\n\n> Q2: As an important baseline, LMPNN also proposes to only train neural networks and keep the KG embeddings unchanged. In the LMPNN paper, it states that \"Extensive experiments show that our approach is a new state-of-the-art neural CQA model, in which only one MLP network and two embedding vectors are trained.\"\n\nA2: We found that the official repository of LMPNN was updated once after we submitted the paper. In the new code version, LMPNN also maintains KGE unchanged during subsequent training. The updated comparison between Q2T and LMPNN is as follows:\n\n1.  In LMPNN, the $\\rho$ function of KGE is invoked during each message propagation for each edge, whereas Q2T only requires a single invocation of the KGE score function for any type of complex query. Therefore, Q2T is better suited for leveraging KGE with higher complexity and larger parameters.\n2. In LMPNN, the coupling of KGE and GNN necessitates the design of distinct logical message propagation functions (predicting head entity representations, predicting tail entity representations) for different types of score functions in KGE, as well as for different types of regularization optimization. However, Q2T can be employed with any KGE without the need for additional code modifications. Therefore, Q2T is more modular.\n\n\n\n> Q3: What is the explicit form of $b_{\\phi(v_i,v_j)}$, What does it mean by saying scalar indexed by $\\phi(v_i,v_j)$.\n\nA3: $b_i$ means the $t$-th element of vector $\\boldsymbol{b}$, which is a scalar. When $i=\\phi(v_i,v_j)$, $\\phi(v_i,v_j)$ is the index.\n\n\n\n> Q4: For Missing References of GammaE and Wasserstein-Fisher-Rao Embedding\n\nA4: We have noticed these works, due to page limitations and Wasserstein-Fisher-Rao Embedding was not published by ACL 2023 when we submitted this article, we didn't add them to Table1 although Q2T outperforms them, we will add them in the updated version. \n\n\n\nBest regards,\n\nAuthors of Paper1769", "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": "1. Q2T proposed novel ways of using KG embeddings.\n2. Q2T reaches state-of-the-art performance, particularly on EPFO queries. Though the scores on negation queries are not stronger than LMPNN, the overall performance is still competitive.", "reasons_to_reject": "1. Some of the key technical details are missing. It is not clear how label smoothing is applied to the negative sampling loss. The coherence should be improved. For example, in Table 7, the model is named CQC but not Q2T as in the rest of this paper.\n2. This paper seems to overclaim its contribution. As an important baseline, LMPNN also proposes to only train neural networks and keep the KG embeddings unchanged. In the LMPNN paper, it states that \"Extensive experiments show that our approach is a new state-of-the-art neural CQA model, in which only one MLP network and two embedding vectors are trained.\" Therefore, it is questionable to argue that \n\n>\"Compared to LMPNN, Q2T further decouples the training for simple and complex queries.\" in lines 206-208\n\n>\"Q2T (NF) means training KGE and encoder on simple and complex queries together (the same strategy as LMPNN)\" in lines 542-545, \n\nso as the comparisons in Table 7. I suggest that the authors double-check this carefully.", "questions_to_authors": "1. What is the explicit form of $b_{\\phi(v_i, v_j)}$? What does it mean by saying scalar indexed by $\\phi(v_i, v_j)$.\n2. How is label smoothing applied to the negative sampling loss.", "paper_topic_and_main_contributions": "This paper proposed a graph transformer-based approach (Query2Triple) for knowledge graph logical query answering, building upon the pretrained knowledge graph embeddings. Query2Triple proposed novel ways to use both the scoring function and pretrained embeddings of existing knowledge graph embedding approaches. The graph transformer model estimates virtual head and relation embeddings so the query answering problem is transformed into a tail estimation problem. It demonstrated strong performances on EPFO queries but suboptimal performances on negation queries.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "Yes", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "In Table 7, the model is named CQC but not Q2T as in the rest of this paper."}, "extra_text": {"Missing_References": "This paper could also discuss some of the baselines that appeared in EMNLP last year and ACL this year. A further literature review is suggested.\n\n1. Dong Yang, Peijun Qing, Yang Li, Haonan Lu, and Xiaodong Lin. 2022. GammaE: Gamma Embeddings for Logical Queries on Knowledge Graphs. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 745–760, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.\n2. Zihao Wang, Weizhi Fei, Hang Yin, Yangqiu Song, Ginny Wong, and Simon See. 2023. Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport. In Findings of the Association for Computational Linguistics: ACL 2023, pages 13679–13696, Toronto, Canada. Association for Computational Linguistics."}}]

Author rebuttal:

Meta-review: This paper proposed a graph transformer-based approach (Query2Triple) for knowledge graph logical query answering, building upon the pretrained knowledge graph embeddings.

Reasons to accept:
- The task addressed in the paper is relevant for EMNLP audience and it is supported by robust experiments and results.
- The paper proposes an interesting approach whose results are very competitive with SOTA.
- Analysis and discussion are robust and insightful for future research.

Reasons to reject:
- some concepts (baselines, contributions, and other minors, see reviews) can be described better in the text.
Decision: Accept-Findings