Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables
This work addresses causal structure learning for researchers in fields like statistics and machine learning, but it appears incremental as it builds on existing ordering-based methods with a new optimization focus.
The authors tackled the problem of learning causal structures in the presence of unobserved variables by proposing ordering-based approaches that use a novel removable order (r-order) instead of traditional causal orders, resulting in improved performance and scalability as demonstrated on real-world and randomly generated networks.
We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature recover a graph through learning a causal order (c-order). We advocate for a novel order called removable order (r-order) as they are advantageous over c-orders for structure learning. This is because r-orders are the minimizers of an appropriately defined optimization problem that could be either solved exactly (using a reinforcement learning approach) or approximately (using a hill-climbing search). Moreover, the r-orders (unlike c-orders) are invariant among all the graphs in a MEC and include c-orders as a subset. Given that set of r-orders is often significantly larger than the set of c-orders, it is easier for the optimization problem to find an r-order instead of a c-order. We evaluate the performance and the scalability of our proposed approaches on both real-world and randomly generated networks.