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

At work, we've got this gnarly problem where users are asking for complex 'friends of friends' or 'mutual connections' type queries. In our current SQL setup, we're using recursive CTEs, and for someone with a few thousand connections, these queries can easily blow past 10 seconds. It's just not cutting it for a real-time feed. We've been evaluating graph databases, specifically Neo4j, because it promises much faster traversal times for these kinds of relationship-heavy queries. The thought of adding a whole new database type to our stack is daunting though, considering the operational overhead and learning curve. What's the real tipping point where you say, 'okay, the complexity of a graph database is justified here'? Is it purely query performance, or are there other factors like data modeling simplicity for highly interconnected data that push you over the edge? I'm trying to figure out if our specific performance pain for these relationship queries is enough to warrant the leap.