Ancestral graph

Markov equivalence

Two ancestral graphs are Markov equivalent if they encode the same set of conditional independence relations. The independence relations in an ancestral graph are determined using m-separation, a graphical criterion that generalizes d-separation from DAGs to ancestral graphs.

A collider on a path is a vertex where two arrowheads meet. A non-collider on a path is any vertex on the path that is not a collider. A collider may have an order, which indicates the minimum number of vertices on certain discriminating paths associated with that collider. A discriminating path for a vertex ${\displaystyle b}$ in an ancestral graph is a path ${\displaystyle \pi =⟨x,q_1,\dots ,q_p,b,y⟩}$ ${\displaystyle (p\ge 1)}$ where:

• ${\displaystyle x}$ is not adjacent to ${\displaystyle y}$
• Every vertex ${\displaystyle q_i}$ ${\displaystyle (1\le i\le p)}$ is a collider on ${\displaystyle \pi }$ and a parent of ${\displaystyle y}$

For maximal ancestral graphs, Markov equivalence can be characterized graphically: two MAGs are Markov equivalent if and only if they have:

• The same adjacencies (pairs of vertices connected by some edge)
• The same unshielded colliders (colliders on unshielded paths where the two vertices adjacent to the collider are not themselves adjacent)
• The same colliders with order on discriminating paths

This characterization leads to a polynomial-time algorithm for determining whether two maximal ancestral graphs are Markov equivalent, running in ${\displaystyle O(n{e}^4)}$ time where ${\displaystyle n}$ is the number of vertices and ${\displaystyle e}$ is the number of edges.

Applications

Ancestral graphs are used to depict conditional independence relations between variables in Markov models. They are particularly useful for representing the independence structure over observed variables when some variables in an underlying DAG model are unobserved (latent) or when data are sampled from a specific sub-population determined by selection variables.

Ancestral graphs are advantageous because they can represent causal relationships without explicitly including latent variables in the model, which makes the search space tractable for causal discovery algorithms. Unlike DAG models with latent variables, which create an infinite search space unless the number of latent variables or network topology is constrained, ancestral graphs provide a finite representation.

Ancestral graphs are closely related to inducing path graphs (IPGs), another graphical representation for causal systems with latent variables. While syntactically MAGs form a subclass of IPGs (as MAGs do not contain almost directed cycles while IPGs may), PAGs generally reveal more qualitative causal information than partially oriented inducing path graphs (POIPGs). This makes ancestral graphs particularly advantageous for causal discovery and inference tasks.

Ancestral graphs enable the estimation of causal effects from observational data even when the system is causally insufficient (containing unmeasured common causes). The LV-IDA algorithm (Latent Variable Intervention-calculus when the DAG is Absent) extends the IDA approach to estimate bounds on causal effects when latent variables may be present. Unlike methods that assume causal sufficiency (no unmeasured confounders), this approach can identify when causal effects are non-identifiable and provide informative bounds instead of point estimates.

Causal discovery

The FCI algorithm (Fast Causal Inference) is a procedure for learning causal structure from observational data in the presence of latent confounders and selection bias. The algorithm outputs a partial ancestral graph (PAG), which represents a Markov equivalence class of MAGs. Zhang (2008) established that with additional orientation rules beyond those in the original FCI algorithm, the procedure is complete. That is, it can discover all aspects of causal structure that are uniquely determined by conditional independence relations, under standard causal inference assumptions.

The completeness of orientation rules for PAGs has important implications for identifying invariant relationships under interventions. A conditional probability ${\displaystyle P(Y|Z)}$ is invariant under an intervention on ${\displaystyle X}$ if the probability remains unchanged after the intervention. PAGs provide complete graphical criteria for determining when such invariance holds, meaning they can identify all invariant relationships that are uniquely determined by the conditional independence structure.

Do-calculus

Ancestral graphs support causal reasoning about the effects of interventions. Zhang (2008) extended Pearl's do-calculus to the context of ancestral graphs, enabling causal inference when only an equivalence class of causal structures (represented by a PAG) is known rather than a unique causal DAG. This calculus provides rules for determining when post-intervention probability distributions can be identified from pre-intervention (observational) data, even when the exact causal structure is not uniquely determined.

The extension requires distinguishing between visible and invisible directed edges in a MAG. A directed edge ${\displaystyle A\to B}$ is visible if there exists a vertex ${\displaystyle C}$ not adjacent to ${\displaystyle B}$ such that either there is an edge between ${\displaystyle C}$ and ${\displaystyle A}$ that is into ${\displaystyle A}$, or there is a collider path between ${\displaystyle C}$ and ${\displaystyle A}$ that is into ${\displaystyle A}$ and every vertex on this path is a parent of ${\displaystyle B}$. Otherwise the edge is invisible. This distinction determines how graph manipulations affect the correspondence between a MAG and its underlying DAGs.

The calculus involves two types of graph manipulations:

• Lower-manipulation (denoted ${\displaystyle M_{\mathbf{X}}}$): For visible edges out of variables in ${\displaystyle \mathbf{X}}$, delete them; for invisible edges out of variables in ${\displaystyle \mathbf{X}}$, replace them with bidirected edges
• Upper-manipulation (denoted ${\displaystyle M^{\mathbf{X}}}$): Delete all edges into variables in ${\displaystyle \mathbf{X}}$

These manipulations allow formulation of graphical conditions under which certain probabilistic equalities hold, such as when ${\displaystyle P(\mathbf{y}|\text{do}(\mathbf{x}),\mathbf{w})=P(\mathbf{y}|\mathbf{x},\mathbf{w})}$. The PAG-based do-calculus is formulated in terms of definite m-separation, which requires the absence of possibly m-connecting paths rather than just m-connecting paths.

A central application is determining invariance under interventions: a conditional probability ${\displaystyle P(Y=y|Z=z)}$ is invariant under an intervention ${\displaystyle X:=x}$ if the post-intervention probability equals the pre-intervention probability. Graphical conditions for such invariance can be checked directly from a PAG without enumerating all compatible DAGs.