They are useful specifically in the intelligence field like NSA(no wonder they have so much graph stuff opensourced). Let me share one obvious use case you have data on a lot of people like call data records, Facebook friends list, Twitter followers/following list and potentially a lot of other data as well. Now you have two targets person A and person B with graph databases it is a trivial one liner to find how these two people are linked. They can be linked directly or they could have 5 people between them doing the same in SQL recursive CTE is a major PIA and takes a lot of time(see degrees of kevin bacon using graph database). There are very niche companies that are making big bucks by just selling libraries/softwares just to plot these graphs and most of their customers are government agencies with a lot of funds.