NuTrea: Neural Tree Search for Context-guided Multi-hop KGQA
Authors: Hyeong Kyu Choi
Seunghun Lee
Jaewon Chu
Hyunwoo J. Kim
Venue: NeurIPS 2023 poster (2023)
Keywords: Knowledge Graph Question Answering
Knowledge Graph
Graph Neural Networks
TL;DR: We propose NuTrea, a GNN model for multi-hop KGQA that resembles a tree search algorithm, and introduce the RF-IEF node embedding technique.

Abstract: Multi-hop Knowledge Graph Question Answering (KGQA) is a task that involves retrieving nodes from a knowledge graph (KG) to  answer natural language questions. Recent GNN-based approaches formulate this task as a KG path searching problem, where messages are sequentially propagated from the seed node towards the answer nodes. However, these messages are past-oriented, and they do not consider the full KG context. To make matters worse, KG nodes often represent pronoun entities and are sometimes encrypted, being uninformative in selecting between paths. To address these problems, we propose Neural Tree Search (NuTrea), a tree search-based GNN model that incorporates the broader KG context. Our model adopts a message-passing scheme that probes the unreached subtree regions to boost the past-oriented embeddings. In addition, we introduce the Relation Frequency-Inverse Entity Frequency (RF-IEF) node embedding that considers the global KG context to better characterize ambiguous KG nodes. The general effectiveness of our approach is demonstrated through experiments on three major multi-hop KGQA benchmark datasets, and our extensive analyses further validate its expressiveness and robustness. Overall, NuTrea provides a powerful means to query the KG with complex natural language questions. Code is available at https://github.com/mlvlab/NuTrea.

NuTrea: Neural Tree Search for Context-guided Multi-hop KGQA
Hyeong Kyu Choi Computer Sciences
Seunghun Lee Computer Science & Engineering
University of Wisconsin-Main Madison hyeongkyu. choi sroi@wisc.eer edu
Korea University
11sshh319@korea.co ac. kr
Jaewon Chu Computer Science & Engineering
Hyunwoo J. Kim
Computer Science Engincering
Korea University
Korea University hyunxoojjkn@kkrea.. ac. kr
allonsy07@korea.c ac.kr
Abstract
Multi-hop Knowledge Graph Question Answering (KGQA) is a task that involves retrieving nodes from knowledge graph (KG) answer natural language ques- tions. Recent GNN-based approaches formulate this task as a KG path searching problem, where messages are sequentially propagated from the seed node towards the answer nodes. However, these messages are past-oriented, and they do not consider the full KG context. To make matters worse, KG nodes often represent proper noun entities and are sometimes encrypted, being uninformative in selecting between paths. To address these problems, we propose Neural Tree Search (Nu- Trea), tree search- based GNN model that incorporates the broader KG context. Our model adopts message-passing scheme that probes the unreached subtree regions boost the past-oriented embeddings. In addition, we introduce the Rela- tion Frequency-Inverse Entity Frequency (RF-IEF) node embedding that considers the global KG context to better characterize ambiguous KG nodes. The general effectiveness of our approach is demonstrated through experiments on three major multi-hop KGQA benchmark datasets, and our extensive analyses further validate its expressiveness and robustness. Overall, NuTrea provides a powerful means query the KG with complex natural language questions. Code is available https://uthub.co///lla///nnn
Introduction
The knowledge graph (KG) is a multi-relational data structure that defines entities in terms of their relationships. Given its enormous size and complexity, it has long been challenge to properly query the KG via human languages [T6]. A corresponding machine learning task is knowledge graph question answering (KGQA), which entails complex reasoning the KG to retrieve the nodes that correctly answers the given natural language question. To resolve the task, several approaches focused on parsing the natural language process the KG so that answer nodes can be ranked and retrieved [144 2 Building on these
KG-executable form 7-10 whereas others tried to
works, there has been recent stream of research focusing on answering more complex questions with intricate constraints, which demand multi-hop reasoning on the KG.
Work done Korea University. Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Answering complex questions on the KG requires processing both the KG nodes (entities) and edges (relations). Recent studies have addressed multi-hop KGQA by aligning the question text with KG edges (relations), to identify the correct path from seed nodes (i.e., nodes that represent the question subjects) towards answer nodes. Many of these methods, however, gradually expand the search area outwards via message passing, whose trailing path information is aggregated onto the nodes, resulting in node embeddings that are past-oriented. Also, as many complex multi-hop KGQA questions require selecting nodes that satisfy specific conditions, subgraph-level (subtree- level) comparisons are necessary in distinguishing the correct path to the answer node. Furthermore, KG node entities often consist of uninformative proper nouns, and sometimes, for privacy concerns, they may be encrypted [[5]. To address these issues, we propose Neural Tree Search (NuTrea), a graph neural network (GNN) model that adopts a tree search scheme to consider the broader KG contexts in searching for the path towards the answer nodes.
NuTTee leverages expressive message passing layers that propagate subtree-level messages to ex- plicitly consider the complex question constraints in identifying the answer node. Each message passing layer consists of three steps, Expansion - Backup - Node Ranking, whose Backup step probes the unreached subtree regions to boost the past-oriented embeddings with future information. Moreover, we introduce the Relation Frequency-Inverse Entity Frequency (RF-IEF) node embedding, which takes advantage of the global KG statistics to better characterize the KG node entities. Overall, NuTrea provides novel approach in addressing the challenges of querying the KG, by allowing it to have a broader view of the KG context in aligning it with human language questions. The general effectiiennes of NuTrea is evaluated on three major multi-hop KGQA benchmark datasets: WebQuestionsSP
16..
Complex WebQuestions
and MetaQA [1]]
Then, our contributions are threefold:
We propose Neural Tree Search (NuTrea), an effective GNN model for multi-hop KGQA, which adopts tree search scheme with an expressive message passing algorithm that refers to the future-oriented subtree contexts in searching paths towards the answer nodes.
We introduce Relation Frequency-Ineen Entity Frequency (RF-IEF), a simple node embedding technique that effectively characterizes uninformative nodes using the global KG context.
We achieve the state-of-the-ar on multi-hop KGQA datasets, WebQuestionsSP and Complex We- bQuestions, among weakly supervised models that do not use ground-truth logical queries.
2 Related Works
A knowledge graph (KG) is type of a heterogencous graph 19 20 G = (V.E), whose edges in & are each assigned to a relation type by the mapping function f 8 - R. The KGs contain structured information from commonsense knowledge 15 21 to domain specific knowledge (22), and the Knowledge Graph Question Answering (KGQA) task aims to answer natural language questions grounding these KGs by selecting the set of answer nodes. Recent methods challenge more complex questions that require multi-hop graph traversals to arrive at the correct answer node. Thus, the task is aliased as multi-hop KGQA or complex KGQA, which is generally discussed in terms of two mainstream approaches [23]: Semantic Parsing and Information Retrieval.
Semantic Parsing. The main idea of semantic parsing-based methods is to first parse natural language questions into a logical query. The logical query is then grounded on the given KG in an exccutable form. For example, [8] applics the semantic query graph generated by natural language questions. In replace of hand-crafted query templates, [7] introduced framework that automatically learns the templates from the question-answer pairs. Also, [24] proposed a novel graph generation method for query structure prediction. Other methods take case-based reasoning (CBR) approach, where previously seen questions are referenced to answer a complex question. Approaches like 9 25 26 use case-basee reasoning by referring to similar questions or KG structures. Recently, proposed a framework that jointly infers logical forms and direct answers to reduce semantic emors in the logical query. A vast majority of methods that take the semantic parsing approach utilize the ground-truth logical forms or query executions during training. Thus, these supervised methods generally susceptible incomplete KG settings, but have high explainability.
10
Information Retrieval. Information Retrieval-basee methods focus processing the KG to retrieve the answer nodes. The answer nodes are selected by ranking the subgraph nodes conditioned on the given natural language question. One of the former works [27] proposes enhanced Key-Value

---

Memory neural network to answer more complex natural language questions. [28 and 229 extract answers from question sppooificsccccccoee subgraphs generated with text corpora. To deal with incompletenee
and sparsity of KG, [I]] presents a KG embedding method to answer questions. Also, [12 handles this problem by executing query in the latent embedding space. In effort to improve explainability of the information retrieval approach, [3] infers an adjacency matrix by learning the activation
probability of each relation type. By adapting the teacher-student framework with the Neural State Machine (NSM), (14) made learning more stable and efficient. Furthermore, [30] utilized multi-task learning that jointly trains on the KG completion task and multi-hop KGQA, while [2] provides a novel link prediction framework. Recently, there has been trend of borrowing the concept of logical queries from Semantic Parsing approaches, attempting to learn the logical instructions that guide the path search the KG [.. Our NuTrea also builds these approaches.
3 Method
In recent studies, models that sequentially process the knowledge graph (KG) from the seed nodes have shown promising results on the KGQA task. Building upon this approach, we propose Neural Tree Search (NuTrea). NuTrea adopts a novel message passing scheme that propagates the broader subtrec-level information between adjjccnt nodes, which provides more context in selecting nodes that satisfy the complex question constraints. Additionally, we introduce a node embedding technique called Relation Frequency-Invera information when initializing node features. These methods allow for richer representation of each node by leveraging the broader KG context in answering complex questions the KG.
Entity Frequency (RF-IEF), which considers the global KG
3.1 Problem Definition
Here, first define the problem settings for Neural Tree Search (NuTree)). The multi-hop KGQA task is primarily a natural language processing problem that receives a human language question X as input, and requires retrieving the set of nodes from G (V, 8) that answer the question. Following the standard protocol in KGQA (II] the subject entities in Xa are given and assumed always to be mapped to a node in V via entity-linking algorithms [31]. These nodes are called seed nodes, denoted V's E V,, which are used to extract subgraph Gg = (V₁, Eg) from G so that Vy is likely to contain answer nodes Va E Va. Then, the task reduces to a binary node classification problem of whether each node v E Vy satisfies v E Va.
Following prior works [14 [. we first compute different question representation vectors with language model based module, called Instruction Generators (IG). We have two IG modules, each for the Expansion (section
B.2.1p and Backup (section 3.2.2 step, compute
(9exp)
(0) I (xy)
M j=1 = (xy))
(1)
where we name 4xxp= Yoyk E RD as the expansion instruction and backup instruction, respectively. the supplement. Then, the learnable edge (relation) type embeddings R RRIR are randomly initialized or computed with pretrained language model. On the other hand, node embeddings H E R'D, Vy are initialized using the edges in Eg and their relation types by function H as H = H (E R) (e.g., H = arithmetic mean of incident edge relations). This is because the node entities are often uninformative proper nouns encrypted codes. Then, our NuTrea model F function is defined as
(
Detailed description on the IG module
" == F ((9p))) i=1. ( Vu: Gy. H).
(1) .N
where ý E R| the predicted node score vector normalized across nodes in Vg, whose ground- truth labels are y [1(v E Va)lvev, E Bl%),, Then, the model is optimized with the KL divergence loss between y and y. In this work, we claim our contributions in (section 3.2) and H (section 3.3)
3.2 Neural Tree Search (f)
Our Neural Tree Search (NuTrea) model consists of multiple layers that each performs message passing in three consecutive steps: (1) Expansion, (2) Backup, and (3) Node ranking. The Expansion step propagates information outwards to expand the search tree, which is followed by the Backup step, where the depth-K subtree content is aggregated to each of their root nodes, to enhance the past-oriented messages from the Expansion step. Then, the nodes are scored based on how likely they answer the given question.
3

---

What school did Martin Luther King Jr. receive his doctoral degree from?
Texp leducation, institute, ...]
IG
Qbak
doctor, degree....
1. IEF Node Embedding
2. Neural Tree Search
edocation 1.0
deliver speech
related to
KG Subgroph
g
Expansion (gexp)
edurattio attonntonnnn 1.0
related
mt
degnes
RF-IEF
Backup (qbak)
uuviuu tegret
previous methods w/o Backup
-0.2
inuriuu
0.3
educattion
equi + Iusg 0.6
0.3
Node Ranking
education 1.0
0.2
0.3
Expansion
Backup
+0.0-0.33
Figure Neural Tree Search. Given natural language question, corresponding KG subgraph Gy is extracted, and expansion instructions dexp and backup instructions 4hak are computed with Instruction Generators (IG). The node embeddings of Gy are first defined by our RF-IEF (section 3.3), which characterizes nodes based on the global KG information by suppressing prevalent relation types that hold less meaning. Then, in each NuTrea layer (section 3.2). messages are propagated outwards from the seed node with respect qexp (Expansion), which contain Tuture- future-oriented subtree information conditioned by qbak (Backup). Then, the nodes are scored by adding and normalizing the logits (Node Ranking), which are utilized in the subsequent layer. The figure describes the first layer of NuTrea whose Backup subtree depth K is 2, and di is the softmax function. Overall, Nu Nuer considers the broader KG contexts in distinguishing the correct paths, contrary previous methods that do not incorporate the Backup step.
3.2.1 Expansion
Starting from the seed node V, V,, a NuTrea layer first expands the search tree by sequentially propagating messages outwards to the adjacent nodes. The propagated messages e(() are conditioned on the expansion instructions (4exp) i=1 which are computed as
N
ReRLe(WWrr
FFa (esp).
where i E [1,N]. Wr E DxD is a learnable linear projection, Fuv = row(R) E RR is the relation v, and O is element-wise product operator. Optionally, the
type embedding of edge relative position embedding euv E R as
uv ReLURRWerrrrrr ewv) 9esp).
where eur is defined for each relation type. Then, for an edge - v, N types of messages are propagated, which are element-wiss products between the edge relation and the N different question representation vectors. This operation highlights the edges that are relevant to the given question. Then, the messages are aggregated to a node via an MLP aggregator, computed as
N
Σ
(1)
SuLav
HEN())
(5)
f, MLP(h, f.).
where h, = row RD is the node embedding and E RR is the score value of a head node u. the first layer, the seed nodes are the only head nodes, whose scores are initially set to 1. In subsequent layers, we use the updated node scores shortly section 3.2.3 Notably, the nodes with score su 0, which are typically nodes that are yet to be reached, do not pass any message to their neighbors.
whose computation will be introduced
3.2.2 Backup
After the Expansion step grows the search tree, the leaf nodes of the tree naturally contain the trailing path information from the seed nodes, which is past-oriented. To provide future context, employ

---

the Backup step to aggregate contextual information from subtrees rooted at the nodes reached by previous NuTrea layers. We denote subtree of depth K rooted at node T, (V,, E,) C Gy (Vq. Eq). Here, V, = {u SP(,, v) I K and & and "1, u2 V.). where SP(u, v) a function that returns the length of the shortest path between nodes and v. For the Backup step, we consider only the edge set E, of T.K The reason behind this that the edges (relation types) better represent the question context in guiding the search on the KG.
Vq) and E {(1 ("I u2)
Also, using both the node and edge sets may introduce computational redundancy, as the initial node features originate from the edge embeddings [4 (See section B.I.
To pool the constraint information from Ey, we apply max-pooling conditioned on the question content. Specifically, we take similar measure as the Expansion step by computing M types of messages conditioned on the backup instructions { (f) M
[ j=1"
U 4
Yaak
(6)
where j E [1. M] and We E RDDD, Then, we max max-pool pool the messages as
MAX- MAX-POOL () (u), u2) &v
(7)
which represents the extent to which the local subtree context of is relevant to the conditions and constraints in the question. Next, the information aggregated with an MLP layer, and the node embedding h, is updated as
M (n)
C, j=1 Cr
(8)
h, MLP(f, || c.).
where f, refers to the propagated embeddings originating from Eq. (5) This serves as a correction of the original past-oriented message with respect to question constraints, providing the next NuTrea layer with rich local context.
3.2.3 Node Ranking
Finally, each node is scored and ranked based on the embeddings before and after the Backup step. For node v. f, from Eq. (5) and h, from Eq. 8 are projected to the expansion-score s. and backup-score sy respectively, as
= We
-0)== h, Wb.
where We, W RR. The final node score is retrieved by adding the two scores. We context coefficient to control the effect of the Backup step, and apply softmax to normalize the scores as
s, Softmax ([s!") +1 +1 "adss"''Deee Dvery,
(10)
which is passed on to the next layer to be used for Eq. (5) Figure provides holistic view of our method, and pseudocode is in the supplement.
Overall, the message passing scheme of NuTrea resembles the algorithm of Monte Carlo Tree Search (MCTS): Selection - Expansion - Simulation - Backup. The difference is that our method replaces the node 'Selection' and 'Simulation' steps with a soft GNN-based approach that rolls out subtrees and updates the nodes at once, rather than applying Monte Carlo sampling methods.
3.3 RF-IEF Node Embedding (H)
Another notable challenge with KGs is embedding nodes. Many KG entities (nodes) are proper nouns that are not informative, and several KGQA datasets [66] [7] consist of encrypted entity names. Thus, given no proper node features, the burden is on the model layers to learn meaningful node embeddings. To alleviate this, we propose novel node embedding method, Relation Ceoquencc-Inveerse Entity Frequency (RF-IEF), which grounds on the local and global topological information of the KG nodes.
Term frequency-inverse document frequency (TF-IDF) is one effective feature that characterizes textual document (32 The bag-of-words model computes the frequency of terms a document and penalizes frequent but noninformative words, e.g., 'a', 'the', 'is", 'are', by the frequency of the
5

---

{a}
{a}
{a, c)
{a, b)
{a}
{6)
(c)
bl
ja,c)
fa b
fa
fa b.
bab. (a,
aa c, eh
[d]
{e]
[d]
(e}
{a, dj {a,c,e) <layer 2>
(a,b,d] c,, <layer 3>
{d]
(e)
<input>
<layer 1>
<layer 1>
(b)
Figure 2: Expressiveness of NuTree layers. In the input KG subgraph (left-most figure), let node and 2 be the seed and answer node, respectively, where information d is critical in choosing node the answer. The shaded nodes indicate the regions that sequentially reached by consecutive GNN layers. Compared (a) previous methods 14 that require 3 message passing steps for node to access d, our (b) NuTrea layer requires only 1 step for node 2 to acquire information d to determine it as the answer.
term across documents. Motivated by the idea, we represent node on KG as bag of relations. An entity node is characterized by the frequencies rare (or informative) relations. Similar to TF-IDE define two functions: Relation Frequeney (RF) and Inverse Entity Frequency (IEF). The RF function is defined for node E Va and relation type r R as
RF(v.))
Σ 1[f(e)= =3) (EI(V)
(11)
where [(v) is the set of incident edges of node v. 1l is an indicator function, and f & - R function that retrieves the relation type of an edge. Then, the output of the RF function is matrix RF I that counts the occurrence of each relation type incident to each node in the KG subgraph. We used raw counts for relation frequency (RF) to reflect the local degree information of node. On the other hand, the IEF function is defined
IV4l
IEF(r) log
(12)
1+ EF(r)
where
EF()) Σ 1 s.t. f(e) =r.
(13)
VETV
EF counts the global frequency of nodes across KG subgraphs that have relation r within its incident edge set. With IEF E RÍR), the RF-IEF matrix E R/V/1 is computed as
== RF diag(IEF).
(14)
where diag(IEF) E R[/G) denotes diagonal matrix constructed with the elements of IEF.
The RF-IEF matrix F captures both the local and global KG structure and it can be further enhanced with the rich semantic information on the edges of KGs. Unlike entity nodes with uninformative text, e.g., proper nouns and encrypted entity names, edges generally are accompanied by linguistic descriptions (relation types). Hence, the relations commonly embedded by pre-trained language model in KGQA. Combining with the relation embeddings R|R|DD our final RF-IEF node embeddings H is computed as
(15) where H RID/X>, and Wn, E RDDD, The RF-IEF node embeddings can be viewed as the aggregated semantics of relations, which are represented by a language model, based on graph topology as well as the informativeness (or rareness) of relations. A row in H is node embedding vector h, which is used in Eq. (5) at the first NuTrea layer.
H F R RW
3.4 Discussion
Expressiveness of the NuTrea layer. While many previous multi-hop KGQA models simultane- ously update all node embeddings, recent works 14 2 have shown the superiority of approaches that search paths on the KG. These methods gradually expand the searching area by sequentially

---

updating nodes closer to the seed node towards the answer nodes. Our model builds on the latter sequential search scheme as well, enhancing expressiveness with our proposed NuTrea layers.
With a simple toy example in Figure 2 we compare the message flow of previous sequential search models and our NuTrea. The example demonstrates that our NuTrea layer (b) can probe subtrees to quickly gather fringe node (i.e., node 4 or 5) information without exhaustively visiting them. This is accomplished by our Backup step, which boosts the original past-oriented node embeddings with future-oriented subtree information.
4 Experiments
4.1 Experimental Settings
Datasets. We experiment on three large-scale multi-hop KGQA datasets: MetaQA [35]. WebQues- tionsSP (WQP) [16) and Complex WebQuestions (CWQ) [17]. Meta-QA consists of three different splits, 1-hop. 2-hop, and 3-hop, each indicating the number of hops required reach the answer node from the seed node. The questions are relatively easy with less constraints. WQP and CWQ, on the other hand, contain more complex questions with diverse constraints. WQP relatively easier, as CWQ is derived from WQP by extending its questions with additional constraints. MetaQA is answer- able with the WikiMovies knowledge base [27], while WQP and CWQ require the Freebase KG [I5] to answer questions. Further dataset information and statisties are provided in the supplement.
Baselines. We mainly compare with previous multi-hop KGQA methods that take the Information Retrieval approach (section2) 2) These models, unlike Semantic Parsing approaches, do not access the ground truth logical queries and focus on processing the KG subgraph to rank the nodes to identify answer nodes. To introduce the three most recent baseline models: (1) SQALER [3] proposes scalable KGQA method whose complexity scales linearly with the number of relation types, rather than nodes or edges. (2) TERP (2] introduces the rotate-and scaasle entity link prediction framework to integrate textual and KG structural information. (3) ReaRev [I] adaptively selects the next reasoning step with variant of breadth-firs first search (BFS). Other baselines are introduced in the supplement.
Implementation Details. For WQP, 2 NuTrea layers with subtree depth K = is used, while CWQ with more complex questions uses layers with depth K 2. In the case of RF-IEF node embedding. we pre-compute the Entity Frequency (EF) values in Eq. 13) for subgraphs in the training set before training. We use the same EF values throughout training. validation, and testing. This stabilizes computation by mitigating the large variance induced by relatively small batch sizes. For MetaQA, the number of NuTrea layers are selected from (2, 3), and K for ego-graph pooling from (1,2). See the supplement for further hyperparameter settings and details.
4.2 Main Experiments
Here, we present the experimental results of NuTrea. Following the common evaluation practice of previous works, we test the model that achieved the best performance on the validation set. In the WQP dataset experiments in Table D we achieved the best performance of 77.4 H@ among strong KGQA baselines that take an information retrieval approach, as discussed in Section 2 Compared to the previous best, this is large improvement of 0.6 points. In terms of the Fl score, which evaluates the answer set prediction, our method achieved score of 72.7, exceeding the previously recorded value by a large margin of 1.8 points. In addition, we also improved the previous state-of-the-art performance on the CWQ dataset by achieving an 53.6 H@1 1, which is an improvement of 0.7 points.
We also experimented NuTrea on MetaQA as well. On three data splits, NuTrea achieved comparable performance with previous state-of-the-ae methods for simple question answering. Evaluating with the average H@1 score of the three splits, NuTrea performs second best among all baseline models.
see it performs reasonably well with easy questions
4.3 Incomplete KG Experiments
The KG often human made and the contents are prone to being incomplete. Hence, is a norm to test model's robustness on incomplete KG settings where a certain portion of KG triplets, i.e., tuple of (head, relation, tail), are dropped. This experiment evaluates the robustness of our model to missing relations in a KG. We follow the experiment settings in [1] and use the identical incomplete KG dataset which consists of WQP samples with [50%, 30%, 10%] of the original KG
triplets remaining. In Table 2 NuTrea performs the best in most cases, among the GNN models
7

---

Table I: Results multi-hop KGQA datasets. The Hit@] and Fl scores are reported. The baselines are taken from the original papers. The best performances bold, and the second best are underlined.
WQP
CWQ
MetaQA
Models
I@1
F1
1-hop
2-hop
3-hop
Avg. I@@1
KV-Mem 27
46.7
38.6
21.1
95.8
25.1
10.1
43.7
GraftNet 28
66.7
62.4
32.8
96.8
PulINet 29
68.1
45.9
97.0
99.9
91.4
96.1
HmbedKGQA 11
66.6
97.5
98.8
94.8
97.0
ReifiedKB [36
52.7
96.2
81.1
72.3
83.2
EMQL [7]
75.5
97.2
98.6
99.1
98.3
TransferNet
71.4
48.6
48.6
97.5
100.0
100.0
NSM(+p) [4]
73.9
66.2
48.3
44.0
97.3
99.9
98.9
98.7
NSM(+h) 14
74.3
67.4
48.8
44.0
97.2
99.9
98.9
98.6
Rigel [3X
73.3
48.7
SQALER-GNN 3
76.1
99.9
99.9
TERP 2
76.8
49.2
97.5
99.4
98.9
98.6
ReaRev
76.4
70.9
52.9
NuTrea (Ours)
77.4
72.7
53.6
97.4
100.0
98.9
98.8
Table 2: Incomplete KG experiments. NuTrea also performs well in incomplete KG settings. The baseline figures were taken from
Table 3:
Component ablation experiments. The ablation experiments were done on the WQP datasct. Two main contributions studied.
Portion KG triplets (%)
H@l
50%
F1
H@l
30%
F1 H@1 F1
10%
RF-IEF Node Emb.
Backup step
WQP H@1
WQP F1
Graftnel 28
47.7 34.3 34.9
20.4
15.5
6.5
SGReader 39
49.2 33.5 35.9
20.2
17.1
7.0
(-0.0)
72.7 (-0.0)
HGCN 40
49.3 34.3 35.2
21.0
18.3
7.9
74.8 (-2.6)
70.4 (-2.3)
ReaRev
53.4 39.9
37.9
23.6
19.4
8.6
/
76.8 (-0.6)
71.5 (-1.2)
NuTrea (Ours)
53.7 40.1 38.3
24.1
18.9 8.7
73.4 (-4.0)
70.9 (-1.8)
designed to handle incomplete KGs. We believe that our model adaptively learns multiple alternative reasoning processes and can plan for future moves beforehand via our Backup step, so that it provides robust performance with noisy KGs.
5 Analysis
In this section, we provide comprehensive analyses on the contributions of NuTrea to ensure its effectiveness KGQA. We try to answer the following research questions: Q1. How does each component contribute to the performance of NuTrea?? Q2. What is the advantage of NuTrea's 's tree search algorithm over previous methods? Q3. What are the effects the RF-IEF node embeddings?
5.1
Ablation Study
Here, we evaluate the effectiveness of each component NuTrea to answer Q1. An ablation study performed our two major contributions: the Backup step in our NuTrea layers and the RF-IEF node embeddings. By removing the RF-IEF node embeddings, we instead apply the common node initialization method used in [4 J. which simply averages the relation embeddings incident each node. Another option to use zero embeddings, but we found it worse than the simple averaging method. For Trea layer ablation, remove the Backup step which plays a key role in aggregating the future-oriented subtree information onto the KG nodes. Then, only the expansion-scon (s!*)) computed, and the backup-score (b)) is always 0. Also, the embedding f, (Eq. (5), directly output from the NuTrea layer and no further updates
made via the Backup step.
Table we can see that the largest performance drop is observed when Backup step removed. Without it, the model has limited access to the broader context of the KG and cannot reflect the complex question constraints in node searching. Further discussion on this property of NuTrea's message passing is provided in the next Section 5.2 Also, observed non-trivial 0.6 point drop

---

Entity Frequency
RF-IEF Weights
Who Queen Elizabeth Il's mom?
Queen Elizabeth
the Queen Mother
(0.0062 - 0.5297)
Enting Erequeen (eol)
organizztions founded
George VI
(0.9936 0.4678)
Q. What was James Garfield most known for?
US President
(0.0035 0.3069)
founders
Bustomante
Laity
(0.2491 0.1817)
Dvents
What country did Gregor Mendel live in?
Compated
Brno
(0.0023 = 0.5211) (0.5535 0.4755)
competiters
Austrian Silesia
menionn
Ollers
Figure 3: Qualitative examples (without
Kemar Builey-Cole Cole
Backup = with Backup) (section 5.2.2
Figure 4: Weights computed by RF-IEF (section 5.3
in H@ 1 by removing the RF-IEF initialization method. By ablating both components, there was
significant degradation of 4.0 H@) points.
5.2
Advantages of NuTrea
To answer Q2, we highlight the key advantages of NuTrea over recent approaches. We analyze the efficiency of NuTrea, and provide qualitative results.
5.2.1 Efficiency of NuTrea
In addition, to further verify the utility of our model, we provide analyses on the latency of NuTrea with WQP in Table 4 Compared to the most recent ReaRev [1] model, training and inference latency per epoch/sample is slightly bigger, due to our additional Backup module. However, thanks to our expressive message passing scheme, NuTrea converges way faster, allowing the training GPU hours to reduced from 4.3 hours to 2.9 hours.
Table 4: Latency of ReaRev and NuTrea.
Models
NuTrea (Ours)
ReaRev
Training Latency (per epoch) Inference Latency (per sample)
100.2 s
78.0
67.7 ms
51.3 ms
Training GPU Hours
2.9 H
4.3
To provide more insight in terms number of NuTrea layers, also reveal its effect model performance, in Figure []] The figure re- ports the F1 scores for both with and without the Backup module, evaluated on the WebQues- tionsSP dataset. "NuTrea without Backup" has an equivalent model configuration used in the Backup ablation experiment of Table Overall, the performance of "NuTrea without Backup" does generally improve with additional layers, but "NuTrea with Backup" reached the highest score of 72.7 with only 2 NuTrea layers. This is enabled by our Backup module, which allevi- ates the burden of exhaustively searching deeper nodes. This is computationally more efficient than stacking multiple layers to achieve higher perfor- mance. Specifically, by comparing the 2-layer "NuTrea with Backup" and 5-layer "NuTrea without Backup", the former required an average of 73.8 ms of inference time per question, whereas the latter required 108.6 ms. With only 68% of compute, our NuTrea achieved comparable performance with the deeper "NuTrea without Backup". Note, these latency values were evaluated on different environment from values reported in Table
73
72.7
72.1
72.7
72.5
F1 Score
71.0
70.4
56.7
NuTrea w/ Backup
NuTrea wo Backup
56.1
2
3
Number of Layers
Figure 5: Effect of number of layers.
5.2.2 Qualitative Results
In Figure we demonstrate several qualitative examples from our error analysis. In each question, the blue (node) entity is the correct answer choice, while the red is the wrong choice made by the

---

model without the Backup step. The values in parentheses demonstrate the difference in node scores between models without and with Backup. Without it, the sequential search model cannot refer to local contexts of node and frequently predicts an extremely low score for the correct answer node (e.g., 0.0062 for "Queen Elizabeth the Queen Mother" in the first question of Figure 33. Such a problem is mitigated by our NuTreea's 's Backup step, which tends to boost scores of correct answers and tone down wrong choices that were wrongly assigned with a high score. More qualitative examples are provided in the supplement, along with an analysis on the different importances of the Backup step in different datasets, by controlling the context coefficient 2.
5.3 Effect of RF-IEF
The RF-IEF node embedding is simple method inspired by an effective text representation technique in natural language processing. Here, disclose the specific effect of RF-IEF on the relation embedding aggregation weights, thereby answering Q3. In Figure (left), the log-scaled EF (Eq. 13) value of each relation type is sorted. The globally most frequent relation types. including "self_loop" s, are too general to provide much context in characterizing a KG node. Our RF-IEF suppresses such uninformative relation types for node embedding initialization, resulting Figure 4 (right). The pie charts display two examples on the difference between aggregation weights for node entity before and after RF-IEF is applied. To illustrate, the weight after RF-IEF corresponds to row of F in Eq. (14), while the weight before RF-IEF would be uniform across incident edges. As "Alexander Bustamante" a politician, the relation types "orgainizations founded" and "founders" become more lucid via RF-IEF, while relations like "events competed in" and "competitors" are emphasized for an athlete like "Kemar Bailey-Cole". Likewise, RF-IEF tends to scale up characteristic relation types in initializing the node features, thereby enhancing differentiability between entities. To further demonstrate RF-IEF's general applicability, we also provide a plug-in experiment on another baseline model in the supplement.
weight distribution like
Conclusion
Neural Tree Search (NuTrea) is an effective GNN model for multi-hop KGQA, which aims to better capture the complex question constraints by referring to the broader KG context. The high expressiveness of NuTrea attained via our message passing scheme that resembles the MCTS algorithm, which leverages the future-oriented subtree information conditioning the question constraints. Moreover, we introduce the RF-IEF node embedding technique to also consider the global KG context. Combining these methods, our NuTrea achieves the state-of-the-art in two major multi-hop KGQA benchmarks, WebQuestionsSP and Complex WebQuestions. Further analyses on KG incompleteness and the qualitative results support the effectiveness of NuTrea. Overall, NuTrea reveals the importance of considering the broader KG context in harnessing the knowledge graph via human languages.
Acknowledgments and Disclosure of Funding
This work was partly supported by ICT Creative Consilience program (UTP--003-2020--0000 supervised by the IITP, the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (NRF=2023R1A2222055377 A2C2005373). and KakaoBrain corporation.
References
[1] Costas Mavromatis and George Karypis. Rearev: Adaptive reasoning for question answering over knowledge graphs. In EMNLP EMNLL-Findings, 2022.
[2] Zile Qiao, Wei Ye, Tong Zhang, Tong Mo, Weiping Li, and Shikun Zhang. Exploiting hybrid semantics of relation paths for multi-hop question answering over knowledge graphs. COLING, 2022.
[3] Mattia Atzeni, Jasmina Bogojeska, and Andreas Loukas. Sqaler: Scaling question answering by decoupling multi-hop and logical reasoning. NeurlPS, 2021.
[4] Jinyoung Park, Hyeong Kyu Choi, Juyeon Ko, Hyeonjin Park, Ji-Hoon Kim, Jisu Jeong, Kyungmin Kim, and Hyunwoo Kim. Relation-awar anguage-graphl transformer for question answering. In AAAI, 2023.
10

---

[5] Kuan Wang. Yuyu Zhang, Diyi Yang, Le Song, and Tao Qin. Gan is a counter? revisiting gnn for question answering. In ICLR, 2021.
[6] X Zhang. A Bosselut, M Yasunaga. H Ren, P Liang, C Manning, and Leskovec. Greaselm: Graph reasoning enhanced language models for question answering. ICLR, 2022.
Abdalghani Abujabal, Mohamed Yahya, Mirck Riedewald, and Gerhard Weikum. Automated template generation for question answering over knowledge graphs. In WWW, 2017.
[8] Sen Hu, Lei Zou, and Xinbo Zhang. state-transition framework to answer complex questions over knowledge base. In EMNLP, 2018.
[9] Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-based reasoning for natural language queries over knowledge bases. In EMNLP, 2021.
[10] Donghan Yu. Sheng Zhang, Patrick Ng. Henghui Zhu, Alexander Hanbo Li, Jun Wang. Yiqun Hu, William Wang, Zhiguo Wang, and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases. arXiv preprint arXiv:22 (0.::2200.0003, 2022.
[11] Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. Improving multi-hop question answering over knowledge graphs using knowledge base embeddings. In ACL, 2020.
[12] Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Michihiro Yasunaga, Haitian Sun, Dale Schuurmans, Jure Leskovec, and Denny Zhou. Lego: Latent execution -uiddd reasoning for multi-hop question answering on knowledge graphs. In ICMI,, 2021.
[13] Jiaxin Shi, Shulin Cao, Lei Hou, Juanzi Li, and Hanwang Zhang. Transfernet An effective and transparent framework for multi-hop question answering over relation graph. In EMNLP, 2021.
[14] Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Improving multi-hop knowledge base question answering by learning intermediate supervision signals. In WSDM, 2021.
[15] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In ACM SIGMOD, 2008.
[16] Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In ACI, 2016.
[17] Alon Talmor and Jonathan Berant. The web as a knowledge-base for answering complex questions. In NAACL, 2018
[18] Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J Smola, and Le Song. Variational reasoning for question answering with knowledge graph. In AAAI, 2018
[19] Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heterogeneous graph neural network. ACM SIGKDD, 2019.
[20] Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, and S Yu Philip. A survey on heterogencous graph embedding: methods, techniques, applications and sources. IEFE Transactions on Big Data, 2022.
[21] Robyn Speer, Joshua Chin, and Catherine Havasi. Conceptnet 5.5: An open multilingual graph of general knowledge. In AAAI, 2017.
[22] Di Jin, Eileen Pan, Nassim Oufattole. Wei-Hung Weng. Hanyi Fang, and Peter Szolovits. What disease does this patient have? a large-scale open domain question answering dataset from medical exams. Applied Sciences, 11(14):6421, 2021.
[23] Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji- Ji-Rong Wen. A survey complex knowledge base question answering: Methods, challenges and solutions. In IJCAI, 2021.
[24] Yongrui Chen, Huiying Li, Yuncheng Hua, and Guilin Qi. Formal query building with query structure prediction for complex question answering over knowledge base. IJCAI, 2020.
[25] Dung Thai, Srinivas Ravishankar, Ibrahim Abdelaziz, Mudit Chaudhary, Nandana Mihindukulasooriya, Tabira Naseem, Rajarshi Das. Pavan Kapanipathi, Achille Fokoue, and Andrew McCallum. Cbr-ikb: A case-based reasoning approach for question answering over incomplete knowledge bases. arXiv preprint arXiv:2204.0m 08554, 2022.
11

---

[26] Rajarshi Das. Ameya Godbole, Ankita Naik, Elliot Tower, Manzil Zaheer. Hannaneh Hajishirzi, Robin Jia. and Andrew McCallum. Knowledge base question answering by case-based reasoning subgraphs. In ICML, PMLR, 2022.
[27] Alexander Miller, Adam Fisch, Jesse Dodge, Amir--osseii Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. EMNLP, 2016.
[28] Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdino,, and William Cohen. Open domain question answering using early fusion of knowledge bases and text. EMNLP, 2018.
[29] Haitian Sun, Tania Bedrax- Weiss, and William Cohen, Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text. In EMNLP-IJCNLP. 2019.
[30] Lihui Liu, Boxin Du, Jiejun Xu, Yinglong Xia, Hanghang Tong. Joint knowledge graph completion and question answering. In ACM SIGKDD, 2022.
[31] Scott Wen-tau Yih, Ming- Heig-Weii& Wei Chang, Xiaodong He, Jianfeng Gao. Semantic parsing staged query graph generation: Question answering with knowledge base. In Proceedings of the Joint Conference of the 53rd Annual Meeting of the ACL and the 7th International Joint Conference on Natural Language Processing the AFNLP, 2015.
[32] Hans Peter Luhn. The automatic creation of literature abstracts. IBM Journal of research and development, 1125119-115, 1958.
[33] Stephen E Robertson and K Sparck Jones. Relevance weighting of search terms. Journal of the American Society for Information science, 27(3): 146, 1976.
[34] Gerard Salton and Christopher Buckley. Terg-tiighting approaches in automatic text retrieval. Information processing & management, 24(5):513-55) 523, 1988.
[35] Yuyu Zhang, Hanjun Dai. Zornitsa Kozareva, Alexander J Smola, and Le Song. Variational reasoning for question answering with knowledge graph. In AAAI, 2018
[36] William W Cohen, Haitian Sun, R Alex Hofer, and Matthew Siegler. Scalable neural methods for reasoning with symbolic knowledge base. In ICLR, 2020.
[37] Haitian Sun, Andrew Arnold, Tania Bedrax Weiss, Fernando Pereira, and William W Cohen. Faithful embeddings for knowledge base queries. NeurlPS, 2020.
[38] Priyanka Sen, Armin Oliya, and Amir Saffari. Expanding end-to-end question answering on differentiable knowledge graphs with intersection. In EMNLP, 2021.
[39] Wenhan Xiong, Mo Yu, Shiyu Chang, Xiaoxiao Guo, and William Yang Wang. Improving question answering over incomplete kbs with knowledge-aware reader. ACL, 2019.
[40] Jiale Han, Bo Cheng, and Xu Wang. Open domain question answering based on text enhanced knowledge graph with hyperedge infusion. In EMNLP-Findings, 2020.
12


Reviews:
[{"review_id": "O56o7dhGRA", "reviewer": "Reviewer_jrbk", "summary": "This paper proposed NuTrea, a graph neural network (GNN) model for Multi-hop KGQA. NuTrea considers broader KG contexts using a tree search scheme to find paths to answer nodes. It uses message-passing layers to explicitly consider question constraints involving bi-directional information (or future context). Also, this paper proposed an interesting node embedding method RF-IEF to characterize KG node entities.", "questions": "See weaknesses.", "limitations": "I have no concerns about the limitations.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea of predicting entities by bi-directional information is reasonable.\n\n- The Relation Frequency–Inverse Entity Frequency metric brined new insight into initializing embeddings of graph nodes.\n\n- The experiments demonstrate the effectiveness of the proposed method.\n\n- The paper is well-written.", "weaknesses": "- The core technical design of this work involves utilizing a backup mechanism that allows models to leverage bidirectional information (or global context), enabling them to distinguish entities with similar paths. Some embedding-based methods(e.g., EmbedKGQA and TERP) and GNN-based methods (e.g., SQALER and GraftNet) can also utilize bidirectional information, somewhat sharing a similar high-level idea. The unique superiority compared with these methods and the connections to them deserve more discussions and analyses. Otherwise, it is unclear how to position this work in the current research background, making the technical contribution seem incremental.\n\n- Although the main results and ablation study show performance superiority, most further analyses are about qualitative evaluation. Figure 2 is more about a concept-illustration example instead of an expressiveness analysis. Putting it into other sections (e.g., introduction or method) may be better. Related to the first issue, this work needs more experimental design and in-depth analysis to highlight the unique merits of the proposed methods regarding leveraging the global context. For example, I am curious to see if this method can outperform other models when both the correct and incorrect entities have the same path. \n\nAfter reading the author’s rebuttal, most of my concerns are addressed. I have no objection to accepting this paper if the authors include more discussion about related works exploiting bidirectional information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. What makes NuTrea different from previous embedding-based and GNN-based methods?\nWhile previous methods (e.g., EmbedKGQA, GraftNet, SQALER) _simultaneously_ update embeddings of all the KG nodes, our NuTrea gradually expands the subgraph and _sequentially_ updates nodes from the seed node towards the answer node, similar to a path-search algorithm. The superiority of this approach has been demonstrated in several recent works, such as NSM (WSDM 2021), TERP (COLING 2021) and ReaRev (EMNLP-Findings 2022). We believe that paths provide a more effective representation of question semantics and are better suited to process the KG in alignment with the given question. Our work builds on this recent line of research by incorporating bi-directional information for enhanced path searching.\n\n&nbsp;\n\n### Q2. Need for analysis to highlight NuTrea’s merit in leveraging global context. For example, can this method outperform other models when both the correct and incorrect entities have the same path?\nAs suggested, we analyzed the ratio of questions that have a KG path (i.e., meta path) that leads to both the correct and incorrect node choices. In the WebQuestionsSP dataset that utilizes the Freebase KG [1], approximately 72% of the questions entailed such KG paths. Thus, outperforming other models on this dataset naturally indicates NuTrea’s unique merit in dealing with circumstances where global context should play a critical role. On the other hand, the MetaQA (1, 2, and 3-hop) dataset that adopts the WikiMovies KB [2] only contained 34% of the questions with such a KG path, which possibly explains the relatively smaller gain in performance on this dataset.\n\n[1] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In ACM SIGMOD, 2008.\\\n[2] Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. In EMNLP, 2016\n\n&nbsp;\n\n### Q3. Putting Figure 2 in the Introduction or Method section may be better.\nWe will reflect your suggestion in our final version. Thank you."}, {"review_id": "J2CgBnO3cQ", "reviewer": "Reviewer_E45E", "summary": "The proposed model adopts a message-passing scheme that probes the unreached subtree regions to boost node embeddings.The work also introduces the Relation Frequency–Inverse Entity Frequency (RF-IEF) node embedding that considers the global KG context to better characterize ambiguous KG nodes. The method shows some effectiveness over multiple datasets.", "questions": "-\tAre relation and relation type the same thing?\n-\tCan you list situations where this backup not useful? Or is it always useful?\n-\tAlso address the weaknesses", "limitations": "The authors discuss some limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "-\tGood results on multiple datasets\n-\tRF-IEF style node embeddings introduced. Might be useful in other works too.\n-\tNice Analysis section.", "weaknesses": "-\tModel sizes/ compute not clearly discussed. Some information present in Table 4 but insufficient.\n-\tHow is the backup step different from a bigger expansion set in the previous works. This model doesn’t bring in any significant inductive bias over previous models.\n 1. The backup is like a DFS during the expansion BFS. Really depends on the dataset as to where you want to focus your compute on. One could either explore or exploit.\n 2. How would this model holdup in 4 or 5 hop QA? Would it not be extremely inefficient?\n-\tThe gains are somewhat marginal and might just be achieved by increasing parameters/expansion depth in previous models.\n-\tRF-IEF is pitched as a generalized node embedding method but was not tested in other models. Although some nice analysis shown.\n-\tBad writing. Lot of forward references to future text - Eq 1, Eq 5.\n-\tIG model descriptions very handwavy in paper and appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. Model size comparison is needed.\nBelow is the table containing the number of model parameters of NuTrea and ReaRev. Although NuTrea contains more parameters, it requires far less training hours than ReaRev. Also, increasing the model size of ReaRev does not necessarily enhance performance (See Q2).\n\n|  | Parameters | Training GPU Hours |   |   |\n|:------:|:----------:|:------------------:|---|---|\n| NuTrea |50 M| 2.9 Hrs | | |\n| ReaRev|24 M| 4.3 Hrs | | |\n \n&nbsp;\n\n### Q2. Can performance gain be achieved by increasing parameters or expansion depth in previous models?\nNo significant performance improvement was observed in the previous model, ReaRev, by simply increasing the expansion depth (i.e., the number of layers). Various expansion depths were tested, ranging from 2 to 5, but the H@1 and F1 performances did not improve much with deeper models. In fact, the original model with 2 layers performed better than deeper variants. Additionally, an attempt was made to enhance the ReaRev-5 model's width by increasing its dimension to 100, denoted as ReaRev-5X in the table below. However, even with these modifications, the performance did not match that of NuTrea. To ensure fairness in comparison, all models, including NuTrea, were trained again under identical environments and conditions.\n|  | # layers |  H@1 |  F1  |   |\n|-----------------|:--------:|:----:|:----:|---|\n| ReaRev-2 (base) | 2 | 75.4 | 70.4 | |\n| ReaRev-3|  3 | 74.0 | 69.9 | |\n| ReaRev-4| 4| 73.8 | 69.5 | |\n| ReaRev-5|5| 74.4 | 70.5 | |\n| ReaRev-5X|5  | 74.9 | 70.2 | |\n| NuTrea (ours)|2  | **77.3** | **72.2** | |\n\n&nbsp;\n\n### Q3. How is the Backup step different from a bigger expansion set in the previous works?\nCompared to previous message passing methods, our Backup’s max-pooling operator (Eq. (7) of manuscript) has its unique advantage in aggregating relevant information from the bag of relations within the multi-hop neighbors (i.e., the subtree). Backup’s effectiveness has been thoroughly demonstrated in our ablation studies (Table 3 of manuscript), providing 3.4 H@1 and 0.6 F1 improvements from the base setting. Furthermore, the experimental results in Q2 reveals that ReaRev with a greater expansion set does not necessarily improve performance.\n\n&nbsp;\n\n### Q4. Will NuTrea be extremely inefficient in 4 or 5 hop QA?\nEach NuTrea layer consists of three steps: (1) Expansion, (2) Backup, and (3) Node ranking. As the model complexity scales linearly with the number of layers (or hops), similar to GNNs, handling 4 or 5-hop QA settings by adding a few more NuTrea layers will not impact efficiency significantly. NuTrea remains sufficiently scalable for such scenarios.\n\n&nbsp;\n\n### Q5. RF-IEF was not tested in other models.\nIn fact, a plug-in experiment on ReaRev is already provided in Table 4 of Appendix I. We brought the table below for your convenience. We observed that ReaRev’s average performance improves with RF-IEF. Note, the values in parentheses are standard deviations across 5 runs.\n| Models         |   ReaRev   | NuTrea (Ours) |\n|----------------|:----------:|:-------------:|\n| without RF-IEF | 74.2 (1.4) |   75.5 (1.1)  |\n| with RF-IEF| 74.6 (0.8) |   76.3 (1.4)  |\n\n&nbsp;\n\n### Q6. Bad writing - Lots of forward references to future text.\nWe’ll polish our writing and reduce forward references in our final version. Thank you.\n\n&nbsp;\n\n### Q7. IG model descriptions are very hand-wavy.\nThe Instruction Generator (IG) is a commonly used text processing module used in many previous KGQA works, including NSM and ReaRev, and its details have already been described in Appendix B. To further illustrate its details, an IG takes the natural language question $x_q$ as input to output question representations $\\\\{\\mathbf{q}_\\text{exp}^{(i)}\\\\}\\_{i=1}^N$ as \n\n$\\\\{\\mathbf{q}\\_\\text{exp}^{(i)}\\\\}\\_{i=1}^N = \\text{IG}_\\text{exp}(x_q).$\n\nIn the IG function, a tokenizer converts input $x_q$ to tokens $\\\\{\\mathbf{x}\\_t\\\\}\\_{t=1}^T$ that are used to retrieve the sentence embedding $\\mathbf{q}_\\text{LM}$ with a language model $\\text{LM}(\\cdot)$ (e.g., SentenceBERT) as\n\n$\\mathbf{q}\\_\\text{LM} = \\text{LM}(\\\\{\\mathbf{x}\\_t\\\\}\\_{t=1}^T).$\n\nTo deterministically sample a sequence of sentence representations, a quasi-monte carlo sampling (or non-probability sampling) approach is adopted. $\\mathbf{q}_\\text{LM}$ is first used to compute attention weights $a_t^{(i)}$ as\n\n$\\mathbf{q}^{(i)} = \\boldsymbol{W}^{(i)} (\\mathbf{q}^{(i-1)} ||   \\mathbf{q}\\_\\text{LM}  ||   \\mathbf{q}\\_\\text{LM} - \\mathbf{q}^{(i-1)} ||  \\mathbf{q}\\_\\text{LM} \\odot \\mathbf{q}^{(i-1)})$\\\n$a_t^{(i)} = \\text{Softmax}(\\boldsymbol{W}_a (\\mathbf{q}^{(i)} \\odot \\mathbf{x}_t)),$\n\nwhere  $i \\in [1,N]$, and  $\\mathbf{q}^{(0)}$ is a zero vector. Also, $||$ indicates the concatenation operator, and $\\boldsymbol{W}\\_a \\in \\mathbb{R}^{D\\times D}$, $\\boldsymbol{W}^{(i)} \\in \\mathbb{R}^{D \\times 4D}$ are learnable matrices. Finally, each question representation $\\mathbf{q}\\_\\text{exp}^{(i)}$ is computed as\n\n$\\mathbf{q}\\_\\text{exp}^{(i)} = \\sum_t a_t^{(i)} \\mathbf{x}_t.$\n\nThe same process is repeated to compute the Backup instructions. We will add this enhanced explanation in our final version.\n\n&nbsp;\n\n### Q8. Are relation and relation type the same thing?\nThe term “relation” refers to the edge or link between two entities in a KG, representing a factual connection between them. On the other hand, “relation type” refers to the type or category of the edge (link).\n\n&nbsp;\n\n### Q9. Can you list situations where Backup is not useful? Or is it always useful?\nBackup is less useful when the global context is less important. Particularly, if the question does not incorporate any conditions or constraints that require considering the broader context of the graph, the Backup module might become redundant. Additionally, if the answer nodes can be easily reached within a few hops from the starting node, the Expansion module alone might be enough to find the correct answer node.\n"}, {"review_id": "RKPYTa2jvd", "reviewer": "Reviewer_jk9R", "summary": "The paper presented two improvements to graph-based (KG) QA tasks: (1) Backup step, and (2) RF-IEF. Both proposed methods, according to Table 3, lead to significant improvement on multiple multi-hop QA tasks.", "questions": "1. Can you please specify your loss function? Is the model trained end-to-end? Any intermediate supervision?\n2. Can you please explain why the ablation study is performed on WQ? Some questions in WQ are 1-hop questions. CWQ should have more multi-hop questions where BackUp should benefit more.", "limitations": "Please see weakness/questions above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed idea of including a BackUp step, which resembles MTCS, is very interesting. Experimentally, it leads to the biggest difference (> 2 points) on the WQ dataset. To my knowledge, this is first paper which explicitly write out the backup term, while previous research relies on the GCN to capture contextual information from the neighbors.\n\nThe RF-IEF is also an interesting observation. The improvement, however, is not as significant. As mentioned by the authors, \"Many KG entities (nodes) are pronouns that are not informative, and several KGQA datasets [11, 12] consist of encrypted entity names.\" Can you please run your model on a subset of questions with \"pronouns\" and/or encrypted entity names\" to justify this claim?", "weaknesses": "Overall, this is a good paper. \n\nPlease consider running experiments suggested above, i.e. with \"pronouns\" and/or encrypted entity names\".\n\nOther comments:\n1. Line 105, it's a bit unfair to say \"Following the standard protocol in KGQA [5], the subject entities in 𝑥𝑞 are given and assumed always to be mapped to a node in V\". There are many work which doesn't make that assumption. It would be better to say this is an assumption you made and make sure that numbers in Table 1, 2, 3 all follow this assumption.\n\n2. Can you please specify what are \"edge type\" in line 116?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. Can you run your model on a subset of questions with \"pronouns\" and/or encrypted entity names\"?\nAll the questions in WebQuestionsSP and ComplexWebQuestions entail encrypted KG entities. Thus, the results in our paper already represent the experimental setting in question.\n\n&nbsp;\n\n### Q2. Is \"Following the standard protocol in KGQA, the subject entities in $x_q$ are given and assumed always to be mapped to a node in $\\mathcal{V}$\" the authors’ assumption?\nThis is not an assumption we made on our own. It is is a standard protocol of KGQA datasets, whose seed nodes (subject entities) are always provided along with the KG subgraph for each question. Thus, we can assume that this assumption holds as long as we evaluate our model on WebQuestionsSP, ComplexWebQuestions, or MetaQA.\n\n&nbsp;\n\n### Q3. what is \"edge type\" in line 116?\nIn this work, “edge type” is equivalent to “relation type”. The edge type (relation type) defines the factual relationship between the two connected nodes (entities) on the KG.\n\n&nbsp;\n\n### Q4. Can you specify your loss function? Is the model trained end-to-end? Any intermediate supervision?\nYes, the model is trained end-to-end without any intermediate supervision. As specified in Line 122~123, we use the KL divergence loss between the predicted score $\\mathbf{\\hat{y}} \\in \\mathbb{R}^{|\\mathcal{V}\\_q|}$ and the ground truth multi-hot vector $\\mathbf{y}  \\in \\mathbb{B}^{|\\mathcal{V}\\_q|}$.  That is,\n\n$\\mathbf{\\hat{y}} = \\text{NuTrea}(\\\\{\\mathbf{q}\\_{\\text{exp}}^{(i)}\\\\}\\_{i=1}^N, \\\\{\\mathbf{q}\\_\\text{bak}^{(j)}\\\\}\\_{j=1}^M, \\mathcal{V}\\_s)$\\\n$\\mathcal{L} = \\text{KLD}(\\mathbf{\\hat{y}}, \\mathbf{y}),$\n\nwhere $\\\\{\\mathbf{q}\\_{\\text{exp}}^{(i)}\\\\}\\_{i=1}^N$ refers to the expansion instructions, $ \\\\{\\mathbf{q}\\_\\text{bak}^{(j)}\\\\}\\_{j=1}^M$ refers to the backup instructions, $\\mathcal{V}\\_s$ is the set of seed nodes, and $\\text{KLD}(\\cdot)$  is the KL divergence function.\n\n&nbsp;\n\n### Q5. Ablation study on CWQ.\nThe ablation results on ComplexWebQuestions are provided in the table below.\n| RF-IEF | Backup | CWQ H@1 | CWQ F1 |\n|:------:|:------:|:-------:|:------:|\n|    v   |    v   |   53.6  |  49.5  |\n|    v   |        |   52.7  |  48.7  |\n|        |    v   |   53.1  |  47.4  |\n|        |        |   51.7  |  48.7  |"}, {"review_id": "sfCEiNIbQS", "reviewer": "Reviewer_QeEo", "summary": "In this paper, a retrieval-based solution to the Multi-hop KGQA problem is proposed. The authors introduce a novel approach that incorporates two innovations: a GNN network with bidirectional message passing (Expansion and Backup) and a novel method for embedding knowledge graph vertices, inspired by TF-IDF.\n \nThe paper features numerous experiments and comparisons with existing baselines using well-known datasets such as WebQuestionsSP, ComplexWebQuestions, and Meta-QA, all of which rely on Freebase KG. \nFurthermore, the authors provide an extensive analysis of the proposed technique, showing that the introduced backup method makes the maximum contribution to the improvement of the results.\n", "questions": "Experiments conducted on Incomplete KG demonstrate that the proposed approach performs notably better compared to others. However, it is not specified in the paper whether RF-IEF was re-trained separately for each Incomplete KG or if the original one was used. If the latter case is true, the experiment is unfair and should be recalculated.", "limitations": "NuTrea limits the search for answers to the vicinity of the original vertex, which restricts the depth of exploration within the graph. The initial depth of search is predetermined and additional heuristics are required.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "In this paper, the authors introduce a new method to the solution of the KGQA problem. The backup component of their solution stands out as particularly intriguing because of its maximum contribution to the improvement of the final results. The method is explained in a clear manner, with all essential formulas described qualitatively. Explanation of the inner working of the method is clear. NuTrea, the proposed approach, demonstrates results that are comparable to the State-of-the-Art (SOTA). Additionally, the authors have conducted qualitative comparisons with existing methods. Openly releasing the code will  benefit the community. \n", "weaknesses": "The authors did not compare their proposed method with papers that showed significantly better results, such as DECAF (DPR + FiD-3B) (Yu, et al., 2023) with a Hit@1 of 78.8. The reason for not doing so was not explained.\nOne aspect of the system utilizes graph vertex embeddings, and the authors introduce a new approach called RF-IEF. However, it is unclear why the authors did not compare the performance of NuTrea with other graph node embeddings like PyTorch-BigGraph, which may have yielded better results. Currently, it is difficult to evaluate the effectiveness of the proposed vertex embedding approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. Why is NuTrea not compared with other methods (e.g. DECAF) that have better results?\nAmong the various KGQA methods, the ones that outperform NuTrea belong to the “Semantic Parsing” category, where they leverage ground-truth logical queries (forms) during training (refer to section 2, Related Works). The logical queries are like ground-truth paths to the answer nodes, which can substantially enhance model performance through supervised training. On the contrary, NuTrea and its baselines belong to the \"Information Retrieval\" category, where direct supervision using ground truth logical queries is not utilized. To our knowledge, NuTrea demonstrates the best performance among the Information Retrieval approaches.\n\n&nbsp;\n\n### Q2. Why is RF-IEF not compared with other graph node embeddings like PyTorch-BigGraph?\nWe compared RF-IEF with three commonly used node embeddings for knowledge graphs, namely TransE, DistMult, and ComplEx. These node embeddings were trained solely on the training set, similar to how we computed the RF-IEF only on the train data. As shown in the table below, the results demonstrate that NuTrea with RF-IEF significantly outperforms the other node embeddings. We conjecture that the main reason for this is that other node embeddings were not contrived for the inductive settings in the KGQA task. That is, node entities that were not seen during the embedding training steps had to be initialized to zero vectors, which would have inevitably damaged performance. Our RF-IEF (and also the previously used method from NSM [1]), on the other hand, is better suited for inductive settings.\n\nIn the case of PyTorch-BigGraph, the pretrained embeddings were labeled with different ID’s, preventing us from mapping the embeddings to the corresponding nodes.\n\n| KG Node Embeddings | WQP H@1 | WQP F1 |\n|:------------------:|:-------:|:------:|\n|       TransE       |   74.6  |  70.0  |\n|      DistMult      |   75.5  |  69.9  |\n|       ComplEx      |   74.1  |  68.7  |\n|       NSM [1]      |   76.8  |  71.5  |\n|       **RF-IEF**  (ours)     |   **77.4**  |  **72.7**  |\n\n[1] Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Improving multi-hop knowledge base question answering by learning intermediate supervision signals. In WSDM, 2021.\n\n&nbsp;\n\n### Q3. Was RF-IEF retrained for each incomplete KG experiment?\nYes, the RF-IEF was recomputed for each incomplete KG experiment, and no pretrained parameters were used for RF-IEF. Thus, the KG incompleteness experiment in Table 2 of the manuscript is valid.\n"}, {"review_id": "8K5uPtdusR", "reviewer": "Reviewer_5UYV", "summary": "This paper proposes a tree search-based GNN model that contains three consecutive steps: expansion, backup, and node ranking. It also proposes a relation frequency-inverse entity frequency node embedding method. The proposed model achieves new SOTA on WebQSP and CWQ datasets.", "questions": "In the ablation study in Table 3, we see a significant performance drop when not using the Backup step. Under this setting, have the authors tried varying the layers of GNN? It would be interesting to see the performance-#layer curves with and without the backup step.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It proposes a tree-search-based GNN method with backup propagation to extend the KG context, which is intuitive and novel.\n2. The RF-IEF node embedding, motivated by TF-IDF, is also a novel method and experimentally effective.\n3. The proposed method achieves SOTA on WebQSP and CWQ datasets.\n4. Extensive experiments including incomplete KG setting, ablation study, and advantage analysis of the proposed method.", "weaknesses": "1. The enhancement relative to the leading benchmark approach, ReaRev, is marginal, notably on the CWQ dataset. The progress is even more slight in the context of the incomplete KG scenario, as highlighted in Table 2.\n\n2. In such circumstances, a more detailed comparative analysis with ReaRev might be required. ReaRev, which employs a variation of the breadth-first search for adaptive reasoning, also strives to expand the modeling of the KG context. How is the proposed tree search method better than ReaRev? More crucially, given that RF-IEF supplements the GNN model, what could be the outcome if RF-IEF were integrated with ReaRev? Would it still perform worse than NuTrea?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. Performance gains are marginal on ComplexWebQuestions and incomplete KG experiments.\nNuTrea’s 0.7 H@1 gain aligns with the standard improvements observed in recently published works. For instance, TERP (COLING 2022) reported a 0.6 H@1 gain compared to the previous best, Rigel (EMNLP 2021) reported a 0.1 H@1 gain, and TransferNet (EMNLP 2021) lags behind NSM (WSDM 2021) by 0.2 H@1. Therefore, when evaluated within the context of these existing works, our 0.7 point gain is far from marginal.\n\nFor incomplete KG experiments, on the other hand, it is important to note that incomplete KG experiments involve training with a considerably low portion of KG triplets (10%, 30%, and 50%). As a result, the performance level in such a setting reaches a state of high saturation, making any improvement even more noteworthy.\n\n&nbsp;\n\n### Q2. How is the proposed tree search method better than ReaRev? \nThe key advantage of NuTrea from ReaRev is the Backup module that considers the subtree contents (i.e., the unreached regions), without explicitly visiting or updating child nodes in the subtree. This approach is crucial in distinguishing between correct and incorrect node choices, especially when the same sequence of relations (i.e., meta paths) can lead to both correct and incorrect nodes. This enhancement allows NuTrea to make more informed decisions during the tree search process based on broader subtree-level contexts, leading to overall performance improvement.\n\n&nbsp;\n\n### Q3. If RF-IEF were integrated with ReaRev, would it still perform worse than NuTrea?\nIn fact, a plug-in experiment on ReaRev is already provided in Table 4 of Appendix I. We brought the table below for your convenience. In the table, we observed that ReaRev’s average performance improves with RF-IEF, but does not yet match that of NuTrea. Note, the values in parentheses are standard deviations across 5 runs.\n| Models         |   ReaRev   | NuTrea (Ours) |\n|----------------|:----------:|:-------------:|\n| without RF-IEF | 74.2 (1.4) |   75.5 (1.1)  |\n| with RF-IEF    | 74.6 (0.8) |   76.3 (1.4)  |\n\n&nbsp;\n\n### Q4. The performance-#layer curves of NuTrea with and without the Backup step.\nWe have added the performance-#layer curve figure in the attached PDF file above in the \"Author Rebuttal by Authors\" thread. The figures report the WebQuestionsSP F1 score of our NuTrea with and without the Backup module. We observed that the model with Backup consistently outperforms its counterpart. Also, the model without Backup does generally improve with more GNN layers, but NuTrea without Backup reached the highest score with only 2 layers.\n\n"}]

Author rebuttal:
We thank all five reviewers for their strong support and constructive comments on our work. We are glad that the reviewers found our work promising and interesting. Our responses for all the reviewers' questions are provided below. Please go over our responses and let us know if there are issues that are yet unresolved. Attached is a PDF file containing the figure that answers Q4 of reviewer 5UYV.

Meta-review: After extensive discussion between authors and reviewers
about the core contributions of the paper, most of the
reviewers' concerns were addressed by the authors. All
reviewers reflected this in their rating -- except for
reviewer jrbk (borderline reject) who states that they are
fine with accepting the paper if the authors incorporate the
discussion on openreview into the camera ready.

In making a decision on this paper, I see the main issue as
the evaluation of the backup mechanism. Most of the
discussion was about this mechanism and the relevant
baselines.

Backup allows models to leverage bidirectional information
(or global context), enabling them to distinguish entities
with similar paths. There is prior work that utilizes
bidirectional information, i.e., prior work with a similar
high-level idea.  However, what seems to be novel about this
submission is the way that bi-directional information is
incorporated for enhanced path searching (by gradually
expanding the subgraph and sequentially updating nodes).
The intuition is that paths are an effective representation
of the semantics of the question and process the KG in
alignment with the question.  This makes enriched context
available during the search for the answer nodes.

The authors helpfully explain in which
scenarios their proposed method is unlikely to result
in improvements: "easier" questions that can be answered
without taking into account broader graph context and/or
that are located "close" to the starting node.

The authors also provide extensive discussion of ReaRev and
quite a few experimental results for the comparison between
ReaRev and their method.  This additional material persuaded
me that the proposed method is novel compared to
prior work.
Decision: Accept (poster)