Research map / Probabilistic and scientific modeling / Bayesian optimization
Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network
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 decomposed quadratization with candidate parent subsets to encode score-based Bayesian network structure learning as a QUBO using fewer binary variables, and runs it on the Fujitsu Digital Annealer.
Problem
Quadratization of higher-degree pseudo-Boolean objectives for QUBO requires too many auxiliary binary variables, which is infeasible for score-based Bayesian network structure learning on annealing hardware with limited bit capacity.
Approach
Decompose quadratization into an auxiliary-variable mapping g1 (auxiliary bits to primary bits) and a quadratic objective g2, and encode candidate parent subsets (unions of two subsets generate candidate parent sets) so that each parent set is captured by at most two active binary variables; an ILP reduces the number of candidate parent subsets.
Key results
- On the 16 instances, the IP + decomposed approach needs far fewer binary variables than the quadratization baseline (e.g., alarm m=4: 1373 vs 3982; andes m=3: 31162 vs 92838).
- Some quadratization instances with m=3 exceed the Digital Annealer's 100K bit capacity while the proposed formulation fits.
- Digital Annealer with the proposed QUBO achieved the highest BDeu score in most medium-to-large instances (e.g., 5/5 trials on chess m=3, pathfinder m=3, andes m=3), outperforming HCS, SAO, ASO, and GOB in those cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Digital Annealer with the proposed QUBO formulation instead of score-based baselines | Bayesian network structure learning · Most medium-sized instances, including chess, pathfinder, mushroom, connect (m=2), munin1, and andes | highest-score trials | Helped |
| Use Digital Annealer with the proposed QUBO formulation instead of GOBNILP | Bayesian network structure learning · alarm, barley, hailfinder, and hepar2 (m=4) | highest-score trials: 0 vs 5 | Hurt |
| Optimize candidate parent subsets with the proposed reduction algorithm rather than IP only (ablation) | QUBO formulation · Instances with larger parent set size | number of binary variables | Helped |
| Use decomposed quadratization with candidate parent subsets instead of conventional quadratization | Bayesian network QUBO formulation · Bayesian network structure learning instances | number of binary variables | Helped |
| Use Digital Annealer rather than classical simulated annealing or Gurobi on the same QUBO | Proposed QUBO formulation · Score maximization | highest-score trials | Helped |
| Use the proposed candidate-parent-subset encoding for larger networks | QUBO formulation · Larger Bayesian networks | execution time | Hurt |
Surprising findings
- Formation time of candidate parent subsets and the IP step dominated execution time, making the QUBO construction a bottleneck for larger networks.
- GOBNILP found optimal networks for smaller instances, outperforming the QUBO-based annealer there.
Limitations
- Execution time to incorporate candidate parent subsets into the objective is a bottleneck for larger problems.
- Two-bit parent set encoding can make 1-bit flip search need up to four bit inversions; more QUBO terms increase minor-embedding overhead.
Experimental setup
Datasets: bnlearn Bayesian network repository (alarm, barley, hailfinder, hepar2, win95pts, pathfinder, munin1, andes) FIMI frequent item set datasets (chess, mushroom, connect)
Benchmarks: 16 Bayesian network structure learning instances (37 to 223 variables)
Metrics: number of binary variables execution time BDeu score (number of trials achieving highest score)
Baselines: quadratization-based QUBO (Mücke et al.) hill climbing search (HCS) simulated annealing over ordering space (SAO) acyclic selection ordering-based search (ASO) GOBNILP Gurobi QUBO solver (GOQ) classical simulated annealing (SAQ)
Builds on: quadratization BDeu score Gurobi
Closest papers by meaning
- BayeSQP: Bayesian Optimization through Sequential Quadratic Programming (NeurIPS 2025 · similarity 0.85)
- Bayes-optimal learning of an extensive-width neural network from quadratically many samples (NeurIPS 2024 · similarity 0.85)
- Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization (NeurIPS 2025 · similarity 0.85)
- A Study of Bayesian Neural Network Surrogates for Bayesian Optimization (ICLR 2024 · similarity 0.84)
- Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization (ICLR 2024 · similarity 0.84)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · 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.