Source-linked AI summary
Learning high-dimensional directed acyclic graphs with latent and selection variables
Diego Colombo, Marloes H. Maathuis, Markus Kalisch, Thomas S. Richardson
TL;DR
The paper asks how to learn causal information from observed variables when arbitrarily many latent and selection variables make FCI computationally infeasible for large graphs. It introduces RFCI, a faster PAG-learning algorithm using fewer and smaller conditional-independence tests. RFCI and FCI are consistent in sparse high-dimensional settings, have similar estimation performance, and differ only rarely in oracle simulations, while RFCI is feasible for large sparse graphs.
Problem
The problem is learning causal information among observed variables when latent and selection variables are allowed, because FCI is computationally infeasible for large graphs.
Method
The paper introduces RFCI, which learns PAGs using fewer conditional-independence tests and conditioning sets smaller than those used by FCI.
Results
RFCI and FCI are consistent in sparse high-dimensional settings, simulations show similar estimation performance, and RFCI is computationally feasible for high-dimensional sparse graphs.
Takeaways & Limitations
RFCI preserves correct asymptotic causal information while providing a practical alternative to FCI for large sparse graphs.
Takeaways & Limitations
RFCI can produce less informative conditional-independence output, with weaker edge-presence semantics and potentially different skeletons or multiple represented Markov equivalence classes.
Abstract
from arXiv · showhide
We consider the problem of learning causal information between random variables in directed acyclic graphs (DAGs) when allowing arbitrarily many latent and selection variables. The FCI (Fast Causal Inference) algorithm has been explicitly designed to infer conditional independence and causal information in such settings. However, FCI is computationally infeasible for large graphs. We therefore propose the new RFCI algorithm, which is much faster than FCI. In some situations the output of RFCI is slightly less informative, in particular with respect to conditional independence information. However, we prove that any causal information in the output of RFCI is correct in the asymptotic limit. We also define a class of graphs on which the outputs of FCI and RFCI are identical. We prove consistency of FCI and RFCI in sparse high-dimensional settings, and demonstrate in simulations that the estimation performances of the algorithms are very similar. All software is implemented in the R-package pcalg.
1. Introduction.
The paper addresses causal-structure learning with arbitrarily many latent and selection variables, where standard DAG-based methods face representational and computational difficulties. It introduces RFCI as a faster alternative to FCI and establishes its correctness, consistency, and empirical similarity to competing algorithms.
- Motivation: Latent and selection variables complicate causal discovery because they are marginalized or conditioned on and can invalidate direct DAG representations over observed variables.These variables can produce observed independence structures that no DAG over the observed variables entails exactly.
- Motivation: MAGs represent observed-variable causal relationships and conditional independencies when the underlying DAG includes latent and selection variables.PAGs summarize causal features shared by all MAGs in a Markov equivalence class under faithfulness.
- Contributions: RFCI uses fewer conditional independence tests and smaller conditioning sets than FCI, making it much faster while potentially yielding less informative output.The smaller tests may also be more reliable in small samples because high-order conditional-independence tests have low power.
- Contributions: The paper defines graph classes where FCI and RFCI outputs are identical and finds that oracle-output differences are very rare in simulations.The differences are attributed to special structures in the underlying DAG.
- Contributions: FCI and RFCI are proven consistent in sparse high-dimensional settings, with weaker required sparsity conditions for RFCI.The paper attributes this difference to RFCI’s lower computational complexity.
- Contributions: Simulations show similar error counts across algorithms, while RFCI remains the only feasible method for large graphs.The proposed modifications of FCI and AAFCI substantially shorten computation time but do not match RFCI’s feasibility on large graphs.
2. Preliminaries.
The preliminaries establish mixed-graph terminology, path and ancestral concepts, and the separation criteria used to connect graph structure with conditional independence. They also define how latent and selection variables induce MAG representations over observed variables.
- Graphical terminology: Graphs contain vertices representing random variables and edges encoding conditional-independence and ancestral relationships, with directed, bidirected, undirected, and partially marked edge types.Edge endpoints may be tails, arrowheads, or circles, and a star denotes an arbitrary mark.
- Graphical terminology: Paths, cycles, triangles, colliders, noncolliders, unshielded triples, and v-structures provide the structural vocabulary for later orientation rules.A v-structure is an unshielded triple whose middle vertex is a collider.
- Graph classes: DAGs are directed acyclic graphs, while ancestral graphs additionally exclude almost directed cycles and restrict undirected edges.DAGs form a subset of ancestral graphs.
- Separation and independence: D-separation and its ancestral-graph generalization m-separation determine when paths are blocked and thus imply conditional independencies.A path is blocked by a conditioning set when it contains a conditioned noncollider or an unconditioned collider without a conditioned descendant.
- Separation and independence: Faithfulness equates the conditional independencies in a distribution with those implied graphically, supporting causal-structure recovery from independence information.Minimal separating sets are conditioning sets with no redundant subset.
- Latent and selection variables: With vertex partition X ∪ L ∪ S, latent variables are marginalized and selection variables are conditioned on when constructing a unique MAG over observed variables.MAG adjacency is determined by inducing paths relative to the observed variables and selection set.
3. Oracle versions of the algorithms.
The oracle-algorithm section formalizes FCI and RFCI outputs as PAGs representing causal information under faithfulness, then describes their test-and-orientation pipelines and the computational trade-off introduced by RFCI.
- Problem and outputs: The target is to infer ancestral relationships among observed variables from oracle conditional independencies involving observed conditioning sets and selection variables.The inferred causal information is represented by a PAG.
- Problem and outputs: FCI-PAGs encode absence and presence of edges through conditional-independence implications, while arrowheads and tails constrain ancestral relations in compatible DAGs.An arrowhead at Xj excludes Xj as an ancestor of Xi or selection variables, whereas a tail asserts ancestry.
- Problem and outputs: RFCI-PAGs retain the same ancestral-mark interpretations but weaken the conditional-independence meaning attached to edge presence.Consequently, every FCI-PAG is an RFCI-PAG, while RFCI outputs can have different, generally larger skeletons and represent multiple Markov equivalence classes.
- FCI pipeline: Possible-D-SEP is a computable superset of D-SEP formed from paths whose internal vertices are colliders or belong to triangles.FCI uses these sets because the exact D-SEP sets cannot be inferred directly from observed conditional independencies.
- FCI pipeline: FCI begins with a skeleton, orients v-structures, searches Possible-D-SEP conditioning sets for further deletions, and applies orientation rules to maximize edge information.Conditional-independence tests are hierarchically arranged from smaller to larger conditioning sets.
- Computational motivation: FCI’s Possible-D-SEP search can become computationally infeasible when these sets are large, motivating path-based and other modifications that reduce computational effort.The paper organizes modifications including FCIpath, RFCI, and accelerated FCI or Anytime FCI variants.
First proposed modification: FCIpath.
FCIpath reduces the relevant search for adjacent vertices by restricting Possible-D-SEP candidates to paths connecting the pair within its biconnected component.
- FCIpath definition: For adjacent Xi and Xj, pdspath(C,Xi,Xj) retains candidates that lie on a collider-or-triangle path from Xi and also on a path between Xi and Xj.This pair-specific restriction refines the broader Possible-D-SEP set.
- FCIpath computation: The set pdspath(C,Xi,Xj) can be computed by intersecting pds(C,Xi,·) with the biconnected component containing the Xi–Xj edge.The modification first computes all biconnected components of C2, then applies the pair-specific path set during the search.
- FCIpath computation: FCIpath modifies the FCI search pipeline after Step 2, using pdspath during the subsequent conditional-independence search.The construction is designed to avoid testing all candidates in unrestricted Possible-D-SEP sets.
Second class of modifications: CFCI, CFCIpath, SCFCI and SCFCIpath.
The paper develops conservative FCI modifications and RFCI to reduce costly conditioning over large Possible-D-SEP sets while preserving asymptotically correct causal information. RFCI can be less informative than FCI, but its extra tests support sound orientations and characterize when outputs differ or coincide.
- CFCI and SCFCI: Conservative FCI orients only unambiguous unshielded triples as v-structures, while Superconservative FCI also restricts later v-structure and orientation rules to unambiguous triples.These conservative choices can change Possible-D-SEP sets, but subsequent FCI steps otherwise remain unchanged for CFCI.
- RFCI algorithm: RFCI avoids conditional independence tests over Possible-D-SEP subsets, replacing them with additional small conditioning-set tests before orienting v-structures and discriminating paths.This design targets sparse graphs, where Possible-D-SEP sets can nevertheless become large.
- RFCI algorithm: The RFCI algorithm takes conditional independence information among observed variables given selection variables as input and returns an RFCI-PAG under faithfulness.This is the algorithm’s oracle soundness guarantee.
- RFCI algorithm: RFCI Step 2 checks additional conditional dependencies and independencies for unshielded triples, orienting or removing edges according to the resulting evidence.The checks use the current separation set with the middle vertex removed, together with the selection variables.
- Examples: Example 2 shows RFCI retaining X1 ↔X5 because it misses a Possible-D-SEP conditional independence, although the ancestral information remains correct and matches FCI.The missing independence is found by FCI in Step 3 but is not exposed through an RFCI unshielded triple or discriminating path.
- Comparison with FCI: If RFCI and FCI outputs differ, the RFCI skeleton is a strict superset of the FCI skeleton, and extra RFCI edges have no ancestral direction between their endpoints.For such an edge, each RFCI edge mark is a circle or arrowhead.
4. Consistency of FCI and RFCI in sparse high-dimensional settings.
The paper proves consistency for RFCI and several FCI variants in sparse high-dimensional settings, with weaker sparsity requirements for RFCI than for FCI.
- Testing procedure: The consistency proofs use Fisher-transformed sample partial-correlation tests for conditional independence, with α serving as a tuning parameter.The testing rule assumes n > |Y| + 3 and compares the transformed statistic with a normal-theory threshold.
- RFCI consistency: RFCI consistency is established when the number of observed variables grows polynomially with sample size and post-skeleton adjacency sets remain sufficiently sparse.The assumptions also require faithfulness, Gaussianity, and bounded partial correlations.
- RFCI consistency: The RFCI sample output converges in probability to the oracle RFCI output under assumptions (A1)–(A5) for a suitable sequence α_n → 0.The stated error probability is bounded by an exponentially decreasing term and tends to one for correct recovery.
- FCI consistency: FCI consistency requires bounding Possible-D-SEP set sizes, a stronger condition than RFCI’s adjacency-set bound.Possible-D-SEP sets can grow linearly even when adjacency-set sizes remain fixed.
- FCI consistency: Under the stronger condition, sample FCI, FCIpath, CFCI, CFCIpath, SCFCI, and SCFCIpath converge to the true FCI-PAG.The result uses a suitable sequence α_n → 0 under the same remaining assumptions.
5. Numerical examples.
Simulations find very similar estimation accuracy across RFCI and tested FCI variants, while RFCI is substantially faster and uniquely feasible for the largest graphs.
- Simulation design: The simulations compare computation time and estimation performance for RFCI, FCI variants, and Adaptive Anytime FCI under small- and large-scale settings.AAFCI is introduced to adaptively set Anytime FCI’s additional tuning parameter.
- Simulation design: The simulations generate Gaussian data from random DAGs, make selected root variables latent, and evaluate algorithms against the true FCI-PAG.Latent variables are chosen among parentless variables with at least two children, and no selection variables are considered.
- Estimation performance: 50 replicates in the small-scale setting show virtually identical missing-or-extra-edge counts and similar edge-mark differences across algorithms.The setting uses E(N) = 2, n = 1000, and α = 0.01.
- Estimation performance: 91 comparable runs in the large-scale setting show similar missing-or-extra-edge and edge-mark performance among the evaluated algorithms.The setting uses E(N) = 3, n = 1000, and α = 0.01 after excluding incomplete runs.
- Computing time: Conservative FCI and AAFCI adaptations reduce mean-max-pds drastically, whereas the new pdspath definition reduces it only slightly.Possible-D-SEP size is emphasized because considering all subsets becomes infeasible when it reaches roughly 25 vertices or more.
- Computing time: For p′ = 500, RFCI takes about 40 seconds while the fastest FCI modifications take about 10,000 seconds, making RFCI the only feasible algorithm for large graphs.RFCI’s local conditioning tests avoid the larger subsets considered by FCI variants.
6. Discussion.
RFCI reduces the conditional-independence testing burden relative to FCI while preserving the interpretation of tails and arrowheads, although edge presence has weaker meaning. The paper reports comparable estimation performance, weaker sparsity requirements for consistency, and substantially better computational feasibility for high-dimensional sparse graphs.
- RFCI uses fewer conditional independence tests and conditions on fewer variables than FCI.
- RFCI preserves FCI’s interpretation of tails and arrowheads, but an RFCI edge has weaker meaning.
- The outputs of FCI and RFCI are identical for a defined class of graphs, with oracle-version differences rare in simulations.
- RFCI has considerably weaker sparsity conditions for consistency than FCI because its computational complexity is lower.
- RFCI is the only compared algorithm computationally feasible for high-dimensional sparse graphs, while all algorithms perform similarly in estimation.