A non-graph-database would not provide operators like deep traversals. Operations are tightly bound to ACID as a whole, not just isolation. Of course ACID would always hold if you strictly linearize everything, but that defeats the purpose of data management, and one would achieve the same goal with even macro processors like `m4`.
Getting traversals and other graph algorithms into the business means that there are lot of things that should be reconsidered, like constraints, and triggers.
For example, if you cannot write a constraint to limit the local clustering coefficient of every entity, you do not proceed in your traversal with a good upper bound time budget. However, it is the vertices that you _don't_ visit that will propagate these constraints back while you are halfway there. Parallelizing such queries, in my opinion, is beyond state-of-the-art research.