It seems some incremental graph query extensions to SQL could add some powerful capabilities to PostgreSQL (without having to think about a complete query language replacement). The incremental change could include: paths as first class citizens and a new MATCH keyword.
"Path as first-class citizens. The notion of Path is fundamental for graph databases, because it introduces an intermediate abstraction level that allows to represents how elements in a graph are related. The facilities provided by a graph query language to manipulate paths (i.e. describe, search, filter, count, annotate, return, etc.) increase the expressivity of the language. Particularly, the ability to return paths enables the user to post-process paths within the query language rather that in an ad-hoc manner [15]."