# Measuring Network Resilience via Geospatial Knowledge Graph: a Case Study of
the US Multi-Commodity Flow Network

Jinmeng Rao  Geospatial Data Science Lab, University of Wisconsin-
MadisonMadisonUSA<EMAIL_ADDRESS>,  Song Gao  Geospatial Data Science
Lab, University of Wisconsin-MadisonMadisonUSA<EMAIL_ADDRESS>,  Michelle
Miller  Center for Integrated Agricultural Systems, University of Wisconsin-
MadisonMadisonUSA<EMAIL_ADDRESS>and  Alfonso Morales  Department of
Planning and Landscape Architecture, University of Wisconsin-MadisonMadisonUSA
<EMAIL_ADDRESS>
(2022)

###### Abstract.

Quantifying the resilience in the food system is important for food security
issues. In this work, we present a geospatial knowledge graph (GeoKG)-based
method for measuring the resilience of a multi-commodity flow network.
Specifically, we develop a CFS-GeoKG ontology to describe geospatial semantics
of a multi-commodity flow network comprehensively, and design resilience
metrics that measure the node-level and network-level dependence of single-
sourcing, distant, or non-adjacent suppliers/customers in food supply chains.
We conduct a case study of the US state-level agricultural multi-commodity
flow network with hierarchical commodity types. The results indicate that, by
leveraging GeoKG, our method supports measuring both node-level and network-
level resilience across space and over time and also helps discover
concentration patterns of agricultural resources in the spatial network at
different geographic scales.

resilience, knowledge graph, smart foodsheds, food supply chain, commodity
flow survey

††journalyear: 2022††booktitle: The 1st ACM SIGSPATIAL International Workshop
on Geospatial Knowledge Graphs (GeoKG ’22), November 1, 2022, Seattle, WA,
USA††copyright: none††ccs: Networks Network measurement††ccs: Networks Network
reliability

##  1\. Introduction

According to the State of Food Security and Nutrition in the World report in
2022 by the Food and Agriculture Organization of the United Nations (FAO,
IFAD, UNICEF, WFP and WHO, 2022), the number of people affected by global
hunger has increased by 150 million since the COVID-19 outbreak, reaching 828
million in 2021. 11.7% of the global population faced food insecurity
nowadays. Resilient and sustainable food supply chain networks may benefit the
production, delivery, and consumption of agricultural products, thereby
showing promises in mitigating global hunger and critical for regional and
global food security (Suweis et al., 2015; Miller, 2021; Karakoc and Konar,
2021). However, food supply chain networks involve multidimensional
interactions and complex decisions. All participants in supply chains contend
with diverse food demands, transportation time and cost, sales strategy,
natural conditions, etc. This means that understanding supply chain resilience
is a grand challenge (Chaturvedi et al., 2014; Yadav et al., 2022).

Recently, different measures have been proposed in complex (spatial) networks
(Gao et al., 2016; Dey et al., 2019; Li, 2016) and applied in understanding
the resilience and the resilience-efficiency trade-off in the global food
trade network (Fair et al., 2017; Puma, 2019; Tu et al., 2019; Karakoc and
Konar, 2021). For example, Fair et al. (2017) built a dynamic model of the
global wheat trade network and explored the resilience of the network to
targeted attacks on edges. Tu et al. (2019) measured the connectivity,
structure, and modularity of a global food trade network and investigated
their association with the resilience of the network. Karakoc and Konar (2021)
studied topological and weighted resilience and efficiency metrics and
proposed a complex network framework for evaluating the trade-off between
efficiency and resilience of food trade networks. However, it is still hard to
comprehensively assess the food system resilience with complex
multidimensional information (e.g., multiple commodity types, suppliers and
customers, geographic proximity, and at different scales). With the recent
advances in geospatial knowledge graphs (GeoKG) (Janowicz et al., 2022; Mai et
al., 2020), the importance of spatial concepts (e.g., the scale of geographic
entities and spatial dependence) has been addressed in knowledge discovery,
semantic reasoning, etc. Such concepts can be integrated with food systems
(Hollander et al., 2020) to help decision makers understand and improve the
structure and resilience of food supply chain networks, thereby safeguarding
local, regional, and global food security.

In this work, we present a novel method for measuring network resilience via
GeoKG and apply it for understanding the node-level and network-level
resilience of the US agricultural multi-commodity flow network at different
geographic scales. By leveraging GeoKG, we are able to integrate several
factors into resilience metrics (i.e., commodity value, supplier or customer
commodity diversity, average transport miles, and geographic adjacency) and
comprehensively measure the single-sourcing dependence of suppliers,
customers, and commodity types as well as the geographic proximity and
adjacency (spatial dependence) in the network. Such comprehensive resilience
metrics may not only allow a good assessment of the resilience of the entire
network or the nodes themselves when facing disruption risks, but also help us
discover trends in the dispersion or concentration of agricultural resources
at different geographic scales.

The remainder of the paper is organized as follows: In Section 2, we first
introduce the ontology design of CFS-GeoKG, a geographic knowledge graph for
storing and querying geospatial semantics of multi-commodity flow data. We
then propose two resilience metrics for the comprehensive measurement of node-
level and network-level resilience via CFS-GeoKG which considers commodity
value and diversity, average transport miles, and geographic adjacency. In
Section 3, we report and discuss the results from a case study of the US
agricultural multi-commodity flow network using our proposed methods. In
section 4, we discuss the limits associated with our data source and metric
design, and we summarize corresponding future research directions. Finally, in
Section 5, we conclude this work and outline future works.

##  2\. Methods

In this section, we first present a GeoKG ontology design: CFS-GeoKG, which
describes the US multi-commodity flow network based on the US Commodity Flow
Survey (CFS) data111https://www.census.gov/programs-surveys/cfs.html. Then we
introduce several network resilience evaluation metrics based on the designed
CFS-GeoKG, which comprehensively consider multi-dimensional semantics such as
supplier/customer/commodity diversity, commodity value, geographic adjacency,
and average transport mileage in the measurements. We also demonstrate how to
calculate the proposed resilience metrics via CFS-GeoKG using the SPARQL
query.

Figure 1. The ontology design of CFS-GeoKG.

###  2.1. CFS-GeoKG Ontology

We design an ontology “CFS-GeoKG” to comprehensively describe geospatial
semantic information in the US multi-commodity flow network. The CFS-GeoKG
ontology is designed to 1) define hierarchical geographical entities and their
relations in the multi-commodity flow network; 2) describe hierarchical multi-
type commodity flows and their properties; and 3) support network resilience
measurement; and 4) link out to and reuse existing semantic ontology design
patterns for better interoperability or interlinking existing Linked data and
other Web resources (Janowicz et al., 2014). Figure 1 presents the ontology
design of CFS-GeoKG. Each commodity flow in the network belongs to the class
cfs:CFObject, which has several essential properties: cfs:CFValue, the total
value ($ millions) of the commodity flow; cfs:AvgMileage, the average
transport mileage (miles) of the commodity flow; time:year from the Time
Ontology in OWL222https://www.w3.org/TR/owl-time/, the year of the commodity
flow; cfs:CFCode, the commodity code such as Standard Classification of
Transported Goods (SCTG, described by
cfs:SCTG)333https://bhs.econ.census.gov/bhsphpext/brdsearch/scs_code.html or
North American Industry Classification System (NAICS, described by
cfs:NAICS)444https://www.census.gov/naics/. Note that the hierarchical
structure in commodity types, if exists, can be preserved by adding
corresponding data properties to cfs:CFCode; and kwg-
ont:Region555https://stko-kwg.geog.ucsb.edu/lod/ontology#Region from the
KnowWhereGraph ontology (Janowicz et al., 2022), describing hierarchical
geographical entities involved in CFS data such as the geographical or
administrative origin and destination (e.g., state, region, division, and CFS
area) of a commodity flow. Note that the concepts of regions and divisions we
employ in the paper are from the Geographic Levels defined by the US Census
Bureau666{https://www.census.gov/programs-surveys/economic-census/guidance-
geographies/levels.html}.

For each agricultural commodity code (i.e., each food type), if available, we
also link it to its corresponding FoodOn ontology class (Dooley et al., 2018)
to add more food information. To support the storage and query of geospatial
information, we utilize the GeoSPARQL developed by Open Geospatial Consortium
(OGC) that defines a vocabulary for representing geospatial data in resource
description framework (RDF) (Battle and Kolas, 2011). Specifically, kwg-
ont:Region has either a geo:Geometry or a geo:GeometryCollection depending on
its geographical type. For example, a state has one geo:Geometry that
describes its boundary, area, etc.; a region or division contains multiple
states, therefore having a geo:GeometryCollection containing multiple
geo:Geometry. We also utilize the GeoNames ontology (Vatant and Wick, 2006)
(e.g., assigning a gn:Feature for each kwg-ont:Region) to support the storage
and query of geographical names, geoID, geographical types, etc. Note that we
did not show all CFS attributes in Figure 1 for simplicity. In fact, more
properties such as the total weight of the commodity flow (e.g., cfs:CFWeight)
can be described in the CFS-GeoKG. With the CFS-GeoKG, we are able to annotate
the geographical entities and commodity flow entities as well as their
properties and relations in the semantic network, which lays the foundation
for a comprehensive network resilience assessments.

###  2.2. Network Resilience Metrics

We measure resilience in a multi-commodity flow network mainly based on the
extent of dependence on Single-Sourcing Dependence (Swift, 1995; Namdar et
al., 2018). According to different levels of resilience measurement, we
propose two types of resilience metrics: node-level resilience and network-
level resilience. Generally speaking, a node (e.g., a state) is less resilient
if it tends to rely more on a single supplier, a single customer, or a single
commodity type. This is because a centralized risk due to single sourcing
leads to a lower fault tolerance. When the largest supplier or customer of the
node is removed from the supply chain, or the commodity on which the node is
most reliant are out of supply or unsalable, the resulting impact could be
devastating for the node’s economy (e.g., disruption risks (Kamalahmadi and
Parast, 2017)). Also, from a geographical perspective, a node is less
resilient if it tends to rely more on geographically distant or non-adjacent
suppliers or customers. Generally, longer distance transport not only
increases transport costs, but also increases transport risks (Inman and
Blumenfeld, 2014). We therefore define the resilience of a node as a
comprehensive measurement of the dependence on multiple suppliers/customers,
commodity types and geographic proximity. In Table 1, we list four factors
that affects node-level resilience: Commodity Value (CV),
Supplier/Customer/Commodity Diversity (SCCD), Average Transport Mileage (ATM),
and Geographic Adjacency (GA). We summarize a bottom-top calculation of node-
level resilience in four steps (Figure 2):

Table 1. Factors affecting node resilience. Factors |  Description
---|---
CV |  The value of a commodity flow
SCCD |  The diversity of suppliers/customers/commodities
ATM |  The average transport mileage of a commodity flow
GA |  The geographic adjacency between the origin and destination of a commodity flow

Combining CV with ATM and GA: In order to reflect the average transport
mileage and geographic adjacency information in commodity values, we combine
them using the following formula:

(1) $V^{\prime}_{(i\rightarrow j,c)}=V_{(i\rightarrow
j,c)}\times\alpha_{(i\rightarrow j,c)}\times\beta_{(i,j)}$

where $V_{(i\rightarrow j,c)}$ and $\alpha_{(i\rightarrow j,c)}$ denote the
value and the factor for average transport mileage of the flow with commodity
type $c$ from node $i$ to node $j$, respectively. We set
$\alpha_{(i\rightarrow j,c)}=1$ when ATM is shorter than 1 mile, otherwise we
set $\alpha_{(i\rightarrow j,c)}$ to be the square root of ATM;
$\beta_{(i,j)}$ denotes the factor for geographic adjacency between node $i$
and node $j$. $\beta_{(i,j)}=0.9$ if node $i$ and node $j$ is geographically
adjacent, otherwise $\beta_{(i,j)}=1$. Note that these factors can be modified
based on domain knowledge. Also, in the CFS-GeoKG, CV and ATM can be queried
via cfs:CFValue and cfs:AvgMileage, and GA can be queried using geo:ehMeet,
the ’Meet’ relation in Egenhofer’s Topological Relation Family between regions
(Egenhofer, 2010) and implemented by GeoSPARQL.

Figure 2. A conceptual graph showing the bottom-up node-level export
resilience calculation.

Measuring Single-Supplier/Customer Dependence: By leveraging Shannon entropy
(Shannon, 1948), we measure the single-supplier/customer dependence of a node
for each commodity type (here we measure the single-customer dependence as an
example):

(2) $H_{(i,c)}=-\sum_{j}p_{j}\log_{2}p_{j}$ (3)
$D_{(i,c)}=2^{-H_{(i,c)}}=\prod_{j}p_{j}^{p_{j}}$

Where $H_{(i,c)}$ denotes the Shannon entropy of the value distribution of
commodity type $c$ centered to node $i$; $p_{j}=V^{\prime}_{(i\rightarrow
j,c)}/\sum_{j}V^{\prime}_{(i\rightarrow j,c)}$ is the normalized commodity
value; $D_{(i,c)}$ denotes the extent of single-customer dependence of node
$i$ on commodity type $c$ (i.e., a weighted geometric mean of normalized
commodity value distribution (Nelson, 2017)). A larger $D_{(i,c)}$ implies a
higher single-customer dependence.

Measuring Single-Commodity-Type Dependence: Building upon the single-customer
dependence, we further measure the single-commodity-type dependence of a node.
Due to the hierarchy of commodity types (e.g., ’SCTG 02100 Wheat’ is a
subClass of ’SCTG 02 Cereal Grains’) as shown in Figure 2, we first calculate
the single-commodity-type dependence for each aggregated commodity type (e.g.,
CFCode A and B), and then we calculate the overall single-commodity-type
dependence of a node:

(4) $D_{(i,A)}=\prod_{c\in A}p_{(i,c)}^{p_{(i,c)}}$ (5) $D_{i}=\prod_{A\in
Agg}p_{(i,A)}^{p_{(i,A)}}$

where $D_{i}$ is the overall single-commodity-type dependence of node $i$;
$Agg$ is a set of aggregated commodity types;
$p_{(i,A)}=V^{\prime}_{(i,A)}/\sum_{A\in Agg}V^{\prime}_{(i,A)}$ is the
normalized value of $V^{\prime}_{(i,A)}=D_{(i,A)}\sum_{c\in
A}V^{\prime}_{(i,c)}$, which is the value of aggregated commodity $A$
reflecting single-commodity-type dependence; $D_{(i,A)}$ is the single-
commodity-type dependence of the aggregated commodity type $A$;
$p_{(i,c)}=V^{\prime}_{(i,c)}/\sum_{c\in A}V^{\prime}_{(i,c)}$ is the
normalized value of
$V^{\prime}_{(i,c)}=D_{(i,c)}\sum_{j}V^{\prime}_{(i\rightarrow j,c)}$, which
is the value of commodity type $c$ reflecting single-customer dependence. Note
that in the CFS-GeoKG, aggregated commodity types are stored as data
properties of cfs:CFCode.

Measuring Node-Level Resilience: Eventually, we get a node-level resilience
$R_{i}$ that comprehensively measures the single-supplier/customer dependence,
single-commodity-type dependence, transport distance, and geographic adjacency
of the node $i$:

(6) $R_{i}=1-D_{i}\frac{\sum_{A\in Agg}V^{\prime}_{(i,A)}}{V^{\prime}_{i}}$

where $V^{\prime}_{i}=\sum_{A\in Agg}\sum_{c\in
A}\sum_{j}V^{\prime}_{(i\rightarrow j,c)}$ denotes the total commodity value
of node $i$ combined with average transport miles and geography adjacency
information. The higher the $R_{i}$, the less dependent node $i$ is on single
or geographically distant/non-adjacent supplier/customer or single commodity
type, thus the higher the resilience. Depending on commodity in-flows and out-
flows, we can calculate the node-level import resilience $R^{in}_{i}$ and
export resilience $R^{out}_{i}$ of node $i$, respectively.

Measuring Network-Level Resilience: It is natural to consider how to extend
this node-level resilience metric to a network-level resilience metric.
Likewise, network-level resilience also relies on CV, SCCD, ATM, and GA. We
refer to the concept of a food trade network resilience proposed by (Karakoc
and Konar, 2021), where they define network resilience as the resilience to
the targeted attack on the major exporter with the most mass supply. We modify
this definition as “the resilience to the targeted attack on the most
influential importer/exporter in the multi-commodity network”. Here the most
influential importer/exporter may: 1) have a very high total commodity flow
value (combined with transport mileage and geographic adjacency) in the multi-
commodity network; and 2) have very deep integration with the multi-commodity
network (i.e., the business and value are deeply linked to most of the
commodity types). The most influential importer/exporter does the best of the
two aspects combined, therefore attacking such an importer/exporter will have
a huge impact on the vulnerability of entire network. By capturing such a
change in the network, we are able to measure the network-level resilience as
below:

(7) $R_{net}=1-max(I_{i})$ (8)
$I_{i}=\frac{R_{i}V^{\prime}_{i}}{\sum_{i}R_{i}V^{\prime}_{i}}$

where $R_{i}$ denotes the node-level resilience of node $i$, which also
implies the extent of integration between node $i$ and the network;
$V^{\prime}_{i}$ denotes the total commodity value of node $i$ described in
formula (6). $I_{i}$ thereby reflects the overall influence of node $i$ on the
entire network. Likewise, we can calculate the network-level import resilience
$R^{in}_{net}$ and export resilience $R^{out}_{net}$ using commodity in-flows
and out-flows, respectively.

Resilience Computation via CFS-GeoKG using SPASQL: The aforementioned
resilience metrics can be defined and implemented as on-demand query functions
(with the prefix cfsf:) (Regalia et al., 2016), which are used to calculate
the node-level and network-level resilience scores via the CFS-GeoKG. Here we
give an example of how to retrieve the top-10 states with the highest node-
level export resilience in 2017 using the predefined
cfsf:node_export_resilience query function. This function takes a kwg-
ont:Region node and three other parameters (i.e., year, ATM and GA factors) as
inputs, and return the export resilience of that node as the output:

⬇

1cfsf:node_export_resilience (node: kwg-ont:Region,

2year: time:year,

3atm: xsd:string,

4ga: xsd:double): xsd:double

The example SPARQL query is as below:

⬇

1SELECT ?state (cfsf:node_export_resilience(?state, 2017, ’sqrt’, 0.9)

2AS ?expResilience)

3WHERE {

4?state rdf:type kwg-ont:Region.

5?state cfs:hasGnFeature ?gnFeature.

6?gnFeature gn:featureCode ’ADM1’.

7}

8ORDER BY DESC(?expResilience)

9LIMIT 10

where ?state denotes the nodes in the CFS-GeoKG we select. We first select the
state-level kwg-ont:Region nodes with gn:featureCode as ’ADM1’, and then we
calculate their node-level export resilience via the
cfsf:node_export_resilience query function, where we set year as 2017 for
calculating resilience scores in 2017, atm as ’sqrt’ to use the square root of
ATM for the $\alpha$ factor reflecting average transport mileage, and ga as
0.9 for the $\beta$ factor reflecting geographic adjacency. Lastly, we sort
the results based on the calculated export resilience in descending order and
return the first 10 results. Similarly, the node-level import resilience and
the network-level resilience measures can also be calculated on-the-fly with
predefined SPARQL query functions. The key consideration of on-demand
computation vs. pre-compute is because we can calibrate the parameters and
update resilience scores to see the changes, especially when we want to
investigate how a change in node property would affect the network resilience.

##  3\. Results

Figure 3. The visualization of the state-level resilience and influence in the agricultural multi-commodity flow network in the U.S. in 2012 and 2017. A-B: node-level import and export resilience of each state in 2012; C-D: node-level import and export resilience of each state in 2017; E-F: import and export influence of each state on the network in 2012; C-D: import and export influence of each state on the network in 2017. Table 2. List of agricultural commodity types in SCTG. Code |  Description
---|---
01 |  Live Animals and Fish
02 |  Cereal Grains (including seed)
03 |  Agricultural Products Except for Animal Feed, Cereal Grains, and Forage Products
04 |  Animal Feed, Eggs, Honey, and Other Products of Animal Origin
05 |  Meat, Poultry, Fish, Seafood, and Their Preparations
06 |  Milled Grain Products and Preparations, and Bakery Products
07 |  Other Prepared Foodstuffs, Fats and Oils
08 |  Alcoholic Beverages and Denatured Alcohol

In our experiments, we utilize the CFS-GeoKG and designed metrics to measure
both node-level resilience and network-level resilience of the US Multi-
Commodity Flow Network. The CFS is conducted every five years by the Bureau of
Transportation Statistics (BTS) and the U.S. Census Bureau. CFS provides
comprehensive data of domestic freight shipments including commodity type,
value, weight, distance shipped, origin and destination, etc. from national-
level to state-level. As an example, we focus on the agricultural multi-
commodity flows in 2012 and 2017 at differential geographical scales by
extracting the data with SCTG code from 01 to 08 (details are listed in Table
2) and under different geographical units (i.e., state, division, and region).
Following the SCTG Commodity Code
List777https://bhs.econ.census.gov/bhsphpext/brdsearch/scs_code.html, we
further aggregate code 01-05 (i.e., Agriculture Products and Fish, denoted as
$A$) and 06-08 (i.e., Grains and Alcohol, denoted as $B$) to preserve the
hierarchical commodity type structure. After loading CFS data into CFS-GeoKG,
there are 64 geographical unit entities, including 51 states, 9 divisions, and
4 regions. There are also 3,381 commodity flow entities covering different
geographical units, years, and commodity types. The state-level agricultural
commodity flows in 2012 and 2017 are visualized on the map in Figure 4,
respectively. The flow width reflects the total commodity value of each flow.

Figure 4. The state-level agricultural multi-commodity flow network in the
U.S. in 2012 (left) and 2017 (right).

We first calculate the node-level import resilience $R^{in}_{i}$ and export
resilience $R^{out}_{i}$ for each node $i$ at the state level in the
agricultural multi-commodity flow network and list the top-10 resilient states
in 2017 in Table 3. Then we calculate both import influence $I^{in}_{i}$ and
export influence $I^{out}_{i}$ to the network for each node $i$ and list the
top-10 states in 2017 in Table 4. The ranking in Table 3 differs from Table 4
as node-level resilience mainly reflects the resilience of the nodes
themselves to single-source dependence, transport distance, and geographic
adjacency, which does not necessarily rely on their total commodity values,
while the influence on the network relies heavily on the total commodity value
of the nodes. In Figure 3, we further visualize all the node-level import and
export resilience for each state in 2012 and 2017 as well as the import and
export influence of each state to the entire food flow spatial network in 2012
and 2017. Darker color represents higher resilience or influence. We can
observe from the figure that the east-coast states, west-cost states, and mid-
west states have higher node-level resilience than other areas. This might be
because they have larger and wider supply chains for purchasing and selling
agricultural products, making them less dependent on single-sourcing
suppliers/customers or geographic constraints, and thereby more resilient to
disruption risks. Moreover, we can observe that many top agricultural-
producing states such as California, Texas, and mid-west states have high
import and export influence on the network, indicating that they contribute
high agricultural commodity values, practice robust supply chain strategies,
and play important roles in the US food system. In Figure 5, we also show how
the ranking of each state’s import or export influence on the entire network
changes from 2012 to 2017. It shows that the rankings of both the most
influential and less influential states in the network do not change a lot,
and most of the states in the middle may change rankings within a certain
range, which also matches our intuition.

Table 3. The Top-10 states with highest node-level import or export resilience in the network in 2017. State |  $R^{in}_{i}$ |  State |  $R^{out}_{i}$
---|---|---|---
North Carolina |  0.968 |  California |  0.970
Kentucky |  0.965 |  Georgia |  0.963
Georgia |  0.965 |  Nebraska |  0.962
Pennsylvania |  0.965 |  Kentucky |  0.959
California |  0.964 |  North Carolina |  0.959
Michigan |  0.963 |  Pennsylvania |  0.959
Florida |  0.961 |  South Carolina |  0.957
Illinois |  0.959 |  Alabama |  0.956
Texas |  0.956 |  Minnesota |  0.955
Virginia |  0.954 |  Tennessee |  0.953
Table 4. The Top-10 most influential states to the import or export of the network in 2017. State |  $I^{in}_{i}$ |  State |  $I^{out}_{i}$
---|---|---|---
California |  0.108 |  California |  0.132
Texas |  0.104 |  Texas |  0.096
Florida |  0.062 |  Illinois |  0.061
Louisiana |  0.057 |  Iowa |  0.058
Washington |  0.057 |  Nebraska |  0.045
Pennsylvania |  0.053 |  Minnesota |  0.040
Georgia |  0.052 |  Georgia |  0.039
New York |  0.048 |  Ohio |  0.038
Illinois |  0.046 |  Missouri |  0.032
Ohio |  0.034 |  Kansas |  0.031
Figure 5. The ranking changes of import influence (left) and export influence
(right) of states to the multi-commodity flow network between 2012 and 2017.

We then measure the network-level resilience in 2012 and 2017. Here we report
the overall network-level resilience $R_{net}=(R^{in}_{net}+R^{out}_{net})/2$
at three different geographic scales in Table 5. The results show that the
overall resilience of the agricultural commodity flow network at the state
level increased from $0.867$ in 2012 to $0.880$ in 2017 by $1.5\%$, indicating
the success in creating a more resilient interstate supply chain in
agriculture. At the division level and the region level, however, the overall
resilience in 2017 drops a bit (by 0.4% and 6.7%) from 2012. This might be
related to the increasing concentration of agricultural resources in some
specific areas. For example, the Pacific Division, which is the division with
the most agricultural influence based on CFS data, continued to increase its
import and export influence by 11.6% and 8.6% in 2017 compared to 2012,
respectively, which leads to a drop in network-level resilience in 2017. This
observation suggests that we may need to pay attention to the increasing
concentration of agricultural resources on a larger geographic scale and take
corresponding measures to enhance the resilience of the overall agricultural
supply chain network (Karakoc et al., 2022).

Table 5. The overall network-level resilience in 2012 and 2017 at different geographical scales. Scale |  $R^{2012}_{net}$ |  $R^{2017}_{net}$ |  Changes (%)
---|---|---|---
State |  0.867 |  0.880 |  +1.5%
Division |  0.766 |  0.763 |  -0.4%
Region |  0.647 |  0.604 |  -6.7%

##  4\. discussion

We acknowledge several limits associated with the current data source, each of
which prompts further research directions. First, utilizing CFS data requires
that we represent both food imported internationally as well as that sourced
within the U.S. The easily identifiable CFS state-level unit of analysis
requires further unpacking to reveal geographically relevant foodsheds. This
is to say that corn and wheat produced in the Great Plains cover parts of
several states with broadly similar production characteristics and relatively
few transportation modes to reach processing centers and markets. Likewise,
substate regions, such as cranberry production in Wisconsin or Maine, or the
vast variety of products (and associated ecological problems) of California’s
central valley demand resilience analysis at an appropriate geographic scale.

Second, regions are differentially diverse in their agricultural products and
processing activities. This suggests the need for an index of product
diversity, benchmarked on other USDA measures, such as the typical consumer
market basket or NIH food pyramids to deepen our understanding of regional
resilience. Clearly, such measures should account for locally available
processing to transform commodities into consumable products.

Third, we need to further address the notion of value. Ease of analysis
compels us to reduce the value to a dollar amount associated with the CFS.
This reductionist approach allows for ease of analysis and the ability to
advance an initial understanding of resilience. A deeper understanding would
follow by developing indices of value that relate to nutrition, energy use, or
multifunctionality of specific crops.

Fourth, our measure of resilience is robust given our operationalization of
data and objectives, but, again, a deeper understanding of resilience will
include a variety of social factors. The notion of resilience can be
operationalized at various scales – individuals, households, communities,
ecoregions, etc.. A regional operationalization of resilience would embrace
multiple public and private sector organizations and the demographically
diverse population associated with a region or state. Characteristics of
resilience could include communicative connectivity, flexibility, and
fungibility of organizational units and subunits such that resilience is
represented as a socio-technical characteristic of a region (Woods, 2019;
Morales, 2021). Another promising approach to resilience is to examine the
relative resilience of the distribution infrastructure associated with
geography, and further, we could specify the relative resilience of particular
subpopulations, such as those in prisons, schools, hospitals, or non-consumer
food systems.

Lastly, our point in this paper is to introduce a GeoKG-based approach to
measuring resilience and demonstrate its use. Thus, our results, while real
and meaningful, are mainly for reference since the parameters we use have not
been thoroughly investigated or calibrated. More appropriate parameter
settings will alter the resilience measurement results. So, one more task
would be to refine our parameter settings and metric designs by exploring the
aforementioned research directions.

##  5\. Conclusion

In this paper, we introduce a GeoKG-based approach to measuring the resilience
of a multi-commodity flow network. The case study shows that CFS-GeoKG well
supports the storage and query of geospatial semantics of a multi-commodity
flow network, thereby supporting the comprehensive measurement of single-
sourcing dependence and the dependence of geographically distant or non-
adjacent suppliers/customers. The CFS-GeoKG well supports measuring both node-
level and network-level resilience and also helps discover the increasing
concentration of agricultural resources at higher geographical levels,
implying broad application prospects of GeoKG in multi-commodity supply chain
networks.

Our future works include linking CFS-GeoKG to more existing semantic
ontologies for better scalability, understanding geographically relevant
foodsheds, product diversity index and their relationships with resilience,
integrating more promising data and factors into resilience metrics such as
social economics, energy use, and nutrition profiles, and investigating the
trade-off between resilience and efficiency of multi-commodity flow networks
to discover better food supply chain network structures.

###### Acknowledgements.

We acknowledge the funding support from the National Science Foundation funded
AI institute [Grant No. 2112606] for Intelligent Cyberinfrastructure with
Computational Learning in the Environment (ICICLE). Any opinions, findings,
and conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the funder(s). We also
thank Matthew Lange from IC-FOODS for his valuable suggestions.

## References

  * (1)
  * Battle and Kolas (2011) Robert Battle and Dave Kolas. 2011.  GeoSPARQL: enabling a geospatial semantic web.  _Semantic Web Journal_ 3, 4 (2011), 355–370.
  * Chaturvedi et al. (2014) Alok Chaturvedi, Brian Armstrong, and Rashmi Chaturvedi. 2014\.  Securing the food supply chain: understanding complex interdependence through agent-based simulation.  _Health and Technology_ 4, 2 (2014), 159–169.
  * Dey et al. (2019) Asim K Dey, Yulia R Gel, and H Vincent Poor. 2019.  What network motifs tell us about resilience and reliability of complex networks.  _Proceedings of the National Academy of Sciences_ 116, 39 (2019), 19368–19373.
  * Dooley et al. (2018) Damion M Dooley, Emma J Griffiths, Gurinder S Gosal, Pier L Buttigieg, Robert Hoehndorf, Matthew C Lange, Lynn M Schriml, Fiona SL Brinkman, and William WL Hsiao. 2018\.  FoodOn: a harmonized food ontology to increase global food traceability, quality control and data integration.  _npj Science of Food_ 2, 1 (2018), 1–10.
  * Egenhofer (2010) Max J Egenhofer. 2010\.  The family of conceptual neighborhood graphs for region-region relations. In _International Conference on Geographic Information Science_. Springer, 42–55.
  * Fair et al. (2017) Kathyrn R Fair, Chris T Bauch, and Madhur Anand. 2017\.  Dynamics of the global wheat trade network and resilience to shocks.  _Scientific reports_ 7, 1 (2017), 1–14.
  * FAO, IFAD, UNICEF, WFP and WHO (2022) FAO, IFAD, UNICEF, WFP and WHO. 2022\.  _The State of Food Security and Nutrition in the World 2022: Repurposing food and agricultural policies to make healthy diets more affordable._ https://doi.org/10.4060/cc0639en
  * Gao et al. (2016) Jianxi Gao, Baruch Barzel, and Albert-László Barabási. 2016\.  Universal resilience patterns in complex networks.  _Nature_ 530, 7590 (2016), 307–312.
  * Hollander et al. (2020) Allan D Hollander, Casey Hoy, Patrick R Huber, Ayaz Hyder, Matthew C Lange, Angela Latham, James F Quinn, Courtney M Riggle, and Thomas P Tomich. 2020.  Toward smart foodsheds: Using stakeholder engagement to improve informatics frameworks for regional food systems.  _Annals of the American Association of Geographers_ 110, 2 (2020), 535–546.
  * Inman and Blumenfeld (2014) Robert R Inman and Dennis E Blumenfeld. 2014.  Product complexity and supply chain design.  _International Journal of Production Research_ 52, 7 (2014), 1956–1969.
  * Janowicz et al. (2014) Krzysztof Janowicz, Pascal Hitzler, Benjamin Adams, Dave Kolas, and Charles Vardeman II. 2014\.  Five stars of linked data vocabulary use.  _Semantic Web_ 5, 3 (2014), 173–176.
  * Janowicz et al. (2022) Krzysztof Janowicz, Pascal Hitzler, Wenwen Li, Dean Rehberger, Mark Schildhauer, Rui Zhu, Cogan Shimizu, Colby K Fisher, Ling Cai, Gengchen Mai, et al. 2022\.  Know, Know Where, KnowWhereGraph: A densely connected, cross-domain knowledge graph and geo-enrichment service stack for applications in environmental intelligence.  _AI Magazine_ 43, 1 (2022), 30–39.
  * Kamalahmadi and Parast (2017) Masoud Kamalahmadi and Mahour Mellat Parast. 2017.  An assessment of supply chain disruption mitigation strategies.  _International Journal of Production Economics_ 184 (2017), 210–230.
  * Karakoc and Konar (2021) Deniz Berfin Karakoc and Megan Konar. 2021.  A complex network framework for the efficiency and resilience trade-off in global food trade.  _Environmental Research Letters_ 16, 10 (2021), 105003\.
  * Karakoc et al. (2022) Deniz Berfin Karakoc, Junren Wang, and Megan Konar. 2022\.  Food flows between counties in the United States from 2007 to 2017.  _Environmental Research Letters_ 17, 3 (2022), 034035\.
  * Li (2016) Daqing Li. 2016\.  Resilience of spatial networks.  In _Complex Systems and Networks_. Springer, 79–106.
  * Mai et al. (2020) Gengchen Mai, Krzysztof Janowicz, Ling Cai, Rui Zhu, Blake Regalia, Bo Yan, Meilin Shi, and Ni Lao. 2020\.  SE-KGE: A location-aware knowledge graph embedding model for geographic question answering and spatial semantic lifting.  _Transactions in GIS_ 24, 3 (2020), 623–655.
  * Miller (2021) Michelle Miller. 2021\.  Identifying Critical Thresholds for Resilient Regional Food Flows: A Case Study From the US Upper Midwest.  _Frontiers in Sustainable Food Systems_ 5 (2021), 684159.
  * Morales (2021) Alfonso Morales. 2021\.  Public marketplaces promoting resilience and sustainability.  , 6025 pages.
  * Namdar et al. (2018) Jafar Namdar, Xueping Li, Rupy Sawhney, and Ninad Pradhan. 2018\.  Supply chain resilience for single and multiple sourcing in the presence of disruption risks.  _International Journal of Production Research_ 56, 6 (2018), 2339–2360.
  * Nelson (2017) Kenric Nelson. 2017\.  Assessing probabilistic inference by comparing the generalized mean of model and source probabilities.  _Entropy_ 19, 6 (2017), 286.
  * Puma (2019) Michael J Puma. 2019\.  Resilience of the global food system.  _Nature Sustainability_ 2, 4 (2019), 260–261.
  * Regalia et al. (2016) Blake Regalia, Krzysztof Janowicz, and Song Gao. 2016\.  VOLT: a provenance-producing, transparent SPARQL proxy for the on-demand computation of linked data and its application to spatiotemporally dependent data. In _European Semantic Web Conference_. Springer, 523–538.
  * Shannon (1948) Claude Elwood Shannon. 1948\.  A mathematical theory of communication.  _The Bell system technical journal_ 27, 3 (1948), 379–423.
  * Suweis et al. (2015) Samir Suweis, Joel A Carr, Amos Maritan, Andrea Rinaldo, and Paolo D’Odorico. 2015.  Resilience and reactivity of global food security.  _Proceedings of the National Academy of Sciences_ 112, 22 (2015), 6902–6907.
  * Swift (1995) Cathy Owens Swift. 1995\.  Preferences for single sourcing and supplier selection criteria.  _Journal of Business Research_ 32, 2 (1995), 105–111.
  * Tu et al. (2019) Chengyi Tu, Samir Suweis, and Paolo D’Odorico. 2019.  Impact of globalization on the resilience and sustainability of natural resources.  _Nature Sustainability_ 2, 4 (2019), 283–289.
  * Vatant and Wick (2006) Bernard Vatant and Marc Wick. 2006.  Geonames ontology (2006).  _Online at http://www. geonames. org/ontology_ (2006).
  * Woods (2019) David D Woods. 2019\.  Essentials of resilience, revisited.  _Handbook on resilience of socio-technical systems_ (2019), 52–65.
  * Yadav et al. (2022) Vinay Surendra Yadav, AR Singh, Angappa Gunasekaran, Rakesh D Raut, and Balkrishna E Narkhede. 2022\.  A systematic literature review of the agro-food supply chain: Challenges, network design, and performance measurement perspectives.  _Sustainable Production and Consumption_ 29 (2022), 685–704.


# Translate First Reorder Later:
Leveraging Monotonicity in Semantic Parsing

Francesco Cazzaro  Equal contribution Davide Locatelli11footnotemark: 1
Ariadna Quattoni
Universitat Politècnica de Catalunya, Barcelona, Spain
{francesco.cazzaro<EMAIL_ADDRESS>Xavier Carreras
dMetrics, Brooklyn, NY

###### Abstract

Prior work in semantic parsing has shown that conventional seq2seq models fail
at compositional generalization tasks. This limitation led to a resurgence of
methods that model alignments between sentences and their corresponding
meaning representations, either implicitly through latent variables or
explicitly by taking advantage of alignment annotations. We take the second
direction and propose TPol, a two-step approach that first translates input
sentences monotonically and then reorders them to obtain the correct output.
This is achieved with a modular framework comprising a _Translator_ and a
_Reorderer_ component. We test our approach on two popular semantic parsing
datasets. Our experiments show that by means of the monotonic translations,
TPol can learn reliable lexico-logical patterns from aligned data,
significantly improving compositional generalization both over conventional
seq2seq models, as well as over a recently proposed approach that exploits
gold alignments.

##  1 Introduction

The goal of a semantic parser is to map natural language sentences (NLs) into
meaning representations (MRs). Most current semantic parsers are based on deep
sequence-to-sequence (seq2seq) approaches and presume that it is unnecessary
to model word alignments between NLs and MRs because the attention mechanism
can automatically learn the correspondences (Dong and Lapata, 2016; Jia and
Liang, 2016). However, recent work has shown that such seq2seq models find
compositional generalization challenging, i.e., they struggle to predict
unseen structures made up of components observed at training (Lake and Baroni,
2018; Finegan-Dollak et al., 2018).

This limitation motivated the resurgence of approaches that model alignments
between sentences and their corresponding MRs more similarly to classical
grammar and translation-based parsers (Herzig and Berant, 2021). Alignments
can be modeled either implicitly through latent variables (Wang et al., 2021),
or explicitly by leveraging gold alignment annotations (Shi et al., 2020; Liu
et al., 2021a). We take the second direction and exploit a recently released
multilingual dataset for semantic parsing annotated with word alignments:
GeoAligned (Locatelli and Quattoni, 2022), which augments the popular Geo
benchmark (Zelle and Mooney, 1996).

Figure 1 shows some examples of the annotations provided. One key observation
is that a significant percentage of the alignments are monotonic, i.e., they
require no reordering of the target MR (Figure 1a), as opposed to non-
monotonic alignments (Figure 1b). This suggests that learning reliable lexico-
logical translation patterns from aligned data should be possible. If there
are simple patterns, shouldn’t an ideal model be able to exploit them?

Figure 1: Examples of word alignments from the GeoAligned dataset. (a) is a
monotonic alignment (b) is non-monotonic.

With this in mind, we propose TPol, a Two-step Parsing approach that leverages
monotonic translations. TPol introduces a modular framework with two
components: a _Monotonic Translator_ and a _Reorderer_. The Translator is
trained from pairs of NLs and MRs, where the MRs have been permuted to make
them monotonically aligned. Hence, the Translator’s output will be an MR whose
order might not correspond to that of the gold truth. For this reason, the
Reorderer is trained to restore the correct order of the original MR.

Our experiments on GeoAligned demonstrate that by leveraging monotonicity,
TPol improves compositional generalization both over conventional seq2seq
parsers, as well as over models that similarly exploit alignments. Compared to
a multilingual BART model (Liu et al., 2020), TPol achieves similar
performance on the random test split ($87.5\%\rightarrow 87.3\%$) but
significantly outperforms on the compositional split: $69.4\%\rightarrow
87.8\%$. Compared to SpanBasedSP (Herzig and Berant, 2021), another recently
proposed approach that leverages alignments, TPol further improves on the
compositional splits: $74.6\%\rightarrow 87.8\%$.

Because most semantic parsing datasets do not contain alignment information,
we experiment with alignments generated automatically using the IBM models
(Brown et al., 1993). We test TPol on the popular Scan dataset (Lake and
Baroni, 2018) and show competitive results on all partitions, matching the
near-perfect performance of other models. When tested on Geo with automatic
alignments, TPol outperforms mBART on the compositional partition in English
($69.4\%\rightarrow 79\%$) and German ($56.3\%\rightarrow 60.7\%$), and
matches performance on Italian. This demonstrates that our approach fares well
even with automatic alignments and can be used on datasets that do not contain
gold annotations.

In summary the main contributions of this paper are: (1) We propose TPol, a
modular two-step approach for semantic parsing which explicitly leverages
monotonic alignments; (2) Our experiments show that TPol improves
compositional generalization without compromising overall performance; (3) We
show that even without gold alignments, TPol can achieve competitive
results.111Our code will be released upon publication.

##  2 Related Work

Recently, the semantic parsing community has raised the question of whether
current models can generalize compositionally, along with an effort to test
for it (Lake and Baroni, 2018; Finegan-Dollak et al., 2018; Kim and Linzen,
2020). The consensus is that conventional seq2seq models, while they obtain
excellent results on in-distribution test splits, struggle to generalize
compositionally (Loula et al., 2018; Keysers et al., 2020). Moreover, large
pre-trained language models have been shown not to improve compositional
generalization (Oren et al., 2020; Qiu et al., 2022b). This has prompted the
community to realize that parsers should be designed intentionally with
compositionality in mind (Weißenhorn et al., 2022). It has also been pointed
out that compositional parser architectures are often designed for synthetic
datasets and that compositionality on non-synthetic data is under-tested (Shaw
et al., 2021).

Data augmentation techniques have been proposed to improve compositional
generalization (Andreas, 2020; Yang et al., 2022; Qiu et al., 2022a), as well
as models with specialized architectures (Lake, 2019; Gordon et al., 2020).
Another strategy is to exploit some level of word alignments. In general,
there has been a resurgent interest in alignments as it has been shown that
they can be beneficial to neural models (Shi et al., 2020). It has also been
conjectured that the lack of alignment information might hamper progress in
semantic parsing (Zhang et al., 2019). As a result, the field has seen some
annotation efforts in this regard (Locatelli and Quattoni, 2022; Shi et al.,
2020).

Alignments have been modeled implicitly: Wang et al. (2021) treat alignments
as discrete structured latent variables within a neural seq2seq model,
employing a pipeline that first reorders the NL and then decodes the MR.
Explicit use of alignment information has also been explored: Herzig and
Berant (2021) use alignments and predict a span tree over the NL. Sun et al.
(2022) recently proposed an approach whereby data augmentation is done via
sub-tree substitutions using the gold alignment annotations by Herzig and
Berant (2021). In text-to-SQL, attention-based models that try to capture them
have been proposed (Lei et al., 2020; Liu et al., 2021b), as well as attempts
that try to leverage them directly (Sun et al., 2022).

Our two-step approach resembles statistical machine translation, which
decomposes the translation task into lexical translation and reordering.
Machine translation techniques have previously been applied to semantic
parsing. The first attempt was by Wong and Mooney (2006), who argued that a
parsing model can be viewed as a syntax-based translation model and used a
statistical word alignment algorithm. Later a machine translation approach was
used on the Geo dataset, obtaining what was at the time state-of-the-art
results (Andreas et al., 2013). More recently, Agarwal et al. (2020) proposed
an approach that employs machine translation as an aid to semantic parsing.

##  3 Word Alignments

This section provides a preliminary explanation of word alignments, showing
the difference between monotonic and non-monotonic alignments, and
illustrating the notion of monotonic translations.

Assume that we have a pair of sequences ${\bf x}=x_{1},\ldots,x_{n}$ and ${\bf
y}=y_{1},\ldots,y_{m}$, where $n$ and $m$ are the respective sequence lengths.
A bi-sequence is defined as the tuple $({\bf x},{\bf y})$. In our application,
${\bf x}$ is a natural language sentence, and ${\bf y}$ is its corresponding
meaning representation. For example:

${\bf x}=$ which city has the highest population density?

${\bf y}=$ answer ( largest ( density ( city ( all ) ) ) )

A bi-sequence word alignment is a set of bi-symbols $\mathcal{A}$, where each
bi-symbol defines a mapping. For instance, the bi-symbol $(x_{i},y_{j})$
aligns word $x_{i}$ to word $y_{j}$. In our example, the words "which" and
"answer" could be paired by a bi-symbol $($which, answer$)$.

If a word $x_{i}$ doesn’t align to anything in ${\bf y}$, an $\varepsilon$ is
introduced in ${\bf y}$: the resulting bi-symbol $(x_{i},\varepsilon)$
corresponds to a deletion. In our example, the word "has" in the NL can be
deleted with a bi-symbol $($has, $\varepsilon)$. Similarly, if a word $y_{j}$
is not aligned to a word in ${\bf x}$, an $\varepsilon$ is introduced in ${\bf
x}$: $(\varepsilon,y_{j})$ is an insertion. In our example, the word "all" in
the MR is inserted with the bi-symbol $(\varepsilon$, all$)$.

The bi-symbols in $\mathcal{A}$ are all one-to-one. Hence, to map a single
word to a phrase, i.e., to multiple words, it is necessary to choose a head-
word in the phrase, while the remaining words require an insertion or deletion
operation. In our example, the word "density" in the MR corresponds to
"population density" in the NL, and, if "density" is chosen as the headword in
the NL, "population" needs a deletion: the alignment will be given by the bi-
symbols $($population, $\varepsilon)$ and $($density, density$)$.222Locatelli
and Quattoni (2022) showed that annotators are consistent in the way they pick
head-words, and reported high inter-annotator agreement scores on GeoAligned.
Following this strategy, this notation can account for one-to-many and many-
to-one alignments with deletion and insertion operations.

Figure 2a shows a possible bi-sequence word alignment for the aforementioned
example. Each bi-symbol is conveniently represented by a horizontal line
connecting the words that it maps. Alignments can be monotonic or non-
monotonic. An alignment is monotonic if it does not involve any _crossing_ ,
i.e., a mapping that does not require reordering of symbols. In our example,
the alignment is non-monotonic because the bi-symbol $($city,city$)$ crosses
over others. By permuting the MR we can obtain a monotonic translation of the
NL: Figure 2b shows such permutation. The next section illustrates how the
TPol framework can take advantage of these monotonic translations.

Figure 2: (a) A possible alignment for a NL-MR pair. (b) The corresponding
monotonic translation. For simplicity, we removed the brackets and question
mark.

##  4 Translate First Reorder Later

Figure 3: The TPol parsing approach. An input sentence $\bf x$ is fed to the
_Monotonic Translator_ that predicts an intermediate monotonic MR $\bf z$.
This is in turn fed to the _Reorderer_ , which outputs the final prediction
$\bf y$.

We propose TPol, a two-step parsing approach with a modular framework made up
of two components: a _Monotonic Translator_ and a _Reorderer_. Figure 3 shows
the process by which our semantic parser takes an input sentence $\bf x$ and
predicts the corresponding meaning representation $\bf y$. In the first step,
$\bf x$ is fed to the Translator, which outputs a monotonic translation $\bf
z$. In other words, $\bf z$ is the target MR that has been permuted so that it
aligns monotonically to the input NL. Then, in a second step, $\bf z$ is fed
into the Reorderer, which is trained to place the words back into the correct
order to produce the final MR prediction $\bf y$.

The main idea behind TPol is decomposing the task into lexical translation and
reordering, with the goal of learning more reliable translation patterns. We
purport that modeling monotonic alignments eases the learning of novel pattern
combinations of seen structures, which in turn improves compositional
generalization.

###  4.1 Monotonic Translator

The Monotonic Translator is responsible for making an initial prediction of
the MR sequence, which will contain the correct symbols in monotonic order. To
create the training bi-sequences we use alignment information and permute the
gold MR sequences to obtain a monotonic mapping with the NL. As a concrete
example, consider the non-monotonic alignment in Figure 2a, and its monotonic
translation in Figure 2b.

The translation task can be formulated in various ways. In our implementation,
we work with two alternative approaches: a seq2seq Translator, and a tagger
Translator. In the seq2seq formulation, $\bf x$ is fed into an encoder
network, which produces a hidden vector. The hidden vector is in turn fed to a
decoder network which produces the output $\bf z$, i.e., the monotonically
aligned MR. This can be implemented, for example, with a BART model (Lewis et
al., 2020), which uses a bidirectional encoder and a left-to-right decoder. In
our experiments, we use the multilingual version of BART (Liu et al., 2020).
In the tagging formulation, the Translator assigns an MR word to each word in
$\bf x$, obtaining the monotonic translation $\bf z$ by explicitly aligning in
a word-by-word fashion. We implement this with a BERT model (Devlin et al.,
2019) and we use its classification head as the tagger.

A crucial difference between the seq2seq and the tagger Translator is that the
latter needs $\bf x$ and $\bf z$ to be of the same length. The seq2seq
Translator can learn to perform deletion operations from the raw NL, without
needing epsilons in the input to perform insertion operations. By contrast,
the tagger Translator needs insertion operations to be performed on $\bf x$
before it can predict $\bf z$. In general, NL sequences are significantly
longer than the MR sequences, i.e., most epsilons are in the MR sequence. In
other words, deletions are more frequent than insertions. However, for some
datasets there are alignments that contain epsilons in the NL sequence: at
prediction time we will not know where insertions might occur, and thus we
need a way to predict them. For this purpose we additionally include a model
in our processing pipeline which inserts the missing epsilons in $\bf x$ when
necessary. Similarly to Ribeiro et al. (2018) this model is a simple rule-
based system based on a list of prefix patterns compiled from the training
data.

###  4.2 Reorderer

The Reorderer module is responsible for taking the monotonic predictions of
the Translator and putting them back into the correct order to obtain the
final MR prediction. This model is trained from pairs of MR sequences $(\bf
z,\bf y)$ where the input $\bf z$ is a monotonically permuted MR and the
output $\bf y$ is the gold MR in its correct order. These training pairs can
be directly generated from the alignment annotations.

Similarly to the Translator module, the Reorderer can be implemented both as a
seq2seq model and as a tagger. In our experiments, we use multilingual BART in
the seq2seq formulation, and BERT in the tagging formulation.

##  5 Experiments

We test TPol on two semantic parsing datasets, in multiple languages, with
both gold and automatically generated word alignments. For every dataset we
evaluate on standard IID partitions as well as the more challenging
compositional partitions. We compare with competitive baselines and state-of-
the-art models that do not leverage alignments, as well as with a competing
model that does.

###  5.1 Datasets

GeoAligned (Locatelli and Quattoni, 2022) augments the popular Geo semantic
parsing benchmark (Zelle and Mooney, 1996) with word alignment annotations.
The dataset contains questions about US geography and it employs the FunQL
formalism (Kate et al., 2005). In total, there are 880 examples, all annotated
with word alignments. We evaluate on three partitions: question, query and
length. The question partition is a standard IID split where test and train
are sampled from the same distribution. The query partition, introduced by
Finegan-Dollak et al. (2018), is designed to be compositional. It ensures that
the templates of the MRs in the test set are never seen in the train. The
length partition, introduced by Herzig and Berant (2021), instead assigns the
longest sequences to the test.

The dataset comes translated in English, Italian and German, in this way we
can test our approach across different languages. For our experiments we use
the version of the dataset that does not anonymize constants: in other words,
we keep the original NL and MR sequences which include names of cities,
states, rivers and places. We follow Wang et al. (2021) in removing brackets.

ScanSP (Herzig and Berant, 2021) is a set of navigational commands presented
in natural language paired with action sequences. It is based on the Scan
original dataset by Lake and Baroni (2018), which does not contain program
MRs. Herzig and Berant (2021) used automatic translation of the action
sequences into programs to obtain a semantic parsing version of the dataset.
Besides the IID partition, we test on the compositional partitions based on
the "right" and "around right" primitives from Loula et al. (2018). ScanSP has
20,910 commands which across the splits are distributed roughly as 12,000
train, 3,000 validation and 4,000 test examples.

The ScanSP dataset does not come with alignments, therefore we employ a
statistical alignment algorithm to generate them automatically with IBM models
(Brown et al., 1993) with the GIZA++ toolkit (Och and Ney, 2003). We also
operate in the same fashion and obtain automatic alignments for GeoAligned to
compare the performance with the gold annotations.

###  5.2 Models for comparisons

LSTM. A standard seq2seq model with a bi-directional LSTM encoder and an LSTM
decoder with attention (Bahdanau et al., 2015). We use pre-trained GloVe
embeddings for the three languages: English (Pennington et al., 2014), Italian
and German (Ferreira et al., 2016).

mBART. mBART (Liu et al., 2020) is a multilingual version of BART (Lewis et
al., 2020), a seq2seq model with a Transformer-based architecture. BART models
are pre-trained through a denoising self-supervised task, and recently have
been successfully applied to parsing (Bevilacqua et al., 2021).

mT5. mT5 (Xue et al., 2021) is the multilingual version of the T5 model
(Raffel et al., 2020). It has been trained on the mC4 dataset (Xue et al.,
2021) which comprises natural text in 101 languages drawn from the public
Common Crawl web scrape. We use the _google/mt5-small_ pre-trained checkpoint
from the Transformers library (Wolf et al., 2020).

SpanBasedSP. Herzig and Berant (2021) proposed this parser that predicts a
span tree over an input utterance. The authors have provided annotated gold
trees for both Geo (in the English version), and ScanSP. We use their model
without their lexicon, as that involves some processing of the constants and
of the lexicon that would be unfair with respect to the other models.

###  5.3 Evaluation metric

To evaluate results we follow the standard practice of using exact match
accuracy where the predicted MR is counted as correct if it is exactly the
same as the gold MR.

###  5.4 Main Results

| Geo |
---|---|---
Model | EN | IT | DE | ScanSP
| ? | Q | LEN | ? | Q | LEN | ? | Q | LEN | IID | RX | ARX
LSTM | 52.9 | 24.9 | 5.0 | 46.4 | 18.1 | 4.3 | 42.9 | 17.6 | 3.2 | 100 | 24.4 | 1.1
mT5 | 80.0 | 60.0 | 19.3 | 73.2 | 44.9 | 20.4 | 68.2 | 47.8 | 18.6 | 100 | 41.2 | 99.8
mBART | 87.5 | 69.4 | 27.5 | 86.6 | 76.4 | 23.3 | 75.5 | 56.3 | 18.2 | 100 | 99.4 | 100
SpanBasedSP | 87.7 | 74.6 | 55.0 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | 100 | 100 | 100
-gold | 66.4 | 51.8 | 24.6 | 49.6 | 37.3 | 10.4 | 40.4 | 21.4 | 5.0 | 100 | 100 | 100
TPol | 87.3 | 87.8 | 41.9 | 85.9 | 82.4 | 31.3 | 73.3 | 69.4 | 22.9 | $-$ | $-$ | $-$
-gold | 85.8 | 79.0 | 35.6 | 83.6 | 75.1 | 20.2 | 73.8 | 60.7 | 17.5 | 100 | 99.4 | 100
Table 1:  Exact match accuracy of all models on both GeoAligned and ScanSP
datasets.

We report the results of our experiments in Table 1. For all models we
validate hyper-parameters on the validation sets, and then train jointly on
training and validation sets. For both SpanBasedSP and TPol we test the models
both with and without gold alignments. When we use gold alignments, we test
with IBM models 3, 4, and 5, and pick the best out of the three. In general,
all models achieve similar performance. For SpanBasedSP the gold alignments
mode is only possible for the English version of Geo, as the annotations
required are provided only for that language. For TPol, the choice of the
modules’ architecture is validated on the development set, and we report a
breakdown of the performance in Section 7.

We first consider the results with gold alignments. On the Geo dataset, the
LSTM and mT5 achieve the lowest performance in all the partitions. Looking at
the question partition, the other models show similar performances which is
not surprising as the test split does not require compositional
generalization. If we instead look at the query partition, TPol shows
significant improvements over all the other models across all languages. In
English it obtains 87.3% outperforming both mBART (69.4%) and SpanBasedSP
(74.6%). In Italian and German it obtains 82.4% and 69.4% respectively, while
mBART 67.4% and 56.3%. On the length partition, TPol does better than mBART
across all languages, while on English SpanBasedSP fares better.

If we examine the results obtained without gold alignments, we see that TPol
shows considerable improvements against SpanBasedSP when it is also run
without gold alignments. In particular, it improves on the English query
partition obtaining 79% against 51.8%. Furthermore, the accuracy does not drop
significantly with respect to TPol run with gold alignments.

Finally, looking at the Scan dataset, as expected the models designed for
compositional generalization achieve perfect performance on the dataset. What
is surprising is that also mBART is able to do so, contrary to other deep
models. With some internal testing we have seen that this is not the case for
BART and we hypothesize that model size and pre-training might be a factor of
success for the multilingual version.

##  6 Error Analysis

| Geo EN
---|---
Module | ? | Q | LEN
Translator | 86.1 | 86.2 | 42.5
Reorderer | 87.6 | 87.3 | 57.1
Table 2: Performance breakdown of TPol modules on GeoAligned English. | Geo EN
---|---
Model | ? | Q | LEN
| MN | NMN | MN | NMN | MN | NMN
mBART | 90.4 | 81.0 | 67.1 | 76.5 | 29.2 | 25.1
SpanBasedSP | 94.7 | 73.7 | 89.6 | 39.8 | 68.1 | 35.9
TPol | 89.9 | 81.4 | 93.7 | 69.9 | 55.5 | 23.2
Table 3: Performance breakdown of TPol over monotonic (MN) and non-monotonic
(NMN) sequences in GeoAligned English.

Table 2 shows a breakdown of performance of TPol on the English version of
GeoAligned. The results indicate the exact match accuracy achieved by the two
modules: using this we can check whether the model struggles more with the
translation or with the reordering step. To analyze the performance of the
Translator, we regard the monotonically aligned MRs as the gold truth. To
analyze the performance of the Reorderer, we provide it with the monotonically
aligned MR and compare the output to the gold MR. In other words, the
evaluation of the Reorderer assumes that the Translator makes a correct
prediction. The performance of the two modules is fairly similar, and, by
comparing these results with Table 1, we see that the accuracy of each
component is not much higher than the overall accuracy, suggesting that
neither component is hampering performance more than the other. The only
exception seems to be in the length partition, where the Reorderer does
considerably better than the Translator.

Table 3 shows the breakdown of the performance over monotonically and non-
monotonically aligned MRs. We can observe that, compared to SpanBasedSP, TPol
generally presents smaller drops in performance over the non-monotonic
sequences. For instance, in the question partition, SpanBasedSP drops from
94.7% over the monotonic examples to 73.7% over the non-monotonic, while TPol
drops from 89.9% over the monotonic to 81.4% over the non-monotonic. When we
look at the query partition, we see that for both of these models, the drop is
much higher than the one on the question partition: SpanBasedSP goes from
89.6% to 39.8%, while TPol drops from 93.7% to 69.9%. In other words, both
models struggle more on non-monotonic examples when compositional
generalization is required. TPol, however, still performs significantly
better.

Surprisingly, mBART shows the opposite trend on the query partition, with the
non-monotonic accuracy being higher than the monotonic one. Most of our
improved performance comes from a better modeling of the monotonic sequences
($67.1\%\rightarrow 93.7\%$), while maintaining a slightly inferior
performance over non-monotonic sequences. Interestingly, the SpanBasedSP
approach shows a similar improvement over mBART on monotonic sequences
($67.1\%\rightarrow 89.6\%$).

This suggests that exploiting lexico-logical alignments with our two-step
approach offers the best of both worlds: it can capture well the simpler
patterns that mBART fails to learn, while maintaining reasonable performance
over the more complex alignments on which SpanBasedSP fails.

Figure 4: Average alignment error of the different IBM automatic alignment
models, over all partitions and languages for the GeoAligned dataset. For each
model, we also plot the average drop in performance, where the drop is
computed with respect to the corresponding model that uses gold alignments.

Figure 4 shows the average drop in performance of the different models trained
with automatic IBM alignments when compared to the same model that uses gold
alignments. We also report the corresponding alignment error, calculated as
the percentage of bi-symbols that differ from the gold annotations from
GeoAligned. We observe that, in general, a larger alignment error is
associated with a higher drop in performance. This validates the importance of
the alignment information and points to improving the unsupervised alignment
algorithm as a natural line of future work.

##  7 Architecture study

| Geo
---|---
Model | EN | IT | DE
| ? | Q | LEN | ? | Q | LEN | ? | Q | LEN
Bert2Bert | 74.9 | 84.6 | 41.9 | 74.0 | 74.2 | 31.3 | 62.5 | 46.0 | 22.9
Bert2mBart | 82.1 | 87.8 | 36.4 | 76.9 | 81.6 | 27.5 | 63.2 | 68.9 | 20.0
Bert2mBart silver | 82.5 | 87.0 | 34.6 | 76.6 | 81.1 | 27.0 | 65.4 | 69.4 | 19.9
mBart2Bert | 74.5 | 70.7 | 24.5 | 77.7 | 76.1 | 24.2 | 65.7 | 56.1 | 17.5
mBart2mBart | 87.3 | 72.2 | 25.2 | 85.7 | 82.4 | 23.1 | 73.3 | 59.2 | 16.3
mBart2mBart silver | 86.4 | 71.5 | 24.9 | 85.9 | 82.4 | 20.0 | 73.2 | 59.5 | 17.0
Table 4: Performance breakdown of TPol for different module architectures on
GeoAligned.

We emphasize here that our approach is an abstract, high-level methodology,
and that it does not place any constraint on the underlying architectures of
the two components. We believe that different architectures, and in particular
specialized ones for each module, could be beneficial for parsing performance.
We therefore encourage further work to be carried out in this regard. To this
purpose, we present some architectural studies using BERT (Devlin et al.,
2019) and mBART (Liu et al., 2020) as components. We employ them as both a
Translator and a Reorderer. We also examine the possible combinations between
them, meaning mBART as first component and BERT as second, and vice versa. As
explained in Section 4.1, mBART is used as a standard seq2seq models, and BERT
is employed with a classification head such that it functions as a tagger for
every word in the input sequence.

Additionally, when mBART is used as a Reorderer, we introduce a new way of
training it: normally, the Reorderer is trained by taking the gold alignment
annotations and outputting the meaning representation. Instead, we use as
training input the predictions of the Translator model, and we indicate this
as _silver_ training mode. By doing so, the Reorderer trains on inputs that
mimic more closely what it will actually receive at test time: this is done
straightforwardly for a seq2seq model like mBART, while for our BERT tagger
every word in input needs to be aligned with a symbol in output, and when the
input is corrupt it is not possible to achieve the same training technique.

In Table 4 we present the results for our different architectural components.
To distinguish among the different model combinations, we use a
[Translator]2[Reorderer] naming convention, meaning that mBart2Bert uses mBART
as the Translator and Bert as the Reorderer. We observe that our two-step
approach seems to be robust overall. We can discern some trends about
different architectures combinations which can be helpful to help us choose an
architecture for a specific task. For example, the BERT Translator seems to
achieve better results for the compositional partitions, while mBART for the
IID. We believe that different architectural components, especially if more
specialized, could further improve performance. We leave this as future work.

##  8 Conclusion

Sequence to sequence models have become increasingly popular in semantic
parsing. However, they are limited in their abilities to generalize to
unobserved structures. Here, we proposed TPol: a two-step parsing approach
that leverages alignment annotations with a modular framework composed of a
Translator and a Reorderer.

We showed that TPol improves compositional generalization over conventional
seq2seq models, as well as over a competing model that also leverages
alignment information. We also showed that our approach is robust when trained
with automatically generated alignments, demonstrating competitive results on
two semantic parsing datasets. Lastly, we showed that TPol is model agnostic,
and studied its performance with several architectural configurations. This
opens the door to further experimentation of different architectures for the
two components.

##  9 Limitations

Regarding the limitations of our approach, one point is that the FunQL meaning
representation has a relatively straightforward nature, with a strong
structural correspondence with the NL sequences. Transitioning to a different
meaning representation might need some adaptation, and might require several
insertion and deletion operations.

A second limitation is our use of gold alignments. We partially address this
by training TPol with automatic alignments obtained with the IBM models, but
we believe there is room for more work to be done, so that this approach can
be more easily scaled to datasets that do not have alignments annotations.

## References

  * Agarwal et al. (2020) Oshin Agarwal, Mihir Kale, Heming Ge, Siamak Shakeri, and Rami Al-Rfou. 2020.  Machine translation aided bilingual data-to-text generation and semantic parsing.  In _Proceedings of the 3rd International Workshop on Natural Language Generation from the Semantic Web (WebNLG+)_ , pages 125–130, Dublin, Ireland (Virtual). Association for Computational Linguistics.
  * Andreas (2020) Jacob Andreas. 2020.  Good-enough compositional data augmentation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7556–7566, Online. Association for Computational Linguistics.
  * Andreas et al. (2013) Jacob Andreas, Andreas Vlachos, and Stephen Clark. 2013.  Semantic parsing as machine translation.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 47–52, Sofia, Bulgaria. Association for Computational Linguistics.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * 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.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(14):12564–12573.
  * Brown et al. (1993) Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993.  The mathematics of statistical machine translation: Parameter estimation.  _Computational Linguistics_ , 19(2):263–311.
  * 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.  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 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dong and Lapata (2016) Li Dong and Mirella Lapata. 2016.  Language to logical form with neural attention.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 33–43, Berlin, Germany. Association for Computational Linguistics.
  * Ferreira et al. (2016) Daniel C. Ferreira, André F. T. Martins, and Mariana S. C. Almeida. 2016.  Jointly learning to embed and predict with multiple languages.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2019–2028, Berlin, Germany. Association for Computational Linguistics.
  * Finegan-Dollak et al. (2018) Catherine Finegan-Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. 2018.  Improving text-to-SQL evaluation methodology.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 351–360, Melbourne, Australia. Association for Computational Linguistics.
  * Gordon et al. (2020) Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. 2020.  Permutation equivariant models for compositional generalization in language.  In _ICLR_.
  * Herzig and Berant (2021) Jonathan Herzig and Jonathan Berant. 2021.  Span-based semantic parsing for compositional generalization.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 908–921, Online. Association for Computational Linguistics.
  * Jia and Liang (2016) Robin Jia and Percy Liang. 2016.  Data recombination for neural semantic parsing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 12–22, Berlin, Germany. Association for Computational Linguistics.
  * Kate et al. (2005) Rohit J. Kate, Yuk Wah Wong, and Raymond J. Mooney. 2005.  Learning to transform natural to formal languages.  In _Proceedings of the 20th National Conference on Artificial Intelligence - Volume 3_ , AAAI’05, page 1062–1068. AAAI Press.
  * Keysers et al. (2020) Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020.  Measuring compositional generalization: A comprehensive method on realistic data.  In _International Conference on Learning Representations_.
  * Kim and Linzen (2020) Najoung Kim and Tal Linzen. 2020.  COGS: A compositional generalization challenge based on semantic interpretation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9087–9105, Online. Association for Computational Linguistics.
  * Lake and Baroni (2018) Brenden Lake and Marco Baroni. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2873–2882. PMLR.
  * Lake (2019) Brenden M Lake. 2019.  Compositional generalization through meta sequence-to-sequence learning.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Lei et al. (2020) Wenqiang Lei, Weixin Wang, Zhixin Ma, Tian Gan, Wei Lu, Min-Yen Kan, and Tat-Seng Chua. 2020.  Re-examining the role of schema linking in text-to-SQL.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6943–6954, Online. Association for Computational Linguistics.
  * 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_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Liu et al. (2021a) Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. 2021a.  Learning algebraic recombination for compositional generalization.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1129–1144, Online. Association for Computational Linguistics.
  * Liu et al. (2021b) Qian Liu, Dejian Yang, Jiahui Zhang, Jiaqi Guo, Bin Zhou, and Jian-Guang Lou. 2021b.  Awakening latent grounding from pretrained language models for semantic parsing.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1174–1189, Online. 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.
  * Locatelli and Quattoni (2022) Davide Locatelli and Ariadna Quattoni. 2022.  Measuring alignment bias in neural seq2seq semantic parsers.  In _Proceedings of the 11th Joint Conference on Lexical and Computational Semantics_ , pages 200–207, Seattle, Washington. Association for Computational Linguistics.
  * Loula et al. (2018) João Loula, Marco Baroni, and Brenden Lake. 2018.  Rearranging the familiar: Testing compositional generalization in recurrent networks.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 108–114, Brussels, Belgium. Association for Computational Linguistics.
  * Och and Ney (2003) Franz Josef Och and Hermann Ney. 2003.  A systematic comparison of various statistical alignment models.  _Computational Linguistics_ , 29(1):19–51.
  * Oren et al. (2020) Inbar Oren, Jonathan Herzig, Nitish Gupta, Matt Gardner, and Jonathan Berant. 2020\.  Improving compositional generalization in semantic parsing.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2482–2495, Online. Association for Computational Linguistics.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global vectors for word representation.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543.
  * Qiu et al. (2022a) Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022a.  Improving compositional generalization with latent structure and data augmentation.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4341–4362, Seattle, United States. Association for Computational Linguistics.
  * Qiu et al. (2022b) Linlu Qiu, Peter Shaw, Panupong Pasupat, Tianze Shi, Jonathan Herzig, Emily Pitler, Fei Sha, and Kristina Toutanova. 2022b.  Evaluating the impact of model scale for compositional generalization in semantic parsing.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Ribeiro et al. (2018) Joana Ribeiro, Shashi Narayan, Shay B. Cohen, and Xavier Carreras. 2018.  Local string transduction as sequence labeling.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 1360–1371, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Shaw et al. (2021) Peter Shaw, Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. 2021.  Compositional generalization and natural language variation: Can a semantic parsing approach handle both? In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 922–938, Online. Association for Computational Linguistics.
  * Shi et al. (2020) Tianze Shi, Chen Zhao, Jordan Boyd-Graber, Hal Daumé III, and Lillian Lee. 2020\.  On the potential of lexico-logical alignments for semantic parsing to SQL queries.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1849–1864, Online. Association for Computational Linguistics.
  * Sun et al. (2022) Runxin Sun, Shizhu He, Chong Zhu, Yaohan He, Jinlong Li, Jun Zhao, and Kang Liu. 2022.  Leveraging explicit lexico-logical alignments in text-to-SQL parsing.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 283–289, Dublin, Ireland. Association for Computational Linguistics.
  * Wang et al. (2021) Bailin Wang, Mirella Lapata, and Ivan Titov. 2021.  Structured reordering for modeling latent alignments in sequence transduction.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 13378–13391. Curran Associates, Inc.
  * Weißenhorn et al. (2022) Pia Weißenhorn, Lucia Donatelli, and Alexander Koller. 2022.  Compositional generalization with a broad-coverage semantic parser.  In _Proceedings of the 11th Joint Conference on Lexical and Computational Semantics_ , pages 44–54, Seattle, Washington. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi 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 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.
  * Wong and Mooney (2006) Yuk Wah Wong and Raymond Mooney. 2006.  Learning for semantic parsing with statistical machine translation.  In _Proceedings of the Human Language Technology Conference of the NAACL, Main Conference_ , pages 439–446, New York City, USA. Association for Computational Linguistics.
  * Xue et al. (2021) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2021.  mT5: A massively multilingual pre-trained text-to-text transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 483–498, Online. Association for Computational Linguistics.
  * Yang et al. (2022) Jingfeng Yang, Le Zhang, and Diyi Yang. 2022.  SUBS: Subtree substitution for compositional semantic parsing.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 169–174, Seattle, United States. Association for Computational Linguistics.
  * Zelle and Mooney (1996) John M. Zelle and Raymond J. Mooney. 1996.  Learning to parse database queries using inductive logic programming.  In _Proceedings of the Thirteenth National Conference on Artificial Intelligence - Volume 2_ , AAAI’96, page 1050–1055. AAAI Press.
  * Zhang et al. (2019) Sheng Zhang, Xutai Ma, Kevin Duh, and Benjamin Van Durme. 2019.  AMR parsing as sequence-to-graph transduction.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 80–94, Florence, Italy. Association for Computational Linguistics.

##  Appendix A Experimental details

For our experiments with TPol we report the average of three runs for every
result. We select the hyperparameters with grid search on the development set
performance stopping when there is no more improvement. We choose the learning
rate among $1e^{-4}$, $1e^{-5}$ and $1e^{-6}$ and the batch size between the
bounds of $4$ and $32$. Usually the best performing models choose a learning
rate of $1e^{-5}$ and batch size of $8$. An experiment takes about $90$
minutes on a single Nvidia V100 GPU. Our BERT ($110$M parameters) and mBART
($680$M parameters) implementations are taken from the transformers library
(Wolf et al., 2020). We use for English bert-base-uncased, for Italian
dbmdz/bert-base-italian-uncased and for German dbmdz/bert-base-german-uncased.
For mBART we use facebook/mbart-large-50.