Source-linked AI summary
Constraint-based Causal Discovery from Multiple Interventions over Overlapping Variable Sets
Sofia Triantafillou, Ioannis Tsamardinos
TL;DR
Causal discovery must integrate heterogeneous data sets that measure overlapping variables under different interventions, rather than analyze each distribution separately. COmbINE converts cross-data-set statistical constraints into a SAT formulation with confidence-based conflict resolution, and the paper reports soundness, completeness, improved efficiency over a similar method, and application to real experimental data. Its scope includes acyclic structures and depends on a shared underlying causal mechanism across data sets.
Problem
Causal discovery needs to combine heterogeneous data sets with overlapping variables and different interventions, but standard methods often analyze such data sets separately.
Method
COmbINE converts dependency and independency information into path constraints on semi-Markov causal models, encodes them as SAT, and ranks conflicting constraints by p-value-based confidence.
Results
COmbINE is sound and complete in the sample limit and was reported as more efficient than a similar algorithm, with empirical evaluation showing high precision and recall and scaling to sparse networks of up to 100 variables.
Takeaways & Limitations
The SAT representation supports summaries of identifiable and non-identifiable causal characteristics and can be extended to enumerate plausible models or query structural properties.
Takeaways & Limitations
COmbINE addresses acyclic structures and its computational cost is affected by the maximum length of possibly inducing paths considered.
Abstract
from arXiv · showhide
Scientific practice typically involves repeatedly studying a system, each time trying to unravel a different perspective. In each study, the scientist may take measurements under different experimental conditions (interventions, manipulations, perturbations) and measure different sets of quantities (variables). The result is a collection of heterogeneous data sets coming from different data distributions. In this work, we present algorithm COmbINE, which accepts a collection of data sets over overlapping variable sets under different experimental conditions; COmbINE then outputs a summary of all causal models indicating the invariant and variant structural characteristics of all models that simultaneously fit all of the input data sets. COmbINE converts estimated dependencies and independencies in the data into path constraints on the data-generating causal model and encodes them as a SAT instance. The algorithm is sound and complete in the sample limit. To account for conflicting constraints arising from statistical errors, we introduce a general method for sorting constraints in order of confidence, computed as a function of their corresponding p-values. In our empirical evaluation, COmbINE outperforms in terms of efficiency the only pre-existing similar algorithm; the latter additionally admits feedback cycles, but does not admit conflicting constraints which hinders the applicability on real data. As a proof-of-concept, COmbINE is employed to co-analyze 4 real, mass-cytometry data sets measuring phosphorylated protein concentrations of overlapping protein sets under 3 different interventions.
1. Introduction
COmbINE addresses the difficulty of jointly analyzing heterogeneous data sets by learning causal structure from overlapping variables and different interventions. It converts statistical constraints into SAT, resolves conflicts by confidence, and was reported as more efficient than a similar method.
- Causal studies may measure different variables under different interventions, producing heterogeneous data sets from one system.
- Standard machine-learning and statistical methods often analyze these data sets separately rather than making joint inferences across distributions.
- COmbINE learns causal structure from overlapping variable sets under different hard manipulations, assuming one underlying causal mechanism generates all data sets.
- The algorithm converts dependencies and independencies into path constraints, encodes them as a SAT instance, and summarizes invariant and variant characteristics across fitting causal models.
- COmbINE ranks constraints by confidence using p-values and discards lower-ranked constraints that conflict with higher-ranked ones.
- COmbINE was reported as more efficient than a similar SAT-based algorithm, while the evaluation also examined sample size, numbers of data sets, and computational efficiency.
2. Related Work
Prior work addressed overlapping variables or multiple experiments, but few methods jointly handled overlapping variables and different experimental conditions. COmbINE was presented as the first acyclic approach in this setting without specific parametric assumptions or an independence oracle.
- Causal-discovery methods have increasingly combined multiple data sources as intervention and data-collection technologies have expanded.
- Some methods combine observational data with overlapping variables, including sound and complete approaches for learning common MAG characteristics.
- Other methods combine experimental and observational data, model interventional distributions, or use interventions to learn or design causal Bayesian networks.
- Only a limited number of methods co-analyze overlapping variable sets under different experimental conditions, with some relying on linearity or other restrictions.
- COmbINE was presented as the first method for overlapping variables and multiple interventions in acyclic structures without specific parametric assumptions or an independence oracle.
3. Mixed Causal Models
Mixed causal models represent causal relations and conditional independencies when latent confounding may be present. MAGs provide a maximal representation of ancestral mixed graphs, while SMCMs can encode direct causation and hidden confounding but may contain non-adjacency that does not imply conditional independence.
- SMCMs use directed edges for direct causation and bi-directed edges for unobserved confounding.
- Mixed graphs extend d-separation through m-separation, which characterizes whether paths connect variables given a conditioning set.
- Unlike DAGs, SMCM non-adjacency does not always imply a conditional independence among observed variables.A pair of non-adjacent variables may remain dependent given every subset of observed variables.
- MAGs are ancestral mixed graphs in which every non-adjacent pair has some conditioning set yielding m-separation.Under causal Markov and faithfulness, MAG m-separation corresponds to conditional independence in the associated distribution.
- MAGs are closed under marginalization, producing a unique MAG for each marginal distribution when the original MAG is faithful.
- Primitive inducing paths explain why marginal ancestral graphs can require additional adjacencies, and Algorithm 1 adds such edges when transforming an SMCM into a MAG.The reverse transformation is generally impossible because an edge may represent direct causation, confounding, or a non-trivial inducing path.
4. Learning causal structure from multiple data sets measuring overlapping variables under different manipulations
COmbINE formulates causal discovery from heterogeneous data sets with overlapping variables and different manipulations as a constrained search for consistent SMCMs. It translates PAG-derived structural features into SAT constraints and summarizes invariant and variant causal characteristics across satisfying models.
- Problem formulation: COmbINE assumes one underlying causal mechanism over the union of variables, with each data set representing a manipulated marginal containing potentially latent variables.The consistency requirement is that one SMCM explains every data set after accounting for manipulations and measured-variable selection.
- Constraint construction: COmbINE converts PAG adjacencies, colliders, and discriminating paths into constraints on edges, tails, arrows, and paths in the underlying SMCM.Adjacency constraints require inducing paths, while collider and non-collider constraints impose ancestor or non-ancestor relations.
- Algorithm COmbINE: The algorithm initializes a candidate SMCM from PAGs produced for each data set, combining observed adjacencies while orienting only arrowheads shared across PAGs.It also adds edges between variables that were not measured and manipulated together, according to the initialization procedure.
- Soundness and conflict handling: In the sample limit and under the stated assumptions, the SAT formula is satisfied by exactly the possible underlying SMCMs consistent with the manipulated marginal PAGs.With statistical errors, COmbINE selects a non-conflicting subset of constraints before solving the instance.
- Output: The output graph records features whose truth values are shared by all satisfying assignments, thereby summarizing invariant edges and orientations while retaining conflicting explanations.This summary is obtained by querying the SAT formula for variables with identical truth values across all solutions.
- Constraint construction: The SAT instance enforces graph validity through edge biconditionals, collider conditionals, acyclicity, and endpoint constraints ensuring every edge has an arrowhead.The constraints also prohibit simultaneous tails in both directions, corresponding to the no-selection-bias condition.
21 end
COmbINE encodes cross-dataset causal constraints in SAT and summarizes invariant and variant features across models consistent with heterogeneous interventions and measurements. It is sound and complete in the sample limit, while its conflict-resolution strategy ranks constraints by confidence to handle statistical errors.
- Constraint encoding: COmbINE incorporates manipulation information by restricting plausible inducing paths so edges cannot point into manipulated variables.For example, when X15 is manipulated, an inducing edge cannot have an arrow into X15.
- Constraint encoding: The algorithm converts observed adjacencies and independencies into constraints over plausible causal structures and solves them as a SAT instance.Conflicting constraints can make the SAT instance unsolvable, so soft constraints are selected incrementally when statistical errors occur.
- Summary graph: COmbINE’s summary graph marks invariant edges, absent edges, and endpoint orientations across the consistent underlying SMCMs.Solid edges are present in all possible underlying SMCMs, while absent edges are absent in all of them; dashed features vary across models.
- Cross-dataset inference: COmbINE can infer a solid edge between variables never measured together by combining constraints from overlapping datasets.Figure 6 illustrates this through two possible structures in which Y and Z share an edge in every consistent SMCM.
- Guarantees: Theorem 13 establishes soundness and completeness: every solid feature is present in all consistent SMCMs, and every universally present feature is solid.This guarantee applies to the summary graph returned by COmbINE under the stated constraint formulation.
- Conflict resolution: The Maximum MAP Ratio ranks adjacency and non-adjacency constraints using p-values, but its estimates rely on heuristic approximations.The method uses maximum p-values from FCI and is affected by dependence among tests and by taking maxima over several tests.
5. Experimental Evaluation
The experimental evaluation characterizes COmbINE using simulated networks, surrogate graph-recovery metrics, and repeated runs under varied problem settings.
- The evaluation varied sample size, the number of co-analyzed data sets, and other problem factors, and included comparisons of conflict-resolution methods.A proof-of-concept application used heterogeneous mass-cytometry data measuring overlapping variables under three manipulations.
- Experiments used randomly generated DAGs with specified variable counts and maximum parents per variable, followed by parameterized data generation.The default settings included maximum path length 3, α = 0.1, maximum conditioning set maxK = 5, and Fisher z-tests.
- COmbINE was evaluated on solid-edge and orientation precision and recall by comparing its summary graph with the data-generating SMCM.Dashed edges and endpoints were excluded from these surrogate metrics because they represent unresolved uncertainty.
- Because dashed features do not affect precision and recall, the evaluation also reported their proportions to expose conservative outputs.Results were summarized by the median, 5th percentile, and 95th percentile over 100 runs unless otherwise stated.
5.1 COmbINE vs. SBCSD
COmbINE was compared with SBCSD and alternative conflict-resolution strategies, showing stronger computational completion and favorable performance for the proposed MMR approach.
- SBCSD lacks a conflict-resolution strategy, so the comparison with COmbINE used an oracle of conditional independence and excluded statistical conflicts.SBCSD’s incremental backbone computation also complicates pre-ranking constraints.
- COmbINE completed all 10-variable cases and most 14-variable cases, whereas SBCSD completed less than 50% and 0%, respectively.SBCSD′ completed most 10-variable cases but only 4% of 14-variable cases.
- COmbINE was more time-efficient than SBCSD and SBCSD′, with its compact constraint representation contributing at least partly to the difference.The comparison used acyclic networks with 10 and 14 variables and measured running time on completed cases.
- MMR achieved better precision and identified more solid edges than BCCDR, while BCCDR achieved slightly better recall.MMR and BCCDR were compared alongside MaxSAT and wMaxSAT on networks with statistical errors.
- A maximum path length of 3 provided a reported trade-off among performance, dashed-feature percentages, and efficiency.The path-length comparison averaged results across networks and displayed 5th–95th percentile ranges.
- For 50-variable networks, BCCDR ratio estimation took about 150 seconds on average, whereas MMR ratio estimation took less than a second.MaxSAT and wMaxSAT did not show significant quality benefits in the evaluated setting and often exceeded the 500-second limit.
5.3 COmbINE performance with increasing maximum path length
Limiting maximum path length affects COmbINE’s uncertainty and performance, with length 3 reported as a practical compromise.
- Learning performance was not monotonic as maximum path length increased.Long paths may be needed for asymptotic correctness but can propagate statistical errors into complicated solutions.
- Maximum path lengths above 3 did not significantly affect performance, making 3 a reasonable trade-off among precision, recall, uncertainty, and efficiency.These findings motivated maximum path length 3 as COmbINE’s default parameter.
5.4 COmbINE performance as a function of network density and size
COmbINE’s performance declines with network density, while additional input data sets and larger samples improve recall and reduce uncertainty.
- Learning performance monotonically decreased as network density increased, while the percentage of dashed features did not significantly vary.Density was controlled by the maximum number of parents per variable.
- Network size had a smaller performance impact in sparse networks, but dense networks performed relatively poorly and worsened with larger sizes.The figure reports s- and o-precision, s- and o-recall, and dashed-feature proportions.
- Increasing the number of input data sets steadily reduced dashed features and improved recall, while precision was relatively unaffected.The corresponding figure reports median performance with a shaded 5th–95th percentile range.
- Increasing sample size improved recall and reduced the percentage of dashed endpoints.The number of input data sets was held constant at the default value of 5 in this comparison.
5.6 COmbINE performance for increasing number of latent variables
COmbINE’s performance is evaluated under increasing confounding and varying computational factors. Confounding has limited overall impact, while variables and maximum path length are identified as key runtime determinants.
- Latent variables: Overall, increasing the number of confounding variables does not greatly affect COmbINE’s performance.The evaluation considers 3, 6, and 9 latent variables in 30-variable networks.
- Latent variables: COmbINE’s s-Recall is lower with confounded variables than without confounding for the same network size.
- Computational performance: Running time depends on maximum path length, input data sets, sample size, and the number of variables.
- Computational performance: The number of variables and maximum path length seem to be the most critical factors for computational performance.
5.8 A case study: Mass Cytometry data
The mass-cytometry case study applies COmbINE to heterogeneous measurements of CD4+ and CD8+ T-cells under interventions. It demonstrates a proof-of-concept analysis, while the authors caution that the output graphs cannot be quantitatively validated against known ground truth.
- Data and biological setting: Mass cytometry measures protein activity in cells and supports studying immune-system signaling profiles.
- Data and biological setting: Mass cytometry is suitable for causal discovery because it measures single cells and provides samples in the thousands, but it measures at most 34 variables.
- Data and biological setting: The case study focuses on CD4+ and CD8+ T-cells and combines overlapping protein measurements from two studies.The procedure was repeated for both cell sub-populations.
- COmbINE analysis: COmbINE analyzes mass-cytometry data with overlapping variables under three different interventions.
- COmbINE analysis: The analysis predicts pAkt as a direct cause of pMAPK in both CD4+ and CD8+ cells.
- Interpretation: The case study is a proof-of-concept because the ground truth is unknown and the authors make no claims about the validity of the output graphs.
6. Conclusions and Future Work
COmbINE provides sound and complete causal discovery for overlapping variable sets under different interventions in acyclic domains. It combines SAT-based structural inference with confidence-based conflict resolution and demonstrates efficiency, scalability, and real-data applicability.
- Conclusions: COmbINE is sound and complete for causal discovery from multiple data sets with overlapping variables and different interventions in acyclic domains.
- Conclusions: COmbINE converts constraints on inducing paths into a SAT instance and summarizes identifiable and non-identifiable SMCM characteristics.
- Empirical evaluation: COmbINE outperforms a similar algorithm in efficiency and scales to networks with up to 100 variables for relatively sparse networks.
- Conflict resolution: COmbINE ranks dependencies and independencies by confidence as a function of p-values to resolve conflicts caused by statistical errors.
- Empirical evaluation: Limiting maximum path length trades fewer inferences for improved computational efficiency.
- Future work: Future work includes soft interventions and known instrumental variables, while the method can query SAT solutions for structural characteristics and prior constraints.
Proposition
The proposition establishes that the SAT constraints characterize possible underlying SMCMs by matching graph adjacencies, collider structures, and path properties across data-set PAGs. The proof uses inducing-path equivalence and the construction of the initial search graph.
- Proposition: An inducing path in a faithful SMCM exists exactly when the corresponding inducing path exists in its faithful MAG.
- Search graph: The initial search graph contains the relevant edges of an underlying SMCM and preserves ancestral and possibly inducing path properties.
- Constraint construction: The SAT constraints enforce edge presence or absence by requiring corresponding inducing paths or their absence in manipulated models.
- Constraint construction: Collider and non-collider constraints preserve unshielded triples between the PAGs and the candidate SMCMs.
- Constraint construction: Constraints on discriminating paths likewise preserve collider status in the candidate SMCMs.
- Formula semantics: Any graph satisfying the final formula is a possibly underlying SMCM with no directed cycles and at most one tail per edge.