There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially modifications of edge weights) of which some examples are
the set of edges constituting to the shortest paths between a pair of vertices does not change if all edge weights are multiplied by a positive factor; it may however change, if a constant value is added to each edge-weight.
the set of edges constituting to a minimum spanning tree doesn't change after multiplying the weights with a positive factor and/or adding a constant value; it may however change, if the transformation is only applied to the weights of edges that are adjacent to some given vertex (e.g. after adding "node weights")
the set of edges constituting to either the shortest Hamilton cycle as well as the one constituting to the minimum weight maximal matching, are invariant to changes of "node weights"
the last example is special in that an NP-hard problem and an efficiently solvable problem are apparently invariant under the same kind of edge-weight modifications.
I would like to know, if those kinds of invariants have already been investigated in the spirit of an "Erlangen Program".
$$ $$ Addendum
David's example of a shortest-path preserving transformation makes clear, that the algorithm that is used to calculate the shortest path may also play a role in the definition of invariance.
There seem to be "strongly" invariant transformations that preserve the solution subgraph under every algorithm that determines that same subgraph in the unmodified graph and, also "weekly" invariant transformations that depend on the underlying algorithm.
That observation may also indicate, that a classification of algorithms based on the solution-set preserving transformations they support is also an interesting aspect of characterising the invariants of graph transformations.