Coresets for fast causal discovery with the additive noise model.

Causal discovery reveals the true causal relationships behind data and discovering causal relationships from observed data is a particularly challenging problem, especially in large-scale datasets. The functional causal model is an effective method for causal discovery, but its time efficiency cannot be guaranteed. How to efficiently apply it to massive data still needs to be solved. In this paper, we propose a coreset construction for the additive noise model to accelerate causal discovery. According to the asymmetry characteristic of causality, samples were assigned different weights to construct the coreset. With the constructed coreset, we propose a Fast causal discovery algorithm based on the Additive Noise Model (FANM) to improve the time efficiency of the functional causal model while ensuring the result performance of causal discovery. Experiments on synthetic data and real-world data show that our proposed algorithm is much more time-efficient than the methods based on the functional causal model, and the runtime of FANM remains consistent as sample size increases while maintaining or exceeding the accuracy of the original nonlinear additive noise model. • New coresets proposed for the additive noise model greatly reduces the data size for causal discovery. • A time-efficient algorithm, FANM, is proposed for causal discovery based on the coresets. • The coreset construction is applied to causal graph learning algorithm, CDCSG, to show its effectiveness. • The proposed FANM is verified by both synthetic data and real-world data. [ABSTRACT FROM AUTHOR]