Comparison with Other Approaches

As we have already mentioned, there are several works devoted to learning Bayesian networks, within the score+search approach, which use the space of completed PDAGs to carry out the search process. There is a slight difference between the operators considered in the different works: the addition and deletion of edges is considered by [53], within a Markov Chain Monte Carlo process, which also performs Monte Carlo sampling from the space of the orderings of the variables compatible with the current CPDAG. Edge addition and deletion is also used by [67], but within a greedy process that first grows the structure by adding edges and then thins it by deleting edges. Additional operators are considered by [16], including arc reversal and creation of v-structures.

All these methods move through the space of completed PDAGs in the following way: given the current CPDAG $G$, after selecting an operator, applying it to $G$ and obtaining a neighboring PDAG $G'$, they generate a consistent extension $H'$ of $G'$ (a DAG belonging to the equivalence class represented by the PDAG), if one exists. If this is the case (otherwise $G'$ is not a valid configuration), then $G'$ is evaluated by computing the score of $H'$, $g(H':D)$. The completed PDAG representation of $G'$ is then recovered from its consistent extension $H'$.

The process of checking the existence of a consistent extension and generating it is carried out with a procedure called PDAG-to-DAG [32], which runs in time $O(n\cdot e)$ in the worst case, where $e$ denotes the number of edges in the PDAG. Another procedure, called DAG-to-PDAG, is invoked in order to obtain the completed PDAG representation of the new valid configuration. There are different implementations of DAG-to-PDAG [4,15,55,59]. For example, the time complexity of the algorithm proposed by [15] is $O(e)$ on the average and $O(n\cdot e)$ in the worst case.

Our search method does not need to use any of these two procedures: in order to check the validity of a neighboring configuration of an RPDAG $G$, it is only necessary, in some cases, to perform a test to detect either an undirected path or a partially directed path between two nodes in $G$ (implemented by procedures $UC()$ and $DC()$ in Section 4.3). On the other hand, once the search process has explored the neighborhood of $G$ and determined the best neighboring configuration $G'$, $G'$ is not always an RPDAG, and we must generate its RPDAG representation. This generation procedure is also very simple: it consists in firing, starting from a single node $y$, a cascaded process that either directs links away from $y$ or undirects arcs (implemented by procedures $Complete()$ and $Undo()$ in Section 4.3). Note that all these procedures used by our search method are less time-consuming than PDAG-to-DAG and DAG-to-PDAG.

More importantly, our search method can take advantage of the decomposability of many scoring functions, and each RPDAG (except the initial one) can be evaluated by computing only two local scores. However, the methods based on completed PDAGs need to recompute all the local scores, although the algorithm proposed by [56], which operates on completed PDAGs and uses three insertion operators (for arcs, links and v-structures) is also able to score any neighboring configuration using two local scores; however, the validity conditions of some of these operators are not correct.

Finally, [17]⁷ describes an algorithm that searches in the space of completed PDAGs and is also able to evaluate configurations by computing only (up to four) local scores. It uses six operators, link and arc addition, link and arc deletion, creation of v-structures by directing two already existing links, and reversal of arcs. All the operators can be evaluated using two local scores, except reversal and creation of v-structures, that require four local scores. The validity conditions of the operators are established essentially in terms of two conditions: (1) the absence of semi-directed or undirected paths between two nodes that do not pass through certain set of nodes, $S$, and (2) the fact that a certain set of nodes forms a clique. Link insertion and creation of v-structures need the first type of condition, link and arc deletion need the second one, whereas arc insertion and arc reversal require both conditions. The ``path'' validity conditions take time $O(\vert S\vert+e)$ in the worst case, and the ``clique'' conditions take time $O(\vert S\vert^2)$, also in the worst case. This algorithm also requires the PDAG-to-DAG and DAG-to-PDAG procedures to be used.

So, although the validity conditions of the operators in Chickering's algorithm and their postprocessing are somewhat more complex than ours, the advantage is that this algorithm does not have any duplicate representations of the equivalence classes. Whether the computational cost of moves in the CPDAG space can compensate for the larger number of RPDAGs (and the larger number of local scores to be computed) is a matter of empirical evaluation, that will possibly depend on the ``sparseness'' of the specific domain problem considered.