well if you dont want to go away from PG, there are extension like AGE, but i have ni personal experience with those.

How big is the data? A lot of the "real" graph engines dont perform well on huge datasets that don't fit in ram

PMs are not possible to that account :( loop me in please :)