I've used a bunch of graph databases and I find they all fall short in one way or another. Almost all of them don't do anything that a good relational model can't do (except maybe faster for some queries). The biggest thing that leads me to believe that the graph database arena is not mature is that Tinkerpop is becoming the de facto standard. Talk about a joke. It is one of the silliest frameworks ever designed. Most of it's promise is just promise. Apache taking it over will probably lead to it's death.

Anyway, I'm going to give titan a second look with dynamo. I'm using OrientDB and neo4j right now. Both have major scaling issues, we haven't reached their limits yet but expect too very soon. I am wary of Titan because of Tinkerpop.