Graph databases are somewhat notoriously hard to optimize at scale.
Graph DBs are not magic. If you drill down into their query/execution plans it becomes very obvious that there isn't really a technical distinction between a traditional RDBMs and a Graph DB.
If you need graph traversal you can just as well use a table with edge-like indexing and recursive CTEs, and in the future with implementations of SQL/PGQ you can also do that in a "nice" Cypher-like syntax.
More concretely I'm pretty sure you could demonstrate using relational algebra that any graph can be formed pretty trivially using relations. So I think there is probably provably no use case that can't be done with a more traditional RDBMS. Likewise it seems obvious that any graph can be stored in a key/value store (bunch of nodes, bunch of edges, badda bing badda boom) and therefore there is similarly no graph db use case that can't be done using a k/v store if that's your thing.
On the contrary, redis is super popular, and that is basically what it is.
> More concretely I'm pretty sure you could demonstrate using relational algebra that any graph can be formed pretty trivially using relations. So I think there is probably provably no use case that can't be done with a more traditional RDBMS.
The question would be more about efficiency & ease of use than if you could literally just store a graph in a rdbms