A stage-driven construction algorithm of undirected independence graph for Bayesian network structure learning

Decomposition structure learning algorithms are widely adopted to recover Bayesian network structures. In the recursive process of separation phase, the network partition is obtained through recursively two steps: constructing the undirected independence graph (UIG) and decomposing with the help of partition methods. UIG as the basis for decomposition directly affects the result of the network partition and then impacts the accuracy of output structure. Existing construction algorithms adopt a fixed type of UIG in the recursive process and researches divide into two directions: constructing moral graph and moral graph with extra edges. The former suffer from the problem that computational complexity of recovering all conditional independences (CIs) is too high to divide network well due to relatively complex networks at the beginning of the recursive process, while the latter suffer from the problem that the network partition is hard to find by insufficient expression degree of CIs due to relatively simple networks at the end of the recursive process. The reason is that the fixed type of UIG can not cope with variation of network size. Therefore, this paper proposes a stage-driven construction algorithm considering variation of network size in the recursive process. Different from other construction algorithms, the proposed algorithm designs the network scale factor to achieve the stage division of the recursive process, and selects different algorithms at different stages to build appropriate UIGs through demand analysis. Experiments on different benchmark networks verify that the proposed algorithm can obtain better performances compared with other representative algorithms.