# What is the correct definition for completeness in d-separation in directed graphical models?

I was reading Koller's book of probabilistic graphical models and in section 3.3.2 she discusses what properties should hold for d-separation as a method for determining independence. She tries to motivate that hopefully, separation should be sound and complete. Sound in the sense that, if we have that two nodes $X$ and $Y$ are d-separated given some set of nodes in the graph $\vec{Z}$, then we are guaranteed that they are in fact conditionally independent given $\vec{Z}$. Complete in the sense that hopefully, d-separation detects all possible independencies. She tries to make those terms rigorous by providing some explanations and definitions and I wish to ask about the definitions she provides for completeness.

First define that $I(P)$ is the set of all independencies that hold in distribution P and similarly, $I(G)$ are all independencies that hold in graph G. Also, let the notation $d-sep_G(X;Y \perp \vec{Z})$ be defined as; X is d-separated from Y in graph $G$ given (the set of nodes) $\vec{Z}$.

In that section (3.3.2) she defines the following notion:

A distribution P is faithful to G if, whenever $(X \perp Y | \vec{Z}^{\,}) \in I(P)$, then $d-sep_G(X;Y \perp \vec{Z})$. In other word, any independence in P is reflected in the d-separation properties of the graph.

The following is the important part. In trying to define for completeness, she suggests the following notion of completeness:

1) For any distribution P that factorizes over $G$, we have that P is faithful; if X and Y are not d-separated given $\vec{Z}$ in G, then X and Y are dependent in all distribution P that factorize over G.

However, it ends up that this is actually not a good definition for completeness (for some reason which I don't completely understand yet but is not the main issue in this question) and decides to define a weaker definition. The definition is instead:

2) If $(X \perp Y \mid \vec{Z})$ in all distributions P that factorize over $G$, then $d-sep_G(X;Y \mid \vec{Z})$. And the contrapositive: if $X$ and $Y$ are not d-separated given $\vec{Z}$ in G, then X and Y are dependent in some distribution P that factorizes over G

So this is the main issue with my question. Even though she provides two supposedly different definitions, I fail to appreciate what is the true difference between the two. It seems to me that they both say the exact same thing (I know, they don't because she says that the second is "weaker"), but I wanted to understand the difference between the two definition and why the second one is weaker.

Maybe the a good way to approach this problem is by instead of having English sentences describing the definitions, if instead we could express the definitions compactly using only quantifiers and mathematical notation.

The difference is a quantifier. Definition 1 requires dependence in all distributions P, whereas Definition 2 requires dependence in some distribution P.

Here's an example where definition 2 holds, but definition 1 does not. Say we are epidemiologists, interested in learning whether hormonal birth control (BC) increases the risk of deep vein thrombosis (DVT). We have the following graph:

In this picture, BC has a positive direct effect on DVT, but also a negative indirect effect via Pregnancy (BC reduces the risk of pregnancy, and pregnancy increases the risk of DVT). So the total effect of BC on DVT depends on the relative weights of these pathways. Notably, if $\gamma = \alpha\beta$, then the pathways perfectly cancel out, and BC is independent of DVT.

So there is a set of parameterizations of this model where the distribution $P$ is "unfaithful" to the graph: it has an extra independence that we don't get from the graphical structure. However there are plenty of distributions $P'$ that do include the dependence (for example, any linear model where $\gamma \neq \alpha\beta$).

The $d$-separation and faithfulness principles are quite different. $d$-separation tells you all the independence relations that are entailed by the graph; it doesn't say anything about additional independences that might hold. Faithfulness says that the independences entailed by the graphical factorization are the only independences that hold. I hope this example helps make it concrete.

The first claim is that:

if $$X$$ and $$Y$$ are not d-separated given $$\vec{Z}$$ in G, then $$X$$ and $$Y$$ are dependent in all distribution $$P$$ that factorizes over $$G$$.

And a weaker definition is that:

if $$X$$ and $$Y$$ are not d-separated given $$\vec{Z}$$ in G, then $$X$$ and $$Y$$ are dependent in some distribution $$P$$ that factorizes over $$G$$

Let's rephrase the first definition as follows:

"if we see(using our eyes) from a graph $$G$$ that $$X$$ and $$Y$$ are not d-separated given $$\vec{Z}$$, we cannot craft/design a distribution $$P$$(by tweaking its CPDs) 1) that is a factorization following $$G$$ and 2) such that $$X$$ and $$Y$$ are independent. "

That's,

Suppose p factorizes over G. We know I(G) ⊆ I(p). Does it hold that I(p) ⊆ I(G)?

We only need to disprove it by one counterexample. Suppose that a graph is like this: $$A\rightarrow B$$, and we design a distribution p like this:

We see from the graph that even if $$A$$ seems $$dependent$$ of $$B$$ we see from the CPT that $$A$$ and $$B$$ are independent in fact.

Then that kind of completeness doesn't hold, and the definition should be weaker by changing the "all" with "some", allowing a very few(or a set of measure 0 in the space of CPD parameterizations as stated in this article) exceptions.