Source-linked AI summary
Order-independent constraint-based causal structure learning
Diego Colombo, Marloes H. Maathuis
TL;DR
The paper addresses order-dependence in constraint-based causal structure learning, where the shared PC-algorithm can yield variable results, especially in high-dimensional settings. It proposes simple modifications that reduce or remove this dependence while preserving high-dimensional consistency under the original conditions. The modifications improve stability in sparse high-dimensional simulations and perform similarly to the original algorithms in low-dimensional settings.
Problem
The PC-algorithm's output depends on variable order, a problem that can be highly pronounced in high-dimensional settings and affect downstream causal-learning algorithms.
Method
The paper proposes simple PC-algorithm modifications that remove part or all of order-dependence and carry over to FCI, RFCI, and CCD.
Results
The modifications improve and stabilize estimation in sparse high-dimensional simulations while performing similarly to the original algorithms in low-dimensional settings.
Takeaways & Limitations
The proposed modifications retain existing high-dimensional consistency results under the original algorithms' conditions while improving stability in sparse high-dimensional settings.
Takeaways & Limitations
The final orientation rules retain a minor order-dependence because edges eligible under multiple rules may be oriented differently depending on rule order.
Abstract
from arXiv · showhide
We consider constraint-based methods for causal structure learning, such as the PC-, FCI-, RFCI- and CCD- algorithms (Spirtes et al. (2000, 1993), Richardson (1996), Colombo et al. (2012), Claassen et al. (2013)). The first step of all these algorithms consists of the PC-algorithm. This algorithm is known to be order-dependent, in the sense that the output can depend on the order in which the variables are given. This order-dependence is a minor issue in low-dimensional settings. We show, however, that it can be very pronounced in high-dimensional settings, where it can lead to highly variable results. We propose several modifications of the PC-algorithm (and hence also of the other algorithms) that remove part or all of this order-dependence. All proposed modifications are consistent in high-dimensional settings under the same conditions as their original counterparts. We compare the PC-, FCI-, and RFCI-algorithms and their modifications in simulation studies and on a yeast gene expression data set. We show that our modifications yield similar performance in low-dimensional settings and improved performance in high-dimensional settings. All software is implemented in the R-package pcalg.
1. Introduction
Constraint-based causal structure-learning algorithms share the PC-algorithm as a first step, whose variable-order dependence can become highly pronounced in high-dimensional data. The paper introduces modifications that reduce this dependence while retaining consistency and improving stability in high-dimensional settings.
- Constraint-based methods use conditional independence tests to learn information about underlying causal structure.
- PC, FCI, RFCI, and CCD share the PC-algorithm as a first step, so PC modifications can carry over to the other algorithms.
- The PC-algorithm's output depends on variable order, and this order-dependence is especially problematic in high-dimensional sparse settings.
- 5361 genes and 63 wild-type yeast organisms produced roughly 5000-edge skeletons across 25 orderings: about 1500 highly stable, 1500 moderately stable, and 2000 unstable edges.
- The same yeast data produced highly variable IDA causal-effect rankings: some ROC curves outperformed the published result, while others were indistinguishable from random guessing.
- The proposed modifications remove part or all of order-dependence and remain consistent in high-dimensional settings under the original algorithms' conditions.
2. Preliminaries
The preliminaries define graph structures, conditional independence, probabilistic interpretation, Markov equivalence, and the causal interpretation of directed paths. These concepts provide the terminology for representing and interpreting causal structure.
- A graph consists of vertices representing random variables and edges representing relationships between variable pairs.
- A partially directed graph may contain directed and undirected edges, and its skeleton replaces all directed edges with undirected ones.
- The adjacency set adj(G, Xi) contains the vertices adjacent to Xi, while a parent of Xi is a vertex with an edge Xj →Xi.
- A directed acyclic graph has directed edges and no directed cycles; a directed cycle combines a directed path with a return edge.
- An unshielded triple has adjacent Xi-Xj and Xj-Xk but nonadjacent Xi-Xk, while a v-structure orients it as Xi →Xj ←Xk.
- Xi ⊥⊥Xj|S denotes independence of Xi and Xj conditional on S, and S is then a separating set for the pair.
- A DAG factorizes a joint density into each variable's conditional density given its parents, and d-separation entails corresponding conditional independencies.
- Markov-equivalent DAGs share a skeleton and v-structures and are uniquely represented by a completed partially directed acyclic graph.
3. The PC-algorithm
The PC-algorithm first finds a skeleton and separation sets, then orients v-structures and other edges. In sample settings, variable ordering can alter skeletons, separating sets, and orientations, whereas the oracle version is correct under faithfulness and perfect conditional-independence information.
- Algorithm structure: Step 1 returns the skeleton and separation sets; Step 2 orients unshielded triples as v-structures, and Step 3 applies rules R1–R3 to orient remaining edges.A triple (Xi, Xj, Xk) is oriented as a v-structure exactly when Xj is absent from sepset(Xi, Xk).
- Step 1: The algorithm starts with a complete undirected graph and deletes an edge when two variables are conditionally independent given a subset of the remaining variables.Conditioning-set sizes increase from ℓ=0 until current adjacency sets are too small; separation sets are stored for deleted edges.
- Oracle version: Under faithfulness and perfect conditional-independence information, PC outputs the CPDAG representing the underlying DAG.Faithfulness equates conditional independence with d-separation, supporting recovery of the skeleton and orientations.
- Sample version: Different variable orderings can produce different, incorrect sample skeletons, including a missing X3−X4 edge and an additional X2−X4 edge.In one ordering, an erroneous deletion of X4−X3 occurs before testing X4−X2; in another, the altered adjacency sets prevent the relevant conditioning set from being considered.
- Oracle versus sample: The oracle version may yield order-dependent separating sets without changing v-structure decisions, because any valid separating set gives the correct decision.For the same pair, different orderings produce {X2} or {X3}, while both preserve X1 → X5 ← X4.
- Sample version: In the sample version, ordering can change separating sets and v-structure decisions, and conflicting orientations can depend on which triple is considered last.The examples show both incorrect v-structures from erroneous tests and alternative orientations for the same edge under different processing orders.
4. Modified algorithms
The paper introduces modifications of the PC-algorithm that remove order-dependence from skeleton estimation, v-structure decisions, and orientation rules, with extensions to FCI and RFCI. These modifications retain oracle correctness and the original high-dimensional consistency guarantees under the same conditions.
- Scope of the modifications: The proposed modifications target order-dependence in the PC-algorithm’s skeleton, v-structure, and orientation stages, as well as related FCI and RFCI procedures.The paper develops oracle and sample versions, then derives corresponding modifications for related algorithms.
- Skeleton estimation: PC-stable stores adjacency sets at each conditioning-set size, preventing edge deletions from changing other conditional-independence checks at that level.This makes the estimated skeleton order-independent and allows parallel processing at each conditioning-set size.
- Skeleton estimation: The PC-stable sample algorithm produces the same skeleton for every variable ordering, while its oracle version is sound and complete under faithfulness and perfect independence information.The oracle output is the CPDAG representing the faithful DAG.
- Determination of the v-structures: CPC-stable and MPC-stable use separating-set information to make sample v-structure decisions order-independent; MPC labels triples using a majority rule and is less conservative than CPC.CPC requires the middle node to occur in all or none of the separating sets, whereas MPC uses a 50% threshold.
- Orientation rules: List-based LCPC-stable and LMPC-stable variants are correct in the oracle version and fully order-independent in the sample version.The list procedure records conflicting orientations and permits bidirected edges.
- Consistency and related algorithms: The modifications preserve high-dimensional consistency for PC, FCI, and RFCI variants under exactly the same conditions as their original algorithms.The key requirement is that conditional-independence tests remain restricted to conditioning sets no larger than the graph degree when no errors occur.
5. Simulations
Simulations show that stabilized algorithms improve estimation and reduce order-dependent variability, especially in high-dimensional settings, while low-dimensional performance is similar. PC-stable and RFCI-stable produce sparser skeletons with fewer errors and better true discovery rates than their original counterparts.
- Overall performance: Modified algorithms performed better than original algorithms in the high-dimensional settings considered, whereas all algorithms performed similarly in the low-dimensional setting.The comparisons covered simulated systems with and without latent variables.
- Skeleton estimation: PC-stable and RFCI-stable returned fewer skeleton-estimation errors than PC and RFCI for every tested α value.Their reduction in false-positive edges outweighed any increase in false-negative edges.
- Skeleton estimation: PC-stable and RFCI-stable achieved better True Discovery Rates than their unstabilized counterparts for all tested α values.The estimated skeletons were generally too sparse relative to the true CPDAGs and PAGs, whose average edge counts were 1000 and 919, respectively.
- Order dependence: For one high-dimensional graph, PC-stable largely captured edges stable across PC’s 20 variable orderings while returning far fewer edges.The original PC algorithm also produced many extra edges that appeared or disappeared across orderings.
- Oriented graph estimation: PC-stable and RFCI-stable significantly improved CPDAG and PAG estimation across α values, while MPC- and CPC-based variants further improved performance over PC-stable.MRFCI- and CRFCI-stable likewise improved over RFCI-stable.
- Variability and orientations: Stabilized versions yielded significantly smaller variance in SHD and SHD edge marks across variable orderings than versions with unstabilized skeletons.MPC-stable and MRFCI-stable provided the best ROC curves among the compared variants, while directed-edge discovery was harder with hidden variables.
6. Yeast gene expression data
On yeast gene expression data, PC produced skeletons and causal-effect estimates that varied with variable ordering, whereas PC-stable produced an order-independent skeleton and generally more stable causal-effect results.
- Skeleton estimation: PC yielded highly order-dependent estimated skeletons, while PC-stable produced the same skeleton across all 26 tested variable orderings.The PC-stable skeleton roughly captured edges stable across the original PC outputs.
- Skeleton estimation: Set 1 contained 1478 edges and Set 2 contained 1700 edges, defined respectively by presence in all or at least 90% of the 26 original-PC orderings.Set 1 included 7 directed edges and Set 2 included 20 directed edges.
- Skeleton estimation: PC-stable recovered about as many stable edges as PC but produced far fewer estimated edges outside the two stability sets.Table 3 reports averages and standard deviations over the 26 variable orderings.
- Causal-effect estimation: PC-stable generally yielded better and more stable IDA results than PC for identifying the largest causal effects from observational data.The target set comprised the top 10% of effects in absolute value, evaluated against interventional data.
- Causal-effect estimation: CPC-stable and MPC-stable nearly eliminated ordering variation but produced almost entirely undirected CPDAGs, causing poor IDA performance.Their graphs contained around 90 directed edges among 2086 total edges.
- Causal-effect estimation: PC-stable with stability selection, with or without permuted variable orderings, produced the best fit across the reported causal-effect results.PC with permuted-order stability selection lost performance initially but performed better later in the curve.
7. Discussion
The discussion presents simple modifications that address order-dependence while retaining the original algorithms’ high-dimensional consistency conditions, with improved stability in sparse high-dimensional settings.
- Motivation: Order-dependence is especially problematic for constraint-based causal learning in sparse high-dimensional settings, despite these methods’ computational efficiency.The paper investigates this issue systematically.
- Contributions: The proposed modifications resolve various sources of order-dependence and are designed to be as simple as possible.They preserve existing soundness, completeness, and high-dimensional consistency results.
- Results: The modifications improve and stabilize estimation in sparse high-dimensional simulations while performing similarly to the original algorithms in low-dimensional settings.The consistency results remain valid under the same conditions as for the original algorithms.
- Caveat: The analyses retain a minor order-dependence from the order in which final edge-orientation rules are applied.The study used the original ordering of those rules.
- Implementation and extensions: The modifications are implemented in the R-package pcalg and can be combined with other adaptations of constraint-based algorithms.The paper specifically mentions hybrid score-based versions and PC∗ as examples.
Appendix A. Additional simulation results
The appendix reports additional simulation results for low-, high-, and medium-dimensional settings.
- Scope: Additional simulation results cover low-dimensional, high-dimensional, and medium-dimensional settings.These results are presented in Appendix Sections A.1, A.2, and A.3.
A.1 Estimation performance in low-dimensional settings
In low-dimensional simulations, stable modifications generally matched the original algorithms on skeleton estimation, while orientation-focused modifications more effectively reduced variation in edge orientations.
- Experimental setup: The low-dimensional simulations evaluated estimation performance for graphs with less sparse structure.The reported experiments varied the conditional-independence testing level α.
- Experimental setup: The simulations without latent variables used 250 weighted DAGs with p = 50, samples of size n = 1000, and 50 random variable orderings per graph.PC, PC-stable, CPC variants, and MPC variants were evaluated across specified α levels.
- Experimental setup: The latent-variable simulations used 120 weighted DAGs with p = 50, samples of size n = 1000, and 20 random orderings of observed variables per graph.Latent variables were introduced by selecting certain parentless variables with at least two children.
- Skeleton estimation: PC and PC-stable had basically indistinguishable skeleton-estimation performance across α values, as did FCI and FCI-stable and RFCI and RFCI-stable.FCI-stable tended to return slightly fewer edges than RFCI-stable because FCI performed more tests.
- Orientation stability: CPC and MPC modifications, including their stable versions, performed better particularly at reducing SHD variance and edge-mark variance.Most order-dependence in the low-dimensional setting was in edge orientation.
- FCI and RFCI: There were only small differences between modifications of FCI and RFCI across the proposed measures.The appendix also reports that modified FCI and RFCI variants had similar behavior in several comparisons.
A.2 Number of tests and computing time
PC-stable performs more tests initially than PC, but these additional tests produce a sparser skeleton and fewer tests at larger conditioning-set sizes. The resulting trade-off makes PC-stable somewhat slower overall in the high-dimensional setting.
- Number of tests: Marginal-correlation tests were identical for PC and PC-stable, while PC-stable performed slightly more than twice as many tests at ℓ = 1.For larger ℓ, PC-stable performed fewer tests because its earlier additional tests produced a sparser skeleton.
- Number of tests: PC-stable performed about 1.39 × 10^5 more tests than PC in total.The absolute difference at large ℓ was rather small because PC also performed relatively few tests there.
- Experimental setting: The high-dimensional comparison used p = 1000, n = 50, α = 0.04 for the test-count analysis and averages over 250 random graphs and 20 variable orderings.The experiments reported averages and standard deviations over the stated random graphs and orderings.
- Computing time: PC-stable was somewhat slower than PC for all values of α.The runtime difference is explained by PC-stable’s tendency to perform more tests.
A.3 Estimation performance in settings where p = n
In settings where p = n, the stable versions of FCI and RFCI produce slightly sparser skeletons and slightly better TDR than their non-stable counterparts. They also improve PAG fit, with M(R)FCI variants especially improving fit in denser graphs.
- Experimental setting: The latent-variable experiments used 250 weighted DAGs with p = 50, expected degree set {2, 4}, n = 50, and 50 observed-variable orderings per graph.Half of the variables with no parents and at least two children were randomly designated latent.
- Skeleton performance: FCI-stable and RFCI-stable produce slightly sparser graphs and slightly better TDR than FCI and RFCI in both settings.Figure 17 evaluates skeleton estimation across different α values using 250 graphs and 50 variable orderings per graph.
- PAG performance: The stable versions of FCI and RFCI produce a better fit to PAGs than their non-stable versions in SHD edge marks.The comparison also considers the variance of SHD edge marks across variable orderings.
- PAG performance: C(R)FCI-stable and M(R)FCI-stable perform similarly for sparse graphs and improve PAG fit, while M(R)FCI-stable still improves fit in denser graphs.The cited comparison distinguishes sparse and denser graph settings.