Don’t Test What You Can Deduce: Causal Discovery with Logical Inference

Jonghwan Kim, Sanghack Lee
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:2958-2993, 2026.

Abstract

Constraint-based causal discovery relies on conditional independence tests (CITs), which are highly unstable in high-dimensional settings. As the conditioning set grows, CITs suffer from low statistical power, leading to frequent false negatives. In the context of structure learning, this causes error propagation that degrades the accuracy of the estimated graph. We propose DF-{PC} (Deduce-First {PC}), a theoretically sound framework that integrates graphoid-based reasoning into the {PC} algorithm. Unlike prior approaches that primarily utilize deduction for conflict resolution or additive checks, DF-{PC} adopts a proactive “Deduce-First” strategy: it prioritizes logical deduction from strictly lower-order tests to preemptively replace high-order CITs. This "Deduce-First" strategy enables structure learning with potentially fewer CITs while improving performance. Empirical evaluations across various settings demonstrate that DF-{PC} achieves competitive learning performance and computational efficiency.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-kim26a, title = {Don’t Test What You Can Deduce: Causal Discovery with Logical Inference}, author = {Kim, Jonghwan and Lee, Sanghack}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {2958--2993}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/kim26a/kim26a.pdf}, url = {https://proceedings.mlr.press/v337/kim26a.html}, abstract = {Constraint-based causal discovery relies on conditional independence tests (CITs), which are highly unstable in high-dimensional settings. As the conditioning set grows, CITs suffer from low statistical power, leading to frequent false negatives. In the context of structure learning, this causes error propagation that degrades the accuracy of the estimated graph. We propose DF-{PC} (Deduce-First {PC}), a theoretically sound framework that integrates graphoid-based reasoning into the {PC} algorithm. Unlike prior approaches that primarily utilize deduction for conflict resolution or additive checks, DF-{PC} adopts a proactive “Deduce-First” strategy: it prioritizes logical deduction from strictly lower-order tests to preemptively replace high-order CITs. This "Deduce-First" strategy enables structure learning with potentially fewer CITs while improving performance. Empirical evaluations across various settings demonstrate that DF-{PC} achieves competitive learning performance and computational efficiency.} }
Endnote
%0 Conference Paper %T Don’t Test What You Can Deduce: Causal Discovery with Logical Inference %A Jonghwan Kim %A Sanghack Lee %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-kim26a %I PMLR %P 2958--2993 %U https://proceedings.mlr.press/v337/kim26a.html %V 337 %X Constraint-based causal discovery relies on conditional independence tests (CITs), which are highly unstable in high-dimensional settings. As the conditioning set grows, CITs suffer from low statistical power, leading to frequent false negatives. In the context of structure learning, this causes error propagation that degrades the accuracy of the estimated graph. We propose DF-{PC} (Deduce-First {PC}), a theoretically sound framework that integrates graphoid-based reasoning into the {PC} algorithm. Unlike prior approaches that primarily utilize deduction for conflict resolution or additive checks, DF-{PC} adopts a proactive “Deduce-First” strategy: it prioritizes logical deduction from strictly lower-order tests to preemptively replace high-order CITs. This "Deduce-First" strategy enables structure learning with potentially fewer CITs while improving performance. Empirical evaluations across various settings demonstrate that DF-{PC} achieves competitive learning performance and computational efficiency.
APA
Kim, J. & Lee, S.. (2026). Don’t Test What You Can Deduce: Causal Discovery with Logical Inference. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:2958-2993 Available from https://proceedings.mlr.press/v337/kim26a.html.

Related Material