I will follow the path you have suggested and see what that I can achieve. The problem with the g.V() queries is that it is iterating over all vertices, so it is fast when I first start deleting but gets slower over time as it restarts the iteration after each batch of 10,000. FYI, here is the profile output for the g.E() query: