# Alpha-Fair Routing in Urban Air Mobility with Risk-Aware Constraints

Yue Yu, Zhenyu Gao, Sarah H.Q. Li, Qinshuang Wei, John-Paul Clarke, and Ufuk
Topcu Y. Yu, Q. Wei, and U. Topcu are with the Oden Institute for
Computational Engineering and Sciences, The University of Texas at Austin,
Austin, TX, 78712, USA (emails<EMAIL_ADDRESS><EMAIL_ADDRESS>utopcu@utexas.edu). Z. Gao and J-P. Clarke are with the Department of
Aerospace Engineering and Engineering Mechanics, The University of Texas at
Austin, Austin, TX, 78712, USA (email<EMAIL_ADDRESS>johnpaul@utexas.edu). Sarah H.Q. Li is with the Autonomous Control Laboratory,
ETH Zürich, Zürich, Switzerland (email: sarahli@control.ee.ethz.ch).

###### Abstract

In the vision of urban air mobility, air transport systems serve the demands
of urban communities by routing flight traffic in networks formed by
vertiports and flight corridors. We develop a routing algorithm to ensure that
the air traffic flow fairly serves the demand of multiple communities subject
to stochastic network capacity constraints. This algorithm guarantees that the
flight traffic volume allocated to different communities satisfies the _alpha-
fairness conditions_ , a commonly used family of fairness conditions in
resource allocation. It further ensures robust satisfaction of stochastic
network capacity constraints by bounding the coherent risk measures of
capacity violation. We prove that implementing the proposed algorithm is
equivalent to solving a convex optimization problem. We demonstrate the
proposed algorithm using a case study based on the city of Austin. Compared
with one that maximizes the total served demands, the proposed algorithm
promotes even distributions of served demands for different communities.

##  I Introduction

Urban air mobility (UAM) aims to provide sustainable and accessible air
transport services at low altitudes in metropolitan areas [1, 2]. Recent
advancements in electrification, automation, and digitalization have enabled
many technological innovations for aviation, such as those for electric
vertical take-off and landing aircraft, unmanned aerial systems, and automated
air traffic management. Together these innovations will facilitate a wide
range of urban aviation tasks, such as passenger mobility, goods delivery, and
emergency services.

One challenge in UAM is to allocate limited and uncertain amounts of network
resources _fairly_ to different flights. On the one hand, the capacity of the
transportation network in UAM, defined by its vertiports and flight corridors,
is both limited—due to construction budget [3], noise pollution regulations
[4], and safety concerns for navigation [5]—and uncertain—due to stochastic
weather conditions, dynamic obstacles [6], and emergencies. The air traffic
routed through the network must robustly satisfy these uncertain capacity
constraints. On the other hand, the network must support flights between
multiple origins and destinations to serve the demands of different user
groups.

The existing methods for air traffic management with fairness considerations
mainly focus on allocating delays fairly among different flights. These
methods allocate delays to different flights by minimizing certain deviations
from a target allocation [7, 8, 9]. This target allocation typically satisfies
certain desired principles, such as the ration-by-distance principle, which
prioritizes flights according to their flight distances [8, 9], or the ration-
by-schedule principle, which preserves the first-scheduled-first-served
ordering of flights [10]. Different planning methods minimize different
deviation functions, such as the amount of overtaking and number of reversals
in the ordering of flights [11, 12], the amount by which the total delay
exceeds the maximum expected delay along a route [10, 12], the proportion of
the total delays allocated to an airline divided by its peak requests [13,
14], and the lexicographical worst-case deviation among different flights
[15]. Recent results in UAM also consider fairness under uncertainties [16].

However, these existing methods focus on fairness among the service providers,
such as different airlines, rather than fairness among service receivers, such
as users from different communities. In particular, they seek fair
distribution of flight delays based on the flight distances [8, 9] or the
schedules requested by different airlines [10], not the origin and destination
of the flights. In the context of UAM, a paramount question regarding how to
ensure fairness in serving the demands of multiple user communities—which is
among the largest barriers to UAM’s community acceptance [1, 2]—is, to our
best knowledge, still an open question.

We develop a routing algorithm for UAM to fairly serve the demands of
different communities subject to stochastic network capacity. This algorithm
has two key features. First, it ensures that the air traffic volume serving
the demands of different communities satisfies the _alpha fairness conditions_
, a general class of fairness conditions in resource allocation that includes
many different fairness notions, such as proportional fairness, total delay
fairness, and max-min fairness [17, 18]. Second, it ensures robust
satisfaction of stochastic capacities constraints of vertiports and flight
corridors by bounding the coherent risk measures of capacity violation. We
prove that implementing this algorithm is equivalent to solving a convex
optimization problem with conic constraints. We demonstrate this algorithm
using a case study based on the city of Austin. Compared with one that
maximizes the total demands served, the proposed algorithm consistently
promotes even distributions of demands served for different communities.

##  II Alpha-fair routing in urban air mobility

We introduce the alpha-fair routing problem in urban air mobility (UAM). The
idea is to maximize the total utility function of the services in the form of
payloads allocated to different communities subject to network flow
constraints.

Throughout, we use the following notations. We let $\mathbb{R}$,
$\mathbb{R}_{\geq 0}$, and $\mathbb{N}$ denote the set of real numbers,
nonnegative real numbers, and nonnegative integers, respectively. We let
$0_{n}$ and $1_{n}$ denote the $n$-dimensional zero vector and all 1’s vector,
respectively. Given $n_{1},n_{2}\in\mathbb{N}$, we let $[n_{1},n_{2}]$ denote
the set of integers between $n_{1}$ and $n_{2}$. We let
$\Delta_{n}\subset\mathbb{R}^{n}$ denote the $n$-dimensional probability
simplex.

###  II-A Nodes, links, and routes

We model the transportation network using a directed graph $\mathcal{G}$
composed of a set of nodes $\mathcal{N}=\\{1,2,\ldots,n_{n}\\}$, each of which
corresponds to either a vertiport or a waypoint that marks the intersection of
multiple flight corridors, and a set of links
$\mathcal{L}=\\{1,2,\ldots,n_{l}\\}$, each of which corresponds to a flight
corridor. Each link is an ordered pair of distinct nodes, where the first and
second nodes are the “tail” and “head” of the link, respectively. A _route_ is
a sequence of links connected in a head-to-tail fashion. We let
$\mathcal{R}=\\{1,2,\ldots,n_{r}\\}$ denote a set of routes, which does not
necessarily contain all possible routes in $\mathcal{G}$. We will also use the
notion of _community_. Each route serves the demands of one or several of the
total of $n_{c}\in\mathbb{N}$ communities.

###  II-B Incidence matrices

We encode the topology of a graph $\mathcal{G}$ using the notion of _incidence
matrices_ , which, depending on its definition, describes which nodes each
link connects, which links each route contains, and which communities’ demands
each route serves. In particular, we describe the incidence relationship
between nodes and links using the node-link incidence matrix
$E\in\mathbb{R}^{n_{n}\times n_{l}}$. The entry $E_{ij}$ in matrix $E$ is
associated with node $i$ and link $j$ as follows:

$E_{ij}=\begin{cases}1,&\text{if node $i$ is the head of link $j$,}\\\
-1,&\text{if node $i$ is the tail of link $j$,}\\\
0,&\text{otherwise.}\end{cases}$ (1)

Similarly, we describe the incidence relationship between links and routes
using the link-route incidence matrix $F\in\mathbb{R}^{n_{l}\times n_{r}}$.
The entry $F_{ij}$ in matrix $F$ is associated with link $i$ and route $j$ as
follows:

$F_{ij}=\begin{cases}1,&\text{if route $j$ contains link $i$,}\\\
0,&\text{otherwise.}\end{cases}$ (2)

Finally, we describe the incidence relationship between communities and routes
using the community-route incidence matrix $H\in\mathbb{R}^{n_{c}\times
n_{r}}$. The entry $H_{ij}$ in matrix $H$ is associated with community $i$ and
route $j$ as follows:

$H_{ij}=\begin{cases}1,&\text{if route $j$ serves the demand of community
$i$,}\\\ 0,&\text{otherwise.}\end{cases}$ (3)

###  II-C Balanced flow constraints

To ensure that the number of vehicles at each node is balanced, the total
number of incoming vehicles must match the number of outgoing vehicles at each
node. We denote the number of aircraft vehicles on different links per unit
time using the _vehicle flow vector_ $y\in\mathbb{R}^{n_{l}}$. In particular,
the entry $[y]_{k}$ in vector $y$ denotes the number of vehicles that use link
$k$. We formulate this constraint as follows:

$Ey=0_{n_{n}},\,y\geq 0_{n_{l}}.$ (4)

If the constraint in (4) is violated, the vehicles will start to accumulate at
some nodes, which cause unwanted crowding.

###  II-D Vehicle capacity constraints

Whenever multiple routes share an overlapping link, the amount of payload
transported on each route is jointly constrained by the number of vehicles
scheduled on the overlapping link. To model this constraint, we first define
the _payload flow vector_ $z\in\mathbb{R}^{n_{r}}$ such that $z_{i}$ denotes
the number of payloads transported along route $i$. Next, based on the link-
route incidence matrix in (2), the vehicle flow vector and the payload flow
vector jointly satisfy the following constraint:

$Fz\leq y,\,z\geq 0_{n_{r}}.$ (5)

###  II-E Node and link capacity constraints

To ensure collision-free operation, the number of vehicles on each link and
node must be bounded. To model these constraints, we let $c\in\mathbb{R}_{\geq
0}^{n_{n}}$ and $d\in\mathbb{R}_{\geq 0}^{n_{l}}$ denote the nominal node and
link flow volume, respectively. In particular, the values of $c_{i}$ and
$d_{j}$ denote the maximum number of vehicles that enter node $i$ and link
$j$, respectively. Furthermore, we define a weighting matrix
$K\in\mathbb{R}^{n_{n}\times n_{l}}$ such that $K=\max\\{E,0\\}$ i.e., each
element in $K$ is the elementawise maximum of the corresponding element in
matrix $E$ and zero. Based on these matrices, we define the following _node
and link capacity constraints_ :

$Ky\leq(1+\epsilon)c,\,y\leq(1+\epsilon)d,$ (6)

where $\epsilon\in\mathbb{R}_{\geq 0}$ is a tolerance parameter. The
constraints in (6) state that the number of vehicles on each node or link does
not exceed the corresponding nominal value by more than $100\epsilon$ percent.

###  II-F Alpha-fair routing problem

Given the network constraints, we aim to route the air traffic to serve the
demands of multiple communities. Throughout we assume each community has
sufficiently high demands and we aim to maximize the demands we serve for each
community without violating network capacity constraints. To this end, we
introduce the _alpha-fair routing_ approach, which determines the amount of
payload allocated to each community via optimization. Let
$x\in\mathbb{R}^{n_{c}}_{\geq 0}$ denote the _community demand vector_ such
that $x_{k}$ denotes the payload demand we allocate to community $k$. The idea
of alpha-fair routing is to find an optimal allocation
$x^{\star}\in\mathbb{R}^{n_{c}}$ by solving the following optimization
problem:

$\begin{array}[]{ll}\underset{x,y,z}{\mbox{maximize}}&\sum_{k=1}^{n_{c}}\psi_{k}(x_{k})\\\
\mbox{subject to}&Ey=0_{n_{n}},\,x=Hz,\,Fz\leq y,\\\
&Ky\leq(1+\epsilon)c,\,y\leq(1+\epsilon)d,\\\ &y\geq 0_{n_{l}},\,z\geq
0_{n_{r}}\\\ \end{array}$ (7)

where $\alpha\in[0,\infty)$ is a fairness parameter, and $\psi_{\alpha}$ is
the _$\alpha$ -utility function_ defined as follows

$\psi_{k}(x_{k})=\begin{cases}\log(x_{k}),&\text{if $\alpha=1$},\\\
\frac{x_{k}^{1-\alpha}}{1-\alpha},&\text{if $\alpha\geq 0,\alpha\neq
1$}.\end{cases}$ (8)

The goal of optimization (7) is to find an optimal payload allocation that
satisfies a set of _fairness condition_. In particular, let
$x^{\star}\in\mathbb{R}^{n_{c}}$ be optimal for optimization (7). Then one can
prove that, for any $x\in\mathbb{R}^{n_{c}}$ such that $(x,y,z)$ satisfies the
constraints in (7) for some $y\in\mathbb{R}^{n_{l}}$ and
$z\in\mathbb{R}^{n_{r}}$, we must have

$\sum_{k=1}^{n_{c}}\frac{x_{k}-x_{k}^{\star}}{(x^{\star}_{k})^{\alpha}}\leq
0.$ (9)

The conditions in (9) are known as the _$\alpha$ -fairness conditions_ [17].
They include many popular notions of fairness in the network resource
allocation literature, including proportional fairness, total delay fairness,
and max-min fairness. We refer the interested readers to [17, Sec. 2.4] and
the references therein for further details on alpha-fairness.

##  III Risk-aware alpha-fair routing

One drawback of the routing problem in (7) is that it ignores the effects of
uncertainty in air mobility. In the following, we introduce a variation of the
routing problem in (7) that accounts for uncertain network capacity, which
occurs due to, for instance, weather conditions and emergency shutdowns. To
this end, we denote the capacity parameter as
$\omega\coloneqq\begin{bmatrix}c^{\top}&d^{\top}\end{bmatrix}^{\top}$.
Furthermore, we make the following assumption on $\omega$.

######  Assumption 1.

The parameter vector
$\omega\coloneqq\begin{bmatrix}c^{\top}&d^{\top}\end{bmatrix}^{\top}$ is a
discrete random variable with $N\in\mathbb{N}$ possible outcomes. Its sample
space is given by
$\\{\omega^{i}\coloneqq\begin{bmatrix}(c^{i})^{\top}&(d^{i})^{\top}\end{bmatrix}^{\top}\\}_{i=1}^{N}$,
where $c^{i}\in\mathbb{R}_{\geq 0}^{n_{n}}$ and $d^{i}\in\mathbb{R}_{\geq
0}^{n_{l}}$ for all $i\in[1,N]$.

In the following, we will discuss how to modify the capacity constraints in
(6) and the corresponding routing problem in (7) under Assumption (1)

###  III-A Alpha-fair routing with risk-aware constraints

If $(c,d)=(c^{i},d^{i})$ for some $i\in[1,d]$, then the capacity constraints
in (6) is equivalent to a constraint on the optimal value of a linear program.
In this case, one can show that (6) is equivalent to

$h_{i}^{\star}\leq\epsilon,$ (10)

where $h_{i}^{\star}\in\mathbb{R}$ is the optimal value of the following
linear program

$\begin{array}[]{ll}\underset{h_{i}}{\mbox{minimize}}&h_{i}\\\ \mbox{subject
to}&Ky\leq(1+h_{i})c^{i},\,y\leq(1+h_{i})d^{i},\,h_{i}\geq 0.\end{array}$ (11)

To see the equivalence between (6) and (10), notice that (6) implies that
$h_{i}=\epsilon$ satisfies the constraints in (11), hence (10) must hold. On
the other hand, if (10) holds, then letting $h_{i}=h_{i}^{\star}$ in the
constraints in (11) implies that (6).

To constrain the capacity violation under Assumption 1, we define a scalar-
valued random variable $\eta$ with a finite sample space
$\\{h^{\star}_{1},h^{\star}_{2},\ldots,h_{N}^{\star}\\}$, where
$h^{\star}_{i}$ is the optimal value of the deterministic linear program in
(11). In addition, we introduce a family of functions, denoted by
$\rho_{\delta}:\mathbb{R}^{n_{l}}\to\mathbb{R}$ for some parameter
$\delta\in(0,1)$, such that

$\rho_{\delta}(y)=\max_{q\in\mathbb{Q(\delta)}}\,q^{\top}h^{\star},$ (12)

where set $\mathbb{Q}(\delta)\subset\Delta_{N}$ is a closed and convex set
that satisfies the following assumption.

######  Assumption 2.

There exists $p\in\Delta_{N}$ and a closed, convex, and proper function
$g_{\delta}:\mathbb{R}^{N}\to\mathbb{R}\cup\\{\infty\\}$ such that
$g_{\delta}(p)<0$ and
$\mathbb{Q}(\delta)\coloneqq\left\\{q\in\mathbb{R}^{N}|g_{\delta}(q)\leq
0\right\\}\cap\Delta_{N}$. Furthermore, $g_{\delta_{1}}(q)>g_{\delta_{2}}(q)$
for all $q\in\Delta_{N}$ and $0<\delta_{1}<\delta_{2}<1$.

Function $g_{\delta}$ provides a _coherent risk measure_ of random variable
$\eta$. In particular, the representation theorem states that a coherent risk
measure of a random variable $\eta$—which is characterized by the
monotonicity, translational invariance, positive homogeneity, subadditivity
properties [19]—is equivalent to the maximum expectation of this variable over
a convex and closed set of probability distributions [19, Prop. 4.1]. Hence,
under Assumption 2, (12) implies that $g_{\delta}(y)$ is is a coherent risk
measure of $\eta$, where $\delta\in[0,1]$ is an uncertainty parameter: the
volume of set $\mathbb{Q}(\delta)$ increases as $\delta$ increases. Many
common risk measures satisfy Assumption 2. See Appendix for some examples.

Based on function (12), we propose to replace the stochastic constraint in (6)
with the following:

$\rho_{\delta}(y)\leq\epsilon.$ (13)

Under Assumption 1, if $\mathbb{Q}(\delta)=\\{p\\}$, then (13) implies that
the constraints in (6) only hold in expectation. On the other hand, if
$\mathbb{Q}(\delta)=\Delta_{N}$, then (10) holds for all $i\in[1,d]$. By
ranging $\delta$ within the interval $[0,1]$, the constraint in (13) ensures
different tradeoffs between a risk-neutral and a risk-averse variation of the
stochastic constraints in (6).

By replacing the constraints in (6) with its risk-aware variation in (12), we
obtain a risk-aware variation of the routing problem in (7), given as follows:

$\begin{array}[]{ll}\underset{x,y,z}{\mbox{maximize}}&\sum_{k=1}^{n_{c}}\psi_{k}(x_{k})\\\
\mbox{subject to}&Ey=0_{n_{n}},\,x=Hz,\,Fz\leq y,\\\
&\rho_{\delta}(y)\leq\epsilon,\,y\geq 0_{n_{l}},\,z\geq 0_{n_{r}}.\end{array}$
(14)

###  III-B Simplification of risk-aware constraints

Optimization (14) seems challenging to solve: it contains an outer layer
optimization over the network flow variables and an inner layer optimization
that comes from the definition of the coherent risk measure in (12). In the
following, we show that this nested two-layer optimization is equivalent to a
single-level convex optimization using duality theory. To this end, we make
the following assumption on set $\mathbb{Q}$ in (12).

Assumption 2 states that set $\mathbb{Q}$ is the intersection of the sublevel
set of a convex function and the probability simplex. Many popular risk
measures—such as the conditional value-at-risk, entropic value-at-risk, and
total variation distance—satisfy this assumption. See the Appendix for the
detailed formula of some popular risk measures.

Based on Assumption 2, the value of the coherent risk measure in (12) is the
optimal value of not only the maximization problem in (12), but also its dual
problem, as shown by the following proposition.

######  Proposition 1.

Suppose that Assumption 1 and Assumption 2 hold. Given $\delta\in(0,1)$ and
$y\in\mathbb{R}^{n_{l}}_{\geq 0}$, the value of $\rho_{\delta}(y)$ equals the
optimal value of the following optimization problem

$\begin{array}[]{ll}\underset{w,\lambda,\nu,h}{\mbox{minimize}}&\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)-\nu\\\ \mbox{subject
to}&Ky\leq(1+h_{i})c^{i},\,y\leq(1+h_{i})d^{i},\,h\geq 0_{N},\\\ &w-\nu
1_{N}\geq h,\,\lambda\geq 0,\,i\in[1,N],\end{array}$ (15)

where $g_{\delta}^{*}:\mathbb{R}^{N}\to\mathbb{R}\cup\\{\infty\\}$ is the
convex conjugate function of $g_{\delta}$, i.e.,
$g_{\delta}^{*}(w)\coloneqq\sup_{q}\,q^{\top}w-g_{\delta}(w)$ for all
$w\in\mathbb{R}^{N}$. Furthermore, we define $0\cdot
g_{\delta}^{*}(\frac{1}{0}w)\coloneqq\infty$ for all $w\in\mathbb{R}^{N}$.

###### Proof.

We first show that the dual problem of the optimization in (12) is as follows:

$\begin{array}[]{ll}\underset{\lambda,\nu,w}{\mbox{minmize}}&\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)-\nu\\\ \mbox{subject to}&w-\nu 1_{N}\geq
h^{\star},\,\lambda\geq 0.\end{array}$ (16)

Notice that we implicitly assume that $\lambda>0$ in (16). The Lagrangian of
optimiztaion (16) is given by $L(w,\lambda,\nu,q,\sigma)=\textstyle\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)+q^{\top}(h^{\star}+\nu
1_{N}-w)-\sigma\lambda-\nu.$. The dual problem of optimization (16) is as
follows:

$\begin{array}[]{ll}\underset{q,\sigma}{\mbox{maxmize}}&\underset{w,\lambda,\nu}{\mbox{min}}\,L(w,\lambda,\nu,q,\sigma)\\\
\mbox{subject to}&q\geq 0_{N},\,\sigma\geq 0.\end{array}$ (17)

For any $\lambda>0$, we can show that

$\textstyle\underset{w}{\mbox{min}}\,\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)-q^{\top}w=\textstyle-\underset{u}{\mbox{max}}\,\lambda
q^{\top}u-\lambda g_{\delta}^{*}(u)=-\lambda g_{\delta}(q),$ (18)

where the last step is due to the fact that $(g_{\delta}^{*})^{*}=g_{\delta}$
when $g_{\delta}$ under Assumption 2 [20, Thm.12.2]. By using (18) we can show
the following:

$\displaystyle\underset{\lambda,\nu,w}{\mbox{min}}\,L(w,\lambda,\nu,q,\sigma)$
(19) $\displaystyle=\underset{\lambda,\nu}{\mbox{min}}\,-\lambda
g_{\delta}(q)+q^{\top}(h^{\star}+\nu 1_{N})-\sigma\lambda-\nu$
$\displaystyle=\begin{cases}q^{\top}h^{\star},&\text{if
}g_{\delta}(q)=-\sigma,\,q^{\top}1_{N}=1,\\\
-\infty,&\text{otherwise.}\end{cases}$

Substituting (19) into (17) gives

$\begin{array}[]{ll}\underset{q}{\mbox{maxmize}}&\textstyle
q^{\top}h^{\star}\\\ \mbox{subject to}&q^{\top}1_{N}=1,\,q\geq 0,\,g(q)\leq
0.\end{array}$ (20)

Notice that, under Assumption 2, optimization (20) is exactly the optimization
in (12). Since Assumption 1 and Assumption 2 together imply that optimization
(20) is strictly feasible if $q=p$, we conclude that optimization (16) and
optimization (20) have the same optimal value.

Finally, suppose that $(w,\lambda,\nu)$ satisfies the constraints in
optimization (16). Since $h^{\star}$ satisfies the constraints in (11) for all
$i\in[1,N]$, $(w,\lambda,\nu,h^{\star})$ satisfies the constraints in
optimization (15). Next, suppose that $(w,\lambda,\nu,h)$ is optimal for
optimization (15). Since $h_{i}^{\star}$ is the optimal value of optimization
(11) for all $i\in[1,N]$, we necessarily have

$w-\nu 1_{N}\geq h\geq h^{\star}.$

Hence $(w,\lambda,\nu)$ satisfies the constraints of optimization (16).
Therefore there exists $h\in\mathbb{R}^{n}$ such that $(w,\lambda,\nu,h)$
satisfies the constraints in optimization (16) if and only if
$(w,\lambda,\nu)$ satisfies the constraints in optimization (15). Since
optimization (15) and optimization (16) have the same objective function, we
conclude that the optimal values of the two optimization problems are the
same. ∎

Proposition 1 shows that any upper bound on the coherent risk measure in (12)
is an upper bound on the optimal value of a convex minimization problem. Based
on this observation, the following proposition shows that one can merge said
minimization together with the outer-layer maximization in (14) by introducing
additional variables and constraints.

######  Proposition 2.

Suppose that Assumption 1 holds. Optimization (14) is equivalent to the
following optimization problem

$\begin{array}[]{ll}\underset{x,y,z,w,\lambda,\nu,h}{\mbox{maximize}}&\sum_{k=1}^{n_{c}}\psi_{k}(x_{k})\\\
\mbox{subject to}&Ey=0_{n_{n}},\,x=Hz,\,Fz\leq y,\\\
&Ky\leq(1+h_{i})c^{i},\,y\leq(1+h_{i})d^{i},\\\ &w-\nu 1_{N}\geq h,\,y\geq
0_{n_{l}},\,z\geq 0_{n_{r}},\,\,h\geq 0_{N},\\\ &\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)-\nu\leq\epsilon,\,\lambda\geq
0,\,i\in[1,N].\end{array}$ (21)

###### Proof.

If $(x,y,z,w,\nu,\lambda,h)$ satisfies the constraints in (21), then
$(w,\lambda,\nu,h)$ satisfies the constraints in (15). Furthermore,
Proposition (1) implies that

$\textstyle\epsilon\geq\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)-\nu\geq\rho_{\delta}[\zeta_{\mathbb{D}}(y)].$
(22)

Hence $(x,y,z)$ satisfies the constraints in (14). On the other hand, if
$(x,y,z)$ satisfies the constraints in (14), then Proposition 1 implies that
there exists $(w,\lambda,\nu,h)$ such that

$\textstyle\lambda
g_{\delta}^{*}(\frac{1}{\lambda}w)-\nu=\rho_{\delta}[\zeta_{\mathbb{D}}(y)]\leq\epsilon.$
(23)

In other words, $(x,y,z,w,\lambda,\nu,h)$ satisfies the constraints in (21).
Therefore, $(x,y,z)$ satisfies the constraints in (14) if and only if there
exists $w,\lambda,\nu,h$ such that $(x,y,z,w,\lambda,\nu,h)$ satisfies the
constraints in (21). Since optimization (14) and (21) have the same objective
function, we complete the proof. ∎

Proposition 2 shows that the risk-aware routing problem in (14) is equivalent
to the constrained convex optimization problem in (21). For come common risk
measures, the constraints in (21) are either linear or exponential cone
constraints. See Appendix for details.

##  IV Numerical Experiments

We demonstrate the proposed routing algorithm using a case study based on a
UAM network in the city of Austin, illuatrated by Fig. 1a. This network serves
the demands of $n_{c}=46$ communities, each corresponding to a zip code area
in the city of Austin. It contains $n_{n}=17$ nodes, each corresponding to a
vertiport; $n_{l}=72$ links, each corresponding to a flight corridor; and
$n_{r}=200$ candidate routes, each containing at most five connected flight
corridors. We choose the locations of the nodes to be city centers or
subcenters that are geographically and societally reconfigurable into
vertiports. To simplify air traffic management in UAM, we deploy the links
such that there are no intersections between different links. We select the
200 routes based on the public transportation plans and the function of
different communities. We choose the capacities of the vertiports and flight
corridors based on utilization forecast and safety and noise considerations.
We also consider a uniform capacity reduction of $20\%$ and $40\%$ for all
vertiports and flight corridors, which occurs with probability $0.3$ and
$0.2$, respectively.

We aim to route the network flow of vehicles in the Austin network to fairly
serve the demands of all 46 communities subject to constraints on the coherent
risk measures of the stochastic link and node capacity violation. We
illustrate the routing results obtained by solving optimization (21) using the
Frank-Wolfe method [21] (terminated after 100 iterations) in Fig. 1 and Fig.
2. We compare them with the results of maximizing the total community demand
served, which is obtained by solving optimization (21) with
$\psi_{k}(x_{k})=x_{k}$ for all $k\in[1,n_{c}]$. These results show that
optimizing the alpha-utility function promotes even distribution of the
demands served for different communities.

(a) Austin network

(b) Maximizing the total demand served

(c) Ensuring alpha-fairness

Figure 1: The Austin network (left), and the average number of flights per
hour for different links and communities when maximizing the total community
demand served (middle) and ensuring alpha-fairness (right) subject to capacity
constraints based on the conditional value-at-risk.

$0.1$$0.5$$0.9$$100$$300$$500$$\delta$ (a) Conditional value-at-risk

$0.1$$0.5$$0.9$$100$$300$$500$$\delta$ (b) Total-variation distance

Figure 2: The average number of flights per hour assigned to different
communities subject to capacity constraints based on different risk measures
and different values of parameter $\delta$. The red and blue markers show the
results when maximizing the total demand served and ensuring alpha-fairness,
respectively.

##  V Conclusion

We develop a routing algorithm to fairly serve the demands of multiple
communities in UAM subject to risk-aware constraints. We ensure the fairness
of the demands served for different communities by maximizing the sum of
alpha-utility functions, and the robust satisfaction of stochastic link and
node capacity constraints via bounding the coherent risk measures of capacity
violation. We demonstrate our results using a UAM network based on the city of
Austin.

However, our current results still have several limitations. For example, the
proposed algorithm does not consider dynamic changes in link and node capacity
to time-dependent noise regulations. For future work, we plan to extend our
results to dynamic routing as well as simultaneous network design and traffic
routing in UAM.

## Appendix: Function Common risk measures

We provide some common examples of formulas of the function $g_{\delta}$ in
Assumption 2 for some common coherent risk measures, along with its convex
conjugate function, which appears in optimization (21).

###  V-A Conditional value-at-risk

For conditional value-at-risk, the function $g$ in Assumption 2 takes the
following form:

$g_{\delta}(q)\coloneqq\left\lVert\mathop{\rm
diag}(p)^{-1}q\right\rVert_{\infty}-1/(1-\delta)$ (24)

We can show, for any $r\in\mathbb{R}^{N}$, that

$\displaystyle g_{\delta}^{*}(r)$
$\displaystyle=1/(1-\delta)+\sup_{q}\,r^{\top}q-\left\lVert\mathop{\rm
diag}(p)^{-1}q\right\rVert_{\infty}$ (25)
$\displaystyle=1/(1-\delta)+\sup_{u}\,r^{\top}\mathop{\rm
diag}(p)u-\left\lVert u\right\rVert_{\infty}$
$\displaystyle=\begin{cases}1/(1-\delta),&\text{if }\left\lVert\mathop{\rm
diag}(p)r\right\rVert_{1}\leq 1,\\\ \infty,&\text{otherwise.}\end{cases}$

###  V-B Entropic value-at-risk

For entropic value-at-risk, the function $g$ in Assumption 2 takes the
following form:

$g_{\delta}(q)\coloneqq\begin{cases}\sum_{i=1}^{N}q_{i}\ln(q_{i}/p_{i})+\ln(1-\delta),&\text{if
}q\in\Delta_{N},\\\ \infty,&\text{otherwise.}\end{cases}$ (26)

Given $r\in\mathbb{R}^{N}$, we have

$\textstyle
g_{\delta}^{*}(r)=-\ln(1-\delta)+\sup_{q\in\Delta_{N}}\,r^{\top}q-\sum_{i=1}^{N}q_{i}\ln(q_{i}/p_{i})$
(27)

Using the KKT conditions, we can show that the supreme in (27) is attained if
there exists $\beta\in\mathbb{R}$ such that $0=r_{i}-\ln(q_{i}/p_{i})-\beta-1$
for all $i\in[N]$ and $1=q^{\top}1_{N},$. Substituting these conditions into
(27) shows that

$g_{\delta}^{*}(r)=-\ln(1-\delta)+\ln(p^{\top}\exp(r))$ (28)

where $\exp(r)$ is the elementwise exponential of $r$. In this case, one can
show that $g_{\delta}^{*}(r)$ is the optimal value of an exponential cone
program. See [22, Sec. 4.1.2] for a related discussion.

###  V-C Total variation distance

For the total variance distance [23], the function $g$ in Assumption 2 takes
the following form:

$g_{\delta}(q)\coloneqq\left\lVert q-p\right\rVert_{1}-2\delta.$ (29)

Given $r\in\mathbb{R}^{N}$, we can show that

$\displaystyle g_{\delta}^{*}(r)$
$\displaystyle=2\delta+r^{\top}p+\sup_{q}\,r^{\top}(q-p)-\left\lVert
q-p\right\rVert_{1}$ (30)
$\displaystyle=\begin{cases}2\delta+r^{\top}p,&\text{if }\left\lVert
r\right\rVert_{\infty}\leq 1,\\\ \infty,&\text{otherwise.}\end{cases}$

## References

  * [1] A. P. Cohen, S. A. Shaheen, and E. M. Farrar, “Urban air mobility: History, ecosystem, market potential, and challenges,” _IEEE Trans. Intell. Transp. Syst._ , vol. 22, no. 9, pp. 6074–6087, 2021.
  * [2] T. Biehle, “Social sustainable urban air mobility in Europe,” _Sustainability_ , vol. 14, no. 15, p. 9312, 2022.
  * [3] Y. Yu, M. Wang, M. Mesbahi, and U. Topcu, “Vertiport selection in hybrid air-ground transportation networks via mathematical programs with equilibrium constraints,” _IEEE Trans. Control Netw. Syst._ , pp. 1–12, 2023.
  * [4] Z. Gao, A. Porcayo, and J.-P. Clarke, “Developing virtual acoustic terrain for urban air mobility trajectory planning,” _Transp. Res. D: Transport Environ._ , vol. 120, p. 103794, 2023.
  * [5] Q. Wei, Z. Gao, J.-P. Clarke, and U. Topcu, “Risk-aware urban air mobility network design with overflow redundancy,” _arXiv preprint arXiv:2306.05581_ , 2023.
  * [6] P. Wu, J. Xie, Y. Liu, and J. Chen, “Risk-bounded and fairness-aware path planning for urban air mobility operations under uncertainty,” _Aerosp. Sci. Technol._ , vol. 127, p. 107738, 2022.
  * [7] M. Pelegrín, C. d’Ambrosio, R. Delmas, and Y. Hamadi, “Urban air mobility: From complex tactical conflict resolution to network design and fairness insights,” _Optim. Methods Software_ , pp. 1–33, 2023.
  * [8] T. Vossen, M. Ball, R. Hoffman, and M. Wambsganss, “A general approach to equity in traffic flow management and its application to mitigating exemption bias in ground delay programs,” _Air Traffic Control Quart._ , vol. 11, no. 4, pp. 277–292, 2003.
  * [9] M. O. Ball, R. Hoffman, and A. Mukherjee, “Ground delay program planning under uncertainty based on the ration-by-distance principle,” _Transp. Sci._ , vol. 44, no. 1, pp. 1–14, 2010.
  * [10] C. Barnhart, D. Bertsimas, C. Caramanis, and D. Fearing, “Equitable and efficient coordination in traffic flow management,” _Transp. Sci._ , vol. 46, no. 2, pp. 262–280, 2012.
  * [11] D. Bertsimas and S. Gupta, “Fairness and collaboration in network air traffic flow management: an optimization approach,” _Transp. Sci._ , vol. 50, no. 1, pp. 57–76, 2016.
  * [12] C. Chin, K. Gopalakrishnan, M. Egorov, A. Evans, and H. Balakrishnan, “Efficiency and fairness in unmanned air traffic flow management,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 9, pp. 5939–5951, 2021.
  * [13] J. Fairbrother, K. G. Zografos, and K. D. Glazebrook, “A slot-scheduling mechanism at congested airports that incorporates efficiency, fairness, and airline preferences,” _Transp. Sci_ , vol. 54, no. 1, pp. 115–138, 2020\.
  * [14] K. G. Zografos and Y. Jiang, “A bi-objective efficiency-fairness model for scheduling slots at congested airports,” _Transp. Res. C: Emerging Technol._ , vol. 102, pp. 336–350, 2019.
  * [15] A. Jacquillat and V. Vaze, “Interairline equity in airport scheduling interventions,” _Transp. Sci._ , vol. 52, no. 4, pp. 941–964, 2018.
  * [16] L. Sun, P. Wei, and W. Xie, “Fair and risk-averse urban air mobility resource allocation under uncertainties,” _Available at SSRN 4343979_ , 2023.
  * [17] S. Shakkottai, R. Srikant, _et al._ , “Network optimization and control,” _Found. Trends® in Netw._ , vol. 2, no. 3, pp. 271–379, 2008\.
  * [18] V. Xinying Chen and J. Hooker, “A guide to formulating fairness in an optimization model,” _Ann. Oper. Res._ , pp. 1–39, 2023.
  * [19] P. Artzner, F. Delbaen, J.-M. Eber, and D. Heath, “Coherent measures of risk,” _Math. Finance_ , vol. 9, no. 3, pp. 203–228, 1999.
  * [20] R. T. Rockafellar, _Convex analysis_. Princeton University Press, 2015.
  * [21] M. Jaggi, “Revisiting frank-wolfe: Projection-free sparse convex optimization,” in _Proc. Int. Conf. Mach. Learn._ PMLR, 2013, pp. 427–435.
  * [22] A. Dixit, M. Ahmadi, and J. W. Burdick, “Risk-averse receding horizon motion planning,” _arXiv preprint arXiv:2204.09596 [eess.SY]_ , 2022.
  * [23] ——, “Distributionally robust model predictive control with total variation distance,” _IEEE Control Syst. Lett._ , vol. 6, pp. 3325–3330, 2022.


11institutetext: Process and Data Science Chair, RWTH Aachen University,
Aachen, Germany 22institutetext: Fraunhofer FIT, Sankt Augustin, Germany
22email<EMAIL_ADDRESS>
# PM4Py.LLM: a Comprehensive Module for Implementing PM on LLMs

Alessandro Berti 1122 0000-0002-3279-4795

###### Abstract

_pm4py_ is a process mining library for Python implementing several process
mining (PM) artifacts and algorithms. It also offers methods to integrate PM
with large language models (LLMs). This paper examines how the current
paradigms of PM on LLM are implemented in _pm4py_ , identifying challenges
such as privacy, hallucinations, and the context window limit.

###### Keywords:

pm4py Python Large Language Models Large Vision Language Models

##  1 Introduction

Process mining (PM) is a branch of data science aiming to extract process-
related insights from the event data recorded by information systems
supporting the execution of such processes. Both open-source (ProM) and
commercial (Fluxicon Disco, Celonis, SAP Signavio) tools are available for PM.
Among open-source offerings, the _pm4py_ process mining library for Python [3]
is a popular option implementing various process mining techniques, including
process discovery, conformance checking, and model enhancement. _pm4py_ ,
being a library, implements several PM artifacts, including event log
structures, process models (process trees, Petri nets, BPMN models), and
machine learning features. Large Language Models (LLMs) and Large Vision
Language Models (LVLMs) have been recently implemented for PM tasks in
different implementation paradigms [1]. The goal of this paper is to present
how _pm4py_ , allowing for the implementation of different paradigms,
integrates with large language models. In [2], some textual abstractions of
event logs and process models provided by _pm4py_ are described. However, many
more techniques (visual abstractions, APIs for code generation) are currently
provided in the library, that are introduced in this paper and are important
to extend the scope of PM on LLMs. The rest of the paper is organized as
follows. Section 2 describes the current paradigms for PM on LLMs; Section 3
describes the implementation of the paradigms in _pm4py_ ; Section 4 concludes
the paper with an outlook over possible development directions.

##  2 Paradigms for PM on LLMs

The following paradigms have been adopted for PM on LLMs [1]:

  * •

_Direct Provision of Insights_ : A prompt containing abstractions of PM
artifacts, domain knowledge, and questions is provided to the LLM/LVLM.
Different techniques are available for the abstraction of PM artifacts:

    * –

_Textual Abstractions of Process Mining Artifacts_ : The PM artifact is
provided as text [2].

    * –

_Visual Abstractions of Process Mining Artifacts_ : The PM artifact is
provided as a visual representation, which can be interpreted by the LVLM.

Typical questions that are possible using this paradigm are: “What are the
anomalies in the event data?”, “Can you explain the process?”. The main
limitation is the context window limit of the LLM/LVLM. Moreover, the proposed
implementation paradigm might suffer from privacy (data needs to be provided
to the LLM) and _hallucinations_ by the LLM/LVLM [8]. In _pm4py_ , the
textual/visual abstractions can be provided along with a question to an LLM.
In particular, $\mathtt{pm4py.llm.openai\\_query}$ is implemented, which
allows querying OpenAI’s LLMs/LVLMs (such as _gpt-4-turbo-preview_ and
_gpt-4-vision-preview_).

  * •

_Translation of Natural Language Statements to SQL Queries_ : Alternatively,
the LLM can generate SQL queries executable on the process mining dataset [4].
This mitigates the privacy and hallucination issues. However, the user needs
to provide a clear question and all the required domain knowledge on the
dataset and on the process [4]. Typical questions that are possible using this
paradigm are: “How many cases are contained in this event log?”, “Can you
measure the average throughput time of the cases containing the activity X?”.

  * •

_Code Generation_ : Using the LLM to generate scripts executable against the
process mining dataset is a paradigm applied successfully in process modeling
[5]. It requires the detailed specification of the APIs to be used. Typical
statements that are possible using this paradigm are: “Discover a process
model from the data”, “Extract an event log from my Outlook calendar”.

  * •

_Automatic Formulation of Hypotheses_ : This paradigm provides textual
abstractions of the process mining artifacts in order for the LLM to generate
hypotheses over the artifact [2]. A SQL query is also provided to verify the
validity of such hypotheses. Refinement cycles can be realized when the
original hypotheses are not valid, leading to refined hypotheses.

The provision of the original process mining artifact is usually not a viable
option due to the context window limit, as real-life event logs and process
models have millions of events and hundreds of activities.

##  3 Implementations

Command | Description
---|---
pm4py.llm.abstract_dfg | Provides the DFG abstraction of a traditional event log.
pm4py.llm.abstract_variants | Provides the variants abstraction of a traditional event log.
pm4py.llm.abstract_log_attributes | Provides the abstraction of the attributes/columns of the event log.
pm4py.llm.abstract_log_features | Provides the abstraction of the machine learning features obtained from an event log.
pm4py.llm.abstract_case | Provides the abstraction of a case (collection of events).
pm4py.llm.abstract_ocel | Provides the abstraction of an object-centric event log (list of events and objects).
pm4py.llm.abstract_ocel_ocdfg | Provides the abstraction of an object-centric event log (OC-DFG).
pm4py.llm.abstract_ocel_features | Provides the abstraction of an object-centric event log (features for ML).
pm4py.llm.abstract_event_stream | Provides an abstraction of the (last) events of the stream related to a traditional event log.
pm4py.llm.abstract_temporal_profile | Provides the abstraction of a temporal profile model.
pm4py.llm.abstract_petri_net | Provides the abstraction of a Petri net.
pm4py.llm.abstract_declare | Provides the abstraction of a DECLARE model.
pm4py.llm.abstract_log_skeleton | Provides the abstraction of a log skeleton model.

Table 1: Textual abstractions of PM artifacts provided by _pm4py_.

In this section, the implementation in _pm4py_ of the different paradigms
described in Section 2 is discussed.

###  3.1 Textual Abstractions of Process Mining Artifacts

Textual abstractions of PM artifacts can be provided (up to the context window
limit) to any LLM. The possible abstractions are described in Table 1. For
traditional event logs, the top entries of the directly-follows graph (couples
of activities following each other in at least a case of the log) or the top
process variants can be computed. Moreover, it is possible to extract a
summary of the numerical machine learning features extracted from the event
log (each feature is provided with different quantiles). For object-centric
event logs, the top entries of the object-centric directly-follows graph can
be extracted. As for traditional event logs, it is possible to extract a
summary of the machine learning features extracted from the object-centric
event log. It is also possible to abstract the entire list of events and
objects of the object-centric event log. However, the resulting textual
abstraction would probably exceed the context window limit of the LLM if not
limited to a subset of events/objects. The methods support the specification
of the context window limit. The abstractions usually provide, at first, the
most important entry and continue to include entries until the specified
length limit is exceeded.

Petri nets can be textually abstracted as their set of places/transitions/arcs
[2]. Declarative process models, such as DECLARE [7] and the log skeleton [9],
can also be textually abstracted. The exact specification of the artifact can
vary. However, since LLMs might not have the knowledge of a specific
declarative notation, the description of the rules of the notation should also
be included in the textual abstraction. In contrast to event log abstractions,
it is more difficult to enforce the context window limit because of missing
criteria to rank the importance of the elements of the process model. Textual
abstractions of large Petri nets or declarative models with many rules can be
provided only to LLMs with a large context window.

Command | Description
---|---
pm4py.vis.save_vis_petri_net | Saves the visualization of a Petri net model.
pm4py.vis.save_vis_dfg | Saves the visualization of a directly-follows graph annotated with the frequency.
pm4py.vis.save_vis_performance_dfg | Saves the visualization of a directly-follows graph annotated with the performance.
pm4py.vis.save_vis_process_tree | Saves the visualization of a process tree.
pm4py.vis.save_vis_bpmn | Saves the visualization of a BPMN model.
pm4py.vis.save_vis_heuristics_net | Saves the visualization of an heuristics net.
pm4py.vis.save_vis_dotted_chart | Saves the visualization of a dotted chart.
pm4py.vis.save_vis_sna | Saves the visualization of the results of a social network analysis.
pm4py.vis.save_vis_case_duration_graph | Saves the visualization of the case duration graph.
pm4py.vis.save_vis_events_per_time_graph | Saves the visualization of the events per time graph.
pm4py.vis.save_vis_performance_spectrum | Saves the visualization of the performance spectrum.
pm4py.vis.save_vis_events_distribution_graph | Saves the visualization of the events distribution graph.
pm4py.vis.save_vis_ocdfg | Saves the visualization of an object-centric directly-follows graph.
pm4py.vis.save_vis_ocpn | Saves the visualization of an object-centric Petri net.
pm4py.vis.save_vis_object_graph | Saves the visualization of an object-based graph.
pm4py.vis.save_vis_network_analysis | Saves the visualization of the results of a network analysis.
pm4py.vis.save_vis_transition_system | Saves the visualization of the results of a transition system.
pm4py.vis.save_vis_prefix_tree | Saves the visualization of a prefix tree.
pm4py.vis.save_vis_alignments | Saves the visualization of the alignments table.
pm4py.vis.save_vis_footprints | Saves the visualization of the footprints table.
pm4py.vis.save_vis_powl | Saves the visualization of a POWL model.

Table 2: Visualization methods provided by _pm4py_.

###  3.2 Visual Abstractions of Process Mining Artifacts

Visual process representations can also be a source of knowledge for PM on
LVLMs. The method

$\mathtt{pm4py.llm.explain\\_visualization(vis\\_saver,*args,connector,**kwargs)}$

can be used to provide a visualization to an LVMs, in which
$\mathtt{vis\\_saver}$ is one of the visualizations described in Table 2,
$\mathtt{*args}$ (positional arguments) and $\mathtt{**kwargs}$ (keyword
arguments) are the arguments provided to the visualization method, and
$\mathtt{connector}$ is the LVM that should be used. For instance,
$\mathtt{pm4py.llm.openai\\_query}$ can be used to query the _gpt-4-vision-
preview_ model. Several visualizations offer insights that are more immediate
in comparison to the textual abstractions, for instance:

  * •

Dotted charts show events and detect patterns like batching and concept
drifts.

  * •

Performance spectrum visualizes activity flows over time, offering performance
insights.

  * •

Case duration and events per time graphs help understand throughput and
identify concept drifts.

  * •

Petri nets, BPMN, directly-follows graphs, and social network analysis benefit
from visual layout for pattern detection.

It is important to acknowledge that prompts to LVLMs require more
computationally intensive operations than textual prompts to LLMs. Moreover,
LVLMs are not specialized in patterns that might be important for process
mining, as highlighted in [1]. Moreover, LVLMs may miss domain knowledge
needed to interpret such visualizations (for instance, additional explanation
may be required in the prompt to detect some patterns on the dotted charts).

###  3.3 SQL Queries against _pm4py_ Event Logs

Statements in natural language can be translated by LLMs in the most important
SQL dialects [6]. The data structure used for traditional event logs in
_pm4py_ is the Pandas dataframe, which is a columnar data structure easily
imported/exported from/to CSV and Parquet files. Pandas dataframes can be
queried in-memory using, for instance, the DuckDB SQL dialect. The LLM needs
to be provided with the attributes of the Pandas dataframe and their
specification (case ID, activity, timestamp). Moreover, if the target LLM’s
knowledge of DuckDB is not proficient, additional knowledge related to the
database operators and process mining need to be provided. The SQL query can
be executed using duckdb.sql(sqlquery).to_df(), which returns a Pandas
dataframe containing the answer to the question of the user. It is important
to note that only quantitative statements can be translated to SQL queries
using this paradigm. Also, the object-centric data structure in _pm4py_ is a
collection of Pandas dataframes (there are dataframes for the events, objects,
and event-to-object relationships). Therefore, SQL queries can be orchestrated
against any combination of the dataframes part of the object-centric data
structure, enabling LLM-based querying of object-centric event logs111A
textual description of the object-centric data structure in _pm4py_ is
available at https://github.com/fit-alessandro-berti/pm-manuals-for-
llms/blob/main/pm4py_manual.txt.

###  3.4 Generating _pm4py_ Code with LLMs

_pm4py_ comes with a rich documentation covering its features222The
documentation is available at the URL
https://pm4py.fit.fraunhofer.de/static/assets/api/2.7.11/index.html. Using
_RAG_ or _fine-tuning_ , an LLM can be trained over the API of the library333A
textual file collecting the APIs is available at the address
https://github.com/fit-alessandro-berti/pm-manuals-for-
llms/blob/main/pm4py_manual.txt., becoming able to translate user statements
in executable Python code. This paradigm allows not only to query the event
data but also to apply the algorithms provided by _pm4py_ and from any
scientific Python library in general. However, it might pose a security risk
as code generated by the LLM could contain malicious instructions [10]. An
example of LLM trained to generate _pm4py_ code is provided in the OpenAI’s
GPT store444https://chat.openai.com/g/g-EjtLrVyWH-pm4py-assistant.

###  3.5 Automatic Formulation of Hypotheses

Combining the paradigms described in Section 3.1 and 3.3, it is possible to
generate some hypotheses over the process mining artifacts, in particular
concerning event data. Usually, some information about the activities (for
example, the textual abstraction of the directly-follows graph) and the
attributes of the event log are provided along with a question to generate
hypotheses. The request can generically target any hypothesis over the event
data or hypotheses over a specific domain.

An example script is provided for hypothesis
generation555https://github.com/pm4py/pm4py-
core/blob/release/examples/llm/04_hypothesis_generation.py. Each hypothesis
comes with a description/explanation and an executable (DuckDB) SQL statement.
After executing the statement, the result could be validated from the LLM. If
the hypothesis proves valid, then the process stops. Otherwise, refined
hypotheses may be provided by the LLM. The automatic formulation of hypotheses
also suffers from LLM hallucinations [8] and, in a minor way, privacy issues
due to the provision of some textual abstractions in the prompt requesting the
generation of hypotheses.

##  4 Conclusion

The _pm4py_ process mining library offers a rich integration of PM with LLM,
implementing all the paradigms described in Section 2. Potential development
directions, dependent on the future capabilities of LLMs/LVLMs include the
extraction of event logs from videos, the generation of visual explanations
for a business process, and autonomous process discovery/conformance checking
from the event data.

## References

  * [1] Berti, A., Kourani, H., Hafke, H., Yun-Li, C., Schuster, D.: Evaluating Large Language Models in Process Mining: Capabilities, Benchmarks, Evaluation Strategies, and Future Challenges. In: Proceedings of the BPM-DS 2024 Working Conference (TBP). Springer (2024), https://doi.org/10.48550/arXiv.2403.06749
  * [2] Berti, A., Schuster, D., van der Aalst, W.M.P.: Abstractions, scenarios, and prompt definitions for process mining with llms: A case study. In: Business Process Management Workshops - BPM 2023 International Workshops. Lecture Notes in Business Information Processing, vol. 492, pp. 427–439. Springer (2023)
  * [3] Berti, A., van Zelst, S.J., Schuster, D.: Pm4py: A process mining library for python. Softw. Impacts 17, 100556 (2023)
  * [4] Jessen, U., Sroka, M., Fahland, D.: Chit-chat or deep talk: Prompt engineering for process mining. CoRR abs/2307.09909 (2023), https://doi.org/10.48550/arXiv.2307.09909
  * [5] Kourani, H., Berti, A., Schuster, D.: Process Modeling With Large Language Models. In: Proceedings of the EMMSAD 2024 Working Conference (TBP). Springer (2024), https://doi.org/10.48550/arXiv.2403.06749
  * [6] Li, J., Hui, B., et al., G.Q.: Can LLM already serve as A database interface? A big bench for large-scale database grounded text-to-sqls. In: NeurIPS 2023 (2023)
  * [7] Maggi, F.M.: Declarative process mining with the declare component of prom. In: Proceedings of the BPM Demo sessions 2013. CEUR Workshop Proceedings, vol. 1021. CEUR-WS.org (2013)
  * [8] Martino, A., Iannelli, M., Truong, C.: Knowledge injection to counter large language model (LLM) hallucination. In: ESWC 2023 Satellite Events. Lecture Notes in Computer Science, vol. 13998, pp. 182–185. Springer (2023)
  * [9] Verbeek, H.M.W.: The log skeleton visualizer in prom 6.9. Int. J. Softw. Tools Technol. Transf. 24(4), 549–561 (2022)
  * [10] Yao, Y., Duan, J., et al., K.X.: A survey on large language model (LLM) security and privacy: The good, the bad, and the ugly. CoRR abs/2312.02003 (2023), https://doi.org/10.48550/arXiv.2312.02003


# Parsing Table Structures in the Wild

Rujiao Long111Equal Contribution.$~{}^{3}$, Wen Wang111Equal
Contribution.$~{}^{1,2}$, Nan Xue1 Feiyu Gao3,
Zhibo Yang3, Yongpan Wang3, Gui-Song Xia222Correspondence Author.$~{}^{1,2}$
1 School of Computer Science, Wuhan University, Wuhan, China
2 LIESMARS, Wuhan University, Wuhan, China
3 Alibaba-Group, Hangzhou, China
github https://github.com/wangwen-whu/WTW-Dataset

###### Abstract

This paper tackles the problem of table structure parsing (TSP) from images in
the wild. In contrast to existing studies that mainly focus on parsing well-
aligned tabular images with simple layouts from scanned PDF documents, we aim
to establish a practical table structure parsing system for real-world
scenarios where tabular input images are taken or scanned with severe
deformation, bending or occlusions. For designing such a system, we propose an
approach named Cycle-CenterNet on the top of CenterNet with a novel cycle-
pairing module to simultaneously detect and group tabular cells into
structured tables. In the cycle-pairing module, a new pairing loss function is
proposed for the network training. Alongside with our Cycle-CenterNet, we also
present a large-scale dataset, named Wired Table in the Wild (WTW), which
includes well-annotated structure parsing of multiple style tables in several
scenes like photo, scanning files, web pages, _etc._. In experiments, we
demonstrate that our Cycle-CenterNet consistently achieves the best accuracy
of table structure parsing on the new WTW dataset by 24.6% absolute
improvement evaluated by the TEDS metric. A more comprehensive experimental
analysis also validates the advantages of our proposed methods for the TSP
task.

##  1 Introduction

Tables are commonly used in our daily life to record and summarize important
data for quick and better visualization of information. With the increasing
popularity of smartphones and portable cameras, it is very common to share
information with photo of tables. Accordingly, it is highly demanded to
automatically extract and parse table structures from photos or images in the
wild.

Input |  |
---|---|---
TabSplit [19] |  |
Our Results |  |
| TSP in Document images | TSP in the wild

Figure 1: Visual comparison for the difference between the problem of table
structure parsing (TSP) in document images and the images taken in the wild.
We leverage the state-of-the-art approach for document images proposed in [19]
and our proposed Cycle-CenterNet for both input images to obtain the parsing
results.

Given an image, Table Structure Parsing (TSP) aims at extracting all the
tables, locating their cells, and obtaining the row-column information in the
image. Previously, this problem is studied as table structure recognition
focusing on document images. In such scenario, the tabular images are taken
with well imaging conditions and are often horizontally (or vertically)
aligned with clean background and clear table structures. Early pioneering
works, _e.g_. [7, 8, 20, 6], tackle the TSP problem in a bottom-up manner by
heuristically grouping detected cells based on low-level cues (_e.g_., lines,
boundaries and word regions). Recently, deep learning-based approaches are
presented to avoid the heuristic grouping scheme design and resort to
developing end-to-end models. However, limited by the training datasets [9,
17, 2, 24, 5] used for table structure parsing, they still addressed this
problem under the well-aligned assumption of tabular images.

For a more practical requirement of parsing table structures from images taken
by hand-held cameras in the wild, the existing state-of-the-art approaches
[13, 14, 11, 16, 9, 23] are prone to fail as the commonly-used assumption of
tabular images no longer holds. Specifically, the tabular images in the
widely-used datasets (_e.g_., ICDAR-2013 [5], Tablebank [9]) are usually with
clean background and clear table structures. Limited by this, existing TSP
approaches can only handle table structure parsing in a relative simple
scenario by grouping detected cells into tables [11, 16, 9, 23]. Moreover, few
research pays attention to the precision of cell boundary, which is important
in text recognition.

To tackle the TSP problem in the wild, we present a large-scale dataset in
this paper to address the data lacking issue. When we collecting the real-
scene tabular images, we found that the wired tables and wireless tables have
a very large difference. The wireless tables in natural images are very
challenging to be recognized as the lacking of reference for perceptual
grouping by human annotators. Therefore, we mainly focus on the challenging
wired tables for annotation. Our proposed dataset, the Wired Tables in the
Wild (WTW), contains 14,581 images with the annotated information of table id,
tabular cells and corresponding row/column information. Following the data
splitting strategy used in ICDAR 2019 [3], we split our WTW into _training_
/_testing_ subsets with 10,970 and 3611 data samples respectively.

As shown in Fig. 1, the images in the WTW dataset are very different from the
document images, which thus poses a new problem to the table structures
parsing task. For instance, the non-rigid image deformation and complicated
image background presented in natural images will challenge existing
approaches [14] for document images on detecting and grouping the tabular
cells.

With our proposed WTW dataset available, we address the problem of table
structure parsing in the wild by proposing a simple yet effective approach
Cycle-CenterNet. It simultaneously detects the vertices and center points of
tabular cells, and groups the cells into tables by learning the common
vertices. Specifically, we found that the center point and vertices of a cell
have a mutual-directed relationship that can be used to group the cells into
tables by using the common vertex that is located in the intersect of the
adjacent cells. Based on this, we propose a loss function named _pairing loss_
to end-to-end group the cells in training phase. Once the structures of tables
are obtained, we use a simple post-processing algorithm to retrieve the row
and column information for the parsed tables. In experiments, we evaluate the
proposed Cycle-CenterNet on WTW dataset. Compared with the strong baseline of
vanilla CenterNet, our approach largely improves the F1-score of physical
coordinate accuracy from $73.1\%$ to $78.3\%$, while improves the F1-score of
adjacent relationship estimation from $84.8\%$ to $92.4\%$. In the metric of
TEDS [24], the proposed Cycle-CenterNet also obtains an absolute improvement
by 24.6 points.

Our contributions are summarized as follows:

  * -

We build a large-scale dataset in wild complex scenes, which provides a
variety of new challenges for table structure parsing with several real image
distortions.

  * -

We present an approach Cycle-CenterNet by exploiting the cycle-pairing module
optimization with a novel pairing loss proposed, which enables us to precisely
group the discrete cells into the structured tables.

  * -

In the experiments, our method improves the performance of table structure
parsing on the WTW dataset by large margins. It also outperforms the state-of-
the-art methods on the ICDAR2019 dataset, and achieves competitive results on
the ICDAR2013 dataset.

##  2 Related Work

###  2.1 Existing Datasets

There are a number of datasets including UNLV [17], ICDAR-2013 [5], SciTSR
[2], PubTabNet [24] and TableBank [9] etc. that are available in table
structure parsing. Prior to the deep table structure parsing approaches
emerged, the dataset UNLV [17] and ICDAR-2013 [5] were designed for
benchmarking the table structure recognition systems with a limited number
(less than 1,000) of tabular images and annotations. To meet the requirement
of designing data-driven learning approaches for table structure parsing,
large-scale datasets of PubTabNet [24] and TableBank [9] are proposed, but the
incomplete annotations still hinder their development. Recently, FinTabNet
[23] and SciTSR [2] datasets add the cell coordinates and row-column
information to become the most complete and large-scale dataset for table
structure parsing task.

Although the scale of table image datasets has been dramatically improved,
these datasets are with a specific focus on the document images that are
obtained from the digital documents (_e.g_., PDF documents). For our purpose
of parsing table structures in the wild, those datasets cannot be used for
training a learning-based approach with an expected generalization ability.
Recently, a new dataset ICDAR2019 [3] introduce a more challenging task of
parsing table structures from the scanned archival documents instead of the
digital documents. However, it only contains 750 images for table structure
parsing, which will induce the same problem for training a data-driven table
structure parsing model. Besides, the ICDAR2019 [3] dataset is still focused
on the document images. In contrast to those existing datasets, we contribute
a new large-scale table dataset WTW that contains 14,581 complex wired tables
in multiple real scenes including photoing, scanning, and web pages. Different
from the existing datasets, the images in our proposed dataset usually contain
severe practical image distortions including bending, tilting, and occlusion,
_etc_.

###  2.2 Table Structure Recognition and Parsing

The problem of table structure parsing was previously studied as two sub-
problems of table detection and table structure recognition. Kieninger  _et
al_. [8] presented the first table structure recognition system that estimates
the table structures by clustering the detecting the text blocks from tabular
images in a heuristic way. Following this work, the rule-based heuristic
approaches were proposed [21, 18] to recognize or parse table structures from
the hand-crafted visual cues. Recently, the deep learning-based approaches
were proposed to automatically learn informative visual features [5, 2, 24,
12]. However, these methods mainly focuses on the well-conditioned document
images, where the tables [16, 23, 12, 9, 23, 14] are well-aligned to the image
axes. As this assumption does not hold on to more challenging tables, some
researches tried to get rid of the well-aligned assumption and modeled the
table structure parsing problem with graph convolution networks [2, 13, 24].
However, they are implicitly using the adjacent relationship between the
detected cells to construct an informative initial graph and then prune the
unexpected edges during training. Different from those approaches, our
proposed Cycle-CenterNet gets rid of using the assumptions mentioned above to
meet more practical requirements for table structure parsing in the wild.

##  3 The WTW Dataset

This section presents the detail of our proposed dataset, Wired Tables in the
Wild (WTW), which has a total of 14581 images in a wide range of real business
scenarios and the corresponding full annotation (including cell coordinates
and row/column information) of tables.

###  3.1 Image Collection and Annotation

The images in the WTW dataset are mainly collected from the natural images
that contain at least one table. As our purpose is to parsing table structures
without considering the image source, we additionally add the archival
document images and the printed document images. Statically, the portion of
images from natural scenes, archival, and printed document images are 50%,
30%, and 20%. After obtaining all the images, we statically found 7
challenging cases. As summarized in Tab. 1, our proposed WTW dataset covers
all challenging cases with a reasonable proportion of each case.

In our dataset, we annotate all the tables presented in each image for their
cell coordinates and the row/column information. For the images that have more
than one table, their instance information is also annotated. When annotating
the cell coordinate, we follow the benchmark of ICDAR2019 [3] to use the inner
table lines for localization. To ensure that there is no leakage of sensitive
information (names, telephone numbers, etc.), we erased them out.

#### Data splitting.

In order to ensure that the training data and test data distributions
approximately match, we randomly select approximately 75% of the original
images as the training set, and the rest data samples are used for testing and
evaluation. Finally, our WTW dataset has 10970 training samples and 3611
testing ones.

Table 1: A statistical summary and comparison between our WTW dataset and the
existing datasets for table structure parsing. Our proposed dataset covers all
the 7 challenging cases of (1) Inclined tables, (2) Curved tables, (3)
Occluded tables or blurred tables (short in _Occ. or Blur_ , (4) Extreme
aspect ratio tables (short in _Ex. AR_), (5) Overlaid tables, (6) Multi-color
tables and (7) Irregular tables in table structure recognition. In the last
row, we report the total number of samples for all those datasets.

Challenging Cases |  Tablebank [9] |  UNLV [17] |  Marmot [11] |  SciTSR [2] |  ICDAR-13 [5] |  ICDAR-19 [3] |  WTW (Ours)
---|---|---|---|---|---|---|---
Inclined | - | ✓ | - | - | - | ✓ | ✓
Curved | - | - | - | - | - | - | ✓
Occ. or Blur | - | - | - | - | - | ✓ | ✓
EX. AR | - | - | - | - | - | - | ✓
Overlaid | - | - | - | - | - | - | ✓
Multi Color | ✓ | - | - | - | ✓ | - | ✓
Irregular | ✓ | - | ✓ | - | - | ✓ | ✓
# Samples | 145,000 | 423 | 1,000 | 15,000 | 156 | 750 | 14,581

###  3.2 Baselines and Benchmark Evaluation

As our dataset contains a large number of tables that have deformations
(_e.g_., the inclined, curved, and irregular tables), the commonly-used
rectangular representation of tables cannot be generalized well to those
challenging cases in our dataset. As a result, it would be problematic to
directly leverage the state-of-the-art data-driven approaches designed for
documents in our dataset. Accordingly, we present a more appropriate way to
set up the baseline approaches and provide a comprehensive evaluation protocol
to benchmark the new approaches on the WTW dataset.

#### Baseline configuration.

Instead of modeling the table structures in natural images as large
rectangles, we first represent the tabular cells as small objects since the
small objects are more robust to the severe image deformation. Based on this,
we formulate the problem of table structure parsing in two steps: (1) using a
state-of-the-art object detector for cell detection, and then (2) grouping the
detected cells into tables by heuristically calculate the spatial proximity
between cells. After obtaining the table structures, a post-processing step is
applied to the row/column information***More detail and pseudo-codes for the
heuristic grouping scheme and the post-processing module are described in the
supplementary materials.. To make the baseline configuration more convincing,
we use four widely-used object detectors of Faster-RCNN [15], TridenNet [10],
Cascade-RCNN [1] and the anchor-free detector CenterNet [25] as the cell
detector in our baseline.

#### Evaluation protocol for table structure parsing.

A reasonable evaluation protocol is important for quantitatively compare
different approaches. We evaluate a given table structure parser in two
aspects of (1) _the correctness of physical structure_ and (2) _the
correctness of logical structure_ , described as follow:

  * -

_Precision, Recall and F-score for physical structure estimation._

We evaluate the accuracy of cell detection by calculating the precision,
recall, and F1-score for the parsing results with regard to the ground truth
in the testing split of the WTW dataset. Different from the general object
detection, the table structure parsing requires more accuracy of tabular cells
with low tolerance. Therefore, the detected cells whose IOU is below $0.9$ are
regarded as false positive detections.

  * -

_Precision, Recall, F-score and TEDS[24] for adjacent relationship
estimation._

For logical structure correctness, we follow the evaluation protocol used in
document images by calculating the precision, recall, and F-score for the cell
adjacency [4] and the tree-edit-distance similarity (TEDS) [24].

#### Results of baseline models.

We train the cell detectors†††The training detail is described in the
supplemental material. in the baseline and then parse the table structures
with the above-mentioned post-processing schemes. Tab. 2 shows the evaluation
results of all baseline models on the testing split of our WTW dataset.
Compared with the anchor-based approaches Faster-RCNN, TridenNet, and Cascade-
RCNN, the anchor-free CenterNet obtains the best F-score in the aspect of
physical structure accuracy as it does not require fine adjustment of
parameters. With more accurate cell detection results, it also achieves the
best performance for logical structure correctness.

To further analyze the challenges of table structure parsing in the wild, we
visualize the parsing results of two example images taken from different
scenes for the baseline models with different object detectors in Fig. 2. As
shown in this figure, the cells can be detected well for both the anchor-based
and the anchor-free approaches when the table is approximately aligned with
the image domain. By contrast, when leveraging those approaches in the image
that have non-rigid deformation, the anchor-based approaches will yield
incorrect results. The anchor-free detector, CenterNet, performs better than
others while still remaining room for better table parsing accuracy. For more
challenging images, it would be of great interest in developing a robust table
structure parsing approach.

|  |  |
---|---|---|---
|  |  |
Faster-RCNN | TridenNet | Cascade-RCNN | CenterNet

Figure 2: Visualization of the table structure parsing results of the baseline
models on the WTW dataset.

Model | Physical Structure | Adjacency Relation | TEDS
---|---|---|---
Prec. | Rec. | F1 | Prec. | Rec. | F1
Faster-RCNN | 72.1 | 61.5 | 66.4 | 87.1 | 61.3 | 71.9 | 49.5
TridenNet | 64.5 | 65.5 | 65.0 | 85.4 | 71.5 | 77.8 | 47.8
Cascade-RCNN | 77.4 | 65.3 | 70.9 | 89.1 | 64.5 | 74.9 | 53.2
CenterNet | 74.2 | 72.1 | 73.1 | 90.8 | 79.7 | 84.8 | 58.7

Table 2: Baseline models on WTW dataset. The physical structure is to measure
the accuracy of cell coordinate when IOU=0.9, Adjacency Relation, and TEDS
measure the row/col structure information, where the Adjacency Relation is
based on the IOU=0.6 Figure 3:  The pipeline of Cycle-CenterNet. Taking an
image as input, our model produces one 2-channel keypoint heatmap and one
2-channel offset map. The Cycle-Pairing module outputs two 8-channel heatmaps,
which learn the mutual-directed relationship between center point and
vertices. According to the relationship, cells are grouped, and finally, the
number of row and column information can be recovered by parsing processing.

##  4 Cycle-CenterNet

Building on the top of CenterNet, our proposed network adds a Cycle-Pairing
module and Pairing loss to learn the common vertex between neighbor cells on
the basis of CenterNet [25]. Through the common vertex, we can splice all the
cells together and get a complete table structure. Finally, using the same
Parsing-Processing to get row/col information. An illustrative demonstration
for our Cycle-CenterNet is shown in Fig. 3.

Figure 4: Illustration the process of grouping cells by mutual-directed
relationship learned by cycle-pairing module.

###  4.1 Cycle-Pairing Module

To recognize table structure, we proposed a Cycle-Pairing module to locate the
cells and learn the splicing information between cells, which consist of two
branches, including _center-to-vertex branch_ and _vertex-to-center branch_.
As shown in Fig. 3, in the center-to-vertex branch, we regress the offset from
a center of a table cell to its vertices, and following the post process of
Centernet [25], the polygonal representation of table cells could be obtained;
In the vertex-to-center branch, the offsets between common vertex and the
centers of its surrounding cells centers are learned. Finally, the splicing
information of tables could be deduced in the Parsing-Processing.

#### Center-to-Vertex branch for cells localization.

Taking the feature map $F$ from the DLA-34 [22] backbone as input, the center-
to-vertex branch predict a
${{CV}_{map}}\in{{R}^{\frac{h}{4}\times\frac{w}{4}\times 8}}$. As shown in
Fig. 4 (a), the ${{CV}_{map}}$ indicates the coordinate offset
${\\{\Delta{x},\Delta{y}\\}}$ between the center point ${P=\\{x_{C},y_{C}\\}}$
and its four vertices ${V=\\{x_{V},y_{V}\\}}$, denoted by

$\left\\{\begin{split}&\Delta{{x}_{{{C}_{ik}}}}={{x}_{{{C}_{i}}}}-{{x}_{{{V}_{ik}}}}\\\
&\Delta{{y}_{{{C}_{ik}}}}={{y}_{{{C}_{i}}}}-{{y}_{{{V}_{ik}}}}\\\
\end{split}\right.{,{i=1:{{N}^{C}},k=1:4}}\text{ },$ (1)

where ${{N}^{C}}$ is the number of all the center points of table cells.

#### Vertex-to-Center branch for cells grouping.

Taking the feature map $F$ from backbone DLA-34 as input, the Vertex-to-Center
branch predicts a ${{VC}_{map}}\in{{R}^{\frac{h}{4}\times\frac{w}{4}\times
8}}$. As shown in Fig. 4 (b), the ${{VC}_{map}}$ encodes the coordinate offset
${\\{\Delta{x},\Delta{y}\\}}$ between the common vertex
${V=\\{x_{V},y_{V}\\}}$ and four center points ${P=\\{x_{C},y_{C}\\}}$ of the
surrounding table cells, denoted by

$\left\\{\begin{split}&\Delta{{x}_{{{V}_{ik}}}}={{x}_{{{V}_{i}}}}-{{x}_{{{C}_{ik}}}}\\\
&\Delta{{y}_{{{V}_{ik}}}}={{y}_{{{V}_{i}}}}-{{y}_{{{C}_{ik}}}}\\\
\end{split}\right.{{|}{i=1:{{N}^{V}},k=1:4}}\text{ },$ (2)

where ${{N}^{V}}$ denotes the number of all the common vertexes. If the number
of cells sharing this vertex $K$ is smaller than 4, the regression value of
the remaining positions are set to 0.

###  4.2 Pairing Loss for Cycle-Pairing Module

Instead of directly applying loss functions on the output maps of Cycle-
Pairing Module, we design a pairing loss to supervise the network learning
better offsets for both center-to-vertex and vertex-to-center branches by
pair-wise compute the loss function for each pair of the center and vertex
that belongs to the same cell in the expected table. Denoted by
$\mathcal{P}_{cv}=(\Delta x_{cv},\Delta y_{cv},\Delta x_{vc},\Delta y_{vc})$
for the predicted offset of a pair of center $c$ and $v$, we compute the loss
function $L_{p}$ by

$L_{p}=\sum_{c,v}\omega(\mathcal{P}_{cv})\left(\lambda_{cv}L_{cv}+\lambda_{vc}L_{vc}\right),$
(3)

where $L_{cv}$ and $L_{vc}$ are the $\ell_{1}$ loss between the predicted
offsets and the corresponding groundtruth, $\lambda_{cv}=1.0$ and
$\lambda_{vc}=0.5$ are the hyperparameters to tune the importance between
those loss items, $\omega(\mathcal{P}_{cv})$ dynamically weighing the overall
loss according to the regression quality.

#### Dynamic weighing function $\omega(\mathcal{P}_{cv})$.

The cycle-pairing module represents the pairwise pointing relationship between
vertex and center point. In fact, it is not necessary to regress cell bounding
box and common vertex group box such accurately, as long as the prediction of
center and vertex from one center-vertex pair are intersected. So we use
$\omega(\mathcal{P}_{cv})$ to weight losses ${{l}_{cv}}$ and ${{l}_{vc}}$ for
center-vertex pairs:

$\omega(\mathcal{P}_{cv})=1-{\exp\left(-\pi\mathcal{D}_{cv}\right)},$ (4)

where $\mathcal{D}_{cv}$ is the pair distance defined as

$\mathcal{D}_{cv}=\min(\frac{\left|{{x}_{c{{v}_{i}}}}-{{x}_{c{{v}_{i}}}}^{*}\right|+\left|{{x}_{v{{c}_{i}}}}-{{x}_{v{{c}_{i}}}^{*}}\right|}{\left|{{x}_{c{{v}_{i}}}}^{*}\right|},1)$
(5)

where ${{x}_{cv}}$ is a regression value from center to vertex, while
${{x}_{vc}}$ is vertex to the center. Therefore, $\mathcal{D}_{cv}$ defines
the regression error score for each center-vertex pair. As shown in Fig. 5, if
$\mathcal{D}_{cv}=0$, means that the vertex and the center point to each other
strictly without any errors. If $0<\mathcal{D}_{cv}<1$, means that although
the vertex and center couldn’t strictly point to each other, but pointing into
each other’s bounding box. If $\mathcal{D}_{cv}\geq 1$, means that there is no
intersection between the center and vertex, which is the main sample that
needs to focus on learning.

(a) $\mathcal{D}_{cv}=0$ (b) $\mathcal{D}_{cv}\in(0,1)$

(c) $\mathcal{D}_{cv}=1$ (d) $\mathcal{D}_{cv}>1$

Figure 5: Illustration of the traditional cases for center-vertex pairs during
training.

The loss ${{L}_{k}}$ of the keypoint branch and the loss ${{L}_{off}}$ of the
offset branch are consistent with CenterNet [25]. The overall training loss
is:

${{L}_{det}}={L}_{k}+{{\lambda}_{off}}{{L}_{off}}+{L}_{p}$ (6)

###  4.3 Parsing-Processing Module

As the last step, we propose a Parsing-Processing module to recover the
complete table structure information, including table id, start row/column,
and end row/column. First, split every cell into 4 bounding edges, then merge
the up edges and down edges to horizontal lines and merge left edges and right
edges to vertical lines according to cell connectivity. Next, sort the
horizontal lines, vertical lines and index them from 0. Finally, rank cells by
line index and outputs row/column information. The pseudo code is given in the
supplementary materials.

###  4.4 Training Detail

In the training process of the Cycle-Centernet, we use the pre-trained weight
on COCO, and resize the max side of the training image to 1024 with scaling
the short side equally. The initial learning rate is set to
$1.25\text{\times}{10}^{-3}$, and decayed to $1.25\text{\times}{10}^{-4}$ and
$1.25\text{\times}{10}^{-5}$ in the 90th and 120th epoch respectively. The
model is trained with a total of 150 epochs. All the experiments are performed
on a workstation with 8 NVIDIA GTX 1080Ti GPUs. During the training, we set
the batch size to 32 per GPU in parallel.

Category | Model | Backbone | Physical coordinates | Adjacency Relation | TEDS
---|---|---|---|---|---
Prec. | Rec. | F1 | Prec. | Rec. | F1
Base Model | CenterNet | DLA-34 | 74.2 | 72.1 | 73.1 | 90.8 | 79.7 | 84.8 | 58.7
Table structure models | Split+Heuristic | - | 3.2 | 3.6 | 3.4 | 25.7 | 29.9 | 27.6 | 26.0
CascadeTabNet | CascadeNet | - | - | - | 16.4 | 3.6 | 5.9 | 11.4
Ours | CenterNet(Polygon box) | DLA-34 | 75.1 | 75.7 | 75.4 | 93.0 | 89.2 | 91.1 | 70.1
Cycle-CenterNet | DLA-34 | 78.2 | 78.2 | 78.2 | 93.2 | 91.4 | 92.2 | 74.3
Cycle-Centernet+PairLoss | DLA-34 | 78.0 | 78.5 | 78.3 | 93.3 | 91.5 | 92.4 | 83.3
Table 3: Results on WTW dataset. The evaluation metrics are same with Tab. 2 Method | Simple | Inclined | Curved |  Occluded and blurred |  Extreme aspect ratio | Overlaid |  Muti color and grid
---|---|---|---|---|---|---|---
F1 | TEDS | F1 | TEDS | F1 | TEDS | F1 | TEDS | F1 | TEDS | F1 | TEDS | F1 | TEDS
Ours | 99.3 | 94.2 | 97.7 | 90.6 | 76.1 | 70 | 77.4 | 53.3 | 91.9 | 77.4 | 84.1 | 51.2 | 93.7 | 66.7
Table 4: Results on different categories.

##  5 Experiments

We perform extensive experiments on the proposed WTW dataset to verify the
effectiveness of Cycle-CenterNet. Although we mainly focus on wired tables in
wild scenes, we additionally do experiments on the widely used benchmarks of
ICDAR2013 and ICDAR2019 to demonstrate that: 1) the WTW dataset covers a wide
range of tabular images for practical applications and 2) our proposed Cycle-
CenterNet is able to recognize wireless tables.

Model |  Training Datasets | IOU=0.6
---|---|---
Prec. | Rec. | F1
DeepDeSRT [16] | SciTSR | 63.1 | 61.9 | 62.5
Split+Heuristic [19] | Private | 93.8 | 92.2 | 93.0
TableNet [11] | Marmot Extended | 92.2 | 89.9 | 91.0
Tabstruct-Net [14] | SciTSR | 91.5 | 89.7 | 90.6
Ours | WTW+ICDAR19 | 95.5 | 88.3 | 91.7
Ours* | WTW | 97.5 | 98.4 | 98.0

Table 5: Comparison for cell adjacency relation on ICDAR-2013 dataset. Here
”*” denotes for the result on wired tables only.

Model |  Training Datasets | IOU |  WAvg.
---|---|---|---
0.6 | 0.7 | 0.8 | 0.9
NLPR-PAL | - | 36.5 | 30.5 | 19.5 | 3.5 | 20.6
CascadeTab [12] |  Marmot etc. | 43.8 | 35.4 | 19 | 3.6 | 23.2
GTE [23] |  FinTabNet | 38.5 | - | - | - | 24.8
TabStruct-Net [14] |  SciTSR | 80.4 | - | - | - | -
Ours | WTW | 80.8 | 51.1 | 31.9 | 11.2 | 40.0

Table 6: Comparison with participants of ICDAR 19 Track B2 (Modern) F1-scores
[3], here all the methods finetune on the ICDAR-2019 dataset, we just list
their initial training datasets.

###  5.1 Evaluation on WTW

To evaluate the performance of Cycle-Centernet on the WTW dataset, we compare
it with some latest table recognition methods including Split+Heuristic [19]
and CascadeTabNet [12]. For a fair comparison, those methods are retrained on
the WTW dataset with the author-provided hyperparameter settings. As discussed
in Sec. 3.2, we evaluate the correctness of the parsed tables in both aspects
of physical structures and logical structures. For the physical structure
(cell coordinates), the precision, recall and, F1 score are used under a
strict IoU threshold of 0.9. For the logical structure (row/column
information), TEDS [24] and cell adjacent relationship (IOU=0.6) [4] are used
as evaluation metrics.

#### Quantitative comparison.

Tab. 3 shows the performance of all the models on the challenging WTW dataset.
It is shown that the state-of-the-art table structure parsing approaches
CascadeTabNet [12] and Split+Heuristic [19] for well-conditioned tabular
images obtain poor performance on the challenging WTW dataset that has many
wild images. By contrast, benefiting from the flexible design of our method,
we significantly improve the performance of table structure parsing by large
margins. Our proposed Cycle-CenterNet obtains the best performance by using
the proposed pairing loss function.

Figure 6: Qualitative results of Cycle-Centernet on different datasets

#### Ablation study.

In Sec. 3.2, we argue that the accuracy of cell regression has a great
influence on table structure recognition, so we replace horizontal rectangle
regression with arbitrary quadrilateral regression in CenterNet. Although the
cell detection is only increased by 2.3$\%$, we get 6.3$\%$ and 11.4$\%$
improvement on adjacency relation and TEDS. The cycle-pairing module can
simultaneously detect and group tabular cells into structured digital tables,
which makes the Cycle-CenterNet get 2.8$\%$ improvement on cell detection,
1.1$\%$ improvement on adjacency relation, and 4.2$\%$ improvement on TEDS.
With the collaborative optimization of Pairing loss on center-vertice pair,
the addition of Pairing loss makes Cycle-CenterNet significantly increase on
the dedicated table structure evaluation matrix of TEDS by 9$\%$.

Compared with our base model CenterNet, the Cycle-CenterNet has a 7.6$\%$
improvement on adjacency relation and 24.6$\%$ improvement on TEDS. Since the
models in other papers are not designed for wild tables, our Cycle-CenterNet
shows obvious advantages in all evaluation metrics.

#### Sub-category experiments.

To verify the complexity of our WTW dataset, we analyze the model results on
different types of tables separately. Results are shown in Tab. 4. Cycle-
CenterNet achieves 99.3$\%$ in adjacency relation and 94.2$\%$ in TEDS on the
simple subset of WTW, 97.7$\%$ in adjacency relation and, 90.6$\%$ in TEDS on
the inclined subset. It means the Cycle-CenterNet can get a good result for
ordinary tables. Relatively good results (91.9$\%$ at adjacency relation and
77.4$\%$ at TEDS) are obtained for tables with extreme aspect ratios for the
vertex-to-center branch which can pull the bounding box to the vertex.
Although our Cycle-Centernet has reached the state of the art, it still needs
to be improved on some styles like curved, overlaid, etc. Our model just gets
53.3$\%$ at TEDS on occlusion and blur subset. Besides, multiple table
superposition also brings great difficulties to the table recognition task. A
table with especially dense cells, combined with any slightly complex feature
makes the task drastically difficult. We will continue to seek solutions to
these problems and look forward to more researchers joining in.

###  5.2 Evaluation on other Datasets

To evaluate the robustness and versatility of Cycle-CenterNet, we test our
model on two mostly used datasets in table structure recognition, ICDAR-2013
[5] and ICDAR-2019 [3]. These two datasets consisting of both wired and
wireless tables. For lacking wireless table in WTW, we finetune the Cycle-
CenterNet on the ICDAR2019 training set and test on ICDAR 2019 Track B2
dataset. Since ICDAR2013 only has test set, we selected some wireless tables
from ICDAR-2019 to finetune our model and test on ICDAR2013. Tab. 5 and 6 show
the results on datasets ICDAR-2013 [5] and ICDAR-2019 [3]. Here the evaluation
metric only includes the cell adjacency relation [4]: Recall (Rec.), Precision
(Prec.), F1-metric op (F1).

Although Cycle-CenterNet is mainly designed for wired tables and trained on
WTW, it still obtains 91.7$\%$ fscore on ICDAR2013 with wireless tables, and
is only 1.3$\%$ lower than the first-ranked model of Split+Heuristic. This
shows our model can also cover wireless tables. Similarly, our WTW mainly
focuses on wild wired tables, but Cycle-CenterNet trained only on WTW and
tested on ICDAR2013 wired tables can still achieve 98.0$\%$ fscore, indicating
that WTW can also cover simple wired tables.

For ICDAR-2019 [3], we keep the same evaluation metric: ICDAR 19 Track B2
F1-scores [3], which is based on the adjacency relation evaluation [4].
Precision, Recall, and F1 scores are calculated with IoU thresholds 0.6, 0.7,
0.8, and 0.9 respectively. The Weighted-Average F1 (WAvg.) is calculated by
assigning a weight to each F1 value of the corresponding IoU threshold. As
shown in Tab. 6, compared with the highest result of the Weighted-Average F1
reported so far, Cycle-CenterNet has improved 15.2$\%$ and achieve the start
of the art.

##  6 Conclusions and Future Work

In this paper, we tackle the problem of table structure parsing in the wild by
proposing a new WTW dataset and a deep table structure parser, Cycle-
CenterNet. On one hand, the proposed WTW dataset contains about 14k real-scene
images that are taken in wild imaging conditions, which pushes the boundary of
table structure parsing from the digital document images to the real-scene
images. On another hand, we propose a new approach for wild-scene table
structure recognition, called Cycle-CenterNet, which addressed the major
weaknesses of the existing approaches including imprecise geometry prediction
of instances with extremely physical distortion and defectiveness in
extracting logical structures of misaligned tables. The comprehensive
experiments demonstrated that the proposed approach resolves the mentioned
issues in a principled way and achieves a new state-of-art for table structure
parsing. We hope our proposed WTW dataset can further improve future research
on table recognition.

## Acknowledgement

This work was supported by the National Natural Science Foundation of China
under Grant 61922065, Grant 61771350, Grant 41820104006, and National Post-
Doctoral Program for Innovative Talents under Grant BX20200248. This work was
also supported by Alibaba Group through Alibaba Innovative Research (AIR)
program. The numerical calculations in this paper have been done on the
Supercomputing System in the Supercomputing Center of Wuhan University. The
views presented in this paper are those of the authors and should not be
interpreted as representing any funding agencies.

## References

  * [1] Zhaowei Cai and Nuno Vasconcelos.  Cascade r-cnn: Delving into high quality object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6154–6162, 2018.
  * [2] Zewen Chi, Heyan Huang, Heng-Da Xu, Houjin Yu, Wanxuan Yin, and Xian-Ling Mao.  Complicated table structure recognition.  arXiv preprint arXiv:1908.04729, 2019.
  * [3] Liangcai Gao, Yilun Huang, Hervé Déjean, Jean-Luc Meunier, Qinqin Yan, Yu Fang, Florian Kleber, and Eva Lang.  Icdar 2019 competition on table detection and recognition (ctdar).  In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 1510–1515. IEEE, 2019.
  * [4] Max Göbel, Tamir Hassan, Ermelinda Oro, and Giorgio Orsi.  A methodology for evaluating algorithms for table understanding in pdf documents.  In Proceedings of the 2012 ACM symposium on Document engineering, pages 45–48, 2012.
  * [5] Max Göbel, Tamir Hassan, Ermelinda Oro, and Giorgio Orsi.  Icdar 2013 table competition.  In 2013 12th International Conference on Document Analysis and Recognition, pages 1449–1453. IEEE, 2013.
  * [6] E Green and M Krishnamoorthy.  Recognition of tables using table grammars.  In Proceedings of the Fourth Annual Symposium on Document Analysis and Information Retrieval, pages 261–278, 1995.
  * [7] Katsuhiko Itonori.  Table structure recognition based on text block arrangement and ruled line position.  In Proceedings of 2nd International Conference on Document Analysis and Recognition (ICDAR’93), pages 765–768. IEEE, 1993.
  * [8] Thomas G Kieninger.  Table structure recognition based on robust block segmentation.  In Document Recognition V, volume 3305, pages 22–32. International Society for Optics and Photonics, 1998.
  * [9] Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, Ming Zhou, and Zhoujun Li.  Tablebank: A benchmark dataset for table detection and recognition.  arXiv e-prints, pages arXiv–1903, 2019.
  * [10] Yanghao Li, Yuntao Chen, Naiyan Wang, and Zhaoxiang Zhang.  Scale-aware trident networks for object detection.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6054–6063, 2019.
  * [11] Shubham Singh Paliwal, D Vishwanath, Rohit Rahul, Monika Sharma, and Lovekesh Vig.  Tablenet: Deep learning model for end-to-end table detection and tabular data extraction from scanned document images.  In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 128–133. IEEE, 2019.
  * [12] Devashish Prasad, Ayan Gadpal, Kshitij Kapadni, Manish Visave, and Kavita Sultanpure.  Cascadetabnet: An approach for end to end table detection and structure recognition from image-based documents.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 572–573, 2020.
  * [13] Shah Rukh Qasim, Hassan Mahmood, and Faisal Shafait.  Rethinking table recognition using graph neural networks.  pages 142–147, 2019.
  * [14] Sachin Raja, Ajoy Mondal, and CV Jawahar.  Table structure recognition using top-down and bottom-up cues.  In European Conference on Computer Vision, pages 70–86. Springer, 2020.
  * [15] Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun.  Faster R-CNN: towards real-time object detection with region proposal networks.  IEEE Trans. Pattern Anal. Mach. Intell., 39(6):1137–1149, 2017\.
  * [16] Sebastian Schreiber, Stefan Agne, Ivo Wolf, Andreas Dengel, and Sheraz Ahmed.  Deepdesrt: Deep learning for detection and structure recognition of tables in document images.  In 2017 14th IAPR international conference on document analysis and recognition (ICDAR), volume 1, pages 1162–1167. IEEE, 2017.
  * [17] Asif Shahab, Faisal Shafait, Thomas Kieninger, and Andreas Dengel.  An open approach towards the benchmarking of table structure recognition systems.  In Proceedings of the 9th IAPR International Workshop on Document Analysis Systems, pages 113–120, 2010.
  * [18] Ashwin Tengli, Yiming Yang, and Nian Li Ma.  Learning table extraction from examples.  In COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics, pages 987–993, 2004.
  * [19] Chris Tensmeyer, Vlad I Morariu, Brian Price, Scott Cohen, and Tony Martinez.  Deep splitting and merging for table structure decomposition.  In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 114–121. IEEE, 2019.
  * [20] Scott Tupaj, Zhongwen Shi, C Hwa Chang, and Hassan Alam.  Extracting tabular information from text files.  EECS Department, Tufts University, Medford, USA, 1996.
  * [21] Yalin Wang, Ihsin T Phillips, and Robert M Haralick.  Table structure understanding and its performance evaluation.  Pattern recognition, 37(7):1479–1497, 2004.
  * [22] Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell.  Deep layer aggregation.  In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pages 2403–2412, 2018.
  * [23] Xinyi Zheng, Douglas Burdick, Lucian Popa, Xu Zhong, and Nancy Xin Ru Wang.  Global table extractor (gte): A framework for joint table identification and cell structure recognition using visual context.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 697–706, 2021.
  * [24] Xu Zhong, Elaheh ShafieiBavani, and Antonio Jimeno Yepes.  Image-based table recognition: data, model, and evaluation.  arXiv preprint arXiv:1911.10683, 2019.
  * [25] Xingyi Zhou, Dequan Wang, and Philipp Krähenbühl.  Objects as points.  arXiv preprint arXiv:1904.07850, 2019.