Business process models are the conceptual models that explicitly represent the business operations of an enterprise. These models are widely accepted as a useful resource for a variety of purposes ranging from representing requirements for software development to configuring ERP systems. Process Model Matching (PMM) refers to identifying the activities between two process models that represent similar or identical functionality [1]. A pair of activities that represent similar or identical functionality is called a corresponding pair and the involved activities are called corresponding activities [2]. Figure 1 shows the example process models of two universities, University A and University B, and correspondences between their activities. In the figure, each correspondence between a pair of activities is marked by a shaded area. An accurate identification of corresponding activities is of higher significance for the BPM community due to its widespread application areas, such as identifying clones of process models, searching process models and harmonizing process models [3]. To that end, a plethora of automatic techniques have been proposed [4]. Despite the existence of several matching techniques, the need for enhancing the accuracy of matching techniques has been widely pronounced during the recent years [4,5]. For instance, a comprehensive survey of the state-of-the-art has made imperative revelations about process model matching techniques [5]. The two notable ones are, 1) 21 out of 35 techniques use the most basic syntactic measures, and 2) Lin similarity is the most prominent semantic similarity measure. In this study we contend that there are several word-level semantic similarity measures that have shown promising results for various text processing tasks [6,7]. However, an empirical assessment of these competing measures has never been conducted in the context of process model matching. Consequently, a well-grounded recommendation about the choice of a semantic similarity measure is non-existent. Furthermore, the presently used similarity measures merely focus on the word-to-word semantic similarity, without paying adequate attention to the aggregation of word-level similarity scores to an activity-level similarity score. This arbitrary selection of sentence-level aggregation method, such as average score, may impede the effectiveness of the matching techniques. To that end, in this study we evaluate the effectiveness of five WordNet-based word-to-word semantic similarity measures and three sentencelevel methods, which extend word-level semantic similarity scores to an activity-level similarity score. The effectiveness of all (fifteen) combinations of five word-level semantic similarity measures and three sentence-level methods are evaluated using the three PMMC'15 datasets.
The rest of the paper is organized as follows: Section 2 provides an overview of the word-level and sentence-level semantic similarity measures. Section 3 and 4 presents the experimental setup and results of the experiments, respectively. Section 5 provides an overview of the related work. Finally, Section 6 concludes the paper.
The semantic similarity methods that we have applied for identifying corresponding activities between process models are based on WordNet. WordNet is widely acknowledged as a valuable source to find semantic similarity between two words as it organizes words based on lexical relations and then defines semantic relations between those lexically related synsets. The lexical relationships are categorized into two subcategories: synsets, and antonyms, whereas semantic relations are categorized into five sub categories: hyponyms, meronyms, co-ordinate terms, entailment of a verb, and troponym of a verb. Synsets are related with other synsets to form a hierarchical structure of conceptual relations. In the WordNet version 2.0, there are nine noun hierarchies that include 80,000 concepts and 554 verb hierarchies that are made up of 13,500 concepts. All the concepts are linked to a unique root, called entity.
Word-level Semantic Similarity Measures
We have selected five well established and widely used word-level semantic similarity measures to compute the degree of semantic similarity between activity pairs. These are: Resnik similarity [7], Jiang similarity [8], Leacock similarity [6], Lin similarity [9], and Wu similarity [10]. The methods have been previously used for lexical and textual semantic relatedness [11,13], word sense disambiguation [12], gene and sequence matching [14], generating sentences from pictures [15], paraphrasing [16], sentiment analysis [17] and topic modeling [18,19]. A brief overview of these measures is as follows:
Resnik Similarity. Resnik similarity relies on is-a relationship in the WordNet taxonomy, where each node represents a unique WordNet synset or concept. According to this measure two nodes are considered more similar if they share more information. This shared information is specified by Information Content (IC) of the nodes that subsumes these nodes in a taxonomy. Formally, IC is calculated as follows: πΌπΆ = β πππ π(πΆ) Let C1 and C2 be the two concept nodes in WordNet taxonomy and concept node C is the lowest common subsumer node of nodes C1 and C2. Furthermore, let P(C) is the probability of occurrence of longest common subsumer node C and probability of node C is simply found by normalizing occurrences of concepts with total number of nouns in the taxonomy.
Where, W(C) is the set of concepts in which word w occurs and each occurrence of a word is considered as occurrence of all concepts containing that word. The Resnik similarity is referred as maximal IC over all concepts to which both words belong. Formally, it is defined as follows:
π ππ ( πΆ1, πΆ2) = πΌπΆ (πΏπΆπ ( πΆ1, πΆ2)) Where, LCS is the lowest common subsumer of concept nodes C1 and C2 defined as the common parent of these with minimum node distance.
Jiang Similarity. This method uses corpus statistical information i.e. Information Content (IC) and nodes path in is-a taxonomy for computing similarity, where, IC is measure of occurrence of the concept in the corpus. Given a word pair C1 and C2, this measure computes similarity between the words by using following equation:
Where, IC stands for information content and LCS is the Lowest Common Subsumer of concepts C1 and C2 defined as the common parent of these with minimum node distance.
Leacock Similarity. This similarity measure is based on a node based approach using is-a taxonomy in the WordNet. When considering the WordNet taxonomy, each node represents a unique concept (or synset) in the taxonomy. Subsequently, the degree of similarity between a word pair is computed by calculating the shortest path between two concepts (represented as nodes), and dividing it by twice the maximum depth of the graph. Formally, it is represented as follows:
π ππ ( πΆ1, πΆ2) = βπππ *
In the equation, C1 and C2 are the two concepts represented by nodes, shortest path length is the minimum path length from node C1 to node C2 by using node counting, and depth is the number of maximum nodes from root node to a leaf node.
Lin Similarity. According to this measure, similarity between two concepts is expressed as the similarity between generic terms belonging to these concept classes, rather than measuring similarity between all terms. For instance, word 'design' belongs to the concept class 'blueprint', and the word 'construct' belongs to the concept class named 'concept'. According to Lin, the similarity between these words should be the same as the similarity between two synsets 'blueprint' and 'concept' to which these words belong. Formally, if there is a word x1β C1 and a word x2β C2 the information shared by two words can be expressed by C, the most specific class that subsumes both. The similarity is then computed as:
Where C is the most specific class that subsumes concepts C1 and C2 is the common parent of the two concepts with a minimum node distance. log P (C), log P (C1) and log P (C2) are log likelihood of the occurrence of concepts C, C1 and C2.
Wu Similarity. This similarity measure relies on the depth of both concept nodes, and depth of lowest common subsumer. The similarity between two concepts is then computed by using the following Equation.
Where LCS is the lowest common subsumer of concepts C1 and C2 defined as the common parent of C1 and C2 with minimum node distance. Depth (C1) represents the number of nodes from C1 to LCS node C, depth (C2) represents the number of nodes from C2 to LCS node C and depth (LCS) represents the number of nodes from LCS node C to root node.
Sentence-Level Similarity Methods
The preceding section presented various WordNet-based semantic similarity measures for computing word-level similarity. These measures compute similarity between a pair of words, however, PMM refers to computing similarity between activity pairs. Therefore, there is a need to combine the word-level measures with sentence-level methods, where each label is considered as a sentence. For this purpose, we applied three methods which extend word-level measures to sentence-level methods. These methods are Greedy Pairing [21], Optimal Matching [22], and Quadratic Assignment Problem (QAP) [23]. A brief overview of each method is described below.
Greedy Pairing. Using this method, at first both sentences are tokenized. After that, word-level semantic similarity method is used to search the maximum semantic similarity of each token in the first sentence with all the tokens in the second sentence. These maximum similarities are weighted using Inverse Document Frequency (IDF) scores. Maximum similarity scores of all the tokens in the first sentence are computed, summed up and resulting score is normalized with maximum sentence length. The same steps are repeated to find the maximum mappings for each token of the second sentence with the first sentence. The final similarity score between sentence pair is obtained by computing the average scores obtained using sentence one and two.
Optimal Matching. This method is based on combinatorial matching problem, where for a given weighted bipartite graph the problem is to find maximum matching of graph. Bipartite graph is the graph whose nodes can be divided into two disjoint sets. Using this approach, the two sentences S1 and S2 are considered part of a weighted bipartite graph G = S1 βͺ S2, where words in sentences are represented as nodes of graph and the weight of edges between these nodes corresponds to similarity score between the respected nodes. The task is to select those node pairs in matching M such that overall sum of all selected node pair is maximum.
Quadratic Assignment Problem (QAP). This approach finds an optimal assignment of word in first sentence to second sentence using word-level similarity measure and at the same time maximizes the similarity between syntactic dependencies of words pair. The Koopmans-Beckmann formulation of the QAP problem is used. The goal is to maximize the objective function QAP (F, D, B) where F and D captures syntactic dependencies between words in two sentences respectively and B captures the word-toword similarity across the two sentences.
For the experiments we have used three well established datasets, developed by experts and used in Process Model Matching Contest 2015 (PMMC '15). Since the competition, the datasets are widely used for the evaluation of process model matching techniques [24]. The datasets are named as, University Admissions (UA), Birth Registration (BR), and Asset Management (AM) datasets. Below, we present a brief overview of the three datasets. The UA dataset is composed of 9 process models about admission to nine German universities and 36 pairs of process models. In addition to that, the dataset includes gold standard correspondences between equivalent activities. The specifications of the three datasets are given below in Table 1.
The BR dataset includes 9 process models, 36 pairs of these nine models and gold standard correspondences. The models represent birth registration process of different countries: Germany, Russia, South Africa, and the Netherlands. The collection includes both 1:1 and 1: n correspondences. The AM dataset consists of 36 process model pairs selected from 72 process models of the SAP reference model collection [24]. The selected process models cover different aspects from the area of asset management.
This section presents the analysis of the results, which are obtained by applying five combinations of five word-level semantic similarity measures and 3 sentence-level methods.
The main goal of experiments is to classify each activity pair as 'equivalent' or 'nonequivalent'. Since, the semantic similarity methods used in this study return a numeric score between 0 and 1, we have converted these numeric scores into binary 0 (nonequivalent) and 1 (equivalent) at nine different thresholds from 0.1 to 0.9 with a gap of 0.1. However, due to space limitations we have used a cut-off threshold 0.7 because multiple matching systems participating in the latest episode of the Process Model Matching Contest 2015 achieved promising results at this threshold. This threshold value represents that each activity pair for which the similarity score is greater than or equal to 0.7 is marked as equivalent (or 1) and non-equivalent (or 0) otherwise. The F1 scores at 0.7 threshold are presented in Table 2 and the remaining results are made available for download. For each dataset, the word-level measure that obtained the highest F1 score for a sentence-level method is highlighted in bold. Therefore, each sentence-level method has at least one bold value. Furthermore, we have underlined the word-level measure that obtained the highest F1 score for a dataset, independent of any sentence-level aggregation method. A brief analysis of the results is as follows.
Difficulty level of datasets. From the table it can be observed that there is a clear difference between the performance of all techniques for the three datasets. That is, all combinations of techniques obtained high F1 scores for UA dataset, moderate F1 scores for BR dataset, and low F1 scores for AM dataset. These results indicate that the corresponding activity pairs of the AM dataset are harder-to-detect than that of UA and BR datasets. Furthermore, the corresponding activities in the BR datasets are harder-todetect than that of the UA dataset.
Performance variation across word-level measures. From Table 2 it can be observed that in the case of Greedy pairing sentence-level method, Jiang similarity obtained the highest F1 scores for all the three datasets (0.516, 0.534 and 0.464). Furthermore, for Optimal pairing sentence-level method, Jiang similarity obtained the highest F1 scores for two datasets, BR and AM datasets (0.534 and 0.464) whereas, Lin similarity obtained the highest F1 score for one dataset, UA dataset. Similarly, for QAP pairing, Jiang similarity obtained the highest F1 scores for two datasets, BR and AM datasets, whereas Lin similarity obtained the highest F1 score for one dataset, UA dataset. Based on these observations and the previous observation about the hardness of the three datasets (AM > BR > UA) we conclude, Jiang similarity is the most suitable word-level semantic similarity measure.
Performance variation across sentence-level methods. From Table 2 it can be observed that for the UA dataset, among the five word-level measures, Lin similarity obtained the highest F1 score with Optimal and QAP pairing (i.e. 0.520 for Optimal and 0.525 for QAP pairing). However, in the case of Greedy pairing sentence-level method, both Resnik and Jiang measures obtained a higher F1 score than Lin similarity. Similarly, for the BR dataset, both Lin similarity and Jiang similarity obtained the highest F1 score with QAP pairing. However, the F1 scores obtained by Jiang similarity with Optimal and Greedy pairing is higher than that of the Lin similarity. These changes in the best performing similarity measures due to the change in sentence-level methods, highlights the significance of sentence-level methods. Hence, we conclude that adequate attention should be given to the choice of the sentence-level methods. Another key observation regarding the sentence-level methods is that, for each dataset, the highest F1 score obtained by a word-level measure involved QAP pairing. This indicates that QAP pairing is the most suitable sentence-level aggregation method than Optimal and Greedy pairing methods.
A plethora of process model matching techniques have been developed which can be broadly divided into two types, syntactic and semantic [5]. Syntactic techniques merely rely on the similarity or distance between the labels without taking into consideration the meaning of the words. In contrast, semantic techniques rely on the semantics of words for computing similarity.
A recent survey of PMM has identified a set of semantic matching techniques that are used in literature [5]. A summary of these techniques is presented in Table 3 From the table it can be observed that most of the studies propose to use synonyms for semantic similarity. However, these studies do not explicitly present the measures used for computing similarity. Also, it can be seen from the table that, Lesk, Wu and Lin are the other similarity measures used in literature. Furthermore, it can be observed that Leacock, Resnik and Jiang measures have never been used for identifying corresponding activities between a pair of process models. Additionally, only word-level semantic similarity measures are considered for computing similarities between activity pairs and these word-level similarity measures have not been extended to compute similarity at activity-level.
Several semantic Process Model Matching (PMM) techniques have been proposed, however these techniques merely focus on the word-to-word semantic similarity, without due consideration to aggregation of word-level similarity to sentence-level (or activity-level) similarity. Furthermore, the existing studies have only used three semantic similarity measures and ignored the other semantic similarity techniques that have shown promising results for various text processing tasks. To that end, in this paper, we have used five word-level sematic similarity measures and three sentence-level aggregation techniques to experimentally evaluate the effectiveness of all the 15 combinations in the context of PMM. For the experiments we have used well established datasets from PMMC'15. The results reveal the following: a) the hardness of the three datasets are different, with AM dataset being the hardest, BR dataset being the moderate, and UA dataset being the easiest, b) Jiang similarity, is the most suitable matching technique, and c) QAP Pairing is the most effective sentence-level measure. In the future, we plan to compare the performance of these semantic measures with all the existing matching techniques.