Linear-Time Primitives for Algorithm Development in Graphical Causal Inference
This work addresses computational bottlenecks for researchers and practitioners in causal inference by offering a scalable and flexible framework for algorithm development.
The paper tackles the problem of inefficient algorithmic primitives in graphical causal inference by introducing CIfly, a framework that reduces many causal reasoning tasks to reachability operations, achieving linear-time execution and providing a more efficient alternative to existing methods like moralization and latent projection.
We introduce CIfly, a framework for efficient algorithmic primitives in graphical causal inference that isolates reachability as a reusable core operation. It builds on the insight that many causal reasoning tasks can be reduced to reachability in purpose-built state-space graphs that can be constructed on the fly during traversal. We formalize a rule table schema for specifying such algorithms and prove they run in linear time. We establish CIfly as a more efficient alternative to the common primitives moralization and latent projection, which we show are computationally equivalent to Boolean matrix multiplication. Our open-source Rust implementation parses rule table text files and runs the specified CIfly algorithms providing high-performance execution accessible from Python and R. We demonstrate CIfly's utility by re-implementing a range of established causal inference tasks within the framework and by developing new algorithms for instrumental variables. These contributions position CIfly as a flexible and scalable backbone for graphical causal inference, guiding algorithm development and enabling easy and efficient deployment.