Research map / Probabilistic and scientific modeling / Bayesian optimization
Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CG-DCA, a row-and-column generation method for score-based Bayesian network structure learning that reformulates the pricing problem as difference-of-submodular minimization solved by DCA.
Problem
Score-based Bayesian network structure learning as an integer program has exponentially many variables (parent sets) and constraints (cluster constraints); the column generation pricing problem is a computational bottleneck, especially with MINLP formulations for Gaussian scores.
Approach
Rewrite the l0-penalized likelihood pricing objective as a difference of submodular functions and solve it inexactly with the Difference of Convex Algorithm (DCA) using Lovász extensions, embedded in a simultaneous row and column generation scheme with Gurobi.
Key results
- On Gaussian data with 3-hour limit, CG-DCA achieves BIC score gap of 0.00 for d=0.5 and generally lower average gaps than GOBNILP (e.g., (20,5000,2.0): 0.70% vs 4.77%).
- CG-DCA attains better average recall than PC, MMHC and GOBNILP on most Gaussian instances, with competitive SHD.
- On discrete datasets, CG-DCA is clearly worse than GOBNILP (e.g., ALARM SHD 35 vs 7, BIC gap 2.85% vs 0.00%) due to supermodular discrete penalty.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DCA pricing instead of MINLP pricing | Column generation for BNSL on Gaussian.test · Gaussian.test | runtime (seconds): 19.2 -> 1.2 seconds | Helped |
| Use DCA pricing instead of MINLP pricing | Column generation for BNSL on simulated Gaussian data · Gaussian (20 nodes, d=1, N=5,000) first pricing problem | runtime per node (seconds): 35.1 -> 0.3 second per node | Helped |
| Use CG-DCA instead of GOBNILP | BNSL score optimization on simulated Gaussian data · Gaussian datasets, including (15, 5000, d=0.5) and (20, 5000, d=2.0) | BIC score gap (%): 0.15 -> 0.00; 4.77 -> 0.70 | Helped |
| Use CG-DCA instead of GOBNILP | Gaussian Bayesian network structure recovery · Gaussian (15, 5000, d=0.5) | recall: 0.73 -> 0.80 | Helped |
| Use CG-DCA instead of GOBNILP | BNSL score optimization on discrete data · INSURANCE | BIC score gap (%): 0.00 -> 0.75 | Hurt |
| Use random initialization instead of hybrid initialization (ablation) | DCA pricing · Gaussian (15, 5000, d=1.0) | BIC score: -101954.63 -> -101939.75 | Helped |
| Use random initialization instead of hybrid initialization (ablation) | DCA pricing · Gaussian (15, 5000, d=1.0) | runtime (seconds): 25.76 -> 29.40 | Hurt |
| Use warm-start initialization instead of hybrid initialization (ablation) | DCA pricing · Gaussian (15, 5000, d=1.0) | BIC score: -101954.63 -> -101975.70 | Hurt |
| Use warm-start initialization instead of hybrid initialization (ablation) | DCA pricing · Gaussian (15, 5000, d=1.0) | runtime (seconds): 25.76 -> 4.49 | Helped |
| Switch from random to warm-start initialization after 50 parent sets (ablation) | DCA pricing · Gaussian simulated datasets | BIC score and runtime | Mixed |
Surprising findings
- Discrete BIC penalty is supermodular, making DCA ineffective and CG-DCA degrade on larger discrete networks.
- Warm-start initialization for DCA is fastest but yields the worst BIC scores, while random initialization gives best scores but is slowest.
Limitations
- Discrete-data performance is poor because the discrete BIC penalty is supermodular, limiting DCA effectiveness.
- DCA gives local solutions without global optimality guarantees; pricing is inexact.
- Experiments use only simulated linear Gaussian data for the main comparison and small discrete benchmarks.
Experimental setup
Datasets: simulated Gaussian BN data (n=15,20,25; N=5000,20000) LUCAS INSURANCE ALARM Gaussian.test (bnlearn)
Benchmarks: simulated Gaussian BN datasets LUCAS INSURANCE ALARM
Metrics: BIC score gap runtime precision recall SHD
Baselines: GOBNILP CG-MINLP HC stable-PC MMHC
Builds on: Cussens branch-and-price BNSL GOBNILP DCA Lovász extension
Closest papers by meaning
- Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network (AAAI 2025 · similarity 0.85)
- A Study of Bayesian Neural Network Surrogates for Bayesian Optimization (ICLR 2024 · similarity 0.84)
- Scores for Learning Discrete Causal Graphs with Unobserved Confounders (AAAI 2024 · similarity 0.84)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.84)
- Bayesian Optimization of Function Networks with Partial Evaluations (ICML 2024 · similarity 0.84)
- BayeSQP: Bayesian Optimization through Sequential Quadratic Programming (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.