Causes and explanations in the structural-model approach: Tractable cases

Thomas Eiter, Thomas Lukasiewicz

Introduction

Determining the "actual cause" of an event is a fundamental task in artificial intelligence, yet it is often computationally prohibitive. While the structural-model approach developed by Halpern and Pearl (2001) provides a robust logical framework for defining causality, calculating these causes in general systems is NP-hard, often reaching the $\Sigma_2^P$ and $\Sigma_3^P$ levels of the polynomial hierarchy. This paper identifies the first known tractable cases for these problems, demonstrating that causality and explanations can be calculated in polynomial time for specific graph topologies.

The Problem of Causal Complexity

In causal reasoning, we seek to identify which variables in a system are responsible for a specific outcome. A classic example is the "Arsonists" scenario: if two arsonists drop matches and a forest burns down, we must determine if one, both, or a combination constitutes the "actual cause."

A basic causal graph representing the 'Arsonists' scenario, where multiple potential causes lead to a single outcome.

As the number of variables in such a model grows, the computational effort required to check every possible combination of events explodes. For real-time AI applications, this "intractability" is a major bottleneck. The authors address this by searching for structural arrangements—common in real-world diagnostic systems—that simplify the underlying mathematics.

Methods for Achieving Tractability

The authors propose several techniques to reduce complexity by focusing on the topology of the causal graph:

  1. Recursive Characterization: By re-formulating "weak causes" as a recursive property, the authors enable causality checks via information passing along graph edges, avoiding exhaustive searches.
  2. Graph Decomposition: The paper introduces the concept of decomposable graphs, where a complex network is broken down into a "chain" of smaller, width-bounded subgraphs.
  3. Pruning Irrelevant Variables: Algorithms were developed to identify and remove variables that do not influence the outcome or the potential cause, significantly simplifying the model in linear time.
Decomposition of a causal graph into a chain of width-bounded subgraphs.

Key Results and Structural Restrictions

The research identifies two primary architectures where causal reasoning is guaranteed to be tractable:

  • Causal Trees: Hierarchical structures where each variable has at most one effect, leading to a single root event.
  • Layered Causal Graphs: Networks organized into ranks where influence flows strictly from one layer to the next.

For these structures, the authors prove that deciding weak causes, actual causes, and explanations can be performed in $O(poly)$ time relative to the model size and variable domains. Furthermore, the decomposition method extends these results to any graph that can be flattened into a width-bounded chain.

Conclusion and Future Work

This work provides the first explicit proof that non-trivial cases of the Halpern-Pearl model are tractable. By showing that computational complexity depends on the "shape" of causality rather than just the number of variables, the authors open the door for more efficient causal AI in diagnostic and forensic applications. Future research will focus on identifying additional tractable graph shapes and developing automated methods for finding optimal graph decompositions in complex, real-world systems.

Summary updated

Abstract

This paper continues the research on the computational aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we first explore how an instance of deciding weak cause can be reduced to an equivalent instance in which irrelevant variables in the (potential) weak cause and the causal model are removed, which extends previous work by Hopkins. We then present a new characterization of weak cause for a certain class of causal models in which the causal graph over the endogenous variables has the form of a directed chain of causal subgraphs, called decomposable causal graph . Furthermore, we also identify two important subclasses in which the causal graph over the endogenous variables forms a directed tree and more generally a directed chain of layers, called causal tree and layered causal graph , respectively. By combining the removal of irrelevant variables with this new characterization of weak cause, we then obtain techniques for deciding and computing causes and explanations in the structural-model approach, which can be done in polynomial time under suitable restrictions. This way, we obtain several tractability results for causes and explanations in the structural-model approach. To our knowledge, these are the first explicit ones. They are especially useful for dealing with structure-based causes and explanations in first-order reasoning about actions, which produces large causal models that are naturally layered through the time line, and thus have the structure of layered causal graphs. Furthermore, an important feature of the tractable cases for causal trees and layered causal graphs is that they can be recognized efficiently, namely in linear time. Finally, by extending the new characterization of weak cause, we obtain similar techniques for computing the degrees of responsibility and blame, and hence also novel tractability results for structure-based responsibility and blame.
BibTeX
@misc{eiter2012causes,
  author = {Thomas Eiter and Thomas Lukasiewicz},
  title = {{Causes and explanations in the structural-model approach: Tractable cases}},
  year = {2012},
  eprint = {1301.0566},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1301.0566},
}
Figure