Determine the modal vertices. Raise the power of the graphs to some power k. Normalize the modal rows. Compare these rows for sufficiently high k.
If these distributions are the same then the graphs are similar.
Following my previous post: In answer to your specific example, Connect the base version of the graph to its changing version at the vertices which are fixed. Then watch the mode Row distribution change as the graph changes using the same matrix power method I described. The mode row is the row containing the vertex, which has the most edges.
What you will get is the drift in mode frequency over time. Similarities follow.
Chris Durand