Can graph databases be easily distributed?
even that the way to distribute data in graph databases is not that easy as in key-value stores, where the keys are distributed by ranges, there are techniques to distribute a graph. 

InfiniteGraph (made by Objectivity) for instance is a highly distributed graph database. It uses a P2P technology to increase read and write performance by growing the hardware. It allows the user to cluster a certain part of the graph or a certain kind of information as its needed and to distribute it over some machines as its needed too.

As I heard this process of clustering/distribution will be eased for the user in release 3.0. A parallel query mechanism is also planned, that allows to run one query concurrently on the machines.