There are many papers that are devoted to efficient inference in graphical models. Though many of these paper don't explicitly talk about the learning (training, etc) problem. For example:
I am a little confused on how these models being trained. I thought they are probably doing an EM-like algorithm, i.e.
Inference (and calculating all marginals, using VB or EP)
Maximizing the likelihood using some blackbox optimization toolboxes using the marginals in the previous case
For example, consider different variants of Belief-Propagation. There are HUGE number of variants for BP, but how a graphical model could be trained?