At the end of the presentation the presented mentions that this is structurally identical to loopy belief propagation... Isn't that a big issue, since they inherit many of its tractability issues with regards to training and inference? Modern DL models are far too interconnected for inference to be tractable in general, so the best we can hope for is that we can make simplifying assumptions that make loopy belief propagation feasible.

As a side note, when modern compilers optimize abstract syntax trees, I'm pretty sure they do operations that are similar to the message-passing algorithm described. And they work great, albeit for specialized purposes.