Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM] seminar - Column Generation for Causal Discovery via Difference of Submodular Optimization: Inexact and Exact Approaches

Causal discovery aims to infer causal relationships among variables from data. Its inherently combinatorial nature makes it computationally highly complex. Existing optimization formulations suffer from an exponential growth in the numbers of variables and constraints as the data dimension increases. We consider a column generation approach to deal with this exponential size. To address the challenging discrete and nonlinear pricing problem in column generation, we reformulate it as a difference-of-submodular optimization problem and propose inexact and exact solution approaches, utilizing its combinatorial properties. The proposed methods substantially reduce the computational difficulty of the pricing subproblem while maintaining the quality of the generated columns. Experiments show that the proposed methods significantly outperform state-of-the-art score-based approaches (e.g., GOBNILP), and benchmark constraint-based or hybrid approaches, especially when the causal structure is relatively dense.