[ilzmastr]

What is the connection other than "they both have graphs somewhere in them"?

I sort of see what you mean since NNs transport information across a graph in a straightforward (non-loopy) way, and PGMs can propagate information in crazy (neverending loops) ways when doing belief propagation...

[visarga]

From my limited understanding, pure NNs are not able to express confidence in predictions. By adding probability to the NN, we can have both predictions and confidence scores. In practice, noise is being injected, or connections dropped out randomly, then predictions averaged over multiple runs.

[ilzmastr]

Sure they can, many output probabilities: http://deeplearning.net/tutorial/mlp.html#mlp

[adamnemecek]

Not just graphs but also probability.