Exploiting Symmetry of Independence in d-Separation

In this paper, we exploit the symmetry of independence in the implementation of d-separation. We show that it can matter whether the search is conducted from start to goal or vice versa. Analysis reveals it is preferable to approach observed v-structure nodes from the bottom. Hence, a measure, called depth, is suggested to decide whether the search should run from start to goal or from goal to start. One salient feature is that depth can be computed during a pruning optimization step widely implemented. An empirical comparison is conducted against a clever implementation of d-separation. The experimental results are promising in two aspects. The effectiveness of our method increases with network size, as well as with the amount of observed evidence, culminating with an average time savings of 9% in the 9 largest BNs used in our experiments.