# Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant literature would be nice.

Say we have two directed graphs $G_1 := (V_1, E_1)$ and $G_2 := (V_2, E_2)$. Let $(G \times G)'$ be the set of pairs of graphs which are topologically isomorphic. Finally, let $\text{Sim}: (G \times G)' \to \mathbb{R}$ be a measure of similarity between two topologically isomorphic graphs. For example, in a computer vision setting we might define $\text{Sim}$ as the sum of the similarities of the corresponding edges in the graphs, where the edge-based similarities could come from a comparison of underlying pixels.

I would like to efficiently (perhaps approximately) find $$\max_{g_1 \subseteq G_1, g_2 \subseteq G_2, (g_1, g_2) \in (G, G)'} \text{Sim}(g_1, g_2).$$

In words, I want to find isometric subgraphs of $G_1$ and $G_2$ with the highest similarity.

Extra credit: If this is hard for general similarity functions $\text{Sim}$, but easy for certain constructions of $\text{Sim}$, please let me know.

• Dear emchristiansen, your question is really interesting! But the picture in your profile is rather horrific! May I ask you to change it please? – user42090 Nov 6 '13 at 13:01
• I like it! It's a photo from an early experiment in contact lens displays; in this photo the display is being tested on a rabbit. – emchristiansen Nov 6 '13 at 19:17
• There is no problem about the photo. Poor rabbit! :-( – user42090 Nov 7 '13 at 1:49
• I just saw this image. Why someone would adopt a picture of animal cruelty as their emblem is a mystery to me. – Brendan McKay Dec 29 '13 at 6:34