One could argue that Neo4j is much closer to a relational database than a NoSQL object store, since a relational database is effectively a graph. You could model graph data like Neo4J in a relational database by simply keeping a table of nodes, edges, and a join table for both.
The advantage of Neo4J is that its query language is explicitly optimized for the graph use case, whereas querying a relational database as a graph engine would necessitate fairly complex SQL.
If you are writing lots of joins in SQL, that might be a good use case for a graph database like Neo4j. Neo4j treats relationships as first class citizens, so really anytime you care about relationships in your data you might have a good graph use case.
One way to think about relationships in graph databases is as materialized joins. Relationships are modeled and stored explicitly so there is no join at query time, only a constant time graph traversal. There are differences in flexibility of data model, ease of expressing traversals in the query language, etc but I think traversal vs JOIN is a good way to compare relational vs graph.
My understanding is if you had widespread, conditional joins. I haven't ever implemented though, so somebody feel free to correct me if I'm wrong here:
Example:
News Feed
- JOIN with my friends
- JOIN recent posts
- JOIN topics / keywords that I tend to care about
- Filter by people I interact with more
- Filter out shared posts from sources I ignore
- Sort by some combination of recency, likes, likes from my friends
The idea, it seems, is to be optimized for wide joins.
Ultimately it's up to you, of course. But the most obvious use case would be when you're building something explicitly modeled onto a graph, like a social network.
The advantage of Neo4J is that its query language is explicitly optimized for the graph use case, whereas querying a relational database as a graph engine would necessitate fairly complex SQL.