DSeparation#
Algorithm for testing dseparation in DAGs.
dseparation is a test for conditional independence in probability distributions that can be factorized using DAGs. It is a purely graphical test that uses the underlying graph and makes no reference to the actual distribution parameters. See [1] for a formal definition.
The implementation is based on the conceptually simple linear time algorithm presented in [2]. Refer to [3], [4] for a couple of alternative algorithms.
Here, we provide a brief overview of dseparation and related concepts that are relevant for understanding it:
Blocking paths#
Before we overview, we introduce the following terminology to describe paths:
“open” path: A path between two nodes that can be traversed
“blocked” path: A path between two nodes that cannot be traversed
A collider is a triplet of nodes along a path that is like the following:
... u > c < v ...
), where ‘c’ is a common successor of u
and v
. A path
through a collider is considered “blocked”. When
a node that is a collider, or a descendant of a collider is included in
the dseparating set, then the path through that collider node is “open”. If the
path through the collider node is open, then we will call this node an open collider.
The dseparation set blocks the paths between u
and v
. If you include colliders,
or their descendant nodes in the dseparation set, then those colliders will open up,
enabling a path to be traversed if it is not blocked some other way.
Illustration of Dseparation with examples#
For a pair of two nodes, u
and v
, all paths are considered open if
there is a path between u
and v
that is not blocked. That means, there is an open
path between u
and v
that does not encounter a collider, or a variable in the
dseparating set.
For example, if the dseparating set is the empty set, then the following paths are
unblocked between u
and v
:
u < z > v
u > w > … > z > v
If for example, ‘z’ is in the dseparating set, then ‘z’ blocks those paths
between u
and v
.
Colliders block a path by default if they and their descendants are not included in the dseparating set. An example of a path that is blocked when the dseparating set is empty is:
u > w > … > z < v
because ‘z’ is a collider in this path and ‘z’ is not in the dseparating set. However, if ‘z’ or a descendant of ‘z’ is included in the dseparating set, then the path through the collider at ‘z’ (… > z < …) is now “open”.
Dseparation is concerned with blocking all paths between u and v. Therefore, a
dseparating set between u
and v
is one where all paths are blocked.
Dseparation and its applications in probability#
Dseparation is commonly used in probabilistic graphical models. Dseparation connects the idea of probabilistic “dependence” with separation in a graph. If one assumes the causal Markov condition [5], then dseparation implies conditional independence in probability distributions.
Examples#
>>>
>>> # HMM graph with five states and observation nodes
... g = nx.DiGraph()
>>> g.add_edges_from(
... [
... ("S1", "S2"),
... ("S2", "S3"),
... ("S3", "S4"),
... ("S4", "S5"),
... ("S1", "O1"),
... ("S2", "O2"),
... ("S3", "O3"),
... ("S4", "O4"),
... ("S5", "O5"),
... ]
... )
>>>
>>> # states/obs before 'S3' are dseparated from states/obs after 'S3'
... nx.d_separated(g, {"S1", "S2", "O1", "O2"}, {"S4", "S5", "O4", "O5"}, {"S3"})
True
References#
Pearl, J. (2009). Causality. Cambridge: Cambridge University Press.
Darwiche, A. (2009). Modeling and reasoning with Bayesian networks. Cambridge: Cambridge University Press.
Shachter, R. D. (1998). Bayesball: rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams). In , Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (pp. 480–487). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
Koller, D., & Friedman, N. (2009). Probabilistic graphical models: principles and techniques. The MIT Press.

Return whether node sets 

Determine if a dseparating set is minimal. 

Compute a minimal dseparating set between 'u' and 'v'. 