Equivalence Classes

Equivalence classes of graphs arise in several settings, for instance, during causal discovery algorithms. This guide covers the graph types that represent such classes and how to work with them.

using CausalStructures
using CairoMakie
using NetworkLayout

Equivalence classes of DAGs

A PDAG (partially directed acyclic graph) is a graph whose edges may be directed or undirected, with no directed cycles. Two DAGs are Markov equivalent if and only if they have the same skeleton and the same v-structures (unshielded colliders).

Each Markov equivalence class of DAGs has a unique CPDAG (completed partially directed acyclic graph) representation. In a CPDAG, an edge is directed precisely when it has the same orientation in every DAG in the equivalence class; otherwise it remains undirected.

In CausalStructures, all PDAG types are encoded as subtypes of AbstractPDAG.

Given a DAG, dag_to_cpdag computes its CPDAG:

dag = DAG("C --> X, A --> X + Y, Y --> Z")
cpdag = dag_to_cpdag(dag)
plot(cpdag)

The v-structure C --> X <-- A appears in every DAG in the equivalence class and therefore remains directed. The edges A --- Y and Y --- Z are undirected because no v-structure or Meek rule forces their orientation. count_dags tells us how many DAGs are in the class, and enumerate_dags lists them all:

count_dags(cpdag)

3

enumerate_dags(cpdag)

3-element Vector{DAG}:
 DAG with 5 nodes and 4 edges:
  nodes: A, C, X, Y, Z
  edges:
    A --> X, C --> X, A --> Y, Y --> Z

 DAG with 5 nodes and 4 edges:
  nodes: A, C, X, Y, Z
  edges:
    Y --> A, A --> X, C --> X, Y --> Z

 DAG with 5 nodes and 4 edges:
  nodes: A, C, X, Y, Z
  edges:
    Y --> A, A --> X, C --> X, Z --> Y

When you need one concrete DAG to work with, dag_from_pdag picks one:

dag_from_pdag(cpdag)

DAG with 5 nodes and 4 edges:
  nodes: A, C, X, Y, Z
  edges:
    C --> X, A --> X, A --> Y, Y --> Z

Adjustment sets can be computed on CPDAGs and the result is then valid for every DAG in the equivalence class:

all_adjustment_sets(cpdag, :X, :Z)

2-element Vector{Vector{Symbol}}:
 [:A]
 [:Y]

An MPDAG (maximally oriented partially directed acyclic graph) can, for instance, arise when background knowledge is incorporated during causal discovery, orienting some edges of a CPDAG.

meek_closure propagates all further orientations implied by Meek's rules on a PDAG to obtain an MPDAG:

pdag = PDAG("C --- X, A --> X, A --- Y, Y --> Z")
cpdag = meek_closure(pdag)

MPDAG with 5 nodes and 4 edges:
  nodes: A, C, X, Y, Z
  edges:
    A --- Y, X --> C, A --> X, Y --> Z

Here, X --- C was oriented to X --> C using Meek's rules.

All the methods shown above work on any subtype of AbstractPDAG:

count_dags(pdag)
all_adjustment_sets(cpdag, :X, :Z)

2-element Vector{Vector{Symbol}}:
 [:A]
 [:Y]

julia> cg = PDAG("A --- B --- C --- D --- A")
PDAG with 4 nodes and 4 edges:
  nodes: A, B, C, D
  edges:
    A --- B, B --- C, C --- D, A --- D

julia> is_cpdag(cg)
false

julia> is_mpdag(cg)
true

julia> dag_from_pdag(cg)
ERROR: PDAG cannot be extended to a DAG (Dor-Tarsi failed)

Equivalence classes of MAGs

Maximal Ancestral Graphs (MAGs) naturally arise when some common causes are unobserved: every latent common cause between two observed nodes becomes a bidirected edge (<->) in the MAG. Two MAGs are Markov equivalent if they encode the same conditional independence structure over the observed variables.

Each Markov equivalence class of MAGs has a unique PAG (Partial Ancestral Graph). Like a PDAG for DAGs, the PAG marks each endpoint with the symbol shared by every MAG in the class. A circle (o) at an endpoint means that mark is not invariant; some MAGs in the class have a tail there and others have an arrowhead.

Consider a MAG where A and B share a hidden common cause, C directly causes B, and B directly causes D:

mag = MAG("A <-> B, C --> B --> D")

MAG with 4 nodes and 3 edges:
  nodes: A, B, C, D
  edges:
    A <-> B, C --> B, B --> D

mag_to_pag computes the PAG representing the Markov equivalence class of this MAG, so all MAGs that encode the same conditional independences:

pag = mag_to_pag(mag)

PAG with 4 nodes and 3 edges:
  nodes: A, B, C, D
  edges:
    A o-> B, C o-> B, B --> D

The arrowheads at B on the A-B and C-B edges are invariant: A, B, and C form an unshielded collider at B (since A and C are non-adjacent), so every MAG in the class has an edge pointing into B from both sides. The circle marks at A and C are not invariant; the A-B edge could be A --> B or A <-> B, and similarly for C. The B --> D edge is invariant via Zhang's orientation rule R1: since A and D are non-adjacent and A o-> B --> D, the tail at B is forced in all MAGs.

enumerate_mags lets you explore the equivalence class:

enumerate_mags(pag)

4-element Vector{MAG}:
 MAG with 4 nodes and 3 edges:
  nodes: A, B, C, D
  edges:
    A --> B, C --> B, B --> D

 MAG with 4 nodes and 3 edges:
  nodes: A, B, C, D
  edges:
    A <-> B, C --> B, B --> D

 MAG with 4 nodes and 3 edges:
  nodes: A, B, C, D
  edges:
    A --> B, B <-> C, B --> D

 MAG with 4 nodes and 3 edges:
  nodes: A, B, C, D
  edges:
    A <-> B, B <-> C, B --> D

You can also answer various causal inference questions, see PAG Causal Effects for some examples.