> My intuition let's me know that you can not get below O(n log n) (Lower limit for comparison based ordering)

That intuition should point at O(log n), shouldn't it?

In any case, it totally depends how your data is stored and how/what you want to look up.

If you already have some kind of id of your node in the graph you want to look up, you can get O(1) lookup and still call it a graph database. If you have to traverse the graph, then it depends on the structure of the graph and where your entry point is, etc.

I'm rather skeptical of graph databases. Whatever they can do, you can do with a relation database and datalog. (Think of datalog as SQL plus recursion, perhaps.) See https://en.wikipedia.org/wiki/Datalog