- *Substitution*: An item i from D(φ) is *substituted* by item i φfrom R(φ).

- *Deletion*: Items i of D(φ) = I(X) \ D(φ) are *deleted* from X.
- *Insertion*: Items j from R(φ) = I(Y ) \ R(φ) are *inserted* into Y .

If xi = yi φ , the substitution i by i φis called *identical substitution*. The cost of a partial monomorphism φ is then defined by

$$f\big{(}\phi,X,Y\big{)}=\sum_{i\,\in\,\overline{\mathcal{D}}(\phi)}C_{del}(\mathbf{i})+\sum_{\mathbf{j}\,\in\,\overline{\mathcal{R}}(\phi)}C_{ins}(\mathbf{j})+\sum_{\mathbf{i}\,\in\,\mathcal{D}(\phi)}C_{sub}\left(\mathbf{i},\mathbf{i}^{\phi}\right),\tag{9}$$

where Cdel(i) is the cost of deleting item i of X, Cins(i) is the cost of inserting an item i into Y , and Csub(i, j) is the cost of substituting an item i from X by an item j of Y .

We assume that all costs are nonnegative.

The *graph edit distance problem* is then of the form

minimize $f(\phi,X,Y)$ subject to $\phi\in{\cal M}$ (10)
where the matching objective f is defined as in (9) and M is the subset of all partial
monomorphisms from X to Y . The constrained global maximum of −f is the *graph edit*
distance of X and Y .
To show equivalence between the graph edit distance problem and clique search, we
transform problem (10) to our standard form of a GMP as given in (5). First, we expand
the set A of attributes to A0 = *A ∪ {*d} by including the distinguished symbol d. We
call items with attribute d *dummy items*. Next, we expand X and Y by adding dummy
vertices. Suppose that X and Y are of order |X| = n and |Y | = m, respectively. Insert
m dummy vertices into X and n dummy vertices into Y . Connected each dummy vertex
with all the other (original and dummy) vertices by dummy edges. Let X0 and Y
0 be
the resulting expanded graphs. We call X0 and Y
0the *dummy extensions* of X and Y .
Finally, we define an appropriate compatibility function κ. To this end, we first introduce some auxiliary notations. By V (*X, a*) we denote the subset of all vertices of X that have
attribute a. Furthermore, let C
0
sub be a nonnegative real-valued function on I(X0)×I(Y
0)
such that
$$C_{s u b}^{\prime}(i,j)=\left\{\begin{array}{c}{{C_{s u b}(i,j)\,,}}\\ {{0}}\end{array}\right.$$
sub(i, j) = Csub(i, j) : i ∈ I(X), j ∈ I(Y )
$$\begin{array}{l l}{{:}}&{{i\in I(X),\,j\in I(Y)}}\\ {{:}}&{{\mathrm{otherwise}}}\end{array}\ .$$
Now we consider the following compatibility values of X0 and Y
0

$$\kappa_{i j}=\left\{\begin{array}{l l}{{-C_{d e l}(\dot{\mathbf{i}})}}&{{:}}\\ {{-C_{i n s}(j)}}&{{:}}\\ {{-C_{s u b}^{\prime}(\dot{\mathbf{i}},j)}}&{{:}}\end{array}\right.$$

−Cdel(i) : i ∈ V (X), j ∈ V (Y
−Cins(j) : i ∈ V (X0, d), j ∈ V (Y )
$$\begin{array}{l c r}{{}}&{{}}&{{i\in V(X),\,j\in V(Y^{\prime},{\bf d})}}\\ {{}}&{{}}&{{i\in V(X^{\prime},{\bf d}),\,j\in V(Y)}}\\ {{}}&{{}}&{{\mathrm{otherwise}}}\end{array}\qquad\qquad(11)$$
sub(i, j) : otherwise for all items i of X0 and j of Y
0. Then the GMP over the set of all total monomorphisms from X0to Y
0is equivalent to the graph edit distance problem (10). Note that we consider negative costs as compatibility values to turn the minimization problem (10)
into a maximization problem as in (5).