History and status of the graph matching problem Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from it when using search engines.

Given two graphs $G=(V,E)$ and $G'=(V',E')$ such that $|V| = |V'|$, the task is to find a bijection $\pi : V \rightarrow V'$ such that this bijection establishes as much correspondences between edges of $G$ and $G'$ as possible.

In other words, if $M$ and $M'$ are the adjascency matrices, then we want to maximize

$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$

This problem clearly contains graph isomorphism as a special case, and can be reduced to bipartite matching under a (non-polynomial!) reduction.

What kind of algorithms do exist, and what is known about its complexity?
From the paper Approximate Graph Isomorphism:


  We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $π$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log{n})}$ time approximation scheme that for any constant factor $α &lt; 1$, computes an $α$-approximation. We prove this by combining the $n^{O(\log{n})}$ time additive error approximation algorithm of Arora et al. [Math. Program., 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $α$-approximate for any constant factor $α$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.