{'fraction_non_alphanumeric': 0.05613927448423959, 'fraction_numerical': 0.022266533732136922, 'mean_word_length': 3.32577684396771, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Maximum Common Subelement Metrics and its Applications to Graphs

In this paper we characterize a mathematical model called Maximum Common Subelement (MCS) Model and prove the existence of four different metrics on such model. We generalize metrics on graphs previously proposed in the literature and identify new ones by showing three different examples of MCS Models on graphs based on (1) subgraphs, (2) induced subgraphs and (3) an extended notion of subgraphs. This latter example can be used to model graphs with complex labels (e.g., graphs whose labels are other graphs), and hence to derive metrics on them. Furthermore, we also use (3) to show that graph edit distance, when a metric, is related to a maximum common subelement in a corresponding MCS Model.


Introduction
Graphs are a natural model for a number of concepts in many different domains such as molecules in chemistry, interaction networks in social studies and biochemistry, workflow descriptions in scientific computing, just to name a few. In each of these domains, when dealing with collections of such objects, it is usually important to have a precise notion of similarity/dissimilarity between them. An adequate and precise way to define similarity/dissimilarity between graphs is by means of a metric on (the set of) graphs.
Bunke and Shearer [2] showed that the function is a metric on the set of graphs when g 1 and g 2 are graphs with, respectively, v 1 and v 2 vertices, and v 12i is the maximum number of vertices of a common induced subgraph of g 1 and g 2 . Later, Wallis et al. [7] showed that, by rearranging the same terms, the function is also a metric on the set of graphs. We say that these two metrics are based on induced subgraphs because the term v 12i is related to a common induced subgraph of input graphs g 1 and g 2 .
An initial motivation for this work was to identify metrics on the set of graphs based on subgraphs instead of induced subgraphs that would be analogous d B and d W . Note in Figure 1 that, for the same two graphs, the largest number of vertices of a common subgraph and of a common induced subgraph can be significatively different. This observation leads to the fact that, depending on the application, the graph similarity/dissimilarity notion is better modeled either by a function based on subgraphs or by one based on induced subgraphs. One application where a function based on subgraphs is a better fit is reported by [5]. In their paper, they argue that a common subgraph (not necessarily an induced one) that has the largest number of edges is a better model for the similarity of chemical graphs since, in their words, "it is the bonded interactions between atoms in a molecule that are the most responsible for its perceived activity". In this application for chemical graphs, analogous versions of d B and d W based on subgraphs would be more adequate.
One metric on the set of graphs based on subgraphs was shown by Fernández and Valiente [4]. Their function is equivalent to the following definition: where the new terms e 1 and e 2 are the number of edges of g 1 and g 2 , and v 12s and e 12s are the number of vertices and edges of a common subgraph of g 1 and g 2 that maximizes the sum of number of vertices and number of edges among all subgraphs of g 1 and g 2 .
In this paper we characterize a mathematical structure called Maximum Common Subelement (MCS) Model (Section 3.2), that generalizes the one described by [3], and show that four metrics are valid in such model (Theorem 1), including general analogous versions of the functions d B , d W , and d F . We then show three examples of MCS Models on graphs. The first two examples are based on the usual notions of subgraphs (Section 4.2) and induced subgraphs (Section 4.3), and the third example is based on a notion of extended subgraphs (Section 4.4). We refer to these three MCS Model on graphs as, respectively, S-MCS Model, I-MCS Model, and E-MCS Model. The importance of these MCS Models on graphs is that they enable us to reproduce previous metrics on graphs (e.g., d B , d W , d F ), extend them (weighting scheme), and derive new ones (e.g., analogous of d B and d W based on subgraphs, the metrics on the E-MCS Model).
One interesting aspect of the E-MCS Model is that the (vertex and edge) labels of its graphs are elements of other MCS Models. This permits an E-MCS Model to describe rich structured objects (e.g., graphs whose labels are other graphs) and similarity models on them (i.e., the general MCS Model metrics are readly available for these rich structured objects). In Section 5, we use E-MCS Models to show that for any graph edit distance that is a metric on graphs, we can derive a corresponding MCS Model where the edit distance of two graphs is related to the size of a maximum common subelement of the two graphs in this corresponding MCS Model.

Preliminaries
For the sake of completeness, in this section we state some standard concepts that are fundamental for the rest of the paper.
In this case, the pair (X, d) is called a metric space. If X is finite then we also refer to (X, d) as a finite metric space.
be a relation on a set X, i.e. is a subset of X × X. We use the notation x 1 x 2 to mean (x 1 , x 2 ) is an element of . We say is a partial order on X if the following conditions hold: Furthermore, we use the notations |A|, P(A), and [A] k to mean, respectively, the number of elements in set A, the power set of A, and the set of all sets containin k ≥ 1 elements of A.

Maximum Common Subelement (MCS) Model
In general, a natural model to the similarity of two objects is given by a number reflecting how much do the two objects overlap. The Maximum Common Subelement (MCS) Model is a precise way of encoding this idea of similarity, framed in a general language that can fit many different scenarios (our focus application in the following sections are graphs). A MCS Model is composed of three parts. The first part is a set also called the domain of the model. The second part, used to to make the informal notion of overlap precise, is a partial order on the set or domain of the model. The third and last part, used to quantify how much is an overlap, is a size function which assigns a size value for each element of the domain. The following definitions fix some notation before we formally define a MCS Model. Figure 1: Difference between the maximum number of vertices of a common induced subgraph and of a common subgraph of graphs g 1 and g 2 shown in (a). No common induced subgraph of g 1 and g 2 has more than 6 vertices (b), while there exist a common subgraph with 9 vertices (c). (these graphs represent scientific workflow descriptions generated using [6] (2008)) Definition 3. ( Subelement, Superelement, Common Subelements) Let be a partial order on a set X. For x 1 , x 2 ∈ X, if x 1 x 2 , we say that x 1 is a subelement of x 2 and that x 2 is a superelement of x 1 . We define the function common subelements, denoted by cs, as be a partial order on X. We say a function s : The size function conditions (S1) and (S2) formalizes the idea that a subelement must have either a smaller size (proper subelement), or have the same size and be the same element (a non-proper subelement). Now we are ready to define a MCS Model.
where is a partial order on X, and s is a size function on (X, ) such that (A1) Given x 1 , x 2 ∈ X, cs({x 1 , x 2 }) = ∅ and {s(x) | x ∈ cs({x 1 , x 2 })} has a maximum; (A2) Given x 1 , x 2 , x ∈ X and x 1 , x 2 x there exists x 12 ∈ cs({x 1 , Condition (A1) on a MCS Model states that any two elements (not necessarily distinct) have at least one common subelement, and, among all common subelements, there is at least one (could be more than one) whose size is the largest possible. Condition (A2) is rooted on the idea that a superelement of any two elements must, some how, contain these two elements simultaneously, in other words, it contain a kind of union of these two elements. Imagine two finite sets S 1 and S 2 , intuitively we expect that the number of elements of any superset S of sets S 1 and S 2 to have at least as much elements as their union: |S| ≥ |S 1 ∪ S 2 | = |S 1 | + |S 2 | − |S 1 ∩ S 2 |, but never fewer elements than that.
The MCS Model is a generalization of the model proposed by [3], referred here as the DR Model. The motivation to define the DR Model in their paper was the same we had to define the MCS Model here: a template to fit applied situations into, and derive metrics. A terminology difference between the DR Model and the MCS Model is that the terms pattern, generalization, specialization in the former becomes, respectivelly, element, subelement, superelement in the latter. A more important difference is that, in our terminology, while the DR Model requires every two elements to have at least one subelement and one superelement, the MCS Model only requires the subelement to exist. Once the terminology between the two models is aligned, it is straightfoward to prove that MCS Model is in fact a generalization of the DR Model (e.g., diamond inequality there is equivalent to condition (A2)). Thus, all the examples given in that paper, namely weighted sets, strings and trees (with appropriate partial order relations and size functions) are also examples of MCS Models. [3] proved one metric function to be valid in any DR Model. In this paper (Theorem 1) we extend this list to four metric functions to be valid in an even more general model: the MCS Model.
When presenting examples of MCS Models in the following sections, instead of showing that property (A1) is valid, we show that the following more restrictive property (A1') is valid: Clearly, (A1') implies (A1), since the number of subelements of any two elements is finite.
Before going into some properties and the metrics of MCS Models we set more terminology Definition 6. ( Auxiliar Functions) If (X, , s) is a MCS Model and X is a subset of X then the maximum common subelements size function, denoted by s , is defined by s (X ) = max{ s(x) : x ∈ cs(X ) }, and the maximum common subelements function, denoted by mcs, is defined by Note that, in general, s and mcs might not be well defined (e.g., common subelements of three elements might be empty). By (A1), these functions are well defined when when |X | ≤ 2. In the rest of the paper we should use these functions only when they are well defined.

Some Properties of MCS Models
Proposition 1 (Uniqueness of minimum size element). Let (X, , s) be a MCS Model and let x 0 ∈ X be such that s(x 0 ) = min({s(x)|x ∈ X}). Then, the following statements are true: The element x 0 is a global subelement, i.e., x 0 ∈ cs(X).
The following lemma provides a way to derive a MCS Model from a finite metric space. The interesting relation between this metric space and its derived MCS Model is that the metric is somehow preserved in the structure of the MCS Model. Figure 2 presents a finite metric space and a visual illustration of its derived MCS Model. We use this lemma in Section 5 to built a relation between Graph Edit Distance and MCS Models.
where Σ ⊆ X and, for σ 1 , σ 2 ∈ Σ, (1) Proof. Let n = |Σ| and K n = (Σ, [Σ] 2 ) be a complete (unlabeled simple) graph. Assume the natural interpretation: in K n , an edge {σ 1 , σ 2 } ∈ [Σ] 2 has endpoints σ 1 , σ 2 ∈ Σ. Furthermore, let Z be all non empty subsets of edges in K n that induces a connected subgraph of K n . We are now able to define the elements of our M X : the set X, the order relation X , and the size function s X . First, the elements of X are the vertices of K n plus every subset of edges in K n that induces a connected subgraph of K n : and vertex σ is an endpoint of some edge in E.
Define R to be for any σ 1 , σ 2 in Σ. By Lemma 1 for any other metric (on a finite set) there is a MCS Model satisfying the same properties as in this example.
Note that, with this definition of s X , θ is the size of [Σ] 2 (which is an element in Z and is the smallest element in M X ). We now prove that M X = (X, X , s X ) is a MCS Model: • ( X is a partial order) -(Reflexive) By (O1), X is reflexive.
x 3 ∈ Σ, then, by (H1), x 1 ⊇ x 2 and, by (H2), x 1 is an endpoint of some edge e in x 2 . As edge e is also en edge in x 1 we can conclude • (s X is a size function) First, by the definitions of R and s X it is easy to check that s X (x) ≥ 0 for all x ∈ X. If x 1 X x 2 then three cases can occur: -(S1) We need to show that: If (C1) occurs then x 1 ⊇ x 1 and, by definition, the expression for s X (x 1 ) will subtract from R at least the same edge terms d(σ 1 , σ 2 )/2 as the expression for s X (x 1 ), therefore, s X (x 1 ) ≤ s X (x 2 ). If case (2) occurs, x 1 has at least one edge e and the expression for s X (x 1 ) subtracts at least one positive value from R (e.g., the value relative to e). Since Assume x 1 X x 2 and s(x 1 ) = s(x 2 ). If (C1) occurs, then x 1 ⊇ x 2 and, by definition, the expression for s X (x 1 ) subtracts from R at least the same edges as in s X (x 2 ). If we assume x 1 = x 2 then s X (x 1 ) would subtract at least one more positive term from R and therefore s X (x 1 ) < s X (x 2 ), which contradicts the assumption s X ( • (A1) We are going that (A1) holds, by showing that (A1') also holds. In order to do so, let Before going into this axiom, we first note that if . There must be a path from σ a to σ in x 1 (which is contained in x 1 ∪ x 2 ) and there must be a path from σ b to σ in x 2 (which is contained in x 1 ∪ x 2 ). By joining these paths we have a path from σ a to σ b in x 1 ∪ x 2 . Therefore, We will split this into three cases: By the symmetric roles that x 1 and x 2 take in this axiom, these cases are enough to cover all possibilities.
-Case (1): As x 1 ∈ Σ, then we must have x = x 1 and making x 12 = x 2 we have the axiom, since -Case (2): x and x has at least one edge since it is an element in Z. Making x 12 = x 1 ∪ x 2 we have the axiom since: Note that x 1 ∩x 2 might not be a member of Z, but, since the formula for s X is well defined any subset of [Σ] 2 , we used it.
is also true in this case. If x 1 ∩ x 2 is the empty set we have that the only element in common between the graphs induced by x 1 and x 2 is the single vertex x. We can use the same development as in the previous case to estbilish the axiom in this case.
It now remains to show that Equation 1 is valid. The case where σ 1 = σ 2 is trivially true. Suppose σ 1 = σ 2 . By the definition of X we know that {{σ 1 , σ 2 }} X σ 1 and {{σ 1 , σ 2 }} X σ 2 . Furthermore, by the definition of s X , There must be a path σ 1 , β 1 , β 2 , . . . , β k , σ 2 in x otherwise x X σ 1 and x X σ 2 would not be true. Actually x must induce a path from σ 1 to σ 2 otherwise we could remove the extra (non-path) edges and still get a set of edges inducing a connected subgraph and with a larger s X . Furthermore, for paths of the form σ 1 , β 1 , β 2 , . . . , β k , σ 2 , replacing edges {σ 1 , β 1 } and {β 1 , β 2 } by {σ 1 , β 2 } we still have a path, and, by the fact that d is a metric, we have not increased the size s X of our x. This way we can erase all intermediate graphs and get that the graph that induces the path σ 1 , σ 2 must be a member of mcs({σ 1 , σ 2 }). With this, the result is estabilished.
Lemma 2 is a technical property used in Section 3.2 in the proof of Theorem 1.

Metrics on MCS Models
The main result in this section is the Theorem 1 which states that four different functions are indeed metrics on MCS Models.

(6)
Then, all of them are metrics on X.
Proof. Since s ({x 1 , x 1 }) = s(x 1 ), it is easy to check that (M1) is true for all formulas. Furthermore, as s ({x 1 , , it is also easy to see that (M2) is true for all formulas. Note that for any Maximum Common Subelement Model we have It is now easy to see that (M4) is true in all formulas (except for the case s(x 1 ) = s(x 2 ) = 0 on d c and d d ) by using its contrapositive form Assume x 1 = x 2 and check that, using Equation 7 above, each of the four distance formulas will result in a positive number. The case when s(x 1 ) = s(x 2 ) = 0 on the formulas d c and d d is also true because, by Proposition 1, there can be only one element with size zero in a MCS Model. The proof of (M3) will be given separately for each formula. For all the following proofs let x 1 , x 2 , x 3 ∈ X.
• (M3) is valid for d a : Using the Lemma 2, we can write which proves (M3) for d a .
• (M3) is valid for d b : We split this proof in three cases. These are the only cases need to be considered, since the role played by x 1 and x 3 in (M3) are symmetric.
We can write: , adding s(x 3 ) to both sides of (2) we have , adding s(x 3 ) to the left hand side and s(x 2 ) to the right hand side of (2) we have x 3 ) to be greater than or equal to zero. We split this into three cases: -(Case 1) If s(x 1 ) = s(x 2 ) = 0, then, by Property 1, x 1 = x 2 and the triangle inequality becomes d c ( which is obviously true. An analogous argument can be made to show that (M3) is valid in the cases where s(x 1 ) = s(x 3 ) = 0 and s(x 2 ) = s(x 3 ) = 0.
If (Case 1) doesn't occur, then at least two elements in {x 1 , x 2 , x 3 } have size s greater than zero and the definition of d c we need to use is the bottom one in Equation (5). In this case, the expression for (M3) becomes and M ij is a short name for max{s(x i ), s(x j )}. The remaining cases that are sufficient to prove that (M3) is valid for d c are: Since s(x 2 ) > 0, this implies that (8) ≥ 0. -(Case 3) Similarly, if not (Case 1) and s(x 1 ) ≥ s(x 2 ), s(x 3 ) then Since s(x 1 ) > 0, this implies that (8) ≥ 0.
• (M3) is valid for d d : This proof follow the same lines as the one given for graphs in [7]. The triangle inequality (M3) requires expression x 3 ) to be greater than or equal to zero. We split this into three cases: -(Case 1) If s(x 1 ) = s(x 2 ) = 0, then, by Property 1, x 1 = x 2 and the triangle inequality becomes d d ( If (Case 1) doesn't occur, then at least two elements in {x 1 , x 2 , x 3 } have size s greater than zero and the definition of d d we need to use is the bottom one in Equation (5). In this case, the expression for (M3) becomes (9) ≥ 0, where (9) is and In this way we can write Let non negative numbers a 1 , a 2 , a 3 , a 12 , a 23 , a 123 be defined by s(x 123 ) = a 123 ; s(x 12 ) = a 12 + a 123 ; s(x 23 ) = a 23 + a 123 ; s(x 1 ) = a 1 + a 12 + a 123 ; s(x 2 ) = a 2 + a 12 + a 23 + a 123 ; s(x 3 ) = a 3 + a 23 + a 123 ;. And let T = a 1 + a 2 + a 3 + a 12 + a 23 + a 123 . We now can write To show that (11) ≥ 0 it is sufficient to show that (11) times a positive number is greater than or equal to zero. Let (T − a 1 )(T − a 2 )(T − a 3 ) be this positive number, since (Case 1) is false.

Graph MCS Models
In this section we present three examples of MCS Models on graphs and use Theorem 1 to derive different metrics on graphs for each of these examples. In particular, we are able to reproduce and generalize previous metrics on graphs based on subgraphs and induced subgraphs, and obtain new metrics on graphs based on an extended subgraph notion.

Graphs Terminology
Here is a series of graph related definitions we use in the rest of the paper. We chose undirected simple graphs as our default case, but the results we present in the following sections also work for directed graphs.

Definition 7. ( Graph)
A graph is a 4-tuple g = (V, E, v , e ) where • V is a finite set of vertices; • E ⊆ [V ] 2 is the set of edges; • V : V → Σ V is a function that assigns labels to vertices; • E : E → Σ E is a function that assigns labels to edges; If V = ∅ then g is called the empty graph.
Definition 9. ( Induced Subgraph) A graph g = (V , E , V , E ) is said to be an induced subgraph of g = (V, E, V , E ) if g is a subgraph of g and Definition 10. ( Isomorphism) Let g 1 = (V 1 , E 1 , V 1 , E 1 ) and g 2 = (V 2 , E 2 , V 2 , E 2 ) be graphs. A bijection φ : V 1 → V 2 is an isomorphism between g 1 and g 2 if the conditions four conditions are valid: (1) If there exists an isomorphism between two graphs we say they are isomorphic.
Definition 11. ( Subgraph Isomorphic) A graph g is subgraph isomorphic to a graph g , denoted by g ⊆ g, if there exists a subgraph of g that is isomorphic to g .
Definition 12. ( Induced Subgraph Isomorphic) A graph g is induced subgraph isomorphic to a graph g , denoted by g ⊆ i g, if there exists an induced subgraph of g that is isomorphic to g .
Definition 13. ( Graph n-Completion) Let g = (V, E, V , E ) be a graph with vertex labels in Σ V and edge labels in Σ E . For n ≥ |V |, a special vertex label ε V , and a special edge label ε E , we define the graph n-completion of g as When ε V and ε E are clear in the context, we will denote the graph n-completion of g as κ n (g).

Subgraph MCS Model
The first example of MCS Model on graphs is based on the subgraph relation ⊆ (Definition 11).

Definition 14. ( S-MCS Model) A subgraph MCS Model or S-MCS Model is a triple
where • G is the set of graphs (Definition 7) with vertex labels in Σ V , and edge labels in Σ E . Furthermore, we consider two graphs g 1 , g 2 ∈ G that are isomorphic to be the same graph: g 1 = g 2 .
• ⊆ is the subgraph isomorphic relation on G (Definition 11); • s GV Eα : G → [0, +∞) is a function based on a label weighting function α : (Σ V ∪ Σ E ) → (0, +∞) and, for g = (V, E, V , E ), is defined by The following theorem shows a S-MCS Model is indeed a MCS Model.

Theorem 2. The S-MCS Model is a MCS Model.
Proof. It can be verified that ⊆ is a partial order on G. Here we are only going to show (S1), (S2), (A1) and (A2).
(S1) Let g 1 = (V 1 , E 1 , V 1 , E1 ) and g 2 = (V 2 , E 2 , V 2 , E2 ) be graphs in G. If g 1 ⊆ g 2 then there is an isomorphism φ between g 1 and g 2 , a subgraph of g 2 . It should be clear that s(g 1 ) = s(g 2 ) since for every vertex and edge in g 1 there is a φ-corresponding, equally labeled, vertex and edge in g 2 and vice-versa. As the vertices and edges of g 2 are subsets of V 2 and E 2 , then s(g 2 ) ≤ s(g 2 ), since the vertex and edge sums in s GV Eα would run over these subsets. From this we can conclude s GV Eα (g 1 ) ≤ s GV Eα (g 2 ).
(S2) Consider the same setup as in (S1) above: g 1 ⊆ g 2 and g 1 isomorphic to subgraph g 2 of g 2 . Add the extra hypothesis that s GV Eα (s 1 ) = s GV Eα (s 2 ). This implies, as s GV Eα (g 1 ) = s GV Eα (g 2 ), that s GV Eα (g 2 ) = s GV Eα (g 2 ) which implies that the vertices and edges of g 2 are exactily V 2 and E 2 . In other words, g 2 = g 2 and g 1 is isomorphic to g 2 which in our case is the same as g 1 = g 2 .
(A1) We are going to show that (A1') holds. In fact, the empty graph is a subgraph of any other graph. This implies that, for any pair g 1 , g 2 ∈ G, we have {"empty graph"} ⊆ cs({g 1 , g 2 }) and, consequently, 0 < 1 ≤ |cs({g 1 , g 2 })|. Also, by our definition, graphs have finite number of vertices and edges. This implies that all subgraphs of a graph is also finite (all possible subsets of the vertex and edge sets of a graph are finite). As we are consider isomorphic graphs to be equal, we know cs({g 1 , g 2 }) ⊆ cs({g 1 }) = "subgraphs of g1". As the right set in the previous chain is finite implies cs({g 1 , g 2 }) is also finite.
(A2) Let g 1 , g 2 ⊆ h. Let φ 1 be an isomorphim between g 1 and a subgraph h 1 = (V h1 , E h1 , V h1 , Eh1 ) of h and φ 2 be an isomorphism between g 2 and a subgraph h 2 = (V h2 , E h2 , V h2 , Eh2 ) of h. Define h 12 to be another subgraph of h whose vertices and edges are, respectively, V h1 ∩ V h2 and E h1 ∩ E h2 . The vertex and edges labels of h 12 are chosen to match the ones in h. With this construction of h 12 it can be verified that h 12 ⊆ g 1 , g 2 and that To see this last inequation one should only notice that every vertex and edge of h that was counted twice in the sum s GV Eα (g 1 ) + s GV Eα (g 2 ) is decreased once when we subtract s GV Eα (h 12 ).
This completes the proof of Theorem 2.
The Theorem 2 is true, if we use directed graph instead of undirected ones. Hence, we conclude, as a corollary of Theorem 2, that (G, ⊆, s GV Eα 1 ), where α 1 denotes the constant function equal to one, is a MCS model and hence d F is a metric on G (since, by Theorem 1, d a is a metric on G), with this we reobtain the result in [4]. Furthermore, again by Theorem 1, d c and d d are metrics on G, which shows versions of d B and d W based on subgraphs (note that we need to use as size function the sum of the number of edges and the number of vertices).
It is worth noting that the Theorem 2 enables the use of different label weighting functions that makes possible to enconde application domain knowledge in the MCS Model definition and hence in the metrics in Theorem 1.

Induced Subgraph MCS Model
The second example of MCS Model on graphs is based on the induced subgraph relation ⊆ i (Definition 12).

Definition 15. ( I-MCS Model) An induced subgraph MCS Model or I-MCS Model is a triple
where • G is the set graphs (Definition 7) with vertex labels in Σ V , and edge labels in Σ E . Furthermore, we consider two graphs g 1 , g 2 ∈ G that are isomorphic to be the same graph: g 1 = g 2 .
• ⊆ i is the induced subgraph relation on G (Definition 12); • and s GV α : G → [0, +∞) is a function based on a label weighting function α : Σ V → (0, +∞) and, for g = (V, E, V , E ), is defined by The following theorem shows that I-MCS Models are indeed a MCS Model.
Theorem 3. The I-MCS Model is a MCS Model.
Proof. It can be verified that ⊆ i is a partial order on G. The arguments to show that (S1), (S2) and (A1) are valid here are essentially the same as in the proof of Theorem 2 if we replace the terms "subgraph" by "induced subgraph" and s GV Eα by s GV α . For (A2) it is sufficient to notice that the construction of h 12 in the other proof replacing "subgraph" by "induced subgraph" yields an induced subgraph of g 1 and g 2 and the same argument used there to show the (A2) inequation was valid with h 12 can also be used here.
Again, Theorem 3 also holds if we deal with directed graphs. Thus, we can get as corollary of Theorem 2 the fact that (G, ⊆ i , s GVα 1 ) is a MCS Model, where α 1 denotes the constant function equal to one. Thus, d B and d W are metrics on G (since, by Theorem 1, d c and d d are metrics on G), with this we reobtain the results by [2] and [7]. Furthermore, since d a is a metric on G, we get a version of d F based on the induced subgraph relation (using as size function the number of vertices). Also, as in the previous case, the use of different label weighting function allows application domain knowledge to be used in the definition of the metrics (similarity notion). In Figure 3 we illustrate the effect on the notion of maximum common subelement (subgraphs and induced subgraphs) caused by using different label weighting functions α.

Extended Subgraph MCS Model
The previous two examples of MCS Models on graphs were based on two well known partial orders on graphs: subgraphs and induced subgraphs. We now define a third kind of partial order on graphs that we call extended subgraphs. The idea is a simple generalization of the subgraph partial order. Suppose that we fix partial orders on the vertex and edge label sets of a graph. Informally we say that a graph g 1 is an extended subgraph of a graph g 2 with respect to these label partial orders, if we can fit the structure of g1 into g 2 in a way that each aligned vertex and edge has a label in g 1 that is a subelement (by the label partial order) of the corresponding aligned element in g 2 . This informal idea is defined preciselly in the following two definitions.
Definition 16. ( Extended Subgraph) Let g = (V , E , V , E ) and g = (V, E, V , E ) be graphs with vertex labels in Σ V and edge labels in Σ E . If Σ V is a parital order on Σ V and Σ E is a partial order on Σ E , we say g is an extended subgraph of g with respect to Σ V and Σ E if When Σ V and Σ E are clear in the context we simply say that g is an extended subgraph of g.
Definition 17. ( Extended Subgraph Isomorphic) If g is isomorphic to a graph that is an extended subgraph of g with respect to Σ V and Σ E , we say that g is extended subgraph isomorphic to g , and denote this fact by g ⊆ e g.
We are now able to define the third example of MCS Model on graphs based on the extended subgraph relation ⊆ e (Definition 17). where, • G is the set of graphs (Definition 7) with vertex labels in Σ V , and edge labels in Σ E ; Furthermore, we consider two graphs g 1 , g 2 ∈ G that are isomorphic to be the same graph: g 1 = g 2 .
• ⊆ e is the extended subgraph relation on G with respect to Σ V and Σ E (Definition 17); • and for g = (V, E, V , E ) ∈ G, The following theorem shows that E-MCS Models are indeed MCS Models. Proof. The proof goes as follows: (S1) Let g 1 , g 2 be graphs such that g 1 e g 2 . By definition of e , there exists an extended subgraph g 2 of g 2 that is isomorphic to g 1 , and, clearly, s GES (g 1 ) = s GES (g 2 ). Since s GES (g 2 ) is a sum running over a subset of the vertices and edges of s GES (g 2 ), and each vertex or edge in the sum of s GES (g 2 ) yields a smaller or equal value than the one in the sum of s GES (g 2 ), we can conclude that (S1) is valid.
(S2) Let g 1 e g 2 and s(g 1 ) = s(g 2 ). By definition of e , there exists an extended subgraph g 2 of g 2 that is isomorphic to g 1 and, clearly, s GES (g 1 ) = s GES (g 2 ). This implies s GES (g 2 ) = s GES (g 2 ). As g 2 is a subgraph of g 2 the only option to make s GES (g 2 ) = s GES (g 2 ) is to have g 2 = g 2 .
In order to prove that the set {s(g)|g e g 1 , g 2 } has a maximum, let g ∅ 1 = (V 1 , E 1 ) and g ∅ 2 = (V 2 , E 2 ) be the unlabelled copies (same structure) of g 1 and g 2 respectivelly. The set of common subgraphs (by the subgraph isomorphic relation) of g ∅ 1 and g ∅ 2 is finite, as in the proof of Theorem 2. Denote this set by cs(g ∅ 1 , g ∅ 2 ) = {h 1 , ..., h n }. For each h i , let Φ i = {φ i , ..., φ ki i } be the set of all subgraph isomorphisms between h i and g 1 . Similarly, let Ψ i = {ψ i , ..., ψ li i } be the set of all subgraph isomorphisms between h i and g 2 . Now, for each s = 1, ..., k i and t = 1, ..., l i , the map φ s i • (ψ t i ) −1 defines a isomorphism from a subgraph g st 1 of g ∅ 1 and a subgraph g st 2 of g ∅ 2 . Finally, denote by g st the extended subgraph of g 1 and g 2 that has the vertex and edge set the same as g st 1 and the labels are defined as follows: for each vertex v and edge e of g st define its label as an element of mcs( V 1 (v), V 2 (φ s i • (ψ t i ) −1 (v))) and mcs( E 1 (e), E 2 (φ s i • (ψ t i ) −1 (e))), respectively. Now let s 0 and t 0 be such that s GES (g s0t0 ) = max({s GES (g st )|s = 1, ..., k i and t = 1, ..., l i }). By construction, such g s0t0 is the extended subgraph of g 1 and g 2 with maximum size.
Define h 12 to be another extended subgraph of h whose vertices and edges are, respectively, V h1 ∩ V h2 and E h1 ∩ E h2 . The label of vertex v of h 12 is defined as follows: let σ h , σ h1 , σ h2 be the label of v in, respectively, h, h 1 , h 2 ; by the fact that h 1 , h 2 are extended subgraphs of h, we have ; define the label of v in h 12 to be σ 12 . The label of an edge of h 12 is defined in an analogous way.
With this construction of h 12 it can be verified that h 12 ⊆ g 1 , g 2 and that The proof of Theorem 4 is complete.
When modeling real world concepts using graphs, it is usually important to have flexibility when defining what information a vertex or an edge will carry. For example, in scientific workflow descriptions vertices represent parameterized modules that represent some kind of computation. Usually a single module is configured with a set of parameters and values which are not adequately represented by a single symbol, but, instead, by a more complicated object. The nesting property of E-MCS Modelsthat enables plugging other MCS Model elements as labels of vertices and edges, and be able to derive metrics for these objects that take into account all parts that form the final object is an interesting one.
To illustrate E-MCS Models, we will use them, in next section, to build a link between Graph Edit Distance and MCS Models. Before that we need an additional property of E-MCS Models that states that if we restrict the elements (graphs) of an E-MCS Model to complete graphs of n vertices, we still have a MCS Model. We will refer to this MCS model as a n-restricted E-MCS Model.
. Let K n be the subset of G formed of complete graphs with n vertices. Let Kn and s Kn be the restrictions of ⊆ e and s GES to K n . In this context, the triple M Kn = (K n , Kn , s Kn ) is also a MCS Model.
Proof. Properties (R1),(R2) and (R3) clearly hold for Kn , since they are valid for ⊆ e . Similarly, the properties (S1) and (S2) hold for s Kn , since they hold for s GES .
Let φ be a bijection between V 1 and V 2 . Then, φ defines a one-to-one correspondence between any vertex and edge of g 1 and g 2 . Then, we can define a graph g 12 ∈ K n , by using the same vertex and edge sets as in g 1 and defining the label for each vertex v ∈ V 1 as an element of cs({ V 1 (v), V 2 (φ(v))}) and for each edge e ∈ E 1 as an element of cs({ E 1 (e), E 2 (φ(e))}).
V 12 (v) = α 12 . With a similar construction, we can define the edge label function E 12 . One can verify that g 12 constructed this way satisfy the axiom (A2).

Relation between Graph Edit Distance and MCS Models
In this section we show a relation between graph edit distance and MCS Models. Informally speaking, this connection states that if d GED is a graph edit distance and a metric on G, then there is a corresponding MCS Model M such that d GED (g 1 , g 2 ) = d a (θ(g 1 ), θ(g 2 )), where g 1 , g 2 ∈ G, θ takes the elements of G into their corresponding elements in M, and d a is the first of the four metrics in Theorem 1 valid in M. Thus, the MCS Model M encodes d GED . The problem of finding the graph edit distance between g 1 and g 2 becomes the problem of finiding a maximum common subelement between θ(g 1 ) and θ(g 2 ) in M.
Before stating the main result of this section, we define precisely what we mean by graph edit distance. We use the notion of graph completion in this definition to facilitate the exposition: for any two graphs we can refer to bijections between the vertices of their completed versions instead of having to deal with functions between subsets of the vertices of the first graph into the vertices of the second graph. This definition of graph edit distance is equivalent to the common use of the term, where the cost of each vertex and edge operation (i.e., addition, deletion, and substitution) is based on labels and these operation costs are known a priori.
Definition 19. ( Graph Edit Distance) Let g 1 and g 2 be graphs with vertex labels in Σ V and edge labels in Σ E . Furthermore, let be, respectivelly, edit cost functions on vertex and edge labels, where ε V and ε E are special labels. Assume that Let F be the set of bijections from V 1 to V 2 . The cost c(f ) for f ∈ F is defined as , E2 (f (e))).
In this context, we define the graph edit distance between g 1 and g 2 as Some uses of the term graph edit distance refer to a more general idea. For example, [1] shows a correspondence between the maximum number of vertices of a common induced subgraph and a specific graph edit distance notion where the edge operation cost depends on which operation was done in its end vertices. Now we are able to state the main result of this section. and an injective function θ : G n → X such that d GED (g 1 , g 2 ) = s X (θ(g 1 )) + s X (θ(g 2 )) − 2s X ({θ(g 1 ), θ(g 2 )}).
Proof. Apply Lemma 1 on the finite metric spaces (Σ V ∪ {ε V }, c V ) and (Σ E ∪ {ε E }, c E ) to obtain corresponding MCS Models M V = (Σ V , Σ V , s Σ V ) and M E = (Σ E , Σ E , s Σ E ), where the size of the smallest element in these MCS Models are strictly positive. Let G be the set of graphs with labels in Σ V and Σ E . Observe that the triple (G , ⊆ e , s GES ) with respect to M V and M E is an E-MCS Model. Define X = K 2n to be the subset of G consisting only of complete graphs with 2n vertices. By Proposition 2 we know that M n = (X, X , s X ) is a MCS Model, when X and s X are restrictions of ⊆ e and s GES to the set X. Assume g 1 , g 2 ∈ G n and their vertex sets are, respectively, V 1 and V 2 . By definition, the graph edit distance between g 1 and g 2 is the minimum value of function c (Equation 15) for a vertex bijection between κ ε V ,ε E |V1|+|V2| (g 1 ) and κ ε V ,ε E |V1|+|V2| (g 2 ). It can be checked that for our metric c V and c E this minimum value of function c is the same if we consider vertex bijections between κ ε V ,ε E 2n (g 1 ) and κ ε V ,ε E 2n (g 2 ). Define θ : G n → X to be the graph completion κ ε V ,ε E

2n
. Make x 1 = θ(g 1 ) = (V 1 , E 1 , V1 , E1 ) and x 2 = θ(g 2 ) = (V 2 , E 2 , V2 , E2 ). Let f be a bijection between the vertices of x 1 and x 2 . Define x f ∈ X in the following way: for every vertex v in x 1 there corresponds a vertex in x f labeled with an element (any element) of mcs({ V1 (v), V2 (f (v))}), and for every edge e in x 1 there corresponds an edge in x f labeled with an element (any element) of mcs({ E1 (e), E2 (f (e))}). Using this construction for x f it is clear that x f X x 1 , x 2 and it can be verified that c(f ) = s X (x 1 ) + s X (x 2 ) − 2s X (x f ). Let f 0 be the bijection between vertices of x 1 and x 2 that yields the graph edit distance between g 1 and g 2 . At this point we can write d GED (g 1 , g 2 ) = c(f 0 ) = s X (x 1 ) + s X (x 2 ) − 2s X (x f0 ).
To conclude the proof it remains showing that s X (x f0 ) = s X ({x 1 , x 2 }). Assume s X (x f0 ) < s X ({x 1 , x 2 }) and x 12 ∈ mcs({x 1 , x 2 }). Let φ 1 and φ 2 be isomorphisms between x 12 and extended subgraphs of x 1 and x 2 . Define f 12 = φ 2 • φ −1 1 . Note that f 12 is a bijection between vertices of x 1 and of x 2 and that s X (x 12 ) = s X (x f12 ). In this case, we can write s X (x f0 ) < s X ({x 1 , x 2 }) = s X (x 12 ) = s X (x f12 ), for bijection f 12 . This contradicts the hypothesis that s X (x f0 ) is the maximum possible for a bijection between vertices of x 1 and x 2 . The theorem is proven.
An interesting aspect of this theorem is that it brings a different and precise materialization for the meaning of a metric graph edit distance between two graphs: we can see it encoded in an element of a corresponding MCS Model. We see as applications of this connection, the interpretation of natural notions in the MCS Model in terms of the original metric graph edit distance. For example, a maximum common subelement of three or more elements of the MCS Model could correspond to a natural generalization of the metric graph edit distance between three or more graphs.

Conclusions
In this paper we have introduced MCS Model which is a generalization of a model proposed by [3]. We then showed four metric functions to be valid in any MCS Model (three additional metrics to the one shown in [3]). The usefulness of the MCS Model is that it serves as a template to fit into applied scenarios