Testing Probabilistic Circuits
Authors: Yash Pote
Kuldeep S. Meel
Venue: NeurIPS 2021 Poster (2021)
Keywords: Probabilistic Circuits
Knowledge Compilation
Distribution Testing

Abstract: Probabilistic circuits (PCs) are a powerful modeling framework for representing tractable probability distributions over combinatorial spaces. In machine learning and probabilistic programming, one is often interested in understanding whether the distributions learned using PCs are close to the desired distribution. Thus, given two probabilistic circuits, a fundamental problem of interest is to determine whether their distributions are close to each other.

The primary contribution of this paper is a closeness test for PCs with respect to the total variation distance metric. Our algorithm utilizes two common PC queries, counting and sampling. In particular, we provide a poly-time probabilistic algorithm to check the closeness of two PCs, when the PCs support tractable approximate counting and sampling. We demonstrate the practical efficiency of our algorithmic framework via a detailed experimental evaluation of a prototype implementation against a set of 375 PC benchmarks. We find that our test correctly decides the closeness of all 375 PCs within 3600 seconds. 

Testing Probabilistic Circuits *f
Yash Pote
Kuldeep S. Meel
School of Computing, National University of Singapore
Abstract
Probabilistic circuits (PCs) are powerful modeling framework for representing tractable probability distributions over combinatorial spaces. In machine learning is often interested in understanding whether
and probabilistic programming, the distributions learned using PCs are close to the desired distribution. Thus, given two probabilistic circuits, f'undamental problem of interest determine whether their distributions are close to each other.
The primary contribution of this paper is closeness test for PCs with respect to the total variation distance metric. Our algorithm utilizes two common PC queries, counting and sampling. In particular, to check the closeness two PCs, when the PCs support tractable approximate counting and sampling. We demonstrate the practical efficiency of our algorithmic framework via a detailed experimental evaluation of prototype implementation against of 475 PC benchmarks. We find that our test correctly decides the closeness of all 475 PCs within 3600 seconds.
provide poly-time probabilistic algorithm
Introduction
Probabilistic modeling is at the heart of modern computer science, with applications ranging from image recognition and image generation 22 30 to weather forecasting [3. Probabilistic models have a multitude of representations, such as probabilistic circuits (PCs) [9, graphical models [19], generative networks [16], and determinantal point processes [20]. Of particular interest us are PCs, which are known to support guaranteed inference and thus have applications in safety-critical fields such as healthcare 2 25). this work, we will focus on PCs that are fragments of the Negation Normal Form (NNF), specifically DNNFs, d-DNNFs, SDNNFs, and Pls [13 We refer to the survey by Choi et al. 9 for more details regarding PCs.
Given two distributions /' and Q, fundamental problem is to determine whether they are close. Closeness between distributions frequently quantified using the total variation (TV) distance, drv Q) = P1/2)] Ql1 where || is the & norm (21] 6). Thus, stated formally, closeness testing is the problem of deciding whether drv () S or dry Q) 2 17 for 0 < < 1) <
Determining the closeness of models has applications in Al planning [13. bioinformatics 31 33 35
and probabilistic program verification [5] 23
Equivalence testing is a special case closeness testing, where one tests if (P,Q) = 0. Darwiche and Huang [13] initiated the study of equivalence testing of PCs by designing an equivalence test for d-DNNFs. An equivalence test is, however, of little use in contexts where the PCs under test
"The accompanying tool, available open source, can found at htttps//ggtuubbcc//////ggapppppp
The
Appendix is available in the accompanying supplementary material.
'The authors decided forgo the old convention of alphabetical ordering of authors in favor of randomized ordering, denoted by @. The publicly verifiable record of the randomization available at httpp::/ /estpa://ww..r www. aeaweb. org/ code: BBL For citation of the work, authors request that the citation guidelines by AEA for random author ordering be followed.
author- order/ with confirmation
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

encode non non-identical distributions that are nonetheless close enough for practical purposes. Such situations may arise due to the use of upproximate PC compilation [00 and sampling- As a concrete example, consider PCs that are learned via approximate methods such as stochastic gradient descent [27]. In such a case, PCs are likely to converge to close but non-identical distributions. Given two such PCs, we would like to know whether they have converged to distributions close to each other. Thus, we raise the question: Does there exist an efficient algorithm to test the closeness of two PC distributions?
learning
of PCs 26 27
In this work, we design the first closeness test for PCs with respect to TV distance, called Teq. Assuming the tested PCs allow poly- time approximate weighted model counting and sampling, Teq runs in polynomial time. Formally, given two PC distributions P and Q, and three parameters (E.1),8,, for closeness(E), farness(7). and tolerance(d), Teq returns Accept if drv ( (P. Q) I E and Reject if drv Q) 2 1 with probability at least 1 8. Teq makes atmost O((1) E) log(b-1)) calls to the sampler and exactly 2 calls to the counter.
Teq builds on general distance estimation technique of Canonne and Rubinfeld 4 that estimates the distance between two distributions with a small number of samples. In the context of PCs, the algorithm requires access an exact sampler and an exact counter. Since not all PCs support exact sampling and counting, we modify the technique presented in 4l to allow for approximate samples and counts. Furthermore, we implement and test Teq on a dataset of publicly available PCs arising from applications in circuit testing. Our results show that closeness testing can be accurate and scalable in practice.
For some NNF fragments, such as DNNF, no sampling algorithm is known, and for fragments such as PI, sampling is known to be NP-hard [32). Since Teq requires access to approximate weighted counters and samplers to achieve tractability, the question of determining the closeness of the PCs mentioned above remains unanswered. Thus, we investigate further and characterize the complexity of closeness testing for broad range of PCs. Our characterization reveals that PCs from the fragments d-DNNFs and SDNNFs can be tested for closeness in poly-time via Teq, owing to the algorithms of Darwiche [1] and Arenas et al. []] We show that the SDNNF approximate counting algorithm of Arenas al. can be extended to log-linear SDNNFs using chain formulas (8). Then, using previously known results, we also find that there are no poly-time equivalence tests for PCs from Pl and DNNF, conditional on widely believed complexity-theon theoretic conjectures. Our characterization also reveals some open questions regarding the complexity of closeness and equivalence testing of PCs.
The rest of the paper is organized in the following way. We define the notation and discuss related work in Section 2 We then present the main contribution of the paper, the closeness test Teq, and the associated proof of correctness in Section 3 We present our experimental findings in Section 4 and then discuss the complexity landscape closeness testing in Section We conclude the paper and discuss some open problems in Section 6 Due to space constraints, we defer some proofs to the
supplementary Section A
2 Background
Let 10, 10 be a circuit over n. Boolean variables. An assignment {0, 1)ah to the variables of y is satisfying assignment if (f() = 1. The set of all satisfying assignments of yp is R.p- If [Rpl > O, then to is said to be satisfiable and if [Rpl 2n, then to is said to be valid. We use [ypl to denote the size of circuit y,, where the size is the total number of vertices and edges in the circuit DAG.
The polynomial hierarchy (PH) contains the classes EP (NP) and II (co-NP) along with generaliza- tions of the form > and 11 where 11f., co-N and > = -f 34 The classes V; and TI are said to be at level i. If it is shown that two classes on the same or consecutive levels are equal, the hierarchy collapses to that level. Such a collapse is considered unlikely, and hence used as the basic assumption for showing hardness results, including the ones we present in the paper.

---

2.1 Probability distributions
weight function w :00, 13" + Q+ assigns a positive rational weight to each assignment o. We
extend the definition of w to also allow circuits as input: w(p) = Σ w(o). For weight function
deR,
and circuit yp, x(y) is the weighted model count (WMC) of y w.r.t
In this paper, we focus on log-linear weight functions as they capture a wide class of distributions, including those arising from graphical models, conditional random fields, and skip-gram models 224
Log-linear models are represented as literal-weighted functions, defined as:
Definition 1. For a X of n variables, weight function is called siteral-wiihhte if there is poly-time computable map w X + QQ (0, 1) such that for any assignment a E {0,1]"
((O) = II x
if r r= 1 if
xEa 1-w(w) (1-
x=0
For all circuits so, and log-linear weight functions w, w(pp) can be represented in size polynomial in the input.
Probabilistic circuits: A probabílistic circuit is a satisfiable circuit & along with a weight function
yp and together define a discrete probability distribution on the set {0, 1 that is supported over
ppar) 0
Ryp We denote the p.m.f. of this distribution as: P(g,,)
wwo)/w(p))
((())
In this paper, study circuits that are fragments of the Negation Normal Form (NNF). A circuit yo in NNF is rooted, directed acyelic graph (DAG), where each leaf node is labeled with true, false, v or mF; and each internal node is labeled with A V and can have arbitrarily many children. We focus on four fragments of NNF, namely, Decomposable NNF(DNNF), Structured DNNF(SDNNF)) and Prime Implicates(PI). For further information regarding circuits in NNF, refer to the survey 14 and the paper 28
The TV distance of two probability distributions P(P1 w.) and P(p2, w2) over {0, 1)" is defined as: drv (P(p), w,), ((22, w2)) E.Eee...) (0.1) [P(p), W, (o) P(pp, (o)).
P(Pp1, w;) and P(yp2, W2) are said to be (1) equivalent if dr w:), P(y2, H2)) 0, (2) e-close if drv (P((1, (P(pp)),))) P(yp,, wa)) S E, and (3) ff-far if drv (Pv((((()),, wi), P(pp2 w2)) 2
Our closeness testing algorithm Teq, assumes access an approximate weighted counter Awct(a, 3, 40, w). and an approximate weighted sampler Samp(a, 3 w). We define their behavior as follows:
Definition 2. Awct(a, 3, sp, u) takes a circuit sp, a weight function w, tolerance parameter a > 0 and a confidence parameter 3 > 0 input and returns the approximate weighted model count of up w.r.l. w such that
v(p)
< Awct(aa, 8. w) S a)x((() 2 1
Pr
1+a
Tractable approximate counting algorithms for PCs are known as Fully Polynomial Randomised Approximation Schemes (FPRAS). The running time of an FPRAS is given by T(a33,4) poly(a 1lg((3-)) lpl).
Definition 3. Samp(o, B. w) takes a circuit y,, weight function w, a tolerance parameter O and a confidence parameter 3 O as input and returns either (I) a satisfying assignment a sampled approximately w.r.t. funchtnnnction function w with probability > 1 3 or (2) symbol 1 indicating failure with probability < 3. In other words, whenever Samp samples o:
P(p, P(p,,)(o)
Pr[Saam(a,, 3, B,,,,,,,,,,,,,
o (1 + + (1) W)))
1+a
Tractable approximate sampling algorithms for PCs are known as Fully Polynomial Almost Uniform
Samplers (FPAUS). The running time of an FPAUS for a single sample is given by T(a, 3, Φ) =
poly(a 1og( >..
In the rest of the paper (m] denotes the set 21, m). (e) represents the indicator variable for event e, and [Ev)) represents the expectation of random variable v.
3

---

2.2 Related work
Closeness testing: Viewing circuit equivalence testing through the lens of distribution testing. we see that the d-DNNF equivalence test of Darwiche and Huang [13] can be interpreted as an equivalence test for uniform distribution on the satisfying assignments of d-DNNFs. This relationship between circuit equívalence testing and closeness testing lets us rule out the existence of distributional equivalence tests for all those circuits for which circuit equivalence is already known to be hard under tohplexity-theoreiic assumptions. We will explore this further in Section 5.2
Distribution testing: Discrete probability distributions are typically defined over an exponentially large number of points; hence a lot of recent algorithms research has focused on devising tests that require access to only sublinear even constant number of points in the distribution [5]. In this work, we work with distributions over {0, 1}"", and thus we aim to devise algorithms with running time most polynomial in n. Previous work in testing distributions over Boolean functions has focused on the setting where the distributions offer pair-conditional sampling access 77 22). Using pair-conditional sampling access, Meel et al. 22 were able to test distributions for closeness using ((tilt(p) /(n 2r) queries, where tilt is the ratio of the probabilities of the most and least probable element in the support.
3 Teq: a tractable algorithm for closeness testing
In this section, we present the main contribution of the paper: closeness test for PCs, Teq. The pseudocode of Teq is given in Algorithm
Given satisfiable circuits F1, and weight functions Wa, w2 along with parameters (,, 17, d), Teq decides whether the TV distance between P(Pi, wr) and P(y22, Wa) is lesser than & or greater than 7) with confidence Awct(a, 3, q, w), and an approximate weighted sampler Samp(a, 3, 4,, w). We define their behavior in the following two definitions.
least 1 8. Teq assumes access to approximate weighted counter
The algorithm Teq starts by computing constants y and m. Then it queries the Awet routine with circuit 10 and weight function w, to obtain 11++1/00 7/44 approximation of w, (fP1) with confidence at least 1 - 5/8. A similar query is made for yo2 and w2 to obtain an approximate value for wa( These values are stored in k and 22, respectively. Teq maintains m-sized array т, to store the estimates for r(a:). Teq now iterates m times. In each iteration, it generates one sample o, through the Samp call on line 7 There a small probability of at most 8/ //m that this call fails and returns L.
Teq only samples from one of the two PCs.
The algorithm then proceeds compute the weight of assignment o; w.r.t. the weight functions wi and and stores it in $1 and $2, respectively. Using the weights and approximate weighted counts stored in k1, ky the algorithm computes the value r(or) on line 10, where r(or)) is an approximation of the ratio of the probability of a; in the distribution (((2,, W2) to its probability in P(P1, (1).,w)). Since o; was sampled from P((2 w1), its probability in P(yp1, W,) cannot be O, ensuring that there is no division by O. If the ratio r(a,) is less than 1, then r[i] is updated with the value r(a;) otherwise the value of [ii remains O. After the m iterations, Teq sums up the values the array r. If the sum is found to be less than threshold m(E + 7). Teq returns Accept and otherwise returns Reject.
The following theorem asserts the correctness of Teq.
Theorem 1. Given two satisfiable probabilistic circuits 41, P2 and weight functions W1, W2, along with parameters E < 1 < and 8 <
A. If dry (P((1,, wz), P((2,, w2)) I E. then Teq( Was i22, W2, 17, returns Accept with probability at least (1 -)).
B. If drv (P((p,, ((P2,, wz)) 2 n, then Teq(sp1, W1, P2, Wa, 6a, 8,,,, 6) returns Reject with probability at least (1 5).
The following theorem states the running time of the algorithm,
Theorem 2. Let γ
7 - E. then the time complexity of Teq is in O (TAwa(7, 8, max((121)) (1221)) + Tsmm max(1seal 1x22))) log(s 1) If the underlying

---

Algorithm 1 Teq M1; 62,
1: y < (7) -1- /2
2: < [2log(4/0)) //
3: + [0] * m
4: 4ι + Awct( 1+ 7
5: h2 Awct( 11-7741-,6885 101-1,6/8844 11 W2)
6: for i E
.m do
7: d Samp(7/ - 8/ 8/4m, 11, wz)
8:
if + then
9:
$1 (1(a)) 82 x2(0,)
r(ox)) < 22
Ag
$1
11:
r(;
then
12:
[[ t- r(a;)
if
E
WE [m]] [ S m(E +?) then
Return Accept
15:
else 16:
Return Reject
PCs support approximate counting and sampling in polynomial time. then the rumning time of Teq is also polynomial in terms r, log(( and max(1ş1). (p2)).
To improve readability, we use Pi to refer to the distribution P(y wi) and Pg to refer to P(y2,, W2).
3.1 Proving the correctness of Teq
In this subsection, we present the theoretical analysis of Teq, and the proof of Theorem AA). We
will defer the proofs of Theorem [[B) and Theorem 2 to the supplementary Section A.4.2 and
Section A.4.3 respectively.
For the purpose of the proof, we will first define events Pass;, Pass2 and Good. Events Pass,, Pass2 are defined w.r.t. the function calls Awet( 1 + 1 1, 1, 8/8, (Pi, w1) and Awct(v/++///
1, 6/8, (22, W2), respectively (as on lines 4 5 of Algorithm [ Pass; and Pass2 represent the events that the two calls correctly return
7/4 approximations of the weighted model counts 7/4 1, 1,6/8, wt) < (vI+ (p1), and vo(())) S Awct( / 1 + 7/4 1, 12, w2) < (v 1 + (P2)). From the definition of Awct, Vi+a/4
of 91 and 22 i.c.
V1+7/1 < Awct(
(((11)
we have Pr[Paas,]] [r[pass]] 2 1 8/8.
Let Fail; denote the event that Samp (Algorithm) I line returns the symbol 1 the ith iteration of the loop. By the definition of Samp we know that Vec[m) Pr[Fail,] < 8/4m.
The analysis of Teq requires that all m Samp calls and both Awet calls return correctly. We denote
this super-event as Good = Nie(mi Fail, 0 Pass; n Pass2. Applying the union bound we see that the probability of all calls Awct and Samp returning without error least 1 - -5/2:
Pr[Good] = Pr[ U Fail, U Pass; Pass2 m 8 4/4m- 2- 5/8 = 8/2 (1)
ic [m]
We will now state lemma, which will prove in the supplementary Section A.4
Lemma 1. Good + |r(a) Ato) < 7/4 Pa(ar
Piao
We now prove the lemma critical for our proof correctness of Teq.
Lemma 2. Assuming the event Good, let A Exe(a,)) 1 (r(g) ()()) then
1. If drv (P). < s, then A 4/4
2. If drv (P),P)) n7 then A > 1 - 7/4
5

---

Proof. If Σ2 (P((z) - P2(=)) 0, then 2/2 Ex (P(()) =
E (P((z)-P1(x))
Using this fact we see that,
1 P2(o)
dr (P, o:Pa(o)<P((0)
Σ
Pi(a) P2(a)
E
Pi(o)
Pi(a)
Pa #: P[O)
P2(o)
<1) (1
P2(0)
Σ
1
Pi(o) Pi(e)
Pi(o)
oE(0,1)
P2(())
<1 (1- P2(0)
= A
Σ
Pi(o) -A
Pi(o)
Pi(o)
of [E(01]
B
Thus we have that drv (Pi, P2) A=
= B. We now divide the set of assignments E 10, into
three disjoint partition S1, S2 and S3 as following: S = fo 1( Pa(a)
< 1) = 1(r(o) < 1)}: <) (r((o) < 1)}; Sg = fo PT < 1) < 1(r(o) < 1)}. The
P(())
S2 = fo 1( Pa(a) (o)
P.la
definition implies that the indicator (r(o) < <1) is is for all assignments in the set S2, and is 1 for
all assignments in Sz. Similarly 1 Pa(a) respectively.
(9 1) takes value 1 and for all elements in S and Sg,
Now we bound the magnitude of B,
I
P3(o)) 1 Pi(o)
(Pa(o) <1) - - (())) <1) (i)
B
Σ
(0,1))
For by O, we have that E, aybyl S E, lay1b,, and thus:
|BIS Σ
[[t- -
(i()) 1 -1-
P2(a)
<1] Pi(O)
OE(0.1)"
We split the summation into three terms based on the sets in which the assignments lie. Some summands take the value 0 in a particular set, so we don't include them in the term.
Pa(a) (i(
<1) ((0)- ((())
P2(o)
Pa(a) Pi(a)
<1) (1
Pa(o)
B <
Σ rES1
Pi(a) + Σ 1
Pi(a)
Pi
rES
Σ
1 (r(o) < ())()r()))P((
Pala) Since we know that Vo E S2, r()) > 1 and Yo S3, P.(a)
> 1, we can alter the second and third
terms of the inequality in the following way:
P2
(2(a) ((o) (i(a)
P2(a)
Pa(o)
[B| < Σ 1
<1)
(i + Σσ 1
<1
r(())
(i
(i(
Pi(0)
Pi(o)
eES
oES₂
Pa(a) r(o) (i( S
r(o) Pa(a)
+ Σ
(r(a) 1)
Σ
Pi
Pi(a)
dES,
dES,US,US,
Using assumption of the event Good and Lemma 1 |B| S E Eoe 7/4 (o( S 7/4 Since drv (r,(P,,P) P2)
B, we get ddv (P,,P) A S 7/4. We can now deduce that drv P2) S then A < + 7/4 and if drv P1, P2) 2 n. then A 2 7/4.
Using Teq to test PCss in general. Exact weighted model counting (MC) is commonly supported query on PCs. In the language of PC queries, a WMC query is known as the marginal (MAR) query. Conditional inference (CON) is another well studied PC query. Using CON and MAR, one can sample from the distribution encoded by a given PC. It is known that if a PC has the structural properties of smoothness and decomposabillty, then the CON and MAR queries can computed tractably. For the definitions of the above terms and further details, please refer to the survey [9]

---

Evaluation
To evaluate the performance Teq, we implemented a prototype in Python. The prototype uses weighted sampler to sample over the input d-DNNF circuits. The primary objective of our experimental evaluation was to seek an answer to the following question: Is Teq able to determine the closeness of pair of probabilistic circuits by returning Accept if the circuits are 8-close and Reject if they are yy-frr? We test our tool Teq the following two settings:
WAPS 17
A. The pair of PCs represent small randomly generated circuits and weight functions.
B. The pair of PCs are from the set of publicly available benchmarks arising from sampling and counting tasks.
Our experiments were conducted on high performance compute cluster with Intel (eon(R) E5-2690 v3@2.60GHH CPU cores. For each benchmark, we use a single core with timeout of 7200 seconds.
4.1 Setting Synthetic benchmarks
Our dataset for experiments conducted in setting A consisted of randomly generated 3- CNFs and with random literal weights. Our dataset consisted of 3-CNFs with {14, 15, 16, 17, 183 variables. Since the circuits are small, we validate the results by computing the actual total variation distance using forte-
Dataset
drv
Benchmark
2 1
Actual
Result
Expected Result
14_1
0.9
0.99
0.740
A
A
14_2
0.8
0.9
0.764
A
A
15 15_3
3
0.75
0.94
0.804
A/R
17_4
0.75
0.9
0.941
R
18_2
0.75
0.9
0.918
R
R
Table 1: Runtime performance of Teq. We experiment with 375 random PCs with known drv, and out of the 375 benchmarks we display 5 in the table and the rest in the supplementary Section B In the table 'A' represents Accept and 'R' represents Reject. In the last column 'A/R' represents that both Accept and Reject are acceptable outputs for Teq.
Results Our tests terminated with the correct result less than 10 seconds on all the randomly generated PCs experimented with. We present the empirical results in Table The first column indicates the benchmark's 's name, the second and third indicate the parameters & and 17 on which we executed Teq. The fourth column indicates the actual drv distance between the two benchmark PCs. The fifth column indicates the output of Teq. and the sixth indicates the expected result. The full detailed results presented in the appendix Section B
4.2 Setting B Real-world benchmarks
Dataset We conducted experiments on a range of publicly available benchmarks arising from sampling and counting tasks Our dataset contained 100 d-DNNF circuits with weights. We have assigned random weights to literals wherever weights were not readily available. For the empirical evaluation of Teq. needed pairs of weighted d-DNNFs with known drv distance. To generate such a dataset, we first chose a circuit and a weight function, and then we synthesized new weight functions using the technique of one variable perturbation, described in the appendix Section B.1
https//github.cmm/meeeggguuuuu/u
hupp:///enndooongrrrc/////77770

---

drv S
drv 2 1
Benchmark
Result
Teq(s)
Result
Teq(s)
or 01-70-10-8-UC-I1
A
23.2
22.82
s641_15. _5_
A
33.66
R
33.51
or-50-5-4
A
414.17
R
408.59
ProjectService3
A
356.15
356.14
s713_15_7
A
24.86
R
24.41
or 10000000-20
31.04
31.0
s1423a
A
153.13
R
152.81
s1423a 7_4
A
104.93
103.51
or-50-5-10
A
283.05
R
282.97
0r-60-20-6-UC-20
363.32
362.8
Table 2: Runtime performance of Teq. We experiment with 100 PCs with known drv, and out of the 100 benchmarks we display 10 in the table and the rest in the appendix B In the table 'A" represents Accept and 'R' represents Reject. The value of the closeness parameter is 0.01 and the farness parameter 1= 0.2.
Results We set the closeness parameter farness parameter y and confidence d for Teq to be 0.01, 0.2 and 0.01, respectively. The chosen parameters imply that the input pair of probabilistic circuits are I 0.01 close in drv, then Teq returns Accept with probability atleast 0.99, otherwise the circuits are 2 0.2 far in drv, the algorithm returns Reject with probability at least 0.99. The number of samples required for Teq (indicated by the variable only on E, 17. 8 and for the values we have chosen, we find that we require m 294 samples.
line of Algorithm I depends
Our tests terminated with the correct result in less than 3600 seconds on all the PCs we experimented with. We present the empirical results in Table The first column indicates the benchmark's 's name, the second and third indicate the result and runtime of Teq when presented with pair of e-close PCs as input. Similarly, the fourth and fifth columns indicate the result observed runtime of Teq when the input PCs f7-far The full set of results are presented in the supplementary Section B
5 A characterization of the complexity of testing
In this section, we characterize PCs according to the complexity of closeness and equivalence testing. We present the characterization in Table The results presented in the table be separated into (1) hardness results, and (2) upper bounds. The hardness results, presented in Section [5.2] are largely derived from known complexity- -thooriitt results. The upper bounds, presented in Section [..] are derived from combination of established results, our algorithm Teq and the exact equivalence test of Darwiche and Huang (13 (presented in supplementary Section A. for completeness).
5.1 Upper bounds
In Table we label the pair of classes of PCs that admit a poly-time closeness and equívalence test with green symbols C and F. respectively. Darwiche and Huang [13] provided equivalence test for d-DNNF s. From Theorem [ we know that PCs that supports the Awct and Samp queries in poly-time must also admit poly-time approximate equivalence test. A weighted model counting algorithms for d-DNNFs was first provided by Darwiche [[]] and weighted sampler was provided by (17] Arenas al. (1) provided the first approximate counting and uniform sampling algorithm for SDNNFs. Using the following lemma, we show that with the use of chain formulas, the uniform sampling and counting algorithms extend log-linean SDNNF distributions well.
Lemma 3. Given SDNNF formula ip (with v-tree T), and weight function w, Samp(p,, w) requires polynomial time in the size of sp
The proof is provided in the supplementary Section A.5

---

NNF
P1
DNNF
SDNNF
d-DNNF
NNF
EC
PI
EC
00
DNNF
EO
FU
EU
SDNNF
EC
EU
EU
EC
d-DNNF
EC
0U
EU
EC
EC
Table Summary of results. C (resp. E) indicates that a poly-time closeness (resp. equivalence) test exists. C (resp. E) indicates that poly-time closeness (equivalence) test exists only if PH collapses. " indicates that the existence of a poly-time test is not known. The table is best viewed in color.
5.2 Hardness
In Table we claim that the pairs of classes of PCs labeled with symbols C and cannot be tested in poly-time for closeness equivalence, respectively. Our claim assumes that the polynomial hierarchy (PH) does collapse. To prove the hardness of testing the labeled pairs, we combine previously known facts about PCs and a few new arguments. Summarizing for brevity,
We start off by observing that PC families are in hierarchy, with CNF C NNF and DNF C SDNNF DNNF [14.
We then reduce the problem of satisfiability testing of CNFs (NP-hard) and validity testing of
DNFs (co-NP-hard) into the problem of equivalence and closeness testing of PCs, in Propo-
sitions 12 and These propositions and their proofs can be found in the supplementary
Section
We then connect the existence of poly-time algorithms for equivalence to the collapse of PH via complexity result due to Karp and Lipton 18
The NP-hardness of deciding the equivalence of pairs of DNNFs and pairs of SDNNFs was first shown by Pipatsrisawat and Darwiche (28). We recast their proofs in the language of distribution testing for the sake of completeness the supplementary Section|..5
Conclusion and future work
In this paper, studied the problem of closeness testing of PCs. Before our work, poly-time algorithms were known only for the special case of equivalence testing of PCs; and, no poly-time closeness test was known for any PC. We provided the first such test, called Teq, that used ideas from the field of distribution testing to design a novel algorithm for testing the closeness of PCs. We then implemented prototype for Teq, and tested it publicly available benchmarks to determine the runtime performance. Experimental results demonstrate the effectiveness Teq in practice.
We also characterized PCs with respect to the complexity of deciding equivalence and closeness. We combined known hardness results, reductions, and our proposed algorithm Teq to classify pairs of PCs according to closeness and equivalence testing complexity. Since the characterization is incomplete, as seen in Table 3 there are questions left open regarding the existence of tests for certain PCs, which we leave for future work.
Broader Impact
Recent advances in probabilistic modeling techniques have led to increased adoption of the said techniques in safety-critical domains, thus creating need for appropriate verification and testing methodologies. This paper seeks to take a step this direction and focuses on testing properties of probabilistic models likely find use in safety-critical domains. Since our guarantees probabilistic, practical adoption of such techniques still requires careful design to handle failures.

---

Acknowledgments and Disclosure of Funding
We are grateful the anonymous reviewers of UAI 2021 and NeurIPS 2021 for their constructive feedback that greatly improved the paper. We would also like to thank Suwei Yang and Lawqueen Kanesh for their useful comments on the earlier drafts of the paper. This work was supported in part by National Research Foundation Singapore under its NRF Fellowship Pro URFFAI1-2019-000 ] and AI Singapore Programme RAISG-RP-2018-003 and NUS ODPRT Grant [R- IR-252-0000688-13) The computational work for this article was performed on resources of the National Supercomputing Centre, Singapore (https://www.nscc..g
10

---

References
[1] Marcelo Aremas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. When is Approximate Counting for Conjunctive Queries Tractable? In STOC, 2021.
[2] Dominik Aronsky and Peter J Haug. Diagnosing community-acquirer pneumonia with bayesian network. In Proceedings of the AMIA Symposium, 1998.
[3] Rafael Cano, Carmen Sordo, and José M Gutiérrez. Applications of bayesian networks in meteorology. In Advances in Bayesian networks. 2004.
[4] Clément Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data. In Automala, Languages, and Programming, 2014.
[5] Clément L Canonne. A survey distribution testing: Your data is big. but is it blue? Theory of Computing, 2020.
[6] Clément I. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Testing bayesian networks. IEEE Transactions on Information Theory, 2020.
[7] Sourav Chakraborty and Kuldeep Meel. On testing of uniform samplers. In AAAL, 2019.
[8] Supratik Chakraborty, Dror Fried, Kuldeep $ Meel, and Moshe Y Vardi. From weighted to unweighted model counting. In IJCAI, 2015.
[9] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. 2020.
[10] Karine Chubarian and György Turán. Interpretability of bayesian network classifiers: Obdd approximation and polynomial threshold functions. In ISAIM, 2020.
[1]] Adnan Darwiche. On the tractable counting of theory models and its application truth maintenance and belief revision. Journal of Applied Non-Classical Logics, 2001.
[12] Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 2003.
[13] Adnan Darwiche and Jinbo Huang. Testing equivalence probabilistically. In Technical Report, 2002.
[14] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. JAIR, 2002.
[15] Saikat Dutta, Owolabi Legunsen, Zixin Huang, and Sasa Misailovic. Testing probabilistic programming systems. In Proc. of Joint Meeting on ESE and FSE, 2018.
[16] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks, 2014.
[17] Rahul Gupta, Shubham Sharma, Subhajit Roy, and Kuldeep Meel. Waps: Weighted and projected sampling. In TACAS, 2019.
[18] Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In STOC, 1980.
[19] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[20] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. arXiv preprint /207vv1207.608.8 2012.
[21] Zinan Lin, Ashish Khetan, Giulia Fanti, and Sewoong Oh. Pacgan: The power of two samples in generative adversarial networks. NeurIPS, 2018.
[22] Kuldeep S. Meel(, Yash Pote ①, and Sourav Chakraborty. On Testing of Samplers. In NeurIPS, 2020.
11

---

[23] Andrzej S. Murawski and Joël Ouaknine. On probabilistic program equivalence and refinement.
In Martín Abadi and Luca de Alfaro, editors, CONCUR, 2005.
[24] K.P. Murphy, Machine Learning: A Probabilistic Perspective. MIT Press, 2012.
[25] Agnieszka Oniško, Marck Druzdzel, and Hanna Wasyluk. Extension of the hepar ii model to multiple-disorder diagnosis. In Intelligent Information Systems. 2000.
[26] Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In ICML, 2020.
[27] Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp. Kristian Kersting, and Zoubin Ghahramani. Random sum sum-proode pon-prdduct networks: A simple and effective approach to probabilistic deep learning. In UAL. PMLR, 2020.
[28] Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based on structured decomposability. In AAAI, 2008.
[29] Arthur R Pope and David G Lowe. Probabilistic models of appearance for 3-d object recognition. International Journal of Computer Vision, 2000.
[30] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint
2015.
[31] Yasir Rahmatallah, Frank Emmert-Strett and Galina Glazko. Gene sets net correlations analysis (gsnca): multivariate differential coexpression test for gene sets. Bioinformatics, 2014.
[32] Dan Roth. On the hardness of approximate reasoning. Arlificial Intelligence, 82(1-2), 1996.
[33] Nicolas Städler and Sach Mukherjee. Multivariate gene-set testing based graphical models. Biostatistics, 2015.
[34] Larry J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 1976.
[35] Weiwei Yin, Swetha Garimalla. Alberto Moreno, Mary R Galinski, and Mark P Styczynski. tree-like bayesian structure learning algorithm for small sample datasets from complex biological model systems. BMC Systems Biology, 2015.
12


Reviews:
[{"review_id": "jx1r5r8Qqsf", "reviewer": "Reviewer_LJEd", "summary": "This paper presents a statistical closeness test for evaluating whether the total variation distance between the probability distributions encoded by two circuits is below a lower threshold or above an upper threshold with a given confidence in polynomial time. The authors introduce the setting, present the algorithm and give a sample of the analysis by proving parts of the main result. The results are evaluated on public datasets.", "questions": "", "limitations": "", "rating": 6, "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 problem addressed in this paper is certainly an interesting and relevant one. The paper motivates this well. It is clearly written, definitely not an easy read, but there is nothing particularly problematic about it. I could get through it within reasonable time and effort. I could follow the main flow of the arguments and at a high level and they seem sound. \n\nRegarding the originality I think there are two points of view that can be expressed here.\nFrom the point of view of testing structured distributions, the approach is quite novel given that the early stage of the state of the art on this problem. From the point of view of distribution closeness testing, the approach seems to follow relatively established lines, the contribution seems to be to account for the type of queries that are typically supported by common circuit families. One relatively important line of criticism is that the approach doesn't really account for the structured nature of distributions encoded by circuits. This is instead hidden under the oracle assumptions. Presumably, an algorithm that can unpack some of that structure would have greater significance on the field. This is not all bad though --- perhaps the fact can be interpreted as indicative that there is a lot more potential here, and perhaps this paper could provoke some follow-up research.\n\nFinally, I think it's important to sweep through a gird of epsilon, eta, delta configurations evaluating the probability of failure (i.e. fixing delta, running the test multiple times and evaluating the actual probability of failure empirically) to see whether the bound provides a good qualitative characterization. It's also interesting to see how the runtime of the oracle implementation behaves as a function of the parameters.\n\nA few nits from the paper:\n* Definition 1 presents either a typo or a horrendous abuse of notation.  The assignment sigma is defined as a binary vector, yet the sum iterates over x in sigma as if sigma is a set. In the subsequent expression, the letter x is used to both represent the symbolic variable as a member of the set X (as in w(x)) and its value as a binary (as in x=1). A better notation here is to use \\sum_x \\in X { w(x) if \\sigma(x) = 1 as in \"the x'th coordinate of sigma is 1\".\n* the paper mentions that the problems in the dataset are publicly available. I did not find a reference to them if that is the case.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be good if the authors discuss how the structure of circuits might impact efficiency (apart from lowering the cost of counting/evaluation).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "999"}, "extra_text": {}}, {"review_id": "VXCtSkBfVtH", "reviewer": "Reviewer_KnQP", "summary": "The contribution of this paper is a method for testing the closeness\nof the probability distributions encoded by two different\nprobabalistic circuits (PCs). The closeness tester (called Teq),\nassumes access to an approximate weighted counter and an approximate\nweighted sampler. Teq is described (in words and pseudo-code) and the\nbulk of the paper is devoted to proving (PAC-style) correctness of Teq\n(ie Theorem 1) and characterising its time complexity (Theorem\n2). Empirical results are given supporting the correctness of Teq and\nthe stated time complexity theoretical results on Teq.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "I think probabilistic circuits are an important probabilistic\nrepresentation. The authors tell us that \"Determining the closeness of\nmodels has applications in AI planning [12], bioinformatics [29, 31,\n33] and probabilistic program verification [14, 21].\" and I am\nprepared to trust them, but it would have been better to include some\nindication of how closeness results are used in applications (I\nappreciate space is short!) This is briefly alluded to in the 'broader impact' section.\n\nThe goal of the paper is sufficiently important, so it remains to\nconsider whether the paper is technically correct and written clearly\nenough. The Teq algorithm is clearly described, and the algorithm\nitself is nice and straightforward: the hard work is ensuring that\nTheorem 1 is correct (eg m, the number of samples, is big enough). I\ndid check the proof and found no errors (but max should be \\max on\nline 194); the empirical results provide further evidence that neither\nthe authors or I have missed errors in the proof.\n\ntypos:\n\n138: lesser than -> less than\nrefs: fix capitalisation, eg bayesian -> Bayesian", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they point to applications in safety-critical testing and note that care must be taken when applying probabilistic results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "RuawZeGAYUH", "reviewer": "Reviewer_LYkj", "summary": "This paper proposes a polytime probabilistic algorithm for testing the closetness of two probabilistic circuits (e.g., such as those based on weighted d-DNNFs).  This is the first such algorithm for a probabilistic circuit (whereas some have been known for their propositional analogues).\n", "questions": "", "limitations": "", "rating": 6, "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 premise of the paper is simple: provide a polytime test whether two probabilistic circuits are equivalent.  To my knowledge, no such test existed before, and it should be useful.  For example, it could be useful to perform caching when learning a probabilistic circuit from data.  Hence, I believe there is agood chance this test could be the basis of useful future work.\n\nThe testing procedue itself seems relatively simple, and an analysis of its correctness is provided, tho I did not check the details.\n\nI believe I have a question on the empirical evaluation, and how significant it is.  In particular, the paper says that in order to evaluate benchmarks with a known distance, a \"one variable perturbation\" scheme was used to synthesize a dataset.  It appears, according to the appendix, that this will perturb the weights of a single variable.  Is this a good enough test for the proposed algorithm?  Are we ultimately drawing samples from a probabilistic circuit, and then drawing enough of them (based on the marginal distribution of the individual variable) and then testing to see if that one particular pair of weights is close or not?\n\nI would find an evaluation based on small enough d-DNNF circuits where the distance could be evaluated brute-force to be more compelling.  The instances could be simulated by learning two PCs from different datasets drawn from the same distribution.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "ok", "review_text": "", "extra_scores": {"ethical_concerns": "ok", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8Gg_HBjsk1T", "reviewer": "Reviewer_3D6J", "summary": "This paper proposed a polynomial-time algorithm to check the closeness of two probabilistic circuits (PCs) with respect to the total variation distance metric, given that the PCs support tractable approximate counting and sampling. Experiments on benchmarks show that the algorithm is efficient in practice.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This paper identifies and studies a very interesting theoretical problem, namely testing the closeness of two PCs with respect to the total variation distance. To solve this task, the authors propose a polynomial-time algorithm, which could be potentially applied in other tasks such as structure-learning for PCs. The overall structure of the proofs and the intermediate results do not have obvious flaws, but the proofs are a little bit hard to follow in detail. I would recommend the authors to replace the actual proofs by the more intuitive sketch-proofs and move the details and computations to the appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There shouldn't be any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recognized the value of having an approximate testing scheme to compute the total variation distance between two weighted d-DNNF formulas. 

During the discussion, a number of suggestions to strengthen the work before being published has been highlighted. Namely, these include

  - fixing the presentation by properly comparing general probabilistic circuits (PCs, as defined in Choi et al.) and the weighted d-DNNF formulas used in this work, e.g., by discussing how the proposed methods can be extended from such weighted boolean circuits to general PCs
  - adding synthetic experiments with small-scale d-DNNF to compare against a ground truth
  - adding real-world experiments with PCs learned from data to show generality
  - performing a grid search over the several hyperparameters 
  - refactoring the proofs as to provide a more high level introduction

As the authors promised some content/results but they did not provide it during the rebuttal phase, the paper is accepted subject to incorporating this content.
Decision: Accept (Poster)