CIfly将因果推断任务转化为图的可达性问题，实现线性时间高效计算。
Linear-Time Primitives for Algorithm Development in Graphical Causal Inference
- 将多种因果推理任务归约为可即时构建的状态空间图中的可达性判断。
- 算法时间复杂度为线性，比传统方法快一个数量级。
- 适合需要高效因果推断的科研与工程场景，支持Python/R调用。
我们提出CIfly框架，通过将因果推理任务简化为即时构建的状态空间图中的可达性问题，实现高效的算法原语。该框架基于一个核心洞察：许多因果推理任务均可归约至特定构造的状态空间图中的可达性判断。我们形式化了一种规则表结构来指定此类算法，并证明其可在线性时间内运行。我们进一步证明，常见的道德化（moralization）和潜变量投影（latent projection）操作在计算上等价于布尔矩阵乘法。开源的Rust实现支持从文本规则表文件解析并执行算法，提供高性能且可通过Python和R访问的接口。我们通过在框架内重实现多个经典因果推断任务，并开发新的工具变量算法，展示了其灵活性与可扩展性。这些成果使CIfly成为图形化因果推断中可灵活使用、可高效部署的核心支撑系统。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。