On Causal Discovery in the Presence of Deterministic Relations
Li, Loka Al Ghothani, Hanin Huang, Biwei Chen, Guangyi Zhang, Jiji Harel, Shahar Zhang, Kun
Li, Loka
Al Ghothani, Hanin
Huang, Biwei
Chen, Guangyi
Zhang, Jiji
Harel, Shahar
Zhang, Kun
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2024
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Many causal discovery methods typically rely on the assumption of independent noise, yet real-life situations often involve deterministic relationships. In these cases, observed variables are represented as deterministic functions of their parental variables without noise.When determinism is present, constraint-based methods encounter challenges due to the violation of the faithfulness assumption. In this paper, we find, supported by both theoretical analysis and empirical evidence, that score-based methods with exact search can naturally address the issues of deterministic relations under rather mild assumptions. Nonetheless, exact score-based methods can be computationally expensive. To enhance the efficiency and scalability, we develop a novel framework for causal discovery that can detect and handle deterministic relations, called Determinism-aware Greedy Equivalent Search (DGES). DGES comprises three phases: (1) identify minimal deterministic clusters (i.e., a minimal set of variables with deterministic relationships), (2) run modified Greedy Equivalent Search (GES) to obtain an initial graph, and (3) perform exact search exclusively on the deterministic cluster and its neighbors. The proposed DGES accommodates both linear and nonlinear causal relationships, as well as both continuous and discrete data types. Furthermore, we investigate the identifiability conditions of DGES. We conducted extensive experiments on both simulated and real-world datasets to show the efficacy of our proposed method.
Citation
L. Li et al., “On Causal Discovery in the Presence of Deterministic Relations,” Adv Neural Inf Process Syst, vol. 37, pp. 130920–130952, Dec. 2024, Accessed: Mar. 24, 2025. [Online]. Available: https://github.com/lokali/DGES.git.
Source
Advances in Neural Information Processing Systems (NeurIPS 2024)
Conference
Keywords
Causal discovery, Deterministic relations, Score-based methods, Greedy Equivalent Search (GES), Faithfulness assumption
Subjects
Source
Publisher
NEURIPS