# Learning to Transpile AMR into SPARQL

Mihaela Bornea♣ , Ramon Fernandez Astudillo♣, Tahira Naseem, Nandana
Mihindukulasooriya
Ibrahim Abdelaziz, Pavan Kapanipathi, Radu Florian Salim Roukos
IBM Research AI
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
{nandana.m<EMAIL_ADDRESS>
{kapanipa, raduf<EMAIL_ADDRESS>
###### Abstract

We propose a transition-based system to transpile Abstract Meaning
Representation (AMR) into SPARQL for Knowledge Base Question Answering (KBQA).
This allows us to delegate part of the semantic representation to a strongly
pre-trained semantic parser, while learning transpiling with small amount of
paired data. We depart from recent work relating AMR and SPARQL constructs,
but rather than applying a set of rules, we teach a BART model to selectively
use these relations. Further, we avoid explicitly encoding AMR but rather
encode the parser state in the attention mechanism of BART, following recent
semantic parsing works. The resulting model is simple, provides supporting
text for its decisions, and outperforms recent approaches in KBQA across two
knowledge bases: DBPedia (LC-QuAD 1.0, QALD-9) and Wikidata (WebQSP, SWQ-WD).

††$\clubsuit$ These authors contributed equally to this work

##  1 Introduction

The task of Question Answering over Knowledge Bases (KBQA) Zou et al. (2014);
Vakulenko et al. (2019); Diefenbach et al. (2020) consists in finding the
answer to natural questions by retrieving the information contained in a
Knowledge Graph (KG). Compared to other automatic QA tasks, such as reading
comprehension Rajpurkar et al. (2018); Kwiatkowski et al. (2019); Clark et al.
(2020), KBQA has the advantage of producing answers backed by structured
repositories of information, offering strong factual accuracy guarantees.
Solving KBQA amounts to transforming a natural language question into some
programming language, usually a query language such as SQL or SPARQL. It is
thus considered a form of executable semantic parsing. We illustrate the KBQA
task in Figure 1.

PREFIX dbr:http://dbpedia.org/resource/PREFIX
dbo:http://dbpedia.org/ontology/PREFIX dbp:http://dbpedia.org/property/SELECT
DISTINCT  ?s WHERE {?i <dbp:state> <dbr:Maharashtra>.?i <dbo:sport> ?s.}
Figure 1: SPARQL graph for the question Name some sports played in
institutions of Maharashtra?.  ?s is the  unknown variable (related to sports)
and  ?i is an  intermediate variable (related to institution), needed to
relate the unknown with the  KG entity (Maharashtra).  Q. Name some  sports
played in the  institutions of Maharashtra ?SPARQL GraphAMR Graph?s?i Maha-
rashtra
statesportname-01sportimperativeyousomeplay-01institutionstatename"Maharashtra"
“http://dbpedia .org/resource /Maharashtra"
ARG1modeARG0modARG1-oflocationspossnamewikiop1(b)(e)(d)unknown variablesKG
entitiesintermediate variables(a)(b)(c)(d)(e)(f)(g)(h)$<$node$>$amr-
unknown?s$<$node$>$imperative$<$node$>$?smodeARG1have-degree-91amr-
unknown$<$node$>$?sARG1ARG5$<$node$>$weblink$<$node$>$…$<$node$>$wiki$<$node$>$$<$node$>$?i(aligned
to a Noun)$<$node$>$have-degree-91have-
quant-91$<$node$>$$<$node$>$?i$<$node$>$?i$<$node$>$?iARG2ARG1-of:time Figure
2:  (Left) Rules used to align AMR with SPARQL. Matching AMR subgraph patterns
(a-h) are assigned SPARQL constructs (variables, entities). For example rule
(b) identifies AMR node ‘sport’ as unknown variable because it is the object
(arg1) of an ‘imperative’ statement. This is a significantly reduced subset of
the rules in Kapanipathi et al. (2021). Further, some of the rules (e-h for
intermediate variables) are not deterministically applied but must be instead
chosen by the model. (Right) Examples applying hard rules (b) and (d) and an
optional rule (e). Dashed links represent alignments between AMR and SPARQL.

While some large KBQA datasets exist Yu et al. (2018), the amount of paired
examples, i.e. aligned natural language and query language pairs, is generally
scarce Trivedi et al. (2017); Usbeck et al. (2017). Furthermore, human
language exhibits large variability, and obtaining enough training pairs for
specific domains or infrequent natural language formulations requires large
annotation investments. Often, real world implementations of KBQA end up
containing a number of domain specific hand-crafted rules that can be costly
to maintain and expand. The need to manipulate a formal representation with
only a few examples, makes this task harder to learn compared to other QA
tasks.

In order to mitigate the data availability problem Kapanipathi et al. (2021)
proposed to delegate part of the task to an Abstract Meaning Representation
(AMR) parse that incorporates additional semantic information. This work
identifies associations between certain AMR nodes and SPARQL entities and
variables. Unfortunately, these AMR to SPARQL mappings are imperfect,
suffering from low coverage and granularity mismatch. Another concern with
AMR-based approaches is the encoding of the AMR itself which implies an
additional learning burden.

To address these limitations, in this work we propose a new approach to
leverage AMR parsing for KBQA that learns to transpile AMR into the SPARQL
query language. The contributions can be summarized as follows

  * •

We develop a state machine and an oracle that transpiles AMR into SPARQL and
we learn to imitate this oracle with BART Lewis et al. (2019) for KBQA tasks.

  * •

This oracle leverages known relations (i.e. similarities) between AMR and
SPARQL Kapanipathi et al. (2021), but rather than applying them
deterministically as in prior work, we teach the model when to use them.

  * •

We show that it is not necessary to encode AMR directly, but rather encoding
the transpiler state through attention masking as in Fernandez Astudillo et
al. (2020) suffices.

  * •

The resulting transpiler improves upon recent KBQA approaches across Dbpedia
and Wikidata. It outperforms Kapanipathi et al. (2021), by $10$ points on
LcQuAD 1.0 and matches it on QALD-9, while being simpler and exploiting
similar inductive biases. It also outperforms Neelam et al. (2021b), by $2$
points on WebQSP-WD and $4$ points on SWQ-WD.

##  2 AMR to SPARQL Machine and Oracle

Here we show how transition-based parsing can be used to traspile AMR to
SPARQL.

###  2.1 A Transition-based Transpiler

$w$:NamesomesportsplayedininstitutionsofMaharashtra?$g$:n/name-01imperatives/sporty/yous2/somep/play-01i/institutions1/state"http://dbpedia.org/resource/Maharashtra"name"Maharashtra"ARG0ARG1ARG1-ofwikilocationpossnamemodmodeop1locationCityhomeTownstatepopulationTotalbirthPlace
Maha- rashtra SELECT REDUCEBART decoderBART encoderName some sports played in
institutions of  Maharashtra ?Path Stack:Supporting Text:$a$: Actions:$s$:
SPARQL:s1 i p  ss1 ii p ss1 ii p si p  s sports played institutions
Maharashtrainstitutions Maharashtrasports played
institutionsSELECTREDUCEstatesportCLOSESELECT DISTINCT  ?s WHERE {?i
<dbp:state> <dbr:Maharashtra>.?i <dbo:sport> ?s.} Figure 3: Top-left: LC-QuAD
train sentence $w$: Name some sports played in institutions of Maharashtra?
aligned to its AMR graph $g$ (system input) and $3$ relevant subgraphs
identified by applying Figure 2 (c, d, e):  unknown variable (imperative
root),  (optional) secondary variable (entity-adjacent nominal),  linked
entity (wiki). Top-right: time-step 3 of decoding of same sentence indicating
AMR/KG-based constrained decoding and attention masking. Bottom box: Full
oracle for same sentence including implicit machine state defined by the AMR
path stack, explicit machine state defined by the supporting text, oracle
action sequence $a$ and resulting SPARQL $s$ (system output).

The objective is to learn to predict the SPARQL query $s$ corresponding to the
natural language question $w$, by transforming its AMR parse $g$.

At its core, a transition-based transpiler learns to predict a sequence of
actions $a$ that applied to a parameter-less state machine acting on $g$
yields $s$.

$s=M(a,g).$ (1)

The sequence of actions is given by a rule-based oracle that, given the
original question $w$, its AMR $g$ and the gold SPARQL $s$, yields the action
sequence.

$a=O(s,g,w).$ (2)

The oracle, detailed in Section 2.2, requires alignments between the AMR $g$
and SPARQL $s$ graphs but it is only needed to generate training samples
$(w,g,a)\sim\mathcal{D}$, through following procedure:

  * •

draw sentence and SPARQL train pair $(w,s)$ from a KBQA training corpus

  * •

parse $w$ into its AMR graph $g$111Throughout this work we always use the APT
parser Zhou et al. (2021a) to obtain AMR graphs.

  * •

obtain oracle sequence $a=O(s,g,w)$

With these, one can use the oracle as a teacher to train a sequence to
sequence model, e.g. BART Lewis et al. (2020), with a conventional cross
entropy loss

$\hat{\theta}=\arg\max_{\theta}\\{\mathbb{E}_{(w,g,a)\sim\mathcal{D}}\\{\log
p(a\mid w,g;\theta)\\}\\}.$ (3)

At test time, we predict the SPARQL as $\hat{s}=M(\hat{a},g)$, where $g$ is
obtained by parsing $w$ and $\hat{a}$ is obtained with conventional decoding.

$\hat{a}=\arg\max_{a}\\{p(a\mid w,g;\theta)\\}$ (4)

It is important to note that the use of a state machine generates a strong
inductive bias, imposing some specific way in which the sequence to sequence
problem can be solved. In this case we leverage the bias to make the
transpiler aware of AMR path information, but it comes at the penalty of not
fully being able to recover all SPARQL queries i.e. for some queries.

$s\neq M(O(s,g,w),g)$ (5)

This is analyzed in Section 6.

###  2.2 KBQA Oracle and Machine

This section describes how to formulate the state machine $s=M(a,g)$ and
oracle $a=O(s,g,w)$. The basic idea is that given alignments between AMR and
SPARQL graphs, as depicted in Figure 2 (right), it is possible to sequentially
proceed over a subset of paths in the AMR graph and transform them into
components of the SPARQL query, as shown in Figure 3 (bottom).

Initially, all AMR paths to be processed are put in a stack, Figure 3 (bottom
left). At each time step one of the following actions is chosen by the oracle

  * •

{SELECT, ASK, COUNT}: Generate the query header from a closed vocabulary

  * •

<KG relation>: Produce the KG relation for path at the top of the stack and
REDUCE

  * •

REDUCE: Pop path at the top of the stack without predicting any KG relation.

  * •

{CLOSE}: Close the machine

All actions are special symbols added to BART’s vocabulary with the exception
of KG relations, which allows free text generation. The stack initially
contains all AMR paths between entities in the KG ( green) and the unknown
variable in the query ( red) and optional paths involving secondary variables
( blue), if there are any in the AMR. As long as all the AMR subgraphs
matching SPARQL components are present in $g$, the transpiling oracle is able
to generate SPARQL queries with any number of entities and with the presence
of secondary variables i.e. multi-hop questions222Section 6 for an empirical
analysis of oracle coverage in KBQA datasets.. The REDUCE action allows the
oracle to ignore a given AMR path, which in practice controls the application
of rules (e-h). This is useful to compensate for false positive cases where
this rule generates non-existing secondary unknowns.

As an example: In Figure 3, the path at the top of the stack is [s1 i p s].
This path is determined by the alignment of the unknown variable s in the AMR
to the SPARQL projected variable ?s and the alignment of the subgraph s1 to
the entity Maharashtra (rules b, d). Since there is no gold SPARQL triple
connecting ?s and Maharashtra, the action for this path is REDUCE. For the
second AMR path [s1 i], there is a gold SPARQL triple matching the entity
Maharashtra and an intermediate SPARQL variable ?i (obtained by rule e) thus
the action for this path is the KG relation state.

One fundamental advantage of the proposed approach, is that by construction it
aligns sentence $w$, AMR $g$ and SPARQL $s$. This information can be used
during decoding to restrict the output vocabulary of $p(a\mid w)$. For
example, we can enforce header and closing operations only on a full and empty
stack respectively. Further, we can also query the KG with nodes involved in
the path on the top of the stack, to restrict the possible relations to
predict. For example in Figure 3, bottom, to predict the KG relation state we
restrict it to incoming or outgoing KG relations of the node s1, Maharashtra.
Finally, we also obtain textual cues to predict the KG relation, see
Supporting Text in Figure 3. In Section 3 we describe how textual cues are
incorporated into the model, allowing to avoid encoding AMR explicitly.

##  3 BART Transpiler with Inductive Bias

We parametrize $p(a\mid w,g;\theta)$ with a modified BART model Lewis et al.
(2019), but the approach is applicable to sequence-to-sequence Transformers
Vaswani et al. (2017). We dynamically mask cross-attention to encode the
transpiler state, described in Section 2.2. We also dynamically masking of the
output vocabulary to force the decoder to generate only the valid actions for
every state.

###  3.1 Encoding AMR through Transpiler State

In order to encode both sentence $w$ and AMR $g$ in $p(a\mid w,g;\theta)$ one
simple option could be to concatenate both $w$ and $g$ as inputs to BART.
Given the quadratic cost of Transformer’s attention, the large size of AMRs
and the redundancies between $w$ and $g$ this is likely too expensive.

Our model does not need to encode the entire AMR. It suffices to encode the
parser state in the cross-attention heads of the Transformer. Unlike prior
work Fernandez Astudillo et al. (2020); Zhou et al. (2021a, b), our transpiler
stack does not contain the question words directly but contains AMR paths
which we use to represent the transpiler state. A key element is the alignment
between the AMR nodes and words in the question, which allows us to identify
the supporting text for every path.

For example, in Figure 3, top-right we show the BART decoder at the third
decoding step where the path at the top of the stack is [s1 i]. The supporting
text for this path is $institutions~{}Maharashtra$.

The encoder takes as input the question and we dedicate some heads to attend
to the words in the supporting text for the path at the top of the stack.

These structured head weights are given by

$W^{\mbox{cross-att}}_{it}\propto e^{\frac{1}{d}(K\cdot
h^{w}_{i})^{T}\cdot(Q\cdot h^{a}_{t})+m_{2}(a_{<t},w,g)_{i}}$ (6)

where $h^{w}_{i}$ and $h^{a}_{t}$ are encoder and decoder representations for
$i^{th}$ word and $t^{th}$ prediction, and $Q$, $K$, $d$ are query, value and
scaling weights. $m_{2}()_{i}$ masks $h^{w}_{i}$ unless it is aligned to the
path of $g$ for which we are going to predict relation at step $t$.

Using the additional supporting text for every transpiler decision, helps the
explainability of the model decisions, but also plays an important role in
performance, as shown in Section 6.

###  3.2 Constrained Decoding

We use the state machine described in Section 2.2 to forbid certain actions at
each time step $t$ through

$p(a_{t}\mid a_{<t},w,g;\theta)\propto e^{f(a_{<t},w,\theta)+m(a_{<t},w,g)}$
(7)

where $f(a_{<t},w)$ is the output layer of BART without the softmax and
$m(a_{<t},w,g)$ is a state-machine dependent mask that is set to $-\infty$ to
forbid actions. $m()$ is a deterministic function of the input sentence $w$,
its AMR $g$ and action history $a_{<t}$ until step $t-1$.

For the proposed model, masking is used to perform header actions only at the
beginning of the action sequence and closing on an empty stack. In addition,
when the AMR path at the top of the stack contains entity nodes, the KG is
queried and the mask is set to restrict the actions to the appropriate KG
relations. We show such an example in the BART decoder in Figure 3, top-right,
where the actions are restricted to the KG relations for the entity
$Maharashtra$. The relation’s prefix333PREFIX dbo:
http://dbpedia.org/ontology/, PREFIX dbp: http://dbpedia.org/property/  and
direction is also obtained in this process.

These constrains are applied at decoding time only. As shown in the Section 4,
constrained decoding has a fundamental effect on performance.

##  4 Experimental Setup

###  4.1 Datasets

We evaluated our system on two knowledge graphs: DBpedia and Wikidata. For
DBpedia we used the LC-QuAD 1.0 and QALD-9 datasets following the partitions
in Kapanipathi et al. (2021). For Wikidata we used the SWQ-WD and WebQSP-WD
datasets with splits from Neelam et al. (2021b). As in prior work, we report
the Macro F1 score comparing the gold answers to the answers that TransQA
generates when executing its predicted SPARQL. We compute the F1 score for
every question and we report the average over all questions.

#### LC-QuAD 1.0

Trivedi et al. (2017) contains 4,000 questions for training and 1,000
questions for test, created from templates. We tune the hyper parameters of
our model on a random sample of 200 questions from the training set. LC-QuAD
1.0 predominantly focuses on multi-relational questions, aggregation (e.g.
COUNT) and simple questions. Although Lc-QuAD has quantitative questions, the
KG contains relations that can answer these queries without the need for
specific SPARQL constructs e.g. largestCity.

#### QALD-9

Usbeck et al. (2017) has 408 training and 150 test questions concerning
DBpedia. We created a randomly chosen set of 98 questions as development set.
QALD-9 contains more complex queries than LC-QuAD 1.0 including quantitative
questions, time constructs and other.

#### SWQ-WD

Diefenbach et al. (2017) is a KBQA dataset adapted to Wikidata with 14,894
train and 5,622 test examples. We held out 200 examples from the train set for
development. This dataset contains simple queries, with only one relation.

#### WebQSP-WD

Sorokin and Gurevych (2018) has 2,880 train and 1,033 test set questions based
on Wikidata. It includes more complex queries, often involving more than one
relation.

###  4.2 TransQA Model and Training Setup

The model, henceforth referred to as TransQA, uses a modified BART Lewis et
al. (2020) implemented in Wolf et al. (2020) to parameterize $f(a_{<t},w)$ and
trained to learn to imitate the oracle. We implement constrained decoding at
test time and parser state encoding by masking $8/16$ cross-attention heads
both at train and test time, see Section 3 for details.

For LC-QuAD 1.0 the model was trained with the LC-QuAD 1.0 train questions for
13 epochs and using a learning rate of $5\times 10^{-5}$. The QALD-9 model is
trained with both LC-QuAD 1.0 and QALD-9 training examples. We upsample the
QALD-9 5 times to balance between the two datasets and we trained the model
for 16 epochs using a learning rate of $4\times 10^{-5}$. For SWQ-WD we used
its train set and trained the system for 9 epochs with learning rate $5\times
10^{-5}$. WebQSP-WD does not provide SPARQL queries and we use a combination
of LC-QuAD 2.0 Dubey et al. (2019) and SWQ-WD to train the system. LC-QuAD 2.0
Dubey et al. (2019) is a template-based dataset based on Wikidata. It has some
known quality issues Diomedi and Hogan (2022) and does not have a baseline to
compare against. Therefore, we used its training data only to build our
models. From LC-QuAD 2.0, we use only training examples with direct relations.
The final train set contains 12,900 LC-QuAD 2.0 and 14,693 SWQ-WD examples. We
trained the system for 5 epochs with learning rate $5\times 10^{-5}$.

For all models we set the max input sequence length to $64$ tokens, max target
sequence length to $32$ tokens and beam size to $4$. We used the Adam
optimizer with standard parameters and trained on a V100 Nvidia GPU. All
hyper-parameters were determined based on the dev set F1 score. The number of
epochs and learning rate we determined from ranges $[3,18]$ and
$[10^{-5},10^{-4}]$ respectively.

###  4.3 AMR Parsing and Entity Linking

We used the Action Pointer Transformer (APT) transition-based AMR parser Zhou
et al. (2021a) which provides alignments between AMR graph nodes and surface
tokens. The model was trained combining AMR3.0 with the QALD-9-AMR train
dataset Lee et al. (2021) to adapt it to the question domain444AMR train has
no overlap with QALD-9 dev or test.. Although AMR graphs can include entity
linking, BLINK Wu et al. (2020) was also applied as a post-processing stage to
AMR parsing. We run BLINK separately and then attach the :wiki edge to the
most suitable node in the AMR. Linking the AMR nodes to KG entities is
attained by matching the span of text aligned to a subgraph with the mention
via a greedy set of checks. Attachment to conventional named entities is
attempted first. Edit distance and fuzzy match search are also used to find a
suitable alignment.

The rule (e) in Figure 2 requires Part of Speech tagging for which we use
Spacy.

See Section 2.2 for information on how alignments are used to determine parser
state. The same mechanism is used to produce the oracle action sequences for
training.

##  5 Comparison with Related Work

| EL | RL | SI | LCQ1 | Q9 | WQSP | SWQ
---|---|---|---|---|---|---|---
NSQA Kapanipathi et al. (2021) | BLINK | BERT | rules | 44.5555The relation linking method GenRel Rossiello et al. (2021) reports $59.6$ F1 result in LC-QuAD1.0 when combined with NSQA, without specifying the integration details. | 30.9 | - | -
EDGQA Hu et al. (2021) | Ensemb. | BERT | rules | 53.1 | 32.0 | - | -
STaG-QA (Ravishankar et al., 2021) | BLINK | - | BERT | 51.4 | - | - | *66footnotemark: 6
SYGMA Neelam et al. (2021a) | BLINK | BERT | rules | 47.0 | 29.0 | 31.0 | 44.0
Seq2Seq | BLINK | - | BART | 20.5 | 22.6 | 30.3 | 50.3
TransQA | BLINK | - | BART | 54.5 | 31.4 | 33.0 | 48.1
Table 1: TransQA comparison with other recent KBQA approaches. Including Entity Linking (EL), Relation Linking (RL) and the SPARQL inference (SI) components. TransQA uses a single module for relation linking and SPARQL inference. Macro F1 scores for SPARQL results on the test set to LC-QuAD1.0 (LCQ1), QALD-9 (Q9), WebQSP-WD (WQSP), SWQ-WD (SWQ)  |  | LC-QuAD 1.0 | QALD-9
---|---|---|---
AMR parsing† | Entity Linking | Oracle (F1) | TransQA (F1) | Oracle (F1) | TransQA (F1)
APT | BLINK | 68.7 | 47.4 | 67.0 | 53.6
APT | Gold | 78.7 | 63.1 | 77.5 | 58.6
Table 2: Oracle and TransQA performances as well as effect of gold Entity Linking, measured by macro F1 of SPARQL results on the dev set of LC-QuAD 1.0 and QALD-9. Oracle performance with gold Entity Linking can be seen as reflecting transpiler coverage i.e. how much of the SPARLQ patterns are captured and an approximate upper bound for TransQA performance. †Note that entity Linking is part of AMR but is separated here for clarity. | LC-QuAD 1.0 | QALD-9
---|---|---
TransQA mask $8$ heads | 56.5 | 53.6
TransQA no mask | 52.1 | 49.5
TransQA mask 5 heads | 56.0 | 50.5
TransQA mask 12 heads | 55.8 | 52.8
TransQA no constrained decoding using KG | 46.3 | 41.8
Table 3: Ablation study measuring the effect of constrained decoding and
parser state encoding on BART. Measured by the macro F1 of SPARQL results on
the dev set.

We compare TransQA against a number of recent neural approaches for KBQA
trained in comparable conditions. We excluded approaches using gold entity
linking and relation linking Banerjee et al. (2022) since, both tasks have a
strong impact in performance. We also include a BART baseline to control for
the effect of pre-trained models since most other recent methods use BERT
Devlin et al. (2019).

NSQA Kapanipathi et al. (2021) Uses a pipeline of AMR parsing
(StackTransformer Fernandez Astudillo et al. (2020)), entity linking (BLINK Wu
et al. (2020)), rule-based transpiling of AMR, BERT based Relation linking
(SemRel Naseem et al. (2021)) and a final integrator module producing SPARQL
from competing hypothesis. TransQA, borrows a significantly reduced amount of
rules from this work for alignment, but replaces this pipeline by a simpler
learnt transpilation of AMR using a modified BART Lewis et al. (2020).

SYGMA Neelam et al. (2021b) is another multi-component pipeline with final
integrator and using the same entity and relation linking as NSQA. It
leverages lambda calculus as intermediate representation and features improved
handling of temporal relations and an extended experimental setup.

EDGQA Hu et al. (2021) proposes a custom Entity Description Graph (EDG) to
represent the structure of complex questions, rather than relying on
established formalisms such as AMR. It applies multiple decomposition rules
and BERT-based re-scoring to produce SPARQL. It also uses an ensemble of three
entity linking tools: Dexter Ceccarelli et al. (2014), EARL Dubey et al.
(2018) and Falcon Sakor et al. (2019) as one entity retriever. EDGQA also uses
a relation linker trained with LC-QuAD 1.0 and QALD-9.

STaG-QA (Ravishankar et al., 2021) is a two stage text to SPARQL system that
first generates a query skeleton learned end-to-end with a BERT model and then
performs beam search to find optimal grounding of the skeleton into a target
KG. The paper also provides results for silver data training which are left-
out for comparability purposes.

seq2seq baseline. BART has been shown to excel at semantic parsing with no
need for special parametrization Chen et al. (2020); Bevilacqua et al. (2021).
We train BART to produce the SPARQL directly from input sentences and we use
the same training data as for TransQA. To incorporate Entity Linking, we
concatenate BLINK entity linking to the input to teach BART to copy it into
the target.

Table 1 displays the comparison with related work. The proposed TransQA
outperforms all methods both on DBpedia and Wikidata, with two notable
exceptions. EDGE-QA has better results in QALD-9 but it utilizes likely
stronger entity linking. Also the simple BART baseline outperforms all other
methods in simple web questions, while lagging clearly behind in LC-QuAD and
QALD, which are more complex. This result may be explained by a trade-off
between inductive bias and expressiveness, helping TransQA for complex
grammars but limiting performance in simple cases. It is also worth noting
that TransQA outperforms NSQA and SYGMA, while exploiting similar inductive
bias and being simpler666STaG-QA SWQ-WD experiments use a self-selected data
split, with smaller, non comparable test set.

##  6 Oracle and State Encoding Analysis

Table 2 reports oracle performance for BLINK and gold entity linking on the
development set of LC-QuAD 1.0 and QALD and system performance of a TransQA
trained with the corresponding oracle. Note that both results still use real
AMR parses from APT Zhou et al. (2021a). The gold entity linking oracle
results measures how well oracle covers the distribution of SPARQL patterns
found in these datasets and can be seen as an approximate upper bound for the
performance of TransQA. Overal, correcting for entity linking errors, oracle
performance reaches $78.7$ and $77.5$ for LC-QuAD 1.0 and QALD respectively.
Although much higher than any reported system performance, this indicates
oracles do not cover all possible SPARQL patterns, supporting the idea that a
transpiling oracle implies a trade-off between inductive bias and
expressiveness. Overall, this trade-off has strong positive effect if we
compare the TransQA and BART seq2seq baseline results in Table 2.

Entity linking errors are shown to have a strong influence in TransQA,
reducing performance by at least $5$ points for both LC-QuAD 1.0 and QALD.
Other systems can also be expected to have a similar dependency since they can
not recover for a linking error, making systems harder to compare.

Table 3 ablates the inductive bias introduced in BART through attention and
output vocabulary modifications described in Section 3. Masking cross-
attention to attend to the sentence words aligned to and AMR path, and thus to
a potential triple, improves performance by around $4$ points for an optimal
number of $8$ modified attention heads, selected on the dev set. Constrained
decoding has an even larger effect of $10$ points on LC-QuAD 1.0 and $12$
points on QALD-9, sensibly larger than the effect of gold entity linking. This
is likely because of the large reduction on possible decoding options. Another
possibility is that it provides some visibility into the KG structure. This is
particularly important to compensate for the fact that the knowledge graphs
lack a schema, i.e. it is unclear if relations expressing one particular
category will exist. Constrained decoding provides thus a limited view into
the database, informing future decisions of the transpiler.

##  7 Prior Work

See Section 5, for descriptions of NSQA Kapanipathi et al. (2021), SYGMA
Neelam et al. (2021a), EDGQA Hu et al. (2021) and STaG-QA Ravishankar et al.
(2021). Both NSQA and SYGMA are relatively similar and involve a combination
of multiple systems including entity and relation linking an integration
module and a large set of rules. They can thus be seen as having the strongest
inductive bias, exploiting human knowledge at the cost of complexity and
limited expressiveness. The BART seq2seq baseline can be seen as the other
extreme, lacking any inductive bias and clearly suffering when fine-tuned to
complex grammars and limited amounts of train data. TransQA can be seen as
finding the optimum between these two, needing only a small sub-set of NSQA’s
rules, and introducing the inductive bias through oracle imitation, attention
masking and constrained decoding. The resulting system, is clearly simpler
than NSQA and SYGMA but has higher performance in all corpora tested and,
unlike BART, it does not suffer with more complex grammars.

EDGQA and other recent approaches such as Saparina and Osokin (2021),
transform natural language into intermediate question decomposition
representations that are not well known and require of a number of rules. Here
we employ AMR, a well established formalism with abundant training data in
various languages and robust high performant parsers e.g. Lee et al. (2021).
TransQA is threfore likely to generalize better while requiring a small set of
rules. Though EDGQA outperforms TransQA on QALD, it has to be taken into
account that this model uses a ensemble of models for entity linking that
likely provides extra performance.

Though less performant than TransQA, STAG-QA is also a relatively simple
approach using two stages of inference. The latter step needs however the beam
search which can be computationally prohibitive in datasets with more complex
structure than LC-QUAD.

GGNN Sorokin and Gurevych (2018) is a baseline system on WebQSP-WD dataset
which specifically models the graph structure of the semantic parse using
graph convolution. Is also defines a custom semantic parsing formalism to
construct semantic graph representation from the train examples in WebQSP-WD.
Our system outperforms GGNN by $7$ F1 points on the WebQSP-WD dataset.

More recently Banerjee et al. (2022), propose a seq2seq baseline with T5 where
they assume the gold entities and relations have been provided. As shown in
our experiments in Table 2, gold entity linking alone causes a large
difference in performance. This work is therefore not comparable with the rest
of the approaches here considered.

##  8 Conclusions

We introduced TransQA, an approach for KBQA that transpiles a well established
semantic representation, AMR, obtained from an off-the-shelf parser, into
SPARQL. This transpiling operation is learned through a transition-based
approach, resulting on a simpler and more performant system than prior
approaches leveraging AMR. Empirical results on KBQA corpora show that TransQA
finds an optimal trade-off between inductive bias and expressiveness,
outperforming both sequence to sequence models and more complex pipeline
systems incorporating a large number of rules. Ablation analysis shows that
encoding of the transpiler state in the self-attention mechanism and
constrained decoding yields clear gains, while removing the need to encode
AMR. Finally oracle analysis reveals that the proposed transition system is
able to attain high coverage across datasets while remaining simple.

##  9 Limitations

The current implementation has several limitation which can be addressed in
future work. We show in section 5.1 that our technique is severely impacted by
the quality of relation linking. This also complicates comparison across
systems. Furthermore, we still rely on a small set of rules, see Figure 2 and
do not support type constraints and other SPARQL constructs. This limits the
coverage of the model, see Table 3, although overall still leads to
competitive results and theoretical limits given by the oracle are close to
$80$ F1. For Wikidata our system uses direct KB relations and the current
implementation can not predict statements and reified relations.

Regarding data and compute requirements, the model is trained with small data-
sets by leveraging transfer learning from BART and a pre-trained semantic
parser. Both models have multiple other purposes, amortizing the overall cost.

The experiments were carried out for the English language but there are little
language-specific choices. Both multi-lingual versions of BART Liu et al.
(2020) and cross-lingual transition AMR parsers Lee et al. (2021) exist and
some of the corpora like QALD have multi-lingual versions. Though limited by
the amount of data available and alignment quality, the approach could be in
principle extended to other languages without drastic changes being needed.

## References

  * Banerjee et al. (2022) Debayan Banerjee, Pranav Ajit Nair, Jivat Neet Kaur, Ricardo Usbeck, and Chris Biemann. 2022.  Modern baselines for sparql semantic parsing.  _arXiv preprint arXiv:2204.12793_.
  * Bevilacqua et al. (2021) Michele Bevilacqua, Rexhina Blloshmi, and Roberto Navigli. 2021.  One spring to rule them both: Symmetric amr semantic parsing and generation without a complex pipeline.
  * Ceccarelli et al. (2014) Diego Ceccarelli, Claudio Lucchese, Salvatore Orlando, R. Perego, and Salvatore Trani. 2014.  Dexter 2.0 - an open source tool for semantically enriching data.  In _SEMWEB_.
  * Chen et al. (2020) Xilun Chen, Asish Ghoshal, Yashar Mehdad, Luke Zettlemoyer, and Sonal Gupta. 2020\.  Low-resource domain adaptation for compositional task-oriented semantic parsing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5090–5100, Online. Association for Computational Linguistics.
  * Clark et al. (2020) Jonathan H. Clark, Eunsol Choi, Michael Collins, Dan Garrette, Tom Kwiatkowski, Vitaly Nikolaev, and Jennimaria Palomaki. 2020.  TyDi QA: A benchmark for information-seeking question answering in typologically diverse languages.  _Transactions of the Association for Computational Linguistics_ , 8:454–470.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _ArXiv_ , abs/1810.04805.
  * Diefenbach et al. (2020) Dennis Diefenbach, Andreas Both, Kamal Deep Singh, and Pierre Maret. 2020.  Towards a question answering system over the semantic web.  _Semantic Web_ , 11:421–439.
  * Diefenbach et al. (2017) Dennis Diefenbach, Thomas Pellissier Tanon, Kamal Deep Singh, and Pierre Maret. 2017\.  Question answering benchmarks for wikidata.  In _SEMWEB_.
  * Diomedi and Hogan (2022) Daniel Diomedi and Aidan Hogan. 2022.  Entity linking and filling for question answering over knowledge graphs.
  * Dubey et al. (2019) Mohnish Dubey, Debayan Banerjee, Abdelrahman Abdelkawi, and Jens Lehmann. 2019.  Lc-quad 2.0: A large dataset for complex question answering over wikidata and dbpedia.  In _Proceedings of the 18th International Semantic Web Conference (ISWC)_. Springer.
  * Dubey et al. (2018) Mohnish Dubey, Debayan Banerjee, Debanjan Chaudhuri, and Jens Lehmann. 2018.  Earl: Joint entity and relation linking for question answering over knowledge graphs.
  * Fernandez Astudillo et al. (2020) Ramón Fernandez Astudillo, Miguel Ballesteros, Tahira Naseem, Austin Blodgett, and Radu Florian. 2020.  Transition-based parsing with stack-transformers.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1001–1007, Online. Association for Computational Linguistics.
  * Hu et al. (2021) Xixin Hu, Yiheng Shu, Xiang Huang, and Yuzhong Qu. 2021.  Edg-based question decomposition for complex question answering over knowledge bases.  In _The Semantic Web – ISWC 2021_ , pages 128–145, Cham. Springer International Publishing.
  * Kapanipathi et al. (2021) Pavan Kapanipathi, Ibrahim Abdelaziz, Srinivas Ravishankar, Salim Roukos, Alexander Gray, Ramón Fernandez Astudillo, Maria Chang, Cristina Cornelio, Saswati Dana, Achille Fokoue, Dinesh Garg, Alfio Gliozzo, Sairam Gurajada, Hima Karanam, Naweed Khan, Dinesh Khandelwal, Young-Suk Lee, Yunyao Li, Francois Luus, Ndivhuwo Makondo, Nandana Mihindukulasooriya, Tahira Naseem, Sumit Neelam, Lucian Popa, Revanth Gangi Reddy, Ryan Riegel, Gaetano Rossiello, Udit Sharma, G P Shrivatsa Bhargav, and Mo Yu. 2021.  Leveraging Abstract Meaning Representation for knowledge base question answering.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3884–3894, Online. Association for Computational Linguistics.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming-Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019.  Natural questions: a benchmark for question answering research.  _Transactions of the Association of Computational Linguistics_.
  * Lee et al. (2021) Young-Suk Lee, Ramon Fernandez Astudillo, Thanh Lam Hoang, Tahira Naseem, Radu Florian, and Salim Roukos. 2021.  Maximum bayes smatch ensemble distillation for amr parsing.  _arXiv preprint arXiv:2112.07790_.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Naseem et al. (2021) Tahira Naseem, Srinivas Ravishankar, Nandana Mihindukulasooriya, Ibrahim Abdelaziz, Young-Suk Lee, Pavan Kapanipathi, Salim Roukos, Alfio Gliozzo, and Alexander Gray. 2021.  A semantics-aware transformer model of relation linking for knowledge base question answering.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 256–262, Online. Association for Computational Linguistics.
  * Neelam et al. (2021a) Sumit Neelam, Udit Sharma, Hima Karanam, Shajith Ikbal, Pavan Kapanipathi, Ibrahim Abdelaziz, Nandana Mihindukulasooriya, Young-Suk Lee, Santosh Srivastava, Cezar Pendus, et al. 2021a.  Sygma: System for generalizable modular question answering overknowledge bases.  _arXiv preprint arXiv:2109.13430_.
  * Neelam et al. (2021b) Sumit Neelam, Udit Sharma, Hima P. Karanam, Shajith Ikbal, Pavan Kapanipathi, I. Abdelaziz, Nandana Mihindukulasooriya, Young-Suk Lee, Santosh Srivastava, Cezar Pendus, Saswati Dana, Dinesh Garg, Achille Fokoue, G P Shrivatsa Bhargav, Dinesh Khandelwal, Srinivas Ravishankar, Sairam Gurajada, Maria Chang, Rosario A. Uceda-Sosa, Salim Roukos, Alexander G. Gray, Guilherme LimaRyan Riegel, Francois P. S. Luus, and L. V. Subramaniam. 2021b.  Sygma: System for generalizable modular question answering overknowledge bases.  _ArXiv_ , abs/2109.13430.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for squad.  In _ACL_.
  * Ravishankar et al. (2021) Srinivas Ravishankar, June Thai, Ibrahim Abdelaziz, Nandana Mihindukulasooriya, Tahira Naseem, Pavan Kapanipathi, Gaetano Rossiello, and Achille Fokoue. 2021\.  A two-stage approach towards generalization in knowledge base question answering.
  * Rossiello et al. (2021) Gaetano Rossiello, Nandana Mihindukulasooriya, I. Abdelaziz, Mihaela A. Bornea, A. Gliozzo, Tahira Naseem, and Pavan Kapanipathi. 2021.  Generative relation linking for question answering over knowledge bases.  _ArXiv_ , abs/2108.07337.
  * Sakor et al. (2019) Ahmad Sakor, Isaiah Onando Mulang’, Kuldeep Singh, Saeedeh Shekarpour, Maria Esther Vidal, Jens Lehmann, and Sören Auer. 2019.  Old is gold: Linguistic driven approach for entity and relation linking of short text.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2336–2346, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Saparina and Osokin (2021) Irina Saparina and Anton Osokin. 2021.  Sparqling database queries from intermediate question decompositions.  In _EMNLP_.
  * Sorokin and Gurevych (2018) Daniil Sorokin and Iryna Gurevych. 2018.  Modeling semantics with gated graph neural networks for knowledge base question answering.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 3306–3317, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Trivedi et al. (2017) Priyansh Trivedi, Gaurav Maheshwari, Mohnish Dubey, and Jens Lehmann. 2017.  Lc-quad: A corpus for complex question answering over knowledge graphs.
  * Usbeck et al. (2017) Ricardo Usbeck, Axel-Cyrille Ngonga Ngomo, Bastian Haarmann, Anastasia Krithara, Michael Röder, and Giulio Napolitano. 2017.  7th open challenge on question answering over linked data (qald-7).  In _Semantic Web Challenges_ , pages 59–69, Cham. Springer International Publishing.
  * Vakulenko et al. (2019) Svitlana Vakulenko, Javier David Fernandez Garcia, Axel Polleres, M. de Rijke, and Michael Cochez. 2019.  Message passing for complex question answering over knowledge graphs.  _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Wu et al. (2020) Ledell Yu Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020.  Scalable zero-shot entity linking with dense entity retrieval.  In _EMNLP_.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai-Chou Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Z Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. 2018.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  In _EMNLP_.
  * Zhou et al. (2021a) Jiawei Zhou, Tahira Naseem, Ramón Fernandez Astudillo, and Radu Florian. 2021a.  AMR parsing with action-pointer transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5585–5598, Online. Association for Computational Linguistics.
  * Zhou et al. (2021b) Jiawei Zhou, Tahira Naseem, Ramón Fernandez Astudillo, Young-Suk Lee, Radu Florian, and Salim Roukos. 2021b.  Structure-aware fine-tuning of sequence-to-sequence transformers for transition-based AMR parsing.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6279–6290, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Zou et al. (2014) Lei Zou, Ruizhe Huang, Haixun Wang, Jeffrey Yu, Wenqiang He, and Dongyan Zhao. 2014\.  Natural language question answering over rdf - a graph data driven approach.  _Proceedings of the ACM SIGMOD International Conference on Management of Data_.