What questions do they need to answer that require the entire graph? It seems like the most complex thing they may need to calculate is friends-of-friends, and that's easy to do even with an adjacency list in a SQL database.