A question was posted on Neo’s community mail list inquiring if there are any “scientific papers proving the power of a graph based DB paradigm (could be specifically Neo4j) against relational DBs.”

Here are some great examples:
The Graph Traversal Pattern
A Comparison of a Graph Database and a Relational Database

Peter Neubauer, VP of Community at Neo Technology, will be presenting a paper at this year European Data Forum.
More information: European Data Forum 2012

Also, Dr. Marko Rodriguez has a bunch of papers on graphs here (with citations to related work):
Additional work from Marko can be found at the following links.