(An) efficient method for reducing search space in bayesian structure learning

Abstract

Recently, efficient search methods are increasingly required for finding large network structures in various applications. Especially in the field of computational biology, several approaches have been studied to infer the relationships between biological entities via network-shaped models such as Bayesian networks. However, the number of considered entities is very large in general. Such large number of entities, i.e., the number of nodes in network models, make it difficult to find target network structures because the search space is super exponential to the number of nodes. To handle such large problems, there have been several approaches to restrict the search space by restricting local network structures around each node. However, such local structure restriction approaches have limitation on their scalability. In this research, a new approach is proposed to restrict the search space of learning Bayesian network structures. We assume that the target network structure has a characteristic of `the network of sub-networks``. By clustering variables, which correspond to the nodes in networks, and estimating directionality of edges between those clusters, we restrict the global structure of target Bayesian networks. Through this global structure restriction approach, target Bayesian networks can be learned in much more reduced time without significant loss of accuracy. An application of using the proposed method is also presented for high-throughput biological data. In the field of computational biology, relationships have been inferred between biological entities using the Bayesian network model with high-throughput data from biological systems. However, most previous approaches limit the number of target entities or use additional knowledge to handle genome-scale problems. The proposed method can efficiently handle such large scale problems without limiting target entities or using additional knowledge.