IANAE, but while reading over the riak docs for an upcoming project, the concept of links is one that stood out.
http://blog.basho.com/2010/03/25/schema-design-in-riak---rel...
Local graph databases avoid the extra seeks by keeping extra copies of the destination vertex immediately next to the source vertex on disk, but I don't think Riak is doing this, or that it is actually practical in an eventually consistent system.