# A Necessary And Sufficient Condition For Graph Matching Being Equivalent To The Maximum Weight Clique Problem

Brijnesh J. Jain and Klaus Obermayer Berlin University of Technology, Germany
{jbj|oby}@cs.tu-berlin.de 31. Oktober 2018 This paper formulates a necessary and sufficient condition for a generic graph matching problem to be equivalent to the maximum vertex and edge weight clique problem in a derived association graph. The consequences of this results are threefold: first, the condition is general enough to cover a broad range of practical graph matching problems; second, a proof to establish equivalence between graph matching and clique search reduces to showing that a given graph matching problem satisfies the proposed condition; and third, the result sets the scene for generic continuous solutions for a broad range of graph matching problems. To illustrate the mathematical framework, we apply it to a number of graph matching problems, including the problem of determining the graph edit distance.

## 1 Introduction

The poor representational capabilities of feature vectors triggered the field of *structural* pattern recognition in the early 1970s to focus on pattern analysis tasks, where structured data is represented in terms of strings, trees, or graphs. A key issue in structural pattern recognition is to measure the proximity of two structural descriptions in terms of their structurally consistent or inconsistent parts. There is also strong evidence that human cognitive models of comparison and analogy establish relational correspondences between structured objects [8, 11, 9]. The problem of measuring the structural proximity of graphs, more generally referred to as the *graph matching problem*, is often computationally inefficient. Therefore, an appropriate formulation of the graph matching problem is important to devise efficient solutions and to gain insight into the nature of the problem.

One popular technique is to transform graph matching to an equivalent clique search in a derived auxiliary structure, called *association graph* [1, 2, 18, 15, 19]. Chen & Yun [6]