Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization

2025/05/16 by Yiran Yang, Rui Chen, Yang, Yiran +1
Computer Science · Decision Sciences · #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2505.11089

openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider a score-based Integer Programming (IP) approach for solving the Bayesian Network Structure Learning (BNSL) problem. State-of-the-art BNSL IP formulations suffer from the exponentially large number of variables and constraints. A standard approach in IP to address such challenges is to employ row and column generation techniques, which dynamically generate rows and columns, while the complex pricing problem remains a computational bottleneck for BNSL. For the general class of ℓ₀-penalized likelihood scores, we show how the pricing problem can be reformulated as a difference of submodular optimization problem, and how the Difference of Convex Algorithm (DCA) can be applied as an inexact method to efficiently solve the pricing problems. Empirically, we show that, for continuous Gaussian data, our row and column generation approach yields solutions with higher quality than state-of-the-art score-based approaches, especially when the graph density increases, and achieves comparable performance against benchmark constraint-based and hybrid approaches, even when the graph size increases.

Citations

• Integer Programming for Causal Structure Learning in the Presence of Latent Variables
• Differentiable Causal Discovery Under Unmeasured Confounding
• DAG-GNN: DAG Structure Learning with Graph Neural Networks
• Causal Structure Learning
• Structure Learning in Graphical Modeling
• Order-independent constraint-based causal structure learning
• Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
• Bayesian network learning with cutting planes
• On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias
• A simple approach for finding the globally optimal Bayesian network structure
• Large-Sample Learning of Bayesian Networks is NP-Hard
• Causal Inference and Causal Explanation with Background Knowledge
• Learning Bayesian Networks: The Combination of Knowledge and Statistical Data
• Theory Refinement on Bayesian Networks
• Estimating the Dimension of a Model
• A Linear Programming Approach to the Cutting-Stock Problem

Related

• Solving Bayesian Network Structure Learning Problem with Integer Linear Programming
• Bayesian Network Structure Learning with Integer Programming: Polytopes,\n Facets, and Complexity
• Advances in Bayesian Network Learning using Integer Programming
• Bayesian network learning with cutting planes
• A Greedy, Flexible Algorithm to Learn an Optimal Bayesian Network Structure