How to tell how much information I lose when I simplify the graph data structure with respect to unsimplified graph? I have the following problem: I have some sort of data (that I can't publish here, but they are in the form of points with XYZ coordinates) and I can represent them as a collection of graphs i.e. $Q = \{G_1, G_2 ... G_t\}$, where for every node there is an associated set of features, e.g. node $u_i$ has feature vector $\mathcal{F}_i$ and the features are changing between graphs (but graph structure does not). The resulting graphs are big in size with this approach. Therefore I decided to make the graphs smaller, by truncating some of the nodes and edges. And I would like to calculate how much information I lose when I simplify the graphs with respect to the not simplified graphs or original data. I would like to get something like "This graph explains 77% variance in the data" And the truncated graphs "This graph explains 55% variance in the data".

The question is then fallowing:
How to tell how much information I lose when I simplify the graph data structure.

Edit: Also the feature vector can be replaced with weighted edges. I think it can make the problem a bit simpler to solve.
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"