Com a ajuda do RhodiumToad no #postgresql, cheguei a esta solução:
WITH RECURSIVE node_graph AS (
SELECT ancestor_node_id as path_start, descendant_node_id as path_end,
array[ancestor_node_id, descendant_node_id] as path
FROM node_relations
UNION ALL
SELECT ng.path_start, nr.descendant_node_id as path_end,
ng.path || nr.descendant_node_id as path
FROM node_graph ng
JOIN node_relations nr ON ng.path_end = nr.ancestor_node_id
)
SELECT * from node_graph order by path_start, array_length(path,1);
O resultado é exatamente o esperado.