DCILP: A Distributed Approach for Large-Scale Causal Structure Learning
This work addresses the scalability challenge in causal learning for researchers and practitioners dealing with large datasets, representing an incremental advancement by optimizing an existing bottleneck through a novel formulation.
The paper tackles the computationally demanding task of large-scale causal structure learning by introducing DCILP, a distributed divide-and-conquer approach that formulates graph reconciliation as an integer linear programming problem, demonstrating significant improvements in computational complexity while preserving learning accuracy on real-world problems and showing at most a slight loss on synthetic ones.
Causal learning tackles the computationally demanding task of estimating causal graphs. This paper introduces a new divide-and-conquer approach for causal graph learning, called DCILP. In the divide phase, the Markov blanket MB($X_i$) of each variable $X_i$ is identified, and causal learning subproblems associated with each MB($X_i$) are independently addressed in parallel. This approach benefits from a more favorable ratio between the number of data samples and the number of variables considered. In counterpart, it can be adversely affected by the presence of hidden confounders, as variables external to MB($X_i$) might influence those within it. The reconciliation of the local causal graphs generated during the divide phase is a challenging combinatorial optimization problem, especially in large-scale applications. The main novelty of DCILP is an original formulation of this reconciliation as an integer linear programming (ILP) problem, which can be delegated and efficiently handled by an ILP solver. Through experiments on medium to large scale graphs, and comparisons with state-of-the-art methods, DCILP demonstrates significant improvements in terms of computational complexity, while preserving the learning accuracy on real-world problem and suffering at most a slight loss of accuracy on synthetic problems.