Graph databases in production: when does Neo4j actually beat SQL?

we're currently trying to optimize a 'friends of friends' style query that's taking 10+ seconds with recursive cte's in postgres, and it's just not cutting it for a user-facing feature. we've been hearing a lot about graph databases like neo4j for these kinds of highly connected data problems. the promise of super fast graph traversals is very appealing. however, introducing a whole new database technology brings significant operational complexity, new query languages to learn, and data synchronization challenges. at what point does the performance benefit of something like neo4j outweigh the additional complexity? has anyone here made the jump from relational to a graph database for specific use cases like social graphs or recommendation engines? what was your 'tipping point' that justified the investment?