Bayesian Network Structure Learning using Digital Annealer
Authors: Yuta Shikuri
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Bayesian Network Structure Learning
Digital Annealer

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

Bayesian Network Structure Learning using Digital Annealer
Anonymous Author(s)
Affiliation Address email
Abstract
Annealing processors, which efficiently solve quadratic unconstrained binary optimization (QUBO), are a potential breakthrough in improving the accuracy score-based Bayesian network structure learning. However, currently, the bit capacity of an annealing processor very limited. To utilize the power of an- nealing processors, it is necessary encode score-based learning problems into QUBO within the upper bound of bits. In this paper, propose novel approach with direct encoding of candidate parent sets in the form of Cartesian products. Experimental results on benchmark networks with 27 to 70 variables show that our approach requires lesser bits than the bit capacity of the accond-generation Fujitsu digital annealer, a fully coupled annealing processor developed by with semiconductor technology. Moreover, we demonstrate that the digital annealer with our conversion method consistently outperforms the state-of-the-art heuristic algorithms the benchmark networks.
2
3
10
11
12
Introduction
14
15 Bayesian network is probabilistic graphical model that represents the structure a joint probabil-
16 ity distribution among random variables in a directed acyelic graph (DAG) (Pearl 1988.. One class
17 of associated computational problems is learning the structure of Bayesian network from data. We
18 focus on score-based Bayesian network structure learning for finding the DAG with maximal score
that depends on the data [Cooper and Herskovits 1992 Cowell 2001
20
The Bayesian network learning problem NP-hard [Chickering et al. 2004] therefore, the standard methodology is using hcuristic approaches. Many algorithms have been proposed to improve the accuracy and to reduce the running time, A search over the space of orderings [Teyssier and Koller Scanagatta al. 2015 one of the most successful heuristic approaches.
21
22
23
2005
24
Annealing processors may contribute to finding a high-scoring network structure in a realistic timeframe. An annealing processor is expected to be an alternative hardware to von Neumann computers for quadratic unconstrained binary optimization (QUBO) problems. In particular, it is reported that complementary metal oxide semiconductor (CMOS) annealing processors already outperform conventional computers on the speed of solving max-cut problems [Gyoten et al., 2018).
25
26
27
28
We note that the bit capacity of an annealing processor is currently limited. Therefore, need an efficient conversion method of Bayesian network structure learning into QUBO within the limited
31 bits. Additionally, it is also important to show the lower bounds of penalty coefficients because the precision for the biases and variable couplers is limited.
32
Submitted to 35th Conference Neural Information Processing Systems (NeurIPS 2021). Do distribute.

---

33
Annealing processors are classified into the nearest neighbor type and the fully connected type Yamamoto! 2020). While the coupling nodes of a nearest neighbor annealing processor is limited to only between adjacent nodes, the coupling exists between arbitrary nodes of a fully coupled annealing processor. Though the scalability of nearest neighbor annealing processors is high, it is necessary to consider the additional bits for minor embedding [Choi 2008 2010).
34
35
36
37
O'Grman et al. 2014 proposed a method to convert score-based Bayesian network structure learning 38
into QUBO that requires (n²²) ) bits for random variables and maximum parent set size m = 2. They also demonstrated the sufficient lower bounds of penalty coefficients. However, when m 2 3, the number of necessary auxiliary variables for a quadratization [Boros and Gruber 2014] is at most Onn(n - )). This is significant disadvantage for the current limited bit capacity of annealing processors.
39
40
41
42
43
44
In this study, we propose an efficient conversion method based on the advanced identification of candidate parent sets and their representation in the form of Cartesian products. We also provide greedy algorithm to decompose the candidate parent sets into the form of Cartesian products and prove the sufficient lower bounds penalty coefficients.
45
46
47
Experimental results benchmark networks with 27 to 70 variables show that conversion method reduces the required bits significantly in comparison to the previous work [O'Gorman et al. 2014]. Our approach allows us to utilize the power of the second generation Fujitsu digital annealer, a fully coupled CMOS annealing processor [Aramon et al., 2019]. We demonstrate that the digital annealer consistently outperforms the ordering space search algorithms on the benchmark networks.
50
51
52
Background
53
2.1
Score-based Bayesian Network Structure Learning
55
The goal of score-based Bayesian network structure learning is to find a DAG with maximal score. 56 Given to random variables = (X+);=1 and a complete data set of instances D = (D1,..,,D)
57 we optimize the parent set II, of each random variable,
II II
arg min Ih Dl C. GEDAG
log ( ID),
(1)
where G -V-8),V= (1,... nn.E (( (1,
n). (1,...,n)).X, I1). and S, I1, R is
59 local score function corresponding to X,. The Bayesian Dirichlet equivalent uniform (BDeu) score Buntine 1991 is one of the commonly used scores,
80
A.
[(agg)
T(NiAA aij..)) I(as,..)
(i) BDe
(I,
II j=1
II Jem
T(N + +ass)
61 where = DE N.j, Noj Σx= Nij.k; oij = Ek Gi.j. B; is the number of joint states of
82 II, 7 is the number of states of Xú, Ni.j. is the number of cases of the parent set II, in its j-th state
63 and X, in its k--th state, a.jj.k = a is the hyperparameter of the Dirichlet function, and 0 << a e R called equivalent sample size [Heckerman al. 1995a].
64
85
2.2
Hamiltonian
66
The Hamiltonian, which is the objective function of an annealing processor, is a quadratic pseudo- Boolean function,
67
H(0)
Σ hoo Σ
Ji.jo
(3)
iEVAP
(K.))EAP
88 where (ox (Arl B|/rll the biases h; R for all e VAP, the couplers Jú, IR for all (i,5) EAP, and the graph GAP (VAP, EAP). Higher degree problems reformed into quadratic ones using auxiliary variables. This reformulation is called quadratization.

---

71
Definition 1. If a quadratic polynomial function g h) is a quadratization of pseudo-Boolee function f(v), then [(v)) = min g(v, h) for all v E BB..
72
73
Anthony et al. 2016 proved that every pseudo-Boolee function of / variables and of degree K has a quadratization involving at most OII auxiliary variables. particular, at most (22)) when
74
75
K I. It is well known that every pseudo-Boolean Boolean function can be uniquely represented
76
multilinear polynomial in its variables [Boros and Hamme 2002].
2.3
Basic Conversion of Score-based Bayesian Network Structure Learning
Using n(nn 1) bits to encode the paths into d = ((dd))))s)sm E Ba(n-1) (dj,s = if X, is the parent of X,, d3, = 0 otherwise) and (2) bits to encode the topological orders into
78
79
80 r (ri.))siess E BB()) (Ti.j = 0 the order of X; is higher than X,. = otherwise), is
81 possible to represent eq. T on the Hamiltonian,
H Heotal (d,
Σ 2=
H score (d.;) Heycle r).
(4)
The states of d are mapped one-to-one to the states of 1I. Let II, (d, for all 1 S The local score of the Hamiltonian is
82
(1)) score (d.,s) =
log S (Ir (0) (d.,)) 1)
D) + log ( I DD)
(5)
84 for all 1 SiSM n. The score function has a quadratization involving at most O - auxiliary 85 variables. O'Gorman et al. 2014 added the maximum parent set size constraint to the Hamiltonian.
86 In this case, the number of auxiliary variables most O(n(n - 1) The cycle constraint of the
87 Hamiltonian consists of the topological order constraint and the consistency constraint,
Heyelo (d, r) =
Σ IsKjj<kn
MRRrissyiA + E ISKUSh
52(di + dz,(1 -ras)), (6)
where R(r1, Tz) = (1 (1- r2)r3 for all 72, T3 E B. When the penalty coefficients 0 < ō1, 62 E R are sufficiently large, the DAG constraint is satisfied indirectly through the relationship of the paths d and the topological order r. it holds that
90
max
max 1ST
max EBn-1
(H (d
-H (d,;; <d1 n1 2
82
31 then there is no cycle on paths of the ground state, where "0''*") ((d,,) ((dd,)isjsnj++b)
("'
92 de = 0 if (j. 3) = (j",;"), a(r""")== dz,, otherwise. The computational cost to obtain the left
98 side of eq. is at most On ).. In particular, at most Onn22n-3 when 1.
3 Candidate Parent Set Decomposition
95
Parent set identification is a major technique to narrow the search space of structure optimization, based on the relationship between parent sets and local scores under the DAG constraints (de Campos and Ji 2011 Correia et al. 20200]. The collection of candidate parent sets of a random variable X, is (X+) W C = (W" (D) sti) (W) ()). To reduce the required bits of the score component of the Hamiltonian, we propose an efficient conversion method with the parent set identification. We directly encode the candidate parent sets instead of using the paths d.
96
97
98
WW& C
39
100
101
Moreover, we decompose the candidate parent sets ( of each random variable into the form of Cartesian products as follows:
102
Decompose (i into (W,,; n Zi) (Wh,, O (X) Zo))
105
2. Remove duplicates in the elements of (Wn,s h.s O Z (Wn, n (X' 2.
3

---

3. Store (Wh, 0 Z:) (Wh, 0 (2 hi) in (Un,)) (Vn.))=i
where Z; _ - Wh. Wo, Uo, Vo,; o, A1, 22, (U for all 1 isis n. There a clear relationship,
(o... ... "
(U,V) E (Uo...". :UA..,s (Vo. i.
(8)
108
for all 1 1S S Here, given that the Hamiltonian is a quadratic pseudo-Booleee Boollen function, we can represent the score against 3 U Vir,s : by allocating Un Viv,s to two bits on the Hamiltonian. There- fore, it is possible to encade the candidate parent sets into the Hamiltonian using (Un,)) A1, h=00 (Vn,))/=0 A2.
110
111
The number of required bits of the score component the Hamiltonian
(11, + >2,5).
112
Example An example of the candidate parent sets in the form of Cartesian products as follows:
== (X1, X2, X3. Xa), Z4 (2), A 5, A1, 2, λ2, {X1, X3, X1), (X1, X2. X3, X4)), (Wa,) n Zi) = (X, X21, 0, {X1),
(Wn,) = (0, (X1), (X1, X2),
(X3, (X)
(Wh,s A (X' Z (0,0, Φ, (Xs, Xa), (X3, X,), (X3,Xa)]
(Un,)) An. (0. {X1}. X2), (Vn,s) A2. (6, (x3.X.)).
113 We optimize Ze C U Wn.s to minimize Λ1, + 22 However, is often infeasible to search all elements of the power set ( Therefore, we heuristically search Z; adding elements one by one, as algorithm |
The computational cost is at most ( for all 1 S S n.
Algorithm 1 Greedy Candidate Parent Set Decomposition
1: Input: (Wh, Output: Initialize: + Ao Z' 0, 2
2: for 1 to |
R=0 Wh.s - 1 do
3:
for X in h=0 Wh, Z do
4: if 11. 2 for Z; (X} then X d1,t + X2,1, Z' Z (U
5:
if Z + Z then Z + Z' else break
115
116
Example 2. An example of the bit reduction flow of algorithm is as follows:
Z: o, A1 0, = 5: (6) {, (X,,
fXs,
Xa, (X,, X3, (X2, Xz,
(X,, {,
Z,
= (Ø, (X1), (x1, x (Ø, X4)) 2, X2), \1, = 2,
4 Efficient Conversion of Score-based Bayesian Network Structure Learning
118 We make (Un,)) (Vh,a) A2, correspond (ph,s) (gh.s)
)a, one-to-one, where Ph,ss gh E B for all 0 < h X1,;, 0 S h A2, 1 iiis n. To identify the parent sets,
An
the one-to-one correspondence constraint that Ex Ph.i = A2,; ih = 1 for all < i S n. The Hamiltonian consists of the score component, the one-to-one correspondence constraint, and the cycle constraint,
120
121
Hiotal (p. r) = Σ ( (p., a. + H=(1)) (.,)) + Hoyele(P) q. r).
1=1
122 where p A1, q ()
/2 Under the one-to-one correspondence constraint, can represent the paths among random variables indirectly using p, without additional auxiliary variables,
di. = Σ
Ph.s +
Σ
4h.s:
(10)
ISh X,EU
1Shs X,EVa.

---

-
2-+3
1+
2 2+4
3+44
(2,3)-+1
(2)-+1
(3) -1
1
(4)
(1) -
Figure 1: An example of bit allocation for conversion method.
3
1, = 0, A1.3 = 1, 22,3 = 1,, = 0, Λ2,4 = 0, U1, = {2, 3). U2 (3)
(4) (3), U13 = (1), Vi,3 = (4). Circle p. q. Square r. Red lines include in the score
component of the Hamiltonian, a green line the one-to-one correspondence constraint, and blue lines the cycle constraint.
125 for all < j S n. Figure is an example of bit allocation using our conversion method. The number bits required in our conversion method
+ 22,:) (*) Note that do not
126
directly encode Po,i, f0, the Hamiltonian.
128 Score Component. The local score component of the Hamiltonian is
A1.
Az,
Ar. Ag.c Σ
Ho (p.i. F..
I (h.
(1I)
Am mm
for all i We can get these coefficients by solving simultaneous equations under the one-to-one correspondence constraint, 81,6, log s(6) (Un, D) + log (x) D), 82,0,
log 5(6 (Vh., (D) + log ( D), D),t,, = log (()) (Un. U Unr () + log s (Un.i (D log 500) (Vir, I D) - log s (6 (D).
132
One-to-One Correspondence Constraint. We penalize the connection among bits to select each
133
element from A1. Az,i
( (
134
H=l0) (p.,i: q.,i)
Σ
ELAPh,
Σ
(12)
ISheh'Sd..
for all < i n. where the penalty coefficient 0 < Eo, E R. If &1, &2, is sufficient large,
136
ΣxE n= Ph.i = Σx Uh,; = is induced indirectly.
137
Cycle Constraint. Compared to eq. (6) the cycle constraint of the Hamiltonian is
Hy (prcte(p.gg (p.g,r)
Σ
Σ
83(di, + dj,[ (1-((1-i..)) ri.)), (13)
Isicjeken
ISisiSn
where the penalty coefficients 0 8 E R. By setting 85,5; appropriately, can prevent the cycle from occurring.
5

---

140
5
Sufficient Lower Bounds of Penalty Coefficients
141
We demonstrate the sufficient lower bounds of penalty coefficients. The basic idea is that we find the range of penalty coefficients so that the change in return value of the Hamiltonian is negative when the input state changes to the state we desire induce.
142
143
One-to-One Correspondence Constraint. We consider to decrease the value of ΣX Ph. by one until it reaches 1. In the case of Ph ,5' 1, Ex Ph,s* 1, it holds that H Hotal q.q.)))) r) A2, and Ph.. = 0 if (h, i) = (h","") (N"
144
H Gotal (p ,5") r) 2 E1,5 + $1, + h= to Ah, Th,'", where pl ,5") = ((p)) ) - (h"
148
147
Ph.s x<)
Ph.s otherwise. Considering the case where p and
148
are swapped in the above, if E1,6, E2,i satisfy that
A
max 0
(-81,6,
Σ
min (ww:)) E1,6,
(14)
A1.
max 0gh5A22
(-82,6,4
Σ
4w,(0,4w,a,.)) (w)))) < E2,4
(15)
h=11
149
for all 1 i Σ n, then the grand state does not violate the one-to-one correspondence constraint.
150
The computational cost to obtain the left side of eq. 14 and eq. 15) is at most (2),) for all
151
1 S iss n.
152
Cycle Constraint. We consider four patterns of (ri d. d violating the consistency
153
constraint. It is assumed that X3- E Un- as Xz+ & Un C C.rrePhe..
,, = 0.
154
In the case of (0, 0),
) it holds that Hista (p. r) - (P. q. rl 5)) 2 52 (n - 2)61.
where ( 5") (ri.) (i' J") "Jssissnn and T2. 5") =1 -1-m Ti, if (i.j) (i",)"). ris
(3'5")
155
Fij
156
otherwise. Similarly, it is possible consider the case of (1,0, In the case of (0,
it holds that Hiotal (P. q. - -Hooaa (p""" ""","") q.r)) 2 65+ + $1 + Eiei tn- A,,- Th.6" (h" A " ) ) and 06" (0) =0
157
$1,4"-,1 Dd21 th h,. 9h,s" where pih "M (") = -(Ph,i (h ("","""
158
Ph.
159
if (h, i) (h", Ph,i
if (h (h**, """, (h" " ()) = Pn,s otherwise. Sim- Ph.i
180
ilarly, it possible to consider the case of 11). These results suggest the relationship of
57, 63 induce the consistency constraint. Here, based theorem [ we consider strategy
to repeat picking up one element from and switching its value until Hirann (r) 0. It is as- sumed that Htrans (r) > Herans (r (()) In the case of (1, it holds that Hiocal (P. Am A2, th h..5 Ih.r-
163
164
Hotal (p A ,.",""), n.q. (( (()) 2 s1, +>=1 hh --,,-,,...------- $1,4--
>
165
Similarly, it is possible to consider the case of (0,0, 0, 1). In the case of (1, O, 0) or (0, 0, holds
that Ho (p. r) Histaal (P. q, (()) > 57- These results suggest the lower bound of o7 to induce the topological order constraint. Considering the case where p and q are swapped in the above, if 87, 82 satisfy that
166
168
52
max max n2.t < 87 n 2' <
(16)
IsiSn
71,1 = max max KiisnshhsA X,EU x, X,UUR,
max OS
max OSh"SA2.
(-81,b,t tn + $1,4 + tn)
12 = max max OSSSnShhAAs X,EV, CVV.
max S
max ugh
(-82,6,i - - + 82,2 + (w)
169
for n 2 3, then the grand state does not violate the cycle constraint under the one-to-one cor-
170
respondence constraint. The computational cost to obtain the left side of eq. (66) is at most
O E n + X2,)).
171
172
Theorem 1. If it holds that Hurans (r) Eistejeksn R(raj. Takk) > O, then there exists
at least one index pair < 1" < 5r S n which satisfy H (r) > Herans (r(i"")))))
d')), where A(r1,T2, rs) = -112(11 - 13) + (1 r1) - for all ri, T3 E B, r= (ran)ssissnn E B()), (²)
173
174
175
p(0'")) (T25
(3' (6'5 (153)))ss and rij = 1 ras (i.j) (("j"), ri (e
rij otherwise.

---

Table 1: The benchmark networks from Bayesian network repository.
Ei=1 X
Name
Li=1
[T
Σ 8.(%
1)
N
100
N 1000
N 10000
insurance
27
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 simulated datasets.
178
Proof. It does lose the generality by considering the case of
(1, Here,
holds that 22,1, /1,3) R(1
11,, P2.3 r1,3) R(r1,2, 72,3, 71,3) R(r,,,, 72,3, 71.3)
R(r1,2 "2,,,, (1,3) - (0(1, 12,3 11,3) = 3. Additionally, it holds that (., R(
179
11,2; 12,s, 71.a) +R Ps.i; F2.1) - R(1-123, T3, (2,1) R((1-R(11.1 F3,i, - r1,1)
0 for all 3 < i. Therefore, it holds that (rrran(r)) - Hirans (r(1.2) Htrans (r) - Harans ( (2,33)
180
181
Htrans (r) Hrane (r(1.3)
From this result, it holds that Hurans Herans (r least one index pair (i* ".'" E ((1,2), (2, 3), (1,3)}.
for
182
Experimental Results
183
184
To validate the performance of our approach, we use 10 simulated datasets for each instance size N 100, 1000, 10000 and each benchmark network. The benchmark networks are discrete networks from Bayesian network repository | The score function is the BDeu score with 1. It is often infeasible to identify exact candidate parent sets by searching the power set P(X') (X,)) in realistic timeframe. We use the candidate parent sets from algorithm Note that the candidate parent sets depend on the heuristic search algorithms, but we do not focus on their performance this study. Table I |disllas the information benchmark networks. The code to replicate each experiment in this paper is available
185
187
188
189
190
191
Algo Algorithm 2 Greedy Candidate Parent Set Identification
1: Input: D, i, m Output: L Initialize: L +- ('),C'+ [") +
2: for to m do
3:
for W in L' do
4:
for X in X'
{X;} W do
5:
if S.W"" DD S.W u(x} D) for all W' c CWU(X) W C then
6:
L" + L" UW (X)).
7:
if C" + then C + CU C C" L" else break
8:
for W in L do
9:
if there exist W C W that satisfies S.(W (D) s S.WW' DD) then + L) (W).
6.1 Number of Required Bits for Score Component
193
In comparison to the existing method O Gorman et al. 2014], we reduce the number of required bits for the score component by encoding the candidate parent sets directly. While En A, candidate parent sets encoded in our approach, n(n 1) paths plus at most (nn(n-In)) 1) auxiliary variables
194
195
196
for m > 2 the existing method. The left side of table[]sht shows reduction rate of the number of
197
required bits for the score component. Moreover, we reduce the number of required bits for the score
component Σ (A1, X2,3) by decomposing the candidate parent sets in the form of Cartesian
https://www..t http://wwwwwhl.r..ccmmm wwt...cpppooosorrr//////////////
See supplemental material.

---

Table 2: The reduction rate of the number of required bits for score component.
E X n(n
1)
Σ Ei= (A1, + 22,5)
Σx=1 X;
Name
N 100
N 1000
N
10000
100
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 simulated datasets.
Table 3: The number of required bits for fully coupled and nearest neighbor annealing processors.
E (A1,5 + )2,1) + (3)
E (A1. + A2,)) 22, + 1)
Name
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 shows that algorithm reduces the number of required bits for the score component although there is some variation among the networks.
200
6.2
Selection of Annealing Processor
202
From the following discussion, the Fujitsu digital annealer suitable for our approach from the viewpoint of bit capacity.
203
To the best of our knowledge, the bit capacity of the Fujitsu digital annealer is the largest in fully coupled annealing processors. The second generation Fujitsu digital annealer can deal with problems on a scale of 8192 bits [Matsubara et al. 2020]. The left side of table shows that it possible to encode all the logical conversion results for benchmark networks to the circuit of the digital annealer within bit capacity.
Fully Connected Type.
205
206
207
208
Nearest Neighbor Type. The number of additional bits required for minor embedding depends the design of the hardware graphs. OOku et al. 2019 proposed heuristic minor embedding algorithm for the Hitachi CMOS annealing machine [Masanao et al. 2010). Using this algorithm, the number of required physical spins when embedding a fully connected graph is + I for / variables. The conversion method proposed in this study has local fully connected graphs on p, q. Therefore,
210
211
212
213
number of required physical spins must be least Σn= (A1, + (A1,) Λ2.5 + 1) + (3). From the right side of table it is currently infeasible to encode logical conversion results for least some networks to the circuit of CMOS annealing machine within its 102400 nodes (Sugie et al., 2021]. As far as we know, the bit capacity of the Hitachi CMOS annealing machine is the largest in nearest neighbor annealing processors.
214
217
218
219
6.3
Score Maximization
220
We demonstrate the performance of Fujitsu digital annealer for score-based Bayesian network structure learning using the conversion results of N 10000 simulated datasets. The running time for each simulated dataset is 6000 [s].

---

3.9
Sime
Sehor
Eshor
Garley
hailliddr
legaa2
017
Figure 2: Results of score maximization by the baseline algorithms. For each simulated dataset and
each baseline algorithm, we normalized Σx= (log 500) (II, (D) -lg S
(ol ( (D)) by dividing it by the
corresponding value of the Fujitsu digital annealer. In this experiment, we used the second-generatie Fujitsu digital annealer. SA simulated annealing, OBS ordering-based search, ASOBS acyclic selection ordering-basee based search.
223
We compare the results obtained by the digital annealer with those of three heuristic algorithms. One algorithm is the simulated annealing algorithm [Heckerman et al. 1995b with QUBO same as the one encoded into the digital annealer. Other algorithms are the ordering space search algorithms, i.e., ordering-basee basedd search and acyelic selection ordering-basee search. For fair comparison, the running time of the simulated annealing algorithm for each simulated dataset is 6000
Baselines.
224
225
226
[s] and that of the ordering space search algorithms is 6000 [s] plus the running time of algorithm [ The computing environment is Microsoft Windows 10 Pro. 3.6 GHz Intel Core i9 processor, and 64 GB memory.
Result. siows that the digital annealer better than all the baselines for all the simulated datasets from all the benchmark networks.
231
232
Conclusion
233
234
proposed novel approach of converting a score-based Bayesian network structure learning into QUBO. The essence this approach lies reducing the number of required bits through the advanced identification of candidate parent and their representation Cartesian products. The Fujitsu digital annealer with our conversion method improved the BDeu score for 27 to 70 variables benchmark networks over existing methods. The bit capacity limitation of annealing processor is being relaxed rapidly Though our approach is still a disadvantage for larger-scale networks, we expect that our proposed algorithms will be effectively applied to larger-scale score-base based Bayesian network structure learning the near future.
235
238
239
240
241
Potential Negative Societal Impacts. The development of annealing processor technology could have an impact on various industry fields. However, the number of companies that have commer- cialized the API usage of annealing processors is still small. Therefore, there is a concern that the market of annealing processors will not work well and the disparities among stakeholders will be widen. Researchers are required to properly evaluate the value of technology and communicate it to
244
245
246
247
the business side.
Fujitsu announced that they achieved megabit-clase performance with digital annealer

---

References
248
Judea Pearl, editor. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
250
251
Gregory F. Cooper and Edward Herskovits. A hayesian method for the induction of probabilistic networks from data, Journal of Machine Learnnng, 9()), 1992.
252
253
Robert G. Cowell. Conditions under which conditional independence and scoring methods lead to identical selection of bayesian network models. In Jack Breese and Daphne Koller, editors, Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pages 97. Morgan Kaufmann Publishers, 2001.
255
David M. Chickering, David Heckerman, and Christopher Mcek. Large-samplc learning of bayesian networks is np-hard. Journal of Machine Learning Research, 20: 1833333-33,, 2004.
257
258
Mare Teyssier and Daphne Koller. Ordering- based search: A simple and effective algorithm for learning bayesian networks. In Proceedings of the 21th Conference on Uncertainty in Artificial Intelligence, pages 584-590, 2005.
260
Mauro Scanagatta, Cassio Polpo de Campos, Giorgio Corani, and Marco Zaftalon. Learning bayesian networks with thousands variables. Proceedings of the 28th International Conference on Neural Information Processing Systems, pages 1864-1872 2015.
262
263
264
Hidenori Gyoten, Masayuki Hiromoto, and Takashi Sato. Area efficient annealing processor for ising model without random number generator. IEICE Transactions on Information and Systemx, (00...(2))31432
265
266
2018.
267
Kasho Yamamoto. Research on Annealing Processors for Large-Scale Combinatorial Optimization Problems. PhD thesis, Graduate School of Information Science and Technology Hokkaido University, 2020.
288
269
Vicky Choi. Minor eiberdimb adiabatic quantum computation: the parameter setting problem. Quantun Information Processing, 7:193-209, 2008.
270
Vicky Choi. Minor-embeddingg in adiabatic quantum computation: li minor-universal graph design. Quantumn Information Processing, 10:343-352, 2010.
272
Bryan A. O'Gorman, Alejandro Perdomo- Ortizz Ryan Babbush, Alan Aspuru- Guzik, and Vadim Smelyanskiy. Bayesian network structure learning using quantum annealing. The European Physical Journal Special Topics. 225(1), 2014.
274
275
278
Endre Boros and Aritanan Gruber. quadratization of pseudo-boolean functions. CoRR, abs/1404.6533, 2014.
Malihch Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki Miyazawa, Hirotaka Tamura, and Helmut G. Katzgraber. Physics-inspired optimization for quadratic unconstrained problems using digital annealer. Frontiers in Physics, 7(48), 2019.
279
Wray Buntine. Theory refinement of bayesian networks. In Proceedings the 7th Conference on Uncertainty in Artificial Intelligence, pages 60, 1991
281
David Heckerman, Dan Geiger, and David M. Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Journal of Machine Learning, 2073):1 1995a.
Martin Anthony, Endre Boros, Yves Crama, and Aritanan Gruber. Quadratic reformulations of nonlinear binary optimization problems. Mathematical Programming. 162(1):115-144, 2016.
286
Endre Boros and Peter L. Hamme. Pseudo-boolean optimization. Journal of Discrete Applied Mathematics. 123: 155-225. 2002.
288
Cassio P. de Campos and Qiang Ji. Efficient structure learning of bayesian networks using constraints. Journal of Machine Learning Research, 12:663-688
2011.
280
Alvaro H. C. Correia, James Cussens, and Cassio de Campos, On pruning for score-based bayesian network structure learning. Journal of Machine Learning Research, 108:2709-2718, 2020.
292
Satoshi Matsubara, Motomu Takatsu, Toshiyuki Miyazawa, Takayuki Shibasaki, Yasuhiro Watanabe, Kazuya Takemoto, and Hirotaka Tamura. Digital annealer for high-speed solving of combinatorial optimization problems and its applications. In Proceedings of the 25th Asia and South Pacific Design Automation Conference, pages 667-672, 2020.
293
285
David Eppstein. Finding large clique minors is hard. Graph Algoritiums and Applications, 13(2):197-244 2009.
10

---

297
Daisuke Oku, Kotaro Terada, Masato Hayashi. Masanao Yamaoka, Shu Tanaka, and Nozomu Togawa. A fully-connected ising model embedding method and its evaluation for cmos annealing machines. IEICE Transactions on Information and Systems, E102-D(9)1669-17706 2019.
299
Yamaoka Masanao, Yoshimura Chihiro, Hayashi Masato, Okuyama Takuya, Aoki Hidetaka, and Mizuno Hiroyuki. A 20k ising chip to solve combinatorial optimization problems with emos annealing, IEEE Journal of Solid-State Circuits, 51(1), 2010.
301
302
303
Yuya Sugie, Yuki Yoshida, Normann Mertig, Takashi Takemoto, Hiroshi Teramoto, Atsuyoshi Nakamura, Ichigaku Takigawa, Shin ichi Minato, Masanao Yamaoka, and Tamiki Komatsuzaki. Minor-embedee embedding heuristies for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes. Soft Computing. 2021.
304
305
307
Daphne Koller and Nir Friedman, editors. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, Cambridge, Massachusetts, 2009.
309
David Heckerman. Dan Geiger, and David M. Chickering. Learning bayesian networks: Search methods and experimental results. In Preliminary Papers of the 5th International Workshop Arrificial, pages 1 112-128, 1995b.
Checklist
312
313
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
315
(b) Did you describe the limitations of your work? [Yes] See section 7
317
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See section 7
318
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
319
2. If you are including theoretical results...
320
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section
321
(b) Did you include complete proofs of all theoretical results? [Yes] See section S
322
3. If you ran experiments...
323
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [Yes] in the supplemental material
324
325
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
YYs]] See section 6
327
(c) Did you report error bars (e.g.. with respect to the random seed after running experiments multiple times)? [Yes] See fig. 2
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [YYs]] See section 6.3
330
331
4. If you are using existing assets (c.g., code, data, models) or curating/relcasnng new assets...
332
(a) If your work uses existing assets, did you cite the creators? [Yes] in the supplemental material
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
335
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're us-
ing/eurating? [N/A]
337
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
339
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable?
341
[N/A]
(b) Did you descrihe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
343
3/4
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on
345
participant compensation? [N/A]
11


Reviews:
[{"review_id": "o66aeyelxYu", "reviewer": "Reviewer_9dre", "summary": "**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.\n\nIn 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.", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "--- Originality\n\nThe main contribution of this work is the specific formulation and encoding of BNSL as a QUBO. In particular, a decomposition of parent sets to a suitable form is given, as well as a way to avoid cycles in the BN structure.\n\n--- Quality\n\nThe technical quality of the work is somewhat limited. For example, it is unclear if the size of the encoding provided here is a tight lower bound on the size of an encoding of this formulation of BNSL. \n\nWhile it is unclear what versions of the order-based searchers were used (with/without restarts, tabu list, etc.), and local search algorithms for the time frame and networks of this size are not state of the art, the BNSL baselines are an improvement compared to the previous version.\n\n--- Clarity\n\nAs a non-expert in such annealing approaches, and especially the Hamiltonian formulations, I found this paper extremely difficult to follow. It is very notation heavy, and very little intuition, description, or context is given for the equations and algorithms.\n\n--- Significance\n\nThe work shows that the proposed formulation of BNSL as a QUBO using the fully connected DA architecture has advantages compared to other formulations of BNSL for the nearest-neighbor DA architecture. However, the (updated) version of the paper does not provide any hints as to how the work may be of interest to either the broader BNSL community or for other DA/QUBO problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "--- Quality\n\nWhile I appreciate that the main contribution of this work is the BNSL formulation for the Fujitsu annealer, the paper also claims to make meaningful improvements in solving BNSL compared to state of the art. Local search algorithms are not state of the art with the long time frame and relatively small networks here; the score can be exactly optimized by a large number of techniques.\n\nThe experiments themselves do not really explore the cases where the formulation and encoding is effective and where it is not. For example, the size of the encoding is dependent on the number of candidate parent sets and how they can be decomposed. It is well known [de Campos and Ji, JMLR 2011; among others] that the number of candidate parent sets is dependent on the number of instances in a dataset as well as the choice of scoring function, among other factors. One possible deeper experiment could explore how these factors affect the QUBO formulation.\n\n--- Clarity\n\nThe paper is very difficult to follow for a non-expert. Additional explanations, intuition, context, etc., about what the various algorithms and equations mean would be very helpful for reaching a wider audience.\n\n--- Significance\n\nThe significance of the work is limited since the authors do not attempt to connect their formulation of BNSL (such as the Cartesian product approach for representing candidate parent sets) to other work in the area. Similarly, it is not clear if the proposed strategies for quadratization for BNSL would be relevant for other problems, even highly related ones such as learning Markov networks.\n\n--- Societal impact\n\nAnnealing processors may indeed have some sort of impact on computing.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "gJXNT__YQxo", "reviewer": "Reviewer_GCo9", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is fairly well written and organised. The quality of the presentation is overall fairly good. However, there are a few issues that should be addressed in order to improve the presentation.\n\n1. The notation used throughout the paper, especially when describing the encoding of the Hamiltonian is quite dense and it makes it very difficult to follow and therefore appreciate the contribution. More specifically, I think it should be simplified in some way but more importantly the presentation needs to be accompanied by clearly described examples of the encodings. Figure 1 is kind of confusing as it stands now. I think it would also be helpful to include an example of a digital annealer architecture and how the Hamiltonian/encoding maps to it.\n\n2. In the experimental section, the baselines considered for comparison (ie, structure learning algorithms that run on classical hardware) are not amongst the best performing ones. For instance, there are more recent algorithms that scale to much larger instances and are able to produce superior quality solutions. See for example those introduced by [Scanagatta el al, 2015] or [de Campos et al, 2011].\n\n[Scanagatta et al, 2015] M. Scanagatta, C. De Campos, G. Corani. M. Zaffalon. Learning Bayesian networks with thousands of variables. NeurIPS 2015.\n\n[de Campos et al, 2011] C. De Campos, Q. Ji. Efficient structure learning of Bayesian networks using constraints. JMLR 12:663-689, 2011.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the paper and there is no potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "bvIO39TYH9X", "reviewer": "Reviewer_Yh3Z", "summary": "The paper concerns a method for learning BNs from discrete data. A\nscore-based approach is taken where the score is BDeu with effective\nsample size = 1. Table 1 shows the learning problems attempted\nhere. The steps are: (1) Choose a limit on parent set size (here\nsimulated data is used, and the chosen size is that of the biggest\nparent set in the true BN). (2) Generate candidate parent sets\n(CPSs). Since the authors claim that it is \"infeasible to identify\nexact candidate parent sets by searching the power set P(X \\ {X i })\nin a realistic timeframe.\" a greedy approach it taken (Algorithm\n2). (3) Decompose the CPSs into Cartesian products (another greedy\nalgorithm is used - Algorithm 1). (4) Use a digital annealer to search\nfor a high-scoring BN. (Comparisions with some other algorithms are\nalso done).\n", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As the authors correctly point out BN learning is NP-hard. They also\nstate that \"the standard methodology is using heuristic\napproaches\". But for 4 of the 6 problems considered here it is\npossible to find a provably optimal (maximal score) BN in a reasonable\namount of time.\n\nThe authors are to be commended for their supplementary material which\nmakes it easy to examine their experiments. I used their code (the R\nscript) to simulate a dataset of size 10000 from the insurance, water,\nalarm and hailfinder. Note that 10000 is the largest size of dataset\nconsidered by the authors. I then used gobnilp (C version from public\ngit repo commit e60ef14, linked to SCIP version 7.0.1 with CPLEX\n20.1.0.0 as the LP solver, on a 2.7 GHz laptop) to find optimal BNs\nusing the same parent set size limits as the authors. The scores of\nthese optimal BNs and time taken are as follows:\n\ninsurance palim=3\nBN score is -132686.365245\nreal\t0m26.157s\n\nwater palim=5\nBN score is -128765.561813\nreal\t0m16.798s\n\nalarm palim=4\nBN score is -105196.063958\nreal\t1m50.351s\n\nhailfinder palim=4\nBN score is -497399.495910\nreal\t6m18.028s\n\nThese times include the time that gobnilp takes to internally\nconstruct candidate parent sets. (gobnilp does not use a greedy\napproach to do this to ensure that the generated candidate parent sets\ncontain those needed for an optimal BN, subject to the given parent\nset size limit.) However, both barley(palim=4) and hepar2(palim=6) are\ntoo hard for gobnilp: it fails to even get past the stage of\ngenerating candidate parent sets.\n\nPerhaps some other exact method could solve them, I don't know. But\nlet's just assume that these two cases are too hard for any 'exact'\n(provably optimal) learning. It could be that the authors' method is a\ngood choice for a heuristic approach. The first step of the authors'\nmethod is to generate a set of candidate parent sets using Algorithm\n2. So I used that algorithm to create a set of candidate parent sets\nfor the barley and hepar2 cases. This takes a while (for barley it\ntook \"real 198m33.421s\" to do using the authors' supplied Julia script).\n\nAfter converting these scores to a format gobnilp understands they\nwere sent to gobnilp, which, in both cases, quickly found an optimal\nBN for the given candidate parent sets:\n\nfrom barley CPS\nBN score is -508892.921268\nreal\t1m26.909s\n\nfrom hepar2 CPS\nBN score is -326309.949418\nreal\t0m11.401s\n\nSo in all 6 of the experiments the authors conducted a superior method\nis available. Part of the authors' method (greedy generation of\ncandidate parent sets) could be a useful contribution but I don't\nthink the current paper provides evidence for that. As it happens if\none lowers the parent set size limit for hepar2 from 5 to 3 and uses\ngobnilp, we get a slightly higher scoring BN than that found using the\ncandidate parent sets greedily generated by the authors' Algorithm 2.\n\nbarley, palim=3\nBN score is -326303.018128\nreal\t0m42.231s\n\nThe current paper contains some interesting ideas and it is reasonable\nto explore the value of using an annealing processor to conduct a\nheuristic search for a high-scoring BN. However, the authors need to\nfocus on problems where exact search is infeasible. They also need\nto show (empirically) that, given the candidate parent sets they\ngenerate with their Algorithm 2, the annealing approach is a superior\napproach to other existing methods which can take a set of candidate\nparent sets as input. Some theoretical analysis of 'what is lost' by\nthe greedy approach of Algorithm 2 would also be welcome.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They addressed potential negative societal impacts but I did not understand the point they were making.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IAi8-q9b8Nv", "reviewer": "Reviewer_UDX7", "summary": "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\" ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The annealing processor optimizes a quadratic function of the vector \\sigma (Equation 3).It may be familiar to those working in the field on how this relates to a solution off a via simulated annealing, and how the network structure translates such as encoding network paths by use of bits available to the annealer.  Assuming the authors are addressing an audience that understands BN structure learning, an extended version of section 2.3 for those not familiar with quantum annealing would make this work accessible.   As it is, I am not in a position to offer an opinion on the method proposed, and give the paper the benefit of the doubt. \n\nGiven the complexity of the encoding, reliance on identification of parent sets, and how the method relies crucially on the bit capacity of current digital annealers, one gets the presumption that the progress that can be made in generally applicable improvements in structure learning is limited. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address speculations about how quantum computing may have extensive social ramifications as it becomes applicable. ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no manifest ethical concerns with the work. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes some quite interesting ideas for learning the structure of Bayesian nets (BNSL). This has been acknowledge during the discussions. However, the current data/experiments/discussions do not show enough evidence that this is an effective method for BNSL (ideas show promise, but it was not considered enough yet). Reviewers and meta-reviewer think that ideas will be eventually worth publishing, so while this is a negative recommendation (sorry!), I would like to say a positive work: keep the interesting work going and you will find a suitable venue to discuss the work.
Decision: Reject