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

arXiv: https://arxiv.org/abs/2505.11089 · HTML: https://mlsanity.com/paper/2505.11089/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 50 references that are in the map.
- First posted on arXiv 16 May 2025.

## Builds on (most cited first, 10 of 10)

- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Structure Learning](https://mlsanity.com/paper/1706.09141/) (2017)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Differentiable Causal Discovery Under Unmeasured Confounding](https://mlsanity.com/paper/2010.06978/) (2020)
- [Theory Refinement on Bayesian Networks](https://mlsanity.com/paper/1303.5709/) (2013)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Integer Programming for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2102.03129/) (2021)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)

## Abstract (arXiv)

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 ℓ0-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.