Yeah sure.... it is much harder and involves minimizing the number of relations across shard boundaries. Not easy. However, to call a system that only allows depth 1 traversals a 'graph database' is slightly pushing the definition. To me, its more a "key value database with relations between keys".

Everyone has different requirements though, if depth 1 and huge scale are what you need, flock db might be for you.