Source-linked AI summary
Learning Sparse Causal Models is not NP-hard
Tom Claassen, Joris Mooij, Tom Heskes
TL;DR
Causal-model discovery has been considered computationally difficult, with minimal Bayesian-network learning known to be NP-hard. The paper adapts FCI for sparse graphs, then shows that discovery requires polynomially many independence tests even with latent variables and selection bias.
Problem
Causal discovery from probabilistic information is considered difficult and generally thought to be at least as hard as related problems such as minimal Bayesian-network learning.
Source: §1 · p. 1Method
Results
O(N^{2(k+2)}) independence tests suffice in the worst case to learn the sound and complete sparse causal model, even with latent variables and selection bias.
Source: §1 · p. 2Takeaways & Limitations
The authors attribute avoiding exponential complexity to exploiting causal-network structure by breaking discovery into smaller constraint-based subproblems.
Source: §6 · p. 8Further runtime optimization remains a goal while preserving correct handling of hidden variables.
Source: §6 · p. 9
Abstract
from arXiv · showhide
This paper shows that causal model discovery is not an NP-hard problem, in the sense that for sparse graphs bounded by node degree k the sound and complete causal model can be obtained in worst case order N^{2(k+2)} independence tests, even when latent variables and selection bias may be present. We present a modification of the well-known FCI algorithm that implements the method for an independence oracle, and suggest improvements for sample/real-world data versions. It does not contradict any known hardness results, and does not solve an NP-hard problem: it just proves that sparse causal discovery is perhaps more complicated, but not as hard as learning minimal Bayesian networks.
1 Introduction
The paper asks whether sparse causal-model discovery is as hard as minimal Bayesian-network learning, and presents a polynomial-in-independence-tests result for bounded-degree graphs. It targets a completed PAG that captures invariant causal information from observed independencies.
1 Introduction
- An FCI adaptation learns a sound and complete causal model as a PAG in O(N^{2(k+2)}) independence tests, for N variables and maximum observed-variable degree k, despite latent confounders and/or selection bias.Source: §1 · p. 2
Graphical causal models
- A causal DAG represents direct causal interactions; observed independencies can be represented by a MAG, while a PAG records invariant features of the MAG equivalence class.Figure 1 illustrates the DAG, observed-variable MAG, and PAG for N = 4 and k ≤ 3.Source: Graphical causal models · p. 2, Figure 1 · p. 2
C-LEARN
- C-LEARN seeks the completed PAG matching a faithful independence oracle, given N variables and a constant node-degree bound k.An independence oracle answers conditional-independence queries in constant time.Source: C-LEARN · p. 2
2 Why learning minimal Bayesian networks is NP-hard
Minimal Bayesian-network learning is NP-hard because a polynomial DBFAS reduction encodes feedback-set choices. That reduction fails for causal models, which allow a smaller mixed-edge component.
2 Why learning minimal Bayesian networks is NP-hard
- DBFAS reduces polynomially to minimal Bayesian-network learning: edge-components use the smaller configuration unless it creates a directed cycle, encoding a minimum feedback set.The hardness applies with a constant-time independence oracle and bounded maximum node degree k ≥ 3.Source: §2 · pp. 2–3
Causal model reduction
- Causal models allow a C ↔ F edge that Bayesian networks cannot use, so the reduction’s components take the Figure 3 configuration and no longer encode a feedback set.The configuration requires 12 free parameters for C and F.Source: Causal model reduction · pp. 3–4, Figure 3 · p. 3
3 Independence based Causal Discovery
With causal sufficiency, PC searches subsets of adjacent nodes to find separating sets. With latent confounders, needed separators can include nonadjacent nodes, motivating a different way to construct the D-SEP search set.
3.1 Causally sufficient systems
- PC removes edges by testing progressively larger subsets of adjacent nodes, then orients invariant edge marks; degree k gives adjacency-search time O(N^{k+2}).The orientation phase checks path configurations in O(N^3).Source: §3.1 · p. 4
3.2 Causal discovery with latent confounders
- Without causal sufficiency, PC can miss separating sets containing nodes not adjacent to either separated variable, leaving edges that may lead to erroneous causal conclusions.Figure 4(b) illustrates a separator containing nonadjacent Z.Source: §3.2 · p. 4, Figure 4 · p. 5
- FCI identifies a guaranteed superset of D-SEP and tests its subsets, but neither this candidate set nor D-SEP is bounded by degree k, leaving worst-case exponential search.The cited passage gives the resulting order as O(2N).Source: §3.2 · p. 5
- The proposed alternative builds a D-SEP set from nodes adjacent to the separated pair and minimal separating sets inferred during PC’s adjacency search.Source: §3.2 · p. 5
4 D-separating sets
D-sep links can survive the PC adjacency search because separating them may require nodes not adjacent to either endpoint. The section develops a way to identify those links and recover their separating sets using hierarchical minimal-separator information.
4 D-separating sets
- After PC adjacency search, D-sep links remain as skeleton edges because their separating sets can require nonadjacent D-sep nodes.The section outlines how to recognize candidate links, recover the needed nodes, and combine those steps into a sound and complete search strategy.Source: §4 · p. 5
4.1 Identifying D-sep links
- In G+, invariant arrowheads expose a U↔X↔Y↔V pattern around a candidate D-sep link when its ancestors contain no other D-sep-link edges.The augmented skeleton adds invariant arrowheads inferred from single-node minimal dependencies.Source: §4.1 · p. 5
- D-sep links are hierarchically ordered: one may need to be found before another, but the dependencies do not form complex cycles.The hierarchy follows from the rule that if one D-separable pair is part of another pair’s separating set, the reverse does not hold.Source: §4.1 · p. 6
4.2 Capturing the D-sep nodes
- A D-sep node appears in a minimal separating set for another pair among the endpoints, other D-sep nodes, and adjacent ancestors; bounded degree k permits an N^2k search.The candidate nodes can be drawn from at most k neighbors of each endpoint.Source: §4.2 · pp. 6–7
- If I contains a minimal separating set for each nonadjacent pair in An({X, Y}) except {X, Y}, then HIE({X, Y}, I) is a D-separating set.HIE recursively adds nodes appearing in minimal separating sets between pairs already in the hierarchy.Source: §4.2 · p. 6
4.3 Search strategy for D-sep links
- Newly found separating sets can enlarge earlier hierarchies, so candidate links are revisited; the search terminates with an additional N^2 complexity factor.The hierarchy guarantees that when undiscovered D-sep links remain, at least one has no undiscovered D-sep links among its ancestors.Source: §4.3 · p. 7
- Selection effects can override the D-sep pattern, turning a link into an ordinary separable pair or destroying the independence; D-sep links are then rarer.The proofs remain valid with or without selection effects, and the search for D-sep nodes can often be avoided when selection bias is present.Source: §4.3 · p. 7
5 Implementing C-LEARN as FCI+
FCI+ modifies FCI’s D-SEP search to learn a sound and complete causal model with polynomial worst-case independence-test complexity when node degree is bounded. Its complexity analysis gives the bound O(N^2(k+2)), and the paper notes that the implementation can be further optimized.
5 Implementing C-LEARN as FCI+
- The method assumes faithfulness and an underlying causal DAG, while allowing latent variables and selection bias in sparse models.Its sound and complete constraint-based discovery guarantee is stated for models with node degree bounded by k.Source: §5 · p. 7
- FCI+ starts with PC adjacency search, builds an augmented skeleton, searches possible D-SEP links, then applies standard FCI orientation rules to return a complete PAG.For each link, it tests hierarchy-derived candidate conditioning sets and stores minimal separating sets when independence is found.Source: §5 · pp. 7–8
Complexity analysis
- For FCI+, the worst-case complexity is of order O(N 2(k+2)); given maximum node degree k, its running time is polynomial in the number of variables N.Source: Complexity analysis · p. 8
- The authors note that the complexity bounds can be tightened through more efficient graph augmentation, pruning candidate base nodes, and precomputing hierarchies.They present these as possible improvements, rather than an optimal implementation.Source: Complexity analysis · p. 8
6 Discussion
The paper establishes polynomial independence-test complexity for sound and complete sparse causal discovery, including settings with latent variables and selection bias. It attributes the bound to FCI+’s guided D-SEP search, while noting practical runtime benefits and a sample-data power caveat.
6 Discussion
- The paper shows that a sound and complete sparse causal-model representation can be learned in polynomially many independence tests, even with latent variables and selection bias.The implementation is FCI+ with a modified D-SEP search stage.Source: §6 · p. 8
- The authors attribute the tractability to breaking discovery into smaller subproblems, a structure they say arises naturally in constraint-based methods.They leave open whether a polynomial score-based causal-discovery method is possible.Source: §6 · p. 8
- FCI+ uses independence information from earlier stages to guide D-SEP search, yielding worst-case O(N^2(k+2)) independence tests and fewer practical candidate combinations.The theoretical bound is still described as infeasible for large N, while practical runtime is reported as vastly better.Source: §6 · p. 8
- In sample versions, conditioning sets may exceed what is necessary and reduce the statistical power of independence tests.Preliminary random-graph investigations up to 200 variables suggest this effect is often not prominent, but it may arise in some circumstances.Source: §6 · p. 8
- The authors’ stated goal is to approach PC runtime while still handling hidden variables correctly.They propose further restricting or reordering possible D-sep edges as potential optimizations.Source: §6 · p. 9
Appendix A. Proofs
The proof sketches establish properties of D-sep links and show how the hierarchy of previously found separating sets can recover the nodes needed to separate them.
Appendix A. Proofs
- For a D-sep link, the proof uses the absence of separating sets among a node’s adjacent nodes to show the other node is not its ancestor and has no selection bias.The lemma’s non-ancestor conclusion for a minimal separating set follows from an earlier lemma.Source: Appendix A · p. 9
- The Figure 7 path configuration yields identifiable independencies and invariant arrowheads on U1 ↔ X ↔ Y ↔ V1, with U1 not adjacent to V1.Including either U1 or Y in the first separating set makes the corresponding pair dependent.Source: Appendix A · p. 9, Figure 7 · p. 9
- The D-sep link hierarchy follows from the non-ancestor property because otherwise it would introduce a cycle..Source: Appendix A · p. 9
- Each required D-sep node blocks a canonical path and becomes necessary in a minimal separator for a neighboring nonadjacent pair, allowing the hierarchy to recover a D-separating set.The proof argues that this process ultimately reaches independencies among the endpoints and their adjacent nodes.Source: Appendix A · p. 9