Structure Learning for Unfaithful Distributions: The Minimal Dependence Faithfulness

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.