The d-separability algorithm answers the question, “From where in the network can information flow to a query node X given evidence nodes Z?” or equivalently, “Which nodes, if observed, would influence X given other evidence nodes Z?” The algorithm is described in the Koller and Friedman book (Probabilistic Graphical Models: Principles and Techniques) as Algorithm 3.1. A adaptation of this as Pythonish pseudocode is included for your reference here:

d-separate.py

However, if a node is unobserved, it may be eligible for pruning even though it is not d-separable from X. That is, we do not need to include it when we do inference. Thus, when we know which nodes are evidence and which are queries, we can expand on the d-separability algorithm to build a more aggressive inference pruning algorithm.

We have two main issues to consider.

Consider the example where we have a Bayesian network with two nodes, $X$ and $\theta$, distributed as follows:

$\theta \sim N(\mu, \tau^2)\,$

$X \sim N(\theta, \sigma^2)\,$

where $\mu$, $\tau^2$, and $\sigma^2$ are constants.

Initially, it may appear possible to prune $\theta$: the node is unobserved, so it has no information to give to X. However, $\theta$ cannot actually be pruned. One way to look at this is to note that there is information in the parameters of $\theta$.

We would like to be able to prune all nodes that are not either evidence nodes, or along some active path to an evidence node. The d-separability algorithm searches through the network and finds all reachable nodes but is over zealous in that it adds all non-d-separable nodes to the “do not prune” list whether they lead to evidence or not. You will need to modify the algorithm such that it lets nodes be pruned.