Structure Learning for Unfaithful Distributions: The Minimal Dependence Faithfulness

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.