How to tell how much information I lose when I simplify the graph data structure with respect to unsimplified graph?
Graph comparisons can be tricky.

One option is to take an Information Theory approach, something like "An information-theoretic, all-scales approach to comparing networks"