PaperlayerView exact revision on arXiv

Source-linked AI summary

Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs

Alain Hauser, Peter Bühlmann

arXiv:1104.2808v2stat.MEcs.DMmath.ST

TL;DR

The paper addresses the limited identifiability of DAG arrow directions from observational conditional independences. It characterizes interventional equivalence classes, represents them with essential graphs, and introduces GIES, whose simulations show improved identifiability and performance comparable to dynamic programming at lower computational cost.

  • Problem

    Observational Markov properties determine a DAG's skeleton but generally do not identify arrow directions, limiting causal interpretation.

  • Method

    The paper defines interventional Markov equivalence, gives a graph-theoretic criterion and essential-graph representation, and develops GIES for learning from multiple interventions.

  • Results

    Interventions rapidly increase causal-model identifiability; GIES matches dynamic programming in most reported cases and has comparable estimate quality at lower computational cost.

  • Takeaways & Limitations

    A small number of intervention experiments can strongly improve causal-structure identifiability, while searching equivalence classes supports effective interventional structure learning.

  • Takeaways & Limitations

    Interpretation of identifiability results requires prudence because orientable-edge counts also reflect the characteristics of the generated DAGs.

Abstract

from arXiv · show

The investigation of directed acyclic graphs (DAGs) encoding the same Markov property, that is the same conditional independence relations of multivariate observational distributions, has a long tradition; many algorithms exist for model selection and structure learning in Markov equivalence classes. In this paper, we extend the notion of Markov equivalence of DAGs to the case of interventional distributions arising from multiple intervention experiments. We show that under reasonable assumptions on the intervention experiments, interventional Markov equivalence defines a finer partitioning of DAGs than observational Markov equivalence and hence improves the identifiability of causal models. We give a graph theoretic criterion for two DAGs being Markov equivalent under interventions and show that each interventional Markov equivalence class can, analogously to the observational case, be uniquely represented by a chain graph called interventional essential graph (also known as CPDAG in the observational case). These are key insights for deriving a generalization of the Greedy Equivalence Search algorithm aimed at structure learning from interventional data. This new algorithm is evaluated in a simulation study.

1 Introduction

The paper addresses the limited causal identifiability of observational DAGs by extending Markov equivalence to multiple interventions and developing a corresponding learning algorithm. It introduces graph representations and GIES for structure learning from combined observational and interventional data.

  • Motivation: Observational Markov properties determine a DAG’s skeleton but generally do not determine arrow directions, limiting causal interpretation.DAGs encode conditional independences, but multiple DAGs can share the same observational Markov property.
  • Motivation: Interventions force variables to chosen values, destroy original causal dependencies, and can improve identification of the underlying causal DAG.The paper considers ensembles combining observational and interventional distributions.
  • Contributions: The paper introduces an algorithmically tractable graphical representation of Markov equivalence classes under specified interventions.The representation supports reading off causal-model identifiability and computation for DAG-learning methods.
  • Contributions: GIES generalizes Greedy Equivalence Search to regularized maximum-likelihood estimation with observational and interventional data.The algorithm is designed for interventional structure learning.
  • Paper organization: The paper establishes an interventional equivalence criterion, characterizes interventional essential graphs, develops search operations, and evaluates GIES experimentally.The proofs are deferred to an appendix, while the experimental evaluation appears in Section 5.

2 Model

The model formalizes observational and interventional distributions through DAG Markov properties, intervention graphs, and families of intervention targets. It defines interventional Markov equivalence and shows how conservative interventions refine observational equivalence while imposing assumptions on the density class.

  • Markov properties: A DAG Markov property represents a positive density through the product of conditional densities given each vertex’s parents.The paper uses this factorization as its basic graphical-model definition.
  • Markov equivalence: Observational Markov equivalence holds when two DAGs define the same set of positive Markov densities.For DAGs, this is equivalent to having the same skeleton and v-structures.
  • Interventions: Stochastic interventions force one or more variables using independent intervention variables, replacing their original causal dependence.The intervened variables are indexed by an intervention target and assigned a joint level density.
  • Interventions: An intervention graph removes all incoming edges into the intervention target, and the resulting interventional density obeys its Markov property.The observational case is recovered by taking the empty intervention target.
  • Interventional data: Interventional datasets contain independent but generally non-identically distributed samples because rows may arise under different intervention targets.The data are represented by the sample matrix together with the target assigned to each sample.
  • Interventional equivalence: Under a conservative target family, interventional equivalence requires shared observational skeletons and v-structures plus matching intervention-graph skeletons.Theorem 10 supplies the graph-theoretic criterion for this equivalence.
  • Scope and assumptions: The framework assumes strictly positive densities, and extending the interventional equivalence results to nonpositive densities remains a conjecture requiring more careful factorization proofs.This restriction may matter for discrete models using counting measure.
  • Discussion: Conservative interventions refine observational Markov-equivalence classes while preserving their observational boundaries.For example, observationally equivalent DAGs can split into distinct interventional classes under targets {∅,{4}}.

3 Essential Graphs

Interventional essential graphs represent DAG equivalence classes under interventions, preserving identifiable orientations while leaving reversible ones undirected. They admit a graph-theoretic characterization and efficient construction, with interventions potentially shrinking equivalence classes substantially.

  • Definitions: For conservative intervention targets, interventional equivalence classes refine observational classes, so their essential graphs contain fewer or equal representatives.The paper states EI(D) ⊂ E{∅}(D) for any conservative family of targets.
  • Characterization: Strong I-protection identifies orientations that cannot vary across the equivalence class because interventions or graph configurations make reversal distinguishable.Reversal can change an intervention-graph skeleton, create or destroy a v-structure, or create a cycle.
  • Algorithms: A DAG representative is obtained by orienting each chain component according to a perfect elimination ordering, while Algorithm 1 constructs the interventional essential graph in polynomial time.The construction successively converts arrows that are not strongly I-protected into lines.
  • Definitions: Interventional essential graphs uniquely represent interventional Markov equivalence classes and encode identifiable orientations as directed edges versus variable orientations as undirected edges.They are defined by the union of all DAGs in an interventional equivalence class.
  • Characterization: Theorem 18 characterizes an interventional essential graph as a chain graph with chordal chain components, additional structural restrictions, and every arrow strongly I-protected.The restrictions include no induced a-b-c subgraph and no undirected edge separated by an intervention target.
  • Example: Identifiability under Interventions: In a linear chain with p vertices, observational data leave p representatives, whereas a single intervention can identify all orientations in the best case or at least half the edges when targeting the central vertex.The central target ⌈p/2⌉ guarantees that at least half of the edges become directed, regardless of the source position.

4 Greedy Interventional Equivalence Search

GIES generalizes GES by greedily searching interventional essential graphs with forward, backward, and turning operations. Its local, score-based implementation relies on score-equivalent decomposable scores and triple-characterized neighboring moves, while complexity depends on chain-component clique sizes.

  • Algorithm overview: GIES greedily maximizes a score over interventional essential graphs rather than searching individual DAGs.This search space accounts for interventional Markov equivalence and yields better estimation than naïve greedy DAG search in the reported simulations.
  • Scoring and efficiency: Each phase selects the highest-scoring candidate and stops when no candidate exceeds the current essential graph.Candidate score evaluation uses a score-equivalent, decomposable function, so equivalent DAGs receive the same score and local score changes can be computed efficiently.
  • Algorithm overview: The algorithm repeatedly executes forward, backward, and turning phases until none can improve the score.Forward moves add one arrow, backward moves remove one arrow, and turning moves reverse one arrow while preserving the edge count.
  • Move characterization: The interventional forward phase uses a shortcut that orients only one chain component to construct a partial I-essential graph after adding an arrow.Caching previously evaluated valid triples can further speed successive forward steps.
  • Move characterization: Every GIES move is characterized by a triple (u, v, C), where C is a clique in v's neighborhood.Finding the best move may require examining all such cliques; bounded vertex degree gives polynomial step complexity, whereas the worst case is exponential.
  • Discussion: The backward and turning phase order is described as somewhat arbitrary, because turning generally improves the score only when few backward steps preceded it.The authors therefore expect changing that order to have little overall effect on performance.

5 Experimental Evaluation

The paper evaluates GIES on simulated interventional data and DREAM4 in silico gene-expression data, restricting both evaluations to Gaussian causal models.

  • Evaluation scope: GIES is evaluated on simulated interventional data and DREAM4 in silico gene-expression data sets.The evaluation is described in Sections 5.2 and 5.3, respectively.
  • Evaluation scope: Both experimental evaluations restrict the causal models to Gaussian settings.

5.1 Gaussian Causal Models

The Gaussian causal-model section represents causal structures with linear structural equations and Gaussian errors, then uses BIC scoring for GIES. Under faithfulness, BIC consistently estimates the true interventional equivalence class in low-dimensional settings.

  • Model specification: Gaussian causal models are parameterized by a DAG-specific weight matrix and a vector of error variances.The weight matrix assigns coefficients to arrows, with zero coefficients outside each node's parent set.
  • Interventional data: Interventional data consist of independent, non-identically distributed Gaussian samples when intervention variables are Gaussian.Both observational and interventional densities are Gaussian under this assumption.
  • Scoring: The method uses the Bayesian information criterion as GIES's score function.The score is based on the maximized Gaussian log-likelihood over DAG-compatible parameters.
  • Model specification: The maximum-likelihood estimator minimizes residual sums of squares for the separate structural equations.This follows from the Gaussian log-likelihood formulation.
  • Consistency: Under faithfulness, the BIC-maximizing DAG consistently estimates the true causal structure in the sense that P[ ˆD ∼I D] →1 as n →∞.The discussion limits its consideration to low-dimensional settings, although BIC is defined for p > n.

5.2 Simulations

Simulations evaluated GIES against alternative search procedures on randomly generated Gaussian causal models, measuring estimated interventional essential graphs with SHD and identifiability. GIES generally improved with more intervention targets, matched DP quality at lower computational cost, and outperformed methods that ignored interventional structure or searched DAGs directly.

  • Simulation design: 4000 randomly generated Gaussian causal models supplied the interventional simulation data used to evaluate GIES.The models were generated with randomized DAG structures, weights, and error covariances.
  • Compared algorithms: GIES was compared with GES, GIES-nt, GDS, and, for p ≤20, dynamic programming over DAGs.GES ignored intervention targets, GIES-nt omitted the turning phase, and GDS searched directly over DAGs.
  • Identifiability under interventions: With single-vertex interventions at 80% of vertices, most simulated DAGs became completely identifiable; target sizes m = 2 and m = 4 required approximately k = 0.6p and k = 0.4p targets.For small target sizes, k targets of size m produced identifiability similar to k · m single-vertex targets, although generated-DAG characteristics affect orientability.
  • Estimation quality: GIES and DP had equal median SHD in 10 out of 12 cases for p ≤20, while GIES achieved comparable quality at much lower computational cost.Estimated graphs were evaluated against true interventional essential graphs using SHD, which combines skeleton errors and orientation errors.
  • Algorithm comparison: GIES generally beat GDS and GIES-nt, combining interventional-equivalence-class search with a turning phase that apparently reduced local-maxima problems.The comparison used SHD between true and estimated interventional essential graphs for p = 30, with similar patterns at other vertex counts.
  • Runtime analysis: GIES runtime followed an approximate O(p^2.8) trend, contrasting with DP’s exponential complexity, although GIES retained exponential worst-case complexity.Regression coefficients were β̂1 = 1.01 for vertices and β̂2 = 0.94 for true-DAG edges.

5.3 DREAM4 Challenge

The DREAM4 evaluation tests GIES on interventional gene-expression prediction and compares it with observational structure-learning methods. GIES generally produced the best predictions, although its advantage was limited by observational-data dominance and acyclic-model misspecification.

  • Evaluation setup: GIES was evaluated on five DREAM4 synthetic gene-regulatory data sets using cross-validation to predict knockout and knockdown expression levels.The data sets contain observational, single-gene knockdown, single-gene knockout, and perturbed time-series measurements, but uncertain interventions were excluded.
  • Evaluation setup: The analysis used 80-point training sets containing interventional data or 61 observational measurements alone, with prediction accuracy measured by mean squared error.GIES, GES, and PC estimated causal models; interventional predictions replaced the intervened variable’s structural equation with a constant.
  • Results: Except for PC(61) on network 1, GIES(80) yielded the best predictions among the evaluated competitors.Figure 15 summarizes MSE differences between GIES(80) and competing methods using boxplots and one-sided sign-test p-values.
  • Results: GIES’s overall prediction performance was comparable with its competitors despite using additional interventional information.The data were dominated by observational measurements, with 61 observational and 20 interventional observations per network.
  • Results: GIES achieved overall rank 10 among 30 DREAM4 evaluations, with network-specific ranks 8, 4, 21, 10, and 3.Except for network 3, the results kept pace with the best third of participating teams despite model misspecification and ignored time-series data.

6 Conclusion

The paper formalizes interventional Markov equivalence and represents its classes with interventional essential graphs, then develops GIES for learning from multiple interventions. Simulations show gains in identifiability and competitive structure-learning and prediction performance, while consistency for interventional data remains unresolved.

  • Contributions: The paper defines a graph-theoretic criterion for DAG equivalence under multiple interventions and characterizes each class by an interventional essential graph.These graphs are defined as the union of all DAGs in an equivalence class and support algorithmic representation.
  • Contributions: GIES extends greedy equivalence search with a turning phase for learning causal structures from observational and multiple-intervention data.The algorithm operates on interventional essential graphs.
  • Findings: With few interventions, the number of non-orientable edges drops quickly, making the gain in causal-structure identifiability quantifiable.For fixed sample size, GIES estimates also approached the true causal structure as intervention vertices increased.
  • Findings: For DAGs with p ≤20 vertices, GIES kept pace with a consistent exponential-time DP approach and beat GDS and GES in the simulations.GIES’s turning phase also improved on GES with observational data.
  • Findings: GIES produced better DREAM4 knockout and knockdown expression predictions than observational estimation methods.The conclusion reports this result for synthetic DREAM4 data sets.
  • Open issue: Consistency of GIES for interventional data was not established because interventional samples are generally not identically distributed.The paper states that extending the observational GES consistency proof is not obvious.

A Graphs

The appendix summarizes the graph notation and basic graph facts used throughout the paper, including conventions for graph types and perfect elimination orderings.

  • Appendix scope: The appendix collects notation and basic graph results, including the perfect-elimination-ordering statements used in Sections 3 and 4.Proofs and listings of these facts are placed in Section A.2.

A.1 Definitions and Notation

This section defines the graph objects and local structures used in the paper, from vertices and edge types to DAGs, chain graphs, chains, cliques, and separation.

  • Basic notation: A graph is defined as vertices and directed edge pairs, with variables indexed by V = [p].The notation uses G = (V, E), excluding self-loops.
  • Edge types: Edges are undirected when both directions occur and directed when only one direction occurs; adjacency holds when either direction is present.The paper denotes adjacency by a b ∈G.
  • Graph structures: A v-structure is an induced a b c pattern, while the skeleton replaces graph edges with undirected adjacency.The skeleton is denoted G^u.
  • Local neighborhoods: Parents, children, neighbors, and adjacent vertices define the local environment of a vertex.These sets are denoted pa_G(a), ch_G(a), ne_G(a), and ad_G(a), respectively.
  • Paths and degree: A chain is a sequence of distinct vertices connected by graph edges, and vertex degree counts the adjacent vertices.The degree is defined as deg_G(a) := |ad_G(a)|.
  • Undirected graph concepts: Complete graphs contain every pairwise adjacency, cliques are complete induced vertex sets, and chordal graphs have a chord in every cycle of length at least four.Separation by a vertex set requires every path between the separated sets to pass through that set.
  • Graph classes: DAGs contain no cycles, whereas chain graphs contain no directed cycles and include undirected graphs and DAGs as special cases.Chain components are the connected components under the graph’s equivalence relation.
  • Orderings: An ordering is a permutation of the vertices, and a perfect elimination ordering requires each vertex to be simplicial in the remaining induced subgraph.A DAG is characterized by the associated preorder being a partial order.

A.2 Perfect Elimination Orderings

Perfect elimination orderings connect chordal graphs to DAG orientations without v-structures and support the construction and implementation of interventional essential graphs.

  • A graph is chordal exactly when it has a perfect elimination ordering.
  • LexBFS: LexBFS produces a perfect elimination ordering for every undirected chordal graph.With suitable data structures, LexBFS runs in O(|E| + |V |).
  • LexBFS: Orienting a chordal graph according to a LexBFS ordering yields a DAG with the graph's skeleton and no v-structures.These orientations provide representatives of essential graphs and support proofs and algorithms in later sections.
  • Constructive consequences: For a chordal graph, prescribed incoming neighbors of a vertex can be realized without v-structures exactly when they form a clique.LexBFS with an appropriate start order constructs the required orientation.
  • Constructive consequences: Proposition 43 uses a clique and a separation condition to construct an orientation with specified directions around adjacent vertices.The resulting DAG has no v-structures, directs edges in C ∪{a} toward a, and directs remaining relevant edges away from that set.

B Proofs

The appendix collects omitted proofs from Sections 2 to 4 for technical completeness and readability.

  • The appendix contains proofs omitted from Sections 2 to 4 to improve the readability of the main text.

B.1 Proofs for Section 2

These proofs establish the density-based and graph-based foundations of interventional Markov equivalence, including how intervention targets constrain DAG orientations.

  • For a target I, the interventional Markov model associated with D equals the observational Markov model of the graph obtained by intervening on I.The proof uses the relationship between interventional densities and the mutilated graph D(I).
  • Under conservative intervention targets, DAGs with the same skeleton and v-structures have matching intervention-induced skeletons when intervention membership forces corresponding arrows.The argument checks both cases in which exactly one endpoint belongs to an intervention target.
  • The proof of the interventional equivalence theorem proceeds through equality of intervention-specific Markov models, induced skeletons, and v-structures.The converse direction reconstructs intervention distributions using truncated factorization and parent-set equality.
  • Conservative target families are used in the construction that recovers a causal model and intervention setting from interventional densities.The proof defines conditional functions from targets excluding each variable and combines them into a positive density.
  • Points (i)–(iii) of the theorem remain equivalent for non-conservative target families, although their proof is more difficult.

B.2 Proofs for Section 3

The proofs characterize interventional essential graphs as chain graphs and establish how their directed edges and orientations encode intervention-specific equivalence.

  • The construction converts arrows on directed cycles into lines and proves that this process yields the same interventional essential graph.This establishes that the graph is already a chain graph.
  • Interventional essential graphs retain the DAG's v-structures and avoid undirected chordless cycles of length at least four.These structural properties adapt corresponding facts from observational essential graphs.
  • Edges whose endpoints are separated by an intervention target are directed in both the interventional essential graph and its chain-graph completion.This prevents conflicting orientations in DAGs obtained from perfect elimination orderings.
  • Every DAG in the interventional equivalence class is obtained by orienting chain components according to perfect elimination orderings.Conversely, such orientations preserve the relevant skeletons and v-structures and remain interventionally equivalent.
  • Every I-essential arrow is strongly I-protected in the interventional essential graph.Protection may arise from intervention membership of exactly one endpoint or from differing parent sets; strong protection is needed for the main characterization theorem.

Proof of Lemma 20

The proof establishes that candidate arrows in the interventional essential graph are strongly I-protected, while checking skeletons and v-structures verifies interventional equivalence.

  • Every arrow in EI(D) is strongly I-protected, and the proof transfers this protection to intermediate graphs under the stated assumptions.
  • Table 2 enumerates configurations for {a, c1, c2}, with labels referring to the strong-protection configurations of Definition 14.
  • The proof checks that D1 and D2 have the same skeleton.
  • It also verifies that D1 and D2 have the same v-structures.

B.3 Proofs for Section 4

These proofs establish structural properties and uniqueness results for interventional graph representatives by preserving skeletons, v-structures, acyclicity, and intervention-equivalence conditions.

  • The proofs establish acyclicity by showing that any hypothetical directed cycle would contradict an existing DAG structure or create a forbidden path configuration.
  • The arguments repeatedly show that graph transformations preserve the skeleton and v-structures required for interventional equivalence.
  • Corollary 26 follows from Proposition 25 because the score function is assumed to be decomposable.
  • Several propositions construct DAGs by selecting neighbor subsets that form cliques, ensuring the requested orientations are realizable.
  • Uniqueness follows by comparing candidate DAGs with identical relevant neighbor sets and checking skeletons, v-structures, and intervention graphs.
  • For intervention graphs, changing only an edge orientation cannot alter the skeleton unless exactly one endpoint is intervened on.
Loading 1104.2808v2…