I've seen plenty of graph problems solved easily with relational databases. However a lot of people seem to confuse the issues here (e.g. when they see "relational" they assume a SQL RDBMS).

Can you provide a better explicit reference for what you're calling a "graph database"?