Comparing two graphs I have a quite big graph which has millions of nodes and edges. I modify the graph using an algorithm which only changes small portion of edges. At then end, I'd like to investigate how the algorithm affects the graph. There are a couple of options I have considered, but neither are appropriate.

1) compare the graph metrics (e.g. avg nodes degree, avg. coefficient clustering) for two graphs. The problem is as the algorithm only affects small portion of edges, and as there are great number of nodes and edges, the reported values are almost the same.

2) sample portion of each graph and find graph metrics on the sampled graphs. Again, the reported numbers are quire similar.

Is there any metric or technique to compare only subgraphs of two graphs? That is, I would like to consider only the modified nodes in the comparison.
here is one table about the different similarity measures which can be found in this paper https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf