🤖 AI

A General Framework on Conditions for Constraint-based Causal Learning

This paper introduces a general framework based on the concept of "properties" to derive and analyze correctness conditions for constraint-based causal learning algorithms, yielding exact conditions for the PC algorithm and demonstrating that the sparsest Markov representation is the weakest condition for minimal graph outputs while Pearl-minimality alone is insufficient to relax faithfulness.

Original authors: Kai Z. Teh, Kayvan Sadeghi, Terry Soo

Published 2026-04-02

📖 6 min read🧠 Deep dive

CC0 1.0

Original authors: Kai Z. Teh, Kayvan Sadeghi, Terry Soo

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Who caused what?

You have a pile of clues (data) about how different things in the world seem to move together. Maybe you notice that whenever it rains, people carry umbrellas. But did the rain cause the umbrellas, or did the umbrellas cause the rain? (Obviously, it's the rain, but in complex data, it's not always this clear).

This is the job of Causal Discovery: figuring out the true map of cause-and-effect relationships just by looking at the patterns in the data.

The Old Way: The "Perfect World" Rule

For a long time, detectives used a rule called Faithfulness.

The Metaphor: Imagine the true cause-and-effect map is a secret blueprint. The "Faithfulness" rule assumes that the blueprint is perfectly honest. It says: "If two things are connected in the blueprint, they will always show up as connected in the data. If they aren't connected in the blueprint, they will never show up as connected in the data."
The Problem: In the real world, things are messy. Sometimes, two unrelated things accidentally look connected (like a coincidence), or two connected things accidentally look unrelated (like a perfect cancellation). The "Faithfulness" rule is too strict; it breaks easily when reality gets a little weird.

The New Framework: The "Property" Lens

The authors of this paper, Kai Teh, Kayvan Sadeghi, and Terry Soo, built a new universal toolkit (a framework) to help detectives design better algorithms.

Instead of just guessing rules, they introduced the idea of a "Property."

The Metaphor: Think of a "Property" as a specific filter or a lens you put over your data.
- Lens A (Faithfulness): "I only trust maps where every connection is obvious." (Too strict).
- Lens B (Sparsity): "I only trust the simplest map that explains the data." (Like Occam's Razor: the simplest explanation is usually right).
- Lens C (Minimality): "I only trust maps that don't have any unnecessary extra lines."

The paper's big breakthrough is a Two-Way Mirror (Duality):

If you pick a Lens (Property): You can instantly know exactly what conditions the data must meet for your detective work to be correct.
If you want a specific result: You can work backward to find the weakest, most flexible Lens that will get you there.

The Three Big Takeaways

1. The "Goldilocks" Algorithm (The PC Algorithm)

The famous PC Algorithm is like a standard detective tool. It usually works if the "Faithfulness" rule holds.

The Paper's Discovery: The authors used their new framework to look at the PC algorithm and found its exact "Goldilocks" zone. They proved that the PC algorithm works under conditions that are slightly more relaxed than the old "Faithfulness" rule. It's like realizing you don't need a perfect, crystal-clear day to solve a case; you just need enough light.

2. The "Sparsest Map" is the Winner

There are many ways to try to find the "simplest" map. Some say "fewest lines," others say "fewest assumptions."

The Metaphor: Imagine you are drawing a map of a city. You want the map to be simple but accurate.
The Finding: The authors proved that the "Sparsest Markov Representation" (SMR) is the weakest (most flexible) condition that still guarantees you get the right map.
Why it matters: If you want to build a new detective algorithm, you should aim for the SMR condition. It's the "easiest" condition to satisfy while still being correct. Any other "minimality" rule is actually stricter and harder to meet. The SP Algorithm (Sparsest Permutation) is the tool that uses this winning rule.

3. Why "Simple" Isn't Enough (The Pearl-Minimality Trap)

The authors also warned about a trap.

The Metaphor: Imagine you are trying to find the simplest map. If you just say, "Give me the simplest map that fits the data," you might end up with a blank map (no connections at all) or a map with every single street connected (a giant mess). Both are "simple" in a weird way, but neither tells you the truth.
The Finding: To get a meaningful answer, you need a rule called Pearl-minimality. This ensures the map isn't too simple (blank) or too complex (messy).
The Twist: However, just having "Pearl-minimality" isn't enough to relax the strict "Faithfulness" rule. To go beyond Faithfulness, you need to strengthen the rule. You can do this by:
- Adding Background Knowledge (e.g., "We know for a fact that A cannot cause B").
- Using stricter "Lenses" like the ones mentioned in the paper (like V-OUS and collider-stability).

The New Way to Build Algorithms (The Design Paradigm)

Before this paper, developers would:

Build a complex computer program (the algorithm).
Hope it works.
Try to prove it works under strict rules (like Faithfulness).

The New Paradigm (The "Property-First" Approach):

Pick your Lens (Property) first. Decide what kind of "simplest map" you want (e.g., "I want the sparsest map").
Check the Rules. Use the framework to see: "What conditions does the data need to meet for this lens to work?" (e.g., "It needs to satisfy the SMR condition").
Build the Program. Now, build the computer steps to find that specific map.

This is like an architect deciding, "I want a house that uses the least amount of wood but is still strong," before drawing the blueprints. You know exactly what constraints you are working with before you start building.

Summary

This paper gives us a universal translator between "What we want the algorithm to do" and "What the data needs to look like for it to work."

It tells us the PC algorithm is more robust than we thought.
It proves that the Sparsest Map (SMR) is the best, most flexible target for new algorithms.
It warns us that we can't just look for "simple" maps; we need smart simple maps (Pearl-minimality), and sometimes we need to bring in outside knowledge to solve the hardest cases.

It turns the art of causal discovery from a guessing game into a precise engineering discipline.

1. Problem Statement

Constraint-based causal learning algorithms (e.g., PC, FCI, SP) aim to recover the underlying causal structure (graph) from observational data by testing conditional independencies.

The Core Issue: These algorithms are provably correct only under specific, often untestable, assumptions. The most common assumption is Faithfulness (the set of conditional independencies in the data exactly matches the graphical separations of the true graph).
Limitations: Faithfulness is frequently violated in practice (e.g., due to parameter cancellations) and is considered too stringent. While recent algorithms (like Sparsest Permutation or Me-LoNS) have proposed weaker conditions, there is no unified theoretical framework to:
1. Systematically derive the exact correctness conditions for any given constraint-based algorithm.
2. Compare the strength of these conditions across different algorithms.
3. Design new algorithms with controlled correctness conditions before implementing computational steps.

2. Methodology: The "Property" Framework

The authors introduce a theoretical framework based on the concept of a "Property" to create a duality between causal learning algorithms and the conditions under which they work.

Key Definitions

Property ( $A$ ): A relation between a distribution $P$ and a graph $G$ . $A(P, G) = \top$ if $P$ satisfies property $A$ with respect to $G$ .
Algorithm as a Property: Any constraint-based algorithm that outputs a set of graphs $\mathcal{G}(P)$ can be represented as a property $A$ where $A(P, G) = \top \iff G \in \mathcal{G}(P)$ .
Class Property: A property where if $G_1$ and $G_2$ are Markov Equivalent (MEC), then $A(P, G_1) = \top \iff A(P, G_2) = \top$ .
$A$ -Uniqueness ( $U_A(P)$ ): A condition stating that all graphs satisfying property $A$ for a given $P$ belong to the same Markov Equivalence Class (MEC).

The Core Theorem (Theorem 1)

The framework establishes a necessary and sufficient condition for an algorithm to be correct:

An algorithm corresponding to property $A$ is correct (outputs the MEC of the true graph $G_0$ ) if and only if:

$A(P, G_0) = \top$ : The true graph satisfies the property.

$U_A(P) = \top$ : The property $A$ uniquely identifies the MEC (i.e., all graphs satisfying $A$ are Markov equivalent).

This creates a design paradigm:

Select a desired property $A$ .
Analyze the correctness condition ( $A$ and $U_A$ ) to ensure it is not too strong.
Design the computational algorithm to output graphs satisfying $A$ .

3. Key Contributions

A. Exact Correctness Conditions for the PC Algorithm

The authors apply the framework to the PC algorithm, which uses orientation rules to identify colliders and non-colliders in a skeleton. By mapping these rules to local properties ( $n$ for non-colliders, $c$ for colliders), they derive exact, necessary, and sufficient conditions for different implementations of the PC algorithm (e.g., standard vs. conservative PC).

They show that the correctness condition depends on the specific orientation rule used (e.g., Rule 1, 2, or 3 in the paper).
They prove that these conditions are mutually incomparable with other existing conditions (like SMR or V-OUS) in general, though specific implications exist (e.g., Conservative PC implies Sparsest Markov Representation).

B. Hierarchy of Minimality Assumptions

The paper rigorously compares various "minimality" assumptions used in causal discovery (Minimally Markovian, Sparsest Markov, Pearl-minimal, Causal-minimal) for both DAGs and Maximal Ancestral Graphs (MAGs).

Result: The Sparsest Markov Representation (SMR) assumption (used by the SP algorithm) is proven to be the weakest possible correctness condition among all algorithms that output graphs satisfying any standard notion of minimality.
This implies that if one seeks an algorithm based on minimality, the SP algorithm is optimal because it requires the least restrictive assumption to guarantee correctness.

C. Necessity of Strengthening Pearl-Minimality

The authors investigate the requirements for "meaningful" causal learning (avoiding degenerate outputs like complete graphs).

Necessity: Any meaningful property must be at least as strong as Pearl-minimality (no subgraph is Markovian to $P$ ).
Insufficiency: However, Pearl-minimality alone is insufficient to relax the Faithfulness assumption. The authors prove that if an algorithm is based solely on Pearl-minimality, its exact correctness condition collapses back to Faithfulness.
Solution: To achieve correctness under conditions weaker than Faithfulness, Pearl-minimality must be strengthened (e.g., by adding background knowledge or specific stability conditions like V-OUS).

4. Key Results and Findings

Duality of Design: The framework allows researchers to control the strength of an algorithm's correctness condition before writing the code. By choosing a property $A$ with a known support (set of valid $P, G$ pairs), one can guarantee the algorithm works under specific, potentially weaker, assumptions.
PC Algorithm Analysis: The paper provides the first exact characterization of when the PC algorithm (and its variants) succeeds, moving beyond the sufficiency of Faithfulness to necessary and sufficient conditions based on local orientation rules.
Optimality of SP Algorithm: Among all algorithms targeting minimality (sparsest edges, causal minimality, etc.), the Sparsest Permutation (SP) algorithm is optimal because its correctness condition (SMR) is the weakest in the hierarchy.
Background Knowledge: The framework demonstrates how incorporating background knowledge (e.g., forbidden edges) can weaken the overall correctness condition of an algorithm, provided the knowledge is consistent with the true graph.
Counterexamples: The paper provides specific structural equation models (SEMs) and distributions to show that:
- SMR does not imply Faithfulness.
- Faithfulness does not imply SMR.
- Different minimality assumptions yield incomparable correctness conditions in certain graph classes.

5. Significance and Implications

Theoretical Unification: The paper unifies disparate causal discovery algorithms (PC, SP, Me-LoNS) under a single theoretical umbrella, allowing for direct comparison of their underlying assumptions.
Algorithm Design: It shifts the paradigm from "design an algorithm and prove it works" to "select a property with a desirable correctness condition and design an algorithm to satisfy it." This is crucial for developing robust algorithms for real-world data where Faithfulness is often violated.
Practical Guidance: It clarifies that simply assuming "minimality" is not enough to escape the Faithfulness assumption; specific structural constraints (like V-OUS) or background knowledge are required to relax Faithfulness while maintaining meaningful causal inference.
Benchmarking: The derived conditions allow for the precise benchmarking of causal discovery algorithms against specific data-generating processes, determining exactly which assumptions are violated when an algorithm fails.

In summary, this work provides a rigorous mathematical foundation for understanding why causal learning algorithms succeed or fail, offering a blueprint for designing next-generation algorithms that operate under weaker, more realistic assumptions than Faithfulness.