Operationalising Weaker Faithfulness: Recovery, Ambiguity and Computational Limits

Abstract

Variables can predict an outcome jointly while each is individually independent of it, causing structure learners to discard informative links. We investigate how to operationalise weaker faithfulness through two approaches: selective protection in an adjacency learner and explicit retention of alternative directed graph explanations. Matched experiments show that changes at both an early candidate-removal stage and later pruning can be necessary. In noisy XOR with a descendant (N = 10,000, 20 matched samples), combining reactivation and protection raises complete parent-pair recovery from 0/20 for either change alone to 20/20, while adding false edges. A confirmation study shows that the family estimator can preserve explanations lost by orienting the protected learner's selected skeleton: in one weaker signal XOR condition (N = 10,000) it retains the entire reference family in 48/50 samples, compared with 0/50 for the skeleton adapter. These gains are conditional. Protection can add only error, weaker effects produce false exclusions, and an ordinary faithful-chain comparison favours the PC learner. Complete nonempty family outputs decline at six/eight variables, and all 400 twelve/twenty-variable searches remain unfinished at the reporting cutoff. Neural controls show engineered retention, while the family estimator returns no accepted graph within its application budget. This operationalisation identifies two deletion stages that must be coordinated in the motivating example and shows when direct family search preserves explanations lost by selecting one skeleton. Finite evidence and computation remain substantial barriers to reliable general inference.