# MEC-IP: Efficient Discovery of Markov Equivalent Classes via Integer Programming

arXiv: https://arxiv.org/abs/2410.18147 · HTML: https://mlsanity.com/paper/2410.18147/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 38 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 6 of 6)

- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Properties of Bayesian Belief Network Learning Algorithms](https://mlsanity.com/paper/1302.6792/) (2013)
- [Improving Accuracy and Scalability of the PC Algorithm by Maximizing P-value](https://mlsanity.com/paper/1610.00378/) (2016)
- [A Uniformly Consistent Estimator of Causal Effects under the k-Triangle-Faithfulness Assumption](https://mlsanity.com/paper/1502.00829/) (2015)
- [Learning Bayesian Networks that enable full propagation of evidence](https://mlsanity.com/paper/2004.04571/) (2020)
- [Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests](https://mlsanity.com/paper/2211.06536/) (2022)

## Abstract (arXiv)

This paper presents a novel Integer Programming (IP) approach for discovering the Markov Equivalent Class (MEC) of Bayesian Networks (BNs) through observational data. The MEC-IP algorithm utilizes a unique clique-focusing strategy and Extended Maximal Spanning Graphs (EMSG) to streamline the search for MEC, thus overcoming the computational limitations inherent in other existing algorithms. Our numerical results show that not only a remarkable reduction in computational time is achieved by our algorithm but also an improvement in causal discovery accuracy is seen across diverse datasets. These findings underscore this new algorithm's potential as a powerful tool for researchers and practitioners in causal discovery and BNSL, offering a significant leap forward toward the efficient and accurate analysis of complex data structures.