Definitely true. There are of course patterns that can slow certain graph traversals down, like having millions of relationships on one single node. Otherwise Neo4j handles up to a couple of billions of nodes/relationships/primitives out of the box, which is a good starting point for most of the cases.

Disclaimer: I am part of the Neo4j team.