# Modeling Graph Structure via Relative Position for Text Generation from
Knowledge Graphs

Martin Schmitt1 Leonardo F. R. Ribeiro2 Philipp Dufter1 Iryna Gurevych2
Hinrich Schütze1

1Center for Information and Language Processing (CIS), LMU Munich
2Research Training Group AIPHES and UKP Lab, Technische Universität Darmstadt
<EMAIL_ADDRESS>
###### Abstract

We present _Graformer_ , a novel Transformer-based encoder-decoder
architecture for graph-to-text generation. With our novel graph self-
attention, the encoding of a node relies on all nodes in the input graph – not
only direct neighbors – facilitating the detection of global patterns. We
represent the relation between two nodes as the length of the shortest path
between them. Graformer learns to weight these node-node relations differently
for different attention heads, thus virtually learning differently connected
views of the input graph. We evaluate Graformer on two popular graph-to-text
generation benchmarks, AGENDA and WebNLG, where it achieves strong performance
while using many fewer parameters than other approaches.111Our code is
publicly available: https://github.com/mnschmit/graformer

##  1 Introduction

A knowledge graph (KG) is a flexible data structure commonly used to store
both general world knowledge (Auer et al., 2008) and specialized information,
e.g., in biomedicine (Wishart et al., 2018) and computer vision (Krishna et
al., 2017). Generating a natural language description of such a graph
(KG$\to$text) makes the stored information accessible to a broader audience of
end users. It is therefore important for KG-based question answering (Bhowmik
and de Melo, 2018), data-to-document generation (Moryossef et al., 2019;
Koncel-Kedziorski et al., 2019) and interpretability of KGs in general
(Schmitt et al., 2020).

Recent approaches to KG$\to$text employ encoder-decoder architectures: the
encoder first computes vector representations of the graph’s nodes, the
decoder then uses them to predict the text sequence. Typical encoder choices
are graph neural networks based on message passing between direct neighbors in
the graph (Kipf and Welling, 2017; Veličković et al., 2018) or variants of
Transformer (Vaswani et al., 2017) that apply self-attention on all nodes
together, including those that are not directly connected. To avoid losing
information, the latter approaches use edge or node labels from the shortest
path when computing the attention between two nodes (Zhu et al., 2019; Cai and
Lam, 2020). Assuming the existence of a path between any two nodes is
particularly problematic for KGs: a set of KG facts often does not form a
connected graph.

We propose a flexible alternative that neither needs such an assumption nor
uses label information to model graph structure: a Transformer-based encoder
that interprets the lengths of shortest paths in a graph as relative position
information and thus, by means of multi-head attention, dynamically learns
different structural views of the input graph with differently weighted
connection patterns. We call this new architecture _Graformer_.

Following previous work, we evaluate Graformer on two benchmarks:  (i) the
AGENDA dataset (Koncel-Kedziorski et al., 2019), i.e., the generation of
scientific abstracts from automatically extracted entities and relations
specific to scientific text, and  (ii) the WebNLG challenge dataset (Gardent
et al., 2017), i.e., the task of generating text from DBPedia subgraphs.  On
both datasets, Graformer achieves more than 96% of the state-of-the-art
performance while using only about half as many parameters.

In summary, our contributions are as follows:  (1) We develop _Graformer_ , a
novel graph-to-text architecture that interprets shortest path lengths as
relative position information in a graph self-attention network.  (2)
Graformer achieves competitive performance on two popular KG-to-text
generation benchmarks, showing that our architecture can learn about graph
structure without any guidance other than its text generation objective.  (3)
To further investigate what Graformer learns about graph structure, we
visualize the differently connected graph views it has learned and indeed find
different attention heads for more local and more global graph information.
Interestingly, direct neighbors are considered particularly important even
without any structural bias, such as introduced by a graph neural network.
(4) Analyzing the performance w.r.t. different input graph properties, we find
evidence that Graformer’s more elaborate global view on the graph is an
advantage when it is important to distinguish between distant but connected
nodes and truly unreachable ones.

##  2 Related Work

Most recent approaches to graph-to-text generation employ a graph neural
network (GNN) based on message passing through the input graph’s topology as
the encoder in their encoder-decoder architectures (Marcheggiani and Perez-
Beltrachini, 2018; Koncel-Kedziorski et al., 2019; Ribeiro et al., 2019; Guo
et al., 2019). As one layer of these encoders only considers immediate
neighbors, a large number of stacked layers can be necessary to learn about
distant nodes, which in turn also increases the risk of propagating noise (Li
et al., 2018).

Other approaches (Zhu et al., 2019; Cai and Lam, 2020) base their encoder on
the Transformer architecture (Vaswani et al., 2017) and thus, in each layer,
compute self-attention on all nodes, not only direct neighbors, facilitating
the information flow between distant nodes. Like Graformer, these approaches
incorporate information about the graph topology with some variant of relative
position embeddings (Shaw et al., 2018). They, however, assume that there is
always a path between any pair of nodes, i.e., there are no unreachable nodes
or disconnected subgraphs. Thus they use an LSTM (Hochreiter and Schmidhuber,
1997) to compute a relation embedding from the labels along this path.
However, in contrast to the AMR222abstract meaning representation graphs used
for their evaluation, KGs are frequently disconnected. Graformer is more
flexible and makes no assumption about connectivity. Furthermore, its relative
position embeddings only depend on the lengths of shortest paths i.e., purely
structural information, not labels. It thus effectively learns differently
connected views of its input graph.

Deficiencies in modeling long-range dependencies in GNNs have been considered
a serious limitation before. Various solutions orthogonal to our approach have
been proposed in recent work: By incorporating a connectivity score into their
graph attention network, Zhang et al. (2020) manage to increase the attention
span to k-hop neighborhoods but, finally, only experiment with $k=2$. Our
graph encoder efficiently handles dependencies between much more distant
nodes. Pei et al. (2020) define an additional neighborhood based on Euclidean
distance in a continuous node embedding space. Similar to our work, a node can
thus receive information from distant nodes, given their embeddings are close
enough. However, Pei et al. (2020) compute these embeddings only once before
training whereas in our approach node similarity is based on the learned
representation in each encoder layer. This allows Graformer to dynamically
change node interaction patterns during training.

Recently, Ribeiro et al. (2020) use two GNN encoders – one using the original
topology and one with a fully connected version of the graph – and combine
their output in various ways for graph-to-text generation. This approach can
only see two extreme versions of the graph: direct neighbors and full
connection. Our approach is more flexible and dynamically learns a different
structural view per attention head. It is also more parameter-efficient as our
multi-view encoder does not need a separate set of parameters for each view.

##  3 The Graformer Model

Graformer follows the general multi-layer encoder-decoder pattern known from
the original Transformer (Vaswani et al., 2017). In the following, we first
describe our formalization of the KG input and then how it is processed by
Graformer.

(a) Original knowledge graph

(b) Directed hypergraph (token graph)

(c) Incidence graph with $\textsc{same}{}_{p}$ edges (dashed green)

Figure 1: Different representations of the same KG (types are omitted for
clarity).

###  3.1 Graph data structure

Knowledge graph. We formalize a knowledge graph (KG) as a directed, labeled
multigraph
$G_{\mathit{KG}}=\left(V,A,s,t,l_{V},l_{A},\mathcal{E},\mathcal{R}\right)$
with $V$ a set of vertices (the KG entities), $A$ a set of arcs (the KG
facts), $s,t:A\to V$ functions assigning to each arc its source/target node
(the subject/object of a KG fact), and
$l_{V}:V\to\mathcal{E},l_{A}:A\to\mathcal{R}$ providing labels for vertices
and arcs, where $\mathcal{R}$ is a set of KG-specific relations and
$\mathcal{E}$ a set of entity names.

Token graph. Entity names usually consist of more than one token or subword
unit. Hence, a tokenizer $\mathit{tok}:\mathcal{E}\to\Sigma_{T}^{*}$ is needed
that splits an entity’s label into its components from the vocabulary
$\Sigma_{T}$ of text tokens. Following recent work (Ribeiro et al., 2020), we
mimic this compositionality of node labels in the graph structure by splitting
each node into as many nodes as there are tokens in its label. We thus obtain
a directed hypergraph
$G_{T}=\left(V_{T},A,s_{T},t_{T},l_{T},l_{A},\Sigma_{T},\mathcal{R},\mathit{same}{}\right)$,
where $s_{T},t_{T}:A\to\mathcal{P}\left(V_{T}\right)$ now assign a set of
source (resp. target) nodes to each (hyper-) arc and all nodes are labeled
with only one token, i.e., $l_{T}:V_{T}\to\Sigma_{T}$. Unlike Ribeiro et al.
(2020), we additionally keep track of all token nodes’ origins:
$\mathit{same}{}:V_{T}\to\mathcal{P}\left(V_{T}\times\mathbb{Z}\right)$
assigns to each node $n$ all other nodes $n^{\prime}$ stemming from the same
entity together with the relative position of $l_{T}(n)$ and
$l_{T}(n^{\prime})$ in the original tokenized entity name. Fig. 1(b) shows the
token graph corresponding to the KG in Fig. 1(a).

Incidence graph. For ease of implementation, our final data structure for the
KG is the hypergraph’s incidence graph, a bipartite graph where hyper-arcs are
represented as nodes and edges are unlabeled:
$G=\left(N,E,l,\Sigma,\left\\{\,\textsc{same}{}_{p}\mid
p\in\mathbb{Z}\,\right\\}\right)$ where $N=V_{T}\cup A$ is the set of nodes,
$E=\left\\{\,\left(n_{1},n_{2}\right)\mid n_{1}\in s_{T}(n_{2})\lor n_{2}\in
t_{T}(n_{1})\,\right\\}$ the set of directed edges, $l:N\to\Sigma$ a label
function, and $\Sigma=\Sigma_{T}\cup\mathcal{R}$ the vocabulary. We introduce
$\textsc{same}{}_{p}$ edges to fully connect $\mathit{same}$ clusters:
$\textsc{same}{}_{p}=\left\\{\,\left(n_{1},n_{2}\right)\mid\left(n_{2},p\right)\in\mathit{same}{}(n_{1})\,\right\\}$
where $p$ differentiates between different relative positions in the original
entity string, similar to (Shaw et al., 2018). See Fig. 1(c) for an example.

###  3.2 Graformer encoder

The initial graph representation
$\bm{H}^{(0)}\in\mathbb{R}^{\left|N\right|\times d}$ is obtained by looking up
embeddings for the node labels in the learned embedding matrix
$\bm{E}\in\mathbb{R}^{\left|\Sigma\right|\times d}$, i.e.,
$\bm{H}_{i}^{(0)}=\bm{e}^{l(n_{i})}\bm{E}$ where $\bm{e}^{l(n_{i})}$ is the
one-hot-encoding of the $i$th node’s label.

To compute the node representation $\bm{H}^{(L)}$ in the $L$th layer, we
follow Vaswani et al. (2017), i.e., we first normalize the input from the
previous layer $\bm{H}^{(L-1)}$ via layer normalization $\mathit{LN}$,
followed by multi-head graph self-attention $\mathit{SelfAtt}_{g}$ (see § 3.3
for details), which – after dropout regularization $\mathit{Dr}$ and a
residual connection – yields the intermediate representation
$\bm{\mathcal{I}}$ (cf. Eq. 1). A feedforward layer $\mathit{FF}$ with one
hidden layer and GeLU (Hendrycks and Gimpel, 2016) activation computes the
final layer output (cf. Eq. 2). As recommended by Chen et al. (2018), we apply
an additional layer normalization step to the output $\bm{H}^{(L_{E})}$ of the
last encoder layer $L_{E}$.

$\displaystyle\bm{\mathcal{I}}^{(L)}$
$\displaystyle=\mathit{Dr}(\mathit{SelfAtt}_{g}(\mathit{LN}(\bm{H}^{(L-1)})))+\bm{H}^{(L-1)}$
(1) $\displaystyle\bm{H}^{(L)}$
$\displaystyle=\mathit{Dr}(\mathit{FF}(\mathit{LN}(\bm{\mathcal{I}}^{(L)})))+\bm{\mathcal{I}}^{(L)}$
(2)

$\mathit{SelfAtt}_{g}$ computes a weighted sum of $\bm{H}^{(L-1)}$:

$\mathit{SelfAtt}_{g}(\bm{H})_{i}=\sum_{j=1}^{\left|N\right|}\alpha_{ij}^{g}(\bm{H}_{j}\bm{W}^{V_{g}})$
(3)

where $\bm{W}^{V_{g}}\in\mathbb{R}^{d\times d}$ is a learned parameter matrix.

In the next section, we derive the definition of the graph-structure-informed
attention weights $\alpha_{ij}^{g}$.

###  3.3 Self-attention for text and graphs with relative position embeddings

In this section, we describe the computation of attention weights for multi-
head self-attention. Note that the formulas describe the computations for one
head. The output of multiple heads is combined as in the original Transformer
(Vaswani et al., 2017).

Text self-attention. Shaw et al. (2018) introduced position-aware self-
attention in the Transformer by  (i) adding a relative position embedding
$\bm{\mathsfit{A}}^{K}\in\mathbb{R}^{M\times M\times d}$ to $\bm{X}$’s key
representation, when computing the softmax-normalized attention scores
$\bm{\alpha}_{i}$ between $\bm{X}_{i}\in\mathbb{R}^{d}$ and the complete input
embedding matrix $\bm{X}\in\mathbb{R}^{M\times d}$ (cf. Eq. 4), and  (ii)
adding a second type of position embedding
$\bm{\mathsfit{A}}^{V}\in\mathbb{R}^{M\times M\times d}$ to $\bm{X}$’s value
representation when computing the weighted sum (cf. Eq. 5):

$\displaystyle\bm{\alpha}_{i}$
$\displaystyle=\sigma\left(\frac{\bm{X}_{i}\bm{W}^{Q}(\bm{X}\bm{W}^{K}+\bm{\mathsfit{A}}^{K}_{i})^{\top}}{\sqrt{d}}\right)$
(4) $\displaystyle\bm{V}_{i}$
$\displaystyle=\sum_{j=1}^{n}\alpha_{ij}(\bm{X}_{j}\bm{W}^{V}+\bm{\mathsfit{A}}_{ij}^{V})$
(5)

where $\sigma\left(\cdot\right)$ denotes the softmax function, i.e.,

$\sigma\left(\bm{b}\right)_{i}=\frac{\exp\left(b_{i}\right)}{\sum_{j=1}^{J}\exp\left(b_{j}\right)},\quad\text{for
$\bm{b}\in\mathbb{R}^{J}$.}$

Recent work (Raffel et al., 2019) has adopted a simplified form where value-
modifying embeddings $\bm{\mathsfit{A}}^{V}$ are omitted and key-modifying
embeddings $\bm{\mathsfit{A}}^{K}$ are replaced with learned scalar embeddings
$\bm{S}\in\mathbb{R}^{M\times M}$ that – based on relative position – directly
in- or decrease attention scores before normalization, i.e., Eq. 4 becomes Eq.
6.

$\bm{\alpha}_{i}=\sigma\left(\frac{\bm{X}_{i}\bm{W}^{Q}(\bm{X}\bm{W}^{K})^{\top}}{\sqrt{d}}+\bm{S}_{i}\right)$
(6)

Shaw et al. (2018) share their position embeddings across attention heads but
learn separate embeddings for each layer as word representations from
different layers can vary a lot. Raffel et al. (2019) learn separate $\bm{S}$
matrices for each attention head but share them across layers. We use Raffel
et al. (2019)’s form of relative position encoding for text self-attention in
our decoder (§ 3.4).

| $V_{T}$ | $A$
---|---|---
|  s |  v |  d |  w |  e |  l |  c |  u1 |  u2
s |  0 |  4 |  5 |  2 |  2 |  2 |  1 |  1 |  3
v |  -4 |  0 |  4 |  2 |  2 |  2 |  1 |  1 |  3
d |  -5 |  -4 |  0 |  2 |  2 |  2 |  1 |  1 |  3
w |  -2 |  -2 |  -2 |  0 |  2 |  2 |  -1 |  $\infty$ |  1
e |  -2 |  -2 |  -2 |  -2 |  0 |  4 |  -3 |  -1 |  -1
l |  -2 |  -2 |  -2 |  -2 |  -4 |  0 |  -3 |  -1 |  -1
c |  -1 |  -1 |  -1 |  1 |  3 |  3 |  0 |  $\infty$ |  2
u1 |  -1 |  -1 |  -1 |  $\infty$ |  1 |  1 |  $\infty$ |  0 |  $\infty$
u2 |  -3 |  -3 |  -3 |  -1 |  1 |  1 |  -2 |  $\infty$ |  0
Figure 2: $\bm{R}$ matrix for the graph in Fig. 1(c)
($\delta_{\mathit{max}}=3$).

Graph self-attention. Analogously to self-attention on text, we define our
structural graph self-attention as follows:

$\bm{\alpha}_{i}^{g}=\sigma\left(\frac{\bm{H}_{i}\bm{W}^{Q_{g}}(\bm{H}\bm{W}^{K_{g}})^{\top}}{\sqrt{d}}+\gamma(\bm{R})_{i}\right)$
(7)

$\bm{W}^{K_{g}},\bm{W}^{Q_{g}}\in\mathbb{R}^{d\times d}$ are learned matrices
and $\gamma:\mathbb{Z}\cup\left\\{\infty\right\\}\to\mathbb{R}$ looks up
_learned scalar embeddings_ for the relative graph positions in
$\bm{R}\in\mathbb{R}^{N\times N}$.

We define the relative graph position $R_{ij}$ between the nodes $n_{i}$ and
$n_{j}$ with respect to two factors:  (i) the text relative position $p$ in
the original entity name if $n_{i}$ and $n_{j}$ stem from the same original
entity, i.e., $\left(n_{i},n_{j}\right)\in\textsc{same}{}_{p}$ for some $p$
and  (ii) shortest path lengths otherwise:

$R_{ij}=\begin{cases}\infty,&\text{if }\delta(n_{i},n_{j})=\infty\\\
&\text{and }\delta(n_{j},n_{i})=\infty\\\ \mathit{encode}(p),&\text{if
}\left(n_{i},n_{j}\right)\in\textsc{same}{}_{p}\\\
\delta(n_{i},n_{j}),&\text{if }\delta(n_{i},n_{j})\leq\delta(n_{j},n_{i})\\\
-\delta(n_{j},n_{i}),&\text{if
}\delta(n_{i},n_{j})>\delta(n_{j},n_{i})\end{cases}$ (8)

where $\delta(n_{i},n_{j})$ is the length of the shortest path from $n_{i}$ to
$n_{j}$, which we define to be $\infty$ if and only if there is no such path.
$\mathit{encode}$ maps a text relative position
$p\in\mathbb{Z}\setminus\left\\{0\right\\}$ to an integer outside $\delta$’s
range to avoid clashes. Concretely, we use
$\mathit{encode}(p):=\mathit{sgn}(p)\cdot\delta_{\mathit{max}}+p$ where
$\delta_{\mathit{max}}$ is the maximum graph diameter, i.e., the maximum value
of $\delta$ over all graphs under consideration.

Thus, we model graph relative position as the length of the shortest path
using either only forward edges ($R_{ij}>0$) or only backward edges
($R_{ij}<0$). Additionally, two special cases are considered:  (i) Nodes
without any purely forward or purely backward path between them
($R_{ij}=\infty$) and  (ii) token nodes from the same entity. Here the
relative position in the original entity string $p$ is encoded outside the
range of path length encodings (which are always in the interval
$\interval{-\delta_{\mathit{max}}}{\delta_{\mathit{max}}}$).

In practice, we use two thresholds, $n_{\delta}$ and $n_{p}$. All values of
$\delta$ exceeding $n_{\delta}$ are set to $n_{\delta}$ and analogously for
$p$. This limits the number of different positions a model can distinguish.

Intuition. Our definition of relative position in graphs combines several
advantages:  (i) Any node can attend to any other node – even unreachable ones
– while learning a suitable attention bias for different distances.  (ii)
$\textsc{same}{}_{p}$edges are treated differently in the attention mechanism.
Thus, entity representations can be learned like in a regular transformer
encoder, given that tokens from the same entity are fully connected with
$\textsc{same}{}_{p}$ edges with $p$ providing relative position information.
(iii) The lengths of shortest paths often have an intuitively useful
interpretation in our incidence graphs and the sign of the entries in $\bm{R}$
also captures the important distinction between incoming and outgoing paths.
In this way, Graformer can, e.g., capture the difference between the subject
and object of a fact, which is expressed as a relative position of $-1$ vs.
$1$. The subject and object nodes, in turn, see each other as $2$ and $-2$,
respectively.

Fig. 2 shows the $\bm{R}$ matrix corresponding to the graph from Fig. 1(c).
Note how token nodes from the same entity, e.g., s, v, and d, form clusters as
they have the same distances to other nodes, and how the relations inside such
a cluster are encoded outside the interval $\interval{-3}{3}$, i.e., the range
of shortest path lengths. It is also insightful to compare node pairs with the
same value in $\bm{R}$. E.g., both s and w see e at a distance of $2$ because
the entities _SVD_ and _word2vec_ are both the subject of a fact with
_embedding learning_ as the object. Likewise, s sees both c and u1 at a
distance of $1$ because its entity _SVD_ is subject to both corresponding
facts.

###  3.4 Graformer decoder

Our decoder follows closely the standard Transformer decoder (Vaswani et al.,
2017), except for the modifications suggested by Chen et al. (2018).

Hidden decoder representation. The initial decoder representation
$\bm{Z}^{(0)}\in\mathbb{R}^{M\times d}$ embeds the (partially generated)
target text $\bm{T}\in\mathbb{R}^{M\times\left|\Sigma\right|}$, i.e.,
$\bm{Z}^{(0)}=\bm{T}\bm{E}$. A decoder layer $L$ then obtains a contextualized
representation via self-attention as in the encoder (§ 3.2):

$\bm{C}^{(L)}=\mathit{Dr}(\mathit{SelfAtt}_{t}(\mathit{LN}(\bm{Z}^{(L-1)})))+\bm{Z}^{(L-1)}$
(9)

$\mathit{SelfAtt}_{t}$ differs from $\mathit{SelfAtt}_{g}$ by using different
position embeddings in Eq. 7 and, obviously, $R_{ij}$ is defined in the usual
way for text. $\bm{C}^{(L)}$ is then modified via multi-head attention
$\mathit{MHA}$ on the output $\bm{H}^{(L_{E})}$ of the last graph encoder
layer $L_{E}$. As in § 3.2, we make use of residual connections, layer
normalization $\mathit{LN}$, and dropout $\mathit{Dr}$:

$\displaystyle\bm{U}^{(L)}$
$\displaystyle=\mathit{Dr}(\mathit{MHA}(\mathit{LN}(\bm{C}^{(L)}),\bm{H}^{(L_{E})}))+\bm{C}^{(L)}$
(10) $\displaystyle\bm{Z}^{(L)}$
$\displaystyle=\mathit{Dr}(\mathit{FF}(\mathit{LN}(\bm{U}^{(L)})))+\bm{U}^{(L)}$
(11)

where

$\displaystyle\mathit{MHA}(\bm{C},\bm{H})_{i}=\sum_{j=1}^{\left|N\right|}\alpha_{ij}(\bm{H}_{j}\bm{W}^{V_{t}})$
(12)
$\displaystyle\bm{\alpha}_{i}=\sigma\left(\frac{\bm{C}_{i}\bm{W}^{Q_{t}}(\bm{H}\bm{W}^{K_{t}})^{\top}}{\sqrt{d}}\right)$
(13)

Generation probabilities. The final representation $\bm{Z}^{(L_{D})}$ of the
last decoder layer $L_{D}$ is used to compute the probability distribution
$\bm{P}_{i}\in\interval{0}{1}^{\left|\Sigma\right|}$ over all words in the
vocabulary $\Sigma$ at time step $i$:

$\bm{P}_{i}=\sigma\left(\bm{Z}_{i}^{(L_{D})}\bm{E}^{\top}\right)$ (14)

Note that $\bm{E}\in\mathbb{R}^{\left|\Sigma\right|\times d}$ is the same
matrix that is also used to embed node labels and text tokens.

###  3.5 Training

We train Graformer by minimizing the standard negative log-likelihood loss
based on the likelihood estimations described in the previous section.

##  4 Experiments

###  4.1 Datasets

We evaluate our new architecture on two popular benchmarks for KG-to-text
generation, AGENDA (Koncel-Kedziorski et al., 2019) and WebNLG (Gardent et
al., 2017). While the latter contains crowd-sourced texts corresponding to
subgraphs from various DBPedia categories, the former was automatically
created by applying an information extraction tool (Luan et al., 2018) on a
corpus of scientific abstracts (Ammar et al., 2018). As this process is noisy,
we corrected 7 train instances where an entity name was erroneously split on a
special character and, for the same reason, deleted 1 train instance entirely.
Otherwise, we use the data as is, including the train/dev/test split.

We list the number of instances per data split, as well as general statistics
about the graphs in Table 1. Note that the graphs in WebNLG are human-authored
subgraphs of DBpedia while the graphs in AGENDA were automatically extracted.
This leads to a higher number of disconnected graph components. Nearly all
WebNLG graphs consist of a single component, i.e., are connected graphs,
whereas for AGENDA this is practically never the case. We also report
statistics that depend on the tokenization (cf. § 4.2) as factors like the
length of target texts and the percentage of tokens shared verbatim between
input graph and target text largely impact the task difficulty.

| AGENDA | WebNLG
---|---|---
#instances in train | 38,719 | 18,102
#instances in val | 1,000 | 872
#instances in test | 1,000 | 971
#relation types | 7 | 373
avg #entities in KG | 13.4 | 4.0
% connected graphs | 0.3 | 99.9
avg #graph components | 8.4 | 1.0
avg component size | 1.6 | 3.9
avg #token nodes in graph | 98.0 | 36.0
avg #tokens in text | 157.9 | 31.5
avg % text tokens in graph | 42.7 | 56.1
avg % graph tokens in text | 48.6 | 49.0
Vocabulary size $\left|\Sigma\right|$ | 24,100 | 2,100
Character coverage in % | 99.99 | 100.0
Table 1: Statistics of AGENDA and the dataset from the WebNLG challenge as
used in our experiments. Upper part: data splits and original KGs. Lower part:
token graphs and BPE settings.

###  4.2 Data preprocessing

Following previous work on AGENDA (Ribeiro et al., 2020), we put the paper
title into the graph as another entity. In contrast to Ribeiro et al. (2020),
we also link every node from a real entity to every node from the title by
title2txt and txt2title edges. The type information provided by AGENDA is, as
usual for KGs, expressed with one dedicated node per type and has-type arcs
that link entities to their types. We keep the original pretokenized texts but
lowercase the title as both node labels and target texts are also lowercased.

For WebNLG, we follow previous work (Gardent et al., 2017) by replacing
underscores in entity names with whitespace and breaking apart camel-cased
relations. We furthermore follow the evaluation protocol of the original
challenge by converting all characters to lowercased ASCII and separating all
punctuation from alphanumeric characters during tokenization.

For both datasets, we train a BPE vocabulary using sentencepiece (Kudo and
Richardson, 2018) on the train set, i.e., a concatenation of node labels and
target texts. See Table 1 for vocabulary sizes. Note that for AGENDA, only
99.99% of the characters found in the train set are added to the vocabulary.
This excludes exotic Unicode characters that occur in certain abstracts.

We prepend entity and relation labels with dedicated $\langle E\rangle$ and
$\langle R\rangle$ tags.

###  4.3 Hyperparameters and training details

We train Graformer with the Adafactor optimizer (Shazeer and Stern, 2018) for
40 epochs on AGENDA and 200 epochs on WebNLG. We report test results for the
model yielding the best validation performance measured in corpus-level BLEU
(Papineni et al., 2002). For model selection, we decode greedily. The final
results are generated by beam search. Following Ribeiro et al. (2020), we
couple beam search with a length penalty (Wu et al., 2016) of $5.0$. See
Appendix A for more details and a full list of hyperparameters.

###  4.4 Epoch curriculum

We apply a data loading scheme inspired by the bucketing approach of Koncel-
Kedziorski et al. (2019) and length-based curriculum learning (Platanios et
al., 2019): We sort the train set by target text length and split it into four
buckets of two times $40\%$ and two times $10\%$ of the data. After each
training epoch, the buckets are shuffled internally but their global order
stays the same from shorter target texts to longer ones. This reduces padding
during batching as texts of similar lengths stay together and introduces a
mini-curriculum from presumably easier examples (i.e., shorter targets) to
more difficult ones for each epoch. This enables us to successfully train
Graformer even without a learning rate schedule.

##  5 Results and Discussion

###  5.1 Overall performance

Table 2 shows the results of our evaluation on AGENDA in terms of BLEU
(Papineni et al., 2002), METEOR (Banerjee and Lavie, 2005), and CHRF++
(Popović, 2017). Like the models we compare with, we report the average and
standard deviation of 4 runs with different random seeds.

Our model outperforms previous Transformer-based models that only consider
first-order neighborhoods per encoder layer (Koncel-Kedziorski et al., 2019;
An et al., 2019). Compared to the very recent models by Ribeiro et al. (2020),
Graformer performs very similarly. Using both a local and a global graph
encoder, Ribeiro et al. (2020) combine information from very distant nodes but
at the same time need extra parameters for the second encoder. Graformer is
more efficient and still matches their best model’s BLEU and METEOR scores
within a standard deviation.

The results on the test set of seen categories of WebNLG (Table 3) look
similar. Graformer outperforms most original challenge participants and more
recent work. While not performing on par with CGE-LW on WebNLG, Graformer
still achieves more than 96% of its performance while using only about half as
many parameters.

| BLEU | METEOR | CHRF++ | #P
---|---|---|---|---
Ours |  $17.80$ $\pm 0.31$ |  $22.07$ $\pm 0.23$ |  $45.43$ $\pm 0.39$ | 36.3
GT |  $14.30$ $\pm 1.01$ |  $18.80$ $\pm 0.28$ | – | –
GT+RBS |  $15.1$ $\pm 0.97$ |  $19.5$ $\pm 0.29$ | – | –
CGE-LW |  $18.01$ $\pm 0.14$ |  $22.34$ $\pm 0.07$ |  $46.69$ $\pm 0.17$ | 69.8
Table 2: Experimental results on AGENDA. GT (Graph Transformer) from (Koncel-Kedziorski et al., 2019); GT+RBS from (An et al., 2019); CGE-LW from (Ribeiro et al., 2020). Number of parameters in millions. | BLEU | METEOR | CHRF++ | #P
---|---|---|---|---
Ours |  $61.15$ $\pm 0.22$ |  $43.38$ $\pm 0.17$ |  $75.43$ $\pm 0.19$ | 5.3
UPF-FORGe | 40.88 | 40.00 | – | –
Melbourne | 54.52 | 41.00 | 70.72 | –
Adapt | 60.59 | 44.00 | 76.01 | –
Graph Conv. | 55.90 | 39.00 | – | 4.9
GTR-LSTM | 58.60 | 40.60 | – | –
E2E GRU | 57.20 | 41.00 | – | –
CGE-LW-LG |  $63.69$ $\pm 0.10$ |  $44.47$ $\pm 0.12$ |  $76.66$ $\pm 0.10$ | 10.4
Table 3: Experimental results on the WebNLG test set with seen categories.
CGE-LW-LG from (Ribeiro et al., 2020); Adapt, Melbourne and UPF-FORGe from
(Gardent et al., 2017); Graph Conv. from (Marcheggiani and Perez-Beltrachini,
2018); GTR-LSTM from (Trisedya et al., 2018); E2E GRU from (Castro Ferreira et
al., 2019). Number of parameters in millions.

$\mu_{c}$ |  | BLEU | METEOR | CHRF++
---|---|---|---|---
${}<1.25$ | Ours | 15.44 | 20.59 | 43.23
(213) | CGE-LW | 15.34 | 20.64 | 43.56
${}<1.5$ | Ours | 17.45 | 22.03 | 45.67
(338) | CGE-LW | 17.29 | 22.32 | 45.88
${}<2.0$ | Ours | 18.94 | 22.86 | 46.49
(294) | CGE-LW | 19.46 | 23.76 | 47.78
${}\geq 2.0$ | Ours | 21.72 | 24.22 | 48.79
(155) | CGE-LW | 20.97 | 24.98 | 49.83
(a) Average size $\mu_{c}$ of graph components.

$\mathsf{d}$ |  | BLEU | METEOR | CHRF++
---|---|---|---|---
1 | Ours | 16.48 | 21.16 | 43.94
(368) | CGE-LW | 16.33 | 21.16 | 44.16
2 | Ours | 18.46 | 22.70 | 46.85
(414) | CGE-LW | 18.20 | 23.14 | 47.28
${}\geq 3$ | Ours | 19.44 | 23.17 | 47.29
(218) | CGE-LW | 20.32 | 24.42 | 49.25
(b) Largest diameter $\mathsf{d}$ across all of a graph’s components.

Table 4: Performance of a single run on the test split of AGENDA w.r.t.
different input graph properties. The number of data points in each split is
indicated in parentheses.

(a) AGENDA

(b) WebNLG

Figure 3: Attention bias $\gamma$ learned by Graformer on the two datasets.
$\textsc{same}{}_{p}$ edges are omitted.

###  5.2 Performance on different types of graphs

We investigate whether Graformer is more suitable for disconnected graphs by
comparing its performance on different splits of the AGENDA test set according
to two graph properties:  (i) the average number of nodes per connected
component ($\mu_{c}$) and  (ii) the largest diameter across all of a graph’s
components ($\mathsf{d}$).

We can see in Table 4 that the performance of both Graformer and CGE-LW
(Ribeiro et al., 2020) increases with more graph structure (larger $\mu_{c}$
and $\mathsf{d}$), i.e., more information leads to more accurate texts.
Besides, Graformer outperforms CGE-LW on BLEU for graphs with smaller
components ($0<\mu_{c}<1.5$) and smaller diameters ($\mathsf{d}\\!<\\!3$).
Although METEOR and CHRF++ scores always favor CGE-LW, the performance
difference is also smaller for cases where BLEU favors Graformer.

We conjecture that Graformer benefits from its more elaborate global view,
i.e., its ability to distinguish between distant but connected nodes and
unreachable ones. CGE-LW’s global encoder cannot make this distinction because
it only sees a fully connected version of the graph.

Curiously, Graformer’s BLEU is also better for larger components ($\mu_{c}\geq
2.0$). With multiple larger components, Graformer might also better
distinguish nodes that are part of the same component from those that belong
to a different one.

Only for $1.5<\mu_{c}<2.0$, CGE-LW clearly outperforms Graformer in all
metrics. It seems that Graformer is most helpful for extreme cases, i.e., when
either most components are isolated nodes or when isolated nodes are the
exception.

Model | BLEU | METEOR | CHRF++
---|---|---|---
Graformer | 18.09 | 22.29 | 45.77
-length penalty | 17.99 | 22.19 | 45.63
-beam search | 17.33 | 21.74 | 44.87
-epoch curriculum | 13.55 | 18.91 | 39.22
Table 5: Ablation study for a single run on the test portion of AGENDA.

###  5.3 Ablation study

In a small ablation study, we examine the impact of beam search, length
penalty, and our new epoch curriculum training. We find that beam search and
length penalty do contribute to the overall performance but to a relatively
small extent. Training with our new epoch curriculum, however, proves crucial
for good performance. Platanios et al. (2019) argue that curriculum learning
can replace a learning rate schedule, which is usually essential to train a
Transformer model. Indeed we successfully optimize Graformer without any
learning rate schedule, when applying the epoch curriculum.

##  6 Learned graph structure

We visualize the learned attention bias $\gamma$ for different relative graph
positions $R_{ij}$ (cf. § 3.3; esp. Eq. 7) after training on AGENDA and WebNLG
in Fig. 3. The eight attention heads (x-axis) have learned different weights
for each graph position $R_{ij}$ (y-axis). Note that AGENDA has more possible
$R_{ij}$ values because $n_{\delta}=6$ whereas we set $n_{\delta}=4$ for
WebNLG.

For both datasets, we notice that one attention head primarily focuses on
global information (5 for AGENDA, 4 for WebNLG). AGENDA even dedicates head 6
entirely to unreachable nodes, showing the importance of such nodes for this
dataset. In contrast, most WebNLG heads suppress information from unreachable
nodes.

For both datasets, we also observe that nearer nodes generally receive a high
weight (focus on local information): In Fig. 3(b), e.g., head 2 concentrates
solely on direct incoming edges and head 0 on direct outgoing ones. Graformer
can learn empirically based on its task where direct neighbors are most
important and where they are not, showing that the strong bias from graph
neural networks is not necessary to learn about graph structure.

##  7 Conclusion

We presented Graformer, a novel encoder-decoder architecture for graph-to-text
generation based on Transformer. The Graformer encoder uses a novel type of
self-attention for graphs based on shortest path lengths between nodes,
allowing it to detect global patterns by automatically learning appropriate
weights for higher-order neighborhoods. In our experiments on two popular
benchmarks for text generation from knowledge graphs, Graformer achieved
competitive results while using many fewer parameters than alternative models.

## Acknowledgments

This work was supported by the BMBF (first author) as part of the project
MLWin (01IS18050), by the German Research Foundation (second author) as part
of the Research Training Group “Adaptive Preparation of Information from
Heterogeneous Sources” (AIPHES) under the grant No. GRK 1994/1, and by the
Bavarian research institute for digital transformation (bidt) through their
fellowship program (third author). We also gratefully acknowledge a Ph.D.
scholarship awarded to the first author by the German Academic Scholarship
Foundation (Studienstiftung des deutschen Volkes).

## References

  * Akiba et al. (2019) Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. 2019\.  Optuna: A next-generation hyperparameter optimization framework.  In _Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.
  * Ammar et al. (2018) Waleed Ammar, Dirk Groeneveld, Chandra Bhagavatula, Iz Beltagy, Miles Crawford, Doug Downey, Jason Dunkelberger, Ahmed Elgohary, Sergey Feldman, Vu Ha, Rodney Kinney, Sebastian Kohlmeier, Kyle Lo, Tyler Murray, Hsu-Han Ooi, Matthew Peters, Joanna Power, Sam Skjonsberg, Lucy Wang, Chris Wilhelm, Zheng Yuan, Madeleine van Zuylen, and Oren Etzioni. 2018.  Construction of the literature graph in semantic scholar.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 3 (Industry Papers)_ , pages 84–91, New Orleans - Louisiana. Association for Computational Linguistics.
  * An et al. (2019) Bang An, Xuannan Dong, and Changyou Chen. 2019.  Repulsive bayesian sampling for diversified attention modeling.  _4th workshop on Bayesian Deep Learning (NeurIPS 2019)_.
  * Auer et al. (2008) Sören Auer, Chris Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2008.  DBpedia: A nucleus for a web of open data.  In _Proceedings of the 6th International Semantic Web Conference (ISWC)_ , volume 4825 of _Lecture Notes in Computer Science_ , pages 722–735. Springer.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Bergstra et al. (2011) James S. Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. 2011\.  Algorithms for hyper-parameter optimization.  In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems 24_ , pages 2546–2554. Curran Associates, Inc.
  * Bhowmik and de Melo (2018) Rajarshi Bhowmik and Gerard de Melo. 2018.  Generating fine-grained open vocabulary entity type descriptions.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 877–888, Melbourne, Australia. Association for Computational Linguistics.
  * Cai and Lam (2020) Deng Cai and Wai Lam. 2020.  Graph transformer for graph-to-sequence learning.  _AAAI Conference on Artificial Intelligence_.
  * Castro Ferreira et al. (2019) Thiago Castro Ferreira, Chris van der Lee, Emiel van Miltenburg, and Emiel Krahmer. 2019.  Neural data-to-text generation: A comparison between pipeline and end-to-end architectures.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 552–562, Hong Kong, China. Association for Computational Linguistics.
  * Chen et al. (2018) Mia Xu Chen, Orhan Firat, Ankur Bapna, Melvin Johnson, Wolfgang Macherey, George Foster, Llion Jones, Mike Schuster, Noam Shazeer, Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. 2018.  The best of both worlds: Combining recent advances in neural machine translation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 76–86, Melbourne, Australia. Association for Computational Linguistics.
  * Gardent et al. (2017) Claire Gardent, Anastasia Shimorina, Shashi Narayan, and Laura Perez-Beltrachini. 2017.  The WebNLG challenge: Generating text from RDF data.  In _Proceedings of the 10th International Conference on Natural Language Generation_ , pages 124–133, Santiago de Compostela, Spain. Association for Computational Linguistics.
  * Guo et al. (2019) Zhijiang Guo, Yan Zhang, Zhiyang Teng, and Wei Lu. 2019.  Densely connected graph convolutional networks for graph-to-sequence learning.  _Transactions of the Association for Computational Linguistics_ , 7:297–312.
  * Hendrycks and Gimpel (2016) Dan Hendrycks and Kevin Gimpel. 2016.  Gaussian error linear units (gelus).  _Computing Research Repository_ , arXiv:1606.08415.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9:1735–80.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations (ICLR)_.
  * Koncel-Kedziorski et al. (2019) Rik Koncel-Kedziorski, Dhanush Bekal, Yi Luan, Mirella Lapata, and Hannaneh Hajishirzi. 2019.  Text Generation from Knowledge Graphs with Graph Transformers.  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 2284–2293, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Krishna et al. (2017) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A. Shamma, Michael S. Bernstein, and Fei-Fei Li. 2017.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International Journal of Computer Vision_ , 123:32–73.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium. Association for Computational Linguistics.
  * Li et al. (2018) Qimai Li, Zhichao Han, and Xiao ming Wu. 2018.  Deeper insights into graph convolutional networks for semi-supervised learning.  _AAAI Conference on Artificial Intelligence_.
  * Luan et al. (2018) Yi Luan, Luheng He, Mari Ostendorf, and Hannaneh Hajishirzi. 2018.  Multi-task identification of entities, relations, and coreference for scientific knowledge graph construction.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3219–3232, Brussels, Belgium. Association for Computational Linguistics.
  * Marcheggiani and Perez-Beltrachini (2018) Diego Marcheggiani and Laura Perez-Beltrachini. 2018.  Deep graph convolutional encoders for structured data to text generation.  In _Proceedings of the 11th International Conference on Natural Language Generation_ , pages 1–9, Tilburg University, The Netherlands. Association for Computational Linguistics.
  * Moryossef et al. (2019) Amit Moryossef, Yoav Goldberg, and Ido Dagan. 2019.  Step-by-step: Separating planning from realization in neural data-to-text generation.  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 2267–2277, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020.  Geom-gcn: Geometric graph convolutional networks.  In _International Conference on Learning Representations (ICLR)_.
  * Platanios et al. (2019) Emmanouil Antonios Platanios, Otilia Stretcu, Graham Neubig, Barnabas Poczos, and Tom Mitchell. 2019.  Competence-based curriculum learning for neural machine translation.  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 1162–1172, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Popović (2017) Maja Popović. 2017.  chrF++: words helping character n-grams.  In _Proceedings of the Second Conference on Machine Translation_ , pages 612–618, Copenhagen, Denmark. Association for Computational Linguistics.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Computing Research Repository_ , arXiv:1910.10683.
  * Ribeiro et al. (2019) Leonardo F. R. Ribeiro, Claire Gardent, and Iryna Gurevych. 2019.  Enhancing AMR-to-text generation with dual graph representations.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3183–3194, Hong Kong, China. Association for Computational Linguistics.
  * Ribeiro et al. (2020) Leonardo F. R. Ribeiro, Yue Zhang, Claire Gardent, and Iryna Gurevych. 2020.  Modeling global and local node contexts for text generation from knowledge graphs.  _Transactions of the Association for Computational Linguistics_ , 8(0):589–604.
  * Schmitt et al. (2020) Martin Schmitt, Sahand Sharifzadeh, Volker Tresp, and Hinrich Schütze. 2020\.  An unsupervised joint system for text generation from knowledge graphs and semantic parsing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7117–7130, Online. Association for Computational Linguistics.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018.  Self-attention with relative position representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 464–468, New Orleans, Louisiana. Association for Computational Linguistics.
  * Shazeer and Stern (2018) Noam Shazeer and Mitchell Stern. 2018.  Adafactor: Adaptive learning rates with sublinear memory cost.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 4596–4604. PMLR.
  * Trisedya et al. (2018) Bayu Distiawan Trisedya, Jianzhong Qi, Rui Zhang, and Wei Wang. 2018.  GTR-LSTM: A triple encoder for sentence generation from RDF data.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1627–1637, Melbourne, Australia. Association for Computational Linguistics.
  * 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 I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , page 5998–6008. Curran Associates, Inc.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks.  In _International Conference on Learning Representations (ICLR)_.
  * Wishart et al. (2018) David S Wishart, Yannick D Feunang, An C Guo, Elvis J Lo, Ana Marcu, Jason R Grant, Tanvir Sajed, Daniel Johnson, Carin Li, Zinat Sayeeda, Nazanin Assempour, Ithayavani Iynkkaran, Yifeng Liu, Adam Maciejewski, Nicola Gale, Alex Wilson, Lucy Chin, Ryan Cummings, Diana Le, Allison Pon, Craig Knox, and Michael Wilson. 2018.  DrugBank 5.0: a major update to the DrugBank database for 2018.  _Nucleic Acids Research_ , 46(D1):D1074–D1082.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Łukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _Computing Research Repository_ , arXiv:1609.08144.
  * Zhang et al. (2020) Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. 2020.  Adaptive structural fingerprints for graph attention networks.  In _International Conference on Learning Representations (ICLR)_.
  * Zhu et al. (2019) Jie Zhu, Junhui Li, Muhua Zhu, Longhua Qian, Min Zhang, and Guodong Zhou. 2019.  Modeling graph structure in transformer for better AMR-to-text generation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5459–5468, Hong Kong, China. Association for Computational Linguistics.

##  Appendix A Hyperparameter details

For AGENDA and WebNLG, a minimum and maximum decoding length were set
according to the shortest and longest target text in the train set. Table 6
lists the hyperparameters used to obtain final results on both datasets. Input
dropout is applied on the word embeddings directly after lookup for node
labels and target text tokens before they are fed into encoder or decoder.
Attention dropout is applied to all attention weights computed during multi-
head (self-)attention.

For hyperparameter optimization, we only train for the first 10 (AGENDA) or 50
(WebNLG) epochs to save time. We use a combination of manual tuning and a
limited number of randomly sampled runs. For the latter we apply Optuna with
default parameters (Akiba et al., 2019; Bergstra et al., 2011) and median
pruning, i.e., after each epoch of a particular hyperparameter run we check if
the best performance so far is worse than the median performance of previous
runs at the same epoch and if so, abort. For hyperparameter tuning, we decode
greedily and measure performance in corpus-level BLEU (Papineni et al., 2002).

Hyperparameter | WebNLG | AGENDA
---|---|---
model dimension $d$ | 256 | 400
# heads | 8 | 8
# encoder layers $L_{E}$ | 3 | 4
# decoder layers $L_{D}$ | 3 | 5
feedforward dimension | 512 | 2000
attention dropout | 0.3 | 0.1
dropout | 0.1 | 0.1
input dropout | 0.0 | 0.1
text self-attention range $n_{t}$ | 25 | 50
graph self-attention range $n_{\delta}$ | 4 | 6
same range $n_{p}$ | 10 | 10
gradient accumulation | 3 | 2
gradient clipping | 1.0 | 1.0
label smoothing | 0.25 | 0.3
$L_{2}$ regularizer | $3\cdot 10^{-3}$ | $3\cdot 10^{-4}$
batch size | 4 | 8
# beams | 2 | 2
length penalty | 5.0 | 5.0
Table 6: Hyperparameters used to obtain final experimental results on WebNLG
and AGENDA.

##  Appendix B Qualitative examples

Table 7 shows three example generations from our Graformer model and the CGE-
LW system by Ribeiro et al. (2020). Often CGE-LW generations have a high
surface overlap with the reference text while Graformer texts fluently express
the same content.

Ref. |  julia morgan has designed many significant buildings , including the los angeles herald examiner building .
---|---
CGE-LW |  julia morgan has designed many significant buildings including the los angeles herald examiner building .
Ours |  one of the significant buildings designed by julia morgan is the los angeles herald examiner building .
Ref. |  asam pedas is a dish of fish cooked in a sour and hot sauce that comes from indonesia .
CGE-LW |  the main ingredients of asam pedas are fish cooked in a sour and hot sauce and comes from indonesia .
Ours |  the main ingredients of asam pedas are fish cooked in sour and hot sauce . the dish comes from indonesia .
Ref. |  banana is an ingredient in binignit which is a dessert . a cookie is also a dessert .
CGE-LW |  banana is an ingredient in binignit , a cookie is also a dessert .
Ours |  a cookie is a dessert , as is binignit , which contains banana as one of its ingredients .
Table 7: Example references and texts generated by CGE-LW (Ribeiro et al.,
2020) and Graformer (marked Ours) for samples from the WebNLG test set. In
case of multiple references, only one is shown for brevity.


# Constraint-Guided Reinforcement Learning: Augmenting the Agent-Environment-
Interaction

Helge Spieker This work has received funding from the European Union under
grant agreement no. 825619 (AI4EU). Simula Research Laboratory
Fornebu, Norway
<EMAIL_ADDRESS>
###### Abstract

Reinforcement Learning (RL) agents have great successes in solving tasks with
large observation and action spaces from limited feedback. Still, training the
agents is data-intensive and there are no guarantees that the learned behavior
is safe and does not violate rules of the environment, which has limitations
for the practical deployment in real-world scenarios. This paper discusses the
engineering of reliable agents via the integration of deep RL with constraint-
based augmentation models to guide the RL agent towards safe behavior. Within
the constraints set, the RL agent is free to adapt and explore, such that its
effectiveness to solve the given problem is not hindered. However, once the RL
agent leaves the space defined by the constraints, the outside models can
provide guidance to still work reliably. We discuss integration points for
constraint guidance within the RL process and perform experiments on two case
studies: a strictly constrained card game and a grid world environment with
additional combinatorial subgoals. Our results show that constraint-guidance
does both provide reliability improvements and safer behavior, as well as
accelerated training.

##  I Introduction

Autonomous systems with self-adaptive or learned components have applications
in a variety of tasks due to the increasing interest in industrial automation,
industry 4.0, or cognitive robotics. However, for the trustful application of
these systems reliability and safety are crucial factors.

Reinforcement Learning (RL) has been successfully applied to control a variety
of applications [1], such as game playing [2], robotics control [3], or
combinatorial optimization [4]. The RL agent explores its environment by
trying random actions and learns through reward signals about its dynamics.
Through sufficient exploration and discovering successful strategies, it
converges towards an optimal policy and solves the problem that is defined by
the environment and its reward function. As an RL agent learns from trial-and-
error, there is no possibility to employ the agent with hard rules or safety
guidelines from the beginning on. And also after training, there are no given
guarantees for the safe and reliable behavior of the agent. Furthermore,
training RL agents is often data-inefficient and takes many iterations of
training runs in sometimes computation-intensive simulations or even more
costly on actual physical devices. These properties of RL agents make it
challenging to deploy them, either as stand-alone agents or as trainable
components within a larger system architecture [5]. Their integration requires
handling uncertainties and to ensure they are applied within their designated
environment in a more strict way than common software components. The RL agent
is not aware that it is receiving inputs that it is not sufficiently trained
for and will be select an action in any case even without having been in the
same or similar state before. An exception to this is Bayesian RL [6] where
uncertainty estimations are considered, but these algorithms have not yet
reached the same level as the more common model-free RL algorithms we
consider.

Contrary to RL, symbolic AI, such as expert systems or constraint solving, can
make decisions based on an explicit constraint model of the environment, but
depending on its complexity, it is often infeasible to model and solve the
environment for every decision. Still, constraint models are data-efficient,
as there is no training, and always avoid unsafe behaviors as defined by the
model.

In this work, we make an argument for the integration of both techniques, such
that the RL agent, also the _learner_ , is guided by an encapsulating
constraint model that describes safety constraints for the agent’s task. We
refer to this integration as _constraint-guided reinforcement learning_ (CGRL)
and it has the goal to design a reliable and safe agent. Within this hybrid
agent, safety models are used to augment the interaction of the RL agent with
its environment to avoid unsafe or undesired actions and behaviors. More
specifically, we discuss three interfaces to augment the agent-environment
interaction: 1) the interface between environment and agent, where external
state information about the environment is observed; 2) the external interface
between agent and environment, where selected actions are transferred to the
environment; 3) the internal decision-making within the agent, to directly
adjust which actions are taken.

Encapsulating RL agents within an outside model for safety or training
purposes has been explored before [7], e.g. in the context of shielding
reinforcement learning agents [8] or imitation learning, where the agent is
shown the behavior of experts and tries to mimic them [9, 10]. Our focus for
the integration within the scope of this work lies on the different interfaces
for augmentation and their effects on the system’s design and reliability. We
further discuss constraint solving techniques to model acceptable behavior or
to define how to act in case of bad decisions from the RL agent.

Developing dedicated encapsulation techniques, represented by the different
constraint models on the interfaces, allows setting strict rules and
guidelines, while not prohibiting the free exploration and decision making of
the agent within the set boundaries. To underline the relevance and motivate
further research in this direction, we discuss the general working mechanisms
of reinforcement learning as well as the potential integration points for an
external constraint model. The implementation of CGRL and its effectiveness is
shown in two case studies. Our results confirm that constraint-guidance is
beneficial for both faster training and better final performance than pure
model-free reinforcement learning.

The main contributions of this paper are: 1) We integrate safety models in the
RL process at the intersection between agent and environment to guide the
decision-making. 2) We present an architecture to implement these models by
using both satisfaction and optimization techniques. 3) We perform an
experimental evaluation of the presented method on two case studies: a card
game and a grid world with a combinatorial puzzle goal.

The remainder of the paper is structured as follows: After reviewing the
necessary background on RL and constraint solving as well as existing works on
their intersection in Sections II and III, we discuss their integration for
constraint-guided RL in-depth in Section IV. In Section V, we implement CGRL
in two environments and evaluate its effects. Before concluding the paper in
Section VII, we discuss the impact and current challenges for CGRL as well as
opportunities for future research in Section VI.

##  II Background

###  II-A Reinforcement Learning

In reinforcement learning (RL) an agent interacts with an environment by
observing the environment’s state $s_{t}$ at time step $t$ and selecting an
action $a_{t}$. From the effect of the action, a reward $r_{t+1}$ is received
and a new state $s_{t+1}$ is reached. The goal of the RL agent is to maximize
the expected return, described as the cumulative discounted reward at time
$t$, that is, $G_{t}=\sum_{k=0}^{\inf}\gamma^{k}r_{t+k+1}$, where
$\gamma\in[0,1)$ is the discount factor. More formally, the environment is
characterized by the tuple $\langle S,A,T,R\rangle$, with $S$ being the set of
states in the environment, $A$ being the set of actions. $T:S\times
A\rightarrow S$ is the transition function from the execution of an action in
one state leading to another state and $R$ is the reward function, which
assigns a numerical feedback to an action in a state $r:S\times
A\rightarrow\mathbb{R}$.

The agent follows a trainable policy $\pi$ from which it chooses the action in
each state $\pi:S\times A\rightarrow[0,1]$. The policy assigns each action $a$
a probability to be taken and from this probability distribution either the
action with highest probability is picked greedily or it is randomly sampled
to encourage exploration. This general agent-environment interaction process
is shown in Figure 1, including extensions for CGRL which we will discuss at a
later point. The agent interacts with the environment in finite episodes,
which means that some states are terminal states and once these states are
reached, the episode is over and a new episode starts. Terminal states can
represent both desired goal states, e.g. in a maze where a certain location
has to be reached, but also undesired states, e.g. the agent performs illegal
or unsafe behavior. For a detailed introduction to RL, we refer the interested
reader to the book by Sutton and Barto (2018).

Over the recent years, deep RL, where the action selection policy is
approximated by deep neural networks, has received large attention and many RL
algorithms have been proposed in the literature [1], for example, Proximal
Policy Optimization (PPO) [11] which we use throughout the experiments in this
paper. These algorithms share, that they represent the state as input to the
neural network and receive a vector of action scores as output. These scores
are interpreted as probabilities and the action is randomly sampled or
greedily chosen by the highest score. The state representation is usually
problem-specific. For problems where the state resembles a form of spatial
information, e.g. images, convolutional neural networks (CNN) are commonly
used, whereas otherwise fully-connected feed-forward neural networks are
common.

We use PPO in an actor-critic way [12], where the agent is modeled by two
neural networks. The first network, the actor, outputs the scores for each
action as described above. The second network has only a single output that
predicts the expected reward for the current state. Both networks usually
share the same architecture and also the weights of the initial layers with
the only difference being the final layers, where the actor has as many
outputs as actions, the critic only has a single real-valued output. Using a
critic network helps to stabilize and accelerate the learning process since it
allows to compare the current policy against the earlier made experiences and
supports the improvement of the policy.

###  II-B Constraint Solving

Throughout this paper, we refer to constraint solving in the context of
modeling the acceptable behavior of a learner, like the RL agent, which is
either a satisfaction problem, when asking ”Does the learner behave according
to the specification?”, or an optimization problem when asking ”What is the
state representation or action that complies with the specification with only
minimal changes?”. Modeling a satisfaction problem allows to identify
undesired states and actions, but does not guide the learner, except when
designing each individual action as separate problems. The optimization model
instead allows augmenting the state or action towards specification
compliance, according to its constraints.

Formally, we define a _constraint satisfaction problem_ (CSP) as a triple
$\langle\mathcal{X},\,\mathcal{C},\,\mathcal{D}\rangle$ where
$\mathcal{X}=\\{\mathbf{x}_{1},\dots,\mathbf{x}_{n}\\}$ is a set of variables,
$\mathcal{C}$ is a set of constraints $\mathcal{C}=\\{c_{1},\dots,c_{m}\\}$,
where each constraint $c_{i}$ involves a subset of the variables. Each
variable $\mathbf{x}_{i}$ is also associated with a finite integer domain
$\mathcal{D}(\mathbf{x}_{i})$ of all its possible values. A variable
assignment $\theta$ satisfies the CSP
$\langle\mathcal{X},\,\mathcal{C},\,\mathcal{D}\rangle$, if each variable $x$
has a value assigned from its domain $D(\mathbf{x}_{i})$, such that none of
the constraints $\mathcal{C}$ are violated. A _constraint optimization
problem_ (COP) extends the CSP formulation by an objective function $f_{z}$,
which is calculated over a subset of the variables, with an objective value
$z$, which, in our context, is to be minimized, while the variable assignment
$\theta$ still satisfies the constraints $\mathcal{C}$. For a detailed
overview on constraint solving, we refer the interested reader to [13].

The constraint model can be modelled and solved by dedicated constraint
solving libraries, e.g. MiniZinc or Essence. This has the advantage of having
solver-provided guarantees for the correctness of results - under the
assumption of a correct model - and tools optimized for the task, but with the
disadvantage of increasing system complexity due to additional libraries and
related dependencies. The alternative would therefore be to implement the
constraint model within the programming paradigm of the autonomous system. In
this case, there are no additional external dependencies, but the
implementation is potentially more error-prone since constraint modeling
languages are usually more expressive for the tasks than general-purpose
programming languages. We will come back to the discussion between these two
alternatives in the discussion part of the paper in Section VI.

##  III Related Work

The main areas of related work are safe, ethical, or social reinforcement
learning and the design of autonomous systems. The work closest to ours is the
method of _Shielded Reinforcement Learning_ by Alshiekh  _et al._ [8] . The
authors propose a safety framework where a shielding component is deployed
either between the environment and the agent or after the agent has made its
action selection. The shield represents a safety specification, based on
temporal logic, that assures the correctness of the system. This is related to
our method, which also considers integrating a constraint-guidance component
at the same interfaces.

Similar works have been based on using barrier functions [14] or provable
formal theories of the acceptable behavior specifications of the RL agent
[15], or focus on specifics of the RL environment, e.g. stochastic dynamics in
robotics [16]. These approaches focus mostly on the provable aspects of the
formalization, and strongly motivate the necessity and feasibility of hybrid
approaches, but focus less on the aspects of how they are implemented and
expressed. A further avenue is the design of RL methods that have safety
inherently in their functional methodology, e.g. [17, 18]. Unlike these
methods, we provide safety extensions to any form of RL agent, even without
inherent safety notion. We see an advantage in a modular approach, however, we
do not argue that one or the other is necessarily better. Finally, for an in-
depth overview on safe reinforcement learning, we refer to the survey by
García and Fernández [7].

Understanding and steering how agents behave and learn in unknown environments
also affects ethical concerns and is an aspect of active research to include
ethical standards as boundaries for the agents’ behavior [19]. For example,
Noothigattu  _et al._ explore the effects of imposing ethical constraints on a
Pacman agent, such that it is prohibited to eat ghosts [20]. The consideration
of ethics for learning agents is of relevance and imposing constraint-
guidance, based on models that capture ethical constraints, proposes an
approach towards this challenge. Another area of interest is to let the agent
learn which actions are either not safe, not desired, or just unfeasible in a
given state. Zahavy  _et al._ [21] propose a method where the agent learns
which actions not to choose in a given state. Learning when an action is
infeasible and should be avoided or when it is just not available has been
part of teaching an agent’s policy, where the agent learns which actions to
avoid, but without an explicit specification of wrong and forbidden actions.

##  IV Integrating Constraints and RL

To achieve constraint-guided reinforcement learning, the constraint model
needs to be integrated within the agent-environment process. In this section,
we identify and discuss the three interfaces for constraint-guidance (Figure
1) and their impacts on the functionality and the autonomy of the encapsulated
RL agent (Figure 2).

RL Agent Environment Action $a_{t}$State $s_{t+1}$Reward $r_{t+1}$123

Figure 1: The Agent-Environment Process with constraint-guidance integration:
(1) Environment-Agent, (2) External Agent-Environment, (3) Internal Agent-
Environment.

(a) Environment-Agent (b) External Agent-Environment (c) Internal Agent-
Environment

Figure 2: Effects of the augmentation interfaces on the observation and action
space. The Environment-Agent interface augments the observation space to map
unseen or unsafe observations to a familiar environment in which the agent can
safely act. The Agent-Environment interfaces replace unsafe actions by a safe
default (External) or limit the availability of actions for the agent before
selection (Internal). The safety of an action depends on the observation and
can vary from step to step.

One integration point lies at the interface between the environment and the
agent, where observations and rewards are received. The second integration
point addresses the interaction from the agent to the environment, i.e., when
an action is issued by the agent. These two interfaces wrap the RL agent as a
black-box and manipulate the inputs and outputs of the agent. The third
integration point, on the other hand, lies within the agent and allows to
apply constraint-guidance in the internal mechanisms of the RL agent. Relating
to the existing literature, the first two interfaces are similar to the work
by Alshiekh _et al._ [8] when their proposed shielding is introduced either
before or after the action selection part. The constraint models for each of
the interfaces are modeled based on a risk- and safety-analysis of the system.
The approach is to formalize the most essential boundaries for the agent’s
behavior without restricting the agent’s freedom within these boundaries more
than necessary. We discuss each of the three integration types in the
following and consider the interfaces that have to be implemented by a
constraint-guidance mechanism.

###  IV-A Environment-Agent Interface

The Environment-Agent Interface augments the transfer of state information
from the environment to the agent in a form of state preprocessing. By
augmenting the state information, either additional information can be added
to the state, or parts of the state can be masked or modified to avoid unsafe
decisions. One application of this is to reduce the decision space for the RL
agent. Aspects of the state, which would lead the agent to act in a specific,
but potentially dangerous way, are replaced by safe dummy values or a
representation that does not lead to a certain action, but also does not
misrepresent the actual state space. For example, when having an agent with an
inventory of items, those items which are dangerous to be used in the current
state can be omitted from the augmented state that is given to the agent.

######  Definition 1 (Environment-Agent Interface).

The interface function $f:S\rightarrow S$ augments the observed state, such
that the difference diff($s_{t},s^{\prime}_{t}$) is minimized while following
side constraints $\mathcal{C}_{Env}$, and returns a modified state
$s^{\prime}_{t}$.

Technically, the augmentation component is based on a constraint model
$c(s_{t})=s^{\prime}_{t}$, that specifies potentially dangerous states, and
can make modifications $c(s)$ receives a state $s_{t}$ and returns a state
$s^{\prime}_{t}$, which can be identical to the original state if $s_{t}$ is
not considered dangerous, or modified to exclude or mask the undesired parts
of the state.

To implement this interface in an _Observation Mask_ model, that augments the
observed state for the agent, a constraint optimization model can be used. The
instance parameters are the observed state, the decision variables are the
augmented state, and the objective function measures the changes between the
observed and augmented state. During optimization, the augmented state is
adjusted such that the state complies with the modeled specification, e.g.
unusable items from an agent’s inventory are masked while making as few
modifications as possible. Making only minimal changes is relevant to keep the
augmented state close to the actual observation because large changes can lead
the agent to make an unsuitable decision for the actual state and thereby
hinder the success within the environment.

###  IV-B External Agent-Environment Interface

Once the agent selected an action, this action is passed back to the
environment to be executed. At this point, the _Agent-Environment Interface_
augments the selection and can interfere by observing both the most recent
state and the selected action in order to decide whether the chosen action is
acceptable or violates some guidance criterion, e.g. being unsafe or
potentially harmful. In case the action is not accepted, the interface can
replace the selected action following a heuristic procedure. This replacement
action might not be optimal as it does not follow the learned strategy but can
avoid unsafe outcomes instead.

######  Definition 2 (External Agent-Environment Interface).

The interface function $f:S\times A\rightarrow A$ receives the last observed
state $s_{t}$ and the taken action $a_{t}$ as input and returns a, probably
modified, action $a^{\prime}_{t}$. Action $a^{\prime}_{t}$ must obey the
constraints $\mathcal{C}_{Env}$ for the environment and the last observed
state.

An _Action Replacement_ model can be implemented either as a satisfaction
model, that validates whether an action follows the specification and replaces
invalid actions by a default action or as an optimization model that has a
notion of distance between actions and can optimize the action change to be
minimal while following the specification. The Agent-Environment Interface
forms thereby a fallback strategy that monitors the RL agent’s behavior and
only if it does not behave according to the specified acceptable behavior, its
decisions are overruled.

###  IV-C Internal Agent-Environment Interface

The first two augmentation interfaces are decoupled from the RL agent and see
it as a black-box. The third interface, _Internal Agent-Environment Interface_
, is integrated within the action selection mechanism of the RL agent.

While augmenting the observation and checking the selected action against a
constraint model allow to prohibit undesired or unsafe behavior, the RL agent
is not aware of this constraint-guidance and does not learn that its action
was overruled by an external mechanism. That means the agent does not learn to
avoid this action the next time the same state is encountered and the observed
reward does not match the selected action. The internal integration into
action selection overcomes this, but at the cost of requiring access inside
the agent, unlike the previous interfaces.

######  Definition 3 (Internal Agent-Environment Interface).

The interface function $f:S\rightarrow\mathbb{R}^{n}$ where $n$ is the number
of available actions: $f(s_{t})=m$. Each action is assigned a masking score,
which is inserted into the policy $\pi$ and multiplied with the network
outputs before selecting an action. From the masked output, the action
selection is continued with a bias towards actions favored by $f$.

Using constraint-guidance, the scores of the individual actions can be
adjusted to either discourage unwanted actions by decreasing their score or to
encourage the selection of desired actions by increasing their score. In the
simplest case, $m$ is a boolean vector where each action is masked as
allowed/available or unavailable for the current state. Any of these
adjustments steer the RL agent towards selecting desired actions for which
then a reward is received and the policy is trained with the normal training
procedure.

An _Action Mask_ model, that implements the internal agent-environment
interface, can be interpreted as a constraint satisfaction model with one
decision variable per action, where a solution enables all allowed actions for
the given state.

###  IV-D Deriving Constraint Models

All interfaces require the existence of a constraint model for augmentation.
There are different ways to derive these constraint models and how to
formulate them. The first option, which we consider mostly in this paper and
for the experimental evaluation, is to have the constraint model handcrafted
from expert knowledge. This knowledge can either stem from precisely analyzing
error causes and avoiding these situations or setup generic rules for unsafe
states and actions that are known to cause unrecoverable error situations.

The second option targets to iteratively refine the constraint model through a
dedicated learning process, for example using constraint acquisition or
learning [22]. This process would require access to a safe simulation
environment as the initial set of rules cannot be expected to be safe. Over
subsequent iterations, the RL agent can act using the initial constraint
model, and, in case of unsafe situations and error cases, the provoking states
and actions are used to refine the constraint model via a constraint learning
step. We do not further consider this option in this work, but leave it as a
promising direction for future work on CGRL.

##  V Experiments

In the following section, we apply constraint-guided reinforcement learning in
two environments. The structure for each case study environment follows the
same approach. At first, we introduce the problem setting, the available state
information for the RL agent, and the reward structure. Afterwards, we discuss
the constraint-guidance models to integrate with the RL agent. In each
environment, we consider three constraint-guidance models, one for each of the
integrations previously discussed, and a vanilla RL agent without constraint-
guidance as a baseline for comparison.

Figure 3: Architecture: The constraint-guidance model acts as a wrapper and
has first access to observations and final control over the selected actions.

The RL algorithm is PPO (Proximal Policy Optimization) [11]111The PPO
implementation is available here: github.com/lcswillems/torch-ac. All runs use
the same hyperparameters, which closely follow the defaults proposed by the
authors, except for the network architecture, which is adjusted for each
environment.

###  V-A Environment I: Card Game

####  V-A1 Scenario & Rules

In the first experiment, we focus on a card game, modeled after “The
Game”222The Game: Are you ready to play The Game? (2015). Created by Steffen
Benndorf. Published by Nürnberger-Spielkarten-Verlag.. The goal of the game is
to distribute 98 unique cards, ranging from 2 – 99, onto four card piles. Two
of these card piles are to be filled in increasing order from 1 – 100, the
other two in decreasing order from 100 – 1. It is only allowed to place cards
with a higher respectively lower card value on each of the piles, otherwise
the action is invalid. There is one exception to this rule. A lower
respectively higher card value can be played if the difference in card value
is exactly 10, i.e. if the increasing pile has card 42 on top, card 32 is
allowed on top of it.

The game ends when all cards have been distributed or there is no further move
possible. The original card game can be played with 1–5 players, in this case
study we focus on the single player version, where the player has 8 cards on
their hand and refills their hand from the stack after having played two
cards.

####  V-A2 Environment & Agent

The state is represented by a 12-dimensional vector, consisting of the four
card piles and the eight hand cards, sorted in increasing order. If a slot for
a hand card is empty, because a card was played and no new cards were drawn
yet, it is replaced by a placeholder value of $-1$. The agent can place any
hand card on any of the card piles, leading to a total of $8\times 4=32$
possible actions. The agent’s policy is represented by a feed-forward neural
network with three fully connected layers of each 32 hidden nodes with tanh
activations. Both the actor and the critic network share the weights of the
initial layers.

The agent receives a positive reward of $r=0.1$ for each valid move it plays
and a negative reward of $r=-0.1$ for each invalid move. At the end of the
round the final reward equals the number of played cards, i.e. at most 98.

####  V-A3 Constraint-Guidance Models

We define the CGRL models such that invalid actions are avoided, but do not
impose are restrictions on the inner RL agent. If an action has to be selected
through constraint-guidance, it greedily picks that action which has the
smallest difference between the card piles and the hand card value.

Observation Mask The Environment-Agent Interface is implemented such that
cards with only negative effects, i.e. they cannot be played on any of the
card piles, are hidden from the RL agent by showing that these card slots are
empty. If all cards can be placed on at least one of the piles, no changes are
made.

Action Replacement The External Agent-Environment Interface monitors the
selected action for invalid card placements, which would result in a negative
reward penalty. These actions are heuristically replaced by that action which
incurs the smallest step on any of the card piles, i.e. that card which the
minimum difference between card and pile value.

Action Mask The internal environment-agent interface behaves similar to action
replacement, but instead of replacing the action after it has been selected,
it masks those actions which are invalid. This enforces the agent to always
select a valid action and focuses the exploration towards understanding good
game strategies without having to learn about the validity of actions. Further
variants can be considered, for example, it is possible to enforce playing
cards where the special rule of decreasing/increasing the card pile in the
”wrong” direction can be used. But, this goes beyond the usage of constraint-
guidance for safety aspects and enforces a particular playing strategy upon
the agent, which would be less comparable to the other models.

####  V-A4 Results

The reward curves of the four different agents over a training time of 50
million frames are shown in Figure 4. We train the RL agent such that it runs
multiple environments in parallel to collect experiences for training. This
rollout both allows to run the training in parallel on multiple CPU cores as
well as it stabilizes it, because more diverse states and rewards are
available. We show both the best and the average rewards of 64 training
environments.

01020304050Number of Steps ($\displaystyle\times
10^{6}$)01020304050607080RewardRL onlyAction MaskAction ReplacementObservation
Mask

Figure 4: Card Game: Maximum (solid lines) and average (dotted) rewards with
and without masking. We show the mean and std. dev. over 10 training runs.

The results show a strong impact of constraint-guidance over the RL-only
agent, but they also show differences between the different integration
techniques. The best performance is reached with Action Mask model, which
implements the internal agent-environment interface, and manipulates the
available actions by removing invalid actions. Its performance surpasses that
of the other agents from the beginning and quickly reaches a high level.

The other models follow a similar learning curve but are shifted in their base
performance, which we attribute to the effects of the different augmentation
models. Augmenting the observations, i.e. removing hand cards that are not
possible to be played in the current state, is the least beneficial mask in
this scenario, and also causes instability in the training process visible by
the high fluctuation at around 49 million frames. This is caused by the game
mechanics, where only in few cases a card is actually invalid to be played on
all four card piles. It is much more common that a card is only invalid for a
few piles, but this cannot be modeled in our setup by augmenting only the
observation, but requires adjusting the actions, like the Action Mask does it.
Still, it can be helpful and performs better than RL only.

Regarding the training duration until the agent’s performance converges and
does no longer improve by a large margin, we observe faster convergence when
using the action mask model compared to the external augmentation. The RL only
and the Observation Mask models steadily improve over a longer time, but their
main performance level is reached in a similar time than the others.

###  V-B Environment II: Grid World Puzzle

####  V-B1 Scenario & Rules

The second environment is a puzzle variant of the grid world problem. The
agent is placed in a random 2D grid world environment, consisting of four
rooms, and has the goal to collect a number of distinct items before finding
the exit door of the grid world (see Figure 5). It can move forward, turn left
or right, or pickup an item that is in front of the agent. Every item is
described by its shape (key or circle) and its color. The goal is to pick one
item of each type and reach the exit door in as few steps as possible.

Figure 5: Grid World Puzzle: The agent (red arrow with observable space
highlighted) has to collect 16 items (circles and keys in 8 colors) before
reaching the goal (green square).

This environment poses two challenges for the agent: 1) The visible state of
the grid world is limited to the eight surrounding tiles next to the agent’s
position, which requires exploration of the environment; 2) the agent needs to
learn to avoid items that it has already collected. The inventory of already
collected items is part of the agent’s state and given to the agent at each
step.

####  V-B2 Environment & Agent

The total grid world environment is $32\times 32$ tiles, divided into four
equally sized rooms connected with open doors. Both the placement of doors and
the items is randomly generated for each new environment. The state of the
environment is represented by the agent’s field of view, $7\times 7$ fields,
and its current inventory, listing all collected items. Grid world tiles can
be either a plain field, a field with an item, or the exit door, all of which
can be accessed by the agent at any time, or a wall, which blocks the agent
and cannot be accessed. The set of actions is
$a\in\\{\text{forward},\text{left},\text{right},\text{pickup}\\}$. The agent’s
policy is represented by a small convolutional neural network with three 2D
convolutional layers followed by two fully connected layers. Each layer is
connected with ReLU activation functions. Again, both the actor and the critic
network share the weights of the initial layers.

The reward function is modeled such that the agent receives a positive reward
of $1/16$ for each distinct object it collects. Collecting a duplicate item,
that is already in the inventory, causes a negative reward of $-1$ and ends
the episode. The maximum length of an episode are $8192$ steps, once this
number of steps is reached, the episode is also terminated. When the exit door
is reached, the agent receives an additional reward of
$1-0.8\times\text{Number of steps}/8192$. This reward function does only
return sparse rewards at specific events instead of continuously giving
feedback to the agent, which is contrary to the card game environment, where
every action of the agent is rewarded by the environment. The implementation
of this environment is based on the _MiniGrid_ project [23] with extensions
for the additional puzzle objective.

####  V-B3 Constraint-Guidance Models

The goal of the constraint-guidance models for the grid world puzzle
environment is to avoid collecting duplicate items, i.e. the undesired
behavior.

Observation Mask The model for augmenting the observed states from the
environment hides any duplicate item from the observed state and masks it as a
wall. This signals to the agent, that the masked tile is not of interest and
encourages the agent to further explore or focus on another, unmasked item.

Action Replacement When the agent decides to move to a tile with a duplicate
item, this model observes this specification violation and replaces the move
by turning right.

Action Mask To avoid picking duplicate items, the action mask disables the
action to pick an item as long there is no distinct new item in front of the
agent. Thereby the agent can either move, as long as there is no new item in
front of it, or it is set to pick a new item, which disables the movement.
This guidance model removes the logic for picking items from the learned
agent, which is then only concerned with navigation towards distinct items.

####  V-B4 Results

The results, in form of training curves, are shown in Figure 6. As in the
previous experiment, we trained the agents with 64 environments and parallel
and report both the best and average performance over time, repeated with 10
different random seeds.

01020304050Number of Steps ($\displaystyle\times
10^{6}$)-0.250.000.250.500.751.001.251.501.75RewardRL onlyAction MaskAction
ReplacementObservation Mask

Figure 6: Grid World Puzzle: Maximum (solid lines) and average (dotted)
rewards with and without masking. Shown is the mean and standard deviation
over 10 training runs.

Models using constraint-guidance perform better than the RL-only agent, with
the average CGRL performance being competitive to the best rewards of the RL-
only. This results show the general difficulty of the environment for a
standard RL algorithm. The average reward is close to the minimum reward that
is received for successfully reaching the exit door, but does not show signs
for increased attention towards successfully collecting unique items. The CGRL
models on the other hand achieve higher rewards, with the Observation Mask
model, that excludes already collected items from the observed state,
performing best before the Action Mask and Action Replace models. We further
observe a faster performance increase in the Action Mask model than in the
eventually better Observation Mask model. While the observation mask excludes
already collected items from the observed state by presenting them as walls,
the agent still can walk towards them and collecting them, as the selected
action is not augmented. As the agent needs to learn that walls cannot be
accessed, the observation mask is not as effective as the action mask in the
beginning. The action mask, which was most effective in the card game,
disallows the agent to access fields with already collected items, but only
when the agent stands directly in front of the item. Before that state is
reached, the agent can still plan to collect the item, if it has not learned
to avoid duplicates. This can cause the lower performance of this mask.

##  VI Discussion

Both performed experiments showed the effectiveness of CGRL for guiding a RL
agent in complex environments. This result confirms our expectations, since we
introduce external domain knowledge into the training process and the agent’s
behavior. However, we also observe a better data-efficiency of the training
and the avoidance of unsafe behavior, as confirmed by higher rewards. Better
data-efficiency is important when a single step of the RL agent is more costly
than in the small and computationally cheap environments used here, e.g. when
running a complex physical simulation or even using physical components, there
it is especially useful to model the acceptable behavior via a constraint
model. In addition to the physical environment, where unsafe behavior might be
harmful for the machine or the physical environment, the avoidance of unsafe
behavior is crucial for the application and deployment to either safety-
critical or ethically challenging environments.

A challenge in the application of CGRL can occur from the additional runtime
overhead added from the constraint solving for augmentation. As the model has
to be run for every step of the RL agent a small overhead can accumulate to a
longer runtime. However, this limitation mostly applies only in cases where
the overhead is significant in relation to the general computational cost of
one step in the environment. In an environment where every step is already
costly, the benefits of faster training and less undesired behavior will
exceed the disadvantage of a runtime overhead.

As future work on CGRL, besides the challenges raised, we plan to extend the
method to environments with more complex state representations. Here it can be
necessary to additionally preprocess the observation before constraint
reasoning can be applied. Another direction is to adopt principles from
imitation learning, where expert behavior can be observed, to learn
augmentation rules, e.g. via constraint acquisition [22], as addressed in
Section IV-D. This way, CGRL would first learn a static constraint model for
guidance and then allow an RL agent to learn a strong policy within its
specification.

##  VII Conclusion

We presented Constraint-Guided Reinforcement Learning (CGRL), a method to
combine constraint solving and reinforcement learning into a hybrid agent that
behaves according to a specification, but is otherwise free to explore and
learn the best policy for the problem. CGRL augments the interfaces between
the RL agent and the environment through constraint models, which specify
acceptable behavior that the agent should comply to. Constraint solving acts
here as a safety fallback for the encapsulated RL agent.

Augmentation can happen by changing the state observation from the environment
to exclude certain aspects in order to encourage the agent towards accepted
behavior, but it can also observer the actions made by the agent and adjust to
avoid behavior that violates the specification. Finally, a third potential
interface for constraint-guidance is to augment the action selection process
within the agent – unlike the first two approaches, which consider the RL
agent as black-box – and mask actions that would violate the specification.

## References

  * [1] Kai Arulkumaran, Marc Peter Deisenroth, Miles Brundage and Anil Anthony Bharath  “Deep Reinforcement Learning: A Brief Survey”  In _IEEE Signal Processing Magazine_ , 2017
  * [2] Niels Justesen, Philip Bontrager, Julian Togelius and Sebastian Risi  “Deep Learning for Video Game Playing”  In _IEEE Transactions on Games_ , 2019
  * [3] Jens Kober, J. Bagnell and Jan Peters  “Reinforcement Learning in Robotics: A Survey”  In _The International Journal of Robotics Research_ , 2013
  * [4] Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina and Le Song  “Learning Combinatorial Optimization Algorithms over Graphs”  In _NeurIPS_ , 2017
  * [5] Gabriel Dulac-Arnold, Daniel Mankowitz and Todd Hester  “Challenges of Real-World Reinforcement Learning”  In _ICML Workshop on Real-Life Reinforcement Learning_ , 2019
  * [6] Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau and Aviv Tamar  “Bayesian Reinforcement Learning: A Survey”  In _Foundations and Trends® in Machine Learning_ , 2015
  * [7] Javier García and Fernando Fernández  “A Comprehensive Survey on Safe Reinforcement Learning”  In _JMLR_ , 2015
  * [8] Mohammed Alshiekh, Roderick Bloem, Ruediger Ehlers, Bettina Könighofer, Scott Niekum and Ufuk Topcu  “Safe Reinforcement Learning via Shielding”  In _AAAI_ , 2018
  * [9] Bob Price and Craig Boutilier  “Accelerating Reinforcement Learning through Implicit Imitation”  In _JAIR_ , 2003
  * [10] Jonathan Ho and Stefano Ermon  “Generative Adversarial Imitation Learning”  In _NeurIPS_ , 2016
  * [11] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford and Oleg Klimov  “Proximal Policy Optimization Algorithms”, 2017  arXiv:1707.06347 [cs]
  * [12] Volodymyr Mnih et al.  “Asynchronous Methods for Deep Reinforcement Learning”  In _ICML_ , 2016
  * [13] Francesca Rossi, Peter Van Beek and Toby Walsh  “Handbook of Constraint Programming (Foundations of Artificial Intelligence)”, 2006
  * [14] Richard Cheng, Gabor Orosz, Richard M. Murray and Joel W. Burdick  “End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks”  In _AAAI_ , 2019
  * [15] Nathan Fulton and André Platzer  “Safe Reinforcement Learning via Formal Methods: Towards Safe Control Through Proof and Learning”  In _AAAI_ , 2018
  * [16] Shuo Li and Osbert Bastani  “Robust Model Predictive Shielding for Safe Reinforcement Learning with Stochastic Dynamics”  In _ICRA_ , 2020
  * [17] Joshua Achiam, David Held, Aviv Tamar and Pieter Abbeel  “Constrained Policy Optimization”  In _ICML_ , 2017
  * [18] Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman and Mohammad Ghavamzadeh  “A Lyapunov-based Approach to Safe Reinforcement Learning”  In _NeurIPS_ , 2018
  * [19] Francesca Rossi and Nicholas Mattei  “Building Ethically Bounded AI”  In _AAAI_ , 2019
  * [20] Ritesh Noothigattu et al.  “Interpretable Multi-Objective Reinforcement Learning through Policy Orchestration”, 2018  arXiv:1809.08343 [cs]
  * [21] Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz and Shie Mannor  “Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning”  In _NeurIPS_ , 2018
  * [22] Christian Bessiere, Frédéric Koriche, Nadjib Lazaar and Barry O’Sullivan  “Constraint Acquisition”  In _Artificial Intelligence_ , 2015
  * [23] Maxime Chevalier-Boisvert, Lucas Willems and Suman Pal  “Minimalistic Gridworld Environment for OpenAI Gym”  In _GitHub repository_ , 2018