[Hi everyone, been ages,]
neo4j is a stellar product that we use as a backbone to our program NetworkCanvas, but it is woefully inefficient at the scale you're describing. It's basically a database of networks as nodes and edges where edges are a series of bi-directional hashes relating nodes for easy traversal. The cypher language for querying it is neat. I wouldn't say elegant but neat. Neo4j works very nicely with high dimensional data but it is not the most efficient graph database. I might be wrong, but I was given some serious grief lately for using neo4j by some CS people here at Oxford. I told them that for me usability was more important than performance as my current networks are extremely high dimension (multiplex, longitudinal, many atributes) but not very large. They agreed but said I should look a little further afield if I'm working towards more big big data networks.
Also, Jure Leskovec's SNAP is also geared towards very large networks and can definitely handle the sort you're referring to
https://snap.stanford.edu/data/ It's been used to analyze hundreds of millions of accounts and billions of edges on MSN among other things. I haven't used either of these packages in ages though so YMMV.