Once you start getting out to second order it becomes a much more complicated (and interesting) problem -- one that I've been kicking around for a while.

Data-locality is the kicker in a distributed graph database; when doing traversals that cross multiple nodes you need to have a partitioning scheme that coordinates with your traversal algorithms so that you need the minimum number of machine-to-machine hops in a multi-level traversal. Getting that right is far more difficult than traditional database sharding.