11institutetext: Chair of Process and Data Science
RWTH Aachen University, Aachen, Germany
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>aachen.de

# Object-Centric Alignments

Lukas Liss  Jan Niklas Adams  Wil M.P. van der Aalst

###### Abstract

Processes tend to interact with other processes and operate on various objects
of different types. These objects can influence each other creating
dependencies between sub-processes. Analyzing the conformance of such complex
processes challenges traditional conformance-checking approaches because they
assume a single-case identifier for a process. To create a single-case
identifier one has to flatten complex processes. This leads to information
loss when separating the processes that interact on some objects. This paper
introduces an alignment approach that operates directly on these object-
centric processes. We introduce alignments that can give behavior-based
insights into how closely related the event data generated by a process and
the behavior specified by an object-centric Petri net are. The contributions
of this paper include a definition for object-centric alignments, an algorithm
to compute them, a publicly available implementation, and a qualitative and
quantitative evaluation. The qualitative evaluation shows that object-centric
alignments can give better insights into object-centric processes because they
correctly consider inter-object dependencies. Findings from the quantitative
evaluation show that the run-time grows exponentially with the number of
objects, the length of the process execution, and the cost of the alignment.
The evaluation results motivate future research to improve the run-time and
make object-centric alignments more applicable for larger processes.

###### Keywords:

Process mining Object-centric process mining Alignments.

##  1 Introduction

Process mining provides insights into processes by analyzing event data
generated by these processes. When analyzing a process, one standard pipeline
consists of extracting data, discovering a process model, and checking the
conformance of the process with specifications [13]. This paper presents an
approach to compute alignments to check the conformance of object-centric
processes for which traditional conformance-checking methods fail to give
correct insights.

Traditional process mining approaches depend on the assumption that a process
is defined by a single case notion meaning that all actions created for one
object define a process execution. Processes in the real world tend not to fit
that assumption. An example of that is a typical supply chain process. Supply
processes are happening on raw materials, production processes on raw
materials and products, shipping processes on products and orders, and payment
processes operating on orders and customers. One execution of the supply chain
is not defined by a single object. Real-world processes consist of multiple
sub-processes operating on multiple object instances from various types. These
sub-processes can have synchronization points and long-term dependencies
between different objects.

Figure 1: A process execution of our running examples. Events are associated
with objects of type package (prefix p) or item (prefix i). The process
execution describes the partial order of events induced by the individual
objects. Figure 2: Top: De-jure model as an object-centric Petri net. Variable
arcs in the model are marked red. Bottom: The process execution of Figure 1 is
flattened to the individual objects and aligned to the de-jure model’s subnet
of the object’s types.

Recently, approaches have been made to generalize the notion of a process so
that one can describe these complex processes. Those approaches fall under the
umbrella term of object-centric process mining [20]. Object-centric process
mining generalizes traditional process mining techniques such that one does
not follow one object through one process, but multiple objects through
multiple, connected sub-processes. This generalization increases the
complexity. In traditional process mining, one execution of a process is
called case and is defined by a sequence of events [1]. An object-centric
process execution is a graph describing the partial order between events in
different sub-processes [7]. So far, a fitness notion based on replay has been
proposed for object-centric conformance checking, but the approach is
constrained to replayable behavior[5]. However, process owners are typically
interested in aligning observed behavior to modeled behavior, finding
deviations in their execution of the process, i.e., using alignments [8]. The
notion, calculation, implementation, and feasibility analysis for alignments
on object-centric process mining are, so far, missing.

The running example used in this paper describes a packaging process with
cross-object dependencies. In our example, one process execution refers to
multiple items and one package. Figure 1 depicts a process execution as a
graph of events describing the partial order between item and package objects.
Figure 2 shows an object-centric Petri net [4] of the packaging process. An
object-centric Petri net differs from traditional Petri nets by introducing
place types and variable arcs. Tokens are typed and places of one type can
only hold tokens of the same type. Variable arcs can consume an arbitrary
amount of tokens. Places are typed according to either item (green) or package
(blue). We, furthermore, colored transitions with the colors of the types that
are involved in this transition for clarity and highlighted the variable arcs
with red. In the given process, the path of the package depends on the path of
items and vice-versa. The package and the items can either be part of a sample
order or a product order, but never both, depending on whether receive sample
order or receive product order fires. Although the objects do not share any
more events after the start, their allowed behavior still depends on whether
they belong to a sample or product order.

If a process owner would like to find deviations in their object-centric
processes today, they would need to flatten [2] the observed process
executions and apply traditional alignments to the object-centric Petri net’s
subnets of the same type. We show this for our example process execution of
Figure 1 in Figure 2. If flattened to one trace per object, the three
resulting traces get aligned to the type’s subnet in a way that is not
possible in the composed model. As mentioned, activity receive sample order
and receive product order can never happen both in one process execution since
the de-jure model forces a decision between product orders and sample orders.
But the flattened alignments do not agree on which activity should happen. The
alignment for p1 has receive product order in the model part whereas the
alignments for i1 and i2 have receive sample order in their model part. As
shown by the running example, computing alignments on object-centric processes
requires more than just finding alignments for each object individually.
Aligning the sub-processes for all objects by respecting their object
dependencies creates a computationally complex problem that we tackle in this
paper.

This paper presents four contributions to enable and investigate object-
centric alignments. First, we generalize the notion of an alignment to object-
centric processes. Second, we present an algorithm to compute optimal object-
centric alignments. Third, we implemented our algorithm and make it publicly
accessible as an open-source project111https://github.com/LukasLiss/object-
centric-alignments based on the open-source object-centric process mining
library opca [6]. Fourth, we evaluate the quality and the computation time of
object-centric alignments on real-world event data. Thereby, we gain insights
into the scalability and suitability of the approach.

This paper is structured in the following way. We present related work in
Section 2 and preliminaries in Section 3. Then, we define object-centric
alignments in Section 4. Our algorithm to compute alignments consists of two
parts: constructing the synchronous product net (Section 5) and finding an
optimal alignment in the synchronous product net (Section 6). We present a
qualitative and quantitative evaluation in Section 7 and conclude the paper in
Section 8.

##  2 Related Work

Process mining includes discovery, conformance checking, and enhancement of
business processes [1]. Our approach belongs to the category of conformance
checking, where behavior from the event log is compared to allowed behavior
that is specified by a de-jure model [13]. For traditional processes, there
exists a variety of conformance checking approaches [19]. The majority of them
use either a token-based replay [25] approach, or an alignment [8] approach.
Both have been used to derive quality metrics like precision [9] and fitness
[10]. Unlike token-based replay, alignments are independent of the structure
of the de-jure model [8]. Like our calculation, the traditional alignment
calculation defined by Adriansyah et al. uses a two-step algorithm to compute
alignments [8]. Adriansyah et al.’s approach creates a synchronous product net
such that finding optimal alignments relates to finding a shortest path in
that net. This is a well-studied problem that can be solved with the Dijkstra
[16] or $A^{*}$ [14] algorithm. Different ways to speed up the calculation
have been researched [18][27]. However, the alignment algorithm assumes the
process to have a single case identifier and can therefore not be used for
compositions of processes that operate on multiple objects.

Multiple extensions to the traditional alignment algorithm have been made over
the years that consider additional dimensions together with the workflow
dimension [11][12]. Thereby they use higher-order nets to represent the
additional dimensions. The data and resource-aware conformance checking
approach from de Leoni et al. uses data Petri nets [23]. Felli et al. use data
Petri nets together with satisfiability modulo theories to compute data-aware
alignments [21]. Sommers et al. constructed a $\nu$-Petri net to calculate
resource-constrained alignments [26]. But all of the approaches above assume
the process to have a single-case identifier.

There are approaches that lift this generalization and model processes as
interacting sub-processes. Multi-agent process models describe the behavior of
agents and their interaction by composing Petri nets [24]. Object-centric
process mining [2] extends the notion of processes so that they can interact
and operate on objects from different types. Adams et al. defined the notion
of cases and variants for object-centric processes [7] as event graphs instead
of event sequences. The defined process executions serve as input for our
alignment calculation. The other data type that we use as input is an object-
centric Petri net [4] that can describe allowed behavior. Object-centric Petri
nets can be discovered from object-centric event logs using the discovery
algorithm from van der Aalst and Berti [4]. Precision and fitness metrics to
evaluate the quality of a model have, recently, been proposed [5]. However,
techniques to check conformance to a de-jure model and spot deviations, such
as object-centric alignments, are so far missing.

##  3 Preliminaries

Object-centric process mining deals with events that operate on a variety of
objects of different types. Events are activities that happen at a timestamp
for a number of objects of different types. $\mathbb{U}_{event}$ is the
Universe of event identifiers. The universe $\mathbb{U}_{act}$ contains all
visible activities. $\mathbb{U}_{typ}$ is the universe of all object types.
The universe of objects is $\mathbb{U}_{obj}$. Each object has exactly one
type associated with it $\pi_{type}:\mathbb{U}_{obj}\to\mathbb{U}_{typ}$.
$\mathbb{U}_{time}$ is the universe of all timestamps.

######  Definition 1 (Event Log)

$L=(E,O,OT,\pi_{act},\pi_{obj},\pi_{time},\pi_{trace})$ is an event log with:

  * •

$E\subseteq\mathbb{U}_{event}$ is a set of events,
$O\subseteq\mathbb{U}_{obj}$ is a set of objects,

  * •

$OT=\\{\pi_{type}(o)|o\in O\\}$ is a set of object types,

  * •

$\pi_{act}:E\to\mathbb{U}_{act}$ maps each event to an activity,

  * •

$\pi_{obj}:E\to\mathcal{P}(\mathbb{U}_{obj})\setminus\\{\emptyset\\}$ maps
each event to at least one object,

  * •

$\pi_{time}:E\to\mathbb{U}_{time}$ maps each event to a timestamp, and

  * •

$\pi_{trace}:O\to E^{*}$ maps each object onto a sequence of events such that
$\pi_{trace}(o)=\langle e_{1},...,e_{n}\rangle$ with
$\\{e_{1},...,e_{n}\\}=\\{e\in E|o\in\pi_{obj}(e)\\}$ and
$\forall_{i\in\\{1,...,n-1\\}}\;\pi_{time}(e_{i})\leq\pi_{time}(e_{i+1})$

Event logs can contain events from multiple process executions. When analyzing
the behavior we want to extract one process execution.

######  Definition 2 (Process Execution)

Let $L=(E,O,OT,\pi_{act},\pi_{obj},\pi_{time},\pi_{trace})$ be an object-
centric event log. The object graph $OG_{L}{=}(O,I)$ with
$I{=}\\{\\{o,o^{\prime}\\}|\allowbreak\exists_{e\in
E}\\{o,o^{\prime}\\}\subseteq\pi_{obj}(e)\wedge o\neq o^{\prime}\\}$ connects
objects that share events. The connected components $con(L)=\\{X\subseteq
O|X\text{ is a connected component in }OG_{L}\\}$ of the object graph are sets
of inter-dependent objects. Each set $X\in con(L)$ defines a process execution
of $L$. A process execution is a graph $P_{X}=(E_{X},D_{X})$ with nodes
$E_{X}=\\{e\in E|X\cap\pi_{obj}(e)\neq\emptyset\\}$ and edges
$D_{X}=\\{(e,e^{\prime})\in E_{X}\times E_{X}|\exists_{o\in X,1\leq
i<n}\langle e_{1},...,e_{n}\rangle=\pi_{trace}(o)\wedge e=e_{i}\wedge
e^{\prime}=e_{i+1}\\}$. The set $px(L)=\\{P_{X}|X\in con(L)\\}$ contains all
process executions of event log $L$.

Figure 1 shows the process execution of the running example. Object-centric
Petri nets describe object-centric behavior by using types like a colored
Petri net [22].

$\mathcal{B}(A)$ is used to represent all multisets for a set $A$. Given
multiset $M$ for set $A$, the number of instances of element $a\in A$ in $M$
is $M(a)$. We overload the notation $M=[a^{k}|a\in A]$ to state that there are
$k$ instances of element $a$ in multiset $M$.

######  Definition 3 (Object-centric Petri Net [4])

An object-centric Petri net is a tuple $ON=(N,pt,F_{var})$ where $N=(P,T,F,l)$
is a labeled Petri net with places P and transitions T.
$F\in\mathcal{B}((P\times T)\cup(T\times P))$ is the multiset of arcs between
places and transitions. Transitions are labeled with activities or $\tau$ by
$l:T\to\mathbb{U}_{act}\cup\\{\tau\\}$ with invisible activity
$\tau\not\in\mathbb{U}_{act}$. $pt:P\to\mathbb{U}_{typ}$ maps places to object
types and $F_{var}\leq F$ is the sub-multiset of variable arcs.

Note that we label all transitions to activities or $\tau$ with function $l$.
Other common definitions for object-centric Petri nets define $l$ as a partial
function. This can be translated into our definition by assuming $l(t)=\tau$
for all $t$ without a label. We define the following derived notations for
object-centric Petri nets

  * •

$\bullet t=\\{p\in P|(p,t)\in F\\}$ is the preset of transition $t\in T$.

  * •

$t\bullet=\\{p\in P|(t,p)\in F\\}$ is the post set of transition $t\in T$.

  * •

$pl(t)=\bullet t\cup t\bullet$ are the input and output places of $t\in T$,
$pl_{var}(t)=\\{p\in P|\\{(p,t),(t,p)\\}\cap F_{var}\neq\emptyset\\}$ are
places that are connected through variable arcs and $pl_{nv}(t)=\\{p\in
P|\\{(p,t),(t,p)\\}\cap(F\setminus F_{var})\neq\emptyset\\}$ are places that
are connected through non-variable arcs.

  * •

$tpl(t)=\\{pt(p)|p\in pl(t)\\}$, $tpl_{var}(t)=\\{pt(p)|p\in pl_{var}(t)\\}$,
and $tpl_{nv}(t)=\\{pt(p)|p\in pl_{nv}(t)\\}$ are object types related to
transitions.

Figure 2 shows the object-centric Petri net for the running example. It has
two object types and variable arcs for transitions receive sample order and
receive products order.

######  Definition 4 (Well-Formed Object-Centric Petri Net [4])

Let $ON=(N,pt,F_{var})$ be an object-centric Petri net with $N=(P,T,F,l)$. ON
is well-formed if for each transition $t\in T:tpl_{var}(t)\cap
tpl_{nv}(t)=\emptyset$.

In a well-formed object-centric Petri net arcs, connected to the same
transition and places with the same object type, are either all variable or
none of them is. We assume for the following that all the object-centric Petri
nets we use are well-formed. Similar to colored Petri nets, object-centric
Petri nets use the notion of markings and bindings to describe the semantics
of a Petri net.

######  Definition 5 (Marking of object-centric Petri Net [4])

Let $ON=(N,pt,\allowbreak F_{var})$ be an object-centric Petri net with
$N=(P,T,F,l)$. $\mathcal{Q}_{ON}=\\{(p,o)\in
P\times\mathbb{U}_{obj}|pt(p)=\pi_{type}(o)\\}$ is the set of possible tokens.
A marking M of ON is a multiset of tokens $M\in\mathcal{B}(\mathcal{Q}_{ON})$.

A binding describes which transition fires and what object instances are
consumed and produced per object type.

######  Definition 6 (Binding of object-centric Petri Net [4])

Let $ON=(N,pt,\allowbreak F_{var})$ be an object-centric Petri net with
$N=(P,T,F,l)$. The set of all possible bindings is $B=\\{(t,b)\in
T\times(\mathbb{U}_{type}\not\to\mathcal{P}(\mathbb{U}_{obj}))|dom(b)=tpl(t)\land\forall_{ot\in
tpl_{nv}(t)}\forall_{p\in pl_{nv}(t),pt(p)=ot}|b(ot)|=F(p,t)\\}$. A binding
$(t,b)\in B$ corresponds to firing transition t in Petri net ON. The object
map b describes what object instances are consumed and produced. The multiset
of consumed tokens given binding $(t,b)\in B$ is
$cons(t,b)=[(p,o)\in\mathcal{Q}_{ON}|p\in\bullet t\land o\in b(pt(p))]$. The
multiset of produced tokens given binding $(t,b)\in B$ is
$prod(t,b)=[(p,o)\in\mathcal{Q}_{ON}|p\in t\bullet\land o\in b(pt(p))]$.

Binding $(t,b)\in B$ is enabled in marking $M\in\mathcal{B}(\mathcal{Q}_{ON})$
if $cons(t,b)\leq M$. Applying binding $(t,b)$ in marking $M$ leads to new
marking $M^{\prime}=M-cons(t,b)+prod(t,b)$. We use the notation
$M\xrightarrow{\text{(t,b)}}M^{\prime}$ for applying $(t,b)$ in $M$. This
implies that $(t,b)$ was enabled in $M$ and $M^{\prime}$ is the result of
applying $(t,b)$ in $M$.

This notation can be extended to a sequence of bindings
$\sigma=\langle(t_{1},b_{1}),(t_{2},b_{2}),...,\allowbreak(t_{n},b_{n})\rangle\in
B^{*}$ such that
$M_{0}\xrightarrow{\text{$(t_{1},b_{1})$}}M_{1}\xrightarrow{\text{$(t_{2},b_{2})$}}M_{2}...\xrightarrow{\text{$(t_{n},b_{n})$}}M_{n}$.
We use the notation $M\xrightarrow{\text{$\sigma$}}M^{\prime}$ to show that
$M^{\prime}$ can be reached from $M$ by applying the bindings in $\sigma$
after another. The transitions can be mapped to activities using the label
function $l$. This results in the visible binding sequence
$\sigma_{\upsilon}=\langle(l(t_{1}),b_{1}),(l(t_{2}),b_{2}),...,(l(t_{n}),b_{n}))$
where $(l(t_{i}),b_{i})$ is omitted if $l(t_{i})=\tau$.

######  Definition 7 (Accepting object-centric Petri Net [4])

An accepting object-centric Petri net is a tuple $AN=(ON,M_{init},M_{final})$
where $ON=(N,pt,F_{var})$ is a well-formed object-centric Petri net.
$M_{init}\in\mathcal{B}(\mathcal{Q}_{ON})$ and
$M_{final}\in\mathcal{B}(\mathcal{Q}_{ON})$ indicate the initial and final
markings of the net.

Accepting object-centric Petri nets accept some binding sequences and some
not. The set of all binding sequences that are accepted form a language.

######  Definition 8 (Language of an Accepting Petri Net [4])

The language
$\phi(AN)=\\{\sigma_{\upsilon}|M_{init}\xrightarrow{\text{$\sigma$}}M_{final}\\}$
of an accepting object-centric Petri net $AN=\allowbreak(ON,\allowbreak
M_{init},M_{final})$ contains all the visible binding sequences starting in
$M_{init}$ and ending in $M_{final}$.

##  4 Alignment

Alignments show how process executions and the allowed behavior of a de-jure
model relate to each other. We use moves to represent whether something occurs
in the process execution, the de-jure model, or both of them. Note that we do
not allow alignments to alter the set of objects. We assume them to be fixed.

######  Definition 9 (Moves)

Let $L=(E,O,OT,\pi_{act},\pi_{obj},\pi_{times},\pi_{trace})$ be an object-
centric event log and $P_{X}=(E_{X},D_{X})\in px(L)$ a process execution. Let
$AN=(((P,T,F,l),pt,F_{var}),M_{init},M_{final})$ be an accepting object-
centric Petri net. The set of all moves is
$moves(P_{X},AN)\subseteq(\\{\pi_{act}(e)|e\in
E_{X}\\}\cup\\{\gg\\})\times\mathcal{P}(O)\times(T\cup\\{\gg\\})\times\mathcal{P}(O)$
with skip symbol $\gg\not\in\mathbb{U}_{act}\cup T$. A move
$(a_{log},o_{log},t_{mod},o_{mod})\in moves(P_{X},AN)$ is one of the following
three types:
Log move - for an $e\in E_{X}$: $a_{log}=\pi_{act}(e)$,
$o_{log}=\pi_{obj}(e)$, $t_{mod}=\gg$, and $o_{mod}=\emptyset$.
Model move - for a $(t,b)\in\sigma\text{ with }\sigma_{\upsilon}\in\phi(AN)$:
$t_{mod}=t$, $o_{mod}=\bigcup_{o\in range(b)}o$, $a_{log}=\gg$, and
$o_{log}=\emptyset$.
Synchronous move - for an $e\in E_{X}$ and a $(t,b)\in\sigma\text{ with
}\sigma_{\upsilon}\in\phi(AN)$: $a_{log}=\pi_{act}(e)=l(t)$, $t_{mod}=t$, and
$o_{log}=o_{mod}=\pi_{obj}(e)=\bigcup_{o\in range(b)}o$.

Each type of move is presented in Figure 3. For synchronous moves, the
activity and objects of the model and log part have to be exactly the same.
For log and model moves, only one part has an activity and objects while the
other parts are skipped. The skip symbol $\gg$ represents that nothing
happened in that part. The upper part is the log part $a_{log}$ and $o_{log}$.
The lower block is the model part that contains $t_{mod}$, the activity
$l(t_{mod})$ it is labeled with, and $o_{mod}$.

Figure 3: One synchronous move, one log move, and one model move for the
running example with the accepting object-centric Petri net in Figure 2 and
the process execution in Figure 1.

We define the following projections on moves.

######  Definition 10 (Move Projections)

Given a move $m=(a_{log},o_{log},t_{mod},o_{mod})\in moves(P_{X},AN)$ with
process execution $P_{X}$ and accepting object-centric Petri Net
$AN=(((P,T,F,l),pt,F_{var}),\allowbreak M_{init},\allowbreak M_{final})$. We
use the following projections to map moves to their attributes:
$\pi_{la}(m)=a_{log}$ maps moves to their log activity.
$\pi_{lo}(m)=o_{log}$ maps moves to their log objects.
$\pi_{mt}(m)=t_{mod}$ maps moves to their model transition.
$\pi_{ma}(m)=l(t_{mod})$ maps moves to the activity the transition is labeled
with.
$\pi_{mo}(m)=o_{mod}$ maps moves to their model objects.

When reasoning about the model or log behavior individually, we want to ignore
skipped behavior in that part. An alignment, which we define in 12, is a
directed acyclic graph of moves. We need to reason about the model and log
behavior individually to define alignments. Therefore, we introduce the
following reductions that remove moves with skipped behavior in a given part
from a directed acyclic graph of moves while maintaining the partial order
defined by the acyclic graph.

######  Definition 11 (Reduction to Log and Model Part)

Let $MG=(M,C)$ be a directed acyclic graph with vertices $M\subseteq
moves(P_{X},AN)$ and edges $C\subseteq M\times M$ with process execution
$P_{X}$ and accepting object-centric Petri Net $AN$. The reduction to moves
with visible activity in the log part is $MG_{\downarrow log}=(M_{\downarrow
log},C_{\downarrow log})$ with:

  * •

$M_{\downarrow log}=\\{m\in M|\pi_{la}(m)\neq\gg\\}$ synchronous and log
moves.

  * •

$C_{\downarrow log}=\\{(m_{1},m_{n})\in M_{\downarrow log}\times M_{\downarrow
log}|\exists_{<m_{1},...,m_{n}>\in M^{*}}\;\forall_{1\leq
i<n}\;(m_{i},m_{i+1})\in
C\wedge\forall_{1<i<n}\;\allowbreak\pi_{la}(m_{i})\allowbreak=\gg\\}$ edges
between synchronous and log moves and new edges where model moves were
removed.

The reduction to moves with visible activity in the model part is
$MG_{\downarrow mod}=(M_{\downarrow mod},C_{\downarrow mod})$ with:

  * •

$M_{\downarrow mod}=\\{m\in M|\pi_{ma}(m)\neq\gg\\}$ synchronous and model
moves

  * •

$C_{\downarrow mod}=\\{(m_{1},m_{n})\in M_{\downarrow mod}\times M_{\downarrow
mod}|\exists_{<m_{1},...,m_{n}>\in M^{*}}\;\forall_{1\leq
i<n}\;(m_{i},m_{i+1})\in
C\wedge\forall_{1<i<n}\;\allowbreak\pi_{ma}(m_{i})\allowbreak=\gg\\}$ edges
between synchronous and model moves and new edges where log moves were
removed.

In Figure 4 both $MG_{\downarrow log}$ and $MG_{\downarrow model}$ are
visualized for an arbitrary directed acyclic graph of moves. $MG_{\downarrow
log}$ describes a directed acyclic graph after removing all model moves and
related edges. New edges are added when two movements used to be connected via
removed model moves in the movement graph. $MG_{\downarrow model}$ behaves
simultaneously for the model part.

Figure 4: Reductions $MG_{\downarrow log}$ and $MG_{\downarrow model}$ for a
directed acyclic graph of moves.

An alignment is a directed acyclic graph of moves that requires the log part
to contain the process execution and the model part to be in the language of
the de-jure model.

######  Definition 12 (Alignment)

Let $L=(E,O,OT,\pi_{act},\pi_{obj},\pi_{times},\pi_{trace})$ be an object-
centric event log and $P_{X}=(E_{X},D_{X})\in px(L)$ a process execution. Let
$AN=(((P,T,F,l),pt,F_{var})M_{init},M_{final})$ be an accepting object-centric
Petri net. An alignment $AL_{P_{X},AN}=(M,C)$ is a directed acyclic graph on
$M\subseteq moves(P_{X},AN)$ such that:

The alignment contains the process execution behavior in the log parts:
$P_{X}$ is isomorphic to $AL_{{P_{X},AN}_{\downarrow log}}$ with bijective
function $f:E_{X}\to M_{\downarrow log}$ such that $\forall_{e\in
E_{X}}\pi_{act}(e)=\pi_{la}(f(e))\land\pi_{obj}(e)=\pi_{lo}(f(e))$.

The alignment contains behavior that is accepted by the Petri net in the model
parts: There exists a binding sequence
$\sigma=\langle(t_{1},b_{1}),(t_{2},b_{2}),...,(t_{n},b_{n})\rangle\in B^{*}$
with $\sigma_{\upsilon}\in\phi(AN)$ and a bijective function $f^{\prime}:B\to
M_{\downarrow mod}$ such that:

  * •

$\forall_{(t,b)\in\sigma}t=\pi_{mt}(f^{\prime}(t,b))\wedge\bigcup_{o\in
range(b)}o=\pi_{mo}(f^{\prime}(t,b))$

  * •

$\forall_{m_{1},m_{2}\in M_{\downarrow mod}}(m_{1},m_{2})\in C_{\downarrow
mod}\Rightarrow\exists_{1\leq i<j\leq n}m_{1}=f^{\prime}(t_{i},b_{i})\land
m_{2}=f^{\prime}(t_{j},b_{j})$

There can be multiple alignments for a process execution and an accepting
object-centric Petri net. $al(P_{X},AN)$ is the set of all these alignments.

An alignment for the running example can be seen in Figure 5. The graph of
moves is directed and acyclic which creates a partial order of moves. When
reducing the graph to log and synchronous moves, it is isomorphic to the given
process execution in Figure 1. This ensures that the behavior of the given
process execution is contained in the alignment. The reduction to the model
part relates to a binding sequence that has to be in the language of the
accepting object-centric Petri net. This ensures that the model part describes
behavior that is accepted by the model. Note that an alignment does not put
any other requirement on the model part than to be allowed by the model.
Therefore, alignments can also contain model behavior that is very different
from the process execution. Those alignments will end up with more model and
log moves and fewer synchronous moves. Cost functions for moves allow us to
search for special behavior from the model that we want to align. Most of the
time we are looking for the allowed behavior that is the most similar to the
given process execution. That is what the standard cost function formalizes.

######  Definition 13 (Standard Cost of Move Function)

Let $AL_{P_{X},AN}=(M,C)\in al(P_{X},AN)$ be an alignment with process
execution $P_{X}$ and accepting object-centric Petri Net $AN$. The cost
function $cost_{move}:moves(P_{X},AN)\to\mathbb{R}$ is defined as:
$cost_{move}(m)=\begin{cases}0\;\text{if m is a synchronous move,}\\\
|\pi_{lo}(m)\cup\pi_{mo}(m)|\;\text{if m is a model or log
move}\wedge\pi_{ma}(m)\neq\tau,\\\ \varepsilon\;\text{if
}\pi_{ma}(m)=\tau\land a_{log}=\gg,\\\ +\infty\;\text{else}\end{cases}$

With $\varepsilon$ being a positive very small number. The cost of a complete
alignment is the sum over all alignment moves:
$cost_{alignment}(AL_{P_{X},AN})=\sum_{m\in M}cost_{move}(m)$.

The cost of the alignment in Figure 5 is 6 because there are 3 model and 3 log
moves that have one object each. The lower the cost the better model and log
part match, because synchronous moves are cheaper than model and log moves. We
call one of the cheapest alignments an optimal alignment.

######  Definition 14 (Optimal Alignment)

Let $L$ be an object-centric event log and $P_{X}\in px(L)$ be a process
execution. Let $AN$ be an accepting object-centric Petri net. An alignment
$AL_{P_{X},AN}=(M,C)\in al(P_{X},AN)$ is optimal if
$\forall_{a\in al(P_{X},AN)}\allowbreak cost_{alignment}(AL_{P_{X},AN})\leq
cost_{alignment}(a)$.

Note that there can still be multiple optimal alignments for a given process
execution and a de-jure Petri net as long as they are all equally similar to
the process execution.

Figure 5: Alignment for process execution in Figure 1 and accepting object-
centric Petri net in Figure 2.

An optimal object-centric alignment for the running example can be seen in
Figure 5. The inter-object dependencies that are defined in the object-centric
Petri net in Figure 2 are respected by the object-centric alignment. For
example, the object-centric alignment agreed on one shared start activity for
p1, i1, andi2 which keeps the alignment consistent with inter-object
dependencies. This differentiates object-centric alignments and traditional
alignments which can violate this requirement.

##  5 Object-Centric Synchronous Product Net

The first part of our approach to calculate optimal alignments is to create a
synchronous product net for a given process execution and an accepting object-
centric Petri net. That synchronous product net is designed to generate all
possible alignments. Since alignments can have model, log, and synchronous
moves, the synchronous product net consists of three parts that directly
relate to them. In the synchronous product net in Figure 8 these parts are
marked. First, we construct the log part from the process execution. Then, we
pre-process the de-jure model to finally merge them together to the
synchronous product net and add the synchronous part.

###  5.1 Process Execution Net Construction

The process execution net will be the part of the synchronous product net that
guarantees that the process execution is contained in the alignment. The
construction of the process execution net relates to Petri net runs [15] and
causal nets [3]. For each object, each edge in the process execution defines a
precondition for an event. The process execution net in Figure 6, therefore,
has a place for each condition defined in the process execution.

Figure 6: Process Execution Net

Because object-centric Petri nets are under-specified and we will merge the
created net with a given accepting object-centric Petri net, we can not use
the same objects and types for both, the log and model part. The process
execution contains directly follows relations on the level of object
instances. For example, the running example process execution in Figure 1
shows that on item i1 add sample never happens, whereas on item i2 activity
add sample happens twice. Although they both have the same object type, the
process execution differentiates them. An accepting object-centric Petri net
is under-specified in that regard because it only differentiates places by
type. Clearly, it is important to separate the object instances because
otherwise, deviations in one object instance could compensate for a contrary
deviation in another. For example, the missing add sample activity on i1 could
be compensated by the additional add sample activity on i2 if one would not
strictly separate which event happened on which object instance. To enable an
accepting object-centric Petri net to separate object instances, we have to
create a new individual type for each object instance in the process
execution. Since each object instance must have exactly one type, we then need
to replace the original object instances with new individual placeholder
object instances in the process execution net.

######  Definition 15 (Generation of new Objects and Types)

Let $L=(E,O,OT,\allowbreak\pi_{act},\pi_{obj},\pi_{times},\pi_{trace})$ be an
object-centric event log and $P_{X}=(E_{X},D_{X})\in px(L)$ a process
execution containing objects $X$. Let $O_{new}(P_{X})\in\mathbb{U}_{obj}$ with
$O_{new}(P_{X})\cap O=\emptyset$ and $|O_{new}(P_{X})|=|X|$ be a set of new
object instances and $OT_{new}(P_{X})\in\mathbb{U}_{type}$ with
$OT_{new}(P_{X})\cap\\{\pi_{type}(o)|o\in X\\}=\emptyset$ and
$|OT_{new}(P_{X})|=|X|$ be a set of new types.

Let $new_{obj}:X\to O_{new}(P_{X})$ be a bijective function that renames
objects from $X$ to unused objects in $O_{new}(P_{X})$. Let $new_{type}:X\to
OT_{new}(P_{X})$ be a bijective function that relates each object to its
unique new type.

We define the following derivative concepts:
$orob:O_{new}(P_{X})\to X$ with $orob=new_{obj}^{-1}$ returns the original
object.
$orty:OT_{new}(P_{X})\to\\{\pi_{type}(o)|o\in X\\}$ with
$orty(ot)=\pi_{type}(new_{type}^{-1}(ot))$ returns the original type of the
object that is associated with the given new type.

We create the process execution net with the new objects and types. The
conditions defined in the process execution are the directly follows relation
per object. For each condition, the Petri net contains a place. Also, start
and end places are added for each object. The transitions relate to the events
of the process execution.

######  Definition 16 (Process Execution Net)

Let $L=(E,O,OT,\pi_{act},\pi_{obj},\pi_{time},\allowbreak\pi_{trace})$ be an
object-centric event log. Let $P_{X}=(E_{X},D_{X})\in px(L)$ be a process
execution from the event log. The process execution net
$PX_{net}=(((P,T,F,l),pt,\allowbreak F_{var}),M_{init},\allowbreak M_{final})$
is an accepting object-centric Petri net with:

  * •

$P=\\{p_{o;i}|o\in X\wedge\pi_{trace}(o)=\langle e_{1},...,e_{n}\rangle\wedge
1\leq i\leq n-1\\}\\\ \cup\\{p_{o;s}|o\in X\\}\cup\\{p_{o;e}|o\in X\\}$

  * •

$T=\\{t_{e}|e\in E_{X}\\}$

  * •

$F=[(t_{e},p_{o;i})\in T\times P|\pi_{trace}(o)=\langle
e_{1},...,e_{n}\rangle\wedge\exists_{1\leq i\leq n-1}e_{i}=e]\\\
\cup[(p_{o;i},t_{e})\in P\times T|\pi_{trace}(o)=\langle
e_{1},...,e_{n}\rangle\wedge\exists_{1\leq i\leq n-1}e_{i+1}=e]\\\
\cup[(p_{o;s},t_{e})\in P\times T|\pi_{trace}(o)=\langle
e_{1},...,e_{n}\rangle\wedge e_{1}=e]\\\ \cup[(t_{e},p_{o;e})\in T\times
P|\pi_{trace}(o)=\langle e_{1},...,e_{n}\rangle\wedge e_{n}=e]$

  * •

$l(t_{e})=\pi_{act}(e)$; $pt(p_{o;i})=new_{type}(o)$; $F_{var}=\emptyset$

  * •

$M_{init}=\\{(p_{o;s},new_{obj}(o))|o\in X\\}$;
$M_{final}=\\{(p_{o;e},o^{\prime})|new_{obj}(o)\in X\\}$

###  5.2 Pre-processing of the Object-Centric Petri Net

The de-jure behavior is already given as an accepting object-centric Petri
net, which is very close to what we need to create the synchronous product
net. But an accepting object-centric Petri net can have variable arcs. The
Petri net of the running example in Figure 2 has variable arcs for $t_{1}$ and
$t_{2}$. For transitions with variable arcs, we do not know beforehand how
many objects they will use. This becomes a problem when we try to find
synchronous moves between the process execution net and the de-jure net. A
transition can only be synchronous if they use the same object instances which
implies that they use the same number of object instances. Therefore we need
to know beforehand how many object instances a transition will use.

As mentioned in Section 4, we assume that the set of objects for the alignment
is immutable and defined by the process execution. For a predefined set of
object instances, the number of objects a variable arc can use is finite.
Therefore, we can replace transitions with variable arcs with a set of
transitions without variable arcs. For each combination of how many objects a
variable arc could consume we can add a new transition to the Petri net that
uses exactly that number of objects, but by replacing the variable arc with a
number of non-variable arcs. When doing this for the Petri net in Figure 2 the
result will be the Petri net without variable arcs in Figure 7.

######  Definition 17 (Pre-processing of Accepting Object Centric Petri Net)

Let $L=(E,O,OT,\pi_{act},\pi_{obj},\pi_{times},\pi_{trace})$ be an object-
centric event log and $P_{X}=(E_{X},D_{X})\in px(L)$ a process execution. Let
$AN=(((P,T,F,l),pt,F_{var}),\allowbreak M_{init},M_{final})$ be an accepting
object-centric Petri net. Let there be an arbitrary but fixed order of types
$ot_{1},...,ot_{n}\in OT$. The pre-processed accepting object-centric Petri
net is
$DJ_{net}=(((P^{\prime},T^{\prime},F^{\prime},l^{\prime}),pt^{\prime},F^{\prime}_{var})M^{\prime}_{init},M^{\prime}_{final})$
with:

  * •

$P^{\prime}=P$, $pt^{\prime}=pt,F^{\prime}_{var}=\emptyset$,

  * •

$T^{\prime}=\\{t_{c_{1},...,c_{n}}|t\in T\wedge\forall_{1\leq i\leq n}0\leq
c_{i}\leq|\\{o\in X|\pi_{type}(o)=ot_{i}\\}|\text{ if }ot_{i}\in
tpl_{var}(t)\text{ otherwise }c_{i}=0\\}$

  * •

$F^{\prime}=[(p,t_{c_{1},...,c_{n}})\in P^{\prime}\times T^{\prime}|(p,t)\in
F\wedge(p,t)\not\in F_{var})]$
$\cup[(t_{c_{1},...,c_{n}},p)\in T^{\prime}\times P^{\prime}|(t,p)\in
F\wedge(t,p)\not\in F_{var})]$
$\cup[(p,t_{c_{1},...,c_{n}})^{k}\in P^{\prime}\times T^{\prime}|(p,t)\in
F_{var}\wedge\exists_{1\leq i\leq n}pt(p)=ot_{i}\wedge c_{i}=k]$
$\cup[(t_{c_{1},...,c_{n}},p)^{k}\in T^{\prime}\times P^{\prime}|(t,p)\in
F_{var}\wedge\exists_{1\leq i\leq n}pt(p)=ot_{i}\wedge c_{i}=k]$

  * •

$l^{\prime}(t_{c_{1},...,c_{n}})=l(t)$

  * •

$M^{\prime}_{init}=[(p,o)\in P^{\prime}\times X|\forall_{t\in T}(t,p)\not\in
F\wedge pt(p)=\pi_{type}(o)]$

  * •

$M^{\prime}_{final}=[(p,o)\in P^{\prime}\times X|\forall_{t\in T}(p,t)\not\in
F\wedge pt(p)=\pi_{type}(o)]$

We call the pre-processed accepting object-centric Petri net a de-jure net.
The de-jure net of the running example can be seen in Figure 7.

Figure 7: Preprocessed accepting object-centric Petri net without variable
arcs

###  5.3 Creating the Synchronous Product Net

Now that we have two accepting object-centric Petri nets without variable
arcs, one describing the process execution, and one describing the de-jure
behavior, we can add them together to create the synchronous product net. The
synchronous product net should directly relate to possible alignments. In an
alignment, either the process execution and the de-jure parts advance forward
separately or they advance forward synchronously. For activities to happen in
the process execution and the de-jure part simultaneously, they have to be the
same activity on the same object instances. Object-centric Petri nets can only
separate between object types and not between object instances. Therefore, we
extend the object-centric Petri net with $\nu$-net requirements that can
differentiate between object instances. We decode log, model, and synchronous
transitions with $(t_{log},\gg),(\gg,t_{mod}),$ and $(t_{log},t_{mod})$ as one
can see in the synchronous product net in Figure 8.

Figure 8: Synchronous product net for the process execution net in Figure 6
and accepting object-centric Petri net in Figure 7

######  Definition 18 (Synchronous Product Net)

Let
$PX_{net}=(((P_{PX},T_{PX},F_{PX},l_{PX}),pt_{PX},F_{var_{PX}}=\emptyset),M_{init_{PX}},M_{final_{PX}})$
be a process execution net. Let
$DJ_{net}=(((P_{DJ},T_{DJ},F_{DJ},l_{DJ}),pt_{DJ},F_{var_{DJ}}=\emptyset),M_{init_{DJ}},M_{final_{DJ}}$
be a de-jure net. Let $Var$ be a set of unused variable names.

Two transitions can be synchronous if they are labeled with the same activity
and consume the same multiset of tokens. This requires them to be related to
the same types and consume and produce the same number of tokens.
$T_{syn}=\\{(t_{PX},t_{DJ})\in T_{PX}\times
T_{DJ}|l_{PX}(t_{PX})=l(_{DJ}(t_{DJ})\wedge\\{orty(ty)|ty\in
tpl(t_{PX})\\}=tpl(t_{DJ})\wedge\forall_{p_{PX}\in\bullet
t_{PX},p_{DJ}\in\bullet
t_{DJ}}(orty(pt_{PX}(p_{PX}))=pt_{DJ}(p_{DJ}))\Rightarrow
F_{PX}((p_{PX},t_{PX})){=}F_{DJ}((p_{DJ},t_{DJ})))\wedge\forall_{p_{PX}\in
t_{PX}\bullet,p_{DJ}\in
t_{DJ}\bullet}(orty(pt_{PX}(p_{PX}))\allowbreak=pt_{DJ}(p_{DJ}))\Rightarrow(F_{PX}((t_{PX},p_{PX})){=}F_{DJ}((t_{DJ},p_{DJ})))\\}$
is the set of synchronous transitions.

The synchronous product net is the accepting object-centric $\nu$-Petri net
$SP_{net}=(ON_{SP},M_{init_{SP}},\allowbreak M_{final_{SP}},\allowbreak\nu)$
with $ON_{SP}=(N_{SP},pt_{SP},F_{var_{SP}}=\emptyset)$ with
$N_{SP}=(P_{SP},T_{SP},F_{SP},l_{SP})$ such that:

  * •

$P_{SP}=P_{PX}\cup P_{DJ}$ is the union of places and $pt_{SP}=pt_{PX}\cup
pt_{DJ}$

  * •

$T_{SP}\subset(T_{PX}^{\gg}\times T_{DJ}^{\gg})=\\{(t_{PX},\gg)|t_{PX}\in
T_{PX}\\}\cup\\{(\gg,t_{DJ})|t_{DJ}\in T_{DJ}\\}\cup T_{syn}$ is the union of
transitions with additional synchronous transitions.

  * •

$F_{SP}=[(p_{PX},(t_{PX},\gg))|(p_{PX},t_{PX})\in
F_{PX}]\cup[(p_{DJ},(\gg,t_{DJ}))|(p_{DJ},t_{DJ})\in
F_{DJ}]\cup[((t_{PX},\gg),p_{PX})|(t_{PX},p_{PX})\in
F_{PX}]\cup[((\gg,t_{DJ}),p_{DJ})|(t_{DJ},p_{DJ})\in
F_{DJ}]\cup[(p_{PX},(t_{PX},t_{DJ}))|(p_{PX},t_{PX})\in
F_{PX}\wedge(t_{PX},t_{DJ})\in T_{SP}]\\\
\cup[(p_{DJ},(t_{PX},t_{DJ}))|(p_{DJ},t_{DJ})\in
F_{DJ}\wedge(t_{PX},t_{DJ})\in T_{SP}]\\\
\cup[((t_{PX},t_{DJ}),p_{PX})|(t_{PX},p_{PX})\in
F_{PX}\wedge(t_{PX},t_{DJ})\in T_{SP}]\\\
\cup[((t_{PX},t_{DJ}),p_{DJ})|(t_{DJ},p_{DJ})\in
F_{DJ}\wedge(t_{PX},t_{DJ})\in T_{SP}]$

  * •

$l_{SP}=\\{((t_{PX},\gg),a)|(t_{PX},a)\in
l_{PX}\\}\cup\\{(\gg,t_{DJ}),a)|(t_{DJ},a)\in
l_{DJ}\\}\cup\\{((t_{PX},t_{DJ}),a)|(t_{PX},a)\in l_{PX},(t_{DJ},a)\in
l_{DJ}\\}$

  * •

$M_{init_{SP}}=M_{init_{PX}}\cup M_{init_{DJ}}$ and
$M_{final_{SP}}=M_{final_{PX}}\cup M_{final_{DJ}}$

  * •

$\nu:P_{SP}\times T_{SP}\not\to Var$ such that:
$\forall_{(t_{PX},t_{DJ})\in T_{PX}\times
T_{DJ}}\forall_{p_{PX}\in\bullet(t_{PX},t_{DJ})}\exists_{(p_{DJ},(t_{PX},t_{DJ}))\in
F_{SP}}\\\ (p_{DJ}\in P_{DJ}\wedge pt(p_{DJ})=orty(pt(p_{PX})))\Rightarrow\\\
(\nu((p_{DJ},(t_{P}X,t_{DJ})))=\nu((p_{PX},(t_{PX},t_{DJ}))))$

In the process execution part, we use the $orob$ function when comparing
objects from the model and log part. The $\nu$ net requirement function
assigns variables to the in-going arcs of the synchronous transition. For each
in-going arc from the process execution net, there has to be one arc from
every place that has the same original type, so that those arcs have the same
unique variable assigned by $Var$. This requires the synchronous move to use
the same object instance in the process execution net and the de-jure net. The
variables ensure that transitions can only consume the same object instance
for arcs with the same variable. This refers to the original objects not the
newly created ones in the process execution net.

######  Definition 19 (Valid Binding in Synchronous Product Net)

Let
$SP_{net}=(((P_{SP},T_{SP},F_{SP},l_{SP}),pt_{SP},F_{var_{SP}}),M_{init_{SP}},M_{final_{SP}},\nu)$
be the synchronous product net. Let $SP_{net\setminus\nu}$ be the synchronous
product net without $\nu$. A binding sequence
$\sigma=\langle(t_{1},b_{2}),...,(t_{n},b_{n})\rangle\in B^{*}$ is valid for
$SP_{net}$ if it is valid for $SP_{net\setminus\nu}$ and for every
$(t_{i},b_{i})\in\sigma$ with $t_{i}\in T_{sny}$ that is connected to an arc
with a variable assigned by $\nu$ it holds that arcs with the same variable
consume the same object:
$\forall_{p_{DJ}\in P_{DJ},p_{PX}\in
P_{PX},\\{p_{DJ},p_{PX}\\}\subseteq\bullet(t_{i})}(\nu((p_{PX},t_{i}))=\nu((p_{DJ},t_{i}))\Rightarrow\\{orob(o)|o\in
b_{i}(pt((p_{PX},t_{i})))\\}\cap b(pt((p_{DJ},t_{i})))\neq\emptyset)$.

The resulting synchronous Petri net for the running example can be seen in
Figure 8.

##  6 Alignments from Synchronous Product Net

This section describes the second part of our approach to finding object-
centric alignments. As an input for this part, we have a synchronous product
net in which every transition relates to a move of an alignment. All binding
sequences from the initial marking to the final marking in the synchronous
product net relate to an alignment. In this section, we now want to find an
optimal alignment given a cost function for moves. Every binding in the
synchronous product net directly relates to a move. A binding defines the
transition and the used objects. As described in Section 5 the transitions
already describe the type of move with $(\gg,t)$ being a model move, $(t,\gg)$
being a log move, and $(t_{PX},t_{DJ})$ being a synchronous move. The activity
is also defined by the transition from the binding. The objects used in the
binding are the objects of the move.

Therefore, searching for an optimal alignment relates to searching for an
optimal binding sequence from the initial to the final marking of the
synchronous product net. Interpreting markings as nodes and bindings as edges
between markings, we can set up the search space as a graph. The cost of the
edges is then the given cost function applied to the move that relates to the
binding. This is a well-defined search problem we can solve with standard
search algorithms for finding the cheapest or shortest path in a graph.

######  Definition 20 (Weighted State Space Graph)

Let
$SP_{net}=(((P_{SP},T_{SP},F_{SP},l_{SP}),pt_{SP},F_{var_{SP}}),M_{init_{SP}},M_{final_{SP}},\nu)$
be a synchronous product net. Let $B_{SP}$ be all possible bindings in
$SP_{net}$. The weighted search space graph for that Petri net is
$G_{wg}=(V_{wg},E_{wg},w_{wg})$ with
$V_{wg}\subseteq\mathcal{B}(\mathcal{Q}_{ON_{SP}})$,
$E_{wg}\subseteq\mathcal{B}(\mathcal{Q}_{ON_{SP}})\times\mathcal{B}(\mathcal{Q}_{ON_{SP}})$
and $w_{wg}:E_{wg}\to\mathbb{R}$ such that:

  * •

$V_{wg}=\\{M\in\mathcal{B}(\mathcal{Q}_{ON_{SP}})|\exists_{\sigma\in
B_{SP}^{*}}M_{init_{SP}}\xrightarrow{\text{$\sigma$}}M\\}$ is the set of all
reachable markings in the synchronous product net.

  * •

$E_{wg}=\\{(M,M^{\prime})\in\mathcal{B}(\mathcal{Q}_{ON_{SP}})\times\mathcal{B}(\mathcal{Q}_{ON_{SP}})|\exists_{(t,b)\
inB_{SP}}M\xrightarrow{\text{$(t,b)$}}M^{\prime}\\}$ connects each marking to
its directly reachable markings.

  * •

$w_{wg}(M,M^{\prime})=cost_{move}(a_{log},o_{log},t_{model},o_{model})$ where
$(t,b)\in B_{SP}$ with $M\xrightarrow{\text{$(t,b)$}}M^{\prime}$ and
$t=(t_{PX},t_{DJ})\in T_{SP}$ so that:

    * –

$a_{log}=l_{SP}(t_{PX})$; $t_{model}=t_{DJ}$

    * –

$o_{log}=range(b)$ if $a_{log}\neq\gg$ else $o_{log}=\emptyset$

    * –

$o_{model}=range(b)$ if $a_{model}\neq\gg$ else $o_{model}=\emptyset$

###### Theorem 6.1

Let $P_{X}$ be a process execution with a finite number of objects and events
and a let
$DJ_{net}=(((P_{DJ},T_{DJ},F_{DJ},l_{DJ}),pt_{DJ},F_{var_{DJ}}=\emptyset),M_{init_{DJ}},\allowbreak
M_{final_{DJ}})$ be a de-jure net with a finite number of reachable markings
from the initial marking. The synchronous product net $SP_{net}$ for $P_{X}$
and $DJ_{net}$ has a finite number of reachable markings.

######  Proof (Finite Search Space)

Let $P_{X}=(E_{X},D_{X})$ be a process execution with a finite number of
objects $o=|X|$ and events $e=|E_{X}|$. Let
$DJ_{net}=(((P_{DJ},T_{DJ},\allowbreak F_{DJ},l_{DJ}),pt_{DJ},\allowbreak
F_{var_{DJ}}=\emptyset),M_{init_{DJ}},M_{final_{DJ}})$ be a de-jure model for
the process execution with a finite number of reachable markings
$m_{DJ}=|\\{M|\exists_{\sigma\in B_{DJ}^{*}}\allowbreak
M_{init_{DJ}(PX)}\xrightarrow{\text{$\sigma$}}M\\}|$ with $B_{DJ}$ being the
set of possible bindings in $DJ_{net}$.

Step 1 of our method creates the process execution net
$PX_{net}=(((P_{PX},T_{PX},\allowbreak F_{PX},l_{PX}),\allowbreak
pt_{PX},\allowbreak F_{var_{PX}}),M_{init_{PX}},\allowbreak M_{final_{PX}})$
from the process execution. Let $B_{PX}$ be the set of all bindings in
$PX_{net}$. At most one place is added per event for each object together with
one additional start place for each object. Since the number of events and
objects is finite the number of places in $PX_{net}$ is finite. Each
transition produces as many tokens as it consumes because it is connected to
one output place for each input place. So the number of tokens stays
consistent all the time. Therefore, the number of reachable markings
$m_{PX}=|\\{M|\exists_{\sigma\in
B_{PX}^{*}}M_{init_{PX}}\xrightarrow{\text{$\sigma$}}M\\}|\leq(e+1)^{o}$ in
$PX_{net}$ is finite.

Step 2 of our method preprocesses $DJ_{net}$. Thereby, no places are added.
Transitions with variable arcs are replaced by a set of transitions that can
only reach markings the original transition was able to reach as well. Thus,
the number of reachable markings stays the same and is therefore finite.

In Step 3, $DJ_{net}$ and $PX_{net}$ are merged together to form the
synchronous product net. No places are added and the synchronous transitions
that are added, do not add new reachable markings because there always exists
one transition from $DJ_{net}$ and one from $PX_{net}$ that together have the
same effect on the markings of the net. Therefore, the number of markings in
the synchronous product net $SP_{net}$ for $P_{X}$ and the preprocessed
$DJ_{net}$ is the product of the two nets: $m_{SP}=|\\{M|\exists_{\sigma\in
B_{SP}^{*}}M_{init_{SP}}\xrightarrow{\text{$\sigma$}}M\\}|=m_{DJ}*m_{PX}$ with
$B_{SP}$ being the set of all possible bindings in $SP_{net}$. Since $m_{DJ}$
and $m_{PX}$ are finite, the synchronous product net has a finite number of
reachable markings.

As stated in Theorem 6.1 and shown in the finite search space proof, the
weighted search space graph is finite given that the event log and the de-jure
model have a finite size. For a finite weighted graph, it is decidable whether
a cheapest path exists, and if one exists, algorithms like the Dijkstra
algorithm [14] can find them. The only case in which there is no cheapest path
is when there is no path at all. This means that the synchronous product net
cannot reach the final state from the initial state. This can only occur if
the de-jure model has no option to complete for the set of objects of the
process execution. In other words, the de-jure model does not contain any
allowed behavior related to the process execution. In this case, there can be
no alignment and the user is informed that the de-jure model does not match
the process execution. This is similar to traditional alignments with a de-
jure model that has no option to complete. In the normal case where the de-
jure model describes behavior related to the given process execution, an
optimal alignment is determined with the help of the shortest path.

The resulting shortest path is a binding sequence from the initial to the
final marking. It relates directly to an object-centric alignment for the
given process execution and the de-jure model. Using the synchronous product
net in Figure 8 the search for an optimal alignment results in the alignment
in Figure 5. Thereby respecting the inter-object dependencies between package
and item. Also, object instances are correctly separated by the $\nu$-net
requirements, so that deviations of different object instances can not
compensate another. That can be seen in Figure 5 where the missing add sample
activity for i1 and the additional add sample activity for i2 are both
identified as deviations.

There can be multiple binding sequences with the same cost. It is guaranteed
that one of the cheapest is found, but if there are multiple binding sequences
with the same cost, it depends on the implementation which one is found.

##  7 Evaluation

We conducted an evaluation with real-world data from the BPI2017 challenge
[17]. The evaluation is split into a qualitative part and a quantitative
evaluation of the run time.

###  7.1 Qualitative

The purpose of the qualitative evaluation is to evaluate whether the proposed
approach does indeed give better insights into complex processes than existing
approaches. In the following, we will compare the presented object-centric
alignment approach to traditional alignments [8] on a flattened event log [4].

We used data from BPI2017 [17] for our real-world evaluation. It is one of the
few publicly available event logs that can be turned into an object-centric
event log. The two object types of that process are application and offer. All
variants have exactly one application and at least one offer. An application
can be canceled or an offer is accepted.

For this evaluation, we selected only the 4 most dominant variants that made
up 19.6% of process executions. For simplicity and clarity, we removed the
activities Submit, Complete, and Accept because they only appear in the
beginning before the processes for application and offer interact. We
discovered the de-jure Petri net from those 4 variants using the python
library ocpa [6] which implements the discovery approach from van der Aalst
and Berti [4]. The implementation of our approach also uses ocpa [6]. In the
next step, we introduced noise in the log by removing and replacing events in
the given process execution.

Figure 9: A process execution from [17] and a variation of it that has some
noise.

The original accepted process execution and the process execution with noise
can be seen in Figure 9. In this example, the activity Cancel application is
removed from the application trace, as well as the activity Cancel offer.
Instead of Cancel offer the activity Accept offer was recorded for application
1. In the trace of offer 1, nothing was changed. An error like that could be
introduced to a real process by human mistakes. The change created multiple
deviations from the wanted behavior described by the de-jure model. For
example, it is not possible to accept an application without accepting an
offer. This is an inter-object dependency we would want alignments to detect.
Also, the events Cancel application and Cancel offer are now only recorded for
an offer but are not connected with an application. Therefore, this represents
unwanted behavior as well.

We applied the traditional alignment approach [8] after flattening [4] the
object-centric process execution and the object-centric Petri net. This
results in the two alignments. We also applied our object-centric alignment
approach to the described evaluation data. Both the traditional and object-
centric alignment can be seen in Figure 10.

Figure 10: Traditional and object-centric alignments for the variant with
noise and the evaluation de-jure model.

Comparing those two, we can see big differences in the diagnostics. The
biggest difference is that the traditional alignment did not detect that
application 1 should not have been accepted. The reason for that is that with
the traditional approach, the alignment for application 1 is computed without
any knowledge about any offers. Therefore, it has to assume that activity
Accept Offer was a valid activity, where instead there was no matching offer
to accept. This missing information leads to the traditional alignment
suggesting that activities Validate and Pending are missing in the log,
further supporting the understanding that this application should have been
accepted. Our approach considers all dependencies between objects and
therefore identifies Accept offer as a log move. Moreover, the traditional
alignment does not indicate any control flow deviation for offer 1. This
creates a contradiction between the alignment of offer 1 and application 1
because an application can not be accepted and canceled. Contradictions like
that can not occur in an object-centric alignment because the whole process
execution is considered at once.

###  7.2 Quantitative

To evaluate the scalability of our approach, we performed a quantitative
analysis of the run time.

####  7.2.1 Evaluation Setup

As the data source we used BPI2017 event data [17]. Only the most frequent 50%
of activities were used. All other activities were filtered out. Afterward,
the log consisted of 755 variants. We used a Petri net designed so that the
given log contains some dis-aligned process executions. The used Petri net is
available on GitHub11footnotemark: 1. It has 6 visible transitions and 4
silent transitions. There are 10 places in the net. We aligned all the 755
variants with the model and tracked their properties and the resulting
alignment calculation time. The raw results of that evaluation can be found at
GitHub11footnotemark: 1. The evaluation was performed on a 3.1 GHz Dual Core
Intel Core i5 with 8GB of RAM.

Figure 11: Execution time on a logarithmic scale over the number of events.

####  7.2.2 Results

Within the 755 calculated alignments, the cost varied from 0 to a maximum of
5. The number of events spanned 3 events up to 20 events with the majority of
process execution having 11 to 14 events. The object instances involved
started with 2 and went up to 7 instances. The distribution of these
attributes can be seen in Figure 11, Figure 12, and Figure 13. The shortest
calculation time was 0.007 seconds and the longest was 1051.8 seconds. One can
see that near the limits of the value range for all attributes, there are
fewer data points, which makes the results for these values less resistant to
outliers. We computed the correlation coefficient for each pair of attributes.
The number of events and the number of objects show a positive correlation of
0.59 whereas the number of events and the cost show a negative correlation of
-0.38. Especially the latter one is surprising because one would expect more
deviations and therefore a higher cost for process variants with more events.

We plotted the calculation time over the three dimensions number of events
(Figure 11), number of objects (Figure 12), and cost (Figure 13). To reduce
the effect of the negative correlation, we grouped the data points in Figure
13 by their number of events. Note that the time scale for the time is
logarithmic in all three plots and, therefore, the linear increase represents
exponential growth. For all three dimensions, the calculation time grows
exponentially.

Figure 12: Execution time on a logarithmic scale over the number of objects.
Figure 13: Execution time on a logarithmic scale over alignment cost, grouped
by the number of events.

This result can be explained by the structure of the search space. More events
increase the size of the process execution net and can also increase the
number of synchronous transitions in the synchronous product net. Thus there
are more possible markings which leads to a bigger search space. More objects
also increase the size of the process execution net and add a lot of parallel
behavior, thereby also increasing the search space. The run time of the
Dijkstra algorithm is on average exponential in the size of the search space
[16]. Therefore, the computation time grows exponentially for the number of
events and objects. For an alignment with a higher cost, a bigger portion of
the search space is explored because Dijkstra explores all vertices that are
reachable by a path that is cheaper than the cheapest path to the final
marking. As a result, the run-time grows exponentially for the cost of the
alignment.

##  8 Conclusion

This paper presented four contributions for conformance checking in object-
centric process mining. First, we defined object-centric alignments
generalizing traditional alignments to graphs of moves. Second, we provided an
algorithm to calculate optimal alignments on an object-centric log and Petri
net. The two-step approach creates a synchronous product net and searches for
the optimal binding sequence from initial marking to final marking. Third, we
implemented this algorithm using the open-source library ocpa [6] and made it
publicly available on GitHub11footnotemark: 1. Finally, we performed an
evaluation of the presented approach. The qualitative evaluation shows the
advantages of object-centric alignments for deviation diagnostics. Complex
inter-object dependencies are lost when flattening the event data, leading to
contradictions in the alignment. Using object-centric alignments, we preserve
these dependencies and avoid contradictions. Our quantitative evaluation
indicates an exponential computation time in the number of object instances
and cost of the alignment. This suggests, that an alignment of a whole object-
centric event log to a moderately fitting model might be too time-consuming.
In those scenarios, one might use object-centric alignments to get specific
diagnostics for individual process executions or variants.

There are two directions for future work based on object-centric alignments.
On the one hand, one can investigate lifting restrictions of the current
approach. For example, the assumption of a fixed object set could be dropped,
allowing for the approach to introduce completely new objects that might be
missing. On the other hand, one can work towards decreasing the complexity and
run time: Heuristics, using the $A^{*}$ algorithm, and defining relaxations of
the problem are all promising directions to decrease the computation time.

## References

  * [1] van der Aalst, W.M.: Process mining. Communications of the ACM 55(8), 76–83 (2012). https://doi.org/10.1145/2240236.2240257
  * [2] van der Aalst, W.M.: Object-Centric Process Mining: Dealing with Divergence and Convergence in Event Data. In: Software Engineering and Formal Methods. pp. 3–25. Springer (2019). https://doi.org/10.1007/978-3-030-30446-1_1
  * [3] van der Aalst, W.M., Adriansyah, A., van Dongen, B.: Causal Nets: A Modeling Language Tailored towards Process Discovery. In: CONCUR 2011 – Concurrency Theory, vol. 6901, pp. 28–42. Springer (2011). https://doi.org/10.1007/978-3-642-23217-6_3
  * [4] van der Aalst, W.M., Berti, A.: Discovering object-centric petri nets. Fundam. Informaticae 175(1-4), 1–40 (2020). https://doi.org/10.3233/FI-2020-1946
  * [5] Adams, J.N., van der Aalst, W.M.: Precision and Fitness in Object-Centric Process Mining. In: 2021 3rd International Conference on Process Mining (ICPM). pp. 128–135. IEEE (2021). https://doi.org/10.1109/ICPM53251.2021.9576886
  * [6] Adams, J.N., Park, G., van der Aalst, W.M.: ocpa: A Python library for object-centric process analysis. Software Impacts 14, 100438 (2022). https://doi.org/10.1016/j.simpa.2022.100438
  * [7] Adams, J.N., Schuster, D., Schmitz, S., Schuh, G., van der Aalst, W.M.: Defining Cases and Variants for Object-Centric Event Data. In: 2022 4th International Conference on Process Mining (ICPM). pp. 128–135. IEEE (2022). https://doi.org/10.1109/ICPM57379.2022.9980730
  * [8] Adriansyah, A.: Aligning observed and modeled behavior (2014). https://doi.org/10.6100/IR770080, publisher: Technische Universiteit Eindhoven
  * [9] Adriansyah, A., Munoz-Gama, J., Carmona, J., van Dongen, B.F., van der Aalst, W.M.: Alignment Based Precision Checking. In: Business Process Management Workshops. pp. 137–149. Springer (2013). https://doi.org/10.1007/978-3-642-36285-9_15
  * [10] Adriansyah, A., Sidorova, N., van Dongen, B.: Cost-Based Fitness in Conformance Checking. In: 2011 Eleventh International Conference on Application of Concurrency to System Design. pp. 57–66 (2011). https://doi.org/10.1109/ACSD.2011.19
  * [11] Borrego, D., Barba, I.: Conformance checking and diagnosis for declarative business process models in data-aware scenarios. Expert Systems with Applications 41(11), 5340–5352 (2014). https://doi.org/10.1016/j.eswa.2014.03.010
  * [12] Burattin, A., Maggi, F.M., Sperduti, A.: Conformance checking based on multi-perspective declarative process models. Expert Systems with Applications 65(C), 194–211 (2016). https://doi.org/10.1016/j.eswa.2016.08.040
  * [13] Carmona, J., van Dongen, B., Solti, A., Weidlich, M.: Conformance Checking: Relating Processes and Models. Springer (2018). https://doi.org/10.1007/978-3-319-99414-7
  * [14] Dechter, R., Pearl, J.: Generalized best-first search strategies and the optimality of A*. Journal of the ACM 32(3), 505–536 (1985). https://doi.org/10.1145/3828.3830
  * [15] Desel, J., Reisig, W.: Place/transition Petri Nets. In: Lectures on Petri Nets I: Basic Models, pp. 122–173. Springer (1998). https://doi.org/10.1007/3-540-65306-6_15
  * [16] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1(1), 269–271 (1959). https://doi.org/10.1007/BF01386390
  * [17] van Dongen, B.: BPI Challenge 2017 (2017). https://doi.org/10.4121/UUID:5F3067DF-F10B-45DA-B98B-86AE4C7A310B
  * [18] van Dongen, B.F.: Efficiently computing alignments - using the extended marking equation. In: Business Process Management - 16th International Conference, BPM 2018. pp. 197–214. Springer (2018). https://doi.org/10.1007/978-3-319-98648-7_12
  * [19] Dunzer, S., Stierle, M., Matzner, M., Baier, S.: Conformance checking: a state-of-the-art literature review. In: Proceedings of the 11th International Conference on Subject-Oriented Business Process Management. pp. 1–10. S-BPM ONE ’19, Association for Computing Machinery (2019). https://doi.org/10.1145/3329007.3329014
  * [20] Fahland, D.: Process mining over multiple behavioral dimensions with event knowledge graphs. In: Process Mining Handbook, pp. 274–319. Springer (2022). https://doi.org/10.1007/978-3-031-08848-3_9
  * [21] Felli, P., Gianola, A., Montali, M., Rivkin, A., Winkler, S.: Cocomot: Conformance checking of multi-perspective processes via SMT. In: Polyvyanyy, A., Wynn, M.T., Looy, A.V., Reichert, M. (eds.) Business Process Management - 19th International Conference, BPM 2021, Rome, Italy, September 06-10, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12875, pp. 217–234. Springer (2021). https://doi.org/10.1007/978-3-030-85469-0_15
  * [22] Jensen, K., Kristensen, L.M.: Colored petri nets: a graphical language for formal modeling and validation of concurrent systems. Commun. ACM 58(6), 61–70 (2015). https://doi.org/10.1145/2663340
  * [23] de Leoni, M., van der Aalst, W.M., van Dongen, B.F.: Data- and resource-aware conformance checking of business processes. In: Business Information Systems \- 15th International Conference, BIS 2012. pp. 48–59. Springer (2012). https://doi.org/10.1007/978-3-642-30359-3_5
  * [24] Nesterov, R., Bernardinello, L., Lomazova, I., Pomello, L.: Discovering architecture-aware and sound process models of multi-agent systems: a compositional approach. Software and Systems Modeling (May 2022). https://doi.org/10.1007/s10270-022-01008-x
  * [25] Rozinat, A., van der Aalst, W.M.: Conformance checking of processes based on monitoring real behavior. Information Systems 33(1), 64–95 (2008). https://doi.org/10.1016/j.is.2007.07.001
  * [26] Sommers, D., Sidorova, N., van Dongen, B.: Aligning Event Logs to Resource-Constrained $\nu$-Petri Nets. In: Application and Theory of Petri Nets and Concurrency, pp. 325–345. Springer (2022). https://doi.org/10.1007/978-3-031-06653-5_17
  * [27] Song, W., Xia, X., Jacobsen, H.A., Zhang, P., Hu, H.: Efficient Alignment Between Event Logs and Process Models. IEEE Transactions on Services Computing 10(1), 136–149 (2017). https://doi.org/10.1109/TSC.2016.2601094


Manuscript submitted to ACM Manuscript submitted to ACM

# Understanding Twitter Engagement with a Click-Through Rate-based Method

Andrea Fiandro<EMAIL_ADDRESS>0000-0001-8784-2574 FITEC srlVia Goito
51/AGrugliascoItaly10095 ,  Jeanpierre Francois<EMAIL_ADDRESS>,
Isabeau Oliveri<EMAIL_ADDRESS>0000-0001-5985-3583 Politecnico di
TorinoCorso Duca degli Abruzzi, 24TurinItaly10129 ,  Simone Leonardi
<EMAIL_ADDRESS>0000-0002-8009-1082 Politecnico di TorinoCorso Duca
degli Abruzzi, 24TurinItaly10129 ,  Matteo A. Senese
<EMAIL_ADDRESS>0000-0003-4252-7612 LINKS FoundationVia
Boggio, 61TurinItaly10138 ,  Giorgio Crepaldi<EMAIL_ADDRESS>0000-1234-5678-9012 Istituto Italiano di TecnologiaP.O. Box
1212GenovaItaly43017-6221 ,  Alberto Benincasa
<EMAIL_ADDRESS>0000-0001-6470-2835 LINKS FoundationVia
Boggio, 61TurinItaly10138 and  Giuseppe Rizzo
<EMAIL_ADDRESS>0000-0003-0083-813X LINKS FoundationVia
Boggio, 61TurinItaly10138

###### Abstract.

This paper presents the POLINKS solution to the RecSys Challenge
2020111http://www.recsyschallenge.com/2020/ that ranked 6th in the final
leaderboard.222https://github.com/andreafiandro/recsys2020/ We analyze the
performance of our solution that utilizes the click-through rate value to
address the challenge task, we compare it with a gradient boosting model, and
we report the quality indicators utilized for computing the final leaderboard.

Recommender systems, Twitter, Engagement, Interaction classification

††copyright: none††ccs: Information systems Recommender systems

##  1\. Introduction

Twitter is a valuable data source for many research topics due to the richness
of data it provides and the developed and recorded social interactions. The
RecSys Challenge 2020 addresses the prediction tasks of four types of user
engagements on Twitter. For privacy reasons the dataset provided in the
challenge is an artificial one: it is collected in one week span and consists
of public engagements along with pseudo negatives randomly sampled from the
public follow graph (organizersrecsys, ). The artificial estimation of pseudo
negatives along with the unbalance of the four engagement classes make the
prediction task difficult for learning methods. We present the results of our
solution implemented utilizing a method based on Click-Through Rate (CTR) on
the metrics provided by the challenge and we compare them with those obtained
with a gradient boosting learning model. We observe that our solution
outperforms the learning method by a margin on the dataset provided.

###  1.1. Dataset insights

Figure 1. The chart shows the distribution of each action in the training set.
Retweet with comment and Reply are very unbalanced, while pseudo negatives
represent a large part of the dataset. This chart refers to the official and
latest training set released.

The dataset is a collection of public interactions on tweets along with
information about their author and the user that generates the engagement.
This dataset has an uneven class distribution. As illustrated in Figure 1,
class unbalance in the training set makes the classification process difficult
in both validation and test sets. This condition is further stressed in the
modality by which pseudo-negative features are obtained as described in
(organizersrecsys, ). In that work, authors explain the difficulties in
including pseudo-negatives, samples that represent interactions with no
engagement. However, the collection of this data hides the reason why a user
did not interact with a tweet. In fact, a user could not interact willingly or
because he did not see the tweet at all. This implies that a binary classifier
is potentially misled in considering negative class candidates. Additionally,
users’ past history absence leads to the avoidance of user-based and
personalized recommendation algorithms. The lack of user historical data is
presented in the histogram in Figure 2 that highlights how the majority of
users interact at most with less than three tweets.

Figure 2. The histogram in figure represents the amount of tweets for which a
user appears in the challenge dataset as content consumer. The horizontal axis
represents how many tweets are paired with a unique user, while the vertical
axis shows how many users have that number of interactions (both positive or
negative).

###  1.2. Proposed metrics

The organizers of the RecSys Challenge 2020 proposed two different metrics to
evaluate the solutions:

PRAUC:

(Precision Recall Area Under the Curve)

RCE:

(Relative Cross Entropy)

The PRAUC is useful to deal with unbalanced classes like Retweet with comment
and Reply. These classes have numerous rows with null values. This condition
means that no action is performed. The final ranking is computed in different
steps:

  * •

Averaging the PRAUC score across the four engagements

  * •

Averaging the RCE score across the four engagements

  * •

Compute the ranking for both metrics

  * •

Sum the two obtained ranking

As we have observed in our experimental results, this way of computing the
score favors solutions with a good score on the least competitive metric
rankings.

##  2\. Our solution

For the final submission, we propose two solutions that we assess in terms of
performance score as observed as results on the evaluation set. In particular
we submit: a CTR (Click-Through Rate-based) method and a gradient boosting
model. This choice is supported by the following logical reasoning: the
gradient boosting model performs very well on our local test set but it has a
significant worsening on the public leaderboard measured on the evaluation
set. On the other hand, the CTR method behaves almost in the same way on both
sets. This method used an optimized constant that is exactly the CTR value for
each class. We report them in detail in the two following sections.

###  2.1. Click-Through Rate-based method

We estimate which constant value has the best outcome on both PRAUC and RCE to
get a better understanding of the evaluation metrics.

The result of this investigation generates two different outcomes:

  * •

PRAUC: any constant produces the same effect in terms of score.

  * •

RCE: has different outcomes depending on the engagement’s type.

The best result, as pointed out by the way this metric is calculated, is given
by a Click-Through Rate specific for the type of engagement. The CTR
represents the ratio of positive engagements to the number of times a tweet
has been viewed. This value is calculated, on the training set, in different
steps:

  * •

Count the number of positive engagements for each class: an engagement is
considered positive if the timestamp of the interactions between a user and a
tweet is not null.

  * •

Count the total number of rows of the training set: this includes the four
types of engagement along with pseudo-negatives.

  * •

The CTR is calculated with the following equation depending on the class c:

(1) $CTR=\frac{engagement_{c}}{N_{rows}}$

In Equation 1, c represents one of the four engagements to predict: Like,
Retweet, Reply, Retweet with comment. The CTR numerical values are pointed out
in the Table 1.

| Like | Reply | Retweet | Retweet with comment
---|---|---|---|---
CTR | 0.428 | 0.025 | 0.108 | 0.007
Table 1. CTR values calculated on the training set: the class with the highest
ratio is the Like that is intuitively the most frequent.

The optimum value is found, for both RCE and PRAUC, comparing the results of
different constant value on the training set. The optimum value is the CTR in
each class. The CTR scores are computed as illustrated in Figure 4 where the
sum of existing engagements per class (timestamp exists) over the total
existing interaction per class (timestamp exists or it is a null value)
represents the related CTR value. The score is an average of the performance
obtained over different chunks of the dataset. RCE and PRAUC for the four
different classes of engagement are listed in Table 2. The second line reports
the scores obtained with a random constant that is used as baseline. As shown
by the other rows in Table 2 when the constant values increase its absolute
distance from the CTR value, RCE decreases in all the four classes.

| RCE | PRAUC
---|---|---
| Like | Reply | Retweet |  Retweet with comment | Like | Reply | Retweet |  Retweet with comment
CTR | -0.01 | -0.002 | -0.003 | -0.001 | 0.72 | 0.51 | 0.554 | 0.503
Random | -46.09 | -739.49 | -189.84 | -2219.446 | 0.43 | 0.03 | 0.109 | 0.007
0 | -2091.49 | -642.44 | -994.003 | -483.57 | 0.72 | 0.51 | 0.554 | 0.503
0.1 | -54.81 | -35.68 | -0.135 | -181.54 | 0.72 | 0.51 | 0.554 | 0.503
0.3 | -5.87 | -217.64 | -30.219 | -741.73 | 0.72 | 0.51 | 0.554 | 0.503
0.5 | -1.26449 | -481.89 | -100.908 | -1507.97 | 0.72 | 0.51 | 0.554 | 0.503
1 | -2754.47 | -28153.38 | -8817.25 | -79441.8 | 0.72 | 0.51 | 0.554 | 0.503
Table 2. Evaluation of different constants averaged across distinct portions
of the training set: the CTR outperforms all the other numbers on RCE, while
the PRAUC behaves in the same way with all the numbers provided.

This constant value was tested on different partitions of the full training
set to assess the validity of the approach. Each partition contains 16 million
rows to make them similar to the size of the challenge’s validation and test
set. This number has always the same performance in terms of RCE and PRAUC
throughout the different time’s spans, as highlighted in Figure 3.

Figure 3. The two charts describe the score obtained by the CTR constant over
different time spans: the PRAUC has always the exact same value for each type
of engagement and the RCE has almost the same score as well. Figure 4.
Overview of the model based on the CTR constant: the first step is to compute
the number of actions of each type, then the constant is calculated, with a
different value for each class.

###  2.2. Gradient boosting

The gradient boosting approach is implemented using the XGBoost (xgboost, )
library and includes four different models, one for each engagement to
predict. The input of this model is enriched with 59 features that are
reported in the following section.

####  2.2.1. Feature engineering

59 additional features were derived from the dataset provided by the challenge
organizers, in strict adherence with the terms and conditions of the
challenge. These additional features are grouped in different categories to
facilitate their understanding:

Dataset features (12 features): given directly by the dataset, they are
exploited with little or no adjustments. Examples of these features are the
number of hashtags, the language of the tweet and the number of followers.

Author features (18 features): this group profiles each tweet author included
in the training set. They are pre-computed features detailing the behaviour of
each author during the history documented by the dataset. The most relevant
features belonging to this category are:

  * •

Author engagement ratio: $\frac{N_{eng_{c}}}{N_{tweet}}$ where $N_{eng_{c}}$
represents the number of actions of a particular type of engagement c, where c
is one among Like, Retweet, Reply, Retweet with comment, received by a
specific tweet author. Instead, the denominator $N_{tweet}$ refers to the
total number of tweets published by him. In the end, there are four author
engagement ratio, one per engagement type.

  * •

Number of received engagement: expresses the total number of interactions
received by the user for each type of engagement.

User features (18 features): similar to the one applied for the authors but
with the involvement of the person interacting with the tweet. In this group,
we find statistical features such as the engagement ratio and the number of
actions for each type, calculated from the user point of view.

Languages spoken (1 feature): the main intuition behind this feature is that
understanding the language of a tweet plays a key role for a user in having
possible interactions. This approach includes the pre-computation of a file
containing, for each user id, the number of times that a specific user has
interacted with a tweet written in a specific language. The goal of this
computation is to identify, for each user $U_{id}$, a list of languages spoken
by that specific user. In more formal terms:

(2) $f(U_{id},Lang_{id})=n_{LT}$

where $Lang_{id}$ is the id of a language and $n_{LT}$ is the number of tweets
written in that language engaged by the user.

Previous actions (4 features): another pre-computation is performed to
reconstruct the history of previous interactions. This set of features are
formalized with the following function:

(3) $f(U_{id},A_{id},c)=n_{PA}$

where:

$U_{id}$:

is the user id

$A_{id}$:

is the author id

$c$:

is the class representing the engagement type

$n_{PA}$:

is the number of previous actions for the triplet $(U_{id},A_{id},c)$

Word search (6 features) This class of features is the only one referring to
the text of the tweet. We extract some meaningful words from the text tokens
and generate a boolean variable to identify when that specific word is
included in the text of the tweet. The words used are related to the call to
action, a situation when the tweet author invites his followers to do a
specific action with respect to the tweet. The considered words are share,
retweet, reply, comment.

##  3\. Submission

###  3.1. Click-Through Rate-based

This submission was performed using the value of the CTR calculated on the
whole training set. The intuition behind this approach was that, if the
distribution of positive actions with respect to the negative ones does not
change too much, we can achieve a score that outperforms several proposed
models including the gradient boosting model.

###  3.2. Gradient Boosting

The final model includes almost sixty different features. The early stopping
feature of the XGBoost library was used to avoid overfitting. After each
training round the model is evaluated on a validation set using the RCE metric
and if there is no improvement with respect to the last N round the training
is stopped.

The four models were trained on the final release of the dataset with the
parameters in Table 3.

Parameter | Value | Parameter | Value | Parameter | Value
---|---|---|---|---|---
eta | 0.09 | tree_method | gpu_hist | sampling_method | gradient_based
subsample | 0.2 | objective | binary:logistic | max_depth | 5
max_delta_step | 5 | epochs | 200 | early_stopping_rounds | 10
Table 3. XGBoost parameters used by the four different models during the
training phase.

###  3.3. Results

The optimized constant based model achieves better results when compared to
those obtained with gradient boosting. The results are reported in Table 4.
The reason why a constant-based method performs better than a gradient boosted
one is due to the way score and ranking are computed in the RecSys Challenge
2020. As presented by the winning team of the challenge, a very computational
heavy, more complex and deeply parallel boosting model is able to explore each
row in the dataset characteristics, while our fine tuned XGBoost on a subset
of the dataset does not. In this way, an optimized constant is able to
generalize better the classification procedure avoiding overfitting with
respect to the gradient boosted one as described both in Figure 3 and in Table
4.

|  | Retweet | Reply | Like | RwC
---|---|---|---|---|---
Model | Dataset | PRAUC | RCE | PRAUC | RCE | PRAUC | RCE | PRAUC | RCE
CTR-based |  Final Leaderboard (Test set) | 0.5516 | -0.03 | 0.5135 | -0.05 | 0.7131 | 0 | 0.5037 | 0
Public Leaderboard (Validation set) | 0.5516 | -0.0315 | 0.5135 | -0.0476 | 0.7133 | -0.0008 | 0.5037 | -0.0045
Local test set | 0.72 | -0.01 | 0.51 | -0.002 | 0.554 | -0.003 | 0.503 | -0.001
XGBoost |  Public Leaderboard (Validation set) | 0.41 | 6.68 | 0.10 | -3.23 | 0.66 | -32.01 | 0.04 | -1.67
Local test set | 0.710 | 46.85 | 0.626 | 35.24 | 0.830 | 32.56 | 0.586 | -8.916
Table 4. Results of the two described models in different contexts: while the
CTR constant maintains almost the same score, the XGBoost model loses
efficiency when the time difference with respect to the training set period
increases.

##  4\. Final Consideration

The CTR-based method addresses the issues related to the unbalanced classes
and pseudo negatives as described in Section 1. However, the literature on
recommender systems (quadrana, ; dacremadeep, ; recissues, ; netflixrec, ;
reccase, ) highlights some issues that are intrinsically related to the
problems addressed in this challenge and, therefore, observable in the dataset
provided.

Short term trends: those trends that tend to change or disappear quickly due
to the rapid evolution of individual and community preferences.

Cold start problem: when new users enter the system, the preferences of the
new users could not be predicted.

Gray sheep: problematical users that cannot be traced or predictably aligned
to any trend, so the suggestions related to current trends are not an
effective solution.

Real-time analysis: real-time data have to be collected to perform analysis
for unexpected events (e.g., earthquakes, pandemics) and a continuous update
of the model with real-time information.

Context-Awareness, Privacy, and Sparsity: users’ short and long term history
and unnoticeable context-related information may not be retrieved (recissues,
). Despite the huge size of data typically collected, most users are
occasional or not inclined to interact, both for privacy issues and unwanted
exposure of information. These aspects lead to a sparse characterization
matrix, thus resulting in less accurate recommendations.

Baseline metrics: the available evaluation metrics are for general-purpose
recommender systems and are not always applicable in different domains,
especially in evaluating the context-aware ones. Metrics used in common
machine learning approaches do not always lead to well suited recommendations
(dacremadeep, ).

The constant preserves its performance among training, validation and test
set, while the XGBoost model gets worse. A model could be inefficient if it is
not able to capture time and event independent features. This, along with the
above issues, could be a probable cause of the considerable variation of the
challenge leaderboard, from the validation to the final test phase. In fact,
as reported333https://recsys-twitter.com, the entire dataset was produced in
two different weeks. Thanks to our observations over the result of the
validation set, we conclude that an optimized constant performs better. This
intuition turns out to be successful in the test phase, indeed, the POLINKS
solution ranked sixth at the end of the RecSys Challenge 2020.

###### Acknowledgements.

This research was supported by FITEC S.r.l., LINKS Foundation, Politecnico di
Torino and Istituto Italiano di Tecnologia. Computational resources were
provided by HPC@POLITO444http://www.hpc.polito.it, a project of Academic
Computing within the Department of Control and Computer Engineering at the
Politecnico di Torino.

## References

  * (1) Quadrana, Massimo and Cremonesi, Paolo and Jannach, Dietmar, Sequence-Aware Recommender Systems, September 2018, Association for Computing Machinery, New York, NY, USA, 51, 4, 0360-0300, https://doi.org/10.1145/3190616, 10.1145/3190616, ACM Comput. Surv., jul, 66, 36.
  * (2) Dacrema, M. F.; Cremonesi, P. and Jannach, D. Are We Really Making Much Progress? A Worrying Analysis of Recent Neural Recommendation Approaches Proceedings of the 13th ACM Conference on Recommender Systems, Association for Computing Machinery, 2019, 101–109
  * (3) Belli, L.; Ktena, S. I.; Tejani, A.; Yut-Fon, A. L.; Portman, F.; Zhu, X.; Xie, Y.; Gupta, A.; Bronstein, M.; Delić, A.; Sottocornola, G.; Anelli, W.; Andrade, N.; Smith, J. and Shi, W. Privacy-Preserving Recommender Systems Challenge on Twitter’s Home Timeline 2020
  * (4) Khusro, S.; Ali, Z. and Ullah, I. Kim, K. J. and Joukov, N. (Eds.) Recommender Systems: Issues, Challenges, and Research Opportunities Information Science and Applications (ICISA) 2016, Springer Singapore, 2016, 1179-1189
  * (5) Gomez-Uribe, C. A. and Hunt, N. The Netflix Recommender System: Algorithms, Business Value, and Innovation ACM Trans. Manage. Inf. Syst., Association for Computing Machinery, 2016, 6
  * (6) Jannach, D. and Ludewig, M. Determining Characteristics of Successful Recommendations from Log Data: A Case Study Proceedings of the Symposium on Applied Computing, Association for Computing Machinery, 2017, 1643–1648
  * (7) Chen, T. and Guestrin, C. XGBoost: A Scalable Tree Boosting System Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, 2016, 785–794