Traces via Abstract Argumentation⋆

Abstract

Monitoring and analyzing process traces (i.e. event sequences) is an important task in modern companies and organizations. Focusing on scenarios where there is an abstraction gap between trace events and reference business activities, we here consider the interpretation problem of translating the current event generated by an ongoing trace into the step of the activity instance it corresponds to. We briefly discuss how this problem can be encoded into an Abstract Argumentation Framework (AAF), which allows for computing and exploring event interpretations by solving instances of the AAF acceptance problem.

1. Introduction

Process Mining methods help better understand and enact business processes by supporting various analysis tasks over process traces, i.e. sequences of execution events, e.g. process-model 3 =post-surgery, while 4 can be performed only during activity 2. To reconstruct/monitor patient histories, one needs to interpret such a trace in terms of activity executions. However, due to the many-to-many event-activity mapping, even if trace Φ described a completed process instance, multiple interpretations could exist for Φ, like: 1 ≡ “ 1, 2, 3 is the sequence of steps produced by an instance of 1 and 4 is the unique step of an instance of 2”; and 2 ≡ “ 1, 2 and 3, 4 are the step sequences produced by instances of 1 and of 2, respectively”. □

Such an abstraction gap limits the usefulness of process discovery methods, and impedes using standard conformance-checking ones. Thus, supervised log abstraction methods were proposed recently [ 2 ], which try to interpret log traces automatically as executions of given high-level process activities, leveraging domain knowledge. However, these methods sufer from two limitations: () they map each (low-level) event to just one activity, discarding alternative interpretations of ; () they do not provide explanations for their results.

In [ 1 ], we defined a framework that supports interactive explorative analyses of any lowlevel trace Φ, which allow the user to obtain answers and explanations for Interpretation Queries over Φ. Technically, the underlying event-interpretation problem is encoded into an Abstract Argumentation Framework (AAF ) (see Section 2), so that both interpretation queries and associated explanations are computed by solving instances of the AAF acceptance problem. This extended abstract summarizes some major features of the framework introduced in [ 1 ].

2. Background and problem statement

AAF basics An AAF can be viewed as a graph where nodes and edges model arguments and attacks from an argument to another, respectively. Given argument set and argument , we say that “ attacks ” (resp., attacks ) if there is an argument in such that attacks (resp., attacks ). Given arguments , such that attacks , an argument is said to “defend ” if attacks . Argument set is said to “defend ” if contains some argument defending . Argument is acceptable w.r.t. if every argument attacking is attacked by , while is conflict-free if there is no attack between its arguments. Diferent semantics have been proposed to identify “reasonable” sets of arguments, called extensions [ 3 ], in an AAF. In particular, a set ⊆ is said to be an admissible extension if is conflict-free and all its arguments are acceptable w.r.t. . An admissible extension that is maximal (w.r.t. ⊆) is a preferred extension. Acceptance of an argument in an AAF can be stated under both skeptical and credulous perspectives. In particular, adopting the preferred semantics (as in [ 1 ]), is credulously accepted (resp., skeptically accepted), if it belongs to at least one (resp., every) preferred extension of . The interpretation problem Given an ongoing trace Φ, as soon as a new event curr appears in Φ, we want to interactively support the analyst in obtaining () answers to Interpretation Queries on the alternative valid interpretations of curr , and () explanations for certain interpretations considered not valid, where interpretation validity descends from well-structuredness properties and given domain knowledge (described later on). Roughly speaking, basic interpretation queries allow for asking whether curr can be viewed as a step of an instance of a given activity , possibly stating conditions on the activity lifecycle (e.g.,“is curr the initial step of an instance of ?” or on the activity occurrence (e.g., “is curr a step of the 2nd instance of ? ”). Any such a query can be evaluated under skeptical semantics, in order to know whether the proposed interpretation is the unique valid one for curr . Moreover, enumeration queries ask for all valid interpretations of curr satisfying the conditions required.

Two kinds of domain knowledge are considered in the above-described problem: () the list of high-level activities in terms of which events must be interpreted, along with the candidate type-level mappings between these activities and log events; () a declarative process model consisting of activity constraints, including temporal rules of the forms ∶ ⇒ 1| … | (must-constraint) and ∶ ⇒ ¬ (not-constraint), for any given activities , , and time period ∈ [1..∞] , and their respective time-symmetric versions (i.e., positive and 1, … , negative “precedence” constraints). (resp., ) means that an instance must (resp., cannot) be followed by an instance of one of the activities 1, … , (resp., of activity ) in steps. In Example 1, one could use such a constraint to model known behaviors like that 2 is always preceded by 1 immediately; if also knowing that 1 must start with Blood sample taken and end with Blood pressure measurement, this allows for discarding interpretations like 1.

3. Overview of the Solution Approach

The core problem of computing valid (w.r.t. domain knowledge) interpretations of events in a trace Φ is modelled as a dispute via an ad hoc AAF (Φ) = ⟨ Arg, Att ⟩, on top of which interpretation queries and explanation requests can be answered. (Φ) is built incrementally by adding arguments of the following kinds (and attacks between them) as a new step of Φ arrives: 1) Interpretation arguments of the form ⟨ , , , ⟩ , where is an activity label, is a positive integer and ∈ { first , intermediate, last, first&last } indicates a life-cycle execution stage for . Such an argument encodes the interpretation of as a step of type of the -th execution instance of activity . Interpretation 1 in Example 1 can be encoded via interpretation arguments ⟨ 1, , 1⟩⟨

1, , 1⟩⟨ 2) Undermining arguments of five diferent forms: 1, , 1⟩⟨ 2, &, 1⟩ . pretation has been chosen for step Φ[] ; () NotEnoughExecutions , where = ⟨ , , , ⟩ ∈ { first , first&last }, meaning that ’s interpretation of as the start of the -th instance of contrasts with interpreting no previous step as the start of the (−1) -th instance of ; () with NotStarted , where = ⟨ , , , ⟩

with ∈ { intermediate, last}, meaning that ’s interpretation of as a non-initial step of the -th instance of contrasts with interpreting no previous step as the start of the -th instance of ; ( )

NotEnded(, ) , where is an instance counter and an activity, meaning that the trace has terminated and some event was interpreted as the initial step of the -th instance of , but no event has been interpreted as the last step of this instance; ( ) , descending from some must-constraint ∶ ⇒ 1| … | , and meaning that the -th event of Φ cannot be interpreted as the final step of an instance of , for no subsequent event (in steps) has been interpreted as the start of an instance of some . Clearly, the AAF includes several conflicting event interpretations, encoded by interpretation arguments with mutual attacks, e.g.: ′ and ″ (representing alternative interpretations of the same event), ′ and ″ (interpreting distinct events as first steps of the first instance of ), and () NotInterpreted , meaning that no inter... NotEnoughExecutions '

NotStarted '

NotInterpreted5 ''= ...

MC15

... '''=< e6, A, intermediate, 1> ''=... ′ and ‴ (where ‴ interprets 6 as a step of an instance interpreted as closed by ).

As an example of how the AAF ensures activity counters to be consistent, consider NotEnoughExecutions ′, which attacks ′ and it is counter-attacked by ′.

Importantly, the AAF enforces the choice of an interpretation for each trace step. In particular, it contains exactly one argument NotInterpreted for each step , that is attacked by the interpretation arguments over the same step and that attacks the interpretation arguments over the immediately preceding and following steps −1 and +1 .

The AAF also ensures that activity instances can be prolonged only if previously started. For example, in Fig. 1, ′ interprets 5 as a non initial step of the first instance of and is attacked by NotStarted′, and is defended from this attack by ′ and ″, that interpret some previous steps as the starting steps of the same instance of .

All the constraints in the given declarative process model are enforced as well. For instance, in Fig. 1, the must-constraint 1 ∶ ⇒ 1 (triggered by argument ′ over step 5) is encoded by the undermining argument 15 and the attacks ( 15, ′) and ( ′, 15).

Further attacks are included to guarantee that ∅ is the only admissible extension of (Φ) if there is no valid interpretation of Φ (i.e. trace behavior deviates from the process model). This is the case of self-attacks on all NotInterpreted and the special attack from NotInterpreted1 towards each argument of type NotEnoughExecutions, NotStarted, NotEnded.

It was proven in [ 1 ] that there is a biunivocal correspondence between the set of valid interpretations of Φ and the set of preferred extensions of (Φ) , so one can reason on the interpretations of the current event curr by deciding the acceptance of interpretation arguments over curr . Details on the computation of the AAF (Φ) and of answers to interpretation queries and associated explanation requests can be found in [ 1 ].

References

[1] B. Fazzinga , S. Flesca , F. Furfaro , L. Pontieri, Process mining meets argumentation: Explainable interpretations of low-level event logs via abstract argumentation , Information Systems 107 ( 2022 ). doi:h t t p s : / / d o i . o r g / 1 0 . 1 0 1 6 / j . i s . 2 0 2 2 . 1 0 1 9 8 7 .

[2] S. J. van Zelst , F. Mannhardt , M. de Leoni , A. Koschmider, Event abstraction in process mining: literature review and taxonomy , Granular Computing 6 ( 2021 ) 719 - 736 .

[3] P. M. Dung , On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games , Art. Int . 77 ( 1995 ) 321 - 358 .