# Mining Constraints from Reference Process Models
for Detecting Best-Practice Violations in Event Logs

Adrian Rebmann<EMAIL_ADDRESS>Timotheus Kampik
<EMAIL_ADDRESS>Carl Corea<EMAIL_ADDRESS>Han van der Aa
<EMAIL_ADDRESS>University of Mannheim, B6 26, 68159 Mannheim,
Germany  SAP Signavio, Berlin, Germany  University of Koblenz, Koblenz,
Germany

(Received: September 4, 2023 )

###### Abstract

Detecting undesired process behavior is one of the main tasks of process
mining and various conformance-checking techniques have been developed to this
end. These techniques typically require a normative process model as input,
specifically designed for the processes to be analyzed. Such models are rarely
available, though, and their creation involves considerable manual effort.
However, reference process models serve as best-practice templates for
organizational processes in a plethora of domains, containing valuable
knowledge about general behavioral relations in well-engineered processes.
These general models can thus mitigate the need for dedicated models by
providing a basis to check for undesired behavior. Still, finding a perfectly
matching reference model for a real-life event log is unrealistic because
organizational needs can vary, despite similarities in process execution.
Furthermore, event logs may encompass behavior related to different reference
models, making traditional conformance checking impractical as it requires
aligning process executions to individual models. To still use reference
models for conformance checking, we propose a framework for mining declarative
best-practice constraints from a reference model collection, automatically
selecting constraints that are relevant for a given event log, and checking
for best-practice violations. We demonstrate the capability of our framework
to detect best-practice violations through an evaluation based on real-world
process model collections and event logs.

###### keywords:

Best practices , Conformance checking , Declarative process mining , Natural
language processing

††journal: Information Systems

##  1 Introduction

_Process mining_ is a discipline that analyzes event data recorded during the
execution of organizational processes, with the aim of gaining insights into
how these processes are actually running [1]. One of the main tasks of process
mining is the detection of _undesired_ process behavior, as it can reveal
compliance problems, process inefficiencies, and data quality issues. Mainly,
such undesired behavior can be detected using _conformance-checking_
techniques [2], which require a normative process model that was specifically
created for the process to be analyzed. Here, the normative process model is
compared with event data in order to reveal any deviations that might have
occurred. While such approaches are very valuable for companies, an inherent
problem is that such normative process models are rarely available in
organizations and require time-consuming and costly efforts in their creation
[3]. Fortunately, many process types, such as procurement and invoicing
processes, are commonly organized in similar ways across organizations or—at
the very least—involve similar steps. As a consequence, _reference process
models_ have been recognized as an important means to provide depictions of
proven ways to run these processes, serving as best-practice templates for
process implementations in various domains [4, 5]. Beyond the best practices
such models capture for entire process types, they also contain important
knowledge about general behavioral relations that have to hold in these
processes, e.g., that an invoice must be checked before it is approved. The
availability of such reference process models can, thus, alleviate the need
for manually creating a customized normative model, as the former can serve as
a basis against which to check for undesired behavior in the scope of
conformance checking.

A core problem, however, is that it is generally unrealistic to find a single
reference process model that exactly fits to a given real-life process,
because, even though the general way of executing such processes may be
similar, the individual needs of organizations can vary [5]. This means that a
real-world process may be subject to additional requirements than the ones
captured in a reference model; also, some parts of a reference model may not
be applicable in a particular situation. Additionally, an event log might
capture behavior that relates to multiple reference models, e.g., related to
both procurement and invoicing. This makes traditional conformance checking
involving a singular normative model hard for companies. Therefore, in order
to leverage the best practices captured in the reference models for the
detection of undesired behavior, the alignment between these and event data
needs to be achieved in a more flexible manner, involving multiple reference
models at once. Nevertheless, it also brings additional challenges, e.g.,
identifying which reference models are relevant.

We approach this problem through the development of a framework for the
extraction of so-called _relevant_ declarative constraints [6] from a
collection of reference models. Once extracted, they can be used to check if
event logs violate best practices captured in the constraints. The constraints
we extract may stem from thousands of reference process models that capture
best-practices of a plethora of domains, depending on the model collection
used as input. Here, the main challenge is that we need to determine which
constraints are actually relevant and interesting—or even applicable—for a
given event log. We address this challenge through established techniques from
declarative process mining, as well as natural-language-processing techniques
to refine and measure the relevance of mined constraints for a given event
log. In this way, our framework can take advantage of repositories of
reference models and identify relevant best-practice constraints that can be
used for analyzing a given event log. We implement our framework and
demonstrate its capability to detect best-practice violations through an
evaluation based on real-world process model collections.

The remainder of this paper is structured as follows. Section 2 motivates the
goal of mining constraints from reference process models to check for best-
practice violations and Section 3 defines preliminaries. Section 4 presents
our framework for mining, selecting, and checking best-practice constraints,
which we evaluate in Section 5. Section 6 presents application scenarios,
where we apply our framework to real-life event data. Finally, Section 7
discusses related work and Section 8 concludes the paper.

##  2 Motivation

As a motivational example, this section illustrates the potential of checking
for best-practice violations using declarative constraints that are mined from
reference process models.

Figure 1: Exemplary reference process model in BPMN.

Recognizing best-practice violations using a reference process model. Consider
the process model in Figure 1, which shows an exemplary reference process
model of a procurement process for materials. From this model, we can extract
a variety of behavioral relations, such as: A purchase order (PO) must be
created before it is checked and, also, checked before it is approved; a PO
must not be both approved and rejected; a PO must be approved before goods are
received; and no invoice should be entered when a PO is rejected.

Now, consider a trace111Intuitively, a trace is a sequence of events that
represents a process execution. We will formalize this in Section 3. $\sigma$
that stems from an event log of a procure-to-pay process for consumer
products:

$\sigma=\langle$create order, enter goods receipt, enter invoice, check
invoice amount, make payment$\rangle$

The trace can be understood such that first an order is created, then a goods
receipt is entered, and so forth. We can use the relations extracted from the
reference process model to identify behaviors in $\sigma$ that violate best
practices. For instance, goods are received in $\sigma$ but an order was
neither checked nor approved beforehand and an invoice is entered before goods
were received. While the latter may depend on the specific organizational
context, e.g., an arrangement with a supplier would allow for entering an
invoice before goods are delivered, the former is clearly undesirable,
regardless of any specific arrangements.

The example thus shows that the reference model can be used to gain insights
on best-practice violations of the given trace, despite not stemming from
exactly the same process. In fact, some of the behavioral relations captured
in reference models can be broadly applicable. For example, the fact something
cannot be both approved and rejected applies to virtually any process in which
such approval decisions need to be made.

Combining constraints from multiple reference process models. An important
thing to recognize, though, is that, besides containing activities that relate
to materials procurement, trace $\sigma$ also contains activities that go
beyond the scope of the reference process model shown in Figure 1. In
particular, $\sigma$ also contains activities related to _checking the invoice
amount_ and _making a payment_ , which would sooner be covered by a reference
model relating to an invoicing process. Therefore, relying solely on a single
reference model may result in missing relevant best-practice violations, which
means that it is necessary to jointly check for adherence to best practices
captured in multiple reference models.

This can be achieved by turning the behavioral relations captured by
imperative process models (such as Figure 1) into declarative constraints.
This has two main benefits: first, it allows one to consider behavioral
relations from multiple reference models at the same time, while, second, it
allows one to omit parts of the imperative process model, that are not
relevant to the trace at hand, from consideration. Specifically, in the
presence of tens of thousands of constraints, we need to avoid that
constraints that are irrelevant for an event log cause the detection of
violations, i.e., _false positives_. For instance, a constraint such as “
_process goods receipt_ should precede _enter invoice_ ” (extracted from a
procurement process model) should not be applied to a sales process event log,
which does not involve goods receipt objects.

However, expecting users to manually select from tens of thousands of
constraints is unfeasible. To reduce manual effort, we need to automatically
preselect constraints based on the specific context, i.e., the given event
log. To this end, our framework mines constraints from a large collection of a
reference process models and, subsequently, selects those constraints that are
actually relevant to the particular situation at hand.

##  3 Preliminaries

We continue with preliminaries on event data, process models, and declarative
constraints.

###  3.1 Traces, Events, Event Logs

Let $\mathcal{A}$ refer to the universe of possible activities in
organizational processes and $\mathcal{R}$ to the universe of organizational
roles that can be involved in their execution. Then, a trace $\sigma$ is a
sequence that represents the execution of an organizational process. Such a
trace consists of a finite sequence of events $\sigma=\langle
e_{1},...,e_{n}\rangle$, where each event $e_{i}$ is a tuple $(a,r)$, with
$a\in\mathcal{A}$ as the activity that the event relates to and
$r\in\mathcal{R}\cup\\{\bot\\}$ as a possibly empty attribute that indicates
the role of the resource that executed this activity. Note that, in the
remainder, we commonly use dot notation to refer to components of tuples,
e.g., using $e_{i}.a$ as a shorthand to refer to the activity of an event
$e_{i}$

An event log $L$ is then a finite multi-set of traces. Given a trace $\sigma$,
we use $\sigma^{a}$ to refer to the sequence of its activities, i.e.,
$\sigma^{a}=\langle e_{1}.a,\dots,e_{n}.a\rangle$. $L^{a}$ is then the multi-
set of activity sequences obtained from all traces in $L$, i.e.,
$L^{a}=\\{\sigma^{a}\mid\sigma\in L\\}$. Finally, we use
$A_{L}\subseteq\mathcal{A}$, to denote the set of activities that the events
of the traces in $L$ relate to, and $R_{L}$ to denote the set of resource
roles executing activities in $L$.

###  3.2 Process Models and Process Model Collections

Using $\mathcal{M}$ to denote a process model collection, each process model
$M\in\mathcal{M}$ is a tuple $M=$($A$, $F$, $R$, $D$). $A$ is the set of
labeled steps in $M$, including tasks and events in a BPMN diagram or
transitions in a Petri net. Just like for events, we call $a\in
A\subseteq\mathcal{A}$ an _activity_ in the remainder. $F$ is the set of
unique finite execution sequences allowed by the model, with each $\pi\in
F=\langle a_{1},...,a_{n}\rangle$ as a sequence of activities in $A$. Focusing
on finite traces captures the intuition that each process execution is
expected to complete in a finite number of steps [6]. $R\subseteq\mathcal{R}$
is a set of roles involved in the process represented by $M$ and, finally,
$D:\mathcal{A}\rightarrow\mathcal{R}\cup\\{\bot\\}$ is a mapping that
associates activities with roles, e.g., a _create invoice_ activity may be
mapped to a _vendor_ role in a procurement process model.

###  3.3 Declarative Constraints

To specify best-practice constraints, we adopt concepts of Declare and MP-
Declare. Declare is a modeling language for declarative constraints [7] that
describes a set of templates that restrict occurrences and possible orderings
of activities in a process. MP-Declare is an extension of Declare [8] and can
express constraints over multiple perspectives of a process, e.g., the
resource and data perspectives, using Declare templates. The semantics of
Declare templates are often specificied with Linear Temporal Logic (LTL),
which allows to exploit the amenities of LTL verification, with the full
complexity of LTL “hidden” from the user. Table 1 summarizes commonly used
templates and their LTL semantics [6].

Table 1: Semantics of Declare templates Template |  LTL semantics | Activation
---|---|---
AtLeastOne(a) |  F a | at start
AtMostOne(a) |  $\neg\textbf{F}(a\land\textbf{X}(\textbf{F}a))$ | at start
ExactlyOne(a) |  AtLeastOne(a) $\land$ AtMostOne(a) | at start
Absence(a) |  $\neg$F a | at start
RespondedExistence(a,b) |  F a $\rightarrow$ F b | a
Response(a,b) |  G(a $\rightarrow$ F b) | a
AlternateResponse(a,b) |  $\textbf{G}(a\rightarrow$ $\textbf{X}(\neg a\textbf{U}b))$ | a
Precedence(a,b) |  G(b $\rightarrow$ O a) | b
AlternatePrecedence(a,b) |  $(\neg b$ S $a)\land$G $(b\rightarrow(\neg b$ S $a))$ | b
CoExistence(a,b) |  F a $\leftrightarrow$ F b | a,b
Succession(a,b) |  Response(a,b) $\land$
Precedence(a,b) | a,b
AlternateSuccession(a,b) |  AlternateResponse(a,b) $\land$
AlternatePrecedence(a,b) | a,b
NotCoExistence(a,b) |  (F a $\rightarrow\neg$F b) $\land$ (F b $\rightarrow\neg$F a) | a,b

In LTL, time is modeled as a linear sequence of states, or time points. At
each point in time, some statements may be true. Then, LTL formulas can be
used to specify the allowed behavior over the linear sequence. F, X, G, U, S,
and O are LTL operators with the following meaning: F$\phi$ means that $\phi$
holds at some point in the future, X$\phi_{1}$ means that $\phi_{1}$ holds in
the next instant, G$\phi$ means that $\phi$ holds forever in the future,
$\phi_{1}$U$\phi_{2}$ means that at some point in the future $\phi_{2}$ will
hold and until then $\phi_{1}$ holds; $\phi_{1}$S$\phi_{2}$ means that at some
point in the past $\phi_{2}$ held and since then $\phi_{1}$ holds, and O$\phi$
means that $\phi$ held at some point in the past; $\phi$, $\phi_{1}$, and
$\phi_{2}$ being LTL formulas. For a formal definition of these semantics, we
refer to [6].

For any declarative constraint, an _activation_ of a constraint serves as its
triggering condition. Once this condition becomes true, it expects the trace
to satisfy the corresponding target condition. Conversely, if the constraint
is not activated, the fulfillment of the target condition is not enforced and
the constraint is (vacuously) satisfied. For instance, $b$ is an activation
for Precedence(a,b) and $a$ is the target because the occurrence of $b$ forces
a to have occurred before. Table 1 specifies the activation condition per
template.

Given an activity sequence $\pi$ and a constraint $\phi$, assuming that both
relate to the same activity set $A$, $\pi$ is said to satisfy $\phi$, denoted
$\pi\models\phi$, if $\phi$ holds in the initial time point of the sequence.
We write $\pi\not\models\phi$ if $\pi$ violates constraint $\phi$.

MP-Declare extends Declare, among others, by introducing additional conditions
on attributes of events in a trace $\sigma$, i.e., additional activation
conditions. To illustrate this concept, let us examine the constraint
Absence(_decide on application_), which is always activated at the beginning
of a trace, indicating that _decide on application_ should never occur. We can
use an additional condition on other perspectives that must be satisfied to
activate the constraint, though. For instance, we may require that when
_decide on application_ takes place, it should be performed by a manager and
otherwise should not occur. We can express this constraint as Absence(_decide
on application_) $\mid$ role $\neq$ _manager_ , where role is an event
attribute and _manager_ its required value. Now, if (and only if) the role
associated with an event is not _manager_ , the Absence constraint is
activated.

##  4 Framework

This section presents our proposed framework for detecting best-practice
violations in event logs based on constraints mined from reference process
models. As illustrated in Figure 2, it consists of three main stages.

Figure 2: Framework overview.

The input of our framework is a collection of reference process models
$\mathcal{M}$. The _Constraint Mining_ stage extracts best practice
constraints from $\mathcal{M}$, resulting in a set $C_{\mathcal{M}}$
containing various kinds of constraints. This stage is independent of a
specific event log and, therefore, only needs to be performed once for a given
collection $\mathcal{M}$. Then, given an event log $L$, the _Constraint
Selection_ stage identifies which constraints from the collection
$C_{\mathcal{M}}$ are applicable to log $L$ and fits these constraints to the
log, resulting in a set of selected, fitted constraints $C_{L}^{S}$. This
stage contains multiple sub-stages, including constraint identification and
checking whether the recommended set of constraints is consistent. Note that
this stage can be executed in a fully automated manner, although users can
also choose to manually refine the set $C_{L}^{S}$. Finally, the _Conformance
Checking_ stage compares the traces in log $L$ against the constraints in
$C_{L}^{S}$, resulting in a collection of detected best-practice violations
$V_{L}$, presented to the user.

In the following, we continue to detail the individual steps of our framework.

###  4.1 Constraint Mining

In the constraint mining stage, we establish a constraint collection
$C_{\mathcal{M}}$ that represents best practices found in a reference process
model collection $\mathcal{M}$. In the remainder of this section, we first
describe the constraint types and templates that our framework covers (Section
4.1.1), before discussing the steps performed to mine the constraints:
_Constraint Extraction_ (Section 4.1.2) and _Collection Refinement_ (Section
4.1.3).

####  4.1.1 Coverage

Our framework covers four types of best-practice constraints, corresponding to
constraints that capture behavioral relations that should hold between
activities (i.e., activity-level constraints), across business objects (i.e.,
inter-object constraints), within business objects (i.e., intra-object
constraints), and ones that restrict the organizational roles that can perform
particular process steps (i.e., role constraints). Examples of each constraint
type are shown in Table 2. To represent the specific constraints, we use
different sets of Declare templates per constraint type, as shown in Table 3.

Table 2: Constraint types covered by our framework with examples. Type |  Exemplary constraint |  Description
---|---|---
Activity-level |  Precedence(_Approve PO_ , _Process GR_) |  _Approve PO_ should happen before _Process GR_.
NotCoExistence(_Reject PO_ , _Process GR_) |  _Reject PO_ and _Process GR_ should not co-occur.
Succession(_Process GR_ , _Enter Invoice_) |  _Process GR_ happens if (and only if) _Enter Invoice_ happens later.
Inter-object |  Precedence(_purchase order_ , _goods receipt_) |  A _purchase order_ should appear before a _goods receipt_.
RespondedExistence(_invoice_ , _goods receipt_) |  If there is an _invoice_ there should be a _goods receipt_ as well.
Intra-object |  Precedence(_create_ , _approve_) $\mid$ _purchase order_ |  For each _purchase order_ , _create_ should precede _approve_.
AtLeastOne(_create_) $\mid$ _purchase order_ |  For a _purchase order_ , _create_ should always occur.
Role |  Absence(Enter invoice) if role $\neq$ _accounts payable_ |  _Enter Invoice_ should be performed by _accounts payable_.

Activity-level constraints. Activity-level constraints capture best practices
about the behavioral relations that should hold between pairs of activities in
a trace. In order to represent different activity inter-relations, we use
Declare templates that capture that two activities should occur together
(RespondedExistence, CoExistence) or in a certain order (Succession,
AlternateSuccession), that one activity causes (Response, AlternateResponse)
or requires (Precedence, AlternatePrecedence) another activity, or that two
activities should not occur together (NotCoExistence).

For instance, an activity-level constraint may capture that a _approve
purchase order_ activity must precede a _process goods receipt_ activity
(e.g., Precedence(_approve purchase order_ , _process goods receipt_)). We do
not cover constraints that require activities to immediately occur after each
other (e.g., ChainResponse) which, we assume, is too restrictive for best
practices. Each such activity-level constraint is defined as follows:

######  Definition 1 (Activity-level constraint)

An activity-level constraint $c_{\mathcal{M}}\in C_{\mathcal{M}}$ is a tuple
$c_{\mathcal{M}}=(type,templ,$ $a_{1},a_{2},support)$, with
$c_{\mathcal{M}}.type=activity$, $c_{\mathcal{M}}.templ$ the constraint’s
Declare template, $c_{\mathcal{M}}.a_{1}$ and $c_{\mathcal{M}}.a_{2}$ the
activities, and $c_{\mathcal{M}}.support$ the constraint’s support.

Note that the constraints of all types we cover have a $support$ that
indicates how often a constraint was extracted from the model collection
$\mathcal{M}$ and is set when refining the collection of mined constraints
$C_{\mathcal{M}}$.

Table 3: Templates used per constraint type (cf. Section 3 for their definition) Constraint types | Templates
---|---
Activity, Inter-object |  RespondedExistence, Precedence,AlternatePrecedence,
Response, AlternateResponse, Succession,
AlternateSuccession, CoExistence, NotCoExistence
Intra-object |  AtLeastOne, Absence, ExactlyOne, RespondedExistence, Precedence,
AlternatePrecedence, Response, AlternateResponse, Succession,
AlternateSuccession, CoExistence, NotCoExistence
Role | Absence

Inter-object constraints. Inter-object constraints capture relations that
should hold between pairs of business objects occurring in a process, e.g.,
that a trace can only contain (activities related to) an invoice if there is
also at least one activity related to a delivery, i.e.,
RespondedExistence(_invoice_ , _delivery_). As shown in Table 3, we use the
same Declare templates to express inter-object constraints as we use for
activity-level constraints, with the difference that the constraint parameters
here correspond to objects, rather than activities. Consequently, each inter-
object constraint is defined as follows:

######  Definition 2 (Inter-object constraint)

An inter-object constraint $c_{\mathcal{M}}\in C_{\mathcal{M}}$ is a tuple
$c_{\mathcal{M}}=(type,templ,$ $o_{1},o_{2},support)$, with
$c_{\mathcal{M}}.type=interobj$, $c_{\mathcal{M}}.templ$ the constraint’s
Declare template, $c_{\mathcal{M}}.o_{1}$ and $c_{\mathcal{M}}.o_{2}$ its
business objects, and $c_{\mathcal{M}}.support$ its support.

Intra-object constraints. Intra-object constraints capture relations regarding
the actions, i.e., state changes, that are applied to a business object, e.g.,
that an _order_ must be _checked_ before it is _approved_ , i.e.,
Precedence(_check_ , _approve_) $\mid$ _order_. We use the vertical bar
($\mid$) to denote the constraint’s business object, i.e., that both actions
are applied to an _order_. Although it is also possible to represent such
constraints at the activity level (e.g., using Precedence(_check order_ ,
_approve order_)), explicitly capturing them for a business object offers
greater flexibility in generalizing across different business objects. For
instance, in this manner, constraints like Precedence(_check_ , _approve_) can
be more effectively extended to other contexts, such as _sales orders_. This
is advantageous during the fitting of constraints for a specific event log, as
we show in the _Constraint Selection_ stage (Section 4.2).

In addition to capturing pair-wise behavioral relations between actions, we
also consider situations where specific actions must or must not be performed
for certain types of objects. These are captured through the unary AtLeastOne,
Absence, and ExactlyOne templates, which can, e.g., capture that, if a trace
contains an activity related to a purchase order item, that trace must contain
an activity that creates that item, i.e., ExactlyOne(_create_) $\mid$
_purchase order item_.

Based on this, each intra-object constraint is defined as follows:

######  Definition 3 (Intra-object constraint)

An intra-object constraint $c_{\mathcal{M}}\in C_{\mathcal{M}}$ is a tuple
$c_{\mathcal{M}}=(type,templ,$ $object,arity,n_{1},n_{2},support)$, with
$c_{\mathcal{M}}.type=intraobj$, $c_{\mathcal{M}}.templ$ the constraint’s
Declare template, $c_{\mathcal{M}}.object$ its object, and
$c_{\mathcal{M}}.arity\in\\{\emph{unary},\emph{binary}\\}$ its arity
indicating whether $c_{\mathcal{M}}$ is a unary or binary constraint,
according to $c_{\mathcal{M}}.templ$. Moreover, $c_{\mathcal{M}}.n_{1}$
corresponds to the constraint’s first action, $c_{\mathcal{M}}.n_{2}$
represents its second action (set to $\bot$ if
$c_{\mathcal{M}}.arity=\text{unary}$), and $c_{\mathcal{M}}.support$ pertains
to its support.

Role constraints. Finally, role constraints focus on the resource perspective,
restricting the execution of activities to specific roles, i.e., who in an
organization can perform a given process step. These constraints can be
expressed using the Absence template with an activation condition. For
instance, a role constraint may capture that an _approve purchase order_
activity must be performed by an employee with a _manager_ role, written as
Absence(_approve purchase order_) $\mid$ role $\neq$ _manager_ , with role
$\neq$ _manager_ as the activation condition. Each such role constraint is
defined as follows:

######  Definition 4 (Role constraint)

A role constraint $c_{\mathcal{M}}\in C_{\mathcal{M}}$ is a tuple
$c_{\mathcal{M}}=(type,templ,$ $a,r,support)$, with
$c_{\mathcal{M}}.type=role$, $c_{\mathcal{M}}.templ=$Absence,
$c_{\mathcal{M}}.a$ the constraint’s activity, $c_{\mathcal{M}}.r$ the role in
its activation condition, and $c_{\mathcal{M}}.support$ its support.

####  4.1.2 Constraint Extraction

The goal of constraint extraction is to derive a set of constraints $C_{M}$
from each process model $M\in\mathcal{M}$. Using the constraint types and
corresponding templates introduced in the previous section, we base the
extraction of constraints on the idea of declarative constraint mining from
event logs [6], where each template is instantiated with all possible
parameters (or parameter combinations) before they are checked against the
traces for satisfaction. We apply the same idea to the set of execution
sequences allowed by a model, rather than to traces from an event log, with
the extraction procedure depending on the constraint type:

Activity-level constraints. We extract activity-level constraints from a model
$M=(A,F,R,D)$ by first instantiating potential constraints using each template
from Table 3 and each pair-wise combination of activities in $A$. Then we
check which of these potential constraints is satisfied by all and activated
by at least one of the execution sequences in $F$. For instance, for the
Response template, we check for each pair ($a_{1}$,$a_{2}$) $\in A\times A$ if
G($a_{1}\rightarrow$ F $a_{2}$) (cf. Section 3) holds for all $\pi\in F$
and—if so—set $c_{\mathcal{M}}.type=activity$,
$c_{\mathcal{M}}.templ=\textsc{Response}$, $c_{\mathcal{M}}.a_{1}=a_{1}$, and
$c_{\mathcal{M}}.a_{2}=a_{2}$ and add $c_{\mathcal{M}}$ to $C_{M}$.

Inter-object constraints. We extract inter-object constraints by obtaining a
set of allowed object sequences $F_{\emph{obj}}$ and then checking which
constraints hold between pairs of objects according to $F_{\emph{obj}}$.

To obtain $F_{obj}$, we project each (activity) execution sequence $\pi\in F$
to an object sequence $\pi_{\emph{obj}}$, which we achieve using a semantic
extraction technique [9] to obtain the business objects (if any) from each
activity in $\pi$. For instance, for $\pi=\langle\emph{create
order},\emph{check order},\emph{approve order},\emph{ship goods}\rangle$, we
get
$\pi_{\emph{obj}}=\langle\emph{order},\emph{order},\emph{order},\emph{goods}\rangle$.
If an activity does not relate to any business object, it is not considered in
the projected trace. While uncommon, in cases where an activity relates to
multiple business objects, these are considered as a single business object,
assuming that in a reference process model, these are then consistently
referenced together.

Afterwards, we instantiate constraint templates between possible pairs of
objects $(o_{1},o_{2})$ occurring in $F_{\emph{obj}}$ and check them against
the sequences in $F_{\emph{obj}}$, in the same manner as done for activity-
level constraints. For instance, for the binary RespondedExistence template,
we check for each combination ($o_{1}$,$o_{2}$) with $o_{1},o_{2}\in O$ if F
$o_{1}$ $\rightarrow$ F $o_{2}$ holds for all $\pi_{\emph{obj}}\in
F_{\emph{obj}}$ and—if so—set $c_{\mathcal{M}}.type=interobj$,
$c_{\mathcal{M}}.templ=\textsc{RespondedExistence}$,
$c_{\mathcal{M}}.o_{1}=o_{1}$, and $c_{\mathcal{M}}.o_{2}=o_{2}$ and add
$c_{\mathcal{M}}$ to $C_{M}$.

Intra-object constraints. We extract intra-object constraints for each
business object that is contained in the activities in $A$, based on the
actions that are applied to such an object.

To obtain the necessary information on business objects and actions, we,
therefore, again use the semantic extraction technique [9] (as done for inter-
object constraints). This time, we turn the output of that approach into a
function getObjectActionPairs, which, given an activity $a$, returns a set of
object-type-action pairs obtained from $a$, where each pair is given as a
tuple ($o$, $n$), indicating that action $n$ is applied to object $o$.222Note
that, for clarity, we here focus on situations where each activity yields a
single object-action pair, although our framework can also handle activities
with multiple pairs, e.g., receive and check document. For instance,
$\texttt{getObjectActionPairs}(\emph{approve purchase
order})=\\{(\emph{purchase order},\emph{approve})\\}$. By applying the
function to each activity $a\in A$, we obtain a set $O$ of distinct business
objects that appear in the activities in $A$ and a set $N_{o}$ of actions per
business object $o\in O$, which we use to create intra-object sequences.

As shown in Algorithm 1, we create a set of intra-object sequences $F_{o}$ for
each business object $o\in O$ as follows: For each $\pi\in F$, we check for
each activity $a_{i}$ in $\pi$ if $a_{i}$ refers to $o$ and if so only retain
the action applied to $o$. For instance, for $\pi=\langle\emph{create
order},\emph{check order},\emph{approve order},\emph{ship goods}\rangle$, we
get
$\pi_{\emph{order}}=\langle\emph{create},\emph{check},\emph{approve}\rangle$.

Algorithm 1 Create intra-object sequence sets

t Input $F$: set of finite execution sequences; $O$: set of business objects
t Output $res$: set containing a set of action sequences per business object

1:$res\leftarrow\\{F_{o}\leftarrow\emptyset\mid o\in O\\}$ $\triangleright$
Initialize an empty set of action sequences for each business object

2:for each business object $o\in O$ do

3: for each $\pi\in F$ do

4: $\pi_{o}\leftarrow\langle\rangle$

5: for each activity $a_{i}$ in $\pi=\langle a_{1},\ldots,a_{n}\rangle$ do

6: $(o_{a_{i}},n_{a_{i}})\leftarrow\texttt{getObjectActionPairs}(a_{i})$

7: if $o=o_{a_{i}}$ then

8: $\pi_{o}\leftarrow\pi_{o}+\langle n_{a_{i}}\rangle$ $\triangleright$ Retain
the action applied to $o$ and append to current sequence

9: $F_{o}\leftarrow F_{o}\cup\\{\pi_{o}\\}$

10:return $res$

Based on an intra-object set of sequences $F_{o}$, we can then instantiate the
Declare templates with actions in $N_{o}$ in the same manner as done with
entire activities for activity-level constraints. For instance, for the binary
template Precedence, we check for each combination $(n_{1},n_{2})\in
N_{o}\times N_{o}$ if G($n_{2}\rightarrow$ O $n_{1}$)(cf. Section 3) holds for
all $\pi_{o}\in F_{o}$ and—if so—set $c_{\mathcal{M}}.type=intraobj$,
$c_{\mathcal{M}}.templ=\textsc{Precedence}$,
$c_{\mathcal{M}}.arity=\text{binary}$, $c_{\mathcal{M}}.n_{1}=n_{1}$,
$c_{\mathcal{M}}.n_{2}=n_{2}$, and $c_{\mathcal{M}}.object=\emph{order}$ and
add $c_{\mathcal{M}}$ to $C_{M}$.

Role constraints. Finally, role constraints can be extracted independently of
execution sequences from the mapping $D$ of a model $M$, which maps an
activity to the role that is supposed to execute it (if any). These can thus
be created by instantiating the Absence template with a corresponding
activation condition setting $c_{\mathcal{M}}.type=role$,
$c_{\mathcal{M}}.templ=\textsc{Absence}$, $c_{\mathcal{M}}.a=a$, and
$c_{\mathcal{M}}.r=r$ and adding $c_{\mathcal{M}}$ to $C_{M}$ for each
activity $a\in A$ that is mapped to a role $r\in R$ by $D$.

By following this extraction procedure, we obtain a set of best-practice
constraints $C_{M}$ per model $M\in\mathcal{M}$. Having a large collection of
models and a considerable number of constraints extracted per model, we next
set out to refine this collection of constraint sets.

####  4.1.3 Collection Refinement

Having extracted independent constraint sets $\\{C_{M}\mid M\in\mathcal{M}\\}$
per reference process model, we next establish a single refined constraint
collection which is meant to aggregate all individual constraint sets. To this
end, we standardize equal (or very similar) constraints and omit redundant
constraints that are subsumed by stronger ones.

Standardizing constraints. First, we standardize the actions of the
constraints that we extracted to obtain a single, more concise set of
constraints $C_{\mathcal{M}}$. For instance, we avoid that Precedence(_create
invoice, approve invoice_) and Precedence(_invoice created, invoice
approved_), are treated as distinct constraints. Therefore, we standardize the
activities of activity-level and action(s) of intra-object constraints by
turning past-tense actions, like _created_ and _approved_ , into the present-
tense, i.e., _create_ and _approve_. We also update the word ordering of
activity-level constraints accordingly, e.g., turning invoice created into
create invoice.

After this standardization step, we can then aggregate the constraints from
different models setting a constraint’s support to reflect from how many
process models in $\mathcal{M}$ the particular constraint was extracted.

Removing redundant constraints. Finally, we remove weaker constraints that are
encompassed by stronger ones, because these weaker ones are then redundant. To
this end, we make use of the _subsumption relation_ between Declare
constraints, following the approach presented in [10]. An example would be
Response(_a, b_), which encompasses RespondedExistence(_a, b_) (”every
Response is also a RespondedExistence”). The subsumption relations between
templates employed by our framework are shown in Figure 3. For each
$c_{\mathcal{M}}^{w}\in C_{\mathcal{M}}$, we check if a stronger (subsuming)
constraint $c_{\mathcal{M}}^{s}$ exists that was observed the same number of
times, i.e., $c_{\mathcal{M}}^{w}.support=c_{\mathcal{M}}^{s}.support$, and—if
so—remove $c_{\mathcal{M}}^{w}$ from $C_{\mathcal{M}}$.

Figure 3: Subsumption relations between constraints employed by our framework
(adapted from [10]). The subsumption relation is depicted as a line starting
from the subsumed template with an empty triangular arrow and ending in the
subsuming one.

Output of the mining stage. The output of this stage is a refined collection
of mined constraints $C_{\mathcal{M}}$, which together with an event log $L$
serves as the input of the next stage, the _Constraint Selection_ stage.

###  4.2 Constraint Selection

$C_{\mathcal{M}}$ is based on the reference models and therefore might contain
various irrelevant constraints for a concrete event log $L$. The Constraint
Selection stage therefore aims to select those constraints from
$C_{\mathcal{M}}$ that are most relevant for the detection of best-practice
violations in a given event log $L$. This involves three steps, as illustrated
in Figure 4. In the first step, we “fit” the constraints for $L$, which yields
a collection of fitted constraints $C_{L}$ (we will explain what is meant by
“fitting” below). Out of these, we recommend the most relevant ones
$C_{L}^{R}$, taking into account selected configuration parameters and
additional user preferences. Finally, we check the set of selected constraints
$C_{L}^{R}$ for consistency to ensure they are without any contradictions,
which yields a consistent set of selected, fitted constraints $C_{L}^{S}$. In
the following, we explain these steps in detail.

Figure 4: Overview of the constraint selection stage.

####  4.2.1 Constraint Fitting

In this step, our framework tries to fit the mined constraints in
$C_{\mathcal{M}}$ to the contents of the given event log $L$, by relating the
activities, objects, actions, and roles used in mined constraints (derived
from models in $\mathcal{M}$), to counterparts found in the event log $L$,
yielding a set of fitted constraints $C_{L}$. To do this, our framework looks
for semantically similar counterparts, allowing it to, e.g., relate a
Precedence(_receive invoice_ , _pay invoice_) constraint to receive bill and
make payment activities found in a log. Each such fitted constraint is defined
as follows:

######  Definition 5 (Fitted constraint)

Given a mined constraint $c_{\mathcal{M}}$ and an event log $L$, a fitted
constraint $c_{L}$ is a tuple $c_{L}=(c_{\mathcal{M}},$ $type,$ $templ,$
$[components],$ $support,$ $sim,$ $relevance)$, with $c_{L}$’s $type$,
$templ$, and $support$ being equal to those of $c_{\mathcal{M}}$.
$c_{L}.[components]$ is a shorthand to refer to the list of $c_{L}$’s type-
specific components (e.g., $c_{L}.[components]=c_{L}.a_{1},c_{L}.a_{2}$ for
activity-level constraints) that are each linked to components (i.e.,
activities, actions, objects, or roles) found in $L$. Finally, $c_{L}.sim$ is
a map capturing the semantic similarity between $c_{\mathcal{M}}$’s and
$c_{L}$’s components, and $c_{L}.relevance$ is a score indicating the
relevance of $c_{L}$ for $L$.

Creating fitted constraints for $L$ involves matching constraint components to
their event log counterparts and replacing these components with their
counterparts, as shown by Algorithm 2. The algorithm takes as input the
constraint collection $C_{\mathcal{M}}$ and the event log $L$, using a type-
specific fitting procedure for each $c_{\mathcal{M}}\in C_{\mathcal{M}}$.

Semantic similarity computation. A key part of Algorithm 2 is the
match($x_{\mathcal{M}}$, $x_{L}$) function, which is used to decide whether a
constraint component $x_{\mathcal{M}}$ is semantically similar to an event log
component $x_{L}$. It is instantiated using a similarity measure sim and a
threshold $\epsilon$, i.e., match($x_{\mathcal{M}}$,
$x_{L}$)$:=\texttt{sim}(x_{\mathcal{M}},x_{L})>\epsilon$. As a similarity
measure, we employ the cosine similarity based on embedding vectors for
$x_{\mathcal{M}}$ and $x_{L}$, which we obtain from a pre-trained _sentence
transformer_ [11]. These transformers are specifically designed to capture
semantically meaningful representations on the level of sentences rather than
individual words and can thus be applied on activities or business objects
that may consist of multiple words. We set $\epsilon$ to 0.5 by default,
ensuring that all fitted constraints are reasonably similar to the components
of $L$, which avoids having to filter out a lot of constraints from
$C_{L}^{S}$ in the next step.333Note that, in order to make match more or less
restrictive, it is possible to use different values for $\epsilon$ depending
on the type of component we aim to find matches for, i.e., setting different
thresholds for activities, objects, and actions.

Algorithm 2 Constraint fitting

t Input $C_{\mathcal{M}}$: set of mined constraints; $L$: event log
t Output $C_{L}$: set of fitted constraints

1:$C_{L}\leftarrow\emptyset$

2:for $c_{\mathcal{M}}\in C_{\mathcal{M}}$ do

3: if $c_{\mathcal{M}}.type$ is $activity$ then

4: for $(a_{1_{L}},a_{2_{L}})\in A_{L}\times A_{L}$ do

5: if
$\texttt{match}(c_{\mathcal{M}}.a_{1},a_{1_{L}})\land\texttt{match}(c_{\mathcal{M}}.a_{2},a_{2_{L}})\land
a_{1_{L}}\neq a_{2_{L}}$ then

6: FitActivityConstraint($c_{\mathcal{M}}$, $a_{1_{L}}$, $a_{2_{L}}$)

7: if $c_{\mathcal{M}}.{type}$ is $interobj$ then

8: for $(o_{1_{L}},o_{2_{L}})\in O_{L}\times O_{L}$ do

9: if
$\texttt{match}(c_{\mathcal{M}}.o_{1},o_{1_{L}})\land\texttt{match}(c_{\mathcal{M}}.o_{2},o_{2_{L}})\land
o_{1_{L}}\neq o_{2_{L}}$ then

10: FitInterObjectConstraint($c_{\mathcal{M}}$, $o_{1_{L}}$, $o_{2_{L}}$)

11: if $c_{\mathcal{M}}.type$ is $intraobj$ then

12: for $o_{L}\in O_{L}$ do

13: if $\texttt{match}(c_{\mathcal{M}}.object,o_{L})$ then

14: if $c_{\mathcal{M}}.arity=$ unary then

15: for $n_{L}\in N_{o_{L}}$ do

16: if $\texttt{syn}(c_{\mathcal{M}}.n_{1},n_{L})$ then

17: FitIntraObjectConstraint($c_{\mathcal{M}}$, $n_{L}$, $\bot$)

18: if $c_{\mathcal{M}}.arity=$ binary then

19: for $(n_{1_{L}},n_{2_{L}})\in N_{o_{L}}\times N_{o_{L}}$ do

20: if
$\texttt{syn}(c_{\mathcal{M}}.n_{1},n_{1_{L}})\land\texttt{syn}(c_{\mathcal{M}}.n_{2},n_{2_{L}})\land
n_{1_{L}}\neq n_{2_{L}}$ then

21: FitIntraObjectConstraint($c_{\mathcal{M}}$, $n_{1_{L}}$, $n_{2_{L}}$)

22: if $c_{\mathcal{M}}.type$ is $role$ then

23: for $a_{L}\in A_{L}$ do

24: if $\texttt{match}(c_{\mathcal{M}}.a,a_{L})$ then

25: for $r_{L}\in R_{L}$ do

26: if $\texttt{match}(c_{\mathcal{M}}.r,r_{L})$ then

27: FitRoleConstraint($c_{\mathcal{M}}$, $a_{L}$, $r_{L}$)

28:return $C_{L}$

Activity-level constraints. For an activity-level constraint
$c_{\mathcal{M}}$, we need to find activities in $L$ that correspond to the
constraint’s activity components, $c_{\mathcal{M}}.a_{1}$ and
$c_{\mathcal{M}}.a_{2}$. Specifically, we create a fitted version of
$c_{\mathcal{M}}$ for any pair of distinct log activities $a_{1_{L}}$ and
$a_{2_{L}}$ for which both match($c_{\mathcal{M}}.a_{1},a_{1_{L}}$) and
match($c_{\mathcal{M}}.a_{2},a_{2_{L}}$) hold (lines 5–6).

It is important to note that this can result in multiple fitted constraints
being added to $C_{L}$ that stem from a single mined constraint
$c_{\mathcal{M}}$. To illustrate this, consider a mined constraint that
specifies that requests must first be examined before a decision can be made
on them, i.e., Precedence(_examine request_ , _decide on request_). It is
well-imaginable that a process like this actually uses different kinds of
examinations for different types of cases or situations, e.g., having perform
basic examination and perform thorough examination. In such a scenario, the
mined constraint needs to be fitted twice, so that both types of examinations
are covered, yielding constraints capturing Precedence(_perform simple
examination_ , _decide on request_) and Precedence(_perform thorough
examination_ , _decide on request_).

Inter-object constraints. To be able to fit an inter-object constraint
$c_{\mathcal{M}}$, we need to find two business objects in $L$ that match the
business objects of $c_{\mathcal{M}}$. To do this, we use $O_{L}$ to denote
the set of business objects in $L$, which is obtained using
getObjectActionPairs (see Section 4.1.2), i.e.,
$O_{L}=\\{o\mid(o,n)\in\\{\texttt{getObjectActionPairs}(a)\mid a\in
A_{L}\\}\\}$. Then, the fitting procedure for inter-object constraints is
identical to the procedure for activity-level constraints, with the exception
that we match the constraint’s objects to objects in $O_{L}$ (lines 9–10).

Intra-object constraints. For an intra-object constraint $c_{\mathcal{M}}$, we
need to find both a matching business object and one or two corresponding
actions (depending on if $c_{\mathcal{M}}$ is a binary or unary constraint) in
$L$. To this end, we first check for a matching business object $o_{L}$, in
the same manner as done for inter-object constraints (line 13). If found, we
next check for matches between $c_{\mathcal{M}}$’s action(s) and those in the
log that are applied to $o_{L}$, i.e., in the set $N_{o_{L}}$ (see Section
4.1.2).

A distinction we make here is that we do not look for corresponding actions
based on semantic similarity (i.e., using match), but rather look for synonyms
of actions. We make this distinction because actions generally correspond to
verbs, which is a specific class of words that is covered well by lexical
resources, such as _WordNet_ [12], which provide curated lists of similar
terms (e.g., synonyms). Therefore, by checking for synonymous actions, we can
use a restrictive, but highly precise matching strategy for actions.444Note
that this synonym-based matching strategy using syn can be straightforwardly
replaced with match if desired.

For instance, consider a constraint $c_{\mathcal{M}}$ corresponding to
AtLeastOne(_check_) $\mid$ _order_ and an event log that relates to purchase
order objects, including an examine purchase order activity. Then, our
framework would recognize that order and purchase order are semantically
similar, i.e., match(order, purchase order)$=true$, and that examine is a
synonym of check, i.e., syn(check, examine)$=true$, yielding a fitted
constraint $c_{L}$ corresponding to AtLeastOne(_examine_) $\mid$ _purchase
order_.

Role constraints. Finally, to fit a role constraint $c_{\mathcal{M}}$, we need
to identify both a matching activity and a matching role in $L$. To this end,
we first check for a matching activity $a_{L}\in A_{L}$ in the same manner as
for activity-level constraints (line 24). If found, we next check for matches
between $c_{\mathcal{M}}$’s role $c_{\mathcal{M}}.r$ (captured in its
activation condition) and the roles in the log, i.e., in the set $R_{L}$. If
for $r_{L}\in R_{L}$, match($c_{\mathcal{M}}.r$, $r_{L}=true$) holds, we fit
$c_{\mathcal{M}}$ with $a_{L}$ and $r_{L}$ (line 27).

When fitting a constraint, we populate $c_{L}$’s similarity map $c_{L}.sim$
such that it maps the matched components from $c_{\mathcal{M}}$ and their
counterparts in $c_{L}$ to their respective similarity scores, which we will
use for recommendation. Having iterated through all constraints
$c_{\mathcal{M}}\in C_{\mathcal{M}}$, the algorithm outputs the set of fitted
constraints $C_{L}$.

####  4.2.2 Constraint Recommendation

While from the previous step we have obtained a set of fitted constraints,
this set might still be too large, or contain constraints that are
uninteresting. In the recommendation step, we therefore aim to select a subset
of constraints from $C_{L}$ that are most relevant to the event log $L$. To
this end, we first compute a relevance score for each constraint, which we
then use to select a set $C_{L}^{R}$ of recommended constraints, according to
user-defined parameters regarding size and relevance.

Relevance computation. To be able to recommend appropriate constraints, we
need an indicator of how relevant a constraint $c_{L}\in C_{L}$ is to an event
log $L$. To achieve this, we compute a relevance score based on $c_{L}$’s
semantic similarity scores and support. We consider these two aspects, since a
higher semantic similarity indicates that a constraint is more applicable to
the specific context of the given event log $L$ (e.g., because the activities
from the original, mined constraint are highly similar to those found in $L$),
whereas higher support indicates that a constraint is more generally
applicable to processes (because it was found in a larger number of models in
$\mathcal{M}$). We capture these aspects as follows:

$c_{L}.relevance=\omega*\texttt{avg}(\\{s\mid((x,y),s)\in
c_{L}.sim\\})+{(1-\omega)}*(\frac{c_{L}.support}{\texttt{max}(\\{c_{L}^{\prime}.support\mid
c_{L}^{\prime}\in C_{L},c_{L}^{\prime}.type=c_{L}.type\\}}))$

As shown, we combine the average similarity score
$\texttt{avg}(\\{s\mid((x,y),s)\in c_{L}.sim\\})$ observed for the constraint
with the constraint’s support $c_{L}.support$, normalized by dividing it by
the maximum support of a constraint of the same type in $C_{L}$, such that
both, similarity and support, have a comparable range. The two aspects can be
weighed differently by adapting $\omega\in[0,1]$, e.g., to give a higher
weight to support.

Constraint selection. The computed relevance scores can be employed to obtain
a selection of recommended constraints $C_{L}^{R}$. Our framework allows users
to select all constraints from $C_{L}$ that have a relevance higher than a
certain threshold $\tau$, or to select the top-$k$ constraints from $C_{L}$
that have the highest relevance scores, thus providing users control over
either the minimum desired relevance score $\tau$ or the maximal number of
constraints $k$. Users can also apply the selection strategies in a type-
specific manner, i.e., by specifying different relevance thresholds
$\tau_{type}$ for each constraint type, or by selecting the top-$k$
constraints per type.

User input. After providing a set of recommended constraints $C_{L}$, the user
can decide if they continue without intervention or if they want to inspect
the recommended constraints and optionally filter the collection manually. For
instance, if they find that some recommended constraints involve an object
that is not interesting from a compliance perspective, they can remove all
constraints that involve that object.

####  4.2.3 Consistency Checking

The final step of the _Constraint Selection_ stage ensures that $C_{L}^{R}$
contains no inconsistencies. For instance, we want to avoid that the set
contains both CoExistence(a,b) and NotCoExistence(a,b) constraints, since
these directly contradict each other. Note that inconsistencies can also be
more complex due to transitivities, e.g., a set of constraints Response(a,b),
Response(b,c) and NotCoExistence(a,c) is also inconsistent, since the first
two constraints transitively state that $a$ should eventually be followed by
$c$, whereas the final constraint explicitly forbids this. Since such
combinations are hard, if not impossible, to spot for humans [13], automated
consistency checking and resolution is required.

To operationalize this, we use an existing approach for inconsistency
resolution in declarative process specifications [14]. Given a set of
constraints $C$, this approach identifies a set of minimal correction sets
MCS($C$), which are sets of constraints that, if removed from $C$, make $C$
consistent:

######  Definition 6 (Minimal correction sets)

Given a constraint set $C$, a set $\Phi\subseteq C$ is a minimal correction
set of $C$, if $C\setminus\Phi$ is consistent, and
$\forall\Phi^{\prime}\subset\Phi:C\setminus\Phi^{\prime}$ is inconsistent. We
denote MCS(C) as the set of minimal correction sets for the constraints in C.

If the inconsistency resolution approach detects inconsistencies in
$C_{L}^{R}$, our framework, by default, deletes the constraints from the
correction set in MCS($C_{L}^{R}$) with the lowest cumulative relevance score.
This ensures that we obtain a consistent set $C_{L}^{S}$ of constraints, while
maximizing the overall relevance of the retained constraints. If there are no
inconsistencies, $C_{L}^{R}$ simply becomes $C_{L}^{S}$.

User input. The employed inconsistency resolution approach [14] also allows a
user to select specific constraints that should not be removed from
$C_{L}^{R}$, giving them control over the recommended correction sets.
Furthermore, the user has the option to inspect the minimal correction sets
and choose to remove one of these based on their preferences instead of
automatically having the one removed that maximizes relevance.

Output of the selection stage. The output of this stage is a collection of
fitted constraints $C_{L}^{S}$ that is free of inconsistencies. $C_{L}^{S}$ is
used in the subsequent stage to check for best-practice violations.

###  4.3 Conformance Checking

Our framework’s final stage uses the set of selected constraints $C_{L}^{S}$
to check for best-practice violations in the event log $L$ and, if found,
presents these to the user. To this end, the framework first identifies such
violations for each trace, yielding a set of violations $V_{L}$. Afterwards,
it aggregates the violations in $V_{L}$ to the log-level and adds an
explanation of each type of violation.

####  4.3.1 Trace-based Conformance Checking

The goal of this step is to check which constraints are violated per trace
$\sigma\in L$. To this end, our framework creates a collection $V_{L}$ of
trace-constraint pairs ($\sigma$,$c_{L}$), where each pair represents the
violation of $c_{L}$ in $\sigma$. To establish these pairs, our framework
checks per trace $\sigma\in L$ and each constraint $c_{L}\in C_{L}^{S}$ if
that constraint is violated, i.e., if $\sigma\not\models c_{L}$. The checking
process is analogous to the one used in constraint mining (cf. Section 4.1).
However, while in constraint mining we assess whether a constraint is
fulfilled across all sequences allowed by a model, here we focus on
identifying specific traces where a constraint is not met. Given a trace
$\sigma$, the conformance checks per constraint type are performed as follows:

Activity-level and role constraints. For an activity-level or a role
constraint $c_{L}$, our framework can directly check if $\sigma\not\models
c_{L}$ holds and, if so, add ($\sigma$, $c_{L}$) to $V_{L}$.

Inter-object constraints. For an inter-object constraint $c_{L}$, our
framework checks against the object sequence $\sigma^{a}_{obj}$ that it
obtains by projecting the activity sequence $\sigma^{a}$ to its objects, as
also done when mining constraints of this type. Then, it checks if
$\sigma^{a}_{obj}\not\models c_{L}$ holds and, if so, adds ($\sigma$, $c_{L}$)
to $V_{L}$.

Intra-object constraints. For an intra-object constraint $c_{L}$, the
framework checks against the action sequence $\sigma_{o}$ for its business
object $o=c_{L}.object$, which it obtains in the same manner as done in
Algorithm 1. Then, it checks if $\sigma_{o}\not\models c_{L}$ holds and, if
so, adds ($\sigma$, $c_{L}$) to $V_{L}$.

####  4.3.2 Result Representation

In this final step, our framework creates a more concise and informative
summary of the violations for the user by aggregating them across traces.
Specifically, it groups violations per constraint type and template and adds a
textual explanation to each such violation. An example of this is shown in
Table 4. To generate the explanations for the violations, we use a standard
sentence template for each combination of constraint type and Declare
template.

Constraint |  Constraint explanation | Violating traces
---|---|---
AtLeastOne(_create_)$|$_order_ |  Each order must be created | $\\{\sigma_{6},\dots,\sigma_{76}\\}$
Precedence(_check_ , _approve_)$|$_invoice_ |  An invoice must be checked before it is approved | $\\{\sigma_{23}\\}$
Table 4: Exemplary result representation of intra-object constraint
violations.

##  5 Evaluation

In this section, we aim to demonstrate the effectiveness of our framework to
select relevant constraints for detecting best-practice violations. To do so,
we test if the constraints that our framework selects for a given log can be
used to find known violations. We describe the data collection in Section 5.1
and the experimental setup in Section 5.2. In Section 5.3, we present our
evaluation results demonstrating our approach’s efficacy in identifying best-
practice violations and that it outperforms a baseline approach in both scope
and accuracy. The implementation, data collection, evaluation pipeline, and
raw results are all available in our
repository555https://github.com/a-rebmann/semantic-constraint-miner/.

###  5.1 Data Collection

Our goal is to show that our framework is effective in selecting constraints
that are relevant for a given event log and that these constraints can be used
to identify best-practice violations. Therefore, we need a process model
collection to extract constraints from and event logs with known best-practice
violations, i.e., with behavior that deviates from a process model that
represents desired behavior.

Process model collection. Since there is no public reference model collection
available, we use a collection of real-life process models. We use this
collection for both extracting constraints and generating event logs with
violations. For the experiments, we apply a cross-validation procedure as
explained later. Specifically, we use the public _SAP-SAM_ data set [15], a
large process model collection created by academic users of a commercial
process modeling tool.

Given that there is no quality assurance for the entire model collection, we
select only English models that fulfill a set of requirements to reduce data
quality issues. In particular, each model needs to have between 5 and 50
elements, pass the BPMN syntax check (using the functionality of a commercial
process modeling tool), and must be transformable into a sound workflow net.
The former two requirements reduce the probability that models with barely any
(too few elements) or pointless (too many elements and syntax errors) behavior
are included, whereas the latter ensures that we can generate proper event
logs from the models. From those we randomly select 1,500 models, primarily in
order to keep run times manageable. Note that because this is not a real
_reference_ process model collection, we assume that the behavior of the
contained models captures best practices.

Generating event logs with violations. To obtain logs with known violations
from this process model collection, we play out the models and insert noise:
For each model, we use its workflow net to generate an event log that contains
a single trace of each variant that is possible in the net (in case of loops,
each loop is executed at most once). For nets with fewer than 100 variants, we
keep playing out traces until the log has 100 traces, so that we have a
minimum amount of traces available per log for noise insertion. Then, to add
violations to the logs, we select traces to introduce noise into, with a
probability of 50% per trace. If a trace is chosen for noise insertion, we
either randomly add, remove, or swap events or assign a different role to an
event than the original one. After performing a noise-insertion action for a
selected trace, there is a 50% probability to insert noise again (repeated
until false). The characteristics of the log collection (before and after
noise insertion) obtained in this manner are shown in Table 5. As depicted
there, the complexity of the logs varies considerably. For instance, the logs
have 5 activities on average, whereas the maximum number observed is 18 and
the number of object types is 3.9 on average, whereas the maximum is 17. The
differences between the original and noisy logs become clear when looking at
the variants. While the original logs contain 3.5 different variants on
average, this increases to 30.9 for the noisy logs.

Table 5: Characteristics of the original and noisy logs. Collection | Count | Activities | Object types | Variants | Variant length
---|---|---|---|---|---
|  | avg. | max. | avg. | max. | avg. | max. | avg. | max.
Original logs | 1,500 | 4.9 | 18 | 3.9 | 17 | 3.5 | $720$ | 3.7 | 10
Noisy logs | 1,500 | 4.8 | 18 | 3.9 | 17 | 30.9 | $703$ | 3.9 | 14

The inserted noise then leads to violations of activity, inter-object, intra-
object, and role constraints. Because we assume that a process model
established by users contains best-practice behavior, any behavior not allowed
by the model can be considered a best-practice violation. Hence, we compute
the known violations for an event log $L$ by verifying for each trace
$\sigma\in L$ if $\sigma$ violates the behavior of the model $M$ that was used
to generate $L$ and recording violations of this behavior in a collection of
true violations $L^{M}_{V}$. Statistics about the violations contained in our
log collection are depicted in Table 6. As shown there, on average 40% of
traces are affected by activity-level violations, 28% by inter-object
violations, 38% by intra-object violations, and 9% by role violations. Across
constraint types, the average number of violations per log is considerably
higher than the number of affected traces, indicating that frequently there
are multiple violations per trace.

Table 6: Violations per noisy log. Const. Type | Affected traces | Violations
---|---|---
| avg. | max. | avg. | max.
Activity | 40.77 | 312 | 169.00 | 1979
Inter-object | 28.34 | 276 | 95.35 | 1453
Intra-Object | 38.31 | 199 | 91.22 | 905
Role | 9.14 | 150 | 11.47 | 172

###  5.2 Setup

Implementation. We implemented our framework and evaluation pipeline in
Python. For handling the import and generation of event logs, we used PM4Py
[16] and as a basis for constraint checking, we used Declare4Py [17]. To
assess semantic similarity between activities and business objects, we
generated sentence transformer embeddings [11] using the _all-MiniLM-L6-v2_
pretrained language model666Available here: https://huggingface.co/sentence-
transformers/all-MiniLM-L6-v2. Finally, as described in Section 4, we use
existing approaches [9, 14] to extract objects and actions from activities and
to check for inconsistencies in constraint sets.

Configurations. We test various settings for the relevance threshold $\tau$,
the weight of the semantic similarity $\omega$ when computing the relevance of
a constraint, and $k$ that determines how many of the most relevant
constraints per type are selected. In particular, we run experiments for
$\tau\in\\{0.5,0.8\\}$ to investigate the effect of a low vs. a high relevance
score, $\omega\in\\{0.5,0.9\\}$ to investigate the importance of support, and
$k\in\\{10,100,250\\}$ to investigate how the number of selected constraints
impacts performance.

Baseline. We compare our framework to the semantic-anomaly-detection approach
proposed by Van der Aa et al. [18]. Its goal is to detect whether behavior
recorded in an event log does not make sense from a semantic point of view.
Therefore, it can also be used to detect violations of general behavioral
relations captured in models of well-engineered processes, i.e., reference
process models, which makes it a suitable baseline for our framework. Their
approach populates a knowledge base with semantic relations that reflect
appropriate process executions. The knowledge records for this population
procedure are extracted from (1) a general-purpose linguistic resource that
captures relations between verbs and (2) a process model collection (i.e., the
same process model collection we use to mine constraints from). For a given
trace, the approach checks whether pairs of actions that are applied to the
same object violate records in the knowledge base, indicating semantic
anomalies. We compare our work against the configuration with the best
reported results in the original paper, referred to as SEM4 in their
experiments. Importantly, this configuration leverages semantic similarity to
enhance the generalizability of the rules stored in the knowledge base. It is
worth stressing that, because of its focus on actions applied to the same
object, the baseline can solely detect intra-object constraint violations.

Cross validation. Because we use the same model collection $\mathcal{M}$ for
constraint mining and detection, we conduct a 5-fold cross validation. To this
end, we randomly split the model collection into 5 sets and use models of 4
sets for constraint mining and the noisy logs generated from the 5th set for
testing the violation detection. We run the experiments 5 times, so that each
set acts as the test set once.

Measures. We check for violations in the noisy log $L^{M}$, given the original
model $M$, which yields a collection of detected violations $L^{M}_{D}$. For
each detected violation $v\in L^{M}_{D}$, we check if $v$ is contained in the
set of true violation $L^{M}_{V}$ (computed as explained above) resulting in a
true positive (TP) or false positive assessment (FP). Any violation that is
present in $L^{M}_{V}$ but has not been detected by our framework, i.e., is
not included in $L^{M}_{D}$, is deemed a false negative (FN). Using this
approach, we quantify the precision, given by TP/(TP+FP) and the recall, given
by TP/(TP+FN). Beyond these, we report on run time for the different stages.

###  5.3 Results

We first report on the constraints mined from the model collection, before
describing the overall results of the violation detection. Then, we report on
the results per constraint type and inspect the detailed results of selected
logs to provide insights into when our framework performs well and when it
fails. Finally, we compare the performance of our framework against the
baseline and reflect on its run time.

Extracted constraints. Our framework extracted more than 250,000 constraints
from the 1,500 process models. As shown in Table 7, this includes more than
150,000 activity-level, almost 60,000 inter-object, more than 42,000 intra-
object constraints, and more than 3,000 role constraints. Per process model,
it extracted at most 662 activity-level constraints (104.0 on average), 416
inter-object constraints (54.1 on average), 366 intra-object constraints (33.3
on average), and 17 role constraints (6,3 on average).

Table 7: Characteristics of the constraints extracted from the model collection before collection refinement Const. type | Count | Avg. per model | Min./Max. per model
---|---|---|---
Activity | 150,082 | 104.0 | 2 / 662
Inter-object | 59,452 | 54.1 | 2 / 416
Intra-object | 42,377 | 33.3 | 3 / 366
Role | 3,349 |  56.3 | 0 / 17

After refinement, i.e., after equal or highly similar constraints were
standardized and weaker, redundant ones were filtered out, 55,913 activity-
level, 20,920 inter-object, 8,223 intra-object constraints, and 2,387 role
constraints remain, as depicted in Table 8. Many constraints were extracted
from multiple models, as shown by the number of constraints with a support of
$>1$. Notably, more than half of the intra-object constraints (4,484) were
extracted from multiple models, which suggests that these are more generally
applicable than the other types of constraints, for which this ratio is lower.

Table 8: Characteristics of the constraint collection after aggregation and refinement.  Const. type | Count | Support $>1$
---|---|---
Activity | 55,931 | 5,277
Inter-object | 20,920 | 2,965
Intra-object | 8,223 | 4,484
Role | 2,387 | 266

Overall detection results. Table 9 depicts the evaluation results per
configuration for detecting best-practice violations from the noisy logs,
averaged across logs. Our experiments showed that the performance trends per
configuration are always the same across folds. Moreover, we found that
weighing the semantic relevance $\omega$ with 0.9 for all constraint types
consistently yields slightly better results than weighing the support equally.
For the other parameters the variety of the performance achieved is more
substantial, though. Therefore, we report on results with $\omega=0.9$ here
for brevity.777Detailed results including all configurations can be found in
our repository.

Table 9: Results of detecting best-practice violations per constraint type for various configurations (averaged across logs). We generally favor high recall over high precision and the best trade-off between recall and precision per constraint type is printed in bold. $k$ determines the number of most relevant constraints selected per type. $\tau$ is a threshold for the minimum relevance score that a constraint must have to be selected. The weight factor of the relevance score, $\omega$, is set to 0.9 in all configurations. Type | Config. | TP | FP | FN | Precision | Recall
---|---|---|---|---|---|---
| $k$ | $\tau$ |  |  |  |  |
Activity | 10 | 0.5 | 77.10 | 62.04 | 91.90 | 0.70 | 0.51
100 | 0.5 | 134.22 | 230.83 | 34.78 | 0.43 | 0.82
250 | 0.5 | 139.80 | 286.17 | 29.20 | 0.39 | 0.84
| 10 | 0.8 | 54.54 | 24.82 | 114.46 | 0.86 | 0.35
| 100 | 0.8 | 80.08 | 76.61 | 88.92 | 0.75 | 0.49
| 250 | 0.8 | 80.27 | 79.64 | 88.73 | 0.74 | 0.49
Inter-object | 10 | 0.5 | 50.56 | 77.46 | 44.79 | 0.59 | 0.58
100 | 0.5 | 77.57 | 231.39 | 17.77 | 0.34 | 0.82
250 | 0.5 | 79.47 | 277.79 | 15.88 | 0.32 | 0.84
| 10 | 0.8 | 42.07 | 52.11 | 53.28 | 0.70 | 0.48
| 100 | 0.8 | 53.87 | 98.07 | 41.48 | 0.59 | 0.59
| 250 | 0.8 | 53.87 | 98.33 | 41.48 | 0.59 | 0.59
Intra-object | 10 | 0.5 | 51.69 | 26.46 | 39.53 | 0.84 | 0.70
100 | 0.5 | 68.64 | 131.71 | 22.58 | 0.72 | 0.79
250 | 0.5 | 69.55 | 172.97 | 21.67 | 0.70 | 0.79
| 10 | 0.8 | 46.74 | 21.26 | 44.48 | 0.86 | 0.59
| 100 | 0.8 | 58.47 | 94.93 | 32.75 | 0.78 | 0.65
| 250 | 0.8 | 58.80 | 104.46 | 32.42 | 0.77 | 0.65
Role | 10 | 0.5 | 6.51 | 16.73 | 4.96 | 0.60 | 0.57
100 | 0.5 | 9.01 | 37.39 | 2.46 | 0.49 | 0.80
250 | 0.5 | 9.08 | 38.31 | 2.39 | 0.49 | 0.80
| 10 | 0.8 | 4.39 | 8.47 | 7.08 | 0.78 | 0.38
| 100 | 0.8 | 4.77 | 10.78 | 6.69 | 0.76 | 0.41
| 250 | 0.8 | 4.77 | 10.78 | 6.69 | 0.76 | 0.41
Overall | 100 | 0.5 | 72,36 | 157,82 | 19.40 | 0.50 | 0.81

Overall, we find that both precision and recall vary considerably across
configurations (0.37–0.86 resp. 0.35–0.85). Because we generally favor high
recall over high precision when detecting best-practice violations, the best
out of the tested configurations, which achieves good recall while maximizing
precision is $k=100$ combined with a low relevance threshold ($\tau=0.5$) for
all constraint types. By picking this configuration, we achieve an average
precision of 0.50 and a recall of 0.81 across constraint types.888Note that,
while this configuration achieves the best results across constraint types, we
are not bound to using the same configuration per type. Selecting a high
relevance threshold ($\tau=0.8$) yields considerably lower recall scores
(0.35–0.65) compared to when using a lower threshold ($\tau=0.5$; 0.57–0.85).
This indicates that applying such a high relevance threshold is too
restrictive, causing a considerable amount of violations to remain undetected.

We also looked into per-log performance to get insights into how often our
framework achieves excellent, good, and poor performance. Figure 5 shows the
number of logs for which various performance levels are reached, using the
best configuration per constraint type ($k=100$, $\tau=0.5$). We find that our
framework achieved perfect precision and recall for a considerable number of
logs. Especially for intra-object constraints this was the case for more than
350 logs. For the other types the framework does not perform as well but still
for the vast majority, i.e., more than 90% of the logs, a recall (which is the
most important score) of more than 0.5 was achieved. Only for very few logs
both precision and recall are poor, i.e., both below 0.25.

Results per constraint type. To get a better understanding of when the
framework excels and when it fails, we next discuss the results per constraint
type by analyzing the impact of the parameter settings on performance and
inspecting the results achieved for individual event logs.

Figure 5: Number of logs for different performance levels per constraint type
(considering logs for which there were violations to be detected for the given
type of constraint); p=precision, r=recall, lower performance levels exclude
logs that are already included in higher ones.

Activity-level constraints. For activity-level constraints, the best
configuration achieves a moderate precision of 0.43 and a good recall of 0.82.
We find that we primarily obtain perfect scores for rather standard types of
processes, where organization-specific deviations are expected to occur rather
rarely. For instance, for an order-handling event log, all 246 violations were
correctly identified without any false positives, recognizing, e.g., that
_confirm order_ must precede _emit invoice_ , that _archive order_ should only
happen after _receive payment_ , and that _ship product_ should not occur
before _get shipment address_ if the latter occurs. The same applies to a
loan-application log, where for instance, _finalize loan application_ must
naturally not precede _create application_. Conversely, we find that logs for
which our framework achieved poor performance correspond to rather specialized
processes, for instance, for a log of a process that handles the calculation
of compensation during parental leave, our framework only achieved a precision
of 0.30 and recall of 0.56 and for a log that captures the interaction between
a technician and a pharmacist with a software system, we achieved a precision
of 0.20 and recall of 0.78. This indicates that activity-level constraints are
especially useful to detect violations in processes executed by many
organizations in similar ways, i.e., the main use case for reference process
models which our framework expects as input.

Inter-object constraints. For inter-object constraint, we observe similar
trends as for activity-level ones. The best configuration achieves a precision
of 0.34 and a recall of 0.82. For rather streamlined processes, such as a
claim-handling process, it correctly detects that a _claim_ should occur
before a _payment_ and that _payment_ and _claim rejection_ cannot co-occur.
Accordingly, in a travel booking process, it perfectly identifies that a
_plane ticket_ should be involved in a process before _luggage_ is and a
_destination_ should occur before there is a _plane ticket_. Larger numbers of
false positives are detected, for instance, when the process contains many
different object types and at the same time there is a lot of variability in
the process, i.e., many execution variants. For instance, in a log capturing a
heath-care process that spans multiple departments, 349 false positives
violations were found, compared to 75 true positive ones.

Intra-object constraints. When considering intra-object constraints, we
observe substantially better performance compared to the other constraint
types. The best configuration achieves a precision of 0.72 and a recall of
0.79. For more than 400 logs a perfect recall and a precision above 0.75 was
obtained at the same time. The reason for the better results compared to other
constraint types can also be observed by inspecting results of individual
logs. For instance, we achieve perfect recall and precision for a sales
process, for which, e.g., violations were found where an order was archived
before it was rejected, an order was both rejected and confirmed, and an order
was confirmed before it was received. Similarly, in a credit-application log
we found credits that are offered before they are checked and applications
that are never assessed. These examples show that our framework is capable of
identifying violations of general behavioral relations that make sense, such
as that an object should be created before it is checked.

However, there are also cases for which our framework fails for intra-object
violation detection, i.e., misses true violations. For instance, in an event
log that captures the process of candidate selection for scholarships. In the
process, candidates are first classified and later selected. Our framework
failed to recognize violations where one of these were missing or their order
was swapped causing false negatives. A possible reason for this may be the
similar meaning of the actions _select_ and _classify_ , which both describe
the separation of elements of a group [19]. Nevertheless, we found that intra-
object constraints provide a reliable means to detect best-practice violations
in the context of the same type of object.

Role constraints. For role constraints, the best configuration achieves a
precision of 0.49 and recall of 0.8. We also inspected logs for which role
constraints performed perfectly. For instance, in a credit-check process all
violations of wrong roles performing a task were correctly identified, e.g.,
that calling a client should be performed by _customer contact_ , whereas a
credibility check should be performed by _risk management_ and a payment
should be issued by _finance_. However, we also observed false positives. For
instance, for a log capturing the interaction of a pharmacist with an
information system that performs some tasks autonomously, such as sending and
processing notifications, the framework selected constraints that did not
correctly identify who (i.e., the pharmacist or the system) should perform
which steps of the process.

Main insights. Overall, we observe that with a relatively small number of
constraints, picked from a large collection of thousands of constraints per
type, we detect a substantial amount of true violations, achieving good recall
scores across constraint types. Yet, there are also false positives, which in
turn lead to lower precision scores. For the goal of detecting best-practice
violations allowing for false positives while minimizing false negatives can
be acceptable, though, given that a user of our approach can easily filter out
constraints that lead to false positives by selecting constraint components to
avoid when inspecting the detection results. The results must also be seen in
light of the fact that the underlying model collection varies in terms of
quality (despite the automated quality checks we performed), abstraction-
level, and modeling style. The insights from the individual logs suggest that
our framework works particularly well for processes that are commonly executed
in similar ways in organizations, which is exactly what we target by mining
constraints from reference process models. Expectedly, for more specialized
and niche processes the performance decreases.

Baseline comparison. Table 10 shows the results of the comparison against the
baseline. The comparison results presented here focus on intra-object
constraints, which the scope of the baseline is limited to. The baseline
achieves an average precision of 0.80 and recall of 0.20. Our framework
surpasses the baseline for all configurations in terms of recall: When
choosing the configuration that yields the best trade-off between precision
and recall ($k=100,\tau=0.5$), we achieve a slightly lower precision than the
baseline (0.72), but a recall of 0.79, which is almost four times higher.
Choosing a configuration with fewer constraints ($k=10,\tau=0.8$), we also
surpass the baseline in terms of precision (0.86), while the recall we achieve
with that configuration is still three times higher than the baseline’s
recall.

Our framework’s improved performance, especially in terms of recall, can be
attributed to its utilization of a broader range of constraints, resulting in
an increase in true positives and a decrease in false negatives. In
particular, the baseline focuses on detecting violations that depend on
pairwise relations between actions that are applied to the same object, e.g.
that _reject_ and _accept_ exclude each other. The declarative constraint
templates we use as a basis can also detect violations independent of such
pairwise relations. For instance, we can detect that an order was never
created independent of what happens to the order in the remainder of a trace,
whereas the baseline can only detect this based on other actions applied to
the order, e.g., if an _archive_ action is applied to the order and it
observed a relation _create_ is followed by _archive_. Nevertheless, despite
these improvements compared to the baseline, our framework detects a
substantial number of false positives, which needs to be addressed in future
work. Still, for the goal of detecting best-practice violations, our framework
is generally better suited than the baseline. This is because we do not want
users to miss potentially relevant violations; thus, it makes sense to
sacrifice precision for recall. Only when we do this, we achieve a somewhat
lower precision than the baseline, for the benefit of a much higher recall.

Table 10: Results of the baseline comparison only considering intra-object constraints (averaged across logs) Approach | TP | FP | FN | Precision | Recall
---|---|---|---|---|---
Ours (best trade-off) | 68.64 | 131.71 | 22.58 | 0.72 | 0.79
Ours (best precision) | 51.69 | 26.46 | 39.53 | 0.86 | 0.59
Baseline [18] | 35.56 | 26.16 | 55.66 | 0.80 | 0.20

Run time. We ran our experiments single-threaded on a laptop with a 2 GHz
Intel Core i5 processor and 16GB of memory. In this environment, the
constraint mining stage, which has to be run only once for a model collection,
took 112.5 minutes (99% of the time was used for constraint refinement). The
average time to run the selection and checking stages for a log was 72.9
seconds, varying between 19.4 and 167.6 seconds depending on the complexity of
the input event log, i.e., the number of activities and object types.

##  6 Real-life Application

Finally, we applied our framework to real-life event data of a purchasing
process and a sales process to highlight its usefulness in practical settings:

  1. 1.

_Purchasing process_. We use the BPI 2019 challenge [20], which captures event
data on a purchasing process at a multinational company. We selected those
traces from the original log that are supposed to adhere to a 3-ways-match
procedure where the invoice is to be recorded after goods receipt. The
resulting log contains 15,182 traces, 319,233 events, and 38 event classes.

  2. 2.

_Sales process_. We use a proprietary event log of a sales process. The
process instances were executed as part of a business-to-business software
sales process of a medium-sized European company. In this process, a lead
(customer contact) is generated and eventually converted into an opportunity
(lead with specific purchase scenario) that is then either closed or turned
into a paying customer. This event log cannot be shared for privacy-related
ethics and compliance reasons.

For the real-life application scenarios we employed a proprietary reference
model collection of ca. 4,000 BPMN models that provide vendor-specific best
practices.

Results. We discuss the results obtained for the purchasing process and the
sales process separately.

Purchasing process. Although there is no gold standard available that
indicates best-practice violations in this process, our framework was able to
detect a range of potentially undesired behaviors, as shown in Table 11.

ID |  Constraint |  Constraint explanation | #Violations
---|---|---|---
p1 |  Response(_create_ , _confirm_)$\mid$_invoice_ |  After an _invoice_ is _created_ , it should be _confirmed_. | 10,722
p2 |  Succession(_goods receipt_ , _invoice_) |  An _invoice_ occurs iff it is followed by a _goods receipt_. | 9,601
p3 |  AtLeastOne(_create_)$\mid$_invoice_ |  For an _invoice_ , _create_ should occur. | 940
p4 |  Response(_purchase order item_ , _goods receipt_) |  A _goods receipt_ should follow a _purchase order item_. | 638
Table 11: Exemplary best-practice constraints that were selected by our
framework and the number of traces that violated them in the real-life
purchasing event log.

The examples correspond to situations where an invoice is never created (p3),
where purchase order items are never followed by goods receipt (p4), and
invoices that are created but never confirmed (p1). All of these issues
represent behavior that deviates from best practices extracted from a high-
quality reference model collection that includes models for purchasing,
invoicing, and payment processes. Most interestingly, in a considerable amount
of traces a good receipt is not followed by an invoice (p2), which violates
the underlying matching procedure, where invoices should be recorded after
goods are received. These may include incomplete traces, yet, may also hint at
undesired behavior, which is worth investigating further.

Sales process. For the sales process event log we also found some best-
practice violations based on constraints recommended by our framework as shown
in Table 12. In particular, there are traces where a lead is never created
(s4) and assigned more than once or never (s1). Furthermore, there is a
considerable amount of opportunities that are never closed (s2) and activities
in the process that are recorded but not documented properly afterwards (s3).
A discussion with a technical process operations specialist confirmed that all
of these violations indicate lacking process discipline in the affected
traces, i.e., these do not adhere to established procedures, which may cause
efficiency and quality issues in the process. The violations, thus, provide
valuable insights into process improvement opportunities.

ID |  Constraint |  Constraint explanation | #Violations
---|---|---|---
s1 |  ExactlyOne(_assign_)$\mid$_lead_ |  For a _lead_ , _assign_ should occur once. | 220,057
s2 |  ExactlyOne(_close_)$\mid$_opportunity_ |  For an _opportunity_ , _close_ should occur once. | 11,175
s3 |  AlternateResponse(_activity logged task_ , _enter notes_) |  _Activity logged task_ should be followed by _enter notes_. | 9,228
s4 |  AtLeastOne(_create_)$\mid$_lead_ |  For a _lead_ , _create_ should occur. | 418
Table 12: Exemplary best-practice constraints that were selected by our
framework and the number of traces that violated them in the real-life sales
process event log.

These insights further highlight the benefits of our framework to detect
potentially undesired behavior that violates best-practices without the need
for dedicated process models to be available.

##  7 Related Work

In this section, we discuss the primary research streams to which our work
relates: conformance checking, declarative process mining, and process
matching.

Conformance checking. Conformance checking is one of the main tasks of process
mining, aiming to detect deviations between true behavior recorded in event
logs and desired behavior captured in a process model [2, 21]. If the input
models capture rules or regulations, conformance-checking techniques can thus
be used for process compliance checking, where violations of these shall be
detected [22]. Most research on conformance checking focuses on scenarios
where an event log and a dedicated imperative process model, e.g., a BPMN
diagram, are available. In this context, conformance is commonly checked based
on so-called alignments [23, 24], where observed traces are compared with
executions allowed by a predefined process model to find deviations. In the
context of declarative models, conformance checking boils down to checking for
each trace in an event log, if it satisfies each constraint in a declarative
process model [6, 8]. To get a global view on conformance, the idea of
aligning log traces to the closest _model trace_ (considering all model
constraints) can also be lifted to a declarative setting [25]. In our
framework, we adopt the former approach, though, because we do not check
conformance against a given normative (declarative) model. Instead, we
mitigate the need for such a dedicated model and rather check against a
collection of relevant, yet individual, best-practice constraints, essentially
querying the event log (cf. [26]) for violating traces.

Declarative process mining. Declarative process mining is an active research
field and we refer the interested reader to a recent overview of the topic
[6]. In this context, Declare is among the most prominent formalisms. It
relies on LTL, leveraging its reasoning mechanisms for, among others, model
analysis and conformance checking, which we utilize in our framework. Research
in this area is also dedicated to identifying and resolving inconsistencies
and redundancies in declarative process models [10, 27, 14], which we leverage
for both refining our constraint collection in the _Constraint Mining_ stage
of the framework and for checking if the set of recommended constraints is
actually consistent in the _Constraint Selection_ stage.

Recently, _object-centric behavioral constraints_ have been proposed, which
allow for a detailed specification of complex networks of objects and their
relations that co-evolve in one or multiple processes [28]. While still in its
infancy [6], this line of research is promising to be adopted for our
framework. The level of detail this formalism can express goes beyond what is
typically captured in BPMN diagrams, though. Therefore, we would first need to
extend the scope of the input of our framework, which we aim to address in
future work.

Research on declarative process mining further focuses on discovering
declarative models from event logs [29, 30]. In this context, measuring the
interestingness of traces of an event log given a declarative process model
[31] and vice versa [32] is researched. This closely relates to the notion of
relevance we employ in our framework, where we essentially want to assess how
interesting a constraint is for a given log. Complementary to existing
approaches, we consider semantic similarity as an indicator of
interestingness.

Process matching. Process matching techniques revolve around establishing
connections between process concepts found in various artifacts. The primary
research focus lies in process model matching, where the objective is to
create links between activities present in different process models. To
achieve this, process model matchers leverage diverse process model features
including model structure [33] and allowed behavior [34], but also natural-
language-based features [35]. Beyond model-to-model matching, there is also
work on matching (parts of) models to events recorded in event logs [36, 37].
The selection stage of our framework also creates links between components of
the constraints and event log counterparts based on semantic similarity in
order to select the most relevant constraints for the given log.

##  8 Conclusion

Summary. In this paper, we propose a framework to mine declarative constraints
from reference process models to detect best-practice violations in event
logs. Our framework extracts and refines constraints based on imperative
models, instantiates and selects relevant constraints given an event log, and
checks whether the process executions recorded in the log violate the best-
practices captured by the constraints. In this manner, we mitigate the need
for process models specifically designed to capture the desired behavior of
the process recorded in the given event log. Our experiments show that with a
small number of constrains, which our framework selects from a collection of
tens of thousands of mined constraints, we correctly detect a substantial
amount of violations. Furthermore, application scenarios based on real-life
reference models and event logs demonstrate the framework’s usefulness in
practical settings.

Limitations. Our framework and evaluation are subject to certain limitations.
First, our framework does not cover constraints for all process perspectives,
excluding constraints related to the time and data perspectives from
consideration, e.g., that an order should be approved within a given amount of
time or that a specific check should be performed for orders of a certain
value. This is because such constraints are rarely found in reference process
models, whereas they are also much harder to generalize than our activity-,
object-, and role-related ones, because restrictions on time and monetary
values can differ substantially across organizations and processes. Second, in
order to provide relevant best-practice violations, the event log is assumed
to be on the same granularity level as the components of constraints the
framework mined. If the event log records activities on a more fine-granular
level, it may, therefore, be necessary to first abstract the event log before
applying our framework. With respect to our evaluation, there are certain
threats to validity. A threat to internal validity is that the process models
used as a basis for our experiments, although being real-life models, stem
from different sources and were established for different purposes, which
means that they jointly do not represent a reference model collection (due to
the absence of publicly available reference collections). Despite automated
quality checks, the contained models may thus vary in terms of quality,
granularity, and modeling style. A threat to external validity is the
(currently) limited application of our framework in practice. While we applied
it on real-life event data, which yielded interesting best-practice violations
that were verified with a specialist, it has not been field-tested in an
organization so far.

Future work. In future work, we aim to address the aforementioned limitations
of the framework and its evaluation, as well as provide further extensions.
This primarily includes the following. First, we aim to broaden the scope of
input beyond imperative process models, for instance by leveraging data models
like entity-relationship diagrams and database schemata for constraint mining,
since these can give complementary insights into relationships between
individual objects. On the output side, we aim to extend the framework to
provide insights about potential root causes of violations by connecting
violated constraints with shared parameters to each other. For instance, given
two violated constraints, where one captures that an invoice should be checked
at least once and the other one that an invoice should be checked before it is
approved, we aim to derive that a missing invoice check is the cause of both
violations. Finally, we aim to implement the framework into a tool including a
graphical user interface. This will allow users to adapt and specify their own
constraints according to their needs, based on event data and mined
constraints, as well as to analyze constraints and their violations in a more
interactive manner. Based on this tool, we aim to conduct a user study asking
users to apply the framework in an organizational setting using their own
event logs in order to further assess the practical value of our work.

## References

  * [1] W. M. van der Aalst, Process mining: a 360 degree overview, in: Process Mining Handbook, Springer, 2022, pp. 3–34.
  * [2] J. Carmona, B. van Dongen, A. Solti, M. Weidlich, Conformance checking, Springer, 2018.
  * [3] M. Dumas, M. La Rosa, J. Mendling, H. A. Reijers, et al., Fundamentals of business process management, Vol. 2, Springer, 2018.
  * [4] P. Fettke, P. Loos, Classification of reference models: a methodology and its application, Information systems and e-business management 1 (2003) 35–53.
  * [5] F. Gottschalk, W. M. van der Aalst, M. H. Jansen-Vullers, Mining reference process models and their configurations, in: OTM Workshops, Springer, 2008, pp. 263–272.
  * [6] C. D. Ciccio, M. Montali, Declarative Process Specifications: Reasoning, Discovery, Monitoring, Vol. 448 of Lecture Notes in Business Information Processing, Springer, 2022, pp. 108–152.  doi:10.1007/978-3-031-08848-3\\_4.
  * [7] M. Pesic, H. Schonenberg, W. M. Van der Aalst, Declare: Full support for loosely-structured processes, in: 11th IEEE international enterprise distributed object computing conference (EDOC 2007), IEEE, 2007, pp. 287–287.
  * [8] A. Burattin, F. M. Maggi, A. Sperduti, Conformance checking based on multi-perspective declarative process models, Expert systems with applications 65 (2016) 194–211.
  * [9] A. Rebmann, H. van der Aa, Enabling semantics-aware process mining through the automatic annotation of event logs, Inf. Syst. 110 (2022) 102111.  doi:10.1016/j.is.2022.102111.
  * [10] C. Di Ciccio, F. M. Maggi, M. Montali, J. Mendling, Resolving inconsistencies and redundancies in declarative process models, Information Systems 64 (2017) 425–446.  doi:https://doi.org/10.1016/j.is.2016.09.005.
  * [11] N. Reimers, I. Gurevych, Sentence-bert: Sentence embeddings using siamese bert-networks, in: K. Inui, J. Jiang, V. Ng, X. Wan (Eds.), EMNLP 2019, Association for Computational Linguistics, 2019, pp. 3980–3990.  doi:10.18653/v1/D19-1410.
  * [12] G. A. Miller, Wordnet: a lexical database for english, Communications of the ACM 38 (11) (1995) 39–41.
  * [13] S. Nagel, P. Delfmann, Investigating inconsistency understanding to support interactive inconsistency resolution in declarative process models, in: ECIS 2022, Timisoara, Romania, 2022.
  * [14] C. Corea, S. Nagel, J. Mendling, P. Delfmann, Interactive and minimal repair of declarative process models, in: BPM Forum 2021, Rome, Italy, Springer, 2021, pp. 3–19.
  * [15] D. Sola, C. Warmuth, B. Schäfer, P. Badakhshan, J.-R. Rehse, T. Kampik, SAP Signavio academic models: A large process model dataset, in: ICPM Workshops, Springer, 2023, pp. 453–465.
  * [16] A. Berti, S. J. Van Zelst, W. van der Aalst, Process mining for python (pm4py): bridging the gap between process-and data science, arXiv preprint arXiv:1905.06169 (2019).
  * [17] I. Donadello, F. Riva, F. M. Maggi, A. Shikhizada, Declare4py: A python library for declarative process mining, Proceedings of the Best Dissertation Award, Doctoral Consortium, and Demonstration & Resources Track at BPM (2022) 117–121.
  * [18] H. van der Aa, A. Rebmann, H. Leopold, Natural language-based detection of semantic execution anomalies in event logs, Inf. Syst. 102 (2021) 101824.  doi:10.1016/j.is.2021.101824.
  * [19] T. Malone, K. Crowston, G. Herman, Organizing business knowledge: The MIT process handbook, MIT press, 2003.
  * [20] B. van Dongen, BPI Challenge (2019).  doi:10.4121/uuid:d06aff4b-79f0-45e6-8ec8-e19730c248f1.
  * [21] M. Bauer, H. van der Aa, M. Weidlich, Sampling and approximation techniques for efficient process conformance checking, Information Systems 104 (2022) 101666\.
  * [22] F. Caron, J. Vanthienen, B. Baesens, Comprehensive rule-based compliance checking and risk management with process mining, Decision Support Systems 54 (3) (2013) 1357–1369.  doi:https://doi.org/10.1016/j.dss.2012.12.012.
  * [23] A. Adriansyah, B. F. van Dongen, W. M. van der Aalst, Conformance checking using cost-based fitness analysis, in: 2011 ieee 15th international enterprise distributed object computing conference, IEEE, 2011, pp. 55–64.
  * [24] W. Van der Aalst, A. Adriansyah, B. Van Dongen, Replaying history on process models for conformance checking and performance analysis, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 2 (2) (2012) 182–192.
  * [25] M. de Leoni, F. M. Maggi, W. M. van der Aalst, An alignment-based framework to check the conformance of declarative process models and to preprocess event-log data, Information Systems 47 (2015) 258–277.  doi:https://doi.org/10.1016/j.is.2013.12.005.
  * [26] A. Polyvyanyy, C. Ouyang, A. Barros, W. M. van der Aalst, Process querying: Enabling business intelligence through query-based process analytics, Decision Support Systems 100 (2017) 41–56, smart Business Process Management.  doi:https://doi.org/10.1016/j.dss.2017.04.011.
  * [27] C. Corea, J. Grant, M. Thimm, Measuring inconsistency in declarative process specifications, in: BPM 2022, Münster, Germany, Springer, 2022, pp. 289–306.
  * [28] A. Artale, D. Calvanese, M. Montali, W. M. van der Aalst, Enriching data models with behavioral constraints., Ontology Makes Sense 316 (2019) 257–277.
  * [29] F. M. Maggi, R. J. C. Bose, W. M. van der Aalst, Efficient discovery of understandable declarative process models from event logs, in: CAiSE 2012, Gdansk, Poland, Springer, 2012, pp. 270–285.
  * [30] C. D. Ciccio, M. Mecella, On the discovery of declarative control flows for artful processes, ACM Transactions on Management Information Systems (TMIS) 5 (4) (2015) 1–37.
  * [31] A. Cecconi, C. Di Ciccio, G. De Giacomo, J. Mendling, Interestingness of traces in declarative process mining: The janus LTLp approach, in: BPM, Springer, 2018, pp. 121–138.
  * [32] A. Cecconi, G. De Giacomo, C. Di Ciccio, F. M. Maggi, J. Mendling, Measuring the interestingness of temporal logic behavioral specifications in process mining, Information Systems 107 (2022) 101920.
  * [33] R. Dijkman, M. Dumas, B. Van Dongen, R. Käärik, J. Mendling, Similarity of business process models: Metrics and evaluation, Information Systems 36 (2) (2011) 498–516.
  * [34] M. Kunze, M. Weidlich, M. Weske, Behavioral similarity–a proper metric, in: BPM 2011, Clermont-Ferrand, France, Springer, 2011, pp. 166–181.
  * [35] M. Ehrig, A. Koschmider, A. Oberweis, Measuring similarity between semantic business process models, in: APCCM, Vol. 7, 2007, pp. 71–80.
  * [36] T. Baier, J. Mendling, M. Weske, Bridging abstraction layers in process mining, Information Systems 46 (2014) 123–139.
  * [37] H. Van Der Aa, A. Gal, H. Leopold, H. A. Reijers, T. Sagi, R. Shraga, Instance-based process matching using event-log information, in: CAiSE 2017, Essen, Germany, Springer, 2017, pp. 283–297.