Quick way to determine the different independence assumptions

Question

This question is different than my previous question in that I'm asking sort of a "meta" question.

Here's two graphical models (a Belief Network and a Markov Network):

I would like to answer the following question:

Do they encode the same set of independence assumptions? If yes, explain why. If not, list all the independence statements that are true in one of the models, but not in the other.

My answer is that they do not encode the same independence assumptions. If I'm going to list the independence assumptions that are true in the right (but not left), then here's the list:

1. $ B \perp\kern-5pt\perp C | D,A $

Actually, that's the only independence assumption which is true in the MN which is not in the BN. So, it this correct, and - what would be the thought process for quickly determining the differences? I'm asking this, because in order for me to determine this the differences, I had to check every combination of variables, and there's a lot of combinations to check

Answer 1

$\newcommand{\pperp}{\perp\kern-5pt\perp}$

If, in a graph with $n$ nodes, we want to check all the conditional independencies (CIs) of the form $(X\pperp Y\;|\;S)$ where $X$ and $Y$ are single nodes and $S$ is a set of nodes not containing $X$ and $Y$, we would have to check $\binom{n}{2}2^{n-2}$ possibilities, where the symmetry in $X$ and $Y$ would half the number. I.e., in this case with five nodes, we have to check 40 CIs.

Let's start with the BN. Two nodes $X$ and $Y$ that are adjacent cannot be d-separated by any set. This leaves us with the five pairs $(A, D), (A, E), (B, C), (B, E), (C, E)$. Those can be easily checked: $$ \begin{align} (A, D) &: (A \pperp D \;|\; B, C), \; (A \pperp D \; | \; B, C, E)\\ (A, E) &: (A \pperp E \;|\; B, C), \; (A \pperp E \; | \; D, S),\quad\mbox{with }S\;\mbox{any element of the powerset }\mathcal P^{\{B, C\}}\\ (B, C) &: (B \pperp C \;|\; A), \quad \mbox{(note the collider (and its child)),}\\ (B, E) &: (B \pperp E \;|\; D, S),\quad\mbox{with }S\;\mbox{any element of the powerset }\mathcal P^{\{A, C\}}\\ (C, E) &: (C \pperp E \;|\; D, S),\quad\mbox{with }S\;\mbox{any element of the powerset }\mathcal P^{\{A, B\}} \end{align} $$ Thus, we have (not counting the symmetric cases) 16 ICs.
How can we check those ICs in general? I know of one function, the function dsep in the R package pcalg, that checks d-separation in BNs. You would have to wrap it with a loop that generates all possible triples $(X, Y, S)$ which should not be too difficult.

Next, we consider the MN. Here, too, adjacent nodes cannot be separated, so the possibilities are reduced to the same pairs as with the BNs: $$ \begin{align} (A, D) &: (A \pperp D \;|\; B, C), \; (A \pperp D \; | \; B, C, E)\\ (A, E) &: (A \pperp E \;|\; B, C), \; (A \pperp E \; | \; D, S)\quad\mbox{with }S\;\mbox{any element of the powerset }\mathcal P^{\{B, C\}}\\ (B, C) &: (B \pperp C \;|\; A, D), \; (B \pperp C \;|\; A, D, E)\\ (B, E) &: (B \pperp E \;|\; D, S),\quad\mbox{with }S\;\mbox{any element of the powerset }\mathcal P^{\{A, C\}}\\ (C, E) &: (C \pperp E \;|\; D, S),\quad\mbox{with }S\;\mbox{any element of the powerset }\mathcal P^{\{A, B\}} \end{align} $$ Thus, we have 17 ICs.
How can we check those ICs in general? To check for a path between two nodes in an MN conditioned on $S$, just remove the nodes in $S$ from the graph, together with all the edges connected to nodes in $S$, and then check whether they are in the same graph component or simply apply any of the many path-finding algorithms out there.

Finally, comparing the two sets above, we find: $$ \begin{align} \mbox{in BN but not in MN} &: (B \pperp C \;|\; A)\\ \mbox{in MN but not in BN} &: (B \pperp C \;|\; A, D), \quad (B \pperp C \;|\; A, D, E).\\ \end{align} $$