An improved greedy equivalent search method based on relative entropy

As a well-known Bayesian network structure learning algorithm in equivalence class space (E-space), Greedy equivalence search (GES) is used in many fields. However, it encounters high complexity when searching for information from an empty graph. If the initial graph of GES is an equivalence class containing the strongest dependencies instead of an empty graph, its performance will be significantly improved. In this study, we propose a three-phase algorithm to establish the initial graph. First, we design a measure based on relative entropy to evaluate the relation between variables. Then, the variables are connected based on the previously designed metrics and the resulting graph is transformed into E-space. Finally, the resulting graph is used as the initial graph of GES for E-space optimization. We compare the proposed algorithm with GES in efficiency and accuracy, and the results show that our algorithm improves the efficiency and accuracy of GES. Furthermore, extensive comparisons are designed to compare our method with other state-of-the-art methods on benchmarks and real data about COVID-19 pandemic in the UK.