Process model comparison based on cophenetic distance

Process Model Comparison Based on Cophenetic Distance David S´ anchez-Charles1, Victor Munt´ es-Mulero1, Josep Carmona2 1CA Strategic Research Labs, CA Technologies, Spain {David.Sanchez,Victor.Muntes}@ca.com 2Universitat Polit` ecnica de Catalunya, Spain [email protected] Summary. The automated comparison of process models has received increasing attention in the last decade, due to the growing existence of process models and repositories, and the consequent need to assess similarities between the underlying processes. Current techniques for process model comparison are either structural (based on graph edit distances), or behavioural (through activity profiles or the analysis of the execution semantics). Accordingly, there is a gap between the quality of the information provided by these two families, i.e., structural techniques may be fast but inaccurate, whilst behavioural are accurate but complex. In this paper we present a novel technique, that is based on a well-known technique to compare labeled trees through the notion of Cophenetic distance. The technique lays between the two families of methods for comparing a process model: it has an structural nature, but can provide accurate information on the differences/similarities of two process models. The experimental evaluation on various benchmarks sets are reported, that position the proposed technique as a valuable tool for process model comparison. 1 Introduction Nowadays process models are ubiquitous objects in companies and organizations. They are becoming precious for representing unambiguous and detailed descriptions of real processes. On the one hand, BPMS platforms, which allow designing, deploying and managing the processes in organizations, are based on process models. On the other hand, evidence-based process models (i.e., process models with a high alignment with respect to the underlying real process) can be used to analyze the process formally, e.g., detecting inconsistencies or performance problems that may hamper the correct and optimal execution of the process. Furthermore, the existence of environments for creating, managing and querying process model collections enable the hierarchical and cross-organizational analysis, with process models as atomic objects. A core technique necessary in many of the aforementioned situations is the automated comparison of process models. Due to its importance, this problem has received significant attention in the BPM field, which can be split into structural techniques based on graph-edit distance [8, 9, 10, 18], and behavioural techniques that focus on the execution semantics or behavioural relations of the corresponding models [1, 7, 13, 16, 17]. Intuitively, structural techniques are fast but inaccurate (in terms of the differences found), whereas pure behavioural techniques are complex (both in computation time and memory usage) but accurate. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45468-9_9 2 S´ anchez-Charles et al. In this paper we propose a novel method to compare process models1. The technique is based on a recent algorithm [5] from the field of computational phylogenetics, where the objects to compare are labeled trees showing the inferred evolutionary relationships among various biological species. We adapt the algorithm to the BPM context, thus using process trees [4] as notation. Our proposed similarity metric sits halfway between pure structural similarity methods (inheriting their low complexity features), and behavioural similarity metrics (capable of providing similar behavioural information). Moreover, the performance of our approach allow us to consider this metric for large process models. The paper is organized as follows: next section provides an intuition of the metric over a realistic example. In Section 3 the necessary preliminaries are provided. Then in Section 4 we present the main contribution of the paper: a similarity metric for deterministic process trees. The deterministic restriction is dropped in Section 5, giving rise to a heuristic technique that relies on an approximate matching algorithm. The techniques of the paper are evaluated thoroughly in Section 6. Finally, Section 7 concludes the paper and provides pointers for future investigations. 2 Motivating Example Let us use a real-life example to motivate the contributions of this paper. A product manager decides to monitor all accesses to an SVN repository. Those accesses are done through HTTP/S, as specified in the WebDAV/DeltaV protocol. It turns out that those read and write requests over HTTP/S can be translated to human-friendly SVN commands such as svn update or svn commit. Continuing the work done by Li Sun et.al. [15], the product manager plans to model the developer’s behaviour based on the SVN commands they execute daily. Our goal is to measure the differences between those models, inducing a behavioural distance between individuals. This way, intruder attacks to the repository can be detected globally by analyzing process behaviour that is clearly separated from the rest. Fig. 1. Two process models describing how two users access an SVN repository. 1We assume the problem of dealing with real activity labels, e.g., when the name of an activity in the models does not perfectly match, is resolved prior to the techniques of this paper. Process Model Comparison Based on Cophenetic Distance 3 Figure 1 depicts the access behaviour of two users to the same repository, using a block-structured process discovery algorithm2. In our preliminary study, the process model of an average user shows lots of concurrency, duplicate activities and iterative behaviour3. Existing behavioural comparison techniques struggle when dealing with such models. Either they fall short in describing duplicate activities and loops [16], or the underlying technique does not scale in the presence of concurrent process branches [1]. OR LOOP SEQ A OR SEQ B LOOP S1 OR LOOP SEQ S2 OR SEQ LOOP S3 OR LOOP SEQ S4 OR LOOP LOOP A B Subprocess 1 Subprocess 2 (LCA) (LCA) Fig. 2. Extract of the tree representation of the two processes in Figure 1. Only the subtrees related to two common activities Aand Bare represented, and their least common ancestors are depicted in bold. Activities Siare unrelated to Aand B. The approach presented in this paper evaluates the difference of the two minimum subtrees containing a selected pair of activities, and extends the comparison to all possible pairs. Analysis over such subtrees is expected to be more simple and efficient, while still capable of comparing both the structure and behaviour of the two processes. See Figure 2 for an example, which focuses on activities Aand Bin both models. One can check that the difference between the depth of the two activities is an approximation to the graph distance between those two models. For instance, in Figure 2, depths of Aare 11 in the first subprocess and 4in the second subprocess, whilst depths of Bare 11 and 6. The difference of their depths sum 12, implying that 8nodes must be removed and 2 extra edges are needed in order to transform one model into the other. Besides, and more importantly, one can see that the common ancestors of activities Aand Bin Figure 2 model two different behaviours: On the first subprocess, activities Aand Bare mutually exclusive; On the second, Ais executed after activity B. Notice that the depth of this common ancestor also highlights how long it takes to make the behavioural decision of how activities Aand Brelate to each other. Therefore, by incorporating these notions into the distance function, we would be able to not only measure structural differences but also highlight differences in the behaviour of two process models. For instance, one could obtain the sentence: Activities Aand Bin Figure 2 are mutually exclusive in the first subprocess, but activity Aalways occurs after Bin the second subprocess. Besides, the behavioural decision in the first subprocess is done 6steps after the decision is taken in the second subprocess. 2We used Discover a Process Tree using Inductive Miner (ProM 6.5) and then converted them to Petri Nets. 3The most common sequence of commands in the dataset is svn -options,svn update,svn - options indicating they use an IDE that overwrites the SVN options just to perform an update and then returns to its previous status. 4 S´ anchez-Charles et al. 3 Background 3.1 Process Trees: a Tree-like Representation of Business Processes Arooted tree is a directed graph with a distinguished node, called the root, from which every node can be reached with exactly one path. A weighted rooted tree is a pair (T, ω)consisting of a rooted tree Tand a weight function ω:E→R>0that associates every arc e∈Ea non-negative real number ω(e)>0. A labeled rooted tree is a rooted tree Tsuch that there exists a mapping between a subset of the nodes of the tree and a set of labels S. Let T= (V, E)be a rooted tree. Whenever (u, v)∈E, we say that vis a child of uand that uis the parent of v. The nodes without children are the leaves of the tree, and the other nodes are called internal. Whenever there exists a path from a node uto a node v, we say that vis a descendant of uand also that uis an ancestor of v. An internal node is elementary if it only has one child. The depth of a node uin a tree T, denoted by δT(u), is the sum of the weights of the arcs in the path from the root to u. Weights are usually set to 1, but we will later see that we can encode behavioural information from the process by modifying these weights. Definition 1 ([4]). Aprocess tree is a labeled rooted tree Tin which activities are represented as leaves of the tree and internal nodes describe the control-flow of the process. We say that a process tree is deterministic if there is a one-to-one mapping between activity labels and leaves of T. For the sake of simplicity, we will label internal labels as OR4,AND,SEQ and LOOP to represent the usual behavioural structures in a process model. We will also denote these internal nodes by gateways, following the BPMN nomenclature. We allow silent activities by labeling them as ∅. Definition 2. A process tree is reducible if there are elementary nodes, silent transitions hanging over a gateway other than OR, or there exist a pair of internal nodes uand v such that (u, v)is an edge in the graph and both model the same type of gateway. Any reducible process tree can be converted into an irreducible tree by merging all conflicting nodes. We will suppose that all process trees are given in its irreducible form. Figure 3 depicts an example of a reducible process tree and its irreducible counterpart. SEQ SEQ A B ∅OR C SEQ A B C Fig. 3. Two process trees modeling exactly the same behaviour. The left model is reducible, and the right model is its irreducible representation. The silent transition ∅is removed because it is not part of an OR structure. The OR elementary node does not provide behavioural information. 4Following the semantics of block-structured models in [4], only exclusive ORs are modeled. Process Model Comparison Based on Cophenetic Distance 5 3.2 Cophenetic vectors The least common ancestor (LCA) of a pair of nodes uand vof a rooted tree T, denoted by [u, v]T, is the unique common ancestor of them that is a descendant of every other common ancestor. The definition of the Cophenetic vector is based on the discrepancies on the depth of the LCA of every pair of activities. Definition 3 ([14]). Let Sbe the set of labels of a weighted labeled rooted tree T. For every pair of different labels i,j, their Cophenetic value is ϕT(i, j) = δT([u, v]T)u, v have labels i, j To simplify notation, we denote the depth of a node with label iby ϕT(i, i), and ϕT(i, j)=0if either ior jare not activities of the process tree T. Definition 4. Let Tbe a weighted rooted tree, and Sthe set of activity labels of the tree T, its Cophenetic vector is ϕ(T)=(ϕT(i, j))i,j∈S SEQ1 OR2 A3B3 AND2 OR3 C4D4 E3 T1)A B C D E A 3 2 1 1 1 B 3 1 1 1 C 4 3 2 D42 E3 A B C D E A 3 2 1 1 1 B 3 1 1 1 C 4 2 3 D32 E4 SEQ1 AND2 A3B3 AND2 OR3 C4E4 D3 T2) Fig. 4. Example of process trees and their Cophenetic vector (in matrix representation), assuming the depth of the root is 1. For simplicity, we included node’s depth as a subscript of the label. For instance, the LCA of activities Cand Ein T1is the AND gateway that is one children of the root and, hence, its Cophenetic value is 2. In an already fifty years old paper [14], Sokal and Rohlf proposed the use of the cophenetic values to compare dendrograms. Authors in [5] show that cophenetic values can also be applied to uniquely project labelled trees into a multidimensional vector space, allowing them to define a distance on labelled trees as Theorem 1 states. Theorem 1 ([5]). Two weighted labeled trees without elementary nodes, unlabeled leaves nor repeated labels are equal if, and only if, they share the same Cophenetic vector. Cophenetic vectors are not enough for determining process tree similarity: for instance, in Figure 4 if the OR and AND labels of the left tree are interchanged, the Cophenetic vectors of both trees are equal whilst the behaviour represented is different. Besides, constraints in Theorem 1 do not allow models with multiple silent transitions. Next section shows how to transform process trees in order to overcome this limitation. 6 S´ anchez-Charles et al. 4 Distance between Deterministic Process Trees 4.1 Cophenetic Distance definition As we have seen, Cophenetic values unequivocally represents weighted labeled rooted trees. As it is well known, this allows to induce distance metrics in the set of labeled trees. Let dist be any distance between two points in a vectorial space, we define d(T, T0) = dist(ϕ(T), ϕ(T0)) as the distance between two trees. For instance, by using the L1-norm we get d1(T, T0) = X i,j∈S |ϕT(i, j)−ϕT0(i, j)| The Cophenetic values were originally conceived to measure structural differences between the leaves of two dendograms, but we can extend its use to deterministic process trees thanks to Theorem 1. This result allow us to modify the depth of each node in order to model the path of gateways we are tracing from the root to activities (the leaves of the tree). In Definition 5 we propose a depth function to overcome the following weaknesses of the original Cophenetic distance over labelled trees: (1) ensures that non-common activities increases the distance between two models; (2) depth of activities in a sequential order increase in the same sequential order, modeling the complexity of the blocks already seen by the process; (3) allows for silent transitions; and (4) differentiates two processes with the same structure but modeling different gateways at the root. Definition 5. Let Tbe a deterministic process tree. We define the depth function δ0 Tas follows: 1. Root node has depth 1. 2. Iterate over all nodes in a pre-order traversal. 3. The depth of all nodes is 1plus the depth of its parent, except a) If the parent is an OR clause, increase 0.5instead of 1. b) If the activity is silent, increase 0.25 the depth of the parent and any other sibling. Afterwards, remove the silent activity. c) If the parent is the start of a LOOP, increase also by the maximum depth of the underlying tree. d) If the parent is a SEQ gateway, consider the depth of deepest visited children of the node’s siblings instead of the parent. 4. Any remaining elementary node will be removed, and its parent and children will be directly connected. For the sake of simplicity, trf(T)will denote the combination of the tree Twith the aforementioned depth function δT. Figure 5 depicts the transformation of the two processes in Figure 4. With the aforementioned depth function, Cophenetic values now highlight, for example, differences in the two activities Aand Bdue to the behavioural change of their parent node. This transformation allow us to overcome the limitations of Theorem 1, since silent transitions are allowed, but also by ordering children of sequential gateways. As we state in Theorem 2, this transformation uniquely represents deterministic process trees. Process Model Comparison Based on Cophenetic Distance 7 SEQ1 OR2 A2.5B2.5 AND3.5 OR4.5 C5D5 E4.5 T1)A B C D E A2.5 2 1 1 1 B2.5 1 1 1 C5 4.5 3.5 D 5 3.5 E4.5 A B C D E A32 1 1 1 B3111 C5.5 4 5 D 5 4 E5.5 SEQ1 AND2 A3B3 AND4 OR5 C5.5E5.5 D5 T2) Fig. 5. Transformation of the process trees in Figure 4. For the sake of simplicity, we included node’s depth as a subscript of the label. For instance, depth of the AND gateway in T1is 3.5 because its parent represents a sequence and the maximum depth of the previous processed branch is 2.5 Theorem 2. Let Tand T0be two deterministic process trees. If trf(T)and trf(T0) share the same Cophenetic vector, then Tand T0are the same process tree. This theorem shows that Theorem 1 is also applicable to the new depth definition, and therefore useful for checking equality of two process trees and measuring differences between the models. The proof of this theorem is based on the observation that the Cophenetic values of any subtree are highly related to the Cophenetic values of the complete tree, as Lemma 1 shows. Details of the proof of this lemma are omitted, but it is a direct consequence of the pre-order traversal approach of Definition 5. Lemma 1. Let Tbe a weighted rooted tree, and Sa subtree of T. Then the Cophenetic vector of Ssatisfies that ϕS(i, j) = ϕT(i, j)−δ0 T(root of S)+1 Proof (Theorem 2). Let’s proof this by induction. – For processes with 1 or 2 activities, one can list all possible deterministic process trees and check that no two processes share the same transformed tree. – For processes with n > 2activities, we will show that every strict subtree5of Tis equal to another subtree of T0. Let V T be a strict subtree of T. Suppose Aand B are two activities such that [A, B]Tis the root of V T . Activities Aand Bare also included in the deterministic process tree T0, and [A, B]T0is the root of a certain subtree V T0. T . . .. . . [A,B]T A . . . B . . . T’ . . .. . . [A,B]T0 A . . . B . . . Lemma 1 ensures that 5Here a strict subtree of Tis any subtree that does not contain the root of T 8 S´ anchez-Charles et al. ϕV T (i, j) = ϕT(i, j)−δ0 T([A, B]T)+1 =ϕT0(i, j)−δ0 T([A, B]T0) + 1 = ϕV T 0(i, j) where the second equality holds since trf(T) = trf(T0)and Theorem 1. And therefore, V T and V T0share the same Cophenetic vector and its size is smaller than T and T0. By induction, we can say that both process trees are equal. There is one case where there are no two activities Aand Bsuch that [A, B]Tis the root of V T: The root of V T is an OR-clause, and one children is a silent transition. In this particular case, we can work with the non-silent children V Tns. The combination of two consecutive OR conditions is not possible in a valid deterministic process tree, and therefore V Tns falls under the proved assumption. Hence, there is a subtree V T0 ns of T0that is equal to V Tns. T . . .. . . VT(=OR) ∅VTns . . . T’ . . .. . . X VT’ns C . . . V Tns and V T0 ns share the same activities, and V Tns is a strict subtree of T. Therefore, V T0 ns is also a strict subtree of T0. Let Xbe its parent node. We will show that Xis in fact an OR condition, and it only has another silent branch. Let’s assume there exists an activity Cunder Xbut not included in V T 0 ns. There are two options: –Xis the root of T0. In that case, we can replace the subtrees V Tns and V T0 ns by a mock activity C0. We reduced the problem to the 2activities case, already solved. In that case, we share the same Cophenetic value but the two process trees are different (T0does not have a silent transition). We arrived to this contradiction by assuming that Cexists. –Xis not the root of T0. In that case, the subtree V X induced by the node Xis a strict subtree of T0and Xis not and OR condition. By applying the previous reasoning, there is a subtree Wof Tthat is equal to V X and includes V Tns. Notice that, in that case, the only possibility is that Cis a silent transition. This shows that any subtree of Tis equal to a certain subtree of T0. By applying this result to all the direct children of the root of Tone can see that Tand T0are indeed equal. ut 4.2 Behavioural information captured by Cophenetic values The syntax of process trees allow us to easily check the direct causality of two activities in the model: one simply needs to check the behaviour explained by their LCA. Cooccurrence of activities is described by an AND gateway, whilst OR internal nodes induce conflict between their underlying activities. Notice that this causal relation is a property for the minimum subtree containing the pair of activities. For instance, if the two activities are inside a bigger loop structure, we would not be able to retrieve this information due to the loop gateway being some levels above the LCA. Process Model Comparison Based on Cophenetic Distance 9 To provide a more global information than the local direct causality, depths given by Definition 5 can be used. They summarize the behavioural situation of the given node. See, for instance, the processes of Figure 5. Depth of activity Dcould be seen as the sum of the blocks found from the root to the node. δT1(D) = 1(root)+2.5(Seq) + 1(And)+0.5(Or) δT2(D) = 1(root) + 3(Seq) + 1(And) δT1(D)−δT2(D) = (1 −1)(root) + (2.5−3)(Seq) + (1 −1)(And) + (0.5)(Or) =−0.5(Seq)+0.5(Or)(1) Notice that by considering the difference of the two depths, i.e. the value considered by the Cophenetic distance, we start highlighting where are the differences, and the type of changes committed, of the behaviour up to activity D. When comparing pairs of activities, the cophenetic distance does not only consider the depth of the two activities but also the LCA. Following the previous example, let’s compare activity Dwith C: δT1(C)−δT2(C) = (1 −1)(root) + (2.5−3)(Seq)(2) + (1 −1)(And) + (0.5−0.5)(Or) =−0.5(Seq)(3) δT1([C, D]T1)−δT2([C, D]T2) = (1 −1)(root) + (2.5−3)(Seq) + (1 −0)(And) =−0.5(Seq) + 1(And)(4) The Cophenetic value of Cstores the differences on the previous block in the sequence, as it did with Activity D. Besides, the Cophenetic value of activities Cand Dcaptures again the difference in the sequence and also an AND gateway. Hence, the pair of activities Cand Dare a step closer to the end in one of the two process models. But more interesting properties could be extracted by measuring the difference of such Cophenetic values: Whilst the cophenetic value δT1([C, D])−δT2([C, D]) gives an idea of the difference of the two processes up to the LCA [C, D], these two new values provides the same differential analysis on the paths from the ancestor to the activities. In this example, (2) −(3) = 1 indicates that the position of Cwith respect to their common ancestor differ in the insertion of an AND gateway; whilst in the case of activity D, (1)−(2) = 0.5recognizes that an OR gateway has been added, or replaced by an AND, in one of the models. This example shows the potential of the LCA, and the Cophenetic values, to generate more understandable and user-friendly comparison tools between process trees. Definition 6 shows two possible sentences we could build thanks to this information. Definition 6. A set of human-readable differences can be generated using the Cophenetic values. – Given a pair of activities Aand Bsuch that they differ in the behaviour explained by their LCA. We could say that ”In the first model, Activities Aand Bare (in sequential order / co-occurrent / conflict). Whilst they are (in sequential order / co-occurrent / conflict) in the second model. Besides, the position of this behavioural decision differ in δT1([A, B]) −δT2([A, B]) units.” 16 S´ anchez-Charles et al. 6. Thomas Curran, Gerhard Keller, and Andrew Ladd. SAP R/3 business blueprint: understanding the business process reference model. 1997. 7. Remco M. Dijkman. Diagnosing differences between business process models. In BPM 2008, Milan, Italy, September 2-4, pages 261–277, 2008. 8. Remco M. Dijkman, Marlon Dumas, and Luciano Garc´ ıa-Ba˜ nuelos. Graph matching algorithms for business process model similarity search. In BPM 2009, Ulm, Germany, September 8-10, pages 48–63, 2009. 9. Remco M. Dijkman, Marlon Dumas, Luciano Garc´ ıa-Ba˜ nuelos, and Reina K¨ a¨ arik. Aligning business process models. In EDOC 2009, 1-4 September 2009, Auckland, New Zealand, pages 45–53, 2009. 10. Remco M. Dijkman, Marlon Dumas, Boudewijn F. van Dongen, Reina K¨ a¨ arik, and Jan Mendling. Similarity of business process models: Metrics and evaluation. Inf. Syst., 36(2):498–516, 2011. 11. Ranjitha Kumar, Jerry O. Talton, Salman Ahmad, Tim Roughgarden, and Scott R. Klemmer. Flexible tree matching. In Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011), 2011. 12. Adria Alcala Mena and Francesc Rossell´ o. Ternary graph isomorphism in polynomial time, after luks. CoRR, abs/1209.0871, 2012. 13. Artem Polyvyanyy, Matthias Weidlich, Raffaele Conforti, Marcello La Rosa, and Arthur H. M. ter Hofstede. The 4c spectrum of fundamental behavioral relations for concurrent systems. In PETRI NETS 2014, Tunis, Tunisia, June 23-27, pages 210–232, 2014. 14. F. James Rohlf Robert R. Sokal. The comparison of dendrograms by objective methods. Taxon, 11(2):33–40, 1962. 15. Li Sun, Serdar Boztas, Kathy Horadam, Asha Rao, and Steven Versteeg. Analysis of user behaviour in accessing a source code repository. Technical report, RMIT University and CA Technologies, 2013. 16. Matthias Weidlich, Jan Mendling, and Mathias Weske. Efficient consistency measurement based on behavioral profiles of process models. IEEE Tr. Soft. Eng., 37(3):410–429, 2011. 17. Matthias Weidlich, Artem Polyvyanyy, Jan Mendling, and Mathias Weske. Causal behavioural profiles - efficient computation, applications, and evaluation. Fundam. Inform., 113(3-4):399–435, 2011. 18. Zhiqiang Yan, Remco M. Dijkman, and Paul W. P. J. Grefen. Fast business process similarity search. Distributed and Parallel Databases, 30(2):105–144, 2012.