I would say this is true of REST APIs. Not necessarily hypermedia APIs. An API that directly exposed a graph database as an HTTP-based API using hypertext/links within resources would still need to be classified as a hypermedia API, but would fail to adhere to the HATEOAS principle.

Edit: More specifically - a graph database that exposed itself with links for every edge and a resource for every node.