Hierarchical variational models, such as LadderVAE, are prone to local minima
and posterior collapse, and TreeVAE shows similar behavior. Therefore, few
technical choices, such as batch normalization and KL annealing, are needed to
converge to a desirable optimum. For all datasets, we train TreeVAE only on
the training set and evaluate the trained model on the separate test set.

####  E.1.1 Training the Tree

For MNIST, Fashion-MNIST, Omniglot, and 20Newsgroup, the trees are trained for
$M=150$ epochs at each growth step, and the final tree is finetuned for
$M_{f}=200$ epochs. To reduce the risk of posterior collapse during training,
we anneal the KL terms of the ELBO. Starting from $0$, we increase the weight
of the KL terms every epoch by $0.001$ except for the final finetuning of the
full tree. Here, we linearly increase the weight by $0.01$ until we reach $1$,
such that the final model is trained on the complete ELBO. Additionally, for
the aforementioned datasets, we finetune the full tree after every third
growing step for $80$ epochs with KL annealing of $0.001$, so the otherwise
frozen parameters can adapt to the new structure. For CIFAR-10, CIFAR-100, and
CelebA, the splits are mostly determined by the contrastive losses, and
therefore, we avoid finetuning the full tree to reduce the computational time.
The KL term is annealed every epoch by $0.01$ such that the weight reaches $1$
after $100$ of the $150$ epochs every growth step. While the annealing
procedure is required to achieve good performances, the exact annealing decay
plays a smaller role in the final performances, as well as the in-between
finetuning of the trees, and the number of epochs at each training step.

####  E.1.2 Augmentations

Due to the scarcity and heterogeneity of Omniglot, we trained our models using
data augmentation by randomly rotating images by up to $\pm 10$ degrees,
horizontally/vertically shifting images by up to $\pm 2$ pixels, applying up
to $1\%$ shearing, and zooming by up to $\pm 10\%$. Note that for Omniglot, no
contrastive learning was applied; the augmentations were solely used for
overcoming the scarcity of data points.

On the other hand, in CIFAR-10, CIFAR-100, and CelebA, augmentations were
applied to use contrastive learning as introduced in Section 2.6 and Appendix
E.3. For CIFAR-10 and CIFAR-100, first, each image is randomly cropped and
resized with scale $\in(0.2,1)$ and aspect ratio $\in(3/4,4/3)$. Second, each
image is randomly flipped in the horizontal direction with probability $0.5$.
Third, with probability $0.8$, color changes are performed, which consist of
changes in brightness, contrast, and saturation, all with their respective
factors $\in(0.6,1.4)$, as well as change in hue with its parameter
$\in(-0.1,0.1)$. Lastly, with probability $0.2$, we transform the image to
grayscale. The chosen parameters are largely adopted from Li .’s (2022) weak
augmentation scheme.

While these augmentations lead to superior group separation, in CelebA, we are
also interested in generative results. Therefore, to obtain generations
without non-sensical artifacts, we reduce the augmentation strength by
removing the hue and grayscale augmentations, reducing the other color
parameters by a factor $2$, and reducing the cropping parameters to scale
$\in(3/4,1)$ and aspect ratio $\in(4/5,5/4)$.

###  E.2 Model Architecture

In general, model architectures for all datasets are similar and consist of an
encoder, followed by the tree structure with the transformations, routers, and
the bottom-up, as depicted in Figures 2 and 3, and identical decoders for each
leaf of the tree. We always apply batch normalization followed by Leaky ReLU
non-linearities after all convolutional and dense layers. For further details
on the specific implementation of the sections below, we direct the reader to
consult the accompanying code.

####  E.2.1 Transformations/Bottom-Up

The architecture of the transformations and the bottom-up is identical across
all experiments. They take as input the previous latent vector of dimension
$4$ (20Newsgroup), $8$ (MNIST, Fashion-MNIST, Omniglot), or $64$ (CIFAR-10,
CIFAR-100, CelebA) and map them to some intermediate representation of
dimension $128$ (20Newsgroup, MNIST, Fashion-MNIST, Omniglot), or $512$
(CIFAR-10, CIFAR-100, CelebA) using a dense layer, followed by a dense layer
without activation to compute $\mu$ and one with Softplus activation to
compute $\sigma$ of the approximate posterior/conditional prior of the
respective tree level.

####  E.2.2 Routers

Similar to transformations, the architectures of routers are identical across
all experiments. The generative routers take as input ${\bm{z}}_{i}$, the
latent representation of a node $i$, while the inference routers use
$\mathbf{d}_{depth(i)}$. Then, both sequentially apply two dense layers that
both map them to $128$ (20Newsgroup, MNIST, Fashion-MNIST, Omniglot), or $512$
(CIFAR-10, CIFAR-100, CelebA) dimensions, after which a final dense layer with
a Sigmoid activation function computes the probability of the binary decision
that infers the next child node.

####  E.2.3 MNIST/Fashion-MNIST

Figure 18: MNIST and Fashion-MNIST encoder architecture.

For MNIST and Fashion-MNIST we use identical encoder/decoder architectures.
Both datasets have inputs of dimension $28\times 28$ and $8$ dimensional
latent spaces. We use a small encoder as depicted in Figure 18, and a
symmetric decoder. The encoder uses $3\times 3$ convolutions with stride $2$,
whereas the decoder uses transposed convolutions.

####  E.2.4 20Newsgroups

Figure 19: 20Newsgroups encoder architecture.

20Newsgroups is a text dataset, so the encoder/decoder architecture differs
from the other experiments. The samples of 20Newsgroups are preprocessed in
such a way, that the input becomes a $2000$D vector (see Section D.3). Hence,
the encoder for 20Newsgroups is a simple MLP with $5$ dense layers, as
depicted in Figure 19, and the decoder again mirrors the encoder architecture.

####  E.2.5 Omniglot

Figure 20: Omniglot encoder architecture.

For Omniglot, we use an architecture similar to the one for MNIST and Fashion-
MNIST. In contrast to Section E.2.3, we increase the receptive field of the
encoder by using $4\times 4$ convolutions and make it $4$ times wider and $2$
times deeper. We refer to Figure 20 for a schematic of the encoder. As in the
other architectures, the decoder is symmetric to the encoder.

####  E.2.6 CIFAR-10/CIFAR-100/CelebA

Figure 21: CIFAR-10, CIFAR-100, and CelebA encoder architecture. The initial
convolutional layer comprises a ResnetBlock, while the remaining convolutional
layers additionally incorporate average pooling prior to the ResnetBlock.

For real-world image datasets, more complex architectures are required. We
first define a ResnetBlock as two consecutive convolutions with kernel size
$3$ and stride $1$, whose output gets weighted by $0.1$ and combined with a
residual connection to the input of the first convolution. In case input and
output dimensions do not match, the residual connection consists of a
convolution with kernel size $1$ and stride $1$ to match dimensionality. The
encoder consists of consecutive ResnetBlocks with 2D average-pooling of kernel
size $3$ and stride $2$. Here, number of filters per ResnetBlock are
increasing by a factor of $2$, starting from $32$ and going up to $256$ until
the representation is $4\times 4\times 256$, at which point we flatten it to
get $\mathbf{d}_{L}$. We refer to Figure 21 for a schematic of the encoder.
The decoder structure is similar to the reversed encoder, where the pooling
layers are replaced by 2D upsampling with bilinear interpolation and before
the ResnetBlocks, we pass the input through a dense layer and consecutive
reshaping in order to match the expected input dimensions. Slight differences
are required for CelebA due to the higher resolution. To arrive at the same
internal representation, we add one more ResnetBlock with 256 filters to the
encoder, as well as one more ResnetBlock at the start of the decoder, starting
from $16$ instead of $32$ filters.

###  E.3 Contrastive Learning

In real-world datasets, data splits, as determined by the ELBO and especially
by the reconstruction loss, might not coincide with the human-aligned notion
of clusters. For example, we observed that plain TreeVAE utilizes specialized
decoders to focus on good reconstructions of the various background colors.
These data splits are rather intuitive from a reconstruction point of view,
however, these might not encode contextually meaningful splits. Thus, we
introduce an additional contrastive loss to guide TreeVAE toward meaningful
clusters. The idea of contrastive learning (Sohn, 2016; van den Oord ., 2018;
Wu ., 2018; Chen ., 2020) is simple; constrain the space of potential
clustering rules by defining certain data augmentations with respect to which
the model’s cluster assignment should become invariant. The model should
assign a sample to the same cluster independent of whether and which subset of
the chosen augmentations are applied to it. For the augmentations that were
used for contrastive learning, we refer to Appendix E.1.2.

To achieve the desired behavior, we utilize the normalized temperature-scaled
cross-entropy loss (NT-Xent) (Sohn, 2016; van den Oord ., 2018; Wu ., 2018;
Chen ., 2020), whose definition we repeat here for ease of reading:
$\ell_{i,j}=-\log\frac{\exp{(s_{i,j}/\tau)}}{\sum_{k=1}^{2N}\mathbbm{1}_{[k\neq
i]}\exp{(s_{i,k}/\tau)}}$, where $s_{i,j}$ denotes a similarity measure, which
we define as the cosine similarity between the representations of
$\tilde{\bm{x}}_{i}$ and $\tilde{\bm{x}}_{j}$, and $\tau$ is a temperature
parameter. This is computed for all $2N$ pairs of augmented samples
$\tilde{\bm{x}}_{i}$ and $\tilde{\bm{x}}_{j}$ originating from the same
initial sample $\bm{x}$ and then averaged. We compute this depth-wise for
every embedding $\mathbf{d}_{l}$ by first passing it through a separate MLP
with one hidden layer of dimension $512$, followed by batch normalization and
LeakyReLU and the final linear layer with output dimension $64$, on which the
NT-Xent with $\tau=0.5$ is applied. Then, we average the pairwise losses and
sum them up over all $\mathbf{d}_{l}$, where we, to be invariant to the depth
of the bottom-up, divide by the maximum depth. With this, we regularize the
bottom-up embeddings learned by the model to encode every augmented pair of
samples close to each other, thus constraining the learning of information
that the model should be invariant to.

Even with the previous regularization, $\mathbf{d}_{l}$ might still contain
some of information that is not relevant for clustering (such as background
color), and therefore the routers might base their split on such
characteristics. Therefore, we build upon ideas from Li . (2021, 2022), which
propose not only to regularize the embeddings, but also the cluster
probabilities themselves. While Li . (2021, 2022) change from a sample-wise
view to a cluster-wise view for calculating the NT-Xent on the $2K$ clusters,
we instead keep the sample-wise view and apply the NT-Xent with $\tau=1$
directly on the outputs of every bottom-up router
$q({\textnormal{c}}_{i}\mid\mathbf{d}_{l})$. We would like to emphasize here
that we do not project them to another space, because, in contrast to previous
methods (Chen ., 2020), we wish to remove all irrelevant information with
respect to the augmentations from the routers. The computed pairwise loss is
then weighted by the probability of falling into the given node. Lastly, we
sum up the weighted pairwise losses and divide them by the sum of the weights
to ensure equal regularization in every node. This has three advantages: (_i_)
We can use the proposed loss during the training of the subtrees, thus gaining
computational efficiency. (_ii_) We implicitly encourage the splitting of the
data into balanced classes, following the overall design choice for splitting
the data, outlined in Section 2.5. (_iii_) We can omit the computationally
intensive finetuning of the full tree, as the splits, as enforced by the
contrastive losses, are local, which alleviates the need of finetuning the
full tree for global optimization.

Lastly, we add these two contrastive parts together and weigh them by $100$ to
match the gradients of the ELBO. Thus, we naturally introduce a tradeoff
between reconstruction quality and clustering quality, as we constrain the
model to a clustering solution that does not optimally make use of specialized
decoders.

###  E.4 Baselines

For a fair comparison, we retain the same architectural choices made for
TreeVAE for both the Variational Autoencoder and Ladder Variational
Autoencoder, used as baselines. In particular, we retain the same encoder and
decoder structure as explained in Section E.2. For datasets on which TreeVAE
applies contrastive learning, we similarly apply the regularization on the
bottom-up embeddings of the baselines. Below we describe specific training
details that deviate from TreeVAE, due to the differences in the graphical
models.

####  E.4.1 Variational Autoencoder

The non-hierarchical counterpart of TreeVAE is a classical Variational
Autoencoder (VAE). As it does not contain a hierarchical structure, the VAE
consists solely of an encoder and decoder architecture, which follows the
architectural choices of TreeVAE. We train the VAE for $500$ epochs and use
the KL annealing procedure proposed by LadderVAE, which linearly increases the
weight of the KL terms from $0$ to $1$ in $200$ epochs.

####  E.4.2 Ladder Variational Autoencoder

The sequential counterpart of TreeVAE is the LadderVAE (Sønderby ., 2016). We
retain the same encoder, decoder, and transformations used by TreeVAE, and we
set the depth to $5$ for all datasets. We train the LadderVAE for $1000$
epochs and use the KL annealing procedure proposed by the authors, which
linearly increases the weight of the KL terms from $0$ to $1$ in $200$ epochs.

####  E.4.3 Agglomerative Clustering

We train Ward’s minimum variance agglomerative clustering (Ward, 1963; Murtagh
Legendre, 2014) on the plain input space (Agg), the latent space of the VAE
(VAE + Agg) and the last layer of LadderVAE (LadderVAE + Agg). We observed
that clustering on the last layer of LadderVAE performed substantially better
than when using the root (or the top layer). We chose Ward’s method as it
performed better than other classical hierarchical clustering methods (such as
single-linkage agglomeration clustering or bisecting K-means). However, Ward’s
method cannot be tested on a held-out dataset, as it inherently does not allow
for prediction on new data. For this reason, we train and test Ward’s method
on the test set embeddings given by the baseline models, which were trained on
the training data, for a fairer comparison with the other methods.

###  E.5 Resource Usage

In the following, we describe the resource usage of our experiments. All our
experiments were run on RTX3080 GPUs, except for CelebA, where we increased
the memory requirement and use a RTX3090. Training TreeVAE with $10$ leaves on
MNIST, Fashion-MNIST, and Omniglot-50 takes between $1$h and $2$h, Omniglot-5
$30$ minutes, CIFAR-10 $5$h. Training TreeVAE with $20$ leaves on 20Newsgroup
takes approximately $30$ minutes, and on CIFAR-100 $9$h. Training TreeVAE on
CelebA takes approx $8$h. Please note that we only report the numbers to
generate the final results but not the development time.


# Sensitivity Analysis for Piecewise-Affine Approximations of Nonlinear
Programs with Polytopic Constraints

Leila Gharavi  Changrui Liu  Bart De Schutter Fellow IEEE Simone Baldi Senior
Member IEEE This research is supported by the Dutch Science Foundation NWO-TTW
within the EVOLVE project (no. 18484), and by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant agreement No. 101018826 - CLariNet)(Corresponding authors: L.
Gharavi and S. Baldi)L. Gharavi, C. Liu and B. De Schutter are with the Delft
Center for Systems and Control, Delft University of Technology, Delft, The
Netherlands<EMAIL_ADDRESS>Baldi is with the
School of Mathematics, Southeast University, Nanjing, China.
<EMAIL_ADDRESS>
###### Abstract

Nonlinear Programs (NLPs) are prevalent in optimization-based control of
nonlinear systems. Solving general NLPs is computationally expensive,
necessitating the development of fast hardware or tractable suboptimal
approximations. This paper investigates the sensitivity of the solutions of
NLPs with polytopic constraints when the nonlinear continuous objective
function is approximated by a PieceWise-Affine (PWA) counterpart. By
leveraging perturbation analysis using a convex modulus, we derive guaranteed
bounds on the distance between the optimal solution of the original
polytopically-constrained NLP and that of its approximated formulation. Our
approach aids in determining criteria for achieving desired solution bounds.
Two case studies on the Eggholder function and nonlinear model predictive
control of an inverted pendulum demonstrate the theoretical results.

Perturbation Analysis, Non-Convex Nonlinear Programming, Piecewise-Affine
Functions, Max-Min-Plus-Scaling Systems, Function Approximation

##  1 Introduction

Nonlinear Programs (NLPs) are commonly encountered in optimization-based
control of nonlinear systems, e.g., Nonlinear Model Predictive Control (NMPC)
[1]. Solving non-convex NLPs is intractable, posing a great challenge in
applying optimization-based controllers in real-time operations, especially
for systems having fast dynamics. Various solutions have been proposed to
address this issue, such as adaptive problem formulations [2], learning-based
methods [3], and sensitivity analysis of NLPs [4].

PWA approximations are widely used due to their tractability [5, 6]. To obtain
a continuous PWA approximation, $\min$ and $\max$ operators can be used to
maintain continuity and to resolve numerical issues in the resulting
optimization problem [7, 8, 9]. The approximated problem can be used to obtain
a suboptimal solution [10], whose optimality highly depends on the accuracy of
the approximation. For example, a warm start of a non-convex NLP can be
obtained by solving the approximated optimization problem [11, 12]. Optimality
guarantees of such approaches can be derived using sensitivity analysis,
establishing an upper bound on the distance between the original solutions and
the approximated ones. As a result, by finding a subset of the decision space
around the approximated solution, one can sample a structured or random warm
start to solve the original non-convex NLP more efficiently.

Quantitative bounds on the distance between the original and the approximated
solutions have been studied in the sensitivity analysis of quadratic [13] and
convex [14] optimization problems. Regarding NLPs, there exist several results
on their sensitivity to the parameters in the optimization formulation [15,
16] and the initial solution [17]. In addition, optimality and dissipativity
conditions for the perturbed convex NLP problem have also been established
[18, 19]. For a more extensive study, the reader can refer to [20]. Recently,
sensitivity analysis has also been applied to analyze the infinite-horizon
performance of MPC [23]. However, obtaining quantitative bounds on the
distance between the solutions of a non-convex NLP and its PWA approximation
is still a gap that needs to be filled, and our work addresses this problem.

In this paper, we present a method to bound the solutions of a polytopically-
constrained non-convex NLP problem using a continuous PWA approximation of the
nonlinear objective function. We employ the Max-Min-Plus-Scaling (MMPS)
formulation of continuous PWA functions in [8] to construct a piecewise convex
approximation formalism. Leveraging some results in [14], we derive guaranteed
bounds on the distance between the original and the approximated optimal
solution. Moreover, our approach can not only establish such bounds but also
aid in determining necessary criteria during the approximation stage to attain
a desired solution bound. To demonstrate the theoretical findings, we present
two case studies on the Eggholder function [21], a renowned benchmark
optimization problem with multiple local minima, and an NMPC optimization
problem for an inverted pendulum [1].

The rest of the paper is organized as follows. In Section 2, we present
preliminaries regarding the sensitivity analysis of NLPs and the PWA
approximation of nonlinear functions. Section 3 formulates the problem and
Section 4 elaborates our proposed approach to theoretically compute the
confidence radius for the local minima of the corresponding approximated
function. In Section 5, we then demonstrate the derived confidence radius
through a case study on the Eggholder function and we apply our analysis to an
NMPC optimization example. Section 6 concludes this paper.

_Notation:_ For a positive integer $P$, we use $\mathcal{I}_{P}$ to denote the
set $\\{1,2,\dots,P\\}$. For a connected set
$\mathcal{D}\subseteq\mathbb{R}^{n}$, the diameter of $\mathcal{D}$ is defined
as
$\mathrm{diam}(\mathcal{D})\coloneqq\max_{x_{1},x_{2}\in\mathcal{D}}\|x_{1}-x_{2}\|$,
where $\|\cdot\|$ is the Euclidean or the 2-norm.

##  2 Preliminaries

###  2.1 Representation of Continuous PWA Functions

We start with formally defining a continuous PWA function which will be
frequently used throughout the paper.

######  Definition 1 (Continuous PWA function [22]).

A scalar-valued function $f:\mathcal{D}\subseteq\mathbb{R}^{n}\to\mathbb{R}$
is said to be a continuous PWA function if and only if the following
conditions hold:

  1. 1.

the domain space $\mathcal{D}$ is divided into a finite number of closed
polyhedral regions $\mathcal{R}_{1},\dots,\mathcal{R}_{R}$ with non-
overlapping interiors,

  2. 2.

for each $r\in\mathcal{I}_{R}$, $f$ can be expressed as

$f(x)=\alpha_{r}^{T}x+\beta_{r}\quad\rm{if}\quad x\in\mathcal{R}_{r},$

with $\alpha_{r}\in\mathbb{R}^{n}$ and $\beta_{r}\in\mathbb{R}$, and

  3. 3.

$f$ is continuous on the boundary between any pair of regions.

PWA functions can be expressed in different forms, among which MMPS form is
powerful for decomposing PWA functions.

######  Theorem 1 (MMPS representation [8]).

For a scalar-valued continuous PWA function $f$ as in Definition 1, there
exist non-empty index sets $\mathcal{I}_{P}$ and $\mathcal{I}_{Q_{p}}$ such
that

$f(x)=\min_{p\in\mathcal{I}_{P}}\max_{q\in\mathcal{I}_{Q_{p}}}\left(a_{p,q}^{T}x+b_{p,q}\right),$
(1)

for real numbers $b_{p,q}$ and vectors $a_{p,q}\in\mathbb{R}^{n}$.

For convenience, we define the $p$-th local convex segment of $f$ as

$\displaystyle
f_{p}(x)\coloneqq\max\limits_{q\in\mathcal{I}_{Q_{p}}}\left(a_{p,q}^{T}x+b_{p,q}\right),$
(2)

where $f_{p}$ is convex since it is defined as the maximum of a finite number
of affine functions and its domain is also convex. In addition, we define the
region $\mathcal{C}_{p,q}$ in which a certain affine function is activated and
the region $\mathcal{C}_{p,.}$ in which a convex PWA function is activated,
that is,

$\displaystyle\mathcal{C}_{p,q}$
$\displaystyle\coloneqq\\{x\in\mathcal{D}\;|\;f(x)=a_{p,q}^{T}x+b_{p,q}\\},$
(3a) $\displaystyle\mathcal{C}_{p,.}$
$\displaystyle\coloneqq\\{x\in\mathcal{D}\;|\;f(x)=f_{p}(x)\\}.$ (3b)

Further, we have $\mathcal{C}_{p,.}=\bigcup_{q=1}^{Q_{p}}\mathcal{C}_{p,q}.$
Lastly, we define $\sigma_{p}:\mathcal{C}_{p,.}\to\mathcal{I}_{Q_{p}}$ as the
region index function for $f_{p}$ as

$\displaystyle\sigma_{p}(x)=q\iff x\in\mathcal{C}_{p,q}.$ (4)

###  2.2 Sensitivity of the Convex Optimization Problem

The convexity modulus [14], being used to quantify convexity, is useful in the
sensitivity analysis of convex functions. In the following, we define the
convexity modulus specifically for $f_{p}$, the $p$-th convex segment of $f$,
and its domain $\mathcal{C}_{p,.}$.

######  Definition 2 (Convexity modulus [14]).

For a given convex function $f_{p}$, the convexity modulus
$h_{1}:[0,+\infty)\to[0,+\infty)$ over the domain $\mathcal{C}_{p,.}$ is
defined as

$\displaystyle
h_{1}(\gamma)\coloneqq\begin{cases}\begin{array}[]{ll}\inf\limits_{\begin{subarray}{c}v,w\in\mathcal{C}_{p,.}\\\
\|v-w\|=\gamma\end{subarray}}J(v,w)&\text{if
}\gamma<\mathrm{diam}(\mathcal{C}_{p,.})\\\ +\infty&\text{if
}\gamma\geqslant\mathrm{diam}(\mathcal{C}_{p,.})\end{array}\end{cases},$ (5)

where $v$ and $w$ are two points in $\mathcal{C}_{p,.}$ satisfying
$\|v-w\|=\gamma$, and $J(v,w)$ is given as

$\displaystyle
J(v,w)=\dfrac{f_{p}(v)+f_{p}(w)}{2}-f_{p}\left(\dfrac{v+w}{2}\right).$ (6)

######  Theorem 2 (Theorem 4.5 in [14]).

Suppose that $f_{p}:\mathcal{C}_{p,.}\to\mathbb{R}$ is a scalar-valued convex
function and $\delta_{p}:\mathcal{C}_{p,.}\to\mathbb{R}$ is an arbitrary
function satisfying

$\displaystyle\sup_{x\in\mathcal{C}_{p,.}}|\delta_{p}(x)|=\Delta_{p}<\infty.$
(7)

Let $x_{p}^{\ast}$ be any global infimizer of $f_{p}$ and $\hat{x}_{p}^{\ast}$
be any global infimizer of $\hat{f}_{p}=f_{p}+\delta_{p}$. Then

$\displaystyle\|\hat{x}_{p}^{\ast}-x_{p}^{\ast}\|\leqslant
h_{1}^{-1}\left(2\Delta_{p}\right),$ (8)

where $h_{1}$ is the convexity modulus in Definition 2.

For a more compact notation, we call the right-hand side of (8), the
confidence radius, defined as follows:

######  Definition 3 (Confidence radius).

For a given function
$\hat{f}_{p}:\mathcal{C}_{p,.}\subseteq\mathbb{R}^{n}\to\mathbb{R}$
approximating the function
$f_{p}:\mathcal{C}_{p,.}\subseteq\mathbb{R}^{n}\to\mathbb{R}$ with the maximal
approximation error $\Delta_{p}$ from (7), the confidence radius is the upper-
bound on the distance between $\hat{x}^{\ast}_{p}$, the global minimizer of
$\hat{f}_{p}$, and $x^{\ast}_{p}$, the global minimizer of $f_{p}$, and is
obtained by

$\chi=h_{1}^{-1}(2\Delta_{p}),$

where $h_{1}$ is the convexity modulus in Definition 2.

######  Proposition 1 (Proposition 2.2, 2.5 in [14]).

Given a convex function $f_{p}$ on a compact domain $\mathcal{C}_{p,.}$ with
convexity modulus $h_{1}$ defined as (5), the following hold:

  1. 1.

$h_{1}$ is left-continuous on
$\left(0,\mathrm{diam}(\mathcal{C}_{p,.})\right)$, and

  2. 2.

for $\gamma_{1},\gamma_{2}\in[0,\mathrm{diam}(\mathcal{C}_{p,.})$, if
${\gamma_{1}<\gamma_{2}}$, then $h_{1}(\gamma_{1})/\gamma_{1}\leqslant
h_{1}(\gamma_{1})/\gamma_{2}$.

##  3 Continuous PWA Approximation of NLPs

Consider an NLP with polytopic constraints

$\displaystyle\min_{x\in\mathcal{X}}$ $\displaystyle\quad F(x),$ (9)

where $F:\mathcal{D}\subset\mathbb{R}^{n}\to\mathbb{R}$ is the nonlinear
objective function and $\mathcal{X}\subseteq\mathcal{D}$ is the polytopic
feasible region. From now on, we assume that the domain $\mathcal{D}$ is
compact. We approximate $F$ by a continuous PWA function $f$ of the MMPS form
(1) via solving the approximation problem

$\displaystyle\min_{\mathcal{A},\ \mathcal{B}}$
$\displaystyle\quad\int\limits_{\mathcal{D}}\left|F(x)-\min_{p\in\mathcal{I}_{P}}\max_{q\in\mathcal{I}_{Q_{p}}}\left(a_{p,q}^{T}x+b_{p,q}\right)\right|\;dx,$
(10)

to minimize the absolute approximation error, where the ordered sets
$\mathcal{A}$ and $\mathcal{B}$ respectively collect $a_{p,q}$ and $b_{p,q}$.

######  Example 1.

Figure 1 shows a 1-dimensional example of approximating a nonlinear objective
function $F$ by a continuous PWA function $f$ using the MMPS form (1) as

$F(x)\approx
f(x)=\min\left(\underbrace{\max\left(f_{1,1},f_{1,2}\right)}_{f_{1,.}},\underbrace{\max\left(f_{2,1},f_{2,2}\right)}_{f_{2,.}},f_{3,.}\right),$

with $P=3$, $Q_{1}=Q_{2}=2$, and $Q_{3}$ = 1. The convex segments of $f$ are
shown by $f_{p,.}$ which give the maximum value among $Q_{p}$ affine functions
$f_{p,q}$, $q\in\mathcal{I}_{Q_{p}}$. The subregions $\mathcal{C}_{p,q}$ are
shown in the same color as their corresponding active affine functions,
$f_{p,q}$. In this 1-dimensional example, $\mathrm{diam}(\mathcal{C}_{p,.})$
is the distance between the upper and lower bounds of $\mathcal{C}_{p,.}$ on
the $x$-axis.

$\mathcal{C}_{1,1}$$f_{1,1}$$\mathcal{C}_{1,2}$$f_{1,2}$$\mathcal{C}_{1,.}$$\mathcal{C}_{2,1}$$f_{2,1}$$\mathcal{C}_{2,2}$$f_{2,2}$$\mathcal{C}_{2,.}$$\mathcal{C}_{3,.}$$f_{3,.}$$y=F(x)$$y=f(x)$$x$$y$
Figure 1: A conceptual example of approximating a nonlinear function $F$ with
a continuous PWA approximation $f$ using the MMPS form in (1).

##  4 Theoretical Analysis

The main result of this section is the sensitivity bound in Theorem 3. Before,
we present some building blocks about continuity and boundedness of the
convexity modulus (cf. Lemma 1, 2 and 3).

######  Lemma 1.

For a convex PWA function $f_{p}$ expressed by (2), $\partial
h_{1}/\partial\gamma$ is a piecewise constant function.

###### Proof.

For compactness, let us denote

$i=\sigma_{p}(v),\qquad j=\sigma_{p}(w),\qquad
k=\sigma_{p}\left(\dfrac{v+w}{2}\right),$

with $i,j,k\in\mathcal{I}_{Q_{p}}$. For $f_{p}$ expressed by (2), the function
$J$ in (6) can be written as

$J(v,w)=\\\
\dfrac{a_{p,i}^{T}-a_{p,k}^{T}}{2}v+\dfrac{a_{p,j}^{T}-a_{p,k}^{T}}{2}w+\dfrac{b_{p,i}+b_{p,j}-2b_{p,k}}{2}.$
(11)

The necessary Lagrange conditions for optimality at $(v^{\ast},w^{\ast})$ in
(5) state that there must exist $\mu\in\mathbb{R}$ that satisfies the
following simultaneously:

$\displaystyle\nabla
J(v^{\ast},w^{\ast})+\mu\nabla\left(\|v-w\|-\gamma\right)\Big{|}_{\begin{subarray}{c}v=v^{\ast}\\\
w=w^{\ast}\end{subarray}}=0,$ (12a)
$\displaystyle\|v^{\ast}-w^{\ast}\|=\gamma.$ (12b)

By calculating the gradient of (11), we have that (12) becomes

$\displaystyle\dfrac{a_{p,i}^{T}-a_{p,k}^{T}}{2}+\mu\dfrac{v^{\ast}-w^{\ast}}{\|v^{\ast}-w^{\ast}\|}=0,$
(13a)
$\displaystyle\dfrac{a_{p,j}^{T}-a_{p,k}^{T}}{2}+\mu\dfrac{w^{\ast}-v^{\ast}}{\|v^{\ast}-w^{\ast}\|}=0,$
(13b) $\displaystyle\|v^{\ast}-w^{\ast}\|=\gamma,$ (13c)

which implies the existence of $\mu\in\mathbb{R}$ satisfying

$\displaystyle\dfrac{a_{p,i}^{T}-a_{p,j}^{T}}{2}+2\mu\dfrac{v^{\ast}-w^{\ast}}{\gamma}=0.$
(14)

Note that $\partial h_{1}\left/\partial\gamma\right.$ is equal to $\partial
J\left/\partial\gamma\right.$, except where the indices $i$, $j$, and $k$
change. At such points, $h_{1}$ is not differentiable with respect to
$\gamma$, which does not conflict with $\partial
h_{1}\left/\partial\gamma\right.$ being a piecewise constant function. To find
the slope of $h_{1}$ where it exists, the chain rule can be applied as

$\displaystyle\dfrac{\partial h_{1}}{\partial\gamma}=\dfrac{\partial
J}{\partial v^{\ast}}\left/\dfrac{\partial\gamma}{\partial
v^{\ast}}\right.+\dfrac{\partial J}{\partial
w^{\ast}}\left/\dfrac{\partial\gamma}{\partial
w^{\ast}}\right.=\dfrac{a_{p,i}^{T}-a_{p,j}^{T}}{2}\dfrac{\|v^{\ast}-w^{\ast}\|}{v^{\ast}-w^{\ast}},$

which, considering (14), leads to

$\displaystyle\dfrac{\partial h_{1}}{\partial\gamma}=-2\mu,$ (15)

which implies that $\partial h_{1}/\partial\gamma$ is a function of the
$a_{p,i}^{T}-a_{p,j}^{T}$ values. ∎

######  Lemma 2.

For a convex PWA function $f_{p}$ expressed by (2), the convexity modulus
$h_{1}$ in (5) is continuous on $[0,\mathrm{diam}(\mathcal{C}_{p,.}))$.

###### Proof.

From Proposition 1, we know that $h_{1}$ is left-continuous on $[0,+\infty)$.
Seeking a contradiction, let us assume that $h_{1}$ is not right-continuous in
$\gamma_{0}\in[0,\mathrm{diam}(\mathcal{C}_{p,.}))$, hence,

$\lim_{\gamma\to\gamma_{0}^{+}}h_{1}(\gamma)\neq h_{1}(\gamma_{0}).$

The monotonicity property of $h_{1}$ in Proposition 1 requires

$\displaystyle\lim_{\gamma\to\gamma_{0}^{+}}h_{1}(\gamma)>h_{1}(\gamma_{0}).$

Therefore, without loss of generality, we assume there exists a gap
$\epsilon_{0}>0$ and a point
$\gamma_{0}<\gamma_{0}^{+}<\mathrm{diam}(\mathcal{C}_{p,.})$ such that

$\displaystyle h_{1}(\gamma_{0}^{+})=h_{1}(\gamma_{0})+\dfrac{\partial
h_{1}}{\partial\gamma}\Big{|}_{\gamma=\gamma_{0}}\left(\gamma_{0}^{+}-\gamma_{0}\right)+\epsilon_{0}.$
(16)

Using (5), we define the points $v_{0}$, $w_{0}$, and $w_{0}^{+}$ such that

$\displaystyle
h_{1}(\gamma_{0})=\inf\limits_{\begin{subarray}{c}v,w\in\mathcal{C}_{p,.}\\\
\|v-w\|=\gamma_{0}\end{subarray}}J(v,w)=J(v_{0},w_{0}),$

and $\|v_{0}-w_{0}^{+}\|=\gamma_{0}^{+}$. Considering the optimality property
in (5), we have

$\displaystyle h_{1}(\gamma_{0}^{+})\leqslant J(v_{0},w_{0}^{+}),$

and knowing that $J$ is a continuous function by definition, we can deduce

$\displaystyle h_{1}(\gamma_{0}^{+})\leqslant
h_{1}(\gamma_{0})+\rho(w_{0}^{+}-w_{0}),$

where $\rho:\mathcal{C}_{p,.}\to\mathbb{R}$ is a function with the following
property:

$\displaystyle\lim_{\nu\to 0^{+}}\rho(\nu)=0.$ (17)

Substituting (16) into (17) and taking the limit on both sides when
$\gamma_{0}^{+}$ approaches $\gamma_{0}$ leads to

$\displaystyle h_{1}(\gamma_{0})+\epsilon_{0}\leqslant h_{1}(\gamma_{0}),$

which contradicts the fact that $\epsilon_{0}>0$. Therefore, $h_{1}$ is right-
continuous on $[0,\mathrm{diam}(\mathcal{C}_{p,.}))$. ∎

######  Proposition 2.

For a convex PWA function $f_{p}$ expressed by (2), we have

$h_{1}(\gamma)=0,\qquad\forall\gamma\leqslant\max\limits_{q\in\mathcal{I}_{Q_{p}}}\left\\{\mathrm{diam}(\mathcal{C}_{p,q})\right\\}.$

###### Proof.

By seeking a contradiction, let us assume that

$\exists\gamma_{0}\leqslant\max\limits_{q\in\mathcal{I}_{Q_{p}}}\left\\{\mathrm{diam}(\mathcal{C}_{p,q})\right\\},\quad\text{such
that}\quad h_{1}(\gamma_{0})>0,$

with the corresponding optimal points $v^{\ast}_{0}$ and $w^{\ast}_{0}$ from
(5) such that

$\displaystyle
h_{1}(\gamma_{0})=\inf\limits_{\begin{subarray}{c}v,w\in\mathcal{C}_{p,.}\\\
\|v-w\|=\gamma_{0}\end{subarray}}J(v,w)=J(v^{\ast}_{0},w^{\ast}_{0}).$

Let us select two points, $v_{0}$ and $w_{0}$, on the largest subregion in
$\mathcal{C}_{p,.}$ such that

$\|v_{0}-w_{0}\|=\gamma_{0}.$

which results in $J(v_{0},w_{0})=0$. Considering the optimality property in
(5), we have

$J(v^{\ast}_{0},w^{\ast}_{0})\leqslant J(v_{0},w_{0}),$

which contradicts the initial assumption that $h_{1}(\gamma_{0})>0$ and
$h_{1}(\gamma_{0})=J(v^{\ast}_{0},w^{\ast}_{0})$. ∎

######  Lemma 3.

For a convex PWA function $f_{p}$ expressed by (2), the convexity modulus
$h_{1}$ is bounded by $\hat{h}_{1}\leqslant h_{1}$, with

$\displaystyle\hat{h}_{1}(\gamma)\coloneqq\begin{cases}\begin{array}[]{ll}0&\text{if
}\gamma<\mathrm{diam}(\mathcal{C}_{p,.})\\\ c_{1}\gamma+c_{0}&\text{if
}\gamma\geqslant\mathrm{diam}(\mathcal{C}_{p,.})\end{array}\end{cases},$ (18)

where

$\displaystyle c_{1}=\;\min\limits_{j\in\mathcal{I}_{Q_{p}}}\quad$
$\displaystyle\left\\{\dfrac{a_{p,i}^{T}-a_{p,j}^{T}}{2}\right\\},$ (19a)
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle
i=\arg\max\limits_{q\in\mathcal{I}_{Q_{p}}}\mathrm{diam}(\mathcal{C}_{p,q}),$
(19b) $\displaystyle\mathcal{C}_{p,i}\cap\mathcal{C}_{p,j}\neq\emptyset,$
(19c)

and $c_{0}=\;c_{1}\;\mathrm{diam}(\mathcal{C}_{p,.})$.

###### Proof.

This can be directly deduced from Proposition 2, considering the continuity of
$h_{1}$ from Lemma 2, the piecewise-constant property of $\partial
h_{1}/\partial\gamma$ from Lemma 1, and the increasing property of $h_{1}$
from Proposition 1. ∎

$-385$$-330$$-180$$180$$-400$$300$$-512$$512$$x$$y$$\mathcal{C}_{1,.}$$\mathcal{C}_{2,.}$$\mathcal{C}_{3,.}$$\mathcal{C}_{4,.}$$\mathcal{C}_{5,.}$$\hskip
11.38109pt\hat{x}^{\ast}_{1}$$\hskip
11.38109pt\hat{x}^{\ast}_{2}$$\hat{x}^{\ast}_{3}$$\hat{x}^{\ast}_{4}\hskip
8.53581pt$$\hat{x}^{\ast}_{5}$$x^{\ast}_{1}$$x^{\ast}_{2}$$x^{\ast}_{3}$$x^{\ast}_{4}$$x^{\ast}_{5}$Nonlinear
function $F$PWA function $f$Regional minima of $F$Regional minima of $f$
Figure 2: Plots of the nonlinear objective function $F$ and its PWA
approximation $f$.

We are now in the position to state our main result:

######  Theorem 3.

Let $F:\mathcal{D}\to\mathbb{R}$ be a scalar-valued objective function and let
$f$ be a continuous PWA function as in Definition 1 that approximates $F$ with
bounded approximation error $\delta=f-F$. Let $f_{p}$ in (2) be the local
convex segment of $f$ in its MMPS form (1) on the set $\mathcal{C}_{p,.}$, and
let $\delta_{p}:\mathcal{C}_{p,.}\to\mathbb{R}$ be the corresponding
approximation error bounded by

$\sup_{x\in\mathcal{C}_{p,.}}|\delta_{p}(x)|=\Delta_{p}<\infty.$

Let $x_{p}^{\ast}$ be any global minimizer of $f_{p}$ and $\hat{x}_{p}^{\ast}$
be any global minimizer of $F$ on $\mathcal{C}_{p,.}$. Then, the following
condition holds:

$\displaystyle\|\hat{x}_{p}^{\ast}-x_{p}^{\ast}\|\leqslant\dfrac{2\Delta_{p}}{c_{1}}+\max\limits_{q\in\mathcal{I}_{Q_{p}}}\left\\{\mathrm{diam}(\mathcal{C}_{p,q})\right\\},$
(20)

where $c_{1}$ is defined in (19).

###### Proof.

This can be directly concluded by extending Theorem 2 via considering
Proposition 2 and Lemma 3. ∎

##  5 Case Study

To showcase the application of Theorem 3, we select the 1-dimensional cut of
the well-known Eggholder test function [21] at $x_{2}=0$ given by

$\displaystyle F(x)$
$\displaystyle=-47\sin\left(\sqrt{\left|\frac{x}{2}+47\right|}\right)-x\sin\left(\sqrt{|x-47|}\right).$

We approximate $F$ by a continuous PWA function $f$ that we arbitrarily take
as

$\displaystyle f(x)$
$\displaystyle=\min_{p\in\mathcal{I}_{5}}\left(f_{p,.}\right).$

with local convex segments

$\displaystyle f_{1,.}$
$\displaystyle=\max_{q\in\mathcal{I}_{3}}\left(f_{1,q}\right),$
$\displaystyle\mathcal{C}_{1,.}$ $\displaystyle=[-512,-385],$ (21a)
$\displaystyle f_{2,.}$ $\displaystyle=f_{2,1},$
$\displaystyle\mathcal{C}_{2,.}$ $\displaystyle=[-385,-330],$ (21b)
$\displaystyle f_{3,.}$
$\displaystyle=\max_{q\in\mathcal{I}_{3}}\left(f_{3,q}\right),$
$\displaystyle\mathcal{C}_{3,.}$ $\displaystyle=[-330,-180],$ (21c)
$\displaystyle f_{4,.}$
$\displaystyle=\max_{q\in\mathcal{I}_{3}}\left(f_{4,q}\right)$
$\displaystyle\mathcal{C}_{4,.}$ $\displaystyle=[-180,180],$ (21d)
$\displaystyle f_{5,.}$ $\displaystyle=f_{5,1},$
$\displaystyle\mathcal{C}_{5,.}$ $\displaystyle=[180,512].$ (21e)

Figure 2 shows the plots for the nonlinear objective function $F$ and its PWA
approximation $f$. The subregions $\mathcal{C}_{p,.}$ with
$p\in\mathcal{I}_{5}$ are illustrated by different colors. Theorem 3 can be
used in two ways:

  1. 1.

guaranteeing bounds on the distance between the regional minima of $F$ and $f$
on each subregion, given a bound on the approximation error, and

  2. 2.

finding the required criteria for the approximation to obtain a desired bound
on the distance between these minima, which we refer to as the confidence
radius.

We discuss each case separately by focusing on the approximation on
$\mathcal{C}_{3,.}$.

###  5.1 Case 1: Finding the Confidence Radii

Figure 3(a) shows $F$ and two PWA approximations on $\mathcal{C}_{p,.}$ with
two approximation errors. The first is $f_{3}^{(1)}$, which divides
$\mathcal{C}_{3,.}$ into 3 subregions with maximum approximation error
$\Delta_{3}^{(1)}=19.9$, and which is given by

$\displaystyle f_{3}^{(1)}(x)=\max\left\\{\begin{array}[]{c}-7.8x-2365.7\\\
-0.9x-501.2\\\ 6.1x+1176.1\end{array}\right\\}.$

The second approximation is $f_{3}^{(2)}$ with 8 affine pieces, the maximum
error $\Delta_{3}^{(2)}=2.6$, and defined as

$\displaystyle f_{3}^{(2)}(x)=\max\left\\{\begin{array}[]{c}-8.6x-2613.1\\\
-6.8x-2095.6\\\ -4.6x-1477.9\\\ -2.2x-829.8\\\ 0.3x-191.6\\\ 2.8x+412.5\\\
5.1x+944\\\ 6.9x+1348.1\end{array}\right\\}.$

The inverses of the corresponding convexity moduli are shown in Fig. 3(b) in
the same color as their corresponding $f$ in Fig. 3(a), where $\chi$ is the
confidence radius in Definition 3.

Using Theorem 3, the confidence radius for $f_{3}^{(1)}$ by is obtained by
$\chi^{(1)}=70$, which is the same value obtained by finding $h_{1}$ and its
inverse function using (5), which is presented in Fig. 3(b). The same process
can be performed for the second approximation, $f_{3}^{(2)}$, which gives
$\chi^{(2)}=44.3$. Note that Theorem 3 is more conservative for larger values
of $\Delta$, compared to directly using the definition of $h_{1}$. For
instance, if $\Delta_{3}^{(2)}=12.5$, employing Theorem 3 leads to
$\chi^{(2)}=65.7$, while the computed confidence radius using $h_{1}$ is
$58.4$. The areas within the confidence radii for the PWA approximations are
highlighted on the $x$-axis in Fig. 3(a) as well.

$\mathcal{R}^{(2)}$$\mathcal{R}^{(1)}$$-315$$-180$$-250$$0$$200$$x$$y$$x^{\ast}_{3}$$x^{\ast}_{3}$$f_{3}^{(1)}$$f_{3}^{(2)}$$F$
(a) Representation of $f$ and $F$

$2\Delta$$\chi$$39.8$$70.0$$5.2$$44.3$${h_{1}^{(1)}}^{-1}$${h_{1}^{(2)}}^{-1}$
(b) Representation of $h_{1}^{-1}$

Figure 3: Comparison of two different PWA approximations of the nonlinear
function on $\mathcal{C}_{3,.}$.

###  5.2 Case 2: Finding the Approximation Criteria

In this case, we approach the problem from another direction: we select a
desired confidence radius $\chi^{(3)}$ and find the required criteria for the
corresponding approximated function, $f_{3}^{(3)}$. Let the desired
$\chi^{(3)}=15$; then,

$\dfrac{2\Delta_{3}^{(3)}}{c_{1}}+\max\limits_{q\in\mathcal{I}_{Q_{p}}}\left\\{\mathrm{diam}(\mathcal{C}_{3,q})\right\\}\leqslant
10,$

which means the diameter of the largest subregion $\mathcal{C}_{3,.}$ must be
smaller than 10. Firstly, given that $\mathrm{diam}(\mathcal{C}_{3,.})=150$,
it can be concluded that the PWA approximation requires at least 10
partitions. We can then start the approximation by partitioning
$\mathcal{C}_{p,.}$ into 15 subregions with the same diameter and find the
lowest possible error bound $\Delta_{3}^{(3)}$ for the approximation, which is
obtained as $2.83$ with $c_{1}=0.0072$. For this approximation, $\chi^{(3)}$
already exceeds $\mathrm{diam}(\mathcal{C}_{3,.})$.

To improve upon this example, we add another partition to reduce the largest
partition diameter further and this time we do not aim at partitions of
$\mathcal{C}_{3,.}$ with the same diameter, but require

$\max\limits_{q\in\mathcal{I}_{16}}\\{\mathrm{diam}\left(\mathcal{C}_{3,q}\right)\\}\leqslant
10.$

We find $\Delta_{3}^{(3)}=2.47$ with $c_{1}=1.03$ and

$\max\limits_{q\in\mathcal{I}_{16}}\\{\mathrm{diam}\left(\mathcal{C}_{3,q}\right)\\}=9.4.$

For this values, we obtain $\chi^{(3)}=14.24$. In case this value is
acceptable, we can use the corresponding PWA approximation while ensuring that
the minimizer of $F$ on $\mathcal{C}_{3,.}$ lies in a ball or radius $14.24$
around the minimizer of $f^{(3)}$. In case a tighter confidence radius is
desired, the same procedure can be followed by adding more subregions.

###  5.3 Application for NMPC Optimization

To showcase the application of our proposed method in PWA approximation to
control optimization problems, we use an inverted-pendulum NMPC problem as in
[1]. The considered prediction horizon is $N_{\mathrm{p}}=2$ and the initial
rotation velocity is set as $\dot{\theta}=0$. The objective function
$J_{\mathrm{NMPC}}$ can be formulated as a function of the measured pendulum
angle $\theta_{k}$ and the control inputs $u_{k}$ and $u_{k+1}$. For instance,
for $\theta_{k}=0$ we have

$J_{\mathrm{NMPC}}(0,u_{k},u_{k+1})=\sqrt{\left(0.02u_{k}+\pi\right)^{2}+2\pi^{2}}\\\
+0.02\sqrt{u_{k}^{2}+\left(u_{k}+u_{k+1}\right)^{2}}+0.01\sqrt{u_{k}^{2}+u_{k+1}^{2}}.$

Moreover, the feasible region is defined as the box constraint
$|u_{k+i-1}|\leqslant 20N$, $i\in\mathcal{I}_{2}$ with
$\mathrm{diam}(\mathcal{C}_{1,.})=56.4$.

We approximate $J_{\mathrm{NMPC}}$ by two convex MMPS forms $f^{(1)}$ and
$f^{(2)}$ – with $P^{(1)}=P^{(2)}=1$ in (1) – with different complexities in
terms of the number of affine functions as

$\displaystyle
Q^{(1)}=4,\quad\Delta^{(1)}=0.19,\quad\max\limits_{q\in\mathcal{I}_{4}}\\{\mathrm{diam}\left(\mathcal{C}^{(2)}_{1,q}\right)\\}=28.2,$
$\displaystyle
Q^{(2)}=24,\quad\Delta^{(2)}=0.01,\quad\max\limits_{q\in\mathcal{I}_{24}}\\{\mathrm{diam}\left(\mathcal{C}^{(2)}_{1,q}\right)\\}=14.6.$

$0.02$$0.89$$14.6$$28.3$$56.4$$2\Delta$$\chi$${h_{1}^{-1}}^{(1)}$${h_{1}^{-1}}^{(2)}$
(a) Confidence radii

$u_{k}$$u_{k+1}$ (b) Confidence regions

Figure 4: Comparison of two PWA approximations of NMPC.

The inverse of the convexity modulus and the corresponding confidence regions
for both approximations are shown in Fig. 4. While $f^{(1)}$ has a low
approximation error, its complexity level does not allow to guarantee a
confidence radius lower than the diameter of the feasible region. However, the
more accurate approximation $f^{(2)}$ guarantees a smaller confidence radius.
Moreover, a general approximation criterion can be obtained, similar to the
Eggholder NLP example, for an NMPC problem. In this case, it can be observed
from (20) and Fig. 4(a) that $\chi$ is lower-bounded by the maximum subregion
diameter. Therefore, if a particular confidence radius is desired, the
approximation problem (10) can be solved while imposing constraints on the
diameter of subregions, e.g. an upper bound on the maximum subregion diameter.

###  5.4 Discussion

The Eggholder function and the NMPC case studies are two potential
applications with, respectively, 1- and 3-dimensional domains to illustrate
the theoretical results. Nevertheless, our proposed approach is applicable in
higher dimensions since we do not assume any bounds on the dimension of
$\mathcal{D}$ throughout this paper. Moreover, the following aspects should be
considered when applying the proposed approach:

  * •

The conservatism of the current approach in obtaining the confidence radii can
be high, which can be seen in the case studies.

  * •

The complexity in determining the confidence radii is irrelevant to the
dimension of the optimization problem. However, larger dimensions increase the
computation time and range of $\gamma$ values for which (5) needs to be
solved. Nevertheless, since this problem is solved offline, higher computation
time do not limit the applicability of our approach.

##  6 Conclusions

This paper has introduced a novel approach for bounding the minimizers of
polytopically-constrained NLPs with nonlinear continuous objective functions
using continuous PWA function approximations. We have leveraged the continuity
of the PWA approximations resulting from employing an MMPS formalism to
construct a locally-convex representation of the PWA approximation, thus
facilitating the derivation of guaranteed bounds on the distance between the
original and the approximated optimal solutions of the NLP by considering the
maximal approximation error. Our approach offers a practical tool for
determining criteria to achieve desired solution bounds. The effectiveness of
the method has been demonstrated through two case studies on the Eggholder
function and NMPC of an inverted pendulum, highlighting the practical
application of the proposed method and its potential impact in optimization
and optimal control.

For future work, our primary objectives are conducting an in-depth analysis of
the conservatism of our approach, refining our sensitivity analysis, and
extending our method to NLPs with non-convex constraints. Moreover, we aim to
do more comparative studies to gain insight into the impacts of the improved
computational efficiency through PWA approximation in light of the
corresponding solution bounds. Finally, investigating the effects of
probabilistic error bounds would be an interesting direction to help integrate
our approach into learning-based and data-driven applications.

## References

  * [1] S. Gros, M. Zanon, R. Quirynen, A. Bemporad, and M. Diehl.  From linear to nonlinear MPC: bridging the gap via the real-time iteration.  International Journal of Control, 93(1):62–80, 2020.
  * [2] D. W. Griffith, L. T. Biegler, and S. C. Patwardhan.  Robustly stable adaptive horizon nonlinear model predictive control.  Journal of Process Control, 70:109–122, 2018.
  * [3] L. Dong, J. Yan, X. Yuan, H. He, and C. Sun.  Functional nonlinear model predictive control based on adaptive dynamic programming.  IEEE Transactions on Cybernetics, 49(12):4206–4218, 2019.
  * [4] V. M Zavala and L. T. Biegler.  The advanced-step NMPC controller: Optimality, stability and robustness.  Automatica, 45(1):86–93, 2009.
  * [5] Z. Jin, Q. Shen, and S. Z. Yong.  Mesh-based piecewise affine abstraction with polytopic partitions for nonlinear systems.  IEEE Control Systems Letters, 5(5):1543–1548, 2021.
  * [6] A. Bemporad, A. Oliveri, T. Poggi, and M. Storace.  Ultra-fast stabilizing model predictive control via canonical piecewise affine approximations.  IEEE Transactions on Automatic Control, 56(12):2883–2897, 2011\.
  * [7] J. Xu, X. Huang, X. Mu, and S. Wang.  Model predictive control based on adaptive hinging hyperplanes model.  Journal of Process Control, 22(10):1821–1831, 2012.
  * [8] B. De Schutter and T. J.J. van den Boom.  MPC for continuous piecewise-affine systems.  Systems and Control Letters, 52(3-4):179–192, 2004.
  * [9] L. Gharavi, A. Dabiri, J. Verkuijlen, B. De Schutter, and S. Baldi.  Proactive emergency collision avoidance for automated driving in highway scenarios.  arXiv, (2310.17381), 2023.
  * [10] Y. Chen, M. Bruschetta, D. Cuccato, and A. Beghi.  An adaptive partial sensitivity updating scheme for fast nonlinear model predictive control.  IEEE Transactions on Automatic Control, 64(7):2712–2726, 2019.
  * [11] M. Ławryńczuk, P. M. Marusak, P. Chaber, and D. Seredyński.  Initialisation of optimisation solvers for nonlinear model predictive control: Classical vs. hybrid methods.  Energies, 15(7):2483, 2022.
  * [12] T. Ghandriz, B. Jacobson, P. Nilsson, and L. Laine.  Trajectory-following and off-tracking minimisation of long combination vehicles: A comparison between nonlinear and linear model predictive control.  Vehicle System Dynamics, pages 1–34, 2023.
  * [13] J. W. Daniel.  Stability of the solution of definite quadratic programs.  Mathematical Programming, 5(1):41–53, 1973.
  * [14] H. X. Phu.  Minimizing convex functions with bounded perturbations.  SIAM Journal on Optimization, 20(5):2709–2729, 2010.
  * [15] C. Büskens and H. Maurer.  Sensitivity analysis and real-time optimization of parametric nonlinear programming problems.  In M. Grötschel, S. O. Krumke, and J. Rambau, editors, Online Optimization of Large Scale Systems, pages 3–16. Springer Berlin Heidelberg, 2001.
  * [16] I. Subotic, A. Hauswirth, and F. Dorfler.  Quantitative sensitivity bounds for nonlinear programming and time-varying optimization.  IEEE Transactions on Automatic Control, 67(6):2829–2842, 2022.
  * [17] S. Shin and V. M. Zavala.  Diffusing-horizon model predictive control.  IEEE Transactions on Automatic Control, 68(1):188–201, 2023.
  * [18] H. Pirnay, R. López-Negrete, and L. T. Biegler.  Optimal sensitivity based on IPOPT.  Mathematical Programming Computation, 4(4):307–331, 2012.
  * [19] M. A. Muller, D. Angeli, and F. Allgower.  On necessity and robustness of dissipativity in economic model predictive control.  IEEE Transactions on Automatic Control, 60(6):1671–1676, 2015.
  * [20] Y. Puranik and N. V. Sahinidis.  Domain reduction techniques for global NLP and MINLP optimization.  Constraints, 22(3):338–376, 2017.
  * [21] D. Whitley, S. Rana, J. Dzubera, and K. E. Mathias.  Evaluating evolutionary algorithms.  Artificial Intelligence, 85(1):245–276, 1996.
  * [22] L.O. Chua and A.-C. Deng.  Canonical piecewise-linear representation.  IEEE Transactions on Circuits and Systems, 35(1):101–111, 1988\.
  * [23] C. Liu, S. Shi, and B. De Schutter.  Stability and performance analysis of model predictive control of uncertain linear systems.  arXiv preprint arXiv:2405.15552, 2024.


# EventNarrative: A Large-scale Event-centric Dataset for Knowledge Graph-to-
Text Generation

Anthony Colas *, Ali Sadeghian*, Yue Wang, Daisy Zhe Wang
Department of Computer Science, University of Florida
{acolas1, asadeghian, yue.wang1<EMAIL_ADDRESS>
###### Abstract

We introduce EventNarrative, a knowledge graph-to-text dataset from publicly
available open-world knowledge graphs. Given the recent advances in event-
driven Information Extraction (IE), and that prior research on graph-to-text
only focused on entity-driven KGs, this paper focuses on event-centric data.
However, our data generation system can still be adapted to other types of KG
data. Existing large-scale datasets in the graph-to-text area are non-
parallel, meaning there is a large disconnect between the KGs and text. The
datasets that have a paired KG and text, are small scale and manually
generated or generated without a rich ontology, making the corresponding
graphs sparse. Furthermore, these datasets contain many unlinked entities
between their KG and text pairs. EventNarrative consists of approximately
230,000 graphs and their corresponding natural language text, six times larger
than the current largest parallel dataset. It makes use of a rich ontology,
all the KGs entities are linked to the text, and our manual annotations
confirm a high data quality. Our aim is two-fold: to help break new ground in
event-centric research where data is lacking and to give researchers a well-
defined, large-scale dataset in order to better evaluate existing and future
knowledge graph-to-text models. We also evaluate two types of baselines on
EventNarrative: a graph-to-text specific model and two state-of-the-art
language models, which previous work has shown to be adaptable to the
knowledge graph-to-text domain.

##  1 Introduction

Natural language generation (NLG) is a rapidly developing area of natural
language processing (NLP). With the advent of transformer-based language
models, such as BERT [5], GPT-2 [35], XLNet [53], BART [21], UniLM [3] T-5
[36], and ERNIE [45], NLG has seen some recent advances in abstractive
summarization, dialog response generation, and generative question answering.
These tasks in NLG have all been accompanied by previously curated large-scale
parallel datasets, where parallel denotes a tightly coupled input/output,
allowing for generalized fine-tuning, including: the CNN/DM dataset [13, 28]
and Gigaword [40] for abstractive summarization, Persona-Chat [54] and DSTC7
[7] for dialogue response generation, and CoQA [38] for generative question-
answering. While the aforementioned NLG tasks have had a history of curated
large-scale datasets to finetune on, the task of knowledge graph-to-text has
been missing this scale of parallel data.

Figure 1: An example source and output narrative for the “Athletics at the
2012 Summer Olympics — Women’s javelin throw” event. Left: The original
nonparallel narrative with its corresponding KG from EventKG/Wikidata.
Entities in the KG and text are linked by their mutual colors. Right: The
filtered text and KG for the corresponding event. These are both output from
our Dataset Creation approach. We highlight the corresponding entities in the
texts and KGs.

Knowledge graph-to-text generation is the process of taking structured data in
the form of a knowledge graph (KG), which is a collection of subject-
predicate-object $(s,p,o)$ triples, and describing the graph through natural
language sentence(s). KGs describe real-world entities and their properties
and tend to be incomplete. There are over 1,300 publicly available KGs with
over 100B triples [14, 26], containing structured knowledge about biomedicine,
geography, socioeconomic, life sciences, chemistry, publications, etc., and
many cross-domain KGs. Some popular KGs include Wikidata [47], YAGO [37],
ICEWS [31], and DBpedia [20]. These KGs are both user curated and extracted
from Wikipedia text. Nevertheless, there are large disconnects between the
data and natural language text. Resolving these disconnects, enables us to
better serve the vast amount of structured information in the KGs in a user-
friendly manner. One solution is finding methods to directly link the KG to
its corresponding Wikipedia narrative when possible. We can then use the
curated datasets to train NLP models to expand graph narrative generation to
other KGs with fewer resources. Figure 1 illustrates an example Wikidata event
graph with its corresponding narrative from Wikipedia.

The parallel datasets that currently exist for the knowledge graph-to-text
generation are often small in size and do not take advantage of the KG
ontology when creating the data. For example, the 2017 WebNLG Challenge
dataset (WebNLG 2017) only contains 21,855 pairs of graphs and texts, while
requiring an expensive hand-annotated operation to generate text on a given
graph [8]. Another prominent parallel dataset, the AGENDA dataset, contains
40,000 examples [16] but is generated through the SciIE tool [25] on
scientific article abstracts with only 7 different relations. This sparse
ontology does not follow any standard KG ontology and induces sparse graphs
paired with long texts [16]. Moreover, the dataset contains many entities that
are isolated from their KG. We further discuss these and other knowledge
graph-to-text datasets in Sections 4 and 2.

Current knowledge graph-to-text datasets are also entity-centric, containing
data which are incompatible to narrate events. Events involve multiple actors,
complex relations, various lengths, and temporal information, making them more
information dense and variant, as detailed in Section 4. Numerous event-
centric KGs [31, 19, 9] exist, which are valuable to narrate, and recent work
has also looked into how to best extract events from text [4, 6, 22]. We
therefore develop a more comprehensive algorithm that matches event-centric
KGs to their natural-language narration. Many similar events occur frequently
but at different times. Thus, our entity matching algorithm has a date
matching component to ensure the KG-text pairs contain date/time information.
For example, there is a “2014 FIFA World Cup” and “2018 FIFA World Cup”, where
the event descriptions may have high overlap. We refer to each text instance
as a narrative of the graph/event, as when describing an event, one is often
described to be narrating the event [30].

Events are distinct in their length, occurrences, properties, and relations
involved. Our dataset reflects this, containing events from different time
periods, having thousands of types, and containing approximately 650,000
triples. Therefore, EventNarrative overcomes various shortcomings of existing
datasets: it is approximately 6 times larger than the current largest parallel
dataset, knowledge graph-text pairs are generated automatically via an
existing rich ontology, and there are over 7,000 different types of events,
ranging from sports seasons to social media campaigns. Relations within
EventKG include location, event type and start/end time.

We propose EventNarrative, a large-scale supervised graph-to-text dataset,
used to facilitate research in event-based conditional text generation.
EventNarrative is extracted and paired from existing large-scale data
repositories, including Wikidata, Wikipedia, and EventKG [9]. EventKG is a
multilingual event-centric temporal KG, which combines event graphs from
Wikidata, DBpedia, and YAGO. We begin by first extracting events from EventKG,
and then for each event, augment the data with additional corresponding
Wikidata information. In total, EventNarrative contains approximately 220,000
data pairs.

We establish baselines on EventNarrative by comparing current state-of-the-art
knowledge graph-to-text models on our automatically extracted test set. Future
versions of the EventNarrative dataset will aim to enrich the current dataset
by incorporating other KGs such as DBpedia and YAGO.

Altogether, our contributions are as follows:

  * •

A large-scale, event-centric, parallel knowledge graph-to-text dataset of
approximately 225,000 KG-text pairs, spanning over 7,000 event types, and over
650,000 triples.

  * •

A comprehensive entity matching and knowledge graph-to-text matching algorithm
that automatically pairs KGs to natural language texts.

  * •

Benchmark evaluations and baselines results on EventNarrative.

Our dataset can be found at: https://www.kaggle.com/acolas1/eventnarration.

Figure 2: An overview of our data creation approach.

##  2 Related Datasets

One of the early knowledge graph-to-text datasets, WebNLG 2017 [8], is a
human-annotated parallel dataset that consists of 27,731 graph/text pairs and
9,674 unique graph instances, therefore containing multiple text samples per
graph. After the WebNLG 2017 challenge, the dataset was expanded from 9 to 15
categories. As shown in table 1, each KG was extracted from DBpedia. Because
the dataset is handcrafted, there is a high precision between the matches in
the KGs and text, but the dataset does not scale.

The AGENDA dataset, first introduced by Koncel et al. [16] was constructed by
first collecting approximately 40,000 scientific articles from Semantic
Scholar, then extracting KGs from the text using the SciIE [25] tool. The
dataset contains only 7 relations and many entities which are not connected to
a KG. Moreover, the dataset is not bound to any ontology, making it difficult
to expand the KG component of the dataset in a standardized fashion.

A recent established non-parallel dataset, GenWiki, was constructed by
matching Wikipedia articles with DBpedia entities [15]. However, its goal is
to develop a large-scale, non-parallel dataset for unsupervised graph-to-text
learning, where all elements in the graphs are not necessarily contained in
the text. GenWiki also has a third component, namely entities, which are
extracted from the text, but not necessarily contained within the graph. These
entities are used to construct both the graph and text for both the graph
generation and text generation tasks, respectively. While valuable for
unsupervised learning in knowledge graph-to-text, we note that this may not
model the knowledge graph-to-text problem, where all entities should be
contained within the KG and one may not have access to the text in order to
extract the shared entities. Similarly, WikiGraphs was created by matching
WikiText-103 [27] articles with KGs from Freebase [48]. While the KGs and text
in WikiGraphs are not tightly coupled, WikiGraphs instead focuses on pairing
large KGs, containing about 39 nodes per KG, with large texts (complete
Wikipedia articles). While valuable for generating long text, this may not
accurately represent the supervised graph-to-text problem, where the text
should be a complete representation of the graph. Thus, WikiGraphs is most
comparable to works such as GenWiki [15].

EventNarrative sources event items from the more recently established EventKG
[9], an event-centric fusion-based KG. Previous works employing EventKG
include work on timeline generation [10], event series completion [11], and
event-centric question answering [44]. While EventKG contains facts which
involve location, time, and event actors, we enrich EventNarrative by
extracting all related facts from a given event item, so that the graphs can
better align with their corresponding narratives. Although out of scope for
this paper, it is worth mentioning some related work on KG completion and
temporal prediction that only rely on the KG itself [24, 43, 17, 42, 1, 41,
29].

##  3 Dataset Creation

This section explains our data creation process. We detail the various data
sources used to extract events, our algorithm to match entities and text, and
the graph generation technique we used to produce our final narratives and
KGs. An overview of our methodology can be found in Figure 2.

###  3.1 Sources

The knowledge graphs in EventNarrative are first sourced from EventKG [9], a
multilingual event-centric KG which incorporates events from Wikidata,
DBpedia, YAGO, the Wikipedia Current Events Portal, and the Wikipedia events
list. Each event contains information on where it was extracted from and any
aliases or alternative names for the event, if any. Properties of these events
in EventKG include temporal information such as the hasBeginTimeStamp,
hasEndTimeStamp, startUnitType, and endUnitType relations, as well as spatial
information with hasPlace. Events are also connected with the previousEvent
and nextEvent relations. We then filter and keep events which are extracted
from Wikidata and linked to a Wikipedia page. We do so because Wikipedia
articles, and thus the items found in the text/narrative, are directly used to
construct Wikidata, which can be queried through the Wikidata query service
using an article’s Wikidata Q identifier (QID). In total, we collect an
initial set of 322,674 graph events that have both a Wikidata and Wikipedia
resource link through EventKG.

EventKG contains a large number of events, with information pertaining to
location, time, as well as actors involved in the events. Yet, many relations
and properties found on Wikidata can be missing from EventKG. We therefore
query Wikidata to get an event item’s related properties, objects, and labels
through the SPARQL-based Wikidata query
service111https://www.mediawiki.org/wiki/Wikidata_Query_Service. We do so by
obtaining an event’s Wikidata QID from EventKG and querying the Wikidata
online query service, taking precautions to not overload the service by
writing aggregate queries to obtain results for multiple events in parallel.
We also query for each object’s QID, as it is of use in the entity matching
component. Because some relations and properties between EventKG and Wikidata
overlap, we first normalize all temporal or location-based relations from
EventKG into their corresponding Wikidata property names and remove any
duplicates. Next, we filter any events which do not contain a type, e.g.,
sports season, battle, or election. This type is represented though the
relation wikidata_type_label from EventKG or instance of from Wikidata. By
keeping types, future research can filter EventNarrative by event type or
incorporate the types into their knowledge graph-to-text models. After
filtering, the dataset contains 317,364 graph events.

When narrating an event, important details such as actors involved or sub-
events often lie deeper inside the Wikipedia article itself. While previous
work on both table-to-text and knowledge graph-to-text has limited the size
and locality of the textual data [18, 50, 15], we retrieve an event article’s
whole Wikipedia text to capture all of an event’s textual details—the Full
Text Merge step. We then filter out extraneous details contained within square
or curly braces, which typically denote altered or omitted information.
Consequently, some Wikidata events have no Wikipedia article. After retrieving
the whole text, there are 316,281 KG-text pairs.

###  3.2 Entity Matching

To match the in-text tokens with their corresponding KG triples, we devise an
extensive entity matching technique which is specialized for event data, but
can be fitted to capture other types of data. First, similar to Wang et al.
[50], we locate all the hyperlinks in the Wikipedia text and identify their
QIDs. After doing so, we match these QIDs with the ones captured from the
Wikidata graph in the previous step, preserving those entities which have a
match. In-text entities in Wikipedia articles often do not have any links to
Wikidata. To overcome this, we check for exact matches between the Wikidata
property items and in-text tokens, saving those with a match. One drawback of
the exact match method is that Wikidata entities are shorter in length and may
overlap with Wikipedia text that was better suited for a longer Wikidata
entity. We therefore first sort all the Wikidata property entities by length,
longest to shortest, before executing our exact match step. This step also
allows us to match properties from the Wikidata graphs that are numerical or
dates, but only if the date format matches that found within Wikipedia text.

Dates are crucial components for any event-centric dataset. We therefore
design a separate module to match Wikidata dates within our KG set to those
from the Wikipedia text, making our entity matching algorithm biased towards
event-centric data. In order to construct an exhaustive search algorithm for
in-text Wikipedia dates, we refer to the Wikipedia Style Manual
222https://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style/Dates_and_numbers#Formats
which defines acceptable date formats when editing Wikipedia articles. We
write regular expression patterns (RegEx) to match these formats as well as
others observed when manually reviewing the EventNarrative dataset. By
manually iterating through both the Wikidata graphs and Wikipedia text, we
note that many dates only have an overlap in month or year. Therefore, if a
date from Wikidata is not found through the RegEx patterns, we match the date
if it contains a monthly or yearly overlap. We replace those matches in the
narrative with their corresponding match in the KG in order to normalize the
graph-text pairs. After performing the entity matching step, we filter out
those pairs for which we found no matches, keeping 315,724 KG-text pairs.

Our entity matching technique prioritizes a high recall, where dates and
entities may overlap but not correctly match. To verify our entity matching
technique, we sampled 500 events from our final dataset and recruited workers
to note any errors in the data related to the linked entities and matching
relations. Details can be found in Section 4.

###  3.3 Narrative KG Generation

For every graph-text pair ($\bm{G}$, $\bm{T}$) obtained so far, we recursively
discard sentences (and nodes) from $\bm{T}$ (and $\bm{G}$) until all remaining
sentences have at least 2 entities in $\bm{G^{\prime}}$. This is necessary in
order to reduce textual noise. Otherwise, we would have texts that could not
be generated given the information contained in the graph. Figure 1, shows an
example parallel narrative, which contains triples from the KG. During this
process, if any of the $\bm{G}$ or $\bm{T}$ become empty, we discard the pair.
The result is a connected graph which represents the current filtered
narrative text. One could achieve similar results using a simpler sentence
level approach. However, this rather intricate approach of constructing the
graph-text pairs using the complete text preserves triples that are not fully
explainable through a single sentence. In the end, we are left with 224,428
KG-text pairs. More in-depth analysis on the final EventNarrative dataset are
presented in Section 4.

###  3.4 Limitations

Our dataset construction methodology is not without limitations. The narrative
KGs are of course limited to the elements and relations found in Wikidata,
which itself is incomplete, causing it to miss entities found within the
narrative text. We knowingly discard sentences which may contain co-references
to events. While initially creating the dataset, we experimented with current
state-of-the-art co-reference resolution systems, but they performed poorly on
event-centric data. This may be because of the overlap between event names and
their property names, e.g., “2013-2014 Manchester City F.C. season” and
“Manchester City”. Because event names and their properties may have a high
overlap, we do not perform any fuzzy matching techniques to extract events.

##  4 Dataset Analysis

We compare EventNarrative with four popular knowledge graph-to-text datasets,
including: WebNLG 2017 [8], AGENDA [16], GenWiki [15], and WikiGraphs [48].
Note that because WebNLG 2017 contains multiple texts per graph with an n:1
relationship, we decouple each text from its corresponding graph before
analyzing the data. Though GenWiki is a non-parallel dataset primarily
constructed for unsupervised learning, we wish to also highlight other key
differences. We include both renditions of GenWiki, full and fine, where fine
has a tighter entity overlap threshold. Likewise, we include WikiGraphs,
though each KG is loosely coupled with their corresponding Wikipedia text.

Table 1: Overview of current knowledge graph-to-text datasets. A dataset has
an Entity Match if all entities from the KG are contained in the narrative. A
dataset has a Triple Match if all entities are linked to the KG’s triples.

Dataset | KGs | Entity Match | Triple Match | Domain | Ontology | Text | Parallel
---|---|---|---|---|---|---|---
WebNLG 2017 | 9,674 | ✓ | ✓ | 15 Categories | DBpedia | Crowdsourced | ✓
AGENDA | 40,720 | ✓ | ✗ | Semantic Scholar | N/A | Scientific abstracts | ✓
GenWIKI (full) | 1,336,766 | ✗ | ✗ | General Domain | DBpedia | 1-10 Wiki sentences | ✗
GenWIKI (fine) | 757,152 | ✗ | ✗ | General Domain | DBpedia | 1-10 Wiki sentences | ✗
WikiGraphs | 23,522 | ✗ | ✗ | General Domain | Freebase | Full Wiki text | ✗
EventNarrative | 224,428 | ✓ | ✓ | Events | Wikidata | Full Wiki text | ✓

22footnotetext: Note that we compare the WebNLG 2017 dataset released after
the challenge, which contains 15 categories found on: https://webnlg-
challenge.loria.fr/challenge_2017/.

###  4.1 Dataset Synopsis

We begin by first performing a high-level analysis of current knowledge graph-
to-text datasets. Among all the parallel datasets in Table 1, our proposed
EventNarrative is the largest, having 6 times more KGs than the second largest
dataset (AGENDA) and 25 times more than the manually annotated WebNLG.
Although GenWiki is larger than EventNarrative, many entities and relations
from the triples are not contained within the text and many entities from the
text are not found in the graphs. The dataset is purposely created for
unsupervised learning and does not model the knowledge graph-to-text
supervised task. As AGENDA contains isolated entities that do not belong to
triples, the only other dataset with perfect matches between the text and
graphs, WebNLG 2017, was hand-crafted, limiting the number of samples
generated. Since the text was handcrafted in WebNLG-2017, iterative
improvements on the dataset such as standardizing the entities and relations
within the text based on an ontology becomes extremely challenging.
Conversely, because the narratives found in EventNarrative are sourced from
Wikipedia, various existing tools can be used to improve the entity matching
algorithm. Therefore, EventNarrative is the only dataset that is large-scale,
ontology-based, utilizes an open real-world KG, may be used for supervised
learning, and contains connected graphs that are fully contained within a text
narrative.

Figure 3: Examples of KG-narrative pairs from EventNarrative. Linked entities
are color coded.

###  4.2 Statistical Analysis

We now take a closer look at EventNarrative, demonstrating that our dataset
contains a large amount of variable data, with closely aligned KG-narrative
pairs. Table 2 presents some in-depth statistics between the current
supervised knowledge graph-to-text datasets, including: WebNLG 2017, AGENDA,
and the proposed EventNarrative. We exclude GenWiki and WikiGraphs from this
analysis because these datasets does not meet the requirements of being
parallel, and their entities/triples do not completely align with the text.

Table 2: Statistics of the current parallel knowledge graph-to-text datasets.
We report the total number of KG components, number of tokens in the
narratives (including the percentage which encompass entity tokens), and
overall mean statistics for both the KGs and narratives.

| KG | Tokens | Mean
---|---|---|---
Dataset | Entities | Relations | Triples | Total | Unique | Entity | Triples | Text Length | Entities in Text | Triples/Sentence
WebNLG 2017 | 2730 | 354 | 81,927 | 623,902 | 8,075 | 60% | 2.95±1.55 | 22.50±11.24 | 57%±23 | 2.12±0.98
AGENDA | 159,691 | 7 | 180,603 | 5,760,660 | 77,896 | 27% | 4.43±3.19 | 141.47±40.92 | 27%±7% | 0.81±0.74
EventNarrative | 305,685 | 672 | 656,302 | 11,352,387 | 222,338 | 25% | 2.92±2.48 | 50.58±58.59 | 32%±13% | 1.82±1.12

From table 2 we see that EventNarrative has approximately 110 times more
entities, 2 times more relations, and 8 times more triples than WebNLG 2017,
the only other dataset containing no disconnected entities between the KG and
text. Unlike [15], we choose not to limit our relations for two reasons: (1)
our dataset is not open-domain as in [15], (2) our aim is to build a
challenging dataset which simulates real-world KGs. Even so, with 305,685
entities and 224,428 graph-narrative pairs, 672 relations are tractable.

While the AGENDA dataset contains more triples on average per sample, it
contains less than one triple on average per sentence, while also holding the
longest mean text length throughout all of its samples 333All data were
tokenized with NLTK: https://www.nltk.org/. EventNarrative contains an average
of about two triples per sentence, and contains a more stable text length at
approximately 51 tokens. Though both the AGENDA and EventNarrative datasets
are almost equivalent in the percentage of text tokens that are entities,
recall that in AGENDA not all entities belong to a triple, with approximately
49% of the entities missing from their KG.

As expected, WebNLG 2017 has the highest percentage of entity tokens in the
overall text, average percentage of entity tokens in its text per sample, and
average number of triples per sentence, as the dataset is hand-crafted and
human verified. Though automatically generated, EventNarrative is comparable
to WebNLG 2018 in number of triples per sentence, suggesting that our dataset
creation process may closely simulate human annotation.

Another notable aspect of EventNarrative is its high variability between
samples, as shown by the variance in the number of triples and text length.
This makes EventNarrative a complex yet practical dataset for modeling the
knowledge graph-to-text problem, verifying our claim that event data is highly
variable in length.

We illustrate the distributions of event types and relations in figure 4. The
top 10 event types include: sports season, American football season, sporting
event, tennis tournament edition, battle, election, basketball team season,
association football team season, Olympic sporting event, and nation at sport
competition. The top 10 relations include: point in time, location, country,
sport, start time, instance of, end time, part of, sports season of league or
competition, and winner. While EventNarrative is highly variable in its length
per sample, the type and relation distributions reveal that a plurality of the
events are sports related. Intuitively, this makes sense, as there are many
yearly and even monthly sports-related events. EventNarrative also includes a
substantial amount of battles, award ceremonies, legal cases, finals,
bilateral relations, and elections. Future work using GraphWriter can filter
events by types based on their needs.

(a) Distribution of top 10 event types.

(b) Distribution of top relations.

Figure 4: Distribution of most frequent types and relations in EventNarrative.

###  4.3 Qualitative Analysis

In this section, we evaluate our dataset based on how closely it resembles
human annotations. To do so, we recruit 3 annotators to manually check 500
randomly sampled KG-text pairs from EventNarrative. To ensure quality, we
recruited annotators that have experience in KG research. We first ask the
annotators to verify (and count) if all entities and relations contained
within the KG are correct with respect to the narrative. We do so in order to
verify both the Entity Matching and Narrative KG Generation steps from our
dataset creation process. Table 3 demonstrates that both the entities and
relations from the KGs are indeed tightly coupled with their respective
narratives. When aggregating all the annotators’ results, approximately 96% of
all entities and 95% of all relations in the sample were deemed correct. On a
coarser level, 397 of the KGs had no errors of any type. We found an 100%
agreement when measuring the kappa value among the annotators, meaning that
all annotators found entity, relation, or both types of errors in the same
samples. To more closely evaluate each data generation step, including the
sources and RegEx matching, we asked annotators about the different errors
they encountered. They reported that most entities which are incorrectly
paired are either mischaracterized by Wikipedia or are dates that have
different scopes between the KG and source narrative; i.e., containing the day
and month of an event within the text but only containing the year within the
KG.

Three different types of events from EventNarrative are shown in figure 3:
tournament, gubernatorial election, and battle. The first row shows an example
error in our date processing. The original text stated “1–2 November 2014” but
is incorrectly replaced with “2014-2014” because of the different scope of
dates between the KG and narrative.

Table 3: Qualitative analysis results: entities correct (EC), entities
incorrect (EI), relations correct (RC), relations incorrect (RI).

(a) Correct/incorrect per KG-narrative pair. | EC | EI
---|---|---
RC | 397 | 57
RI | 30 | 16

(b) Total correct entities and relations (percentage). EC | % RC
---|---
$95.56\pm 4.0$ | $95.50\pm 4.0$

##  5 Benchmark Evaluation

Our aim is to establish a dataset which can be used to help advance the state-
of-the-art in transforming knowledge graphs to natural language narratives. We
begin this work by comparing established supervised knowledge graph-to-text
baselines on EventNarrative. Currently, there are two approaches to this task:
first, modeling the problem with a graph transformer-based network; second,
treating the problem as a summarization task by finetuning on pretrained
language models (PLMs). The graph transformer-based network we experiment with
is GraphWriter [16], a model which can capture local and global information
when encoding a graph. Second, we experiment by finetuning on two prominent
pretrained language models (PLM), BART [21] and T5 [36], which have been shown
to outperform graph-to-text specific models on the AGENDA and WebNLG 2017
datasets [39].

###  5.1 Experimental Setup

We divide the dataset into an 80/10/10 train/dev/test split. During the
training of BART and T5, we frequently evaluate on the dev set for model
selection. Due to the high computational overhead imposed by the decoding
step, we chose to only use a subset of the dev set for training. We use this
same random subset for model selection for both BART and T5. For all models,
the final reported metrics are on the full test set. All experiments were
performed on NVIDIA RTX 2080 Ti GPUs.

For the GraphWriter model, we use the version provided by Guo et al. [12]
which utilizes the Deep Graph Library (DGL) [49]. We keep its default
parameters of: a learning rate of 2·10-4 size batch size of 32, a beam size of
5, 4 attention heads, and train for 30 epochs444For more details, see
https://github.com/QipengGuo/CycleGT.

To finetune on EventNarrative with BART and T5, we follow a procedure similar
to that of [39], prepending “translate from Graph to Text” to the source
(graph) data for the T5 model and adding the subject <$S$>, predicate <$P$>,
object <$O$> tokens into the vocabulary for both PLMs. All of our PLM
experiments are done using the base models released by HuggingFace [52]. Given
the computational complexity of BART and T5, we choose to follow [39]’s setup,
using the Adam optimizer and linearly decreasing learning rate scheduler
without warm-up with an initial learning rate of 3·10-5. We use a batch size
of 2 and beam search size of 3. The dev set’s BLEU score is used for model
selection.

Table 4: Narrative generation results for EventNarrative. The best result for
each metric is in bold.

| BLEU | chrF++ | CIDEr | METEOR | ROUGE | BERTScore
---|---|---|---|---|---|---
GraphWriter | 30.78 | 47.91 | 4.59 | 27.72 | 71.92 | 92.12
T5base | 12.8 | 56.76 | 3.00 | 22.77 | 52.06 | 89.59
BARTbase | 31.38 | 64.71 | 3.31 | 26.68 | 62.65 | 93.12

###  5.2 Results

We evaluate EventNarrative on frequently used NLG evaluation metrics: BLEU
[32], chrF++ [33, 34], CIDEr [46], METEOR [2], and ROUGE [23]. Additionally,
as in [39], we also evaluate the test set using BERTScore [55] which computes
text similarity based on contextualized embeddings. Table 4 presents the
results for each baseline model. Overall, for the EventNarrative dataset, the
GraphWriter and BART models give similar results, both significantly
outperforming T5. The GraphWriter model outperforms BART on CIDEr, METEOR, and
ROUGE_L, while BART performs best on BLEU and BERTScore. The poor results of
T5 may be because of the difference in data that BART and T5 were originally
trained on. BART was trained on news articles, which can closely resemble
events. Overall, our results show that graph-to-text specific models are still
competitive to PLMs and deserve further investigation.

##  6 Discussion and Conclusion

EventNarrative closely resembles the available KGs and can be used to generate
narratives in a supervised manner. This is enabled by its large size, rich
ontology, and variability within the data. Our human qualitative analysis
verified that about 96% of entities and relations are correctly matched.

Our dataset generation framework is automated, therefore EventNarrative can be
re-assembled and extended with other ontological KGs such as DBpedia or YAGO.
We will periodically improve and update EventNarrative, as the nature of the
dataset depends on continuously adding new events. The dataset generation
framework can also be adapted to other types of entity-centric data in order
to generate rich and more tightly-coupled sets of knowledge graph-to-text
data.

EventNarrative provides the community with new challenges because of the
variety within its data, while also providing new insights into knowledge
graph-to-text baselines. Previous parallel datasets have been lacking because
of their size, loosely coupled triples, and sparsity, all of which can
saturate the results of current baselines. EventNarrative is tightly coupled,
allowing researchers to focus on generating proficient models which narrate
real-world KGs. We hope that EventNarrative can enable ground-breaking new
work in knowledge graph-to-text and event-centric research.

##  7 Broader Impact

EventNarrative can assist researchers in other fields in studying different
graph structured data (e.g., events that are represented as graphs) by
providing them with easily readable narratives. At the same time, as a text
generation dataset, there are risks concerning generating fake news and
disinformation, specifically related to recent or current events which may
appear in the dataset. This can especially occur if the language produced from
the KG looks fluent but is completely fabricated [51]. While all of our
narratives are extracted from Wikipedia and this issue may not be apparent, we
discourage anyone from substituting any text with those that may spread
disinformation.

## Acknowledgements

This work is partially funded and supported by the GSPA at the University of
Florida, the McKnight Doctoral Fellowship, the NSF under IIS Award #1526753,
and DARPA under Award #FA8750-18-2-0014(AIDA/GAIA). We would also like to
thank the annotators and members of the Data Science Research Lab at the
University of Florida who helped throughout this work.

## References

  * [1] Ivana Balažević, Carl Allen, and Timothy M Hospedales.  Tucker: Tensor factorization for knowledge graph completion.  arXiv preprint arXiv:1901.09590, 2019.
  * [2] Satanjeev Banerjee and Alon Lavie.  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, 2005.
  * [3] Hangbo Bao, Li Dong, Furu Wei, Wenhui Wang, Nan Yang, Xiaodong Liu, Yu Wang, Songhao Piao, Jianfeng Gao, Ming Zhou, and Hsiao-Wuen Hon.  Unilmv2: Pseudo-masked language models for unified language model pre-training.  In Preprint, 2020.
  * [4] Yunmo Chen, Tongfei Chen, Seth Ebner, Aaron Steven White, and Benjamin Van Durme.  Reading the manual: Event extraction as definition comprehension.  In Proceedings of the Fourth Workshop on Structured Prediction for NLP, pages 74–83, 2020.
  * [5] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, 2019.
  * [6] Xinya Du and Claire Cardie.  Event extraction by answering (almost) natural questions.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 671–683, 2020.
  * [7] Michel Galley, Chris Brockett, Xiang Gao, Jianfeng Gao, and Bill Dolan.  Grounded response generation task at dstc7.  In AAAI Dialog System Technology Challenges Workshop, 2019.
  * [8] Claire Gardent, Anastasia Shimorina, Shashi Narayan, and Laura Perez-Beltrachini.  Creating training corpora for nlg micro-planning.  In 55th annual meeting of the Association for Computational Linguistics (ACL), 2017.
  * [9] Simon Gottschalk and Elena Demidova.  Eventkg: A multilingual event-centric temporal knowledge graph.  In European Semantic Web Conference, pages 272–287. Springer, 2018\.
  * [10] Simon Gottschalk and Elena Demidova.  Eventkg–the hub of event knowledge on the web–and biographical timeline generation.  Semantic Web, 10(6):1039–1070, 2019.
  * [11] Simon Gottschalk and Elena Demidova.  Happening: Happen, predict, infer — event series completion in a knowledge graph.  In Proceedings of the International Semantic Web Conference (ISWC 2019). Springer, 2019.
  * [12] Qipeng Guo, Zhijing Jin, Xipeng Qiu, Weinan Zhang, David Wipf, and Zheng Zhang.  CycleGT: Unsupervised graph-to-text and text-to-graph generation via cycle training.  In Proceedings of the 3rd International Workshop on Natural Language Generation from the Semantic Web (WebNLG+), pages 77–88, Dublin, Ireland (Virtual), 12 2020. Association for Computational Linguistics.
  * [13] Karl Moritz Hermann, Tomáš Kočiskỳ, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom.  Teaching machines to read and comprehend.  In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 1, pages 1693–1701, 2015.
  * [14] Anja Jentzsch.  Linked open data cloud.  In Linked enterprise data, pages 209–219. Springer, 2014.
  * [15] Zhijing Jin, Qipeng Guo, Xipeng Qiu, and Zheng Zhang.  Genwiki: A dataset of 1.3 million content-sharing text and graphs for unsupervised graph-to-text generation.  In Proceedings of the 28th International Conference on Computational Linguistics, pages 2398–2409, 2020.
  * [16] Rik Koncel-Kedziorski, Dhanush Bekal, Yi Luan, Mirella Lapata, and Hannaneh Hajishirzi.  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, 2019.
  * [17] Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski.  Canonical tensor decomposition for knowledge base completion.  In International Conference on Machine Learning, pages 2863–2872. PMLR, 2018.
  * [18] Rémi Lebret, David Grangier, and Michael Auli.  Neural text generation from structured data with application to the biography domain.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1203–1213, 2016.
  * [19] Kalev Leetaru and Philip A Schrodt.  Gdelt: Global data on events, location, and tone, 1979–2012.  In ISA annual convention, volume 2, pages 1–49. Citeseer, 2013\.
  * [20] Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, et al.  Dbpedia–a large-scale, multilingual knowledge base extracted from wikipedia.  Semantic web, 6(2):167–195, 2015.
  * [21] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7871–7880, 2020.
  * [22] Sha Li, Heng Ji, and Jiawei Han.  Document-level event argument extraction by conditional generation.  In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 894–908, 2021.
  * [23] Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In Text summarization branches out, pages 74–81, 2004.
  * [24] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu.  Learning entity and relation embeddings for knowledge graph completion.  In Twenty-ninth AAAI conference on artificial intelligence, 2015\.
  * [25] Yi Luan, Luheng He, Mari Ostendorf, and Hannaneh Hajishirzi.  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, 2018.
  * [26] John P. McCrae.  In https://lod-cloud.net/#subclouds, 2021.
  * [27] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher.  Pointer sentinel mixture models.  arXiv preprint arXiv:1609.07843, 2016.
  * [28] Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Caglar Gulcehre, and Bing Xiang.  Abstractive text summarization using sequence-to-sequence rnns and beyond.  In Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning, pages 280–290, 2016.
  * [29] Mojtaba Nayyeri, Gokce Muge Cil, Sahar Vahdati, Francesco Osborne, Mahfuzur Rahman, Simone Angioni, Angelo Salatino, Diego Reforgiato Recupero, Nadezhda Vassilyeva, Enrico Motta, et al.  Trans4e: Link prediction on scholarly knowledge graphs.  Neurocomputing, 2021.
  * [30] Neal R Norrick.  Twice-told tales: Collaborative narration of familiar stories.  Language in society, pages 199–220, 1997.
  * [31] Sean P O’brien.  Crisis early warning and decision support: Contemporary approaches and thoughts on future research.  International studies review, 12(1):87–104, 2010.
  * [32] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  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, 2002.
  * [33] Maja Popović.  chrf: character n-gram f-score for automatic mt evaluation.  In Proceedings of the Tenth Workshop on Statistical Machine Translation, pages 392–395, 2015.
  * [34] Maja Popović.  chrf++: words helping character n-grams.  In Proceedings of the second conference on machine translation, pages 612–618, 2017.
  * [35] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  OpenAI blog, 1(8):9, 2019.
  * [36] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  Journal of Machine Learning Research, 21:1–67, 2020.
  * [37] Thomas Rebele, Fabian Suchanek, Johannes Hoffart, Joanna Biega, Erdal Kuzey, and Gerhard Weikum.  Yago: A multilingual knowledge base from wikipedia, wordnet, and geonames.  In International semantic web conference, pages 177–185. Springer, 2016.
  * [38] Siva Reddy, Danqi Chen, and Christopher D Manning.  Coqa: A conversational question answering challenge.  Transactions of the Association for Computational Linguistics, 7:249–266, 2019.
  * [39] Leonardo FR Ribeiro, Martin Schmitt, Hinrich Schütze, and Iryna Gurevych.  Investigating pretrained language models for graph-to-text generation.  arXiv e-prints, pages arXiv–2007, 2020.
  * [40] Alexander M Rush, Sumit Chopra, and Jason Weston.  A neural attention model for abstractive sentence summarization.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 379–389, 2015.
  * [41] Ali Sadeghian, Mohammadreza Armandpour, Anthony Colas, and Daisy Zhe Wang.  Chronor: Rotation based temporal knowledge graph embedding.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6471–6479, 2021.
  * [42] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang.  Drum: End-to-end differentiable rule mining on knowledge graphs.  Advances in Neural Information Processing Systems, 32:15347–15357, 2019.
  * [43] Ali Sadeghian, Miguel Rodriguez, Daisy Zhe Wang, and Anthony Colas.  Temporal reasoning over event knowledge graphs.  2016\.
  * [44] Tarcísio Souza Costa, Simon Gottschalk, and Elena Demidova.  Event-qa: A dataset for event-centric question answering over knowledge graphs.  In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 3157–3164, 2020.
  * [45] Yu Sun, Shuohuan Wang, Yukun Li, Shikun Feng, Hao Tian, Hua Wu, and Haifeng Wang.  Ernie 2.0: A continual pre-training framework for language understanding.  arXiv preprint arXiv:1907.12412, 2019.
  * [46] Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh.  Cider: Consensus-based image description evaluation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4566–4575, 2015.
  * [47] Denny Vrandečić and Markus Krötzsch.  Wikidata: a free collaborative knowledgebase.  Communications of the ACM, 57(10):78–85, 2014.
  * [48] Luyu Wang, Yujia Li, Ozlem Aslan, and Oriol Vinyals.  Wikigraphs: A wikipedia text-knowledge graph paired dataset.  In Proceedings of the Fifteenth Workshop on Graph-Based Methods for Natural Language Processing (TextGraphs-15), pages 67–82, 2021.
  * [49] Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al.  Deep graph library: Towards efficient and scalable deep learning on graphs.  2019\.
  * [50] Qingyun Wang, Xiaoman Pan, Lifu Huang, Boliang Zhang, Zhiying Jiang, Heng Ji, and Kevin Knight.  Describing a knowledge base.  In Proceedings of the 11th International Conference on Natural Language Generation, pages 10–21, 2018.
  * [51] Claire Wardle and Hossein Derakhshan.  Information disorder: Toward an interdisciplinary framework for research and policy making.  Council of Europe, 27, 2017.
  * [52] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  arXiv preprint arXiv:1910.03771, 2019.
  * [53] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  Advances in Neural Information Processing Systems, 32:5753–5763, 2019.
  * [54] Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston.  Personalizing dialogue agents: I have a dog, do you have pets too?  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2204–2213, 2018.
  * [55] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  In International Conference on Learning Representations, 2019.