Does the structure of data & query patterns required demand a graph store for acceptable performance? Would a Postgres-based triplestore & recursive CTE’s suck badly?
Yes, it won't scale well. I have used postgres exactly the way you specified in my past job and it didn't scale well after a certain point.