Given the fact that a graph database does not meet any of the design criteria listed why exactly would one consider neo4j as an option? It is great for what it does, but completely unsuited to the task described by the parent comment.
There are a few features of riak that appear somewhat related to similar features of neo4j (the concept of ancestor/child/sibling links which is only lightly explained in the available docs and does not seem to be really thought out well given the documentation that is available at the moment) but if you want real graph operations you would not use something like riak...