Deriving Complete Constraints in Hidden Variable Models

1. Problem Statement

Hidden variable graphical models (specifically Non-Parametric Structural Equation Models or NPSEMs) often imply constraints on the observable joint distribution that go beyond simple conditional independence relations.

• The Challenge: While conditional independencies (d-separation) are well-understood, more complex constraints—such as inequalities (e.g., instrumental inequalities) and nested equality constraints (e.g., Verma constraints)—are often difficult to derive.
• Limitations of Existing Methods:
  • Nested Markov Models: Characterize only equality constraints and miss inequality constraints.
  • Fourier-Motzkin Elimination/Linear Programming: Can derive complete constraints but become computationally infeasible for moderately sized state spaces.
  • Previous Work: Bonet (2001) derived complete constraints for the binary Instrumental Variable (IV) setting, but generalizing this to arbitrary graphs with categorical variables has been difficult.
• Goal: To develop a systematic, computationally feasible method for deriving the complete set of observable constraints (both equality and inequality) for a broad class of hidden variable models.

2. Methodology

The authors propose an algorithm that extends Bonet's (2001) approach using tools from computational geometry. The method relies on the concept of response function variables and districts.

Key Definitions & Setup

• Canonical DAGs: The method assumes the DAG satisfies specific conditions: unobserved variables are exogenous (no parents) and have at least two observed children.
• Districts (c-components): The graph is partitioned into "districts" (sets of observed variables connected by unobserved confounders).
• c-degree: The maximum number of unobserved variables that are parents of any single district. The method guarantees completeness only when the c-degree is 1 (i.e., each district has at most one common latent cause).
• Response Function Transformation: The authors transform the original DAG $G(W, U)$ into a mixed graph $G(W, R)$ where unobserved variables are replaced by discrete response function variables ($R_{W_i}$). These variables determine how an observed variable $W_i$ responds to its parents.

The Algorithm

The derivation proceeds in three main steps:

1. Identify Standard Independencies: Use d-separation to list all standard conditional independence constraints.
2. Derive Functional Constraints (Vertex Representation):
   • For each district with c-degree 1, express observable probabilities (specifically interventional probabilities $P^*(W_1|W_2)$) as linear combinations of the probabilities of the response function variables.
   • This forms a system of linear equations: $\mathbf{p} = \mathbf{B}\mathbf{r}$, where $\mathbf{p}$ is the vector of observable probabilities and $\mathbf{r}$ is the vector of unobservable response function probabilities.
   • This defines a convex polyhedron in terms of the vertices (response function probabilities).
3. Vertex-to-Halfspace (V-to-H) Conversion:
   • Convert the vertex representation ($\mathbf{p} = \mathbf{B}\mathbf{r}$) into a half-space representation ($\mathbf{H}_i \mathbf{p} \leq \mathbf{b}_i$ and $\mathbf{H}_e \mathbf{p} = \mathbf{b}_e$).
   • This step uses algorithms like the double description method (implemented in software like cddlib) to eliminate the unobservable variables $\mathbf{r}$.
   • The resulting inequalities and equalities constitute the complete set of observable constraints.

Identifying Nontrivial Constraints

The algorithm may produce constraints that are trivial (e.g., implied by basic probability axioms). The authors propose a procedure to filter these:

• Enumerate the extreme points of the unconstrained probability space (the cross-product of probability simplices).
• Test if the derived constraints are violated by any of these extreme points.
• If a constraint is never violated by the unconstrained space, it is trivial. If it is violated, it is a nontrivial constraint imposed by the structural model.

3. Key Contributions

1. Generalization of Bonet's Method: The paper extends the derivation of complete constraints from the specific binary IV setting to a broad class of models with categorical observed variables and c-degree 1.
2. Proof of Completeness: The authors prove that for models with c-degree 1, the derived set of constraints is complete (necessary and sufficient). No other observable constraints exist beyond those derived by this linear programming approach.
3. Unified Framework for Equality and Inequality: Unlike nested Markov models (which only yield equalities), this method naturally derives both Verma-type equality constraints and instrumental-type inequality constraints within a single framework.
4. Handling Higher c-degree (Incomplete but Valid): For models with c-degree > 1, the authors propose a heuristic: merge unobserved variables within a district to reduce the c-degree to 1. While this does not guarantee completeness, it yields a valid (necessary) subset of constraints.
5. Observational Equivalence: The paper provides propositions (adapted from Evans, Ansanelli, and HLP) to transform DAGs with higher c-degree into observationally equivalent DAGs with c-degree 1, allowing the complete method to be applied to a wider range of structures.

4. Results and Illustrations

The authors illustrate the method on several novel settings:

• Sequential Instrumental Variables: Derives sets of instrumental inequalities for sequential IV structures.
• Nested Equivalent Models: Demonstrates two DAGs that are nested Markov equivalent (same equality constraints) but possess distinct inequality constraints, proving that inequalities provide finer discrimination between models.
• Tripartite Bell Graphs: A complex quantum physics scenario. The algorithm derived 53,894 constraints (including 53,856 inequalities) in under 0.5 CPU hours, matching known results from literature (e.g., Śliwa, 2003) and identifying new nontrivial constraints.
• Front-Door Criterion: Shows that the algorithm correctly identifies that the front-door model has no nontrivial inequality constraints, despite generating complex-looking intermediate expressions.

5. Significance and Limitations

Significance:

• Causal Discovery: Provides a finer stratification of causal models. Models that are indistinguishable by conditional independence or equality constraints alone can be distinguished using these derived inequalities.
• Model Falsification: Enables researchers to rigorously test structural assumptions against data. If observed data violates these constraints, the underlying causal model is falsified.
• Statistical Efficiency: These constraints can be used to constrain estimation procedures, potentially improving the efficiency of causal effect estimates.
• Software Availability: The authors provide open-source software (meraconstraints on GitHub) to implement these derivations.

Limitations:

• c-degree Constraint: The guarantee of completeness is strictly limited to DAGs with c-degree 1. For higher c-degree, the method yields necessary but potentially incomplete constraints unless the graph can be transformed into an equivalent c-degree 1 graph.
• Computational Complexity: The number of facets in the resulting polytope grows super-exponentially with the number of variables. While feasible for many settings (as shown in the Bell example), it may become intractable for very large, densely connected graphs.
• Discrete Variables: The method assumes observed variables are categorical and finite. It does not directly apply to continuous variables without discretization.

In conclusion, this paper establishes a robust, computationally grounded framework for uncovering the full geometry of observable distributions implied by hidden variable models, bridging the gap between causal theory and testable statistical constraints.