提出更高效因果发现算法，减少条件独立性检验次数。
On the Number of Conditional Independence Tests in Constraint-based Causal Discovery
- 新算法将检验次数优化至 $p^{\mathcal{O}(s)}$
- 理论证明至少需 $2^{Ω(s)}$ 次检验，算法接近最优
- 适用于高维数据中的因果推断，尤其适合小团大小场景
从观测数据中学习因果关系是跨领域的重要问题。基于约束的方法通过执行条件独立性检验推断因果结构，但现有算法（如经典的PC算法）在最坏情况下需进行指数级的检验，其数量与因果图最大度数相关。尽管研究广泛，仍不清楚是否存在无需额外假设即可实现更好复杂度的算法。本文提出一种新算法，将所需检验次数降低至 $p^{\mathcal{O}(s)}$，其中 $p$ 为节点数，$s$ 为底层本质图的最大无向团大小。同时，我们证明任何基于约束的算法至少需 $2^{Ω(s)}$ 次检验，表明所提算法在检验次数上达到指数最优性（对数因子内）。通过半合成基因表达数据和真实数据集的仿真验证，结果表明该算法在减少检验次数方面显著优于现有方法。
原文摘要 · Abstract (English)
Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph. Despite extensive research, it remains unclear if there exist algorithms with better complexity without additional assumptions. Here, we establish an algorithm that achieves a better complexity of $p^{\mathcal{O}(s)}$ tests, where $p$ is the number of nodes in the graph and $s$ denotes the maximum undirected clique size of the underlying essential graph. Complementing this result, we prove that any constraint-based algorithm must perform at least $2^{Ω(s)}$ conditional independence tests, establishing that our proposed algorithm achieves exponent-optimality up to a logarithmic factor in terms of the number of conditional independence tests needed. Finally, we validate our theoretical findings through simulations, on semi-synthetic gene-expression data, and real-world data, demonstrating the efficiency of our algorithm compared to existing methods in terms of number of conditional independence tests needed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。