Efficiently Deciding Algebraic Equivalence of Bow-Free Acyclic Path Diagrams

Thijs van Ommen
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:3410-3424, 2024.

Abstract

For causal discovery in the presence of latent confounders, constraints beyond conditional independences exist that can enable causal discovery algorithms to distinguish more pairs of graphs. Such constraints are not well-understood yet. In the setting of linear structural equation models without bows, we study algebraic constraints and argue that these provide the most fine-grained resolution achievable. We propose efficient algorithms that decide whether two graphs impose the same algebraic constraints, or whether the constraints imposed by one graph are a subset of those imposed by another graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-ommen24a, title = {Efficiently Deciding Algebraic Equivalence of Bow-Free Acyclic Path Diagrams}, author = {van Ommen, Thijs}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {3410--3424}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/ommen24a/ommen24a.pdf}, url = {https://proceedings.mlr.press/v244/ommen24a.html}, abstract = {For causal discovery in the presence of latent confounders, constraints beyond conditional independences exist that can enable causal discovery algorithms to distinguish more pairs of graphs. Such constraints are not well-understood yet. In the setting of linear structural equation models without bows, we study algebraic constraints and argue that these provide the most fine-grained resolution achievable. We propose efficient algorithms that decide whether two graphs impose the same algebraic constraints, or whether the constraints imposed by one graph are a subset of those imposed by another graph.} }
Endnote
%0 Conference Paper %T Efficiently Deciding Algebraic Equivalence of Bow-Free Acyclic Path Diagrams %A Thijs van Ommen %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-ommen24a %I PMLR %P 3410--3424 %U https://proceedings.mlr.press/v244/ommen24a.html %V 244 %X For causal discovery in the presence of latent confounders, constraints beyond conditional independences exist that can enable causal discovery algorithms to distinguish more pairs of graphs. Such constraints are not well-understood yet. In the setting of linear structural equation models without bows, we study algebraic constraints and argue that these provide the most fine-grained resolution achievable. We propose efficient algorithms that decide whether two graphs impose the same algebraic constraints, or whether the constraints imposed by one graph are a subset of those imposed by another graph.
APA
van Ommen, T.. (2024). Efficiently Deciding Algebraic Equivalence of Bow-Free Acyclic Path Diagrams. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:3410-3424 Available from https://proceedings.mlr.press/v244/ommen24a.html.

Related Material