The capabilities and performance of graph databases do differ, and many aren't cheap, nor well known, so if you need one, you'll need to shop around.

Btw, Neo4J is definitely a graph database, although it might not be what you need.