In Bayesian network graphs, how to systematically search for conditional independent nodes?

Question

In Bayesian network graphs, how to systematically search for pairs of conditional independent nodes, and the associated condition node(s)? Is there some simple rules or algorithms to follow?

Answer 1

There is the Bayes-Ball Algorithm, described in this paper: http://www.gatsby.ucl.ac.uk/~zoubin/course05/BayesBall.pdf

On page 22 of these slides there is a handy diagram that summarizes the algorithm: http://ai.stanford.edu/~paskin/gm-short-course/lec2.pdf

Answer 2

Yes, you can find conditionally independent nodes by evaluating the graphical structure of the Bayesian network. Check out the notion of D-separability which provides 3 rules:

1) X -> Y -> Z

2) X <- Y -> Z

For both (1) and (2), Z is conditionally independent of X given Y

3) X -> Y <- Z
X and Z are marginally independent, however, given Y (or any descendant of Y), they become conditionally dependent!

Andrew Moore has some explanation of these rules on his website.