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.
Introduction
Standard causal inference typically assumes access to a perfectly accurate "map" of cause-and-effect relationships. In practice, however, our knowledge of these connections is often uncertain. Causal discovery tools and domain experts frequently provide probabilities rather than certainties (e.g., "There is a 70% chance that X causes Y"). Standard identification algorithms fail in these scenarios because they require a binary specification for every edge.
As illustrated in Figure 1, the authors address this by introducing a framework for causal identification in probabilistic graphs. They tackle two primary questions: identifying the most probable graph that allows for a specific causal query to be calculated, and finding the most plausible identification formula valid across possible graphs.
The Edge ID Problem
The authors demonstrate that these questions reduce to a single combinatorial optimization problem termed the Edge ID Problem.
Core Logic and Complexity
A fundamental insight of the paper is the "monotonicity" property: if a causal effect is identifiable in a graph, it remains identifiable if edges are removed. This allows the search to be framed as finding the "cheapest" set of edges to remove—where cost corresponds to the negative log-probability of the edge—to reach an identifiable state. The authors prove that the Edge ID Problem is NP-complete, necessitating efficient approximation methods for large-scale networks.
Algorithmic Solutions
To address the computational complexity, the paper proposes several algorithms:
- EDGEID (Exact): A recursive algorithm that uses graphical structures known as "maximal hedges" to prune the search space effectively.
- HEID-1 & HEID-2 (Heuristics): These fast approximation algorithms transform the causal problem into a Minimum-Cut problem, a well-known optimization task solvable in cubic time.
- Reduction to MCIP: The problem is also shown to be equivalent to the "Minimum-Cost Intervention Problem" (MCIP). Figure 6 displays the construction of a transformed graph $\mathcal{H}$ used to leverage existing MCIP solvers.
Experimental Results
The researchers evaluated their algorithms using synthetic graphs (up to 250 vertices) and four real-world benchmarks from Bayesian network literature: Psych, Barley, Water, and Alarm.
- Efficiency: The heuristic algorithms (HEID-1 and HEID-2) maintained runtimes of less than 0.5 seconds even for the largest graphs. In contrast, exact solvers often timed out after 3 minutes for graphs exceeding 20–50 nodes.
- Accuracy: In real-world datasets, the heuristics consistently found the optimal (most plausible) identifiable subgraph in almost every test case.
- Confidence Scoring: The framework allows researchers to quantify confidence. By calculating the ratio of the plausibility of the identified subgraph to the original uncertain graph, researchers can assign a "confidence score" to their causal identifications.
Conclusion and Future Work
This work provides a robust method for performing causal inference when the underlying structure is uncertain. While the current model assumes edge independence, it sets the stage for future research into complex edge dependencies and partial identification (bounding effects). By bridging the gap between probabilistic discovery and formal identification, this framework makes causal inference more applicable to real-world, noisy data.
Summary updated