Graphql gives a better way to request nested schemas and handle relationships and recursion. But when you cross that line, the client now would get ideas and starts asking "Why not be able to do that operation on the 5 level deep object?". Now you have to either not allow the client to do that, or you have to "rewrite the database" to make recursion optimal.
This is not a problem of Graphql. This is an HTTP problem. When you need to promote the database querying layer over HTTP, then you have a problem regardless.
The problem might be to get those 352nd pages of every book with the title starting with "A" sitting on 3rd shelf of every city library: when there are unbounded results nested deeper than top-level, and possibly those multiple times, that's when it gets hairy.
Maybe the trick is to keep it simple? There's no need for a bi-directional graph or advanced filtering. But if there really is, it's not like sticking to REST would make that any easier. Some things are just hard, no matter the interface.