The approach I like is to use a key/value document store as the system of record (SOR). If any data conflicts arise between Redis, the document store, and the graph database, then the SOR wins. A good SOR should contain all of the data necessary to rebuild any other data source in its domain.

Graph databases can scale write throughput fine when those writes are being fed to it from a single source so it's best to have a service who's sole purpose is to keep the graph database in sync with the SOR. The graph should only store the data you actually need in order to get the queries that you want.

The specific queries in my domain are exactly the kind of thing I'm not supposed to talk about, but I will say you can do things like:

Give me 50 users who who live near me (lat/long bounding box), who I'm not already following, who I have not already sent a message to, who have at least two friends who also live near me, and who have matching tags, order by number of followers.

there are a bunch of great examples in this awesome book: http://www.amazon.com/Graph-Databases-Ian-Robinson/dp/144935...

http://shop.oreilly.com/product/0636920028246.do

This is a good book for a quick intro to graph dbs for anyone interested.