Abstract
Learning the structure of Bayesian Networks (BNs) is a fundamental but NP-hard challenge in probabilistic graphical modeling. While Quadratic Unconstrained Binary Optimization (QUBO) offers a promising path for leveraging specialized annealing hardware, standard quadratization techniques suffer from excessive auxiliary variable requirements, creating a hardware capacity bottleneck. We present Decomposed Quadratization, a novel framework that significantly reduces the bit capacity needed for BN structure learning. By representing candidate parent sets as unions of minimal subsets, our method achieves orders-of-magnitude reductions in variable counts. Experimental results on benchmark datasets demonstrate that our approach enables the optimization of large-scale networks (over 200 nodes) on current hardware, outperforming traditional algorithms and previous state-of-the-art QUBO formulations in both efficiency and score maximization.
Introduction
A Bayesian Network (BN) represents a set of variables and their conditional dependencies via a Directed Acyclic Graph (DAG). Learning the optimal structure of such a network from data—known as score-based learning—is notoriously difficult. Researchers have recently turned to Quadratic Unconstrained Binary Optimization (QUBO) to solve this, as it is the native language of specialized annealing machines like the D-Wave quantum annealer and the Fujitsu Digital Annealer.
However, a significant hurdle remains: "bit capacity." Converting high-degree scoring functions into the quadratic form required by these machines (quadratization) typically necessitates a massive number of auxiliary binary variables. For moderately sized networks, the required bit count often exceeds the physical limits of current hardware, stalling the practical application of quantum-inspired optimization in this domain.
Methodology
Decomposed Quadratization Framework
The core contribution of this work is a two-pronged strategy to streamline QUBO formulations. Traditionally, quadratization involves adding one new auxiliary variable for every high-degree term in a polynomial. This 1-to-1 mapping is often redundant. The authors propose a more flexible "decomposed" framework where the mapping between primary and auxiliary variables is optimized to exploit overlaps between terms, resulting in a more compact representation.
Candidate Parent Subsets
The primary application of this framework is the identification of Candidate Parent Subsets. Instead of assigning a unique binary variable to every possible parent set for a given node, the method identifies a minimal collection of subsets. Any specific parent set can then be represented as the union of at most two of these subsets.
To find the optimal, minimal collection of these subsets, the researchers developed an Integer Linear Programming (ILP) approach. This allows the quadratic objective function to "reconstruct" the full parent sets using significantly fewer total bits, effectively shrinking the problem size without losing information.
Experimental Evaluation
Datasets and Hardware
The researchers evaluated the proposed method across 16 benchmark instances, categorized into:
- Discrete Bayesian Networks: Including standard benchmarks such as alarm (37 nodes), hepar2 (70 nodes), and andes (223 nodes).
- Frequent Item Set Mining Datasets: Such as chess (75 nodes) and connect (129 nodes).
The optimization was performed using the Fujitsu Digital Annealer, which features a 100,000-bit capacity and a fully-coupled architecture, allowing for efficient exploration of the solution space.
Key Results and Discussion
Bit Efficiency and Scalability
The "IP + algorithm 2" approach consistently produced the smallest number of binary variables across all test cases. The reduction in bits is often an order of magnitude better than previous methods. For instance, in the andes dataset (223 variables), the proposed method required approximately 31,000 bits, whereas the previous state-of-the-art (O’Gorman et al.) would have required nearly 93,000 bits. This efficiency enabled the encoding of networks with over 200 variables onto a single annealing chip—a feat previously considered infeasible.
Score Maximization
In head-to-head trials, the Digital Annealer utilizing the new formulation achieved the highest scores on almost all medium-to-large instances. It outperformed established algorithms such as Acyclic Selection Ordering (ASO) and GOBNILP, demonstrating that the compact formulation does not compromise the quality of the learned structure.
Limitations and Future Work
Despite its success, the method faces three primary challenges:
- Pre-processing Overhead: The ILP required to find optimal subsets can be computationally expensive for very large networks.
- Energy Landscape Complexity: Representing a parent set with multiple bits can make the optimization landscape harder to navigate for simple search moves, as transitions may require flipping multiple bits simultaneously.
- Term Density: Reducing variables can increase the number of quadratic interactions, which may impact performance on hardware with limited connectivity.
Future research will focus on optimizing the pre-processing phase and extending decomposed quadratization to other complex optimization domains beyond Bayesian networks.
Conclusion
Decomposed Quadratization represents a significant step forward in making Bayesian Network structure learning viable for annealing hardware. By breaking the traditional 1-to-1 constraint of quadratization and utilizing candidate parent subsets, this method drastically lowers the barrier to entry for solving high-dimensional probabilistic modeling problems on current and near-term specialized hardware.
Summary updated