Causal Effect Identification in Uncertain Causal Networks

Sina Akbari, Fateme Jamshidi, Ehsan Mokhtarian, Matthew J. Vowels, Jalal Etesami, Negar Kiyavash

TL;DR

Standard causal inference assumes we have a perfectly known causal map, but in the real world, our knowledge of edges is often probabilistic. This paper introduces the "edge ID problem"—finding the most plausible identifiable subgraph within an uncertain network—proves it is NP-complete, and provides efficient algorithms to solve it.

What Problem Does This Paper Address?

Causal identification is the process of determining if a causal effect (e.g., "Does smoking cause lung cancer?") can be calculated using only observational data. Traditionally, this requires an Acyclic Directed Mixed Graph (ADMG) that is assumed to be 100% correct.

However, causal structures are rarely certain. They are often learned from noisy data via statistical tests or built from the conflicting opinions of domain experts. This leads to "uncertain causal networks" where each edge has a probability of existence rather than a hard "yes" or "no."

The authors tackle two main questions in this probabilistic setting:

  1. Most Probable Graph: Which specific graph is the most likely to be true while still allowing us to identify the causal effect of interest?
  2. Most Plausible Formula: Which identification formula is most likely to be valid across the distribution of possible graphs?

Methods

The authors show that both problems can be reduced to a new combinatorial optimization challenge they call the edge ID problem. The goal is to find a set of edges to remove from the uncertain graph such that the remaining structure is identifiable and the "cost" (based on edge probabilities) is minimized.

Figure 1: (a) An example of a probabilistic ADMG G with corresponding edge probabilities. (b) and (c) are two different subgraphs of G in which Q[y] is identifiable.

To solve this, they propose three main approaches:

  • EDGEID (Recursive Exact Algorithm): A search-based method that uses the "maximal hedge" (a graphical structure that prevents identification) to prune the search space.
  • HEID-1 & HEID-2 (Heuristics): Since the problem is NP-complete, these algorithms use a "minimum cut" approach to approximate the solution in cubic time, making them suitable for large networks.
  • Reduction to MCIP: They prove that the edge ID problem is equivalent to the Minimum Cost Intervention Problem (MCIP), allowing them to leverage existing solvers designed for experimental design.
Figure 3: Reduction from edge ID to MCIP.

Datasets

The researchers evaluated their algorithms using two types of benchmarks:

  • Synthetic Graphs: Randomly generated ADMGs ranging from 5 to 250 vertices, using a sparsity constraint to simulate realistic network densities.
  • Real-World Networks: Four established causal structures—Psych (22 nodes), Barley (48 nodes), Water (32 nodes), and Alarm (37 nodes)—with simulated edge uncertainties to mimic expert belief or statistical confidence.

Key Insights and Ideas

  • Monotonicity of Identification: A crucial "aha" moment is the proof that if a causal effect is identifiable in a graph, it remains identifiable in every edge-induced subgraph. This property allows the optimization to focus on removing edges to "break" hedges.
  • Complexity: The authors formally prove that finding the most plausible identifiable subgraph is NP-complete. This justifies the need for the heuristic approaches they developed.
  • Unification of Problems: By transforming multiplicative probabilities into additive log-costs, the authors unified the search for the "most probable graph" and the "most plausible formula" into a single optimization framework.
  • Negative Correlations: The framework is flexible enough to handle "perfect negative correlations"—scenarios where an expert knows that if Edge A exists, Edge B cannot (e.g., due to a known independence).

Key Results

  • Heuristic Efficiency: The proposed heuristics (HEID-1/2) were remarkably fast, maintaining runtimes under 0.5 seconds even for networks with 250 nodes, whereas exact solvers often timed out after 3 minutes once networks exceeded 20-50 nodes.
  • Near-Optimal Accuracy: Despite being much faster, the heuristics achieved solution costs very close to the exact algorithms on both synthetic and real-world datasets.
  • Robustness: In real-world tests like the 'Alarm' network, the exact EDGEID algorithm found the optimal solution in just 0.0005 seconds, demonstrating that while the problem is hard in the worst case, structured real-world graphs are often highly tractable.
Figure 4: Experimental results comparing runtimes and solution costs across different algorithms.

Limitations and Future Work

  • Edge Independence: The primary results assume that edge uncertainties are mutually independent. While they discuss extensions for correlated edges, a fully general model for complex dependencies remains a future challenge.
  • Point vs. Partial Identification: This work focuses on point identification (finding a single value for the effect). The authors suggest that similar logic could be applied to partial identification (finding a range/bound for the effect) in the future.
  • External Validity: The authors caution that while their method finds the most plausible subgraph given the model, it does not guarantee that the resulting subgraph is the true physical process. Practitioners should still exercise domain-specific caution.

Summary updated

Abstract

Causal identification is at the core of the causal inference literature, where complete algorithms have been proposed to identify causal queries of interest. The validity of these algorithms hinges on the restrictive assumption of having access to a correctly specified causal structure. In this work, we study the setting where a probabilistic model of the causal structure is available. Specifically, the edges in a causal graph exist with uncertainties which may, for example, represent degree of belief from domain experts. Alternatively, the uncertainty about an edge may reflect the confidence of a particular statistical test. The question that naturally arises in this setting is: Given such a probabilistic graph and a specific causal effect of interest, what is the subgraph which has the highest plausibility and for which the causal effect is identifiable? We show that answering this question reduces to solving an NP-complete combinatorial optimization problem which we call the edge ID problem. We propose efficient algorithms to approximate this problem and evaluate them against both real-world networks and randomly generated graphs.
BibTeX
@inproceedings{akbari2023causal,
  author = {Sina Akbari and Fateme Jamshidi and Ehsan Mokhtarian and Matthew J. Vowels and Jalal Etesami and Negar Kiyavash},
  title = {{Causal Effect Identification in Uncertain Causal Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=pH4Fv7C3yC},
}
Figure