Causal Effect Identification in Uncertain Causal Networks
TL;DR.
When the causal graph itself is uncertain, we ask for the most plausible subgraph in which a target effect becomes identifiable. We formulate this as the NP-complete edge-ID problem and develop exact and heuristic algorithms that trade graph plausibility against identifiability.
Why this matters.
Causal graphs often come with confidence scores rather than certainty. This framework lets us use that uncertainty directly instead of forcing a single graph, producing an explicit “most plausible identifiable” causal model.
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.
The paper at a glance
An informal guide to the problem, the idea, and the main results.
1. The problem
Classical identification assumes one known causal graph. In practice, scientists often only know a set of plausible graphs, perhaps because some edges are uncertain or partly oriented.
2. The key idea
We formulate identification over a family of admissible graphs. That turns the question into a robust one: is the effect identifiable in all compatible graphs, and if not, how do we characterize the ambiguity?
3. The edge-ID problem
We formulate the search for the most plausible identifiable subgraph as a combinatorial optimization problem and prove that edge ID is NP-complete.
4. Exact and fast approximate solvers
We derive an exact edge-ID algorithm, two fast heuristics, and polynomial-time reductions between edge ID and minimum-cost intervention design. This makes it possible to leverage both graph-specific methods and existing causal-design solvers.
5. How it works
- Represent the graph uncertainty explicitly.
- Characterize identification across the induced family of causal graphs.
- Use optimization or graph-search ideas to compute robust conclusions.
- Return whether the target effect is identified uniformly or only on a subset of graphs.
What the experiments show
Where this helps
Good fit
- You have several plausible causal graphs rather than one definitive structure.
- You want identification conclusions that are robust to structural ambiguity.
- You care about turning partial causal knowledge into a concrete inferential statement.
Keep in mind
- Edge probabilities can encode expert belief or confidence from statistical structure-learning procedures.
- The framework includes both exact and heuristic solvers, allowing users to choose between guaranteed optimality and near-instant practical solutions.
Cite this paper
@inproceedings{akbari2023uncertain,
title = {Causal Effect Identification in Uncertain Causal Networks},
author = {Sina Akbari and Fateme Jamshidi and Ehsan Mokhtarian and Matthew Vowels and Jalal Etesami and Negar Kiyavash},
booktitle = {Advances in Neural Information Processing Systems},
volume = {36},
year = {2023},
url = {https://proceedings.neurips.cc/paper_files/paper/2023/hash/017c897b4d85a744f345ccbf9d71e501-Abstract-Conference.html}
}