Abstract
One of the common obstacles for learning causal models from data is that high-order conditional independence (CI) relationships between random variables are difficult to estimate. Since CI tests with conditioning sets of low order can be performed accurately even for a small number of observations, a reasonable approach to determine casual structures is to base merely on the low-order CIs. Recent research has confirmed that, e.g. in the case of sparse true causal models, structures learned even from zero- and first-order conditional independencies yield good approximations of the models. However, a challenging task here is to provide methods that faithfully explain a given set of low-order CIs. In this paper, we propose an algorithm which, for a given set of conditional independencies of order less or equal to k, where k is a small fixed number, computes a faithful graphical representation of the given set. Our results complete and generalize the previous work on learning from pairwise marginal independencies. Moreover, they enable to improve upon the 0-1 graph model which, e.g. is heavily used in the estimation of genome networks.
Introduction
In causal discovery, the primary objective is to infer the underlying Directed Acyclic Graph (DAG) that represents causal relationships among variables from observational data. The standard approach relies on Conditional Independence (CI) tests. For instance, if variables $A$ and $B$ are independent given $C$, it implies that $C$ d-separates $A$ and $B$ in the causal graph.
However, high-order CI tests—those conditioning on many variables—suffer from the "curse of dimensionality." In high-dimensional settings with limited samples, such as genomic data, these tests become statistically unreliable. While researchers often resort to low-order tests (conditioning on zero or one variable), these provide an incomplete picture, often resulting in overly dense "0-1 graphs" that contain many false positive edges. This paper introduces the LOCI (Low-Order Causal Inference) algorithm to bridge this gap by providing a faithful graphical representation based solely on low-order CI information.
The LOCI Algorithm
The LOCI algorithm is designed to find a DAG that is $k$-faithful to the data, meaning it perfectly matches all CI statements of order $k$ or less. The process unfolds in three distinct stages:
- Skeleton Construction: The algorithm begins with a complete graph and removes edges between any two nodes found to be independent given any set of size $\le k$.
- Incompatibility Pruning: This is the core innovation of LOCI. The algorithm identifies "incompatible nodes"—pairs that cannot be directly connected in any valid DAG because doing so would conflict with the observed low-order CI patterns (e.g., v-structures). This allows for the removal of edges that a standard 0-1 graph would retain.
- Orientation: Finally, the algorithm applies Meek's logical rules to orient the remaining edges into a Completed Partially Directed Acyclic Graph (CPDAG), representing the equivalence class of all possible causal models consistent with the low-order constraints.
Key Insights: Incompatibility and Pruning
The fundamental breakthrough of LOCI is the realization that high-order independence can often be inferred from a specific configuration of low-order tests. If connecting two nodes $A$ and $B$ forces a conflict in the surrounding v-structures (colliders), then $A$ and $B$ must be independent at some higher order, even if that higher order cannot be reliably tested directly. By formalizing this notion of incompatibility, LOCI can prune the graph significantly more than traditional methods, moving closer to the true underlying causal skeleton without requiring high-sample-size CI tests.
Experimental Results
The authors evaluated LOCI using synthetic datasets of random DAGs with varying sizes ($n=20, 60, 100$) and sparsity levels. The results demonstrate that LOCI significantly outperforms the standard 0-1 graph model:
- Edge Reduction: In a 100-node graph with an average degree of 4, the 0-1 graph contained approximately 1061 edges. LOCI successfully pruned this to roughly 598 edges, a much closer approximation to the true DAG's 199 edges.
- V-Structure Recovery: Even with only first-order CIs ($k=1$), LOCI recovered the vast majority of true v-structures while maintaining a very low false-positive rate.
- Robustness: The algorithm provides a mathematically sound "best approximation" of the causal structure when information is limited, making it particularly valuable for high-dimensional, low-sample applications.
Conclusion and Future Work
LOCI offers a robust framework for causal discovery in data-starved environments. While the current evaluation assumes an "oracle" model with perfect low-order CI tests, future research will focus on handling statistical noise and p-values in real-world data. Additionally, the authors suggest that LOCI could be integrated into active learning frameworks to strategically select the most informative CI tests, further optimizing the discovery process.
Summary updated