1

Some articles* about belief propagation formulate the algorithm in terms of undirected graphical models. Thus if we had a directed (acyclic) graphical model, it would need to be preprocessed into an undirected graph before the algorithm can be applied. The result of this preprocessing (at least in the article I'm reading*) is called the "moral graph." Starting with a directed graphical model, the moral graph is constructed by 1. replacing all edges with undirected egdes and 2. putting an edge between any two nodes which appear as parents of the same node.

Alternatively, other sources about belief propagation formulate the algorithm in terms of factor graphs (see the wikipedia page on belief propagation), and thus similarly if one has a directed graphical model it must be preprocessed into a factor graph.

My question is: is one of these preprocessing steps better than the other? Better is vague, but some comparisons might be: Are there examples of (or general conditions for) directed graphical models for which the resulting moral graph is significantly more complicated/simpler than the resulting factor graph? Do they lead to more efficient algorithms?

(Note: I'm already aware of how the same undirected graphical model can correspond to multiple factor graphs. I'm interested in the case that we are starting with a directed graphical model.)

* specifically, I'm reading Wainwright, Jordan Graphical Models, Exponential Families, and Variational Inference link, which is not free but this appears to be an earlier similar version which mentions moral graphs

  • A note: the 'moral graph' is a joke/mnemonic due to David Spiegelhalter -- 'moral' in the sense that 'parents' of a node are 'married'. More recently he has said "it seemed quite funny at the time, in 1986 I think...". Nowadays it might better to just call it the 'conditional independence graph' – Thomas Lumley Sep 10 '21 at 23:53

0 Answers0