When I was experimenting with Neo4J I found that consistent performance was a strength.  A 4 hop query seems to take the same amount of time regardless of data volumes