“Graph databases” seem to be mostly wrappers over relational databases that are optimized for certain graph operations. One example is Twitter’s FlockDB – an apparently long-abandoned project that’s nonetheless a solid demonstration of the principle. FlockDB uses MySQL as as storage engine, storing its edges as MySQL records.
Flock is optimized for queries that involve a user’s followers and people who follow that user. Like, which of my followers is following President Obama? These are the people A who satisfy the relations follows(Me, A) and follows(A, Obama). Flock contains a single table for for all A s.t. follows(Me, A). And the reverse is also stored, so follows(A, Obama) is just as efficient. So that query ends up being a single query on the me partition combined with a query on the Obama partition.