Read through this article by Facebook. They also have a paper on this. This is their graph data storage layer, built on top of MySQL.
Also, they came up with a graph query engine, Dragon:
Read through both and let’s have a discussion about what we could learn from them.