Measuring Conditional Independence by Independent Residuals: Theoretical Results and Application in Causal Discovery

Hao Zhang, Shuigeng Zhou, Jihong GuanAAAI 2018 · OpenReview

Abstract

We investigate the relationship between conditional independence (CI) $x \perp y | Z$ and the independence of two residuals $x – E(x | Z) \perp 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 Gaussian distributions, then $x \perp y | Z$ if and only if $x – E(x | Z) \perp y – E(y | Z)$. Furthermore, if all these external influences follow non-Gaussian distributions and the model satisfies the structural faithfulness condition, then we have $x \perp y | Z \Leftrightarrow x – E(x | Z) \perp y – E(y | Z)$. We apply these results to the causal discovery problem, showing that in linear non-Gaussian contexts, residuals can help distinguish Markov equivalence classes. Compared with existing discretization-based and kernel-based CI testing methods, the proposed ReCIT method provides a simpler, more robust way to measure CI, requiring only one unconditional independence test and two regression operations.

Introduction

In causal discovery, determining whether two variables are independent given a third set ($x \perp y | Z$) is a fundamental yet notoriously difficult task. If $X$ and $Y$ become independent once $Z$ is accounted for, it suggests the absence of a direct causal link. However, standard conditional independence (CI) testing suffers from the "curse of dimensionality": as the size of the conditioning set $Z$ grows, the data requirements for accurate testing increase exponentially. Existing kernel-based methods, while powerful, are computationally expensive and sensitive to noise. This paper introduces a simplified approach that reduces complex conditional tests to basic marginal independence tests between residuals.

The ReCIT Method

The proposed method, ReCIT (Residual-based Conditional Independence Test), simplifies CI testing through three primary steps:

  1. Regression of $x$ on $Z$: Obtain the residual $\epsilon_x = x - E(x|Z)$.
  2. Regression of $y$ on $Z$: Obtain the residual $\epsilon_y = y - E(y|Z)$.
  3. Independence Testing: Test if $\epsilon_x$ and $\epsilon_y$ are marginally independent.

Theoretically, the authors prove that under linear structural equation models (SEMs), $x \perp y | Z$ is equivalent to the independence of these residuals. This equivalence holds for both Gaussian and non-Gaussian noise. By integrating ReCIT into the standard PC algorithm (PCReCIT), the authors can orient edges in chains and forks by exploiting the asymmetry of non-Gaussian residuals—a capability traditional constraint-based methods lack.

Experimental Results

The authors evaluated ReCIT against the Kernel-based Conditional Independence Test (KCIT) using simulated data and benchmark causal networks like Hailfinder and Win95pts.

Accuracy and Dimensionality

A key advantage of ReCIT is its stability as the dimensionality of the conditioning set $Z$ increases. While KCIT's Type I error rate climbs significantly with more variables in $Z$, ReCIT maintains a stable error rate near the significance level (0.05).

Error rates of ReCIT vs KCIT as dimensionality of Z increases.

Causal Orientation in Non-Gaussian Settings

In non-Gaussian environments, residuals carry "fingerprints" of causal direction. If $Z$ causes $X$, the residual of $X$ given $Z$ is independent of $Z$. This property allows PCReCIT to orient edges that are typically indistinguishable in Markov equivalence classes. On a 6-node graph with no V-structures, PCReCIT correctly oriented all causal directions, whereas the kernel-based approach left most edges undirected.

Causal discovery results on a 6-node graph without V-structures: (a) True graph, (b) PCReCIT result, (c) PCKCIT result.

Performance Summary

Experiments also demonstrated that PCReCIT outperforms PCKCIT in discovering the "skeleton" of causal graphs, particularly with small sample sizes ($n < 100$). Furthermore, ReCIT showed greater robustness to noise, remaining accurate even when the noise-to-signal ratio was low.

Conclusion

ReCIT provides a simpler and more stable alternative to existing CI testing methods by reducing conditional tests to marginal ones. This simplification avoids complex conditional density estimations, making it particularly effective for high-dimensional data. While currently limited to linear models and reliant on the faithfulness assumption, future work could extend this residual-based framework to non-linear relationships using advanced regression techniques like Gaussian Process regression.

Summary updated

Abstract

We investigate the relationship between conditional independence (CI) x ⊥ y | Z and the independence of two residuals x – E ( x | Z ) ⊥ –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 model and all external influences follow Gaussian distributions, 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, 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 linear non-Gaussian context, x – E ( x | Z ) ⊥ y – E ( y | Z ) ⇒ x – E ( x | Z ) ⊥ z or y – E ( y | Z ⊥ z (∀ z ∈ Z ) if Z is a minimal d -separator, 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, compared 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 experimentally validated.
BibTeX
@inproceedings{zhang2018measuring,
  author = {Hao Zhang and Shuigeng Zhou and Jihong Guan},
  title = {{Measuring Conditional Independence by Independent Residuals: Theoretical Results and Application in Causal Discovery}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=Bk4JoCgObH},
}
Figure