Corollary 2. Let X and Y *be attributed graphs. Then the best common subgraph problem* is equivalent to the MWCP in Z = X  Y .

Proof. Proposition 1 and Theorem 1. Probabilistic Graph Matching Problem In probabilistic graph matching, a probability model is drawn to measure compatibility between items. The aim is to then find a morphism from X to Y that maximizes a global maximum a posteriori probability. To describe the probabilistic graph matching problem in formal terms, we first introduce a distinguished *null color* V for vertices not contained in A. Next, we extend the model Y by including an isolated vertex with null color V .

The *probabilistic graph matching problem* is defined by

$$\begin{array}{l l}{{\mathrm{maximize}}}&{{\quad f\big(\phi,X,Y\big)=P\big(\phi|X,Y\big)}}\\ {{\mathrm{subject~to}}}&{{\quad\phi\in{\mathcal{M}}_{X Y},}}\end{array}$$
subject to φ ∈ MXY ,(7)
where the matching objective Pφ|X,Yis the a posteriori probability of φ given the measurements X and Y .

2 Applying Bayes Theorem, we obtain

$$\left(7\right)$$

$$P{\big(}\phi|\mathbf{X},\mathbf{Y}{\big)}={\frac{p(\mathbf{X},\mathbf{Y}|\phi)P(\phi)}{p(\mathbf{X},\mathbf{Y})}},$$
$$({\boldsymbol{\delta}})$$

p(X,Y ), (8)
where P(φ) is the joint prior for φ. The quantities p(X,Y |φ) and p(X,Y ) are the conditional measurement density and the probability density functions, respectively, for the sets of measurements.

Probabilistic graph matching problems are usually solved by a Bayesian inference scheme that does not require explicit calculation of compatibility values in advance.

Conceptually, there are compatibility values and a probabilistic graph matching problem turns out to be a GMP (5) over the set of all total morphisms, where we extend the graph Y by an isolated vertex with void attribute V .

Corollary 3. The probabilistic graph matching problem of X and Y **is equivalent to the**
MWCP in Z = X  Y
0*, where* Y
0extends Y *by an isolated vertex with void attribute* V .

Proof. Proposition 1 and Theorem 1.

Graph Edit Distance Problem The concept of graph edit distance generalizes the Levenshtein edit distance originally defined for strings [13]. The graph edit-distance is defined as the minimum cost over all sequences of basic edit operations that transform X into Y . Following common use, the set of basic edit operations are substitution, *insertion*, and *deletion* of items. Different cost functions can be assigned to each edit operation.

The sequences of edit operations that make X and Y isomorphic can be identified with the partial monomorphisms φ : V (X) → V (Y ). Each partial monomorphism φ induces a bijection φ : D(φ) *7→ R*(φ) from the domain D(φ) to the range R(φ) of φ. In terms of φ, the edit operations have the following form 2In accordance with the terminology used in [21] we refer to X and Y as the sets of measurements.