GraphQL creates the illusion for the consumers that arbitrary queries are cheap, possible, and transparent. None of those things are true. Whether that reality is exposed to the client through more restricted REST endpoints or whether the backend has to support this fiction by handling all these performance considerations in GraphQL in the backend, the fact is that some queries are cheap, others are near impossible to achieve efficiently.
So GraphQL doesn't really _reduce_ complexity; it merely pushes it into other places. Whether the right place is the client or the server depends on your organization and the acceptable engineering tradeoffs, but there's no free lunch when it comes to data locality.