If you don't consider connections between the objects to be part of your versioned resource (and you might -- in which case the following probably doesn't help much), you could consider splitting your objects into a part that represents the connectivity portion of the object and a part that represents the immutable state.
Then you could have each of the connectivity sub-objects contain a vector of the versioned states. This way you could operate with a graph version number to access the appropriate immutable state.
In order to avoid having to traverse the entire graph whenever there is an update to a specific node, you can make it so that if a node is accessed with a version number than is greater than the node's current version number, the current version is used. If the node is then updated, you fill in all the intermediate versions with the previous version -- thus allowing you to do lazy-updates to the object graph.
If the connectivity between objects is part of your versioned state, then the foregoing does not work. But maybe you can extend it as follows:
For each object in the graph, create a "handle object". The handle object contains the list of versioned immutable states. Rather than storing object references in any of the objects of the graph, you would store a reference to the handle object. Then each references to the objects would be de-rereferenced through the handle using the handle and the version number of view of the object graph that was currently being processed. This would return the correct immutable state for the object. The immutable states use the handles for referring to other objects in the graph, so you always get the consistent date for the version of the graph you want to process.
The same logic described above applies for updating the versions within the handles -- which allows lazy, localized updates.