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.