Adjacency-Faithfulness and Conservative Causal Inference

By J. Ramsey, Jiji Zhang, Peter Spirtes. 2006

301 citations recorded by the source corpus.

Most causal inference algorithms in the literature (e.g., Pearl (2000), Spirtes et al. (2000), Heckerman et al. (1999)) exploit an assumption usually referred to as the causal Faithfulness or Stability condition. In this paper, we highlight two components of the condition used in constraint-based algorithms, which we call "Adjacency-Faithfulness" and "Orientation-Faithfulness". We point out that assuming Adjacency-Faithfulness is true, it is in principle possible to test the validity of Orientation-Faithfulness. Based on this observation, we explore the consequence of making only the Adjacency-Faithfulness assumption. We show that the familiar PC algorithm has to be modified to be (asymptotically) correct under the weaker, Adjacency-Faithfulness assumption. Roughly the modified algorithm, called Conservative PC (CPC), checks whether Orientation-Faithfulness holds in the orientation phase, and if not, avoids drawing certain causal conclusions the PC algorithm would draw. However, if the stronger, standard causal Faithfulness condition actually obtains, the CPC algorithm is shown to output the same pattern as the PC algorithm does in the large sample limit. We also present a simulation study showing that the CPC algorithm runs almost as fast as the PC algorithm, and outputs significantly fewer false causal arrowheads than the PC algorithm does on realistic sample sizes. We end our paper by discussing how score-based algorithms such as GES perform when the Adjacency-Faithfulness but not the standard causal Faithfulness condition holds, and how to extend our work to the FCI algorithm, which allows for the possibility of latent variables.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Causal Inference through a Witness Protection Program (2014, background): “Contradictions in constraints entailed by faithfulness have been exploited before to achieve robust causal inference, as in the Conservative PC algorithm of Ramsey et al. (2006). To the best of our knowledge, we provide here the first algorithm for accommodating faithfulness contradictions in a spac”
CAM: Causal Additive Models, high-dimensional order search and penalized regression (2013, methodology): “Keeping the same setting as above results in SHDs of 1214 ± 37, 1330 ± 40 and 477 ± 19 for PC, CPC and CAM, respectively.”
Order-independent constraint-based causal structure learning (2012, methodology): “We propose two methods to resolve the order-dependence in the determination of the v-structures, using the conservative PC-algorithm (CPC) of Ramsey et al. (2006) and a variation thereof.”
Structural Intervention Distance (SID) for Evaluating Causal Graphs (2013, methodology): “, 2000), conservative PC (Ramsey et al., 2006), greedy equivalent search (GES) (Chickering, 2002) and greedy DAG search based on the assumption of equal error variances (GDSEEV) (Peters and Bühlmann, 2014).”
Comparison of Strategies for Scalable Causal Discovery of Latent Variable Models from Mixed Data (2018, background): “In practice, CFCI tends to give more reliable output at the expense of predicted colliders.”
Constraint-based causal discovery from multiple interventions over overlapping variable sets (2014, methodology): “As far as orientations are concerned, in our experience, FCI is very prone to error propagation, we therefore used the rule in (Ramsey et al., 2006) for conservative colliders.”
Structural Intervention Distance for Evaluating Causal Graphs (2015, methodology): “This setting allows us to use the PC algorithm (Spirtes et al., 2000), conservative PC (Ramsey, Zhang, & Spirtes, 2006), greedy equivalent search (GES) (Chickering, 2002) and greedy DAG search based on the assumption of equal error variances (GDS EEV ) (Peters & B¨uhlmann, 2014).”
Comorbidity: A network perspective (2010, methodology): “For acyclic graphs, there are many correct search algorithms (e.g., PC, Spirtes & Glymour 1991; FCI, Spirtes et al. 1993; Conservative PC or CPC, Ramsey et al. 2006; Greedy Equivalence Search [GES], Meek 1997).”
Learning high-dimensional directed acyclic graphs with latent and selection variables (2011, methodology): “Another possibility to decrease the size of Possible-D-SEP is to use conservative rules to orient v-structures in Step 2 of the FCI algorithm, so that fewer arrowheads are introduced, similarly to the Conservative PC algorithm [15].”
Ancestral Causal Inference (2016, unknown): “Related work on conflict resolution One of the earliest algorithms to deal with conflicting inputs in constraint-based causal discovery is Conservative PC [18], which adds “redundant” checks to the PC algorithm that allow it to detect inconsistencies in the inputs, and then makes only predictions th”
Algorithms for Discovery of Multiple Markov Boundaries (2013, background): “…or ancestral graph G = <V , E> and a joint probability distribution P defined over variables V , P and G are adjacency faithful to one another if every adjacency relation between X and Y in G implies that X and Y are conditionally dependent given any subset of V \ {X, Y} in P (Ramsey et al., 2006).”
Network modelling methods for FMRI (2011, unknown): “CCD (Cyclic Causal Discovery; Richardson and Spirtes, 2001), unlike PC, CPC, or GES, allows for the existence of cycles, also producing a more complicated output.”
Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming (2014, background): “The resulting cPC-algorithm (Ramsey et al., 2006) marks any conflicted v-structures and abstains from the orientation inference, i.”
Detection of Unfaithfulness and Robust Causal Inference (2008, methodology): “It turns out, as reported in Ramsey et al. (2006), the Conservative PC algorithm runs almost as fast as the PC algorithm, and is significantly more reliable than the standard PC algorithm.”
Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part I: Algorithms and Empirical Evaluation (2010, background): “Third, oriented local causal discovery is harder than unorientedon (Ramsey et al., 2006), and it makes sense to examine the ability of the feature selection algorithms for causal discovery in tasks of incremental difficulty, especially since as we will see most of the non-causal algorithms do not…”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, unknown): “PC [223] 1993 constraint yes yes yes no CPDAG CCD [196] 1996 constraint yes yes both no PAG FCI [223] 2000 constraint no yes yes no PAG TPDA [31] 2002 constraint yes yes yes no CPDAG CPC [190] 2006 constraint yes relaxed yes no CPDAG KCL [227] 2007 constraint yes yes yes no CPDAG ION [234] 2008 cons”