5

I am playing around with implementing a junction tree algorithm for belief propagation on a Bayesian Network. I'm struggling a bit with triangulating the graph so the junction trees can be formed.

I understand that finding the optimal triangulation is NP-complete, but can you point me to a general purpose algorithm that results in a 'good enough' triangulation for relatively simple Bayesian Networks?

This is a learning exercise (hobby, not homework), so I don't care much about space/time complexity as long as the algorithm results in a triangulated graph given any undirected graph. Ultimately, I'm trying to understand how exact inference algorithms work before I even try doing any sort of approximation.

I'm tinkering in Python using NetworkX, but any pseudo-code description of such an algorithm using typical graph traversal terminology would be valuable.

Thanks!

skaffman
  • 398,947
  • 96
  • 818
  • 769
Joe Holloway
  • 28,320
  • 15
  • 82
  • 92

1 Answers1

3

If Xi is a possible variable (node) to be deleted then,

  • S(i) will be the size of the clique created by deleting this variable
  • C(i) will be the sum of the size of the cliques of the subgraph given by Xi and its adjacent nodes

Heuristic:

In each case select a variable Xi among the set of possible variables to be deleted with minimal S(i)/C(i)

Reference: Heuristic Algorithms for the Triangulation of Graphs

Lance Roberts
  • 22,383
  • 32
  • 112
  • 130
  • 1
    When you say "size of the clique(s)", do you mean the variables you've already connected to one another due to a deletion? I.e. if a graph contains a 5-clique, does your method recognize this on the first iteration or does it initially treat all variables as 1-cliques? I want to avoid calling a method that finds maximal cliques each time I need to compute C(i). – user Nov 09 '10 at 09:21