Efficient graph isomorphism for similar graph queries Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one node from G2, and we have the result of F(G1,G2), can we compute F(G1,G3) without computing it from scratch by extending any existing state-of-the-art methods?

For example, if G2 is formed by nodes 2,3,4,5 and G3 is formed by nodes 3,4,5,6, can we make use of the result of F(G1,G2) to compute F(G1,G3) more efficiently?
This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is isomorphic to $G_1$ is as hard as graph isomorphism itself (in the worst case).

Given two graphs $G = (V, E), G'= (V', E')$ build 

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

i.e. the union of the two graphs plus an extra node $u$ connected to all the vertices of $V$

pick $G_2 = G_1$; and clearly they are isomorphic.

Now build $G_3$ deleting $u$ and adding $u'$ connected to all the vertices of $V'$:

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ are isomorphic iff $G, G'$ are isomorphic.