If I understand correctly, one of the challenges faced by this graph application relates to the workload being irregular and known only as the computation visits new parts of the graph. There's some work in this direction that might be helpful [1].

[1] https://dl.acm.org/doi/10.1145/2807591.2807651