I had almost exactly the opposite experience, although my dataset was pretty small.

We wanted to store a graph in postgres and ended up writing some recursive queries to pull subgraphs then had NetworkX layered over it to do some more complex graph operations. We ended up doing that for a short while but then switched to Neo4j because of how comparatively easy it was to write queries (although the Python support for Neo4j was severely lacking). Never really stressed it out on dataset size though.

I did manage to crash Redis' graph plugin pretty quickly when I was testing that.