Another option is to learn Graph Databases. I notice there's still a big shortage in people with Graph DB experience, and they're not that hard to learn. Try Neo4J, for example.
I've been using Gremlin for crud ops in my apps. I recommend these two resources on Gremlin:
But yes, hosting solutions are terrible at supporting graph databases. Some do have a thin Graph DB layer (often using Gremlin as QL) over a Mongo-like database, but it's not the same thing.