That's exactly the trade off, isn't it? Either you do the work to store the relationships and save on the compute and memory cost later, or you pay as you go to build it in real time with a relational database. It's horses for courses.
To propose a different perspective, a relationship in a graph db is like a materialized join. You pay on relationship creation (you might be using index lookups to find the nodes to connect, similar to a relational db), then for traversal it's just pointer hopping across the relationships to the connected nodes. Aside from the initial lookup of starting node(s), traversing the graph won't use indexes at all, so becomes constant time operations.
With relational databases, you can join on anything anywhen, so you can explore new relationships as you go.