Dependency in DAG models with Hidden Variables

Robin Evans

TL;DR

This paper investigates when two variables in a directed acyclic graph (DAG) model with hidden variables can be made identical while remaining independent of all other observed variables. The key finding is that this is possible if and only if these two variables are "densely connected" in the graph, meaning they cannot be separated by interventions or conditioning. This insight simplifies model search by suggesting we only need to consider graphs where densely connected variables are directly linked.

What Problem Does This Paper Address?

Directed Acyclic Graphs (DAGs) are powerful tools for representing causal relationships and dependencies, especially when some variables are unobserved (hidden or latent). A significant challenge in working with these models is understanding the space of possible probability distributions they can represent, particularly when hidden variables are involved. Specifically, the authors tackle the question: under what conditions can two observed variables, say $X_v$ and $X_w$, be made perfectly equal (i.e., $X_v = X_w$ with probability 1) while simultaneously ensuring they are jointly independent of all other observed variables? This is a non-trivial problem because hidden variables can induce dependencies that are not apparent from the observed variables alone. The paper aims to provide a precise characterization of when this perfect correlation and independence can be achieved, which has implications for model identifiability and causal inference.

Methods

The paper builds upon the concept of nested Markov properties for acyclic directed mixed graphs (ADMGs), which are DAGs augmented with bidirected edges representing latent variables. The core of their method involves:

  • Defining "Densely Connected" Vertices: They introduce a formal definition of "densely connected" vertices. Two vertices $v$ and $w$ are densely connected if they are adjacent in the graph, or if their "closures" (sets of vertices reachable via bidirected paths) are bidirected-connected. This concept captures a strong form of structural linkage.
  • Maximal Arid Projection (MArG): They utilize the MArG projection of an ADMG, denoted $G^\dagger$. This projection simplifies the graph by removing redundant edges while preserving the essential nested Markov properties. The key insight is that the nested Markov models associated with an ADMG $G$ and its MArG projection $G^\dagger$ are identical.
  • Constructing Distributions: For densely connected pairs $(v, w)$, they propose a constructive method to generate a distribution where $X_v = X_w$ and they are independent of other observed variables. This construction involves setting specific latent variables to be independent Bernoulli random variables and defining observed variables as XOR sums of their parents. The specific construction depends on whether the dense connection arises from a directed edge, a bidirected edge, or a combination.
  • Leveraging Existing Results: They build upon theorems and propositions from prior work (e.g., Shpitser et al., 2018) regarding nested Markov properties and graph projections.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of DAG models and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • "Densely Connected" is Key: The central finding is that the ability to make two variables perfectly equal and independent of others hinges entirely on them being "densely connected" in the graph structure. This provides a clear structural criterion.
  • MArG Simplification: The maximal arid projection ($G^\dagger$) is a powerful tool. It shows that complex ADMGs can be reduced to simpler, "arid" graphs without losing information about the realizable distributions. This simplifies analysis.
  • Structural Implication for Model Search: The result suggests that when searching for causal models, we can prune graphs that do not have direct edges between densely connected vertices. This significantly reduces the search space.
  • Beyond Direct Edges: The paper demonstrates that perfect correlation and independence are possible even between variables that are not directly connected by an edge, provided they are "densely connected" through latent variable structures. This highlights the subtle dependencies induced by hidden variables.

Key Results

The main theoretical result is:

Theorem 6.4: A distribution can be obtained such that two variables $X_v$ and $X_w$ are equal and independent of all other observed variables if and only if there is an edge between $v$ and $w$ in the maximal arid projection ($G^\dagger$) of the graph.

This theorem is supported by two propositions:

  • Proposition 6.2: If $w \in \text{pag}((v))$ (i.e., $v \to w$), then $X_v$ can be made equal to $X_w$ and independent of other observed variables.
  • Proposition 6.3: If the pair $(v, w)$ is bidirected-connected in the ADMG, then $X_v$ can be made equal to $X_w$ and independent of other observed variables.

The paper also provides algorithms (e.g., Algorithm 1) for efficiently finding minimal sets of vertices required for these constructions, with proven linear time complexity.

Limitations and Future Work

  • Extension to Multiple Variables: The paper notes that extending the result to simultaneously setting more than two variables to be equal and independent is not straightforward. Figure 7(a) illustrates a case where pairwise equality is possible, but three-way equality is not, even though the arid projection suggests it might be. This is identified as a direction for future research.
  • Computational Complexity of Minimality: While Algorithm 1 provides an efficient way to find minimal sets, the paper acknowledges that finding such sets using Proposition 5.3 can be computationally difficult in some cases (as shown in Example 5.4 and Figure 11).
  • Arbitrary Distributions: The paper primarily focuses on discrete variables (especially binary) and mentions that extensions to arbitrary discrete and continuous distributions are possible but require careful construction. The exact mechanisms for achieving arbitrary joint distributions with continuous variables are briefly outlined.

Summary updated

Abstract

Directed acyclic graph models with hidden variables have been much studied, particularly in view of their computational efficiency and connection with causal methods. In this paper we provide the circumstances under which it is possible for two variables to be identically equal, while all other observed variables stay jointly independent of them and mutually of each other. We find that this is possible if and only if the two variables are `densely connected'; in other words, if applications of identifiable causal interventions on the graph cannot (non-trivially) separate them. As a consequence of this, we can also allow such pairs of random variables have any bivariate joint distribution that we choose. This has implications for model search, since it suggests that we can reduce to only consider graphs in which densely connected vertices are always joined by an edge.
BibTeX
@inproceedings{evans2021dependency,
  author = {Robin Evans},
  title = {{Dependency in DAG models with Hidden Variables}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
}
Figure