No-one seems to have yet mentioned Facebook's TAO paper, which describes scaling basically this approach to 1 billion reads per second. https://cs.uwaterloo.ca/~brecht/courses/854-Emerging-2014/re...
The nice thing about your approach is that you can shard your objects by their id and your edges by their "from" id, and have all lookups go to one box when you shard. Throw in some caching and it scales to multiple boxes really well.