Model and Event Log Reductions to Boost the Computation of Alignments

Abstract

The alignment of observed and modeled behavior is a pivotal issue in process mining because it opens the door for assessing the quality of a process model, as well as the usage of the model as a precise predictor for the execution of a process. This paper presents a novel technique for reduction of a process model based on the notion of indication, by which, the occurrence of an event in the model reveals the occurrence of some other events, hence relegating the later set as less important information when model and log alignment is computed. Once indications relations are computed in the model, both model and log can be reduced accordingly, and then fed to the state of the art approaches for computing alignments. Finally, the (macro)-alignment derived is expanded in these parts containning high-level events that represent a set of indicated events, by using an e cient algorithm taken from bioinformatics that guarantees optimality in the local parts of the alignment. The implementation of the presented techniques shows a signi cant reduction both in computation time and in memory usage, the latter being a signi cant barrier to apply the alignment technology on large instances.

-

Nowadays many systems generate event logs, which are footprints left by process executions. Process mining delves into this information, and examines it to extract, analyze and enhance evidence-based process models [ 10 ]. One of the challenges in process mining is how to align a process model to a set of traces forming an event log. Given a trace representing a real process execution, an optimal alignment provides the best trace the process model can provide to imitate the observed trace [ 1 ]. Alignments are crucial for important metrics like tness, precision and generalization [ 1,2 ].

This paper presents a model-based technique for reduction of a process model and observed behavior that both preserves the semantics of the process model and retains the information of the original observed behavior as much as possible. The technique is meant to ght the main problem current approaches for alignment computation have: the complexity both in space and time. The overall idea relies on the notion of indication between activities of the process model when it is represented as a Petri net. An indication relation between a set of transitions (indicated set) and another transition (indicator) denotes a causal ring relation in the model, which expresses that the presence in any model's sequence of the indicator transition requires the presence of the indicated set as well. The notion of indication is inspired from the reveals relation from [ 3 ]. We use a well-known technique to nd logically independent parts of a graph (known as SESEs in [ 7 ]), which are then used to gather indication relations e ciently. These relations dictate which parts of a process model are abstracted as a single, high-level node. Once the model is reduced, the observed trace to align is projected (hence, reduced as well) into the reduced model's alphabet. This way, not only the model but also the trace are reduced, which in turn makes the alignment techniques to be signi cantly alleviated, specially for well-structured process models where many indication relations may exist. Once alignments are computed, the nal step is also an interesting contribution of this paper: to cast the well-known Needleman{Wunsch algorithm [ 6 ] to expand locally each high-level part of the alignment computed, using the indication relation. 2

Related Work

The seminal work in [ 1 ] proposed the notion of alignment, and developed a technique to compute optimal alignments for a particular class of process models. For each trace in the log, the approach consists on exploring the synchronous product of model's state space and . In the exploration, the shortest path is computed using the A algorithm, once costs for model and log moves are dened. The approach is implemented in ProM, and can be considered as the state-of-the-art technique for computing alignments. Several optimizations have been proposed to the basic approach to speed up and improve memory consumption. The recent work in [ 9 ] proposed a divide and conquer strategy based on Integer Linear Programming (ILP) approach to compute approximate alignments. Despite its memory and time e ciency, it cannot guarantee the obtention of an (optimal) alignment.

The work in [ 5 ] presented a decomposition approach using SESEs for conformance checking of the model and observed behavior. The proposed approach decomposes a given model to smaller parts via SESE and then applies conformance checking for each part independently. This technique is very e cient, but the result is decisional (a yes/no answer on the tness of the trace). Recently [ 12 ] proposed a new approach which provides an algorithm that is able to obtain such an optimal alignment from the decomposed alignments if this is possible, which is called proper optimal alignment. Otherwise, it produces a so-called pseudo-alignment which as in the case of [ 9 ], may not be executable in the net.

The seminal work [ 4 ] rst introduced the notion of reveals relation, which determines that whenever an action a happens, then the occurrence of another action b is inevitable. The notion of indication of this paper is inspired on the reveals relation.

The Re ned Process Structure Tree (RPST), proposed by [ 11 ], is a graph parsing technique that provides well-structured parts of a graph. The resulting parse tree is unique and modular, i.e., local change in the local work ow graph results in a local change of the parse tree. It can be computed in linear time using the method proposed in [ 8 ] which is based on the triconnected components of a given biconnected graph. The proposed approach only works with single sink, single source work ow graphs which hampers its applicability to real world problems with many sink, source nodes. The work in [ 7 ] presents a more e cient way to compute RPST which can deal with multiple source, sink work ow graphs. 3

Preliminaries

A Petri Net is a 3-tuple N = hP; T; F i, where P is the set of places, T is the set of transitions, P \ T = ;, F : (P T ) [ (T P ) ! f0; 1g is the ow relation. Marking of a Petri net represents the number of tokens each place has. Given a node x 2 P [ T , its pre-set and post-set (in graph adjacency terms) are denoted by x and x respectively. WF-net is a Petri net where there is a place start (denoting the initial state of the system) with no incoming arcs and a place end (denoting the nal state of the system) with no outgoing arcs, and every other node is within a path between start and end. Fig. 1(a) represents a WF-net. Given an alphabet of events T = ft1; : : : ; tng, a trace is a word 2 T that represents a nite sequence of events. An event log L 2 B(T ) is a multiset of traces1. An alignment is represented by a two-row matrix where the top and bottom rows represent moves on log and the model respectively. For example given trace t1t4t2t5t8 and the model in Fig. 1(a), an example of alignment is: = t1 ? t4 t2 t5 ? t8

t1 t2 t4 ? t5 t7 t8

Let F E represents a set of edges of a directed graph hV; E; `i, GF = hVF ; F i is the subgraph formed by by F if VF is the smallest set of nodes such that GF is a subgraph. A node in VF is boundary with respect to GF if it is connected to nodes in VF and in V VF , otherwise it is interior. A boundary node u of GF is an entry node if no incoming edge of u belongs to F or if all outgoing edges of u belong to F . A boundary node v of GF is an exit node of GF if no outgoing edge of v belongs to F or if all incoming edges of v belong to F . GF with one entry and one exit node is called SESE. If a SESE contains only one edge it is called trivial. A SESE of G is called canonical if it does not overlap with any other SESEs of G, but it can be nested or disjoint with other SESEs. For example in Fig. 1(b) all SESEs are canonical, S2 and S4 are nested, S3 and S2 are disjoint. A WF-net can be viewed as a Work ow graph if no distinctions are made between its nodes. WF-graph of Fig. 1(a) is presented in Fig. 1(b). Let G be a graph, then its Re ned Process Structure Tree (RPST) is the set of all canonical SESEs of G. Because canonical fragments are either nested or disjoint, they form a hierarchy. In a typical RPST, the leaves are trivial SESE and the root is the whole graph. Fig. 1(c) is the RPST of WF-graph in Fig. 1(b), 1 B(A) denotes the set of all multisets of the set A. S1 which is the entire graph is at root and leaves are trivial SESEs which only contain one edge. Given a process model N , represented by a Petri net, and as observed behavior, the strategy of this paper is sketched in Fig. 2. We now provide descriptions of each stage. { Model Reduction: N will be reduced based on the notion of indication relation which results in Nr. It contains some abstract events representing the indicators of certain indicated sets of transitions. Section 5.1 explains it in detail. { Log Reduction: Using the indication relations computed in the model, is projected into the remaining labels in Nr, resulting in r. Section 5.2 describes this step. { Computing Alignment : Given Nr and r, approaches like [ 1 ] and [ 9 ] can be applied to compute alignments. At this point because both Nr and r contain abstract events, the computed alignment will have them as well. We call it macro-alignment. { Alignment Expansion: For each abstract element of a macro-alignment, the modeled and observed indications are confronted. Needleman{Wunsch algorithm [ 6 ] is adapted to compute optimal alignments. Section 6 will be centered on this. 5 5.1

Reduction of Model and Observed Behavior

The Indication Relation Let us consider the model in Fig. 1(a). For any sequence of the model, whenever transition t4 res it is clear that transitions t1, t3, and t2 have red as well. Formally: De nition 1 (Indication Relation). Let N = hP; T; F i, 8t 2 T , indication is de ned as a function, I(t) where, I : T ! [P (T )+]+ I(t) such that for any sequence 2 L(N ), if t 2 then I(T ) 2 . If I(t) = !1!2:::!n, then elements of !m precede the elements of !n in for 1 m < n. I(t) is called linear if it contains only singleton sets, i.e. 8!i 2 I(t); j!ij = 1 otherwise it is non-linear. For example in Fig. 1(a), I(t4) = ft1gfft2g; ft3ggft4g (non-linear) and I(t8) = ft7gft8g (linear). SESEs are potential candidates for identifying indication relations inside a WF-net: the exit node of a SESE is the potential indicator of the nodes inside the SESE. Since entry/exit nodes of a SESE can be either place or transitions, SESEs are categorized as Fig. 3: Linear SESEs and their reduction. (P; P ), (P; T ), (T; P ) or (T; T ). In case the SESE is linear, indication relations can be extracted easily and the corresponding SESE is reduced (see Fig.3).

Non-linear cases are decomposed into linear ones so that indication relations can be computed directly on the linear components extracted. After that, the indication relation of the corresponding linear SESEs are computed and they are reduced as well. This procedure should be done with caution to avoid reaching a deadlock situation. Hence a post veri cation must be done after reduction of these linear parts. Informally, the veri cation is only needed for particular type of linear SESEs ((T; T )), and consists on validating the property of the SESE after the reduction. Notice the veri cation is necessary in these cases because, nonlinear SESEs may contain linear indications at nested level, but which cannot be extracted due to choice or loop constructs (see See Fig. 4). accordingly and post veri cation will be done after each reduction to check that no deadlock arises. One can see all reductions will be pass the veri cation, except for S7, whose reduction induces a deadlock. Applying the reduction once, results in Fig. 7(b). As mentioned earlier, the reduction can be applied more than once until no reduction can be made. Fig. 7(c) is the reduction of the model in Fig. 7(b) and it is clear that no more reduction can be made from this model. Given a reduced model Nr and , we show how to produce r. We will use the reduced model in Fig. 7(b) and the trace 1 = t1t5t3t11t10t21t6t2t7t16t25t19t20t26. The indication of t5(New) in Fig. 7(b) which is linear, equals to ft5gft15g. So the observed indication for this abstract node is 1#I(t5(new)) = t5. After computing the observed indication the reduced trace is t1t5(new)t3t11t10t21t6t2t7t16t25 t19t20t26. For t17(New), I(t17(New)) = ft3gfft10g; ft11ggft17g, which is non-linear and merged of two linear indications, I1(t17(New))=ft3gft10gft17g andI2(t17(New))= ft3gft11gft17g. So the projection must be done for each linear indication separately, 1#I1(t17(New)) = t3t10 and 1#I2(t17(New)) = t3t11, removing transitions t3, t10, t11 and t17 from the current trace (notice that t17 does not appear originally, hence it is not projected). Finally, we need to insert t17(New) into the reduced trace; it will be inserted at the position of t10, because the end transition of the abstract node, i.e. t17 did not happened in , and t10 happened last in . Therefore the reduced trace so far is t1t5(new)t17(new)t21t6t2t7t16t25 t19t20t26. By applying this process for the rest of abstract nodes (t16(New), t22(New)), we reach r = t1t5(new)t17(new)t21t16(New) t22(New)t26. After reducing a given process model and corresponding observed behavior, we can use current methods for computing alignments [ 1,9 ] to align Nr and r, deriving r. For example the following is the macro alignment of 1r = t1t5(new)t17(new)t21t16(New) t22(New)t26 and the model in Fig. 7(b). r= t1 t5(New) t17(New) t21 ? ? t16(New) t22(New) t26 t1 ? t17(New) t21 t24 t5(New) t16(New) t22(New) t26

When mapped to linear indications, indication of an abstract node and the corresponding observed indication are both sequence of events; hence for each linear combination of modeled/observed indication, we can adapt the dynamic programming approach from [ 6 ] (used in bioinformatics) to align two sequences. As example, we use indication of t17(New) and its observed indication computed in the previous section.

To achieve this goal, we create a table for each linear indication, where the rst row and column are lled by observed and abstract node indications respectively, as depicted in Table 1(a), 1(b). The second row and second column are initialized with numbers starting from 0,-1,-2,..., they are depicted in yellow color. The task then is to ll the remaining cells as follows: SIM (ti; tj)= M AX(SIM (ti 1; tj 1) + s(ti; tj); SIM (ti 1; tj) 1; SIM (ti; tj 1) 1) Where SIM (ti; tj ) represents the similarity score between ti and tj . s(ti; tj ) is the substitution score for aligning ti and tj , it is 0 when they are equal and 1 otherwise.

The nal step in the algorithm is the trace back for the best alignment. In the above mentioned example, one can see the bottom right hand corner in for example Table 1, score as -1. The important point to be noted here is that there may be two or more alignments possible between the two example sequences. The current cell with value -1 has immediate predecessor, where the maximum score obtained is diagonally located and its value is 0. If there are two or more values which points back, suggests that there can be two or more possible alignments. By continuing the trace back step by the above de ned method, one would reach to the 0th row, 0th column. Following the above described steps, alignment of two sequences can be found.

Alignments can be represented by a sequence of paired elements, for example 1 = (t3; t3)(t11; t11)(?; t17), 2 = (t3; t3)(t10; t10)(?; t17) and nal alignment which represent the non-linear indication is = (t3; t3)f(t11; t11); (t10; t10)g(? ; t17). This information is booked for each abstract node.

After computing local alignments for abstract nodes, we can use them to expand corresponding abstract nodes in a given r. The policy of expansion depends on whether the abstract node is in synchronous or asynchronous move.

In r, t17(New) is in a synchronous move so we can expand it by its local alignment, which results in: = t1 t5(New) t3 t11 t10 ? t21 ? ? t16(New) t22(New) t26 t1 ? t3 t11 t10 t17 t21 t24 t5(New) t16(New) t22(New) t26 The same story also happens for t16(New) and t22(New), which results in: = t1 t5(New) t3 t11 t10 ? t21 ? ? t6 t2 t7 ? ? t16 t25 t19 t20 ? t26 t1 ? t3 t11 t10 t17 t21 t24 t5(New) ? t2 t7 t6 t8 t16 t25 t19 t20 t22 t26 On the other hand t5(New) in r is a asynchronous move both on the model and observed trace. The policy of expansion is to expand move on log and move on model independently. To put it in another way, move on log will be expanded using observed indication and move on model will be expanded using the abstract node' indication, which results: The technique presented in this paper has been implemented in Python as a prototype tool. The tool has been evaluated over di erent family of examples, alongside with the state of the art techniques for computing alignments [ 9 ] (ILP:R), [ 1 ] (A ). We used benchmark datasets from [ 9 ], [ 5 ], and a new dataset. Reduction of Models. Table 2 provides the results of one-time reduction by applying the proposed method to benchmark datasets. Signi cant reductions are found often. Obviously one can see that the results of reduction is more representative for models without loops or contain small loops, like (Banktransfer ). Quality of Alignments. Since the alignment technique ILP:R may be approximate, Table 3 provides an overview of how many of the computed alignments can be replayed for ILP:R method when combined with the technique of this paper2.

Comparing with Original Alignments. Table 4 reports the evaluation of the quality of the results for both approaches [ 1 ], [ 9 ] with and without applying the technique of this paper. Columns ED/Jaccard report the edit/Jaccard distance between the sequences computed, while MSE columns reports the mean square root error between the corresponding tness values. Edit distances are often large, but interestingly this has no impact on the tness, since when expanding abstract nodes although the nal position may di er, the model still can replay the obtained sequences very often.

Memory Usage. The memory usage of computing alignments using [ 1 ], is reduced signi cantly. For large models, prDm6, prFm6, prGm6, M6, M10, it can only compute alignments if applied in combination of the technique of this paper. Computation Time Comparison. Fig. 8(a)-(b) report computation times for BPM2013 and other benchmark datasets respectively. It is evident that A approach combined with the proposed method is signi cantly faster than the other approach in nearly all datasets except (prGm6, prDm6, M6, M10). Still A approach cannot compute alignments for models M6 and M10 even after applying the presented technique, and in that case the combination of ILP:R with the presented technique is the best choice. 8

Conclusion and Future Work

We have presented a technique that can be used to signi cantly alleviate the complexity of computing alignments. The technique uses the indication relation 2 Expanded alignments provided by A were replayed 100% for all datasets

Fig. 8: Computation time for (a) BPM2013 and (b) synthetic datasets. to abstract unimportant parts of a process model so that global computation of alignments focus on a reduced instance. The reduced part of computed alignments then will be expanded to represent local deviations as well. Experiments are provided that witness the capability of the technique when used in combination with state-of-the-art approaches for alignment computation. Future work will be devoted to apply the technique on more unstructured inputs.

References

1. Arya Adriansyah . Aligning observed and modeled behavior . PhD thesis , Technische Universiteit Eindhoven, 2014 .

2. Arya Adriansyah , Jorge Munoz-Gama, Josep Carmona, Boudewijn F. van Dongen , and Wil M. P. van der Aalst . Measuring precision of modeled behavior . Inf . Syst. E-Business Management , 13 ( 1 ): 37 { 67 , 2015 .

3. Sandie Balaguer , Thomas Chatain, and Stefan Haar . Building occurrence nets from reveals relations . Fundam . Inform., 123 ( 3 ): 245 { 272 , 2013 .

4. Stefan Haar . Unfold and Cover: Qualitative Diagnosability for Petri Nets . In Proceedings of the 46th IEEE Conference on Decision and Control (CDC'07) , pages 1886 { 1891 , New Orleans, LA, USA, United States , 2007 . IEEE Control System Society.

5. Jorge Munoz-Gama , Josep Carmona , and Wil M. P. Van Der Aalst . Single-entry single-exit decomposed conformance checking . Inf. Syst. , 46 : 102 { 122 , December 2014 .

6. Saul B. Needleman and Christian D. Wunsch . A general method applicable to the search for similarities in the amino acid sequence of two proteins . Journal of Molecular Biology , 48 ( 3 ): 443 { 453 , 1970 .

7. Artem Polyvyanyy , Jussi Vanhatalo, and Hagen Volzer. Simpli ed computation and generalization of the re ned process structure tree . In 7th International Conference on Web Services and Formal Methods, WS-FM'10 , pages 25 { 41 , Berlin, Heidelberg, 2011 .

8. Robert E. Tarjan and Jacobo Valdes . Prime subprogram parsing of a program . In Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '80 , pages 95 { 105 , New York, NY, USA, 1980 . ACM.

9. Farbod Taymouri and Josep Carmona . A recursive paradigm for aligning observed behavior of large structured process models . In 14th International Conference of Business Process Management (BPM) , Rio de Janeiro, Brazil, September 18 - 22 , 2016 .

10. Wil M. P. van der Aalst. Process Mining - Discovery , Conformance and Enhancement of Business Processes. Springer, 2011 .

11. Jussi Vanhatalo , Hagen Volzer, and Jana Koehler. The re ned process structure tree . In Proceedings of the 6th International Conference on Business Process Management, BPM '08 , pages 100 { 115 , Berlin, Heidelberg, 2008 . Springer-Verlag.

12. H. M. W. Verbeek and W. M. P. van der Aalst . Merging Alignments for Decomposed Replay , pages 219 { 239 . Springer International Publishing, Cham, 2016 .