Constraint-Based Methods Overview

Overview

Constraint-based methods recover the causal graph by testing the conditional independence (CI) relations in the data. Under the Faithfulness assumption, they exploit the correspondence between CI relations and d-separation.

Mermaid source (click to expand)

> flowchart LR
>     Data[Data] --> CI[CI Tests]
>     CI --> Skeleton[Skeleton Learning]
>     Skeleton --> Orient[Edge Orientation]
>     Orient --> Graph[CPDAG/PAG]
>

Core Idea

Faithfulness assumption: $X \perp_P Y \mid Z \iff X \perp_\mathcal{G} Y \mid Z$

1. Discover independence relations via CI tests
2. Independence ↔ d-separation correspondence
3. Infer the graph structure

Comparison of Main Algorithms

Algorithm	Output	Latent OK	Complexity	Key Feature
PC Algorithm	CPDAG	✗	$O(n^d)$	Standard baseline
FCI Algorithm	PAG	✓	$O(n^{d+2})$	Latent confounders
CPC	CPDAG	✗	$O(n^d)$	Conservative PC
RFCI	PAG	✓	$O(n^d)$	Fast FCI

Common Algorithmic Structure

Phase 1: Skeleton Learning

1. Start with a complete undirected graph
2. For each edge (X, Y):
   - Search over conditioning sets Z ⊆ Adj(X)
   - If X ⊥ Y | Z, remove the edge
   - Store Z in SepSet(X, Y)
3. Result: Skeleton (undirected graph)

Phase 2: Edge Orientation

1. Identify v-structures:
   - In X — Z — Y, if Z ∉ SepSet(X, Y)
   - → X → Z ← Y
2. Apply orientation rules:
   - Meek rules (PC)
   - FCI orientation rules (FCI)
3. Result: CPDAG or PAG

Conditional Independence Test

See Conditional Independence Test:

Test	Data Type	Assumption
Fisher’s z	Continuous	Gaussian
Partial correlation	Continuous	Linear
G-test / χ²	Discrete	-
KCI	Any	Nonparametric

Significance level α: typically 0.01 or 0.05

Advantages and Disadvantages

Advantages

1. Theoretical guarantees

   • Asymptotic consistency under faithfulness
   • Guaranteed recovery of the true MEC (large sample)

2. Interpretable

   • A clear reason for each edge removal/orientation decision
   • SepSet information can be exploited

3. Easy to implement

   • Uses standard CI tests
   • Many implementations exist (pcalg, causal-learn, etc.)

Disadvantages

1. High-dimensional limitations

   • Conditioning set size grows exponentially
   • Requires many CI tests

2. Finite-sample issues

   • CI test power decreases (small n, large conditioning set)
   • Order-dependence (PC)

3. Dependence on faithfulness

   • Fails under unfaithful distributions

Directions for Improvement

Order-independence

• PC-stable: Independent of edge-removal order
• CPC (Conservative PC): Leaves uncertain orientations undirected

Efficiency

• Parallelization: Parallelize CI tests
• RFCI: Skips some of FCI’s tests

Robustness

• Majority voting: Results that agree across multiple subsets

Related Concepts

Algorithm Details

• PC Algorithm - The representative constraint-based algorithm
• FCI Algorithm - Allows latent confounders
• Conditional Independence Test - Types of CI tests

Theoretical Foundations

• Faithfulness - Essential assumption
• d-separation - CI ↔ graph correspondence
• CPDAG - PC output
• PAG - FCI output

Comparison

• Score-Based Methods Overview - Alternative approach
• Hybrid Methods Overview - Combines constraint + score

Key Papers

• Spirtes, Glymour, Scheines (2000). Causation, Prediction, and Search
• Colombo & Maathuis (2014). Order-independent constraint-based causal structure learning
• zangaSurveyCausalDiscovery2023 - Section 3.1