Mixed-Integer Programming for Causal Discovery with Unknown Hard-Intervention Targets
Abstract
When intervention targets are uncertain, learning causal relationships and identifying directly perturbed variables become a joint task. We develop an exact mixed-integer program based on optimized parent-set scores (PS-MIP) for joint graph and intervention-target estimation in linear Gaussian structural equation models under stochastic hard interventions. The method can incorporate candidate-edge restrictions and partial target knowledge when available. For each random variable, PS-MIP evaluates candidate sets of direct causes, or parent sets, by optimizing the likelihood parameters and compatible target patterns, retaining both the score and a minimizing target pattern. A global mixed-integer program then selects parent sets subject to acyclicity. Under stated conditions, this reduction preserves the joint objective and reconstructs the graph, targets, and likelihood parameters. Because the local scores are precomputed, PS-MIP replaces a direct large bilinear mixed-integer program with a linear selection problem; empirically it certifies global optimality on far more instances than the direct formulation (126 of 180 versus 34) and is often orders of magnitude faster. On synthetic data, PS-MIP achieves favorable false-discovery--true-discovery trade-offs relative to several benchmark algorithms for causal discovery with unknown intervention targets, along with strong intervention-target recovery in denser settings. An exploratory study on real data from a controlled physical system further demonstrates recovery beyond simulation.
Related
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
- Accelerated Benders decomposition for bi-objective mixed integer programming
- Physics-Informed Mixed Integer Programming Methods for Optimal Patch Antennas
BibTeX
@misc{xu2026mixedinteger,
title = {{Mixed-Integer Programming for Causal Discovery with Unknown Hard-Intervention Targets}},
author = {Tong Xu and Armeen Taeb and Simge Küçükyavuz and Ali Shojaie},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01267},
eprint = {2611.01267},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01267},
}
RIS
TY - UNPB
TI - Mixed-Integer Programming for Causal Discovery with Unknown Hard-Intervention Targets
AU - Tong Xu
AU - Armeen Taeb
AU - Simge Küçükyavuz
AU - Ali Shojaie
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01267
UR - https://arxiv.org/abs/2611.01267
AB - When intervention targets are uncertain, learning causal relationships and identifying directly perturbed variables become a joint task. We develop an exact mixed-integer program based on optimized parent-set scores (PS-MIP) for joint graph and intervention-target estimation in linear Gaussian structural equation models under stochastic hard interventions. The method can incorporate candidate-edge restrictions and partial target knowledge when available. For each random variable, PS-MIP evaluates candidate sets of direct causes, or parent sets, by optimizing the likelihood parameters and compatible target patterns, retaining both the score and a minimizing target pattern. A global mixed-integer program then selects parent sets subject to acyclicity. Under stated conditions, this reduction preserves the joint objective and reconstructs the graph, targets, and likelihood parameters. Because the local scores are precomputed, PS-MIP replaces a direct large bilinear mixed-integer program with a linear selection problem; empirically it certifies global optimality on far more instances than the direct formulation (126 of 180 versus 34) and is often orders of magnitude faster. On synthetic data, PS-MIP achieves favorable false-discovery--true-discovery trade-offs relative to several benchmark algorithms for causal discovery with unknown intervention targets, along with strong intervention-target recovery in denser settings. An exploratory study on real data from a controlled physical system further demonstrates recovery beyond simulation.
ER -