On the Expressive Power of Tree-Structured Probabilistic Circuits
Authors: Lang Yin
Han Zhao
Venue: NeurIPS 2024 poster (2024)
Keywords: Probabilistic circuits
Circuit complexities
Network polynomials
Probabilistic models
Primary area: probabilistic_methods
TL;DR: Our paper proves a universal upper bound and a conditional lower bound for the expressive power of tree-structured probabilistic circuits.

Abstract: Probabilistic circuits (PCs) have emerged as a powerful framework compactly representing probability distributions for efficient and exact probabilistic inference. It has been shown that PCs with general directed acyclic graph (DAG) structure can be understood as a mixture of exponentially (in its height) many components, each of which is a product distributions over univariate marginals. However, existing structure learning algorithms for PCs often generate tree-structured circuits, or using tree-structured circuits as intermediate steps to compress them into DAG-structured circuits. This leads to an intriguing question on whether there exists an exponential gap between DAGs and trees for the PC structure.

In this paper, we provide a negative answer to this conjecture by proving that, for $n$ variables, there is a quasi-polynomial upper bound $n^{O(\log n)}$ on the size of an equivalent tree computing the same probability distribution. On the other hand, we will also show that given a depth restriction on the tree, there is a super-polynomial separation between tree and DAG-structured PCs. Our work takes an important step towards understanding the expressive power of tree-structured PCs, and our techniques may be of independent interest in the study of structure learning algorithms for PCs.

On the Expressive Power of Tree-Structured Probabilistic Circuits
Lang Yin
Han Zhao
Department of Computer Science University of Illinois trbana-Champaign langyin201 itriiin@11llim wwwiiniin.................i....e
Department of Computer Science
University of Illinois Jrbana-Champaln Manzhao@illm lliniiii....... ainoissedu .dd
Abstract
Probabilistic circuits (PCs) have emerged as a powerful framework to compactly represent probability distributions for efficient and exact probabilistic inference. has been shown that PCs with general directed acyclic graph (DAG) structure be understood as a mixture of exponentially (in its height) many components, each of which is product distribution over univariate marginals. However, existing structure learning algorithms for PCs often generate tree-structured circuits or use tree-structured circuits as intermediate steps compress them into DAG- structured circuits. This leads to the intriguing question of whether there exists exponential gap between DAGs and trees for the PC structure. In this paper, we provide a negative answer to this conjecture by proving that, for n variables, there exists a quasi-polynomial upper bound n. o(ogg n) on the size of an equivalent computing the same probability distribution. On the other hand, also show that given a depth restriction on the tree, there is a super- sopeer-olyyooiall separation between tree and DAG-structured PCs. Our work takes an important step towards understanding the expressive power of tree-structured PCs, and our techniques may be of independent interest in the study of structure learning algorithms for PCs.
Introduction
Probabilistic circuits (PCs) 7 29 also commonly known as sum product networks (SPNs) [24]. a type of deep graphical model that allow exact probabilistic inference efficiently in linear time with respect to the size of the circuit. Like other deep models, the parameters of a PC can be learned from data samples [8 Because of these desirable properties, they have been increasingly applied in various contexts, including generative modeling [35], image processing [2] 334, robotics [30],
planning (25) and sequential data including both textual and audio signals 6 23 Compared with
deep neural networks, the sum and product nodes in PCs admit clear probabilistic interpretation (36)
of marginalization and context-specific statistical independence (3), which opens the venue of design- ing efficient parameter learning algorithms for PCs, including the
(EM)
algorithm [12), the convex-concan procedure (CCCP) (38), and the variational EM algorithm [37].
Perhaps one of the most important properties of PCs is that they can be understood as a mixture of exponentially (in its height) many components, each of which is product distribution
univariate marginals (38. Intuitively, each sum node in PC can be viewed as hidden variable that encodes mixture model (36] and thus a hierarchy of sum nodes corresponds
an exponential number of components. This probabilistic interpretation of PCs has led to a number of interesting structure learning algorithms I
22 27 However, almost all of the existing structure learning algorithms for PCs output tree-structured circuits, or use tree-structured circuits as intermediates to compress them into D cireuits. Because of the restricted structure of trees, such algorithms do not fully exploit the expressive power of PCs with general DAG structures, and often
13 17
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

output tree- stee-strutturd PCs with exceedingly large sizes 13 Yet, from theoretical perspective, it remains open whether there truly exists an exponential gap between DAGs and trees for the PC structure. Being able to answer this question is important for understanding the expressive power of tree-structured PCs, and may also lead to new insights in structure learning algorithms for PCs.
1.1 Our Contributions
In this work we attempt to answer the question above by leveraging recent results in complexity theory [TI 33. Our contributions are two-folds: an upper and lower bound for the gap between tree and DAG-structured PCs. In what follows we will first briefly state our main results and then introduce the necessary concepts and tools tackle this problem.
An Upper Bound In Section 3 inspired by earlier works in Valiant et al. [33] and Raz and Yehudayoff [26), we show that, for a network polynomial that can be computed efficiently with DAG-structured PC, there always exists a tree-structured PC of a quasi-polynomial size to represent it. An informal version of our main result for this part is stated below.
Theorem 1.1 (Informal). Given a network polynomial of n variables, if this polynomial can be computed efficiently by a PC of size poly(n), then there exists equivalent tree-structured PC of depth O Olog n) and of size (llggn that computes the same network polynomial.
We prove this result by adapting the proof in Raz and Yehudayoff (26). Our construction involves two phases: Phase one applies the notion of partial derivatives for general arithmetic circuits to represent intermediate network polynomials alternatively, and construct another DAG-structured PC using those alternative representations; we will provide fine-grained analysis on the new DAG, such that its depth is O(log n) and its size still (oly(n). Phase two applies the standard duplicating strategy for all nodes with more than one parent to convert the new DAG into a tree. This strategy will lead to an exponential blowup for an arbitrary DAG with depth D, since the size of the constructed tree will be n (D)) However, note that the DAG constructed in the first phase has depth Olog n). Combining it with the duplicating strategy, we will be able to construct an equivalent tree-structured PC of size upper bounded by n (logn), as desired.
The original algorithm in Raz and Yehudayoff (26) only reduces the depth to Olog" n.) due their restriction on the graph of using nodes with at most two children. This restriction is not necessary for PCs, and by avoiding we show that the depth can be further reduced to Olog n) with a slight modification of the original proof in Raz and Yehudayoff [26].
A Lower Bound In Section 4, we show that under restriction the depth of the trees, there exists a network polynomial that can be computed efficiently with a DAG-structured PC, but if a tree-structured PC computes it, then the tree must have a super-polynomial size. The following informal theorem states our main result for this part, which will be formally addressed Section
Theorem 1.2 (Informal). Given n random variables. there exists network polynomial those variables, such that it can be efficiently computed by a PC of size Onn log n) and depth O(log n), but any tree-structured PC with depth o(log n.) computing this polynomial must have size at least (1)))
Our result is obtained by finding a reduction to Fournier et al. [T]. We first fix an integer k and a network polynomial of degree n 22 To show that the polynomial is not intrinsically difficult to represent, i.c., the minimum circuit representing it shall be efficient, we explicitly construct a PC of depth (log n) and size (n log n). Next, suppose via black box, we have a minimum tree-structured PC of depth o(log n) computing this polynomial. After removing some leaves from that minimum tree but maintaining its depth, we recover a regular arithmetic tree that computes a network polynomial of degree vn- 2* Moreover, as shown in [1] if an arithmetic tree with depth o(log n) computes this low-degree polynomial, then the size of the tree must be at least nI))), Our operations on the minimum tree PC must reduce size; therefore, the original tree must have a larger size than (1), and this fact concludes our proof.
1.2 More Related Work
There an extensive literature on expressive efficiency network structures for PCs and probabilistic generating circuits (PGCs) (35, another probabilistic graphic model. Very recently, it was shown in

---

Broadrick et al. [4] that PCs with negative weights are as expressive as PGCs. The investigation on PCs has started as early as in Delalleau and Bengio [8] and later in Martens and Medabalimi [99] In neural networks and variants, this topic, along with the relationship between expressive efficiency and depth/width, has attracted many interests as well
16
18
20
21
28
31 32]. In particular,
Martens and Medabalimi [19 Theorem 34] has shown that there exists network polynomial with a super-poly poper-polynomial minimum tree expression, but it is unclear whether the same polynomial can be computed by a polynomial-sized DAG. Our work provides a positive answer to this question. For arbitrary network polynomials, finding a minimum DAG-structured PC is reducible to a special case of the minimum circuit size problem for arithmetic circuits, which remains to be longstanding open problem in circuit complexity.
2 Preliminaries
We first introduce the setup of probabilistic circuits and relevant notation used in this paper: Notation A rooted directed acyclic (DAG) graph consists a set of nodes and directed edges. For such edge + E, we say that is parent of e, and v is child of u. We use Ch(u) to denote the set of children of the node u. We say there is a directed path from a to if there is an edge a + b or there are nodes uI.... Ug and edges a U1
Uy + b; in this case, say that is an ancestor of b and that b is a descendani of a. If two vertices v and w are connected via a directed path, we call the number of edges in shortest path between them the distance between them, denoted by dist (v; w²). A directed graph is rooted if one and only one of its nodes has no incoming edges. A leaf in a DAG is a node without outgoing edges. A cycle in a directed graph is directed path from a node to itself, and a directed graph without directed cycles is DAG. For two disjoint sets A and B, we will denote their disjoint union by A U B to emphasize their disjointedness.
Clearly, each directed graph has an underlying undirected graph obtained by removing arrows on all edges. Although by definition, DAG cannot have a directed cycle, but its underlying undirected graph may have an undirected cycle. If the underlying undirected graph of a DAG is also acyclic, then that DAG is called a directed tree. Every node in a directed tree has most one parent. If two nodes share a parent, one is said to be a sibling of the other.
Complexity Classes In what follows we introduce the necessary complexity classes that will be used throughout the paper. Let (n) be the runtime of an algorithm with input size n.
A function fn) is in the polynomial class poly(n) f(x) O(n") for a constant & E N.
A function (n) is in the super-polynomial class if (n) is not asymptotically bounded above by any polynomial. Formally, this requires (n) E w(n") for any constant c > 0, i.e.
f(m) co for any c >>( 0. limn ne
A function f(n) is in the quasi-polynomial class if it can be expressed in the form 20oly(logn),
A function ((n is in the exponential class if it can be expressed in the form (0poly(
Probabilistic Circuits A probabilistic circuit (PC) is probabilistic model based on a rooted DAG. Without loss of generality, in our work, we focus on PCs over Boolean random variables. We first introduce the notion of network polynomiul. For each Boolean variable X, we use the corresponding lower case alphabet x to denote the indicator of X, which is either 0 or I; for the same variable, x represents the negation. In many cases, we use 1 : N to denote the index set [N]. A PC over Boolean variables (X,,... )x,) computes a polynomial over the set of indicators {01.- En, Zi, ....,,,,) } we will refer this polynomial as the network polynomial. In the network, the leaves
indicators of variables, and all other nodes are either sum or product nodes; a node that is not a leaf may also be called an internal node. Each internal node computes polynomial already: a sum node computes a weighted sum of the polynomials computed by its children, and a product node computes the product of the polynomials computed by its children. A PC is said to be normalized if the weights of the outgoing edges from a sum node sum to one. It was shown in Zhao et al. [36] that, every unnormalized PC can be transformed into equivalent normalized PC within linear time.
To represent valid probability distributions, a PC must satisfy two structural properties: decompos- ability and smoothness. To define them, we need to define the scope of a node, which is the set of
3

---

fo = fu fw
fw Owr fo
fw fufu
221
Figure 1: Partial derivatives of sum nodes.
variables whose indicators are descendants of that node. For node v, if the indicator x of the variable X is one of descendants of v, then X E scope(u); more generally, scope(v) = Uv'Cc((v) scope (1').
Definition 2.1 (Decomposability and Smoothness). A PC is decomposable if and only if for every product node u and any pair of its children in and v2, we have scope( n scope(v2) 0. PC is smooth if and only if for each sum node, all of its children have the same scope.
In this paper restrict attention to PCs that both decomposable and smooth, since otherwise we can always transform a PC into an equivalent one that is both decomposable and smooth in quadratic time (36] The degree of monomial is the degree of a polynomial f. denoted by deg(f) is the highest degree among its constituent monomials. polynomial is said be homogeneous if all of its monomials have the same degree. PC is said to be homogeneous if all of its sum and product nodes compute a homogeneous polynomial. Later, will show that decomposability and smoothness imply homogeneity, and vice versa with mild conditions. For node in a PC, we use (eg(v) to denote deg(fv). As emphasized earlier, this paper investigates the quantitative relationship between DAG and tree, which are both PCs and represent the same probability distribution. To make the terminology uncluttered, we will call the former DAG-structured PC, and the latter a tree PC. If a tree PC computes the same network polynomial as a DAG-structured PC, then the tree PC is said to be an equivalent tree PC with respect to that DAG-structured PC.
of the exponents of all its variables, and the
Unless specified otherwise, we will use & to denote the entire PC in consideration and f the network polynomial computed by the root. For each node v, the sub-network rooted is denoted by Φ, and the polynomial computed by is fu. The set of variables in Se is X.,, which is subset of {X1,... ). The size of the network &. denoted by [0), the number of nodes and edges in the network. The depth of 4 denoted by (()), is its maximum length of a directed path.
Partial Derivatives In the process of proving the upper bound, key notion named partial derivative is frequently used and formally defined below.
Definition 2.2 (Partial Derivative). For two nodes and w in a network the partial derivative of the polynomial fo with respect to the node w, denoted by f is constructed by the following steps:
1. Substitute the polynomial fw by new variable y.
2. Compute the polynomial computed by e with the variable y; denote the new polynomial by
f.r Due decomposability, for is linear in y.
3. Define the partial derivative Ow alv
By
Observe that the chain rule in calculus also holds for our notion here, and therefore leads to the two following facts.
Let be node with children U1 and U2, and the edges have weight an and az, respectively, then by definition So = a1fm + 02svg- For any other node w, the partial derivative is f 0₁ a. + a2 Ow
Similarly, let o be a product node with children en and 02, then So = sv. Sug. For any other node w, we have Ow for Iwf + for d. fuf

---

The partial derivative has been proven to be powerful tool in the field of complexity theory and combinatorial geometry [[4]5]] Readers are welcome to refer Chen et al. [5] for more details and extensive background. An illustration is provided in Figure I
Arithmetic Circuits An arithmetic circuit, aka algebraic circuit, is generalization of probabilistic circuit. Such circuit shares the same structure as PC and also computes network polynomial. If an arithmetic/algebraic circuit is a directed tree, then we call it an arithmeticcalgeeraae formula. In the proof of the lower bound, the notion of monotonicity of formula is essential, whose definition relies on the concept parse Iree.
Definition 2.3 (Parse Tree). A parse tree of formula t is a sub-formula of 4 which corresponds to a monomial of f. the network polynomial computed by t. Parse trees of & is defined inductively by the following process:
If the root of 4 is sum node, a parse tree of t is obtained by taking a parse tree of one of its children together with the edge between the rool and that child.
If the root of 4 is product node, a parse tree of is obtaieed by taking a parse tree of each of its children together with all outgoing edges from the root.
The only parse tree of a leaf is itself.
Definition 2.4 (Monotonicity). An algebraic formula is monotone if the monomial computed by any of its parse trees has non-negative coefficient in the network polynomial.
3 A Universal Upper Bound
In this section, present our first main result, which provides universal upper bound on the size of an equivalent tree versus a DtG-structured PC.
Theorem 3.1. For any given DAG-structured PC over variables and of size poly(n), there exists an equivalent tree-structured PC of size n (logn) nodes and of depth O(logn) n). computing the same polynomial.
As discussed earlier, our constructive proof heavily relies on deeper properties of partial derivatives, and applying them to represent sub-network polynomials. Our strategy, inspired by Raz and Yehuday- off (26). will be efficient if the circuit being considered is binary circuit, i.e. every node has at most two children. While such structure is rare for natural networks, we make the following observation, that an arbitrary PC can always be transformed to binary one with a polynomial increase in size and depth. The proof and an illustrating figure will appear in Appendix A
Lemma 3.2. Given a DAG- DAG-structured PC 4, we may transform it into another DAG 4' that computes the same network polynomial and every node in &' has at most two children. Moreover, the differences between the sizes and depths of d' and de are only in polynomial size.
Therefore, for the remaining discussion in this section, we will assume without loss of generality, that a given PC is binary. During the conversion process towards a binary circuit, some intermediate nodes may be created to ensure no sum node is connected another sum node and no product node is connected to another product node. The set those intermediate nodes is denoted by 2, and will be present in later discussions. Next, present key property of partial derivatives, which holds for any (including non- PC.
Lemma 3.3. Given PC 4, if v and
two nodes in & such that ow * O. then fw is homogeneous polynomial over the set of variables X, \ Xx of degree deg(v) deg(w).
The next lemma tells that, given a product node, its partial derivative with another node with a restriction on degree can be expressed using its children.
Lemma 3.4. Let u be product node and w be any other node in a PC 4. and deg(u) ) < 2 deg(ww. The children of are Un and v2 such that deg(v1) 2 deg(vz). Then 0, fu. Juz - S
To construct the quasi-polynomial tree, the key to compress many nodes with partial derivatives. Fundamentally, we will use the following results to show that such compression works because each node, and each partial derivative any node with any other, can be more concisely represented using partial derivatives. The key question is to find eligible nodes, so that taking partial derivatives with respect them will lead to compact expressions. Inspired by the observation Raz and Yehudayoff (26), we define the following set Gm, which will be critical in our later process.
5

---

Algorithm 1: Construction of
Data: The original DAG-structured PC d with variables of size poly(n), and the set of its
nodes V
Result: Another DAG-structured PC v of size poly(n) and depth O n)
i <- 0: 1/ < 0; P + d.
for i 0, flog n| do
Fix m. < 2";
Find all nodes v such that 2' < deg(v) < 2 and place them in V;
Find all pairs of nodes (u, w) such that 2 < deg(u) deg(w) s 2 and
deg(u) < 2 (deg(w), and place them in P:
for every u do | Find all nodes in Gm, and compute fo using Equation 15; end
for every pair of nodes (u, w) E P do
Fix (2.(u.)) 2$ + dog(w);
Find all nodes in (w..w and compute f using Equation 17; end
+ 0: -
end
Definition 3.5. Given a PC and an integer in N, the sei Gm the collection of product nodes I in & with children iı and l2 such that m deg(l) and max (,)g((1),eeg(()) S m.
With this set, we may choose set of nodes as variables for partial derivatives for any node in PC, and the following two lemmas respectively illustrate: 1) the compact expression of the sub-networt polynomial fo for any node v in a PC; 2) the compact expression Ow given two nodes u and w with degree restriction. It is easy observe that T n G.,. = 0.
We now present two key lemmas that will be central the proof for the upper bound. Specifically, they spell out the alternative representations for the network polynomial of any node, and the partial derivative of any pair of nodes.
Lemma 3.6 ((26). Let m E N and node u such that m deg(v) S 2m, then fo EIEG f. 0.
Lemma 3.7 ((26)) Let m E N, and v and w be two nodes such that deg(w) S m < deg(u) <
2 deg(;), then Sw ELeg.. Ov J.Ju.
3.1 Construction of V, another DAG-structured PC with restriction on depth
Given binary stG-structured PC with n variables and poly(n) nodes, we explicitly construct tree PC with size n (lin m) and depth Oloogn). Specifically, the construction takes two main steps:
1. Transform to another DAG-structured PC with size poly(n) and depth O(log n).
2. Apply a simple duplicating strategy to further convert to a tree with size n O(logn) and the same depth of V.
We will later show that step two can be simply done. Step one, however, needs much more careful operations. Each iteration, starting from = 0, again needs two steps:
1. Compute f. for each node such that 2 deg(v) < 2' using the compact expression illustrated earlier. We will show that, computing one such polynomial adds poly(n) nodes and increases the depth by most two on V. This new node representing f. will be node in V, denoted by v'.
2. Compute all partial derivatives fu for two non-variable nodes and w in Q such that is an ancestor of w and 2/-1 < deg(u) deg(w) < 2' and deg(u) < 2 deg(w), (w). Like those new nodes representing sub-network polynomials from 4 this new node representing partial derivative will also be node in Vr denoted by (u, w). We will show that computing partial derivative with respect to each pair adds poly(n) nodes and increases the depth by at most two V.

---

Algorithm 2: Transforming a rooted DAG to a tree
Data: A rooted DAG of size S and depth D, and the set of its nodes V A tree of size ()5D) ) and depth D)
Result:
for every node u in V do
if InDeg(e) > 1 then
Duplicate the tree rooted at e for InDeg(v) times;
Construct an outgoing edge from each parent of u to itself.
end end
The process is summarized in Algorithm|] I Before presenting the construction, we first confirm the quantitative information of Y, the output of the algorithm. The first observation is the number of iterations: The degree of the root of & is n. so most log iterations are needed for the entire process. Each iteration only increases the size of the updated circuit by (nly(n) and the depth by constant number. Consequently, the final form of has size poly(n) and depth Ologn).
We now provide an inductive construction of Y starting from i = 0. After each step, it is necessary to verify the validity of the updated V. A Although decomposability is easy verify, smoothness is less straightforward. To tackle this, we argue that the final state of Yp is homogeneous, i.e. every node in T computes homogeneous polynomial, and consequently Y is smooth due the following lemma.
Lemma 3.8. If a decomposable PC contains variables and computes a polynomial of degree n, then it homogeneous if and only if it is smooth.
Iteration zero (i 0): During this iteration, for the first step, we only need to consider nodes such that 0.5 < deg(v) < 1; the degree of any node must be an integer, so we must have deg(v) 1, ie. U represents an affine polynomial. Without loss of generality, we may assume all such affine nodes are sum nodes with strictly more than one child. Indeed, if product node represents an affine polynomial, then must only have exactly one child, which must be a leaf node; in this case, we may remove this product node and connect that leaf to the parents of the original product node. Similarly, a sum node represents an affine polynomial and has exactly one child, then that child must also be a Icaf node, hence we may again remove the original sum node. Due to smoothness, such an affine node v must represent a polynomial in the form az + (1 a)æ, where is the indicator of a variable, and 0 < a < 1. Therefore, the depth of each sub-network T only one. By duplicating all such affine nodes onto V, we add at most poly(n) nodes and increase the depth by one only.
node and connect that leaf to the parents of the
Next, for step two, we only need to consider pairs of nodes (u, w)) such that deg(u) deg(w) S 1. Thanks to Lemma 3.3 we know that Su is affine. For each pair satisfying the restriction, we create a sum node (u, w) whose sub-network ((u.w) has size three and depth one. By moving all such sub-networks to T for each eligible pair, we again add at most poly(n) nodes and increase the depth by one to V
Iteration i 4 1: Suppose. after all previous iterations, we have already computed all sub-network polynomials fo for nodes such that deg(v) S 2 and all partial derivatives Jw. for pairs of nodes (u, w) such that deg(u)- deg(w: < 2 and deg(u) < 2 deg(w). Like the base case, step i + 1 takes two steps: The first step computes fo for cligible nodes, and the second step concerns partial derivatives for eligible pairs of nodes. Because the analysis of the two steps during this iteration is highly involved, we will discussion the construction in details in Appendix A.7
3.2 Construction of the Quasi-polynomial Tree
We conclude the proof of Theorem 3.1 this section by transforming the newly constructed V into a quasi- toaas-pplyyomiil tree. The transformation is a simple application of the naive duplication strategy, which will be illustrated below. In summary, given a poly(n)-sized DAG, the size of the transformed tree directly depends on the depth of the original DAG. The process of the duplication is briefly summarized in Algorithm and the detailed process of the entire transformation from the original + to the final tree is described in Algorithm
7

---

Duplication Strategy Given a DAG-structured PC of size V and depth D, natural algorithm to tree is that, if node v has connect each duplicated sub-tree to parent of v. Indeed this algorithm generates tree computing the same function as the original DAG does, but in the worst case we have to duplicate the entire graph O(V) times and such iterative duplication may be executed for every layer from the first to layer D. Therefore, in the worst case, the final tree has size OVV)).
parents, then duplicate the sub-tree rooted at v for k 1 times, and
The construction of V shows that its size is ((n)) and depth is (log n). Using the naive duplication, we obtain that the size of the final tree is n (logg))
4 A Conditional Lower Bound
In this section, we present our second main result, which provides lower bound on the tree complexity of a network polynomial given restriction on the depth of the tree. Obtaining lower bound for the problem of circuit complexity in general a more difficult problem than obtaining an upper bound because one cannot achieve this goal by showing the failure of a single algorithm. Instead, one must construct specific polynomial, and confirm that no algorithm can produce an equivalent tree of size lower than the desired lower bound. However, thanks to some recent results in circuit complexity theory, such a separation is ensured if the tree PC has a bounded depth. The main result in this section is presented below, stating that, there is concrete network polynomial that cannot be represented by a polynomial-sizen
tree-structured PC if the depth of the tree restricted.
Theorem 4.1. Given an integer k: 2 1 and n. = 22k, there exists a network polynomial E T1, F..] of degree n = 22k, such that any probabilistic tree of depth o(log n) =
In, R[....... o(k) computing P must have size (1))
Note that if the polynomial P is innately difficult to be represented by PCs, i... if it cannot even be
represented efficiently by DAG-structured PCs, then separation is not shown. To show separation, P
should be efficiently computed by a DAG-structured PC, but any tree-structured PC representing P
must have strictly larger size. Our next construction, described with more details in Algorithm 3 confirms a separation by constructing an efficient DAG-ssruccuredd PC p* that computes P. This PC
has size (n log n) and depth 2k 2 log n, where k is the integer given in Theorem 4.1 The next
proposition confirms the validity of p* and the proof is in Appendix B
Proposition 4.2. The tree PC p is decomposable and smooth.
easy to check that pa has the correct size and depth as described earlier. Before adding leaf nodes, the algorithm in total constructs E²-0 2" = 22k+1 - 1 = 2n 1 nodes. Finally, observe that during the construction of leaf nodes, each negation indicator is added exactly k times: At layer containing only product nodes, if a negation indicator is added to a product node u at this layer, then it will next be added to the sibling of the grandparent of v. Because each product node has exactly one sibling, the negation indicator for random variable is duplicated exactly k times, and finally the total size is 2n 1 + kn = (km) O(n log n). The depth (kk) also apparent from the algorithm. We therefore conclude that P can be efficiently computed by polynomial sized tree PC for an unrestricted depth.
However, the efficiency would be less optimal if we restrict the depth to olk). To show this, we design reduction from problem for PCs to well-studied problem arithmetic circuits. Our proof essentially argues that, for any minimum-sized tree-structured PC that computes P. we can obtain its sub-tree that computes a polynomial, and that polynomial has been recently proven to not be able to be represented by a polynomial-sizee
tree-structured PC. This recent result is stated below.
Theorem 4.3 (II). Let n and d = d(n) be growing parameters such that d(n) S VT. Then there monotone algebraic formula F of size at most and depth Olog d) computing a polynomial Q E "[ =n]] of degree at most d such that any monotone formula F' of depth o(log d) computing Q musl have size (1).
The proof of the lower bound for PCs in Theorem 4.1 is to show that, for any II, a minimum tree- structured PC with depth o(k) that computes P, the polynomial in the statement of Theorem 4.1 we can always obtain a smaller-sized arithmetic formula IT' with the same depth that computes the polynomial Q in the statement of Theorem 4.3 The size of II' is super-polynomial due to
8

---

Algorithm 3: Construction of P", an efficient PC for P without depth constraint
Data:
A positive integer k, the number 2 set {x1,"" A2az, 31,
B2ze of 2
indicators
Result: A tree PC of size On log ni) and depth 2k 2 log r j
Place all non-negation indicators #1," Taa at the bottom layer; Label them as -.. L
for i 1,... log do
is odd then
while j < 22k do Construct product node labelled by L2((/22) and two outgoing edges from the new node 14-1. and 1,-1,
j j 2:
end
for every odd integer g 1,3, 22 do
Add the leaves representing negation indicators {0.} for all 2 E scope(Li, as children of Li.gi
Add the leaves representing negation indicators {x.} } for all 2 scope(Ligg) as children of Li,g+1;
end end
is even then while j < 2 do
Construct a sum node labelled by L4,15/2) and two outgoing edges from the new node to 1--15111 and Li-1,ji
j + j + 2:
end
end
end
Theorem 4.3] and result, the size of cannot be smaller. In other words, our proof involves reduction from the PC problem to the AC problem. Before introducing the reduction, we first present the polynomial in the statement of Theorem 4.3 The original construction Fournier al. [11] for the general class, but over here, we only present specific case with 2, which is sufficient for our purpose.
The Construction of the Polynomial Q We denote the polynomial Q by (kk22), which is defined over 22h variables
{ O, E [2]*}.
(1)
The polynomial (k.2) is recursively defined over intermediate polynomials Hu,v for all (u, v) [2] Sk and [u| = lo]. Specifically, if w/ |o then H,,v Fu,vi otherwise, Hu,e Ex=1 H Hu Hn The final polynomial H (R.2) defined to be Ha,g- Observe that the degree of (k.2) is 2h, and it contains 22" monomials.
Given minimum tree-structured PC which computes P and is of depth o(k), we remove all of its leaves that represent negation variables and call this pruned network II' without leaves representing negation variables, II' is just a standard arithmetic formula. Clearly, [IT'] < [I], and the next proposition reveals the polynomial computed by II', and its proof is in Appendix B
Proposition 4.4. The arithmetic formula II' computes H (R.2).
Having all the necessary ingredients, we are now ready to conclude this section by proving Theo- rem the main result of this section.
Proof of Theorem 4.1 The proof of Theorem in Fournier et al. ||| uses the polynomial class
H (k.r) as the hard polynomial Q in the statement. in particular, with 2, 2 and d(n)

---

=n= Note that the depth of II' is ollog d) = o(k), and the degree of H (k.2) is = 2 so the conditions in the statement of Theorem 4.1 are indeed satisfied. Since II' is obtained from II by removing leaves, we obtain the following inequality that concludes the proof:
[ z | 2 (1))
Conclusion
In this paper we have shown that given a network polynomial with n variables that can be efficiently construct a tree PC with at most polysmmaly size
computed by DAG-structured PC, and is no deeper than Ollog n). On the flip side, we have also shown that there indeed exists a polynomial that can be efficiently computed by a poly(n)--izze) PC without a depth restriction, but there is super-poll polyommal separation if we restrict the depth of the tree to be ollog n.). Our results make important step towards understanding the expressive power of tree-structured PCs and show that a quasi-polynomial upper bound is possible. However, the lower bound is still largely open, and we have only shown separation under specific depth restriction. One potential direction for the future work discussed below: although the upper bound n O(oog)) m) is quasi-polynomine polynomial, it is still prohibitively large as n grows. The construction outputs a tree of depth (log n). which would be considered as a shallow tree. Is possible to further reduce the size of the tree, possibly in the cost of a larger depth?
Acknowledgement
HZ would like to thank the support from a Google Research Scholar Award.
References
[1] Tameem Adel. David Balduzzi, and Ali Ghodsi. Learning the structure of sum- sum-product networks via an svd-based algorithm. In Conference on Uncertainty in Artificial Intelligence, 2015. URL https://app: sewanticschooee..e......e org/ wttg/CorpusID::: 15429402
[2] Mohamed R Amer and Sinisa Todorovic. Sum product networks for activity recognition. IEEE transactions on pattern analysis and machine intelligence, 38(4):800-81) -130008811,12 2015.
[3] Craig Boutilier, Nir Friedman, Moises Goldszmidt, and Daphne Koller. Context-specific independence in bayesian networks. arXiv preprint 102.5:130..3562, 2013.
[4] Oliver Broadrick, Honghua Zhang, and Guy Van den Broeck. Polynomial semanties of tractable probabilistic circuits. In Conference on Uncertainty in Artificial Intelligence, 2024. URL https://starai.
ucla. edu/ wal.aa.ddpppppppe http://ppppeeeerrrrctutAAA/
pdf
[5] Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Found. Trends Theor. Compur. Sci., 6(1-2):1-138 2011. doi: 10. 10.1561/04000000433 URI https:/tt:/// org/ 10. 1561/0400000043,
[6] Wei-Chen Cheng, Stanley Kok, Hoai Vu Pham, Hai Leong Chieu, and Kian Ming A Chai. Lan- guage modeling with sum- networks. In Fifteenth Anmual Conference of the International Speech Communication Association, 2014.
[7] Y Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifyyng framework for tractable probabilistic models. UCLA. URL: http://starai. cs. ucla. edudpapers/ProbCic22. pdf. 2020.
[8] Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS' 11, page 666-67 674, Red Hook, NY, USA, 2011. Curran Associates Inc. ISBN 9781618395993,
[9] Aaron Dennis and Dan Ventura. Learning the architecture of sum-product networks using clustering on variables. F. Pereira, C.J. Burges, L.. Bottou, and K.Q. Weinberger, edi- tors, Advances in Neural Information Processing Systems, volume 25. Curran Associates,
10

---

Inc.. 2012. URL /ttpp//pp///p.ccccccasss www.pig.......pi...oo..
pdf
[10] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
[11] Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas. Towards optimal depth-reductions for algebraic formulas. In Proceedings the Conference on Proceedings of the 38th Computational Complexity Conference, CCC '23, Dagstuhl, DEU, fuer Informatik. ISBN 9783959772822. doi: 10. URL https://doll org/ 4230/LIPIcs CCC 2023.22 28
2023. Schloss Pegstuul--eibniz--DA 1.S0LIIPcss.CCC.22222.
[12] Robert Gens and Pedro Domingos. Discriminative learning of sum-product networks. Advances in Neural Information Processing Systems, 25, 2012.
[13] Robert Gens and Domingos Pedro. Learning the structure of cum-product networks. In International conference on machine learning, pages 873-880. PMLR, 2013.
[14] Larry Guth and Nets Hawk Katz. Algebraic methods in discrete analogs of the kakeya problem. Advances in Mathematics, 225(5):2828-283) 2010. ISSN 0001-8708, doi: https://doi.on org// htt.:///...i..2110.0..00 p11//$00018708100000944
URL htwph:ttp///t wcwencedirecct.................. com/ wwomm//cinceeeeeooooomoooooooeee wwriienneaaaiiciiee
[15] Haim Kaplan, Micha Sharir, and Eugenii Shustin. On lines and joints. Discrete and Computa- lional Geometry, 44(4):838-844 843, 2010. ISSN 0179-5376. doi: 10. 1010077000444--1--9446--4
[16] Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. Curran Associates Inc., Red Hook, NY, USA, 2019.
[17] Sang-Woo Lee, Min-Oh Heo, and Byoung- Tak Zhang. Online incremental structure learning of sum-product networks. volume 8227, pages 220 227,22,,1 11 2013. ISBN 978-3-642-42041-2 doi: 10.10077988-3364--2244999
[18) Eran Malach and Shai Shalev-Shwartz. Is deeper better only when shallow is good? Curran Associates Inc., Red Hook, NY, USA, 2019.
[19] James Martens and Venkatesh Medabalimi. On the expressive efficiency of sum product networks. CoRR, abs/1411.7717, 2014. http:///// org/ wttgg/abs//411.111.. 7717
[20] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
[21] Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. Neural networks should be wide enough learn disconnected decision regions. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3740-3749. PMIR, 10-15 Jul 2018. URI. httts:://proceedingg mlr wrwssp pptpss//v0//guunnneeee. htmml html
[22] Robert Peharz, Bernhard Geiger, and Franz Pernkopf. Greedy part-wise learning of sum-product networks. volume 8189, 09 2013. ISBN 378-3-642-38708--11 doi: 111007978-3-664-4000 39.
[23] Robert Peharz, Georg Kapeller, Pejman Mowlaee, and Franz Pernkopf. Modeling speech with sum-product networks: Application to bandwidth extension. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3699-3703. IEEE, 2014.
[24] Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pages 2.11. doi:
[25] Andrzej Pronobis, Francesco Riccio, Rajesh PN Rao, et al. Deep spatial affordance hierarchy: Spatial knowledge representation for planning in large-scale environments. ICAPS 20/7 Workshop Planning and Robotics, pages 1-9, 2017.

---

[26] Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Compu- tational Complexity, 17:515-535, 2008.
[27] Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In Proceedings of the 31st International Conference International Conference on Machine Learning Volume 32, ICML' 14, page I-710-1-711. JMLR.org, 2014.
(28) Itay Safran and Ohad Shamir. wepth-width tradeoffs in approximating natural functions with neural networks. In International conference on machine learning, pages 2979-2987. PMLR, 2017.
[29] Raquel Sanchez-Cauce, Iago París, and Francisco Javier Díez. Sum-product networks: A survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(7):3821-383)) 2021.
networrs:::
[30] Bruno Massoni Sguerra and Fabio G Cozman. Image classification using sum-product networks for autonomous flight of micro aerial vehicles. In 2016 5th Brazilian Conference on Intelligent Systems (BRACIS), pages 139-144. IEEE, 2016.
[31] Shizhao Sun, Wei Chen, Liwei Wang. Xiaoguang Liu, and Tic- Yan Liu. On the depth of deep neural networks: A theoretical view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[32] Matus Telgarsky. benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Pro- ceedings of Machine Learning Research, pages 1517-1539, Columbia University, New York. New York, USA, 23-26 Jun 2016. PMLR. URL SRRLattts:///pccedddgee mlr httpaa/nnw..m...reesseeeeeeeeeee press/v49)
telgarsky16.nse
[33] Leslie G. Valiant, Sven Skyum, Stuart J. Berkowitz, and Charles Rackoff. Fast parallel com- putation of polynomials using few processors. SIAM J. Comput., 12:641-644, 1983. URL
https://api. semanticscholar Perg/CorpuusI- 10197224
[34] Jinghua Wang and Gang Wang. Hierarchical spatial sum sum- uun-product networks for action recogni- tion in still images. IEEE Transactions Circuits and Systems for Video Technology. 28(1): 90-100, 2016.
[35] Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating circuits. In International Conference on Machine Learning, pages 12447-12457. PMLR, 2021.
[36] Han Zhao, Mazen Melibari, and Pascal Poupart. On the relationship between sum-produet networks and bayesian networks. In International Conference on Machine Learning, pages 116 124. PMLR, 2015.
[37] Han Zhao, Tameem Adel, Geoff Gordon, and Brandon Amos. Collapsed variational inference for sum-product networks. In International conference machine learning, pages 1310-1318. PMLR, 2016.
[38] Han Zhao, Pascal Poupart, and Geoffrey Gordon. A unified approach for learning the parameters of sum-product networks. Advances in neural information processing systems, 29, 2016.
12

---

322
32
Figure 2: The process of transforming a non-binary DAG-structured PC to a binary one that computes the identical network polynomial. We omit the edge weights for simplicity.
A Missing proofs in Section
In this section we provide the proofs of the lemmas and theorems that are not included in the main text. For better readability, we first restate the statements and then provide the proofs.
A.1 Proof of Lemma 3.2
Given depth-1 network with V nodes and E edges, we scan over all its nodes. sum node has more than two children, say M,.... MM, then keep Mj and create product node, whose only child an intermediate sum node. The intermediate sum node has two children: M2 and another just created intermediate sum node. Keep going and until an intermediate sum node has M2. as the only child.
The operation is the same if product node has more than two children by just exchanging sum and product. Note that for one operation for node with & children, the depth increases by 2(k: - 1), and 2(k - 1) nodes and edges are added. Once we do the same for all nodes, the number of increased depth, nodes, and edges are upper bounded by
2
Σ out-degree of node N if N has more than children 2V < 2F 2V O(E). NEV
In fact, for depth, this upper bound is very conservative because, for example, if node has three children, one of its children again has three children. After we operate on both of them, the depth increases by four only. A better upper bound is O(M) <. O(V), where M is the maximum out-degree in the original network. is easy to check that each child of the root computes the same polynomial as before, and does the new network. Clearly, the new network is still decomposable and smooth the original network is.
A.2 Proof of Lemma 3.3
Lemma 3.3. Given PC &b if v and w are two nodes in such that 2w + O, then Sw homogeneous polynomial over the of variables X., Xw of degree deg(v) deg(w:.
13

---

be a, and Proof. Clearly, Ou.fu # 0 implies that w is descendant of v. We prove the statement by induction on L, the length of the longest directed path from w. If L i.e. w v. then O. 1 and the statement trivially holds. Suppose the statement is true for all T. and now the longest distance from v to w is I. + 1. We prove the statement by discussing two cases, whether w a sum or product node.
Case I: w is sum node. We first assume w is sum node, and its parent inside this particular path is u. whose children are w and w'. We write J, the polynomial if we substitute with y, and fo the polynomial if we substitute u with y. Note that if we write them as functions with respect to y, then f.(y) = =fo( - fwr), and hence
f. (v) 0foly Swi) 0fvly Sw/) . Oly fwr)
fww'= = Oufe =dff fw--
(2)
Dy
dy
By the inductive hypothesis, aufu is a homogeneous polynomial over the set of variables X, Xa of total degree deg(v) deg( (u), so fu must also be homogeneous, and its degree is deg(O..t + deg(w') = -deg)) +deg(w"" = deg(v) deg(w) - deg( (o'((w) +
deg(r) deg(w)))))))))) and it over variables (X,, Un. = (X, \ (X X. U U =X," XT..
Case II: w is a product node. Next, assume w is a product node. this case, u is a sum node and deg(u)= deg(w) = deg(w'), and X,, X X Let the weight of the edge the weight for u + w/ be b. Then, [.(y) [alay + bl and
(v) Of - bf dy
Ow fo
Auff.
(3)
By
May + +bbw
Clearly, by the inductive hypothesis, both OuJv and aw are homogeneous, and they have the same degree and set of variables. Specifically, deg(Ow.f)) deg(O..v) deg(e) deg(u) deg(v) (w)( and Xw, = Xu,r = Xx X2 = X Xw-
A.3 Proof of Lemmal 3.4
Lemma 344. Let v be product node and w be any other node in a PC 4, and deg(v) < 2 deg(w). The children of are U1 and U2 such that deg(v1) 2 deg(uz). Then Ow fo fvz fw
Proof. Clearly, deg(u) deg(u + deg(uz). Therefore, since deg(v) < 2 deg(w), we have deg(v2) < deg(w); by Lemma 3.3 have Sn, - O, and the conclusion follows directly because of the chain rule.
A.4 Proof of Lemma 3.6
First, observe that with such choice of m, we have Gm n O. Write in and 1/2 as the children of v. If deg(r1) S m and dog(v2) S m, then E Gm- Otherwise, assume without loss of generality that (v)( deg((2) and deg(v1) > m. Keep reducing and there will be position such that the condition of being a member Gm holds.
We now prove the statement by induction on L, the length of the longest directed path from to Gm ie. == max dist(v, v²). If L = O, then descendants of v. Therefore, if E Gm and t o v, we have Ōzfe = 0. Clearly, a. = 1, so
Gm and all other nodes in Gm (if any) are not
fo fo O.fu+ +
Σ
fo. fe.
Σ fr.O.fe.
LEG,
IEG..
Now suppose the statement is true for all L, and now the longest directed path from to Gm has length +
Case I: u a sum node. First, assume v a sum node and fo = a1fv, + azfoz- Recall that, since is node, we have m deg(v1) = (eg( deg(u) 1) S 2m, so we may apply the inductive hypothesis on in and U2. Therefore,
fu, Σ ft a foz Σ fa defez. tEG..
(5)
teG.
14

---

Hence, using the chain rule of the partial derivative, we have
fo aife, + a2fe2
Σ
defar + E a2 fc Orfvz
(6)
teGm
tEGm
Σ teG.
Se. (ai O.5u + + 0lfo2)
(7)
Case II: v is a product node. Next, assume is product node and deg(U)) 2 deg( If v E Gm then the statement trivially holds like the base case, so we assume & Gms and therefore (1 < 2m and the longest directed path from U1 to Gm has length L, while such path does not exist from t2 to G So, by the inductive hypothesis,
fej
Σ ft. Oeter LEGm
(8)
By definition, i E Gm, then we must have 2 2dg((t) > 2m 2 deg(v), and by Lemma 3.4
Sa - Soz
Σ
(Joz -.Sm))
E St O.So. LEGm.
LEG..
A.5 Proof of Lemma 3.7
We again write en and it2 as the children of u, and again induct T., the length of the longest directed path from v to Gm in the network. If L = 0, then v E Gm. and same as the previous case, every other node in Gm
a descendant of u, which implies arfu 0. So,
Sv Swfe OnSu+ +
Σ BEG
Sw Oes. = Σ
Ow O.fo.
(10)
LEG..
Suppose the statement is true for all L, and now the longest directed path from v to Gm has length +++1.
Case I: a sum node. First, assume e sum node and So aiSer + a2/22- Again, since sum node may apply the inductive hypothesis 2 and U2:
OwL
Σ LEGm
Owfe 0efuri fw
Σ tGG.
Sufi Ocfuz-
(11)
Again, by the chain rule, we have
Sw fw + arowlr2
Σ Owli (ard.Sm, a2drlzz)
E Owfe Eowle Sefu- (12)
Case II: v is product node. Now assume is product node and deg(u1) 2 deg(uz). If V E Gms then the statement trivially holds like the base case, so we assume & Gms and therefore deg(v)) < 2 deg(w) w) and the longest directed path from on to G, has length L, while such path does not exist from U2 to G So, by the inductive hypothesis.
Owfer
Sw ÖrSer tEG..
Σ
(13)
Since deg(e) < 2deg(w), w) and for all nodes & E Gm, we have 2 deg(t) > 2m > dog(u), so by applying Lemma 3.4 twice, we have
dw = Snz Ow = Σ
Swli (Jrg O.fm))) = Σ
Ow ŌzS
(14)
LEGm
6 LEG.
15

---

0g d
My dupt 0,
tu 02.13
Figure 3: The process of converting an arbitrary DAG a DAG with depth restriction. The red nodes are those in G2 and their relationships imply the computational procedure.
A.6 Proof of Lemma 3.8
Suppose the network is smooth. Recall that if the root of probabilistic circuit contains variables, then the network computes multi-lines polynomial of degree n. If the root is sum node, then its children must be homogeneous with degree n. If the root is product node, then its children must also be homogeneous, otherwise the product node will not be homogeneous.
Conversely, suppose such network is homogeneous. We prove by induction the depth d of the network. If = and the root is a sum node, then the polynomial must be linear and therefore there can only be variable and h; statement is true for any d, and we have probabilistic circuit with depth d+ 1. If the root is product node, done because if any sum node had two children with different scopes, the inductive hypothesis would be violated. If the root is a sum node, then every sum node other than the root cannot have children with different scopes, because each sum node is in the induced sub-network rooted at grandchild of the root of depth at most d 1 so the inductive hypothesis must hold. So, XR. where R1.... Rg are children of R. Since the R4 are decomposable and homogeneous, those sub-networks must
result, this simple network is smooth. Now suppose the
we only need to show X XR. netboesssrks rooted at R be smooth by the inductive hypothesis. Hence, each R3 computes a polynomial of degree RRR| IXn, < then the polynomial computed by R is not homogeneous of degree and we obtain contradiction. Therefore, each RG must contain all of n variables to compute polynomial of degree and as result, we prove X XR,
X and the smoothness of the entire network.
A.7
Construction of V
A.7.1 Step one: computing for eligible nodes
During iteration + 1, polynomial fo is in consideration if and only if 2 deg(v) < 2 Naturally we shall apply Lemma and therefore choosing an appropriate m and the corresponding Gm is essential. Here we choose m = 2'. Moreover, we define a set T = G. O P. for each being considered; for every E T, we use t and to denote its children. By Lemma 3.6 and the definition that all nodes in Gm are product nodes, we have
fo Σ f.f SET
E fer fez O.f..
(15)
Since & T, we must have max (deg(fi), deg(tz)) S m 2 and therefore
2' deg(t) deg(t1) + deg (2) < 2m 2
(16)
Therefore, deg(e) - deg(!) < 2i+1 2 2 and deg(v) < 2 + deg(!) < 2 degg()). Hence, fnp fia and fufu have all been computed already during earlier iterations. If deg(v) deg(t), then t is
16

---

child of u and Orfe is the weight of the edge - Therefore, to compute such a fe. we need to add (I') product nodes and one sum node, whose children are those [T] product nodes; apparently, the depth increases by two. If a subset of the three terms (St, ft.. Sr is constant, then their product will be the weight of the edge connecting the product node ft, St, and the new sum node.
We now verify the validity of this updated circuit. Because & is decomposable and is a product node, we conclude Xz, n2 = 0 and X, Xx, LX,, By Lemma 3.3 we have Xt. X, \X; X. \ (Xe, L (. Therefore, every summand in Equation (15) is product node whose children are sum nodes with pairwise disjoint scopes, and thus, the updated circuit must be decomposable as well. Also, since fo is a homogeneous polynomial, so must be every summand for each t. As a result, the updated eircuit also homogeneous. Thanks Lemma 3.8] the updated circuit is valid.
A.7.2 Step two: computing Jv for eligible pairs of nodes
As discussed earlier, during iteration i + 1, a pair of nodes u and w are chosen if and only if 2' < dog(u) deg(w) 2 and deg(u) u) < 2 dog(w). In this case, we fix m 2' deg(w) (w), and define T = Gm n Pu. Clearly, deg( w) < m < deg(u) < 2 deg((w,, so by Lemma 3.7 we have fa Leer - For each
T, by definition must be a product node, and since E Q.. have deg(w) w) deg(t)= S deg(u) < 2 deg(w). Recall that the children of i are denoted by and t2, and we may assume without loss of generality that deg((1) 2 deg(t2). Hence, by Lemma 3.4 we have
Su = E Jt2 Jw ÖrSa-
(17)
LET
Furthermore, we may safely assume deg(w) S deg(ti), otherwise w is not descendant of t nor t and therefore Sw = St O. Next, by analyzing their degrees and differences in degrees, we show that for each I, the terms ftg. Sw and 0gfa in that summand have all been computed by earlier iterations or the step one during this iteration i + 1.
Term fez Since
deg(u) S deg(w) + 2:-1 5 2 + deg(()) 26+1 + deg(() - deg((2);
(18)
we have
deg(t2) < 2 + deg(t) deg(u) < 2
(19)
Hence, Stg has already been computed during the first step of this current iteration even earlier.
Term fe Recall that dog((2) I 2' + deg(w), so deg(t1) deg(w) < 2'. Moreover, deg(41) S deg(!) S deg(u) < 2 deg(w). Therefore, the pair (4,,) satisfies both requirements to be computed during iteration i or earlier.
Term 0.fu: Recall that deg(t) > m 2 deg(w). so
deg(u) deg(t) < deg(u) deg(w) 2' < 2 - =
(20)
where the second inequality follows from deg(u) - deg(w) < 2i+1, the requirement of choosing u and w for iteration i + 1. Finally,
dog(u) s 2 + deg(w) < (2' + (w) dog(t).
(21)
=m deg(()
These two facts together ensure that 0,fu must have been computed during iteration i or earlier.
Finally, we verify the validity of the updated eircuit after this step. The new objects introduced in this step are only [T' product nodes whose children are ft,, fw, and ō.fu, for each t T, and one sum node whose children are those [7' product nodes. is easy to see that the sets Xt,, X,, X,, and X,, \ X, are pairwise disjoint since X,, C Xt, and Xt, O X2, 0; therefore, the updated circuit indeed decomposable. By Lemma 3.3 all three terms in each summand are homogeneous, and therefore the new circuit is also homogeneous, and consequently, it is valid again by Lemma 3.8
17

---

B Missing proofs in Section
B.1 Proof of Proposition 4.2
Before writing the rigorous proof, we first fix some terminologies. In this proof, refer the layer of all indicators constructed in step one as layer zero, and each set of nodes constructed in one of steps three, four, and five as one layer above. A negation indicator added in step six does not belong to any layer. Therefore, when we consider a layer of sum nodes, the negation indicator leaves whose parents are product nodes on the next layer are not in consideration. Step six augments the scope of every product node; for any product node v, we use o' to denote the same vertex before being augmented during step six. To prove this statement, we first prove an equivalent condition for | to be valid, and then show P satisfies the equivalent property.
Lemma B.1. Validity of P* is equivalent with the following statement:
In P every product node and its sibling have the same scope. If two product nodes are on the same layer but not siblings, then they have disjoint scopes.
Proof. Suppose the statement holds, then for any sum node, its two children are product nodes and siblings, so they have the same scope; for any product node v, denote its children by w and w', and their children by {wI, w2} } and {w1, w²). respectively. Clearly, w, and w are siblings and have the same scope for any E {1. 2). but if j # i, then wy and w/ have disjoint scopes. Therefore, scope(w)- = scope(w1) = scope(wy) and scope(w") = scope(w1) = (c))e(w()) are disjoint, as desired.
Conversely, suppose p* is decomposable and smooth. For any pair of product nodes which are siblings. they share a unique parent and thus have the same scope due to smoothness. Now suppose we have two product nodes v and w, which are on the same layer but not siblings. We prove useful fact: If two product nodes are on the same layer 2j + 1 for some 1 S j S k, then = = = 225+2, When j = 1, we know that initially every product node on layer one has two leaf children, so adding two negation indicators enforce that every product node that layer has degree four. Assume the statement is true for all j. and we now consider those product nodes 2j + 1. By the inductive hypothesis, every product node on layer 2j- - 1 has degree 2 and therefore every sum node on layer 2j also has degree 22j. If u is a product node on layer 2j + 1 with the sibling u*, we have deg ut) deg((u ("") = 22i+1_ Step six ensures that deg(u)= = deg(u") = deg(u') + deg((u")) = 2
on layer 2(j + 1)
If they share an ancestor that is product node, then their scopes are disjoint due to decomposability. On the other hand, suppose their only common ancestor is the root, whose children are denoted by an and 02 then without loss of generality, we may assume that v is descendant of and w is descendant of a2. Because pa is valid, it must be homogeneous and we have deg(ai) = deg((2)) The fact we proved in the previous paragraph implies that deg(a,) = deg(ab) = 22k-3+2 3+2 2
In other words, step six increases the degree of af and a' by 2 each. Because the whole tree Ps is decomposable, the increase in deg(a') is exactly 2 scope(aa)), and vice versa. Due to smoothness, {XI,... } = scope(a') a U scope(a)), and thus scope(af)) n scope(ab) G. Finally, since scope(u) C scope(a() and scope(w) C scope(as)) we must have scope(r) scope(w) (w) = V.
Now prove Proposition 4.2 by showing that P indeed satisfies the equivalent property. Proposition 4.2. The tree PC pa is decomposable and smooth.
Proof. Now we prove that P satisfies the equivalent statement by induction on the index of the layer containing product nodes only. Using the index above, only the layers with odd indices from (2i - 1)/= are concerned. For the base case, consider those 2 product nodes constructed in step two, denoted by U2. U2 For each 1 S j S 22h-1 if j is odd, then following steps two and six, the children of 0y are {22z-11 D2j. F25+1, 22 ). Its only sibling is 1y+1, whose children are {z 11 Z2j. -2j-11 ). Thus, scope(t;) = sc) = (X2j-1 X25, X25+1, X25+2). The argument is identical if j is even.
On the other hand, suppose 5 r < < 22k-1 and two product nodes v, and vs are not siblings, i.e. either 1,
1 and is even.
18

---

and Case I: 8 3- 1. In this case, the set scope(e,)) is {X2r-1, X2r, X2r+1 Xer+2) if r is odd, even: similarly, the set scope(u,) depends on the parity of If = 2, then they have an identical parity. If they are both odd, then scope(rs) = [X X2(r+))++ -22 X2(r+2)+2] with scopo(U,)) The argument is identical if they are both even. If - > 2, then the largest index among the elements in scope(u,) (,)) is 2r + 2, and the smallest index among the elements in scope(v.) is 28- - 3 2 2(r + 3) - 3 = 2r 3; hence, scope(u,,) scope(v.) = 0.
(X2r-3, 3, 22 X2r-2 11, X2r)
= [X2r43, X2r4-4 X2r+5, X2r+6), and is disjoint
Case II: r = and r is even. In this case, scope(e,) = {X2r 3.r- X2r- X2r- X2r} and scope( = 2 X2s, is odd. Clearly, scope(u,) scope(u,) 0.
= (X2r+1, X2r42, X2r+3, X2r-4) because +
The argument above proves the base case. Suppose the statement holds until the layer 2i - 1 for some i k, and we now consider layer 2 + nodes, denoted by v1,..., U22 They must have non-leaf children, and we denote these nodes without their leaf nodes by 8/, ............................... 2 21- By construction, the layer 2i below contains 22k-2i
2i + 1, which contains 2 2 product
sum nodes, denoted by W1,-. 21; and the layer 2i contains 22k 2 product nodes, denoted by 21,-.- 222k-2 For each 15 2 2i the product node e, has children 12r-1 and W2r, and is their unique parent. Similarly, W2r has children 24,-1 and Σ4r and is their unique parent; 1 has children 34.-3 and 24,-2, and is their unique parent.
We prove a simple fact that will simplify the induction step. We claim that, given two integers r, 8 E {1.-... 22k-2i-1 and A s, the scopes scope(e()) and (v')e(v')) are disjoint. Without loss of gener- ality, we assume r < 8. By construction, Ch(e') thermore, Ch(wwr-1)
{w2r-11 1, w2r} and Ch(v') = (w2--1+ W2s ): fur- Ch(w2=) = : [2r-33, 3, 2). Ch( ch(w2r) = { 1 3. J. Ch(w2--1) = ={ {Z4s-36 3, 248-2). 2 Observe that, if a pair of product nodes belong to one of the four sets above, then they are siblings and have the same scope; if they belong to distinct sets, then they are not siblings and have disjoint scopes. We know that the scope of a node is the union of the scopes of their children, so the four scopes scope(w2r- 1), scope scope scope( W2.)) are pairwise disjoint. As a result, the scopes scope(t?) (f)) = scope(w2r-1) 1) Ll scope(w2r) and scope(u'))
scope( (roppe(w2s-1) (12s-1) scope (w2s) are disjoint.
Now we prove the induction step. the first case, suppose e, and 6--1 are sibling, i.e. r is odd so U/411 is the only sibling of e,. We have shown that (ocopp(((() n scope(t'44)) = 0. However, step six enforces that scope(e,) = scope(v;)) LJ scope()/+1) = scope(r)+1), i), as desired.
Next, suppose Sr<as 22k-2i-1 and V, and us are not siblings. Denote the siblings of e, and Us by Urr and Ugr, respectively; by definition, r' E (r -r-11 1,r + and s' E {s 1, + depending on the parity of r and s. Clearly, the four nodes 6y, Uyr, V,a Us are distinct, and consequently the four sets scope(u,), scope(r,)), scope(v.), and scope(v..) are pairwise disjoint. Step six enforces that scope( v,,) )) = scope(1,)) LJ scope()(,) and scope(v.) = scope(v!)) Li scope()())) which are disjoint as desired.
B.2 Proof of Proposition 4.4
We first realize the polynomial P returned by Algorithm 3 without adding those leaves represent- ing negation variables. Recall that layer one contains 2 2-h-1 product nodes, and before adding negation variables, the bottom layer (layer zero) contains 2 leaves. If for every odd integer i E (1, 5,... 2 1), we denote the monomial by f(++1 = I2f141, then without adding negation variables, the polynomial can be constructed by the following recursion with 2k + 1 steps:
Construct 2 monomials 01 T2aa T2aa..
Sum up 2 pairs of consecutive monomials, and return 2 polynomials with two monomials x x + Iz .... Zzaa - Izat- Tzas.
Multiply 2 pairs of consecutive polynomials, and return 22k-3 polynomials.
Repeat the operation until only one polynomial is returned.
Observe that this polynomial exactly (k:2) defined in Section with an alternative set of indices for the variables (2) x | versus 122 To prove Proposition it is sufficient to show that for
19

---

every minimum trre-structured probabilistic circuit II of depth o(k) that computes P, the removal of those leaves representing negation variables returns an arithmetic formula that has the same depth and computes 1/ (k. To show this, we need the following lemma.
Lemma B.2. In any tree-structured probabilistic circuit 11 that computes P. no node has negation indicator as child, and no product node has only negation indicators as its children.
The proof of Lemma B.2 relies the following lemma monotone arithmetic formulas.
Lemma B.3. A monotone arithmetic, forttmuuliiffmulla computing a homogeneous polynomial must be homo- geneous.
Proof. If formula is rooted the root is a product node with & children, then denote the polynomials computed by them as fi. fu and write f = II f.. Furthermore, for each i E [k], further assume f. contains qi monomials, and write it as
node, then clearly every child of its must be homogeneous.
fi = fi.1 + +... + fi.g. Without loss of generality, assume f1 is not homogeneous and deg(f1.) o deg(f1,2). Then at least two of the monomials of f. namely fi,1 x II f,1 and f1.2 II f,.1, must have distinct degrees and therefore destroy the homogeneity of the root.
(22)
Proof of Lemma B.2 First, observe that in a PC, if sum node has a Ieaf as a child, then due to smoothness, it only have two children, which are negation and non-negation indicators for same variable.
Suppose IT does have sum node u that has negation indicator I; child. Observe that, if we replace all negation indicators with the constant one, then the resulting tree is still monotone and computes F, which is a homogeneous polynomial. The replacement will cause that sum node to compute exactly x; + 1, which is not homogeneous.
Similarly, if a product node v has only negation indicators as its children, then the replacements above force v to compute one. Smoothness enforces that its siblings have the same scope does, and without loss of generality we may assume none of its siblings computes the same polynomial as does, so their degrees are higher than one. As result, the replacements of all negation indicators to one will force the parent of to compute a non-homogeneous polynomial, which contradicts Lemma
Now Proposition 4.4 can be confirmed, because the removal strategy will indeed produce tree that computes (R.2), and no internal nodes will be affected, because Lemma B.2 ensures that, no internal node in 11' computes constant one and can be removed.
20

---

C
Pseudocodes
Algorithm Construction of G
Data: a binary DAG-structured PC & with V nodes and n variables
I,... log n., set of nodes Ggz and for selected w, set of nodes Gzi T 0; P. - 0, Q; + 0. Gz < 0, G2 w + for i E f.. ... log n and w E &; 2, + 0 for u Q. Scan all nodes from the bottom and calculate the degree of each fc.
Result: For each
During the scanning, extract all weights of edges from a sum node to product node. do
for nodes
Pu 4, U (v) if u is parent of v. for = 1 to log do
2' < deg(v) < 2 then
P. - P. (v).
end
v is a product node and deg(v) 2 and deg(vi) s 2 and deg(U2) S 2' then
G2 + Gz: U {v}.
end
for other nodes in + do
2' < deg(v) - deg(w) S 2 and deg(v) < 2 deg(w) then Q ((e w))
end
if u is product node and deg(v) 2 deg(w) and deg(vi) S 2' + deg(w) and deg(v2) 2' + deg(w) then G2 &- G2 w U (v).
end
end
end
end
21

---

Algorithm 5: Construction of the tree
Data: binary DAG- structuud PC & with V nodes and variables
Result: a tree-structurd PC with size 20 T' + 0; P. f 0, Qi + 0. Gz. < 0, G2i + 0 for E {1, ... logn] and w E Φ; 2, + 0 for
eE Φ m
not defined yet
Operate Algorithm and return Go and Gz for all i E {1,-.. ,log n and those & that were selected for computing partial derivatives.
for i = 1 to log n do
m 2'. for E P. do T Go: 7
for do Create product node &, computing ft, St, Ōcfv. end
Create a sum node @y that sums over all (2; for t E II' such that θrfe is a non-zero-or-one constant, the edge +. + &g has weight f.
end for
(u, w) Qi do x- 2 + deg(w) T <- G2 P.:
for 1 E do
Create product node & computing fi, fe, Ōefe- end
Create sum node @(,,w) that sums over all @x: for E T such that @ contains a constant multiplier, the edge @(v,w) 8 has weight of that constant.
end end
Apply the naive duplication to convert the DAG into a tree. Apply Algorithm 2 in 36 to normalize the tree.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [NA]
Justification:
Our paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuii wwwtii/gguie///eeeeeeoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper studies a not have direct societal impact.
theoretical conjecture, and therefore shall
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Our paper does not include experiments and is not relevant with any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The license is CC-BY 4.0.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cow/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "eBMbRP9Hqe", "reviewer": "Reviewer_PAKa", "summary": "This paper studies the expressive power (i.e., expressive efficiency) of tree-structured probabilistic circuits (PCs). Specifically, this paper shows that:\n- Any decomposable PC over n random variables can be transformed into a tree-structured PC of depth O(log n) with n^{O(log n)} nodes.\n- A super-polynomial separation between tree-structured PCs of depth o(log n) and decomposable PCs. Specifically, the authors show the existence of a network polynomial that can be computed by a poly(n)-size decomposable PC but the size of any tree-structured PC of depth o(log n) is lower-bounded by n^{\\omega(1)}.", "questions": "n/a", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Though the proof of the upper bound relies heavily on the existing depth-reduction algorithm proposed by Valiant et al. [32] and Raz and Yehudayoff [25], it is significant for the study of PCs to show that this depth-reduction algorithm preserves decomposability. \n\n- The lower bound result is already very close to showing an unconditional super-polynomial separation between tree-structured PCs and decomposable PCs and eventually leading to a tight bound.", "weaknesses": "n/a", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful to the reviewer for appreciating our contributions.", "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": "", "extra_scores": {}}, {"review_id": "SNnZnhA0V1", "reviewer": "Reviewer_x52f", "summary": "This paper considers the structure expressive power of Probabilistic Circuits (PCs) from a theoretical perspective. Specifically, this paper explores how PCs with directed acyclic graph (DAG) structures and those with tree-like structures contrast each other in terms of circuit size and expressive power. The contributions include theoretical derivations for an upper bound and a conditional lower bound for DAG-structured and tree-structured PCs. First, the authors show that there exists a sub-exponentially-sized tree-structured PC to represent the same network polynomial as a DAG-structured PC. Second, they show that a tree-structured PC must have a super-polynomial size to represent the same network polynomial as a DAG-structured PC given a restriction on the tree depth.", "questions": "- Could the authors provide some new insights on how this work can help further research in PC structure learning?\n- When taking into account the computational costs for learning DAG-structured and tree-structured PCs, how does one manage the trade-offs between these costs, the expressiveness of the circuit, and the resulting circuit size?", "limitations": "The authors have discussed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper is well-organized and logically coherent.\n- This paper provides novel theoretical insights into a relatively under-explored topic (DAG-structured PCs).\n- The theoretical results and algorithmic methods are well-presented.", "weaknesses": "- While the results are interesting, I am a bit skeptical about the applicability of this work in structure learning of PCs. In practice, challenges in PC structure learning often arise from issues such as defining appropriate learning objectives, addressing overfitting, and improving the computational efficiency of learning algorithms. The findings of this paper appear to be of little help in addressing these issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful to the reviewer for acknowledging the novelty of our work and its presentation, and we deeply appreciate the insightful questions.\n\n> Could the authors provide some new insights on how this work can help further research in PC structure learning?\n\nWe agree with the reviewer that our main focus of this paper is theoretical, but we hope that our results on clarifying the size separation between tree-structured and DAG-structured PCs can inspire future algorithmic innovation on directly learning DAG-structured or deep tree-structured PCs from data. As we state in the second paragraph of Section 1 Introduction, existing research on structure learning algorithms (e.g. references 1, 8, 12, 16, 21, 26) for PCs either only learns shallow tree-structured PCs or DAG-structured PCs by using tree-structured PCs as intermediates. Neither line of work can fully exploit the size advantages of DAG-structured PCs. Hence, from this perspective, our work suggests and encourages future research into designing algorithms to directly learn DAG-structured PCs from data, and this should also help in terms of generalization of PCs, due to the size reduction.\n\n> When taking into account the computational costs for learning DAG-structured and tree-structured PCs, how does one manage the trade-offs between these costs, the expressiveness of the circuit, and the resulting circuit size?\n\nBalancing the trade-offs among those criteria indeed requires careful consideration. In particular, there are two significant points to consider.\n- Tree-structured and DAG-structured PCs are equally expressive, in the sense that there does not exist a distribution that can be represented by one but not the other. Therefore, expressiveness of a circuit’s output usually does not raise concerns.\n- There indeed exists a potential tradeoff between the size of PCs and the complexity of learning algorithms. While to the best of our knowledge there is no existing structure learning algorithm that can directly learn a DAG-structured PC from data, in principle one could control the trade-off based on the underlying complexity of the distribution to be learned.", "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": "", "extra_scores": {}}, {"review_id": "w1ObrOWEDl", "reviewer": "Reviewer_Tza1", "summary": "The paper studies the how expressive probabilistic circuits (PCs) whose underlying structure is a tree are compared to those whose structure is a DAG. This is motivated by the fact that algorithms for learning PCs usually construct trees, and thus do not potentially take advantage of the potentially more expressive nature of DAGs. The present work shows that DAGs are strictly more powerful in the sense that there are polynomials that can be expressed as DAG-structured PCs of polynomial size but require super-polynomial size as tree PCs. On the other hand, the gap is not exponential, since DAG-structured PCs can be transformed into tree PCs of sub-exponential size, as shown in the paper.", "questions": "In Sec. 1.1, you state that \"[the] restriction on the graph of using nodes with at most two children ... is not necessary for PCs\", suggesting that nodes in PCs can have multiple children in your setting. On the other hand, you define decomposability for product nodes with exactly two children. It would be good to clarify in the paper which of these is the case.\n\nIn Sec. 1.2, you briefly mention the notion of expressive efficiency. Perhaps here (or somewhere else), it would be relevant to cite the paper [34] on probabilistic generating circuits (PGCs), since they subsume PCs for Boolean random variables. Also related is their follow-up paper (Broadrick et al., 2024; full reference below), where they show that allowing PCs to have negative weights in sum nodes makes them as expressive as PGCs.\n\nLemma 3.2 seems like folklore to me, since it is well-known how circuits of arbitrary fan-in can be transformed into, say, fan-in 2.\n\nThe linebreak in Lemma 3.6 can be confusing to the reader.\n\nAlgorithm 1: Definition of $m_2$ is unclear, since $w$ is not specified.\n\nOliver Broadrick, Honghua Zhang, Guy Van den Broeck:\nPolynomial Semantics of Tractable Probabilistic Circuits. CoRR abs/2402.09085 (2024)", "limitations": "Authors discuss the limitations briefly but sufficiently.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-motivated and, in general, written well.\n\nPCs are an active area of research.\n\nThe results are novel to my knowledge and give theoretical contributions on both lower and upper bounds.", "weaknesses": "For the lower bound, depth constraint $o(\\log n)$ needs to be imposed on the tree-structure. As such, the lower bound appears to have very few practical implications, since we rarely need the tree PC to be that shallow. Admittedly, the authors briefly discuss this limitation in the paper.\n\nSometimes, the presentation could be more polished: For example, symbols $v$, $w$, $u$, $v'$, $v_1$, $v_2$, and $t$ are all used for denoting nodes. Could the notation be somehow made more consistent? Some other examples are listed in the next question.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for acknowledging our contributions, and we deeply appreciate for pointing out the cluttered notation and the limitations of the conditional lower bound. The following is our responses for the questions.\n\n> In Sec. 1.1, you state that \"[the] restriction on the graph of using nodes with at most two children ... is not necessary for PCs\", suggesting that nodes in PCs can have multiple children in your setting. On the other hand, you define decomposability for product nodes with exactly two children. It would be good to clarify in the paper which of these is the case.\n\nIn Definition 2.1, the definition decomposability is intended for ANY pair of a product node’s children v_1 and v_2, instead of implying they are the only children of a product node. We will emphasize this in our final draft.\n\n> In Sec. 1.2, you briefly mention the notion of expressive efficiency. Perhaps here (or somewhere else), it would be relevant to cite the paper [34] on probabilistic generating circuits (PGCs), since they subsume PCs for Boolean random variables. Also related is their follow-up paper (Broadrick et al., 2024; full reference below), where they show that allowing PCs to have negative weights in sum nodes makes them as expressive as PGCs.\n\nThanks for pointing out the references. We will properly acknowledge their contributions in our final draft.\n\n> Lemma 3.2 seems like folklore to me, since it is well-known how circuits of arbitrary fan-in can be transformed into, say, fan-in 2.\n\nWe agree. We added this result for the sake of completeness, because our proof for the upper bound result uses previous results in circuit complexity based on circuits with fan-in two. We will add a clarification stating its relation with existing results in our final draft.\n\n> The linebreak in Lemma 3.6 can be confusing to the reader.\n\nThanks for pointing out this. We will update the typeset to fix this issue.\n\n> Algorithm 1: Definition of $m_2$ is unclear, since $w$ is not specified\n\nThanks for pointing out this. The definition of $m_2$ is indeed dependent on the choice of a pair $(u, w)$. We will move the line “Fix $m_2$ … ” down to ensure clarity.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides nice separation results on the sizes of DAG and tree-structured probabilistic circuits. The reviewers agree that this result may not be immediately useful in learning algorithms, but is nonetheless a valuable theoretical contribution that complements the existing body of work in PCs. All three reviewers advocate for acceptance. I expect that this result will be cited often in future work on PCs, and may lead to even stronger theoretical results, as one reviewer suggests.
Decision: Accept (poster)