2

I have the following MRF graph and I need to find out about the clique factorization of the graph. I understand what it means for a graph to have a clique factorization. However it seems to be that it will not be unique. Is it true that that is the case? If not can I know how to get the clique factorization of the graph? Or is it not possible to know the clique factorization just from the graph itself?

enter image description here

user10024395
  • 1
  • 2
  • 11
  • 21

2 Answers2

1

Your intuition is correct: one cannot read the factorization from the graph. In general, many different clique factorizations will induce the exact same graph.

tddevlin
  • 3,387
  • 1
  • 15
  • 30
1

I'm assuming you are talking about the Clique Tree representation, (Ch.10 of Koller book).

Here's an example of a graphical model, and a clique tree enter image description here

The representation is not unique. You get it by triangulating the graph and then finding a spanning tree where valid edges are separators of original graph. There's freedom in both steps.

For instance, in the graph above, you could triangulated the graph by connecting all nodes to all other nodes, giving you a single super-node, which is also a tree.

Finding optimal clique tree decomposition is NP-complete, as it corresponds to the "treewidth problem", more background here

Yaroslav Bulatov
  • 6,199
  • 2
  • 28
  • 42