Structure Learning for Unfaithful Distributions: The Minimal Dependence Faithfulness

Pouria Ramazi, Hamid Kalantari
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:5661-5676, 2026.

Abstract

Causal discovery algorithms such as {PC} often rely on faithfulness; yet {XOR}-type relations expose violations that {PC} and its weakened-faithfulness variants can miss. In such cases, a target variable $X$ may be independent of each variable $Y_i$ individually, while becoming dependent on $Y_i$ once the remaining variables are conditioned on. We call a minimal set with this property a minimal dependence (MD) set: no proper subset has the same dependence pattern. MD sets of size at least two violate faithfulness. We introduce minimal-dependence faithfulness and a corresponding orientation condition, characterize the resulting {DAG} structure by showing that dependent members of an MD set connect to $X$ directly or through colliders, and define the associated MD-equivalence representation. We then present MD-{PC}, a {PC}-style algorithm that detects such faithfulness violations and, under the proposed assumptions, returns the corresponding candidate class of DAGs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-ramazi26a, title = {Structure Learning for Unfaithful Distributions: The Minimal Dependence Faithfulness}, author = {Ramazi, Pouria and Kalantari, Hamid}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {5661--5676}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/ramazi26a/ramazi26a.pdf}, url = {https://proceedings.mlr.press/v337/ramazi26a.html}, abstract = {Causal discovery algorithms such as {PC} often rely on faithfulness; yet {XOR}-type relations expose violations that {PC} and its weakened-faithfulness variants can miss. In such cases, a target variable $X$ may be independent of each variable $Y_i$ individually, while becoming dependent on $Y_i$ once the remaining variables are conditioned on. We call a minimal set with this property a minimal dependence (MD) set: no proper subset has the same dependence pattern. MD sets of size at least two violate faithfulness. We introduce minimal-dependence faithfulness and a corresponding orientation condition, characterize the resulting {DAG} structure by showing that dependent members of an MD set connect to $X$ directly or through colliders, and define the associated MD-equivalence representation. We then present MD-{PC}, a {PC}-style algorithm that detects such faithfulness violations and, under the proposed assumptions, returns the corresponding candidate class of DAGs.} }
Endnote
%0 Conference Paper %T Structure Learning for Unfaithful Distributions: The Minimal Dependence Faithfulness %A Pouria Ramazi %A Hamid Kalantari %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-ramazi26a %I PMLR %P 5661--5676 %U https://proceedings.mlr.press/v337/ramazi26a.html %V 337 %X Causal discovery algorithms such as {PC} often rely on faithfulness; yet {XOR}-type relations expose violations that {PC} and its weakened-faithfulness variants can miss. In such cases, a target variable $X$ may be independent of each variable $Y_i$ individually, while becoming dependent on $Y_i$ once the remaining variables are conditioned on. We call a minimal set with this property a minimal dependence (MD) set: no proper subset has the same dependence pattern. MD sets of size at least two violate faithfulness. We introduce minimal-dependence faithfulness and a corresponding orientation condition, characterize the resulting {DAG} structure by showing that dependent members of an MD set connect to $X$ directly or through colliders, and define the associated MD-equivalence representation. We then present MD-{PC}, a {PC}-style algorithm that detects such faithfulness violations and, under the proposed assumptions, returns the corresponding candidate class of DAGs.
APA
Ramazi, P. & Kalantari, H.. (2026). Structure Learning for Unfaithful Distributions: The Minimal Dependence Faithfulness. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:5661-5676 Available from https://proceedings.mlr.press/v337/ramazi26a.html.

Related Material