Bayesian Network Structure Learning using Digital Annealer
Year: 2021

Abstract:
Annealing processors, which efficiently solve a quadratic unconstrained binary 1 optimization (QUBO), are a potential breakthrough in improving the accuracy 2 of score-based Bayesian network structure learning. However, currently, the bit 3 capacity of an annealing processor is very limited. To utilize the power of an4 nealing processors, it is necessary to encode score-based learning problems into 5 QUBO within the upper bound of bits. In this paper, we propose a novel approach 6 with direct encoding of candidate parent sets in the form of Cartesian products. 7 Experimental results on benchmark networks with 27 to 70 variables show that 8 our approach requires lesser bits than the bit capacity of the second-generation 9 Fujitsu digital annealer, a fully coupled annealing processor developed by with 10 semiconductor technology. Moreover, we demonstrate that the digital annealer 11 with our conversion method consistently outperforms the state-of-the-art heuristic 12 algorithms on the benchmark networks. 13

Annealing processors, which efficiently solve a quadratic unconstrained binary1 optimization (QUBO), are a potential breakthrough in improving the accuracy2 of score-based Bayesian network structure learning. However, currently, the bit3 capacity of an annealing processor is very limited. To utilize the power of an-4 nealing processors, it is necessary to encode score-based learning problems into5 QUBO within the upper bound of bits. In this paper, we propose a novel approach6 with direct encoding of candidate parent sets in the form of Cartesian products.7 Experimental results on benchmark networks with 27 to 70 variables show that8 our approach requires lesser bits than the bit capacity of the second-generation9 Fujitsu digital annealer, a fully coupled annealing processor developed by with10 semiconductor technology. Moreover, we demonstrate that the digital annealer11 with our conversion method consistently outperforms the state-of-the-art heuristic12 algorithms on the benchmark networks.13
1 Introduction14
A Bayesian network is a probabilistic graphical model that represents the structure of a joint probabil-15 ity distribution among random variables in a directed acyclic graph (DAG) [Pearl, 1988]. One class16 of associated computational problems is learning the structure of a Bayesian network from data. We17 focus on score-based Bayesian network structure learning for finding the DAG with a maximal score18 that depends on the data [Cooper and Herskovits, 1992, Cowell, 2001].19
The Bayesian network learning problem is NP-hard [Chickering et al., 2004]; therefore, the standard20 methodology is using heuristic approaches. Many algorithms have been proposed to improve the21 accuracy and to reduce the running time. A search over the space of orderings [Teyssier and Koller,22 2005, Scanagatta et al., 2015] is one of the most successful heuristic approaches.23
Annealing processors may contribute to finding a high-scoring network structure in a realistic24 timeframe. An annealing processor is expected to be an alternative hardware to von Neumann25 computers for quadratic unconstrained binary optimization (QUBO) problems. In particular, it is26 reported that complementary metal oxide semiconductor (CMOS) annealing processors already27 outperform conventional computers on the speed of solving max-cut problems [Gyoten et al., 2018].28
We note that the bit capacity of an annealing processor is currently limited. Therefore, we need an29 efficient conversion method of Bayesian network structure learning into QUBO within the limited30 bits. Additionally, it is also important to show the lower bounds of penalty coefficients because the31 precision for the biases and variable couplers is limited.32
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Annealing processors are classified into the nearest neighbor type and the fully connected type33 [Yamamoto, 2020]. While the coupling nodes of a nearest neighbor annealing processor is limited to34 only between adjacent nodes, the coupling exists between arbitrary nodes of a fully coupled annealing35 processor. Though the scalability of nearest neighbor annealing processors is high, it is necessary to36 consider the additional bits for minor embedding [Choi, 2008, 2010].37
O’Gorman et al. 2014 proposed a method to convert score-based Bayesian network structure learning38 into QUBO that requires O(n2) bits for n random variables and a maximum parent set size m = 2.39 They also demonstrated the sufficient lower bounds of penalty coefficients. However, when m ≥ 3,40 the number of necessary auxiliary variables for a quadratization [Boros and Gruber, 2014] is at most41 O(n(n− 1)m2 ). This is a significant disadvantage for the current limited bit capacity of annealing42 processors.43
In this study, we propose an efficient conversion method based on the advanced identification of44 candidate parent sets and their representation in the form of Cartesian products. We also provide a45 greedy algorithm to decompose the candidate parent sets into the form of Cartesian products and46 prove the sufficient lower bounds of penalty coefficients.47
Experimental results on benchmark networks with 27 to 70 variables show that our conversion method48 reduces the required bits significantly in comparison to the previous work [O’Gorman et al., 2014].49 Our approach allows us to utilize the power of the second generation Fujitsu digital annealer, a fully50 coupled CMOS annealing processor [Aramon et al., 2019]. We demonstrate that the digital annealer51 consistently outperforms the ordering space search algorithms on the benchmark networks.52
2 Background53
2.1 Score-based Bayesian Network Structure Learning54
The goal of score-based Bayesian network structure learning is to find a DAG with maximal score.55 Given to random variablesX = (Xi)ni=1 and a complete data set ofN instancesD = {D1, · · · , DN},56 we optimize the parent set Πi of each random variable,57
Π∗1, · · · ,Π∗n = arg min Π1,··· ,Πn⊂X G∈DAG n∑ i=1 − logS(i)(Πi | D), (1)
where G = (V, E),V = {1, · · · , n}, E = {(j, i) | j, i ∈ {1, · · · , n}, Xj ∈ Πi}, and Si : Πi → R is58 a local score function corresponding to Xi. The Bayesian Dirichlet equivalent uniform (BDeu) score59 [Buntine, 1991] is one of the commonly used scores,60
S (i) BDeu(Πi | D) ≡ βi∏ j=1
Γ(αi,j)
Γ(Ni,j + αi,j) γi∏ k=1 Γ(Ni,j,k + αi,j,k) Γ(αi,j,k) , (2)
where N = ∑βi j=1Ni,j , Ni,j = ∑γi k=1Ni,j,k, αi,j = ∑γi k=1 αi,j,k, βi is the number of joint states of61 Πi, γi is the number of states of Xi, Ni,j,k is the number of cases of the parent set Πi in its j-th state62 and Xi in its k-th state, αi,j,k = αβiγi is the hyperparameter of the Dirichlet function, and 0 < α ∈ R63 is called equivalent sample size [Heckerman et al., 1995a].64
2.2 Hamiltonian65
The Hamiltonian, which is the objective function of an annealing processor, is a quadratic pseudo-66 Boolean function,67
H(σ) = ∑ i∈VAP hiσi + ∑ (i,j)∈EAP Ji,jσiσj , (3)
where σ = (σi) |VAP| i=1 ∈ B|VAP|, the biases hi ∈ R for all i ∈ VAP, the couplers Ji,j ∈ R for all68 (i, j) ∈ EAP, and the graph GAP = (VAP, EAP). Higher degree problems are reformed into quadratic69 ones using auxiliary variables. This reformulation is called quadratization.70
Definition 1. If a quadratic polynomial function g(v,h) is a quadratization of a pseudo-Boolean71 function f(v), then f(v) = minh∈BJ g(v,h) for all v ∈ BI .72
Anthony et al. 2016 proved that every pseudo-Boolean function of I variables and of degree K has73 a quadratization involving at most O(I K2 ) auxiliary variables. In particular, at most O(2 I2 ) when74 K = I . It is well known that every pseudo-Boolean function can be uniquely represented as a75 multilinear polynomial in its variables [Boros and Hamme, 2002].76
2.3 Basic Conversion of Score-based Bayesian Network Structure Learning77
Using n(n − 1) bits to encode the paths into d = ((dj,i)1≤j≤n,j 6=i)ni=1 ∈ Bn(n−1) (dj,i = 1 if78 Xj is the parent of Xi, dj,i = 0 otherwise) and ( n 2 ) bits to encode the topological orders into79
r = (ri,j)1≤i<j≤n ∈ B( n 2) (ri,j = 0 if the order of Xi is higher than Xj , ri,j = 1 otherwise), it is80 possible to represent eq. (1) on the Hamiltonian,81
Htotal(d, r) ≡ n∑ i=1 H(i)score(d·,i) +Hcycle(d, r). (4)
The states of d·,i are mapped one-to-one to the states of Πi. Let Πi = π(i)(d·,i) for all 1 ≤ i ≤ n.82 The local score of the Hamiltonian is83
H(i)score(d·,i) ≡ − logS(i)(π(i)(d·,i) | D) + logS(i)(φ | D), (5)
for all 1 ≤ i ≤ n. The score function has a quadratization involving at most O(n2n−12 ) auxiliary84 variables. O’Gorman et al. 2014 added the maximum parent set size constraint to the Hamiltonian.85 In this case, the number of auxiliary variables is at most O(n(n− 1)m2 ). The cycle constraint of the86 Hamiltonian consists of the topological order constraint and the consistency constraint,87
Hcycle(d, r) ≡ ∑
1≤i<j<k≤n
δ1R(ri,j , rj,k, ri,k) + ∑
1≤i<j≤n
δ2(di,jri,j + dj,i(1− ri,j)), (6)
where R(r1, r2, r3) = r1r2(1− r3) + (1− r1)(1− r2)r3 for all r1, r2, r3 ∈ B. When the penalty88 coefficients 0 < δ1, δ2 ∈ R are sufficiently large, the DAG constraint is satisfied indirectly through89 the relationship of the paths d and the topological order r. If it holds that90
max{0, max 1≤j∗,i∗≤n j∗ 6=i∗ max d·,i∗∈B n−1
dj∗,i∗=1
(H(i ∗) score(d (j∗,i∗) ·,i∗ )−H (i∗) score(d·,i∗))} < δ1 < δ2 n− 2 , (7)
then there is no cycle on the paths of the ground state, where d(j ∗,i∗) = ((dj,i) (j∗,i∗) 1≤j≤n,j 6=i) n i=1,91
d (j∗,i∗) j,i = 0 if (j, i) = (j ∗, i∗), d(j ∗,i∗)
j,i = dj,i otherwise. The computational cost to obtain the left92 side of eq. (7) is at most O(nm+1). In particular, at most O(n22n−2) when m = n− 1.93
3 Candidate Parent Set Decomposition94
Parent set identification is a major technique to narrow the search space of structure optimization,95 based on the relationship between parent sets and local scores under the DAG constraints [de Campos96 and Ji, 2011, Correia et al., 2020]. The collection of candidate parent sets of a random variable Xi is97 {W ⊆ X \ {Xi} |W ′ ⊂ W ⇒ S(i)(W ′ | D) < S(i)(W | D)}. To reduce the required bits of the98 score component of the Hamiltonian, we propose an efficient conversion method with the parent set99 identification. We directly encode the candidate parent sets instead of using the paths d.100
Moreover, we decompose the candidate parent sets (Wh,i)λih=0 of each random variable into the form101 of Cartesian products as follows:102
1. Decompose (Wh,i)λih=0 into (Wh,i ∩ Zi) λi h=0, (Wh,i ∩ (X \ Zi)) λi h=0,103 2. Remove duplicates in the elements of (Wh,i ∩ Zi)λih=0, (Wh,i ∩ (X \ Zi)) λi h=0,104
3. Store (Wh,i ∩ Zi) λ1,i h=0, (Wh,i ∩ (X \ Zi)) λ2,i h=0 in (Uh,i) λ1,i h=0, (Vh,i) λ2,i h=0,105
where Zi ⊆ ∪λih=0Wh,i,W0,i = U0,i = V0,i = φ, λi, λ1,i, λ2,i ∈ N ∪ {0} for all 1 ≤ i ≤ n. There106 is a clear relationship,107
{W0,i, · · · ,Wλi,i} ⊆ {U ∪ V | (U, V ) ∈ {U0,i, · · · , Uλ1,i,i} × {V0,i, · · · , Vλ2,i,i}}, (8)
for all 1 ≤ i ≤ n. Here, given that the Hamiltonian is a quadratic pseudo-Boolean function, we can108 represent the score against Uh,i∪Vh′,i by allocating Uh,i, Vh′,i to two bits on the Hamiltonian. There-109 fore, it is possible to encode the candidate parent sets into the Hamiltonian using (Uh,i) λ1,i h=0, (Vh,i) λ2,i h=0.110
The number of required bits of the score component of the Hamiltonian is ∑n i=1(λ1,i + λ2,i).111 Example 1. An example of the candidate parent sets in the form of Cartesian products as follows:112
X = {X1, X2, X3, X4}, Zi = {X1, X2}, λi = 5, λ1,i = 2, λ2,i = 1 (Wh,i) λi h=0 = (φ, {X1}, {X1, X2}, {X3, X4}, {X1, X3, X4}, {X1, X2, X3, X4}), (Wh,i ∩ Zi)λih=0 = (φ, {X1}, {X1, X2}, φ, {X1}, {X1, X2}), (Wh,i ∩ (X \ Zi))λih=0 = (φ, φ, φ, {X3, X4}, {X3, X4}, {X3, X4}), (Uh,i) λ1,i h=0 = (φ, {X1}, {X1, X2}), (Vh,i) λ2,i h=0 = (φ, {X3, X4}).
We optimize Zi ⊆ ∪λih=0Wh,i to minimize λ1,i + λ2,i. However, it is often infeasible to search all113 elements of the power set P(∪λih=0Wh,i). Therefore, we heuristically search Zi adding elements one114 by one, as algorithm 1. The computational cost is at most O(λ3i ) for all 1 ≤ i ≤ n.
Algorithm 1 Greedy Candidate Parent Set Decomposition
1: Input: (Wh,i)λih=0 Output: Z Initialize: λ← λi, Z ′ ← φ,Z ← φ. 2: for d = 1 to | ∪λih=0 Wh,i| − 1 do 3: for X in ∪λih=0Wh,i \ Z do 4: if λ1,i + λ2,i < λ for Zi = Z ∪ {X} then λ← λ1,i + λ2,i, Z ′ ← Z ∪ {X}. 5: if Z 6= Z ′ then Z ← Z ′ else break
115 Example 2. An example of the bit reduction flow of algorithm 1 is as follows:116
Zi = φ, λ1,i = 0, λ2,i = 5 : (φ)× (φ, {X1}, {X1, X2}, {X3, X4}, {X1, X3, X4}, {X1, X2, X3, X4}), Zi = {X1}, λ1,i = 1, λ2,i = 3 : (φ, {X1})× (φ, {X2}, {X3, X4}, {X2, X3, X4}), Zi = {X1, X2}, λ1,i = 2, λ2,i = 1 : (φ, {X1}, {X1, X2})× (φ, {X3, X4}).
4 Efficient Conversion of Score-based Bayesian Network Structure Learning117
We make (Uh,i) λ1,i h=0, (Vh,i) λ2,i h=0 correspond to (ph,i) λ1,i h=0, (qh,i) λ2,i h=0 one-to-one, where ph,i, qh′,i ∈ B118 for all 0 ≤ h ≤ λ1,i, 0 ≤ h′ ≤ λ2,i, 1 ≤ i ≤ n. To identify the parent sets, we use the one-to-one119 correspondence constraint that ∑λ1,i h=0 ph,i = ∑λ2,i h=0 qh,i = 1 for all 1 ≤ i ≤ n. The Hamiltonian120 consists of the score component, the one-to-one correspondence constraint, and the cycle constraint,121
H∗total(p, q, r) ≡ n∑ i=1 (H∗(i)score(p·,i, q·,i) +H ∗(i) one (p·,i, q·,i)) +H ∗ cycle(p, q, r), (9)
where p = ((ph,i) λ1,i h=0) n i=1, q = ((qh,i) λ2,i h=0) n i=1. Under the one-to-one correspondence constraint,122 we can represent the paths among random variables indirectly using p, q without additional auxiliary123 variables,124
d∗j,i ≡ ∑
1≤h≤λ1,i Xj∈Uh,i
ph,i + ∑
1≤h≤λ2,i Xj∈Vh,i
qh,i, (10)
for all 1 ≤ j, i ≤ n. Figure 1 is an example of bit allocation using our conversion method. The125 number of bits required in our conversion method is ∑n i=1(λ1,i + λ2,i) + ( n 2 ) . Note that we do not126 directly encode p0,i, q0,i on the Hamiltonian.127
Score Component. The local score component of the Hamiltonian is128
H∗(i)score(p·,i, q·,i) ≡ λ1,i∑ h=1 s1,h,iph,i + λ2,i∑ h=1 s2,h,iqh,i + λ1,i∑ h=1 λ2,i∑ h′=1 th,h′,iph,iqh′,i, (11)
for all 1 ≤ i ≤ n. We can get these coefficients by solving simultaneous equations under the129 one-to-one correspondence constraint, s1,h,i = − logS(i)(Uh,i | D) + logS(i)(φ | D), s2,h,i =130 − logS(i)(Vh,i | D) + logS(i)(φ | D), th,h′,i = − logS(i)(Uh,i ∪ Vh′,i | D) + logS(i)(Uh,i | D) +131 logS(i)(Vh′,i | D)− logS(i)(φ | D).132
One-to-One Correspondence Constraint. We penalize the connection among bits to select each133 element from (Uh,i) λ1,i h=0, (Vh,i) λ2,i h=0,134
H∗(i)one (p·,i, q·,i) ≡ ∑
1≤h<h′≤λ1,i
ξ1,iph,iph′,i + ∑
1≤h<h′≤λ2,i
ξ2,iqh,iqh′,i, (12)
for all 1 ≤ i ≤ n, where the penalty coefficient 0 < ξ1,i, ξ2,i ∈ R. If ξ1,i, ξ2,i is sufficient large,135 ∑λ1,i h=0 ph,i = ∑λ2,i h=0 qh,i = 1 is induced indirectly.136
Cycle Constraint. Compared to eq. (6), the cycle constraint of the Hamiltonian is137 H∗cycle(p, q, r) ≡ ∑
1≤i<j<k≤n
δ∗1R(ri,j , rj,k, ri,k) + ∑
1≤i<j≤n
δ∗2(d ∗ i,jri,j + d ∗ j,i(1− ri,j)), (13)
where the penalty coefficients 0 < δ∗1 , δ ∗ 2 ∈ R. By setting δ∗1 , δ∗2 appropriately, we can prevent the138 cycle from occurring.139
5 Sufficient Lower Bounds of Penalty Coefficients140
We demonstrate the sufficient lower bounds of penalty coefficients. The basic idea is that we find the141 range of penalty coefficients so that the change in return value of the Hamiltonian is negative when142 the input state changes to the state we desire to induce.143
One-to-One Correspondence Constraint. We consider to decrease the value of ∑λ1,i∗ h=1 ph,i∗ by144
one until it reaches 1. In the case of ph∗,i∗ = 1, ∑λ1,i∗ h=1 ph,i∗ > 1, it holds that H ∗ total(p, q, r) −145
H∗total(p (h∗,i∗), q, r) ≥ ξ1,i∗ + s1,h∗,i∗ + ∑λ2,i h=1 th∗,h,i∗qh,i∗ , where p (h∗,i∗) = ((p (h∗,i∗) h,i ) λ1,i h=0) n i=1,146
and p(h ∗,i∗)
h,i = 0 if (h, i) = (h ∗, i∗), p(h ∗,i∗) h,i = ph,i otherwise. Considering the case where p and q147 are swapped in the above, if ξ1,i, ξ2,i satisfy that148
max 0≤h≤λ1,i (−s1,h,i − λ2,i∑ h′=1 min{0, th,h′,i})) < ξ1,i, (14)
max 0≤h≤λ2,i (−s2,h,i − λ1,i∑ h′=1 min{0, th′,h,i})) < ξ2,i, (15)
for all 1 ≤ i ≤ n, then the grand state does not violate the one-to-one correspondence constraint.149 The computational cost to obtain the left side of eq. (14) and eq. (15) is at most O(λ1,iλ2,i) for all150 1 ≤ i ≤ n.151
Cycle Constraint. We consider four patterns of (ri∗,j∗ , d∗j∗,i∗ , d∗i∗,j∗) violating the consistency152 constraint. It is assumed that Xj∗ ∈ Uh∗,i∗ , Xj∗ /∈ Uh∗∗,i∗ ⊂ Uh∗,i∗ , ph∗,i∗ = 1, ph∗∗,i∗ = 0.153 In the case of (0, 1, 0), it holds that H∗total(p, q, r) − H∗total(p, q, r(i
∗,j∗)) ≥ δ∗2 − (n − 2)δ∗1 ,154 where r(i ∗,j∗) = (r (i∗,j∗) i,j )1≤i<j≤n, and r (i∗,j∗) i,j = 1 − ri,j if (i, j) = (i∗, j∗), r (i∗,j∗) i,j = ri,j155 otherwise. Similarly, it is possible to consider the case of (1, 0, 1). In the case of (0, 1, 1),156 it holds that H∗total(p, q, r) − H∗total(p(h ∗,h∗∗,i∗), q, r) ≥ δ∗2 + s1,h∗,i∗ + ∑λ2,i h=1 th∗,h,i∗qh,i∗ −157
s1,h∗∗,i∗ − ∑λ2,i h=1 th∗∗,h,i∗qh,i∗ , where p (h∗,h∗∗,i∗) = ((p (h∗,h∗∗,i∗) h,i ) λ1,i h=0) n i=1, and p (h∗,h∗∗,i∗) h,i = 0158
if (h, i) = (h∗, i∗), p(h ∗,h∗∗,i∗)
h,i = 1 if (h, i) = (h ∗∗, i∗), p(h ∗,h∗∗,i∗) h,i = ph,i otherwise. Sim-159 ilarly, it is possible to consider the case of (1, 1, 1). These results suggest the relationship of160 δ∗1 , δ ∗ 2 to induce the consistency constraint. Here, based on theorem 1, we consider a strategy161 to repeat picking up one element from r and switching its value until Htrans(r) = 0. It is as-162 sumed that Htrans(r) > Htrans(r(i
∗,j∗)). In the case of (1, 1, 0), it holds that H∗total(p, q, r) −163 H∗total(p (h∗,h∗∗,i∗), q, r(i ∗,j∗)) ≥ δ∗1+s1,h∗,i∗+ ∑λ2,i h=1 th∗,h,i∗qh,i∗−s1,h∗∗,i∗− ∑λ2,i h=1 th∗∗,h,i∗qh,i∗ .164 Similarly, it is possible to consider the case of (0, 0, 1). In the case of (1, 0, 0) or (0, 0, 0), it holds165 that H∗total(p, q, r) − H∗total(p, q, r(i
∗,j∗)) ≥ δ∗1 . These results suggest the lower bound of δ∗1 to166 induce the topological order constraint. Considering the case where p and q are swapped in the167 above, if δ∗1 , δ ∗ 2 satisfy that168
max 1≤i≤n
max{η1,i, η2,i} < δ∗1 < δ∗2
n− 2 , (16)
η1,i ≡ max 1≤j≤n max 0≤h≤λ1,i Xj∈Uh,i max 0≤h′≤λ1,i
Xj /∈Uh′,i⊂Uh,i
max 0≤h′′≤λ2,i
(−s1,h,i − th,h′′,i + s1,h′,i + th′,h′′,i),
η2,i ≡ max 1≤j≤n max 0≤h≤λ2,i Xj∈Vh,i max 0≤h′≤λ2,i
Xj /∈Vh′,i⊂Vh,i
max 0≤h′′≤λ1,i
(−s2,h,i − th′′,h,i + s2,h′,i + th′′,h′,i),
for n ≥ 3, then the grand state does not violate the cycle constraint under the one-to-one cor-169 respondence constraint. The computational cost to obtain the left side of eq. (16) is at most170 O( ∑n i=1 nλ1,iλ2,i(λ1,i + λ2,i)).171
Theorem 1. If it holds that Htrans(r) ≡ ∑
1≤i<j<k≤nR(ri,j , rj,k, ri,k) > 0, then there exists172 at least one index pair 1 ≤ i∗ < j∗ ≤ n which satisfy Htrans(r) > Htrans(r(i
∗,j∗)), where173 R(r1, r2, r3) = r1r2(1− r3) + (1− r1)(1− r2)r3 for all r1, r2, r3 ∈ B, r = (ri,j)1≤i<j≤n ∈ B( n 2),174
r(i ∗,j∗) = (r (i∗,j∗) i,j )1≤i<j≤n, and r (i∗,j∗) i,j = 1− ri,j if (i, j) = (i∗, j∗), r (i∗,j∗) i,j = ri,j otherwise.175
Table 1: The benchmark networks from Bayesian network repository.
Name n m
∑n
i=1 |Πi|
∑n
i=1 βi(γi − 1)
∑n
i=1 λi *
N = 100 N = 1000 N = 10000
insurance 27 3 52 984 353 883 4036 water 32 5 66 10083 165 216 735 alarm 37 4 46 509 1829 2272 9081 barley 48 4 84 114005 181 310 1552 hailfinder 56 4 66 2656 144 692 4277 hepar2 70 6 123 1453 4837 665 4782
* The average for 10 simulated datasets.
Proof. It does not lose the generality by considering the case of (r1,2, r2,3, r1,3) = (1, 1, 0). Here, it176 holds that R(r1,2, r2,3, r1,3)−R(1− r1,2, r2,3, r1,3) +R(r1,2, r2,3, r1,3)−R(r1,2, 1− r2,3, r1,3) +177 R(r1,2, r2,3, r1,3)−R(r1,2, r2,3, 1− r1,3) = 3. Additionally, it holds that R(r1,2, r2,i, r1,i)−R(1−178 r1,2, r2,i, r1,i)+R(r2,3, r3,i, r2,i)−R(1−r2,3, r3,i, r2,i)+R(r1,3, r3,i, r1,i)−R(1−r1,3, r3,i, r1,i) =179 0 for all 3 < i. Therefore, it holds that Htrans(r)−Htrans(r(1,2)) +Htrans(r)−Htrans(r(2,3)) +180 Htrans(r)−Htrans(r(1,3)) = 3. From this result, it holds that Htrans(r)−Htrans(r(i
∗,j∗)) > 0 for181 at least one index pair (i∗, j∗) ∈ {(1, 2), (2, 3), (1, 3)}.182
6 Experimental Results183
To validate the performance of our approach, we use 10 simulated datasets for each instance size184 N = 100, 1000, 10000 and each benchmark network. The benchmark networks are discrete networks185 from Bayesian network repository 1. The score function is the BDeu score with α = 1. It is often186 infeasible to identify exact candidate parent sets by searching the power set P(X \{Xi}) in a realistic187 timeframe. We use the candidate parent sets from algorithm 2. Note that the candidate parent sets188 depend on the heuristic search algorithms, but we do not focus on their performance in this study.189 Table 1 displays the information of benchmark networks. The code to replicate each experiment in190 this paper is available 2.191
Algorithm 2 Greedy Candidate Parent Set Identification 1: Input: D, i, m Output: L Initialize: L ← {φ},L′ ← {φ},L′′ ← φ 2: for d = 1 to m do 3: for W in L′ do 4: for X in X \ {Xi} \W do 5: if Si(W ′ | D) < Si(W ∪ {X} | D) for all W ′ ⊂W ∪ {X},W ′ ∈ L then 6: L′′ ← L′′ ∪ {W ∪ {X}}. 7: if L′′ 6= φ then L ← L ∪ L′′,L′ ← L′′,L′′ ← φ else break 8: for W in L do 9: if there exist W ′ ⊂W that satisfies Si(W | D) ≤ Si(W ′ | D) then L ← L \ {W}.
6.1 Number of Required Bits for Score Component192
In comparison to the existing method [O’Gorman et al., 2014], we reduce the number of required bits193 for the score component by encoding the candidate parent sets directly. While ∑n i=1 λi candidate194 parent sets is encoded in our approach, n(n−1) paths plus at mostO(n(n−1)m2 ) auxiliary variables195 for m > 2 in the existing method. The left side of table 2 shows the reduction rate of the number of196 required bits for the score component. Moreover, we reduce the number of required bits for the score197 component to ∑n i=1(λ1,i + λ2,i) by decomposing the candidate parent sets in the form of Cartesian198
1https://www.bnlearn.com/bnrepository/ 2See supplemental material.
Table 2: The reduction rate of the number of required bits for score component.
Name
∑n
i=1 λi / n(n− 1) m 2 *
∑n
i=1(λ1,i + λ2,i) /
∑n
i=1 λi *
N = 100 N = 1000 N = 10000 N = 100 N = 1000 N = 10000
insurance 0.09873 0.24677 1.12742 0.61367 0.47285 0.32476 water 0.00097 0.00126 0.00429 0.72680 0.70588 0.44014 alarm 0.03814 0.04738 0.18938 0.45332 0.35537 0.21617 barley 0.00171 0.00292 0.01464 0.76717 0.75538 0.54149 hailfinder 0.00085 0.00409 0.02525 0.82773 0.60178 0.33365 hepar2 0.00021 0.00003 0.00021 0.49694 0.63346 0.31284
* The average ratio for 10 simulated datasets.
Table 3: The number of required bits for fully coupled and nearest neighbor annealing processors.
Name
∑n
i=1(λ1,i + λ2,i) +
(
n 2
)
* ∑n
i=1(λ1,i + λ2,i)(λ1,i + λ2,i + 1) +
(
n 2
)
*
N = 100 N = 1000 N = 10000 N = 100 N = 1000 N = 10000
insurance 566 767 1661 3375 9023 85482 water 613 648 820 1434 1720 5881 alarm 1489 1472 2628 36761 27985 169004 barley 1247 1362 1968 6758 3446 24796 hailfinder 1659 1957 2967 2212 7084 80578 hepar2 4777 2836 3910 449916 9164 136939
* The average ratio for 10 simulated datasets.
products. The right side of table 2 shows that algorithm 1 reduces the number of required bits for the199 score component although there is some variation among the networks.200
6.2 Selection of Annealing Processor201
From the following discussion, the Fujitsu digital annealer is suitable for our approach from the202 viewpoint of bit capacity.203
Fully Connected Type. To the best of our knowledge, the bit capacity of the Fujitsu digital annealer204 is the largest in fully coupled annealing processors. The second generation Fujitsu digital annealer205 can deal with problems on a scale of 8192 bits [Matsubara et al., 2020]. The left side of table 3 shows206 that it is possible to encode all the logical conversion results for benchmark networks to the circuit of207 the digital annealer within bit capacity.208
Nearest Neighbor Type. The number of additional bits required for minor embedding depends on209 the design of the hardware graphs. Oku et al. 2019 proposed a heuristic minor embedding algorithm210 for the Hitachi CMOS annealing machine [Masanao et al., 2010]. Using this algorithm, the number211 of required physical spins when embedding a fully connected graph is I2 + I for I variables. The212 conversion method proposed in this study has n local fully connected graphs on p, q. Therefore, the213 number of required physical spins must be at least ∑n i=1(λ1,i + λ2,i)(λ1,i + λ2,i + 1) + ( n 2 ) . From214 the right side of table 3, it is currently infeasible to encode logical conversion results for at least some215 networks to the circuit of CMOS annealing machine within its 102400 nodes [Sugie et al., 2021]. As216 far as we know, the bit capacity of the Hitachi CMOS annealing machine is the largest in nearest217 neighbor annealing processors.218
6.3 Score Maximization219
We demonstrate the performance of Fujitsu digital annealer for score-based Bayesian network220 structure learning using the conversion results of N = 10000 simulated datasets. The running time221 for each simulated dataset is 6000 [s].222
Baselines. We compare the results obtained by the digital annealer with those of three heuristic223 algorithms. One algorithm is the simulated annealing algorithm [Heckerman et al., 1995b] with a224 QUBO same as the one encoded into the digital annealer. Other algorithms are the ordering space225 search algorithms, i.e., ordering-based search and acyclic selection ordering-based search. For a fair226 comparison, the running time of the simulated annealing algorithm for each simulated dataset is 6000227 [s] and that of the ordering space search algorithms is 6000 [s] plus the running time of algorithm 1.228 The computing environment is Microsoft Windows 10 Pro, 3.6 GHz Intel Core i9 processor, and 64229 GB memory.230
Result. Figure 2 shows that the digital annealer is better than all the baselines for all the simulated231 datasets from all the benchmark networks.232
7 Conclusion233
We proposed a novel approach of converting a score-based Bayesian network structure learning234 into QUBO. The essence of this approach lies in reducing the number of required bits through the235 advanced identification of candidate parent sets and their representation as Cartesian products. The236 Fujitsu digital annealer with our conversion method improved the BDeu score for 27 to 70 variables237 benchmark networks over existing methods. The bit capacity limitation of annealing processor is238 being relaxed rapidly 3. Though our approach is still a disadvantage for larger-scale networks, we239 expect that our proposed algorithms will be effectively applied to larger-scale score-based Bayesian240 network structure learning in the near future.241
Potential Negative Societal Impacts. The development of annealing processor technology could242 have an impact on various industry fields. However, the number of companies that have commer-243 cialized the API usage of annealing processors is still small. Therefore, there is a concern that the244 market of annealing processors will not work well and the disparities among stakeholders will be245 widen. Researchers are required to properly evaluate the value of technology and communicate it to246 the business side.247
3Fujitsu announced that they achieved a megabit-class performance with digital annealer
References248 Judea Pearl, editor. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan249 Kaufmann, 1988.250
Gregory F. Cooper and Edward Herskovits. A bayesian method for the induction of probabilistic networks from251 data. Journal of Machine Learning, 9(4), 1992.252
Robert G. Cowell. Conditions under which conditional independence and scoring methods lead to identical253 selection of bayesian network models. In Jack Breese and Daphne Koller, editors, Proceedings of the 17th254 Conference on Uncertainty in Artificial Intelligence, pages 91–97. Morgan Kaufmann Publishers, 2001.255
David M. Chickering, David Heckerman, and Christopher Meek. Large-sample learning of bayesian networks is256 np-hard. Journal of Machine Learning Research, 20:1287–1330, 2004.257
Marc Teyssier and Daphne Koller. Ordering-based search: A simple and effective algorithm for learning bayesian258 networks. In Proceedings of the 21th Conference on Uncertainty in Artificial Intelligence, pages 584–590,259 2005.260
Mauro Scanagatta, Cassio Polpo de Campos, Giorgio Corani, and Marco Zaffalon. Learning bayesian networks261 with thousands of variables. In Proceedings of the 28th International Conference on Neural Information262 Processing Systems, pages 1864–1872, 2015.263
Hidenori Gyoten, Masayuki Hiromoto, and Takashi Sato. Area efficient annealing processor for ising model264 without random number generator. IEICE Transactions on Information and Systems, E101.D(2):314–323,265 2018.266
Kasho Yamamoto. Research on Annealing Processors for Large-Scale Combinatorial Optimization Problems.267 PhD thesis, Graduate School of Information Science and Technology Hokkaido University, 2020.268
Vicky Choi. Minor-embedding in adiabatic quantum computation: I. the parameter setting problem. Quantum269 Information Processing, 7:193–209, 2008.270
Vicky Choi. Minor-embedding in adiabatic quantum computation: Ii. minor-universal graph design. Quantum271 Information Processing, 10:343–352, 2010.272
Bryan A. O’Gorman, Alejandro Perdomo-Ortiz, Ryan Babbush, Alan Aspuru-Guzik, and Vadim Smelyanskiy.273 Bayesian network structure learning using quantum annealing. The European Physical Journal Special Topics,274 225(1), 2014.275
Endre Boros and Aritanan Gruber. On quadratization of pseudo-boolean functions. CoRR, abs/1404.6538, 2014.276
Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki Miyazawa, Hirotaka Tamura, and Helmut G.277 Katzgraber. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer.278 Frontiers in Physics, 7(48), 2019.279
Wray Buntine. Theory refinement of bayesian networks. In Proceedings of the 7th Conference on Uncertainty280 in Artificial Intelligence, pages 52–60, 1991.281
David Heckerman, Dan Geiger, and David M. Chickering. Learning bayesian networks: The combination of282 knowledge and statistical data. Journal of Machine Learning, 20(3):197–243, 1995a.283
Martin Anthony, Endre Boros, Yves Crama, and Aritanan Gruber. Quadratic reformulations of nonlinear binary284 optimization problems. Mathematical Programming, 162(1):115–144, 2016.285
Endre Boros and Peter L. Hamme. Pseudo-boolean optimization. Journal of Discrete Applied Mathematics, 123:286 155–225, 2002.287
Cassio P. de Campos and Qiang Ji. Efficient structure learning of bayesian networks using constraints. Journal288 of Machine Learning Research, 12:663–689, 2011.289
Alvaro H. C. Correia, James Cussens, and Cassio de Campos. On pruning for score-based bayesian network290 structure learning. Journal of Machine Learning Research, 108:2709–2718, 2020.291
Satoshi Matsubara, Motomu Takatsu, Toshiyuki Miyazawa, Takayuki Shibasaki, Yasuhiro Watanabe, Kazuya292 Takemoto, and Hirotaka Tamura. Digital annealer for high-speed solving of combinatorial optimization293 problems and its applications. In Proceedings of the 25th Asia and South Pacific Design Automation294 Conference, pages 667–672, 2020.295
David Eppstein. Finding large clique minors is hard. Graph Algorithms and Applications, 13(2):197–204, 2009.296
Daisuke Oku, Kotaro Terada, Masato Hayashi, Masanao Yamaoka, Shu Tanaka, and Nozomu Togawa. A297 fully-connected ising model embedding method and its evaluation for cmos annealing machines. IEICE298 Transactions on Information and Systems, E102-D(9):1696–1706, 2019.299
Yamaoka Masanao, Yoshimura Chihiro, Hayashi Masato, Okuyama Takuya, Aoki Hidetaka, and Mizuno300 Hiroyuki. A 20k-spin ising chip to solve combinatorial optimization problems with cmos annealing. IEEE301 Journal of Solid-State Circuits, 51(1), 2010.302
Yuya Sugie, Yuki Yoshida, Normann Mertig, Takashi Takemoto, Hiroshi Teramoto, Atsuyoshi Nakamura,303 Ichigaku Takigawa, Shin ichi Minato, Masanao Yamaoka, and Tamiki Komatsuzaki. Minor-embedding304 heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes. Soft305 Computing, 2021.306
Daphne Koller and Nir Friedman, editors. Probabilistic Graphical Models: Principles and Techniques. The307 MIT Press, Cambridge, Massachusetts, 2009.308
David Heckerman, Dan Geiger, and David M. Chickering. Learning bayesian networks: Search methods and309 experimental results. In Preliminary Papers of the 5th International Workshop on Artificial, pages 112–128,310 1995b.311
Checklist312 1. For all authors...313
(a) Do the main claims made in the abstract and introduction accurately reflect the paper’s contribu-314 tions and scope? [Yes]315
(b) Did you describe the limitations of your work? [Yes] See section 7.316 (c) Did you discuss any potential negative societal impacts of your work? [Yes] See section 7.317 (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]318
2. If you are including theoretical results...319
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section 4.320 (b) Did you include complete proofs of all theoretical results? [Yes] See section 5.321
3. If you ran experiments...322
(a) Did you include the code, data, and instructions needed to reproduce the main experimental323 results (either in the supplemental material or as a URL)? [Yes] in the supplemental material324
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?325 [Yes] See section 6.326
(c) Did you report error bars (e.g., with respect to the random seed after running experiments327 multiple times)? [Yes] See fig. 2.328
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs,329 internal cluster, or cloud provider)? [Yes] See section 6.3.330
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...331
(a) If your work uses existing assets, did you cite the creators? [Yes] in the supplemental material332 (b) Did you mention the license of the assets? [N/A]333 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]334 (d) Did you discuss whether and how consent was obtained from people whose data you’re us-335 ing/curating? [N/A]336 (e) Did you discuss whether the data you are using/curating contains personally identifiable informa-337 tion or offensive content? [N/A]338
5. If you used crowdsourcing or conducted research with human subjects...339
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?340 [N/A]341
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB)342 approvals, if applicable? [N/A]343
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on344 participant compensation? [N/A]345

Review summaries:
The premise of the paper is both novel and interesting, in regarding Bayes network structure learning as a combinatoric optimization problem amenable to simulated annealing, specifically with current quantum computing tools.  The paper offers an approach to converting a score-based Bayesian network structure learning into quadratic unconstrained binary optimization. The improvement in representation of Bayes networks structure over current published methods turns on identification of candidate parent sets, and that this shows improvements compared to "ordering space search algorithms" 

**N.B.** I have reviewed a previous version of this paper. This version does not address many of the main concerns I raised in that review, so I will mostly repeat those.  In this work, the authors formulate Bayesian network structure learning (BNSL) as a quadratic unconstrained binary optimization (QUBO) problem. The main contribution of the work is a novel encoding of BNSL as a QUBO respecting the bit limitation of a particular digital annealer platform. Experiments on standard benchmarks show the formulation leads to mildly higher likelihoods compared to baseline methods.

The paper considers the problem of structure learning in Bayesian networks but on alternative hardware to the classic von Neumann computers. In particular, a digital annealer is considered and consequently the structure learning problem is encoded into a quadratic unconstrained binary optimisation problem (QUBO). Digital annealers are known to be very good at (approximately) solving these kinds of optimisation problems. Experimental results on standard Bayesian networks demonstrate the effectiveness of the proposed approach compared with standard methods that run on classical hardware.

The paper concerns a method for learning BNs from discrete data. A score-based approach is taken where the score is BDeu with effective sample size = 1. Table 1 shows the learning problems attempted here. The steps are: (1) Choose a limit on parent set size (here simulated data is used, and the chosen size is that of the biggest parent set in the true BN). (2) Generate candidate parent sets (CPSs). Since the authors claim that it is "infeasible to identify exact candidate parent sets by searching the power set P(X \ {X i }) in a realistic timeframe." a greedy approach it taken (Algorithm 2). (3) Decompose the CPSs into Cartesian products (another greedy algorithm is used - Algorithm 1). (4) Use a digital annealer to search for a high-scoring BN. (Comparisions with some other algorithms are also done).