PaperlayerView exact revision on arXiv

Source-linked AI summary

Nested Markov Properties for Acyclic Directed Mixed Graphs

Thomas S. Richardson, Robin J. Evans, James M. Robins, Ilya Shpitser

arXiv:1701.06686v6stat.ME

TL;DR

The paper addresses equality constraints in latent-variable DAG margins that are not ordinary conditional independences. It represents these constraints as kernel conditional independences under fixing, defines nested Markov models for ADMGs, and shows their relevance to latent-DAG margins and causal-effect identification.

  • Problem

    Latent-variable DAG margins can impose nonparametric equality constraints beyond conditional independences, while ordinary observed independences may be insufficient for model characterization and learning.

  • Method

    The paper uses a fixing operation that generalizes conditioning and marginalization to construct kernels and defines ADMG-associated nested Markov models through global and ordered local Markov properties and factorization.

  • Results

    The paper proves that latent-variable DAG margins belong to the corresponding nested Markov models and gives a fixing-based characterization of identifiable causal effects.

  • Takeaways & Limitations

    Nested Markov models capture equality constraints useful for causal inference and computationally efficient marginalization, while connecting these constraints to Tian and Pearl's constraint set.

  • Takeaways & Limitations

    The nested Markov model can include distributions that violate additional inequality constraints imposed by hidden-variable DAGs.

Abstract

from arXiv · show

Conditional independence models associated with directed acyclic graphs (DAGs) may be characterized in at least three different ways: via a factorization, the global Markov property (given by the d-separation criterion), and the local Markov property. Marginals of DAG models also imply equality constraints that are not conditional independences; the well-known ``Verma constraint'' is an example. Constraints of this type are used for testing edges, and in a computationally efficient marginalization scheme via variable elimination. We show that equality constraints like the ``Verma constraint'' can be viewed as conditional independences in kernel objects obtained from joint distributions via a fixing operation that generalizes conditioning and marginalization. We use these constraints to define, via ordered local and global Markov properties, and a factorization, a graphical model associated with acyclic directed mixed graphs (ADMGs). We prove that marginal distributions of DAG models lie in this model, and that a set of these constraints given by Tian provides an alternative definition of the model. Finally, we show that the fixing operation used to define the model leads to a particularly simple characterization of identifiable causal effects in hidden variable causal DAG models.

1. Introduction.

The paper introduces nested Markov models for equality constraints beyond conditional independence in latent-variable DAG margins, representing them through fixing operations on ADMGs. It establishes equivalent characterizations, containment of latent-DAG margins, computational benefits, and implications for causal-effect identification.

  • 1. Introduction.: Latent-variable DAG margins can satisfy nonparametric equality constraints even when their observed distribution has no conditional independences.The Verma constraint is a central example, and ordinary faithfulness-based structure learning can therefore return a saturated, uninformative graph.
  • 1. Introduction.: The paper defines nested Markov models for ADMGs by treating Verma-like constraints as conditional independences in kernels produced by fixing.Fixing generalizes conditioning and marginalization, while the resulting kernels have a causal interpretation as identified interventional distributions.
  • 1. Introduction.: Every marginal distribution of a latent-variable DAG lies in the nested Markov model associated with its latent-projection ADMG, although the converse can fail because hidden-variable DAGs may impose additional inequality constraints.Instrumental inequalities are cited as examples of such additional constraints.
  • 1. Introduction.: The fixing framework supports computationally efficient marginalization and a simple characterization of identifiable causal effects in hidden-variable causal DAGs.The paper also relates the nested model to the constraint set developed by Tian and Pearl.

2. Latent variable DAG models.

Latent-variable DAGs can be represented by ADMGs and CADMGs, whose m-separation and kernel-based operations capture constraints beyond ordinary observed conditional independences.

  • Latent projection converts a DAG with latent variables into a mixed graph whose m-separation relations match the DAG’s observed d-separation relations.
  • ADMG latent projections also encode nonparametric constraints such as Verma constraints beyond ordinary conditional independences.
  • CADMGs distinguish random vertices from fixed indexing vertices, allowing kernels to represent distributions obtained through operations beyond standard conditioning.
  • Kernel independence extends conditional independence to objects indexed by fixed variables, while retaining the semigraphoid axioms.
  • Fixing preserves selected independence relations and transforms districts into subsets after removing a fixed vertex.

3. Nested Markov models.

Nested Markov models impose Markov and factorization constraints across graphs and kernels reached by valid fixing sequences. Their central invariance theorem makes the resulting graph and kernel depend on the fixed set rather than its valid ordering.

  • The nested Markov model is defined through global Markov properties and factorization across all valid fixing sequences.
  • Global nested Markov, ordered local nested Markov, and nested factorization characterizations are equivalent.
  • 3.1. Invariance to the order of fixing in an ADMG.: Any two valid fixing sequences that fix the same vertices produce the same reachable graph and kernel under the nested Markov model.
  • 3.1. Invariance to the order of fixing in an ADMG.: The order-invariance result permits fixing operators to be indexed by the set of fixed vertices whenever a valid sequence exists.
  • Reachable kernels can be constructed from kernels for intrinsic sets through the simplified nested factorization.
  • Complete ADMGs yield saturated nested Markov models, while saturation generally depends on Markov-blanket conditions across valid fixing sequences.

4. Connections with causal inference.

The fixing operation connects latent-variable DAG marginalization with nested Markov models and causal-effect identification. The section establishes that DAG marginals satisfy nested constraints and that fixing supports an identification characterization.

  • DAG marginals with latent variables lie within the nested Markov model associated with their latent projection.
  • When a vertex is not fixable, its intervention distribution may not be identifiable from the observed marginal distribution.
  • Latent-variable DAG models can impose additional inequality constraints beyond those captured by the nested Markov model.
  • Fixing is interpreted causally through intervention distributions and is closely related to identifying causal effects.
  • Theorem 48 characterizes identification using intrinsic districts: if the relevant districts are intrinsic, the causal effect is identifiable; otherwise it is not.
  • The fixing-based reformulation of Tian and Pearl’s algorithm yields constraints defining the nested Markov model and supports r-factorization for variable elimination.

5. Summary.

The paper introduces the nested Markov model to represent equality constraints arising in DAG marginals, including Verma constraints, using ADMGs and recursive fixing. It characterizes the model through Markov properties and factorization, while distinguishing it from the full latent-variable model.

  • The nested Markov model represents equality constraints in DAG marginals, such as the Verma constraint, without explicitly modeling latent variables.
  • Recursive fixing links graphs and kernels, unifying marginalization, conditioning, and applications of the g-formula.
  • The model is characterized by Markov properties and a factorization, with valid fixing sequences yielding the same result.
  • Latent-variable models may impose additional inequality constraints that the nested Markov model does not capture.

A Graphical Model Definitions And Results

This section defines directed and mixed graph structures, separation criteria, latent projections, and core properties of ADMGs and CADMGs. It establishes how latent variables induce directed and bidirected edges while preserving acyclicity.

  • A directed mixed graph contains directed and bidirected edges, while an ADMG additionally contains no directed cycles.
  • An ADMG’s district consists of vertices connected through bidirected paths, and graph terminology includes parents, children, ancestors, descendants, and siblings.
  • For DAGs, the distributions Markov relative to the DAG coincide with the corresponding nested Markov model.
  • In mixed graphs, m-separation generalizes d-separation by classifying path vertices as colliders or non-colliders.
  • Latent projection adds a directed edge for directed paths through latent non-endpoints and a bidirected edge for suitable latent paths with arrowheads at both observed endpoints.
  • Latent projection preserves the ADMG or CADMG structure: projected graphs remain acyclic and retain the required fixed-vertex restrictions.

A.4 Additional Results On Graphs And Kernels

The appendix establishes correspondences among d-separation, m-separation, and kernel independence, and develops kernel constructions and their recursive properties.

  • Kernel independence satisfies the semi-graphoid axioms, including symmetry, decomposition, weak union, and contraction.
  • The appendix proves equivalence between recursive kernel conditions and the ordered factorization conditions for ancestral sets.

A.5 Results On Fixing and Fixability

The appendix characterizes fixability and shows how fixing changes graphs and kernels while preserving key structural properties.

  • Any vertex that was fixable before another vertex was fixed remains fixable afterward, except for the vertex already fixed.
  • If a Markov kernel is associated with a CADMG and the fixed vertex has no children, summing over that vertex leaves the remaining kernel unchanged.
  • The fixing operation is given by dividing the kernel by the conditional factor associated with the fixable vertex.
  • Fixing partitions a vertex’s district into districts of the induced subgraph after that vertex is removed.
  • Fixing a vertex removes its incoming directed edges and transforms it from random to fixed, while preserving other vertices’ parent sets.

A.7 Invariance to the order of fixing in an ADMG

The appendix proves that valid fixing operations are invariant to their order and develops graph-separation results supporting the construction.

  • Fixing two valid vertices in either order produces the same graph and kernel.
  • The equality follows because the products of the divisors for the two fixing operations are symmetric in the vertices.
  • Consequently, fixing sequences may be treated as order-independent when defining kernels obtained by fixing a set of vertices.
  • The appendix relates m-separation in CADMGs to separation in augmented ancestral graphs through path transformations.
  • The resulting graph arguments establish structural links among collider paths, Markov blankets, and m-separation.

C Results On Nested Markov Models

The nested Markov model has equivalent global, factorization, and ordered local characterizations built from valid fixing operations and kernel independences. The construction handles cases where different fixing sequences expose distinct constraints.

  • The global nested Markov property is equivalent to a district-based factorization.
  • The nested model can be defined equivalently through global and ordered local Markov properties and a factorization.
  • Valid fixing sequences determine kernel independences, but the ordered local property must account for sequence-specific constraints when defining the model.
  • Fixing operations generalize conditioning and marginalization, with some fixings corresponding to marginalization and yielding trivial independences.

C.2 Definition of Local Property

The ordered local nested Markov property organizes kernel independences through intrinsic sets, initial-segment districts, and transitions in an intrinsic power DAG. Its defining kernels and independences are invariant to valid fixing-sequence choices.

  • The intrinsic power DAG has intrinsic sets as vertices and directed transitions whenever one intrinsic set can reach another by fixing a vertex.
  • The power DAG contains separate connected components, one for each vertex, and its transitions encode the local constraints.
  • The ordered local property assigns independences to initial-segment districts and to transitions involving fixable vertices.
  • Kernels used in the definition are invariant to the choice of valid fixing sequence, so the local property is sequence-invariant.
  • Lemma C.5 shows that the defining independences can be checked after the corresponding fixing operations without changing their status.

C.3 Proof that ordered local nested property implies the global property

The proof establishes that ordered local nested Markov constraints imply district factorization for every reachable set. This yields the global nested Markov property and, with the converse, equivalence for any topological ordering.

  • Ordered local constraints imply that kernels for reachable sets district-factorize according to their reachable graphs.
  • The proof proceeds by induction over topological prefixes and reachable sets, showing that successive valid fixings preserve the required factorization.
  • When two vertices lie in the same district, the transition independence ensures that their fixing operations commute and the resulting kernel is well defined.
  • Theorem 38 states that global nested Markov and ordered local nested Markov properties are equivalent for any topological ordering.

C.4 Illustrative Examples

The examples show why ordered local constraints must be attached to transitions and fixing contexts rather than only to intrinsic sets. Different fixing sequences can expose distinct ordinary and nested independences.

  • C.4 Illustrative Examples: In the three-node bidirected example, fixing 1 produces X3 ⟂⟂ X2 in the resulting kernel, equivalently marginal independence.
  • C.4 Illustrative Examples: The power DAG represents these alternative constraints through distinct incoming transitions into the intrinsic set {6}.
  • C.4 Illustrative Examples: No single fixing sequence or larger intrinsic set can recover both independences in the vertex-6 example.
  • C.4 Illustrative Examples: For the example centered on vertex 6, two fixing sequences yield distinct independences: X6 ⟂⟂ X4, X5 and X6 ⟂⟂ X3, X5 | X2.
  • C.4 Illustrative Examples: The examples rule out a local property with at most one independence per intrinsic set.

C.5 Saturated Nested Models

This section establishes that, in complete ADMGs, fixing and marginalization operations preserve the relevant kernels under broad conditions, supporting saturated nested models. The proofs analyze when fixing sequences commute and when vertices are fixed by marginalization.

  • Preserved distributions: When two vertices are outside each other’s Markov blankets, fixing one preserves the other’s relevant conditional distribution.The proof tracks how dividing by a fixing factor leaves the conditional distribution unchanged when the vertices are appropriately separated in the fixing graph.
  • Fixing and marginalization: For a childless vertex in a complete ADMG, fixing it—and any previously fixed sibling—can be performed by marginalization.The argument uses the fact that every other random vertex lies in the vertex’s Markov blanket; the result extends inductively to subsequent siblings.
  • Reachable graphs: Starting from a complete ADMG, fixing operations can remove edges and produce a reachable CADMG that is no longer complete.This motivates separate arguments for saturated nested models rather than relying on completeness after every fixing step.
  • Commutativity: For a complete ADMG and a childless vertex, fixing that vertex followed by another fixable vertex yields the same kernel as the corresponding sequential operation.If the vertices are siblings, both operations are marginalizations and commute; otherwise, Markov-blanket structure makes the second operation unaffected.

C.5.1 Maximal Arid Graphs

This section characterizes saturation of nested Markov models through pairwise relationships preserved across valid fixing sequences. The model is saturated exactly when every valid fixing sequence keeps each vertex pair connected through Markov blankets.

  • Maximal arid graphs: The saturation condition is equivalent to every pair of vertices being densely connected, and therefore to nested Markov equivalence with a complete maximal arid projection.The maximal arid projection is simple and replaces dense connectivity with an equivalent graph in which singleton intrinsic closures have the required form.
  • Saturation criterion: The nested model Pn(G) is saturated if and only if every valid fixing sequence places each ordered vertex pair in at least one another’s Markov blanket.The theorem states the condition for every sequence and every pair of positions, with the corresponding blanket relation determining saturation.
  • Non-saturation: If the blanket condition fails, one can construct a distribution with dependent Xi and Xj that violates a nested local Markov independence after fixing.This establishes that the model is not saturated whenever a valid sequence contains a pair that is absent from the relevant Markov blanket.
  • Local Markov property: In complete graphs, kernels for intrinsic sets do not depend on variables outside the intrinsic set and its parents, yielding the local Markov property.Childless vertices can be fixed by marginalization, while the remaining complete-graph cases reduce to parent or sibling relationships.
  • Complete graphs: For complete ADMGs, the nested Markov model is saturated.In a complete graph, directed or bidirected adjacency ensures the required Markov-blanket relation throughout valid fixing sequences.

D Connections To Causal Inference

This section connects nested Markov models and fixing operations to causal inference with latent variables. It shows that DAG marginals satisfy the nested model and that reachable-set kernels characterize identifiable interventions.

  • DAG equivalence: For a DAG without latent variables, the ordinary DAG Markov model and the nested Markov model coincide.This is stated as Pd(G) = Pn(G) for DAGs.
  • DAG marginals: Every marginal distribution of a DAG model belongs to the nested Markov model of its latent projection.The result is summarized as p(xV∪L) ∈ Pd(G(V∪L)) implying p(xV) ∈ Pn(G(V)).
  • Identifiable effects: For any reachable set S in a hidden-variable causal DAG, the intervention p(xS | do(xV\S)) is identifiable from the observed distribution by the fixing kernel.The kernel depends only on xS and the observed parents of S outside S.
  • Identification criterion: A causal effect is identifiable when every relevant district is intrinsic; otherwise a non-intrinsic district yields non-identification.Theorem 48 gives the criterion using the districts of the ancestor graph after intervention variables are removed.
  • Latent projections: Causal DAGs with the same latent projection have identical identification status and, when identified, identical intervention distributions.The corollary applies this equivalence to any disjoint treatment and outcome sets.

E Connections with Tian’s Constraint Algorithm

The paper reformulates Tian’s constraint algorithm using ADMGs, CADMGs, kernels, and fixing operations, showing that the reformulation preserves the algorithm’s structure and characterizes the nested Markov model.

  • Model characterization: The reformulation gives a constraint-generating framework that does not rely on a hidden-variable DAG, unlike Tian’s original formulation.The paper explicitly notes that the reformulated algorithm applies to ADMGs without presupposing an underlying hidden-variable DAG.
  • Algorithmic reformulation: Lemma E.1 establishes that recursive inputs in Tian’s algorithm correspond to intrinsic sets, fixed CADMGs, and matching latent projections in the reformulation.The correspondence includes the graph obtained by fixing vertices outside an intrinsic set and agreement of effective parents with graph parents.
  • Algorithmic reformulation: The reformulation preserves Tian’s recursive structure: every relevant kernel can be produced by Algorithms 1 and 2 through a fixing sequence consistent with the intrinsic power DAG.The stated lemmas connect kernels generated by valid fixing sequences to recursive calls of the algorithms.
  • Model characterization: Theorem 51 shows that the constraints generated by Algorithm 1 define exactly the nested Markov model, while Theorem 52 links that model to r-factorization.The equality Pt(G, V, ≺) = Pn(G(V)) identifies the algorithmic constraint set with the nested model.

E.1 Comparison of Tian’s Algorithm and Local Nested Markov Property

The example compares constraints generated by Tian’s recursive algorithm with those obtained from the local nested Markov property, emphasizing redundancy and the role of fixing-order invariance.

  • Power-DAG example: The example gives another constraint, 6 ⟂⊥ 2, 3 | 1, under fixing sequence ⟨5,4⟩ for the ancestral set {1, 2, 3, 6}.This illustrates how constraints arise from different ancestral subgraphs and fixing sequences.
  • Comparison of constraint sets: Theorem 31 explains why constraints from different valid fixing orders can be compared: the order of fixing does not affect the resulting graph and kernel under the model.The example notes that redundancy is not immediately apparent without this invariance result.
  • Comparison of constraint sets: Tian’s algorithm can produce syntactically redundant constraints in different kernels, whereas the local nested procedure gives fewer equivalent independences.The example identifies repeated constraints involving X5 and X6 under kernels that are not a priori the same.
  • Power-DAG example: The power-DAG subgraph for vertex 6 retains only nine edges that could logically yield constraints, corresponding to the constraints listed in Table 2.The figure caption defines the displayed subgraph’s scope, and the accompanying text states the edge count and correspondence.
Loading 1701.06686v6…