According to Lukas Krejci from the Hawkular team, they have been able to improve graph queries by copying some information to edges, too.

It works like this:
When asking for ....out("imports").has("name","javax.naming.InitialContext"), gremlin hops over over the edge and tests the vertex (using an index). This hop is quite expensive as it's still performing 2 queries to the key-value storage, asking for a wide row containing the set of edges going from particular vertex, and then filtering those which have the matching name.

We are actually starting from the imported class and then getting all the java files it is contained in. But still:
If it tests at the edge, it moves the filtering to the edge query and makes it reportedly significantly faster .

Source: http://www.hawkular.org/blog/2015/10/09/graph-db-performance.html