This article proposes a new method for causal discovery based on a novel dependence measurement criterion, namely, Multi-level Wavelet Mapping Correlation (MWMC). MWMC captures nonlinear dependencies between variables by measuring their correlations across multiple levels of wavelet mappings. From a theoretical perspective, we show that the empirical estimate of MWMC converges exponentially fast to its population quantity. Under the null hypothesis of independence, we further design a permutation-based independence testing procedure, termed the Wavelet Independence Test (WIT), built upon MWMC. We prove that WIT not only effectively controls the Type I error rate (false positives), but also guarantees that the Type II error rate (false negatives) is upper bounded by \(\mathcal{O}(n^{-1})\) , where \( n \) denotes the sample size, even with a finite number of permutations. Building on these theoretical guarantees, we derive a causal discovery method by integrating MWMC-based WIT into standard causal discovery pipelines. Extensive experiments on (conditional) independence testing and causal discovery using both synthetic and real-world datasets with varying sample sizes demonstrate that our approach consistently outperforms existing independence testing and causal discovery methods in terms of reduced Type II error rates and statistically validated performance improvements. Impact Statement —Causal discovery is a fundamental task in knowledge discovery, aiming to uncover the underlying data-generating mechanisms in order to support more accurate and interpretable predictions. Statistical independence tests and conditional independence (CI) tests have long served as core tools in this area. To improve the reliability of independence testing, we propose a novel test, WIT, which achieves lower Type II error rates in 19 out of 25 distinct experimental scenarios involving diverse data distributions, compared to 15 out of 25 for the strongest existing baseline. We further apply WIT to CI testing and causal discovery, and extensive empirical results show that it consistently improves the performance of multiple causal discovery algorithms across a range of experimental settings.

Determining conditional independence (CI) relationships between random variables is a fundamental yet challenging task in machine learning and statistics, especially in high-dimensional settings. Existing generative model-based CI testing methods, such as those utilizing generative adversarial networks (GANs), often struggle with undesirable modeling of conditional distributions and training instability, resulting in subpar performance. To address these issues, we propose a novel CI testing method via score-based generative modeling, which achieves precise Type I error control and strong testing power. Concretely, we first employ a sliced conditional score matching scheme to accurately estimate conditional score and use Langevin dynamics conditional sampling to generate null hypothesis samples, ensuring precise Type I error control. Then, we incorporate a goodness-of-fit stage into the method to verify generated samples and enhance interpretability in practice. We theoretically establish the error bound of conditional distributions modeled by score-based generative models and prove the validity of our CI tests. Extensive experiments on both synthetic and real-world datasets show that our method significantly outperforms existing state-of-the-art methods, providing a promising way to revitalize generative model-based CI testing.

Discovering causal relationships from observational data is a challenging topic in artificial intelligence. Recent works formulate causal discovery as a continuous optimization problem with a differentiable acyclic constraint. Although these methods have achieved considerable performance improvement, they have two drawbacks: 1) they require a relatively large number of training samples; and 2) their performance will substantially deteriorate when facing heterogeneous noise. To address these problems, we first propose a low-order conditional independence (CI) constraint for the continuous optimization problem, and then design a soft version of the constraint by transforming it to a regularization term in the loss function of the continuous optimization problem. We show the convergence of continuous optimization with our constraint under some mild conditions, and the consistency of causal structure learning with the CI regularization. Extensive experiments on both synthetic and real-world datasets show that with our CI constraint or regularization, existing continuous optimization methods can achieve considerable performance improvement of causal discovery, especially when sample size is small.

Recently, many regression-based conditional independence (CI) test methods have been proposed to solve the problem of causal discovery. These methods provide alternatives to test CI of x,y given Z by first removing the information of the controlling set Z from x and y , and then testing the independence between the two residuals R x,Z and R y,Z . When the residuals are linearly uncorrelated, the independence test between them is nontrivial. With the ability to calculate inner product in high-dimensional space, kernel-based methods are usually used to achieve this goal, but they are considerably time-consuming. In this paper, we test the independence between two linear combinations under linear structural equation model. We show that the dependence between the two residuals can be captured by the difference between the similarity of R x,Z and R y,Z and that of R x,Z and R r ( R r is an independent copy of R y,Z ) in high-dimensional space. With this result, we provide a new way to test CI based on the similarity between residuals, which is called SCIT — the abbreviation of Similarity-based CI Testing. Furthermore, we develop two versions of the proposal, called Kernel-SCIT and Neural-SCIT, respectively. Kernel-SCIT calculates the similarity by using kernel functions, while Neural-SCIT approximates the upper bound of the similarity by using deep neural networks. In both algorithms, random permutation tests are performed to control Type I error rate. The proposed tests are evaluated on (conditional) independence test and causal discovery with both synthetic and real datasets. Experimental results show that Kernel-SCIT is simpler yet more efficient and effective than the typical existing kernel-based methods HSIC and KCIT in the cases of small sample size, and Neural-SCIT can significantly boost the performance of CI testing when sufficient samples are available. The source code is available at https://github.com/xyw5vplus1/SCIT .

In recent years, many methods have been developed for discovering causal relationships from observed data. However, as an important kind of causes existing in many causal systems, combined causes (e.g. multi-factor causes consisting of two or more component variables that individually might not be a cause) have not received enough attention. The existing approach includes both individual and combined variables in the causal discovery process using constraint-based methods, can neither distinguish a set of Markov equivalence classes nor identify a combined cause containing one (or more) individual cause(s), therefore can output only some combined causes, instead of all combined causes. In this paper, we first subsume all possible combined causes into three types and give them formal definitions, then extend the additive noise model (ANM) to infer combined causes. We show that if a candidate variable set X w.r.t. a target Y satisfies: (1) allowing ANM for only the forward direction X→Y, and (2) no disturbance variable is contained in X, i.e., removing any component of X will weaken the causal relationship between X and Y, then X forms a combined cause. Based on this finding, we develop an efficient method to discover combined causes. Furthermore, we also conduct extensive experiments to validate the proposed method on both synthetic and real-world data sets.

We investigate the relationship between conditional independence (CI) x ⫫ y | Z and the independence of two residuals x −E( x | Z )⫫ y −E( y | Z ), where x and y are two random variables and Z is a set of random variables. We show that if x , y , and Z are generated by following linear structural equation models and all external influences follow joint Gaussian distribution, then x ⫫ y | Z if and only if x −E( x | Z )⫫ y −E( y | Z ). That is, the test of x ⫫ y | Z can be relaxed to a simpler unconditional independence test of x −E( x | Z )⫫ y −E( y | Z ). Furthermore, testing x −E( x | Z )⫫ y −E( y | Z ) can be simplified by testing x −E( x | Z )⫫ y or y −E( y | Z )⫫ x . On the other side, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have x ⫫ y | Z ⇔ x −E( x | Z )⫫ y −E( y | Z ). We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of V -structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in the linear non-Gaussian context, in many cases x −E( x | Z )⫫ z or y −E( y | Z )⫫ z (∀ z ∈ Z and Z is a minimal d -separator) is satisfied when x −E( x | Z )⫫ y −E( y | Z ), which implies z causes x (or y ) if z directly connects to x (or y ). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes. In summary, comparing with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is extensively validated by experiments.