Am I right that this algorithm is going to visit each “important” node nG in G once per path from nG to the output? If so, that could be pretty slow given a densely-connected interpretation, right?
Yep, this is correct—in the worse case, you could have performance that is exponential in the size of the interpretation.
(Redwood is fully aware of this problem and there have been several efforts to fix it.)
Am I right that this algorithm is going to visit each “important” node nG in G once per path from nG to the output? If so, that could be pretty slow given a densely-connected interpretation, right?
Yep, this is correct—in the worse case, you could have performance that is exponential in the size of the interpretation.
(Redwood is fully aware of this problem and there have been several efforts to fix it.)