I've been sticking my feet in the graph database waters for a while, and I find them really compelling.
As a rule of thumb, here's how I think of the differences:
Graph databases are optimized for joins. Relational databases are optimized for selects.
Easy use cases:
Tagging systems where you're tagging million of items.
Social graphs, and "friending" people are an easy slam dumk for a graph database.
I'm convinced that a graph database is the secret to Linked In's success. Their ability to quickly identify first, second and third order connections are a graph problem, and become a lot easier when you're built on top of a graph database.
Commenting systems like HN's commenting system, where a threaded comment ordering is based on frequently changing scores is a giant pain in the ass trying to model in a relational database. That's why most commenting systems are date based. That only requires a single SELECT statement in a RDMS. I know because I built my own, and it was a giant pain, and required modeling a tree structure in a RDMS. HN's commenting system works well because comments on HN are modeled as an S expression tree, and kept in memory. Only occasionally are they serialized and written to disk for permanent storage. I'm convinced that the underlying tree structure is the reason that there hasn't been much innovation in commenting systems for the last decade.
Real time recommender systems can be modeled easier in graph structures.
Anything semantic web related will probably be modeled in a Graph database easier than in a Relational Database.
Also, for further reference, look at Dydra[1] and Directed Edge[2].
If you're interested, ping me and I can probably put you in contact with the Neo4j team. They're really responsive to questions like this.
ref:
[1] http://dydra.com/
[2] http://www.directededge.com/index.html http://www.directededge.com/products.html
