Integer Programming for Causal Structure Learning in the Presence of Latent Variables

Rui Chen, Sanjeeb Dash, Tian Gao

Introduction

In causal inference, researchers frequently rely on Directed Acyclic Graphs (DAGs) to represent how variables influence one another. However, standard DAG learning relies on a significant assumption: causal sufficiency, which posits that there are no unobserved "latent" variables influencing the system.

In reality, latent variables are ubiquitous—from unmeasured genetic factors in medical studies to unrecorded habits in health surveys. When these hidden factors exist, a simple DAG can no longer accurately represent the dependencies. Instead, researchers must use Ancestral Acyclic Directed Mixed Graphs (ADMGs). These graphs use directed edges to denote direct causality and bidirected edges to represent latent confounding (i.e., two variables influenced by the same hidden cause).

While algorithms for learning ADMGs exist, they are typically "constraint-based" (prone to cascading errors if a single statistical test fails) or "greedy/heuristic" (liable to get stuck in local optima). This paper introduces AGIP (Ancestral Graph Integer Programming), the first exact score-based method capable of finding the globally optimal causal graph in the presence of hidden variables.

The AGIP Methodology

AGIP frames causal discovery as a mathematical optimization problem that can be solved by powerful off-the-shelf integer programming (IP) solvers like Gurobi.

The core technical components of AGIP include:

  • Score Decomposition: The authors utilize the fact that the Bayesian Information Criterion (BIC) score for Gaussian ADMGs can be broken down into "c-components" (subgraphs defined by sets of nodes connected by bidirected edges). This allows the IP to select the optimal combination of these components.
  • Novel Constraints: To ensure the resulting graph is a valid ADMG, the authors introduce two types of linear inequalities:
  • Strengthened Cluster Inequalities: These prevent standard directed cycles (e.g., $A \to B \to C \to A$).
  • Bicluster Inequalities: The primary theoretical contribution of the paper, these constraints prevent "almost directed cycles," where a path of directed edges is closed by a bidirected edge (e.g., $A \to B \leftrightarrow A$).
Depiction of the bicluster inequality, which prevents "almost directed cycles."
  • Pruning: Because the number of possible subgraphs is astronomical, AGIP employs strict pruning rules to discard sub-optimal candidate components before the optimization begins, drastically reducing the search space.

Experimental Evaluation

The authors evaluated AGIP across several scenarios, including a 4-node "ground truth" example (simulated from a 5-node DAG with one intentionally hidden node), randomly generated ADMGs with up to 20 total variables, and specifically chosen "non-DAG" ADMGs that cannot be simplified into standard DAGs.

Key Insights and Results

  • Exactness Outperforms Heuristics: The paper demonstrates that greedy searches (like M3HC) frequently miss the best model. In random graph tests, AGIP improved the BIC score over the greedy M3HC algorithm in 53 out of 60 instances.
  • Handling Non-DAG Structures: Many real-world causal structures are "non-DAG representable." Standard DAG-learning tools struggle in these environments, whereas AGIP's expanded search space allows it to accurately recover the true underlying structure.
  • Superior Accuracy: AGIP consistently achieved the best Structural Hamming Distance (SHD), precision, and recall compared to both DAG-based IP models and popular constraint-based methods like FCI.
  • Consistency: As the sample size ($N$) increased, AGIP's performance improved significantly, demonstrating its reliability as a consistent estimator for large datasets.
Comparison of solutions: AGIP correctly identifies the structure where other methods fail.

Limitations and Future Work

While AGIP represents a major step forward for exact causal discovery, the authors note a few limitations:

  • Scalability: The number of potential "c-components" grows exponentially with the number of variables. The current implementation limits the size of these components to maintain computational speed, making it best suited for medium-sized problems (around 18 observed variables).
  • Distribution Assumptions: The scoring function used in this study assumes the data follows a multivariate Gaussian distribution. Extending this framework to discrete data or non-linear relationships is a logical next step.
  • Selection Bias: The current model focuses exclusively on latent variables but does not yet account for selection bias, which would require the introduction of undirected edges in the graph.

Summary updated

Abstract

The problem of finding an ancestral acyclic directed mixed graph (ADMG) that represents the causal relationships between a set of variables is an important area of research on causal inference. Mos...
BibTeX
@inproceedings{chen2021integer,
  author = {Rui Chen and Sanjeeb Dash and Tian Gao},
  title = {{Integer Programming for Causal Structure Learning in the Presence of Latent Variables}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=YtTRM3ymnDI},
}
Figure