There is support for graph rewriting for a Titan-backed data-set using Faunus. Titan does not support global graph operations. Therefore, Faunus was created to allow you to perform offline graph operations much like the one you've described.