To my knowledge, Neo4j has been working on performances a lot. Neo4j v2.2+ does a much better job with large-scale graphs. The use-case you describe (a couple

To my knowledge, Neo4j has been working on performances a lot. Neo4j v2.2+ does a much better job with large-scale graphs. The use-case you describe (a couple million nodes + edges) sounds like a fairly reasonable task for Neo4j. If Neo4j has been a bad experience for you, I also recommend looking into TitanDB v1+, which scales horizontally (backed by Cassandra), although the query language (Gremlin) is not as easy to learn as Cypher.