Very well summarized, particularly about the point of locality.

In terms of intractability large graph problems, here’s an example of a scalable solution that provides incredible performance (measured in terms of response times, queries per second, etc) by Facebook to represent the social graph https://www.usenix.org/system/files/conference/atc13/atc13-b...