
## 2.2 The Idea

Our goal is to present an intuitive idea of a necessary and sufficient condition (C) for equivalence between graph matching and clique search. To this end, we turn from the MCISP to the general case. Suppose that X and Y are two graphs, and let MXY be the set of all partial morphisms from X to Y . The graph matching problem considered here generalizes the MCISP in two ways:
- By allowing nonnegative real-valued compatibility values κijrs = κ*jisr*.

- By allowing any subset of MXY as search space.

Allowing real-valued compatibility values κ*ijrs* ≥ 0 enables us to measure the degree of compatibility, or *consistency*, between items i = (*i, j*) of X and r = (*r, s*) of Y . This generalization is useful to cope with noisy attributes. Considering arbitrary subsets of MXY provides a flexible mechanism to cope with structural errors.

Applying both generalizations, the *graph matching problem* (GMP) is a combinatorial optimization problem of the form

$$\begin{array}{l l}{{\mathrm{maximize}}}&{{\quad f\left(\phi,X,Y\right)=\sum_{i\in{\mathcal{D}}(\phi)}\kappa_{i i\phi}}}\\ {{\mathrm{subject~to}}}&{{\quad\phi\in{\mathcal{M}},}}\end{array}$$
$$\left(5\right)$$

where the search space M is a subset of MXY , and i φ = (i φ, jφ) ∈ I(Y ) is the image item of item i = (*i, j*) ∈ I(X). Problem (5) is a generic formulation that subsumes a broad range of practical graph matching problems.

Often, solving an instance of problem (5) is computationally intractable. As for the MCISP, we therefore consider simpler versions of (5) that allow local optimal solutions.

A partial morphism φ ∈ M is a local optimal solution of (5) if D(φ) ⊆ D(ψ) implies f(φ, X, Y ) ≥ f(*ψ, X, Y* ) for all ψ ∈ M.

Applying the Association Graph Framework The central question at issue is: Under which conditions is the generic graph matching problem (5) equivalent to clique search in a derived association graph Z = X  Y ?

Certainly, an association graph Z should satisfy the following properties:

P1. Z uniquely encodes each partial morphism φ from the search space M as a clique Cφ in Z such that f(*φ, X, Y* ) = ω(C), where ω(C) denotes the weight of clique C.

P2. The set CZ(M) = {Cφ ∈ CZ : φ *∈ M}* of all cliques encoding partial morphisms from M is equal to the set CZ of all cliques in Z.
Ad P1: We can always derive an association graph satisfying the first property P1.

Consider the complete graph ZXY with vertex set VXY = V (X) × V (Y ). To each item
(i, j),(*r, s*)∈ I(ZXY ), we assign the weight κ*ijrs*. Since ZXY is complete, there are only vertex and edge items. We extract a subgraph from ZXY to form an association graph