An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer

Lifu Liu, Shiyuan He, Jianhua Guo

International Conference on Machine Learning 2025 · Oral

This talk introduces an innovative approach to a fundamental problem in causal inference: efficiently counting the number of **Markov Equivalent DAGs (MEC)**. Presented by Lifu Liu, Shiyuan He, and Jianhua Guo at ICML 2025, the work unveils the **Improved Clique-Picking (ICP) algorithm**, which significantly enhances the computational efficiency of determining the size of an MEC. This problem is critical because observational data often cannot uniquely identify a single Causal Directed Acyclic Graph (DAG), instead yielding an MEC—a set of DAGs that all encode the same conditional independence relationships. Understanding the size of this equivalence class is paramount for quantifying the inherent causal uncertainty in a given dataset.

AI review

Liu, He, and Guo present the Improved Clique-Picking (ICP) algorithm, which reduces the complexity of a specific bottleneck step in MEC size counting from M*(V+E) to M^2 via a clever structural transfer mechanism called SC-Trans. The contribution is technically honest, the improvement is real, and the empirical results are consistent with the theoretical claim. This is competent, incremental algorithmic work on a legitimate problem in causal inference — but it is narrow, and the article's framing significantly overstates both the novelty and the practical reach of the result.