Causal Discovery by Interventions via Integer Programming

Abdelmonem Elrefaey, Rong Pan · 2024

Read Causal Discovery by Interventions via Integer Programming by Abdelmonem Elrefaey, Rong Pan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01674.txt.

Introduction

Abdelmonem Elrefaey and Rong Pan find causal structures by interventions via integer programming in two thousand twenty-four. Watching data alone can hide cause behind confounding traits. Planned interventions cut through that fog by design. Their method picks the smallest set of interventions that names the structure.

Integer programming states the pick as an exact optimization. Solutions are modular and bend to lab limits or costs. Tests across settings show the method holds up well. It stays robust as constraints on the trials shift. The work serves fields that need causal maps from data.

Catalog record

CREATORAbdelmonem Elrefaey, Rong Pan
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01674

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Causal Discovery by Interventions via Integer Programming Abdelmonem Elrefaey, Rong Pan Abstract Causal discovery is essential across various scientific fields to uncover causal structures within data. Traditional methods relying on observational data have limitations due to confounding variables. This paper presents an optimization-based approach using integer programming (IP) to design minimal intervention sets that ensure causal structure identifiability. Our method provides exact and modular solutions that can be adjusted to different experimental settings and constraints. We demonstrate its effectiveness through comparative analysis across different settings, demonstrating its applicability and robustness. August 24, 2026 1 Introduction Causal discovery is a crucial endeavor in many scientific fields. Specifically, it focuses on revealing the causal structures within the data. Generally, causal discovery can be carried out through one of two data collection approaches – observational data-based discovery and interventional or experimental data-based discovery. Most of past research employs observational methods, such as those using conditional independence tests, to provide valuable insights into causal structure. However, these methods have significant limitations, as they often face challenges from confounding variables and their inability to determine causality conclusively [ 1 , 2 ] . Observation-based causal discovery can most reveal a Directed Acyclic Graph (DAG) up to its Markov Equivalence Class (MEC) level, which means that there could be multiple different causal structures equivalent to fitting to the conditional independence revealed by the observational data alone [ 3 ] . The experimental approach, in contrast, provides a robust framework for discovering causal relationships by systematically manipulating variables and observing the effects [ 4 ] . The randomized controlled trial (RCT) is often considered the gold standard in this context, providing clear evidence of causality by isolating the effects of specific interventions [ 5 ] . However, traditional experimental designs presume a bipartite separation of variables into treatment and outcome categories (with possible covariates), which requires prior knowledge of which variables are potential causes (treatments) and which are potential effects (outcomes). They cannot adequately address the causal structure scenarios that do not fit this framework. For example, for a complex causal network, the conventional Design of Experiments (DOE) principles often do not provide useful guidance to the design of network interventions [ 6 ] . The primary goal of traditional DOE is to determine whether the treatment variable influences the outcome variable and, if so, to what extent. However, it does not offer advice on how to select treatment variables. Although bipartite separation is assumed in many studies given the condition of time-ordered information or limited intervention possibilities, there are numerous other situations where such restrictions are unwarranted (e.g., when multiple causal pathways exist between treatment and outcome variables). A more comprehensive framework for discovering causal structures – causal Bayes nets – has been developed in the fields of computer science and philosophy [ 7 , 2 ] . Unlike the bipartite structure assumed in DOE, causal Bayes nets accommodate general graphical networks (though this discussion is limited to acyclic networks). They represent causal relationships among variables by a DAG and a probability distribution on the variables in the DAG [ 8 ] . This framework calls for new principles for intervention experimental designs and involves setting new design parameters such as selecting intervention and outcome variables, determining the type of intervention (structural or parametric), and the level of perturbation for each intervention variable. Moreover, the diversity of interventions should be planned to cover different aspects or levels of the variables of interest, including combinatorial interventions to explore joint effects and interactions while not exceeding cost limitations. Ensuring an adequate sample size is also a crucial design parameter for achieving sufficient statistical power, improving generalizability, and counting variations in outcome measures. The main focus in recent years has been on the number of intervention experiments required to reveal a causal structure under certain assumptions, as well as on deciding on which variables are to be intervened on in each experiment. The methodology by which many other design parameters remain open problems. 2 Related Work In [ 9 ] the authors prove the bounds for the minimal number of experiments required for causal discovery for one-intervened-variable or multiple-intervened-variable experiments. Frederick Eberhardt’s early work [ 10 ] has laid a solid groundwork for the field of interventional causal discovery. Two main types of interventions are discussed in his thesis: structural interventions and parametric interventions. Structural interventions break all incoming causal influences to an intervened variable, making it independent of its causes, thus it is effective in determining direct causal links from the intervened variable to other unintervened variables. Parametric interventions, on the other hand, modify the conditional probability distribution of the intervened variable without breaking incoming influences, preserving the original causal structure. This is necessary when structural intervention is impractical or unethical. His thesis explores the efficacy of fixed and adaptive [ 11 , 12 , 13 , 14 ] intervention strategies and discusses the efficiency of multiple simultaneous variable interventions. Following Eberhardt’s seminal work, [ 15 ] specifies the minimal number of experiments needed to uniquely determine a causal graph from its observational MEC. The authors show that the number of required experiments is related to the largest clique in MEC. The OPTINTER algorithm proposed by the authors focuses on breaking down cliques quickly by selecting vertices in the largest cliques, but this algorithm is an NP-complete MAX-CUT problem. [ 16 ] formalize the causal identifiability problem as variable pair conditions as follows: • Unordered Pair Condition (UPC): Ensures an experiment where one of any two variables is intervened upon and the other is passively observed. • Ordered Pair Condition (OPC): Ensures an experiment where the first variable in any ordered pair is intervened upon and the second is passively observed. • Covariance Condition (CC): Ensures an experiment where a pair of variables are passively observed. The paper connects these conditions to combinatorial problems, using separating systems and cut-coverings in graph theory following results in [ 17 , 18 ] . This approach allows the construction of optimal experiment sets that satisfy the necessary conditions for causal discovery in the worst case (when the true DAG is fully connected). Later work, such as that by [ 19 ] developed algorithms based on the optimal coloring of chordal graphs, requiring up to \log_{2}(\chi) interventions to learn any causal graph, where \chi is the chromatic number of the chordal skeleton of the DAG. [ 20 ] focus on the problem of learning causal networks using interventions under Pearl’s Structural Equation Model with independent errors (SEM-IE). They aim to minimize the number of experiments needed to discover the causal directions of all edges in a causal graph. A key contribution is proving that any deterministic adaptive algorithm needs to be a separating system to learn complete graphs in the worst case. They also present a novel separating system construction that is close to optimal and simpler than previous work in combinatorics. [ 21 ] address the same problem with a cost consideration. They formulate the cost-optimal causal graph learning problem, aiming to design a set of interventions with a minimum total cost that can uniquely identify any causal graph given its skeleton. Their approach leverages the connection between graph-separating systems and

Read the complete text