Yeah, it depends on what you're trying to do with the graph as well. I was using a mix of Postgres operations and Java code to do a Floyd-Warshall "all shortest paths" calculation. I forget how many vertices I had, but it wasn't many... on the order of hundreds or thousands, at most. And the Postgres part just totally bogged down when using CTEs. I finally switched to storing the underlying graph itself in my own hand-rolled format (and eventually ran into different bottlenecks, but that's another story).

Now it's possible that if I were more of a Postgres expert, I could have tuned or optimized it to behave better. But at the minimum, I'll say that a naive graph implementation using CTEs didn't prove to scale well for me, in this given use-case.