A Transformational Characterization of Unconditionally Equivalent Bayesian Networks

Alex Markham, Danai Deligeorgaki, Pratik Misra, Liam Solus
Proceedings of The 11th International Conference on Probabilistic Graphical Models, PMLR 186:109-120, 2022.

Abstract

We consider the problem of characterizing Bayesian networks up to unconditional equivalence, i.e., when directed acyclic graphs (DAGs) have the same set of unconditional {$d$}-separation statements. Each unconditional equivalence class (UEC) is uniquely represented with an undirected graph whose clique structure encodes the members of the class. Via this structure, we provide a transformational characterization of unconditional equivalence; i.e., we show that two DAGs are in the same UEC if and only if one can be transformed into the other via a finite sequence of specified moves. We also extend this characterization to the essential graphs representing the Markov equivalence classes (MECs) in the UEC. UECs form a partition coarsening of the space of MECs and are easily estimable from marginal independence tests. Thus, a characterization of unconditional equivalence has applications in methods that involve searching the space of MECs of Bayesian networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v186-markham22a, title = {A Transformational Characterization of Unconditionally Equivalent Bayesian Networks}, author = {Markham, Alex and Deligeorgaki, Danai and Misra, Pratik and Solus, Liam}, booktitle = {Proceedings of The 11th International Conference on Probabilistic Graphical Models}, pages = {109--120}, year = {2022}, editor = {Salmerón, Antonio and Rumı́, Rafael}, volume = {186}, series = {Proceedings of Machine Learning Research}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v186/markham22a/markham22a.pdf}, url = {https://proceedings.mlr.press/v186/markham22a.html}, abstract = {We consider the problem of characterizing Bayesian networks up to unconditional equivalence, i.e., when directed acyclic graphs (DAGs) have the same set of unconditional {$d$}-separation statements. Each unconditional equivalence class (UEC) is uniquely represented with an undirected graph whose clique structure encodes the members of the class. Via this structure, we provide a transformational characterization of unconditional equivalence; i.e., we show that two DAGs are in the same UEC if and only if one can be transformed into the other via a finite sequence of specified moves. We also extend this characterization to the essential graphs representing the Markov equivalence classes (MECs) in the UEC. UECs form a partition coarsening of the space of MECs and are easily estimable from marginal independence tests. Thus, a characterization of unconditional equivalence has applications in methods that involve searching the space of MECs of Bayesian networks.} }
Endnote
%0 Conference Paper %T A Transformational Characterization of Unconditionally Equivalent Bayesian Networks %A Alex Markham %A Danai Deligeorgaki %A Pratik Misra %A Liam Solus %B Proceedings of The 11th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2022 %E Antonio Salmerón %E Rafael Rumı́ %F pmlr-v186-markham22a %I PMLR %P 109--120 %U https://proceedings.mlr.press/v186/markham22a.html %V 186 %X We consider the problem of characterizing Bayesian networks up to unconditional equivalence, i.e., when directed acyclic graphs (DAGs) have the same set of unconditional {$d$}-separation statements. Each unconditional equivalence class (UEC) is uniquely represented with an undirected graph whose clique structure encodes the members of the class. Via this structure, we provide a transformational characterization of unconditional equivalence; i.e., we show that two DAGs are in the same UEC if and only if one can be transformed into the other via a finite sequence of specified moves. We also extend this characterization to the essential graphs representing the Markov equivalence classes (MECs) in the UEC. UECs form a partition coarsening of the space of MECs and are easily estimable from marginal independence tests. Thus, a characterization of unconditional equivalence has applications in methods that involve searching the space of MECs of Bayesian networks.
APA
Markham, A., Deligeorgaki, D., Misra, P. & Solus, L.. (2022). A Transformational Characterization of Unconditionally Equivalent Bayesian Networks. Proceedings of The 11th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 186:109-120 Available from https://proceedings.mlr.press/v186/markham22a.html.

Related Material