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

Lifu Liu, Shiyuan He, Jianhua Guo
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:38582-38597, 2025.

Abstract

Efficiently counting Markov equivalent directed acyclic graphs (DAGs) is crucial in graphical causal analysis. Wienöbst et al. (2023) introduced a polynomial-time algorithm, known as the Clique-Picking algorithm, to count the number of Markov equivalent DAGs for a given completed partially directed acyclic graph (CPDAG). This algorithm iteratively selects a root clique, determines fixed orientations with outgoing edges from the clique, and generates the unresolved undirected connected components (UCCGs). In this work, we propose a more efficient approach to UCCG generation by utilizing previously computed results for different root cliques. Our method introduces the concept of super cliques within rooted clique trees, enabling their efficient transfer between trees with different root cliques. The proposed algorithm effectively reduces the computational complexity of the Clique-Picking method, particularly when the number of cliques is substantially smaller than the number of vertices and edges.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-liu25x, title = {An Improved Clique-Picking Algorithm for Counting {M}arkov Equivalent {DAG}s via Super Cliques Transfer}, author = {Liu, Lifu and He, Shiyuan and Guo, Jianhua}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {38582--38597}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/liu25x/liu25x.pdf}, url = {https://proceedings.mlr.press/v267/liu25x.html}, abstract = {Efficiently counting Markov equivalent directed acyclic graphs (DAGs) is crucial in graphical causal analysis. Wienöbst et al. (2023) introduced a polynomial-time algorithm, known as the Clique-Picking algorithm, to count the number of Markov equivalent DAGs for a given completed partially directed acyclic graph (CPDAG). This algorithm iteratively selects a root clique, determines fixed orientations with outgoing edges from the clique, and generates the unresolved undirected connected components (UCCGs). In this work, we propose a more efficient approach to UCCG generation by utilizing previously computed results for different root cliques. Our method introduces the concept of super cliques within rooted clique trees, enabling their efficient transfer between trees with different root cliques. The proposed algorithm effectively reduces the computational complexity of the Clique-Picking method, particularly when the number of cliques is substantially smaller than the number of vertices and edges.} }
Endnote
%0 Conference Paper %T An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer %A Lifu Liu %A Shiyuan He %A Jianhua Guo %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-liu25x %I PMLR %P 38582--38597 %U https://proceedings.mlr.press/v267/liu25x.html %V 267 %X Efficiently counting Markov equivalent directed acyclic graphs (DAGs) is crucial in graphical causal analysis. Wienöbst et al. (2023) introduced a polynomial-time algorithm, known as the Clique-Picking algorithm, to count the number of Markov equivalent DAGs for a given completed partially directed acyclic graph (CPDAG). This algorithm iteratively selects a root clique, determines fixed orientations with outgoing edges from the clique, and generates the unresolved undirected connected components (UCCGs). In this work, we propose a more efficient approach to UCCG generation by utilizing previously computed results for different root cliques. Our method introduces the concept of super cliques within rooted clique trees, enabling their efficient transfer between trees with different root cliques. The proposed algorithm effectively reduces the computational complexity of the Clique-Picking method, particularly when the number of cliques is substantially smaller than the number of vertices and edges.
APA
Liu, L., He, S. & Guo, J.. (2025). An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:38582-38597 Available from https://proceedings.mlr.press/v267/liu25x.html.

Related Material