I am thinking about something like this as well, but finishing things is not my strength. ;)
What I desired were probably quite different requirements to other graph libraries. My background is compiler optimizations, where the programs are represented as a graph: libFirm [0]. 1) A transaction mechanism. In debug mode, libfirm runs some checks on every graph change. However, sometimes a sequence of changes must be completed until the graph is in a valid state again. A transaction mechanism could be used to run the verifier after a complete transaction. 2) Node maps. Compiler optimizations sometimes rely on multiple analyses, which usually compute information for each node in the graph. While a hash map can be used to annotate nodes, a graph specific map should be more efficient. Additionally, a graph might know about its corresponding maps and update them implicitly, if the graph changes. [0] http://pp.info.uni-karlsruhe.de/firm/Main_Page