Introduction
Distinguishing between "correlation" and "causation" remains the fundamental challenge of causal inference. Standard constraint-based methods, such as the widely used PC algorithm, rely on conditional independence (CI) tests to map out causal structures. However, these methods face two major hurdles. First, CI tests are notoriously unreliable when data is scarce, leading to "early errors" that cascade and result in completely incorrect causal graphs. Second, without interventions, it is often impossible to distinguish a direct causal link from a spurious correlation caused by a hidden confounder.
To tackle these challenges, researchers ask a fundamental question: What is the simplest possible hidden variable that could explain the observed correlation? By leveraging the concept of common entropy—the minimum complexity required for a latent variable to explain the correlation between two observed variables—this paper introduces an information-theoretic framework that significantly improves causal discovery in data-starved scenarios.
The Core Concept: Common Entropy
The paper centers on Rényi Common Entropy. If two variables $X$ and $Y$ are correlated, their common entropy is the minimum entropy a third variable $Z$ must have to make $X$ and $Y$ independent when conditioned on $Z$.
A core assumption of this approach is the "Simplicity of Nature": latent confounders in real-world systems are often relatively simple (low entropy) compared to the variables they influence. Conversely, causal mediators (variables in a chain $X \to M \to Y$) tend to be complex. Common entropy provides a physical lower bound. If a statistical test suggests that a low-entropy variable $S$ explains away the correlation between $X$ and $Y$, but the common entropy of $(X,Y)$ is higher than the entropy of $S$, the statistical test is likely a false positive caused by noise.
Methodology: LatentSearch and EntropicPC
To operationalize this concept, the authors introduce two key technical contributions:
- LatentSearch Algorithm: An iterative, multiplicative update algorithm designed to find the minimal latent variable $Z$. It optimizes a loss function that balances the residual dependency between $X$ and $Y$ against the complexity (entropy) of $Z$.
- EntropicPC: A modified version of the standard PC algorithm that uses common entropy as an information-theoretic "sanity check." Before the algorithm accepts that a set of variables $S$ makes $X$ and $Y$ independent, it checks if the entropy of $S$ is at least as large as the common entropy of $X$ and $Y$. If $S$ is too "simple" to explain the correlation, the independence claim is rejected.
Furthermore, the authors prove that if a hidden confounder is simple (low entropy), they can theoretically distinguish a purely confounded graph from one with a direct causal link, aiding in causal identification.
Experimental Validation and Key Results
The authors validated their approach using a mix of synthetic and real-world data, including 100 Erdös-Rényi random graphs, the Tuebingen Cause-Effect Pairs benchmark, and the ADULT census dataset.
- Superior Performance in Small Samples: On synthetic data with only 1,000 samples, EntropicPC showed significant improvements in identifying the correct "skeleton" (the presence of edges) of the causal graph compared to the standard PC algorithm. The F1 score for EntropicPC was consistently higher when data was limited, demonstrating its robustness to noise and early errors.
- Real-World Success: In the ADULT dataset, the standard PC algorithm failed to find any causes for "Salary," treating it as an isolated node. EntropicPC, however, correctly identified that "Education" and "Occupation" are causal drivers of "Salary."
- Mediator Validation: Using the Tuebingen dataset, the authors confirmed their hypothesis that causal mediators generally have high entropy, supporting the use of common entropy as a reliable tool for distinguishing causal structure.
Limitations and Future Work
While highly effective, the framework has limitations. The assumption that confounders are "simpler" than their effects may not hold in every domain, such as highly complex biological systems. Additionally, the LatentSearch algorithm is iterative, and scaling it to graphs with hundreds or thousands of variables will require further optimization. Finally, the current work focuses on discrete variables; extending these information-theoretic bounds to continuous variables using differential entropy remains a promising but challenging future direction.
Summary updated