On the Expressive Power of Tree-Structured Probabilistic Circuits

Authors: lang  yin
han  zhao
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:35:56

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.

Main paper: 
 introduction: 
 Probabilistic circuits (PCs) [7, 29] , also commonly known as sum product networks (SPNs) [24] , are 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 [38] . Because of these desirable properties, they have been increasingly applied in various contexts, including generative modeling [35] , image processing [2, 34] , 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 designing efficient parameter learning algorithms for PCs, including the expectation-maximization (EM) algorithm [12] , the convex-concave 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 a product distribution over univariate marginals [38] . Intuitively, each sum node in PC can be viewed as a hidden variable that encodes a mixture model [36] and thus a hierarchy of sum nodes corresponds to an exponential number of components. This probabilistic interpretation of PCs has led to a number of interesting structure learning algorithms [1, 9, 13, 17, 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 DAG-structured circuits. Because of the restricted structure of trees, such algorithms do not fully exploit the expressive power of PCs with general DAG structures, and often output tree-structured PCs with exceedingly large sizes [13] . Yet, from a 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.In this work we attempt to answer the question above by leveraging recent results in complexity theory [11, 26, 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 to 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 a 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 an equivalent tree-structured PC of depth O(log n) and of size n O(log n) 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 is still poly(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 O (D) . However, note that the DAG constructed in the first phase has depth O(log n). Combining it with the duplicating strategy, we will be able to construct an equivalent tree-structured PC of size upper bounded by n O(log n) , as desired.The original algorithm in Raz and Yehudayoff [26] only reduces the depth to O(log 2 n) due to their restriction on the graph of using nodes with at most two children. This restriction is not necessary for PCs, and by avoiding it, we show that the depth can be further reduced to O(log n) with a slight modification of the original proof in Raz and Yehudayoff [26] .A Lower Bound In Section 4, we show that under a restriction on 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 in Section 4. Theorem 1.2 (Informal). Given n random variables, there exists a network polynomial on those n variables, such that it can be efficiently computed by a PC of size O(n 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 n ω (1) .Our result is obtained by finding a reduction to Fournier et al. [11] . We first fix an integer k and a network polynomial of degree n = 2 2k . To show that the polynomial is not intrinsically difficult to represent, i.e., the minimum circuit representing it shall be efficient, we explicitly construct a PC of depth O(log n) and size O(n log n). Next, suppose via a 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 √ n = 2 k . Moreover, as shown in [11] , if an arithmetic tree with depth o(log n) computes this low-degree polynomial, then the size of the tree must be at least n ω (1) . Our operations on the minimum tree PC must reduce its size; therefore, the original tree must have a larger size than n ω (1) , and this fact concludes our proof.There is an extensive literature on expressive efficiency of 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 [19] . In neural networks and variants, this topic, along with the relationship between expressive efficiency and depth/width, has attracted many interests as well [10, 16, 18, 20, 21, 28, 31, 32] . In particular, Martens and Medabalimi [19, Theorem 34] has shown that there exists a network polynomial with a super-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 a longstanding open problem in circuit complexity.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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 an edge u → v, we say that u is a parent of v, and v is a 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 b if there is an edge a → b or there are nodesu 1 , • • • , u k and edges a → u 1 → • • • → u k → b;in this case, we say that a is an ancestor of b and that b is a descendant of a. If two vertices v and w are connected via a directed path, we call the number of edges in a shortest path between them as 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 a directed path from a node to itself, and a directed graph without directed cycles is a DAG. For two disjoint sets A and B, we will denote their disjoint union by A ⊔ B to emphasize their disjointedness.Clearly, each directed graph has an underlying undirected graph obtained by removing arrows on all edges. Although by definition, a 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 at most one parent. If two nodes share a parent, one is said to be a sibling of the other.In what follows we introduce the necessary complexity classes that will be used throughout the paper. Let f (n) be the runtime of an algorithm with input size n.• A function f (n) is in the polynomial class poly(n) if f (n) ∈ O(n k ) for a constant k ∈ N. • A function f (n) is in the super-polynomial class if f (n)is not asymptotically bounded above by any polynomial. Formally, this requires f (n) ∈ ω(n c ) for any constant c > 0, i.e.lim n→∞ f (n) n c = ∞ for any c > 0. • A function f (n) is in the quasi-polynomial class if it can be expressed in the form 2 poly(log n) . • A function f (n) is in the exponential class if it can be expressed in the form 2 O(poly(n)) .Probabilistic Circuits A probabilistic circuit (PC) is a 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 polynomial. For each Boolean variable X, we use the corresponding lower case alphabet x to denote the indicator of X, which is either 0 or 1; 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 1 , • • • , X n } computes a polynomial over the set of indicators {x 1 , • • • x n , x1 , • • • , xn };we will refer this polynomial as the network polynomial. In the network, the leaves are 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 a 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 an equivalent normalized PC within linear time.To represent valid probability distributions, a PC must satisfy two structural properties: decomposability and smoothness. To define them, we need to define the scope of a node, which is the set of variables whose indicators are descendants of that node. For a node v, if the indicator x of the variable X is one of descendants of v, then X ∈ scope(v); more generally, scope× + + x 1 x1 x 2 x2 v f v = f w × f w ′ w f w = ∂ w ′ f v w ′ f w ′ = ∂ w f v(v) = ∪ v ′ ∈Ch(v) scope(v ′ ).Definition 2.1 (Decomposability and Smoothness). A PC is decomposable if and only if for every product node v and any pair of its children v 1 and v 2 , we have scope(v 1 ) ∩ scope(v 2 ) = ∅. A PC is smooth if and only if for each sum node, all of its children have the same scope.In this paper we restrict our attention to PCs that are 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 a monomial is the sum of the exponents of all its variables, and the degree of a polynomial f , denoted by deg(f ) is the highest degree among its constituent monomials. A polynomial is said to be homogeneous if all of its monomials have the same degree. A PC is said to be homogeneous if all of its sum and product nodes compute a homogeneous polynomial. Later, we will show that decomposability and smoothness imply homogeneity, and vice versa with mild conditions. For a node v in a PC, we use deg(v) to denote deg(f v ). As emphasized earlier, this paper investigates the quantitative relationship between a DAG and a tree, which are both PCs and represent the same probability distribution. To make the terminology uncluttered, we will call the former a 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.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 at v is denoted by Φ v and the polynomial computed by v is f v . The set of variables in f v is X v , which is a subset of {X 1 , • • • , X n }. The size of the network Φ, denoted by |Φ|, is the number of nodes and edges in the network. The depth of Φ, denoted by D(Φ), is its maximum length of a directed path.Partial Derivatives In the process of proving the upper bound, a key notion named partial derivative is frequently used and formally defined below. Definition 2.2 (Partial Derivative). For two nodes v and w in a network Φ, the partial derivative of the polynomial f v with respect to the node w, denoted by ∂ w f v , is constructed by the following steps:1. Substitute the polynomial f w by a new variable y. 2. Compute the polynomial computed by v with the variable y; denote the new polynomial by fv . Due to decomposability, fv is linear in y.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification:Guidelines:• The answer NA means that the paper has no 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
define the partial derivative: 
 ∂ w f v = ∂ fv ∂y .Observe that the chain rule in calculus also holds for our notion here, and therefore leads to the two following facts.• Let v be a sum node with children v 1 and v 2 , and the edges have weight a 1 and a 2 , respectively, then by definition f v = a 1 f v1 + a 2 f v2 . For any other node w, the partial derivative is∂ w f v = a 1 • ∂ w f v1 + a 2 • ∂ w f v2 .• Similarly, let v be a product node with children v 1 and v 2 , thenf v = f v1 • f v2 .For any other node w, we have∂ w f v = f v1 • ∂ w f v2 + f v2 • ∂ w f v1 .The partial derivative has been proven to be a powerful tool in the field of complexity theory and combinatorial geometry [14, 15] . Readers are welcome to refer Chen et al. [5] for more details and extensive background. An illustration is provided in Figure 1 .Arithmetic Circuits An arithmetic circuit, aka algebraic circuit, is a generalization of a probabilistic circuit. Such a circuit shares the same structure as a PC and also computes a network polynomial. If an arithmetic/algebraic circuit is a directed tree, then we call it an arithmetic/algebraic formula. In the proof of the lower bound, the notion of monotonicity of a formula is essential, whose definition relies on the concept parse tree. Definition 2.3 (Parse Tree). A parse tree of a formula Φ is a sub-formula of Φ which corresponds to a monomial of f , the network polynomial computed by Φ. Parse trees of Φ is defined inductively by the following process:• If the root of Φ is a sum node, a parse tree of Φ is obtained by taking a parse tree of one of its children together with the edge between the root and that child. • If the root of Φ is a product node, a parse tree of Φ is obtained 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 a non-negative coefficient in the network polynomial.In this section, we present our first main result, which provides a universal upper bound on the size of an equivalent tree versus a DAG-structured PC. Theorem 3.1. For any given DAG-structured PC over n variables and of size poly(n), there exists an equivalent tree-structured PC of size n O(log n) nodes and of depth O(log 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 Yehudayoff [26] , will be efficient if the circuit being considered is a 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 a 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-structured PC Φ, we may transform it into another DAG Φ ′ that computes the same network polynomial and every node in Φ ′ has at most two children. Moreover, the differences between the sizes and depths of Φ ′ and Φ 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 to another sum node and no product node is connected to another product node. The set of those intermediate nodes is denoted by Φ 1 , and will be present in our later discussions. Next, we present a key property of partial derivatives, which holds for any (including non-binary) PC.Lemma 3.3. Given a PC Φ, if v and w are two nodes in Φ such that ∂ w f v ̸ = 0, then ∂ w f v is a homogeneous polynomial over the set of variables X v \ X w 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 v be a product node and w be any other node in a PC Φ, and deg(v) < 2 deg(w). The children of v are v 1 and v 2 such that deg(v 1 ) ≥ deg(v 2 ). Then ∂ w f v = f v2 • ∂ w f v1 .To construct the quasi-polynomial tree, the key is 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 of 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 to them will lead to compact expressions. Inspired by the observation in Raz and Yehudayoff [26] , we define the following set G m , which will be critical in our later process.Algorithm 1: Construction of Ψ Data: The original DAG-structured PC Φ with n variables of size poly(n), and the set of its nodes V Result: Another DAG-structured PC Ψ of size poly(n) and depth O(log n) i ← 0; V ← ∅; P ← ∅.for i = 0, 1, ⌈log n⌉ -1 do Fix m 1 ← 2 i ; Find all nodes v such that 2 i < deg(v) ≤ 2 i+1, and place them in V; Find all pairs of nodes (u, w) such that 2 i < deg(u)deg(w) ≤ 2 i+1 and deg(u) < 2 deg(w), and place them in P; for every v ∈ V do Find all nodes in G m1 and compute f v using Equation 15; end for every pair of nodes (u, w) ∈ P do Fix m 2,(u,w) ← 2 i + deg(w); Find all nodes in G m 2,(u,w) and compute ∂ w f v using Equation 17; end V ← ∅; P ← ∅. end Definition 3.5. Given a PC Φ and an integer m ∈ N, the set G m is the collection of product nodes t in Φ with children t 1 and t 2 such that m < deg(t) and max {deg(t 1 ), deg(t 2 )} ≤ m.With this set, we may choose a set of nodes as variables for partial derivatives for any node in a PC, and the following two lemmas respectively illustrate: 1) the compact expression of the sub-network polynomial f v for any node v in a PC; 2) the compact expression of ∂ w f v given two nodes v and w with a degree restriction. It is easy to observe that Φ 1 ∩ G m = ∅.We now present two key lemmas that will be central to 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 ∈ N and a node v such that m < deg 26] ). Let m ∈ N, and v and w be two nodes such that deg(w(v) ≤ 2m, then f v = t∈Gm f t • ∂ t f v . Lemma 3.7 ([) ≤ m < deg(v) < 2 deg(w), then ∂ w f v = t∈Gm ∂ w f t • ∂ t f v .Given a binary DAG-structured PC Φ with n variables and poly(n) nodes, we explicitly construct a tree PC with size n O(log n) and depth O(log n). 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(log n) and the same depth of Ψ.We will later show that step two can be simply done.Step one, however, needs much more careful operations. Each iteration, starting from i = 0, again needs two steps:1. Compute f v for each node v such that 2 i-1 < deg(v) ≤ 2 i using the compact expression illustrated earlier. We will show that, computing one such polynomial adds poly(n) nodes and increases the depth by at most two on Ψ. This new node representing f v will be a node in Ψ, denoted by v ′ . 2. Compute all partial derivatives ∂ w f u for two non-variable nodes u and w in Φ, such that u is an ancestor of w and2 i-1 < deg(u) -deg(w) ≤ 2 i and deg(u) < 2 deg(w).Like those new nodes representing sub-network polynomials from Φ, this new node representing a partial derivative will also be a node in Ψ, denoted by (u, w). We will show that computing a partial derivative with respect to each pair adds poly(n) nodes and increases the depth by at most two on Ψ.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 Result: A tree of size O(S D ) and depth D for every node v in V do if InDeg(v) > 1 then Duplicate the tree rooted at v for InDeg(v) -1 times; Construct an outgoing edge from each parent of v to itself. end endThe process is summarized in Algorithm 1. Before presenting the construction, we first confirm the quantitative information of Ψ, the output of the algorithm. The first observation is the number of iterations: The degree of the root of Φ is n, so at most log n iterations are needed for the entire process. Each iteration only increases the size of the updated circuit by poly(n) and the depth by a constant number. Consequently, the final form of Ψ has size poly(n) and depth O(log n).We now provide an inductive construction of Ψ starting from i = 0. After each step, it is necessary to verify the validity of the updated Ψ. Although decomposability is easy to verify, smoothness is less straightforward. To tackle this, we argue that the final state of Ψ is homogeneous, i.e. every node in Ψ computes a homogeneous polynomial, and consequently Ψ is smooth due to the following lemma. Lemma 3.8. If a decomposable PC contains n variables and computes a polynomial of degree n, then it is 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 v such that 0.5 < deg(v) ≤ 1; the degree of any node must be an integer, so we must have deg(v) = 1, i.e. v 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 a product node represents an affine polynomial, then it 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, if a sum node represents an affine polynomial and has exactly one child, then that child must also be a leaf node, hence we may again remove the sum node and connect that leaf to the parents of the original sum node. Due to smoothness, such an affine node v must represent a polynomial in the form ax + (1a)x, where x is the indicator of a variable, and 0 < a < 1. Therefore, the depth of each sub-network Φ v is only one. By duplicating all such affine nodes onto Ψ, we add at most poly(n) nodes and increase the depth by one only.Next, for step two, we only need to consider pairs of nodes (u, w) such that deg(u)deg(w) ≤ 1. Thanks to Lemma 3.3, we know that ∂ w f u 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 Ψ for each eligible pair, we again add at most poly(n) nodes and increase the depth by one to Ψ.Iteration i + 1: Suppose, after all previous iterations, we have already computed all sub-network polynomials f v for nodes v such that deg(v) ≤ 2 i , and all partial derivatives ∂ w f u for pairs of nodes (u, w) such that deg(u)deg(w) ≤ 2 i and deg(u) ≤ 2 deg(w). Like the base case, step i + 1 takes two steps: The first step computes f v for eligible 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.We conclude the proof of Theorem 3.1 in this section by transforming the newly constructed Ψ into a quasi-polynomial 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 2, and the detailed process of the entire transformation from the original Φ to the final tree is described in Algorithm 5.Duplication Strategy Given a DAG-structured PC of size V and depth D, a natural algorithm to a tree is that, if a node v has k > 1 parents, then duplicate the sub-tree rooted at v for k -1 times, and connect each duplicated sub-tree to a parent of v. Indeed this algorithm generates a 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 O(V D ).The construction of Ψ shows that its size is O(n 3 ) and depth is O(log n). Using the naive duplication, we obtain that the size of the final tree is n O(log n) .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
a conditional lower bound: 
 In this section, we present our second main result, which provides a lower bound on the tree complexity of a network polynomial given a restriction on the depth of the tree. Obtaining a lower bound for the problem of circuit complexity is 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 a 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 a concrete network polynomial that cannot be represented by a polynomial-sized tree-structured PC if the depth of the tree is restricted. Theorem 4.1. Given an integer k ≥ 1 and n = 2 2k , there exists a network polynomialP ∈ R[x 1 , • • • , x n , x1 , • • • , xn ] of degree n = 2 2k, such that any probabilistic tree of depth o(log n) = o(k) computing P must have size n ω (1) .Note that if the polynomial P is innately difficult to be represented by PCs, i.e., 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 a strictly larger size. Our next construction, described with more details in Algorithm 3, confirms a separation by constructing an efficient DAG-structured PC P * that computes P . This PC has size O(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.It is easy to check that P * has the correct size and depth as described earlier. Before adding leaf nodes, the algorithm in total constructs 2k r=0 2 r = 2 2k+1 -1 = 2n -1 nodes. Finally, observe that during the construction of leaf nodes, each negation indicator is added exactly k times: At a layer containing only product nodes, if a negation indicator is added to a product node v 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 a random variable is duplicated exactly k times, and finally the total size is 2n -1 + kn = O(kn) = O(n log n). The depth O(k) is also apparent from the algorithm. We therefore conclude that P can be efficiently computed by a polynomial sized tree PC for an unrestricted depth.However, the efficiency would be less optimal if we restrict the depth to o(k). To show this, we design a reduction from our problem for PCs to a well-studied problem on 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-sized tree-structured PC. This recent result is stated below. The proof of the lower bound for PCs in Theorem 4.1 is to show that, for any Π, a minimum treestructured 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 Π ′ with the same depth that computes the polynomial Q in the statement of Theorem 4.3. The size of Π ′ is super-polynomial due to Algorithm 3: Construction of P * , an efficient PC for P without a depth constraintData: A positive integer k, the number 2 2k , a set {x 1 , • • • , x 2 2k , x1 , • • • , x2 2k } of 2 2k+1 indicators Result: A tree PC of size O(n log n) and depth 2k = 2 log n j ← 0 Place all non-negation indicators x 1 , • • • , x 2 2k at the bottom layer; Label them as L 0,1 , • • • , L 0,2 2k . for i = 1, • • • , 2 log n do if i is odd then while j < 2 2k-i doConstruct a product node labelled by L i,(j/2) and two outgoing edges from the new node to L i-1,j-1 and L i-1,j ; j ← j + 2; end for every odd integer q = 1, 3,• • • , 2 2k-i -1 doAdd the leaves representing negation indicators {x z } for all z ∈ scope(L i,q+1 ) as children of L i,q ; Add the leaves representing negation indicators {x z } for all z ∈ scope(L i,q ) as children of L i,q+1 ; end end if i is even then while j < 2 2k-i do Construct a sum node labelled by L i,(j/2) and two outgoing edges from the new node to L i-1,j-1 and L i-1,j ; j ← j + 2; end end end Theorem 4.3, and as a result, the size of Π cannot be smaller. In other words, our proof involves a reduction from the PC problem to the AC problem. Before introducing the reduction, we first present the polynomial Q in the statement of Theorem 4.3. The original construction in Fournier et al. [11] is for the general class, but over here, we only present a specific case with r = 2, which is sufficient for our purpose.The Construction of the Polynomial Q We denote the polynomial Q by H (k,2) , which is defined overEQUATIONThe polynomial H (k,2) is recursively defined over intermediate polynomialsH u,v for all (u, v) ∈ [2] ≤k × [2] ≤k and |u| = |v|. Specifically, if |u| = |v| = k, then H u,v = x u,v ; otherwise, H u,v = r a=1 H u1,va H u2,va . The final polynomial H (k,2) is defined to be H ∅,∅ . Observe that the degree of H (k,2) is 2 k , and it contains 2 2 k -1 monomials.Given a 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 Π ′ ; without leaves representing negation variables, Π ′ is just a standard arithmetic formula. Clearly, |Π ′ | ≤ |Π|, and the next proposition reveals the polynomial computed by Π ′ , and its proof is in Appendix B.Proposition 4.4. The arithmetic formula Π ′ computes H (k,2) .Having all the necessary ingredients, we are now ready to conclude this section by proving Theorem 4.1, the main result of this section.Proof of Theorem 4.1. The proof of Theorem 4.3 in Fournier et al. [11] uses the polynomial class H (k,r) as the hard polynomial Q in the statement, in particular, with r = 2, n = 2 2k and d(n) = √ n = 2 k . Note that the depth of Π ′ is o(log d) = o(k), and the degree of H (k,2) is d = 2 k , so the conditions in the statement of Theorem 4.1 are indeed satisfied. Since Π ′ is obtained from Π by removing leaves, we obtain the following inequality that concludes the proof: (1) . ■|Π| ≥ |Π ′ | ≥ n ω 
conclusion: 
 In this paper we have shown that given a network polynomial with n variables that can be efficiently computed by a DAG-structured PC, we can construct a tree PC with at most quasi-polynomial size and is no deeper than O(log n). On the flip side, we have also shown that there indeed exists a polynomial that can be efficiently computed by a poly(n)-sized PC without a depth restriction, but there is a super-polynomial separation if we restrict the depth of the tree to be o(log n). Our results make an 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 a separation under a specific depth restriction. One potential direction for the future work are discussed below: although the upper bound n O(log n) is quasi-polynomial, it is still prohibitively large as n grows. The construction outputs a tree of depth O(log n), which would be considered as a shallow tree. Is it possible to further reduce the size of the tree, possibly in the cost of a larger depth?+ × × × x 2 + + x1 x 1 x1 x 2 x2 + × × x 2 + × × + + x1 x 1 x1 x 2 x2Figure 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. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 long-standing theoretical conjecture, and therefore shall not have direct societal impact.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 or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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, or 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 no such risks.• Released models that have a 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 to 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 not require this, but we encourage authors to take this into account and make a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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. The operation is the same if a product node has more than two children by just exchanging sum and product. Note that for one operation for a node with k 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 by2 × N ∈V out-degree of node N if N has more than two children -2V ≤ 2E -2V ∈ O(E).In fact, for depth, this upper bound is very conservative because, for example, if a 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. It is easy to check that each child of the root computes the same polynomial as before, and so does the new network. Clearly, the new network is still decomposable and smooth if the original network is.A.2 Proof of Lemma 3.3 Lemma 3.3. Given a PC Φ, if v and w are two nodes in Φ such that ∂ w f v ̸ = 0, then ∂ w f v is a homogeneous polynomial over the set of variables X v \ X w of degree deg(v)deg(w).Proof. Clearly, ∂ w f v ̸ = 0 implies that w is a descendant of v. We prove the statement by induction on L, the length of the longest directed path from v to w. If L = 0, i.e. w = v, then ∂ w f v = 1 and the statement trivially holds. Suppose the statement is true for all L and now the longest distance from v to w is L + 1. We prove the statement by discussing two cases, whether w is a sum or product node.Case I: w is a sum node. We first assume w is a sum node, and its parent inside this particular path v ⇝ w is u, whose children are w and w ′ . We write f v as the polynomial if we substitute w with y, and f v as the polynomial if we substitute u with y. Note that if we write them as functions with respect to y, then f v (y) = f v (y • f w ′ ), and henceEQUATIONBy the inductive hypothesis, ∂ u f v is a homogeneous polynomial over the set of variables X v \ X u of total degree deg(v)deg(u), so ∂ w f v must also be homogeneous, and its degree is deg(∂ u f v ) + deg(w ′ ) = deg(v)-deg(u)+deg(w ′ ) = deg(v)-deg(w)-deg(w ′ )+deg(w ′ ) = deg(v)-deg(w),and it is over variables(X v \ X u ) ∪ X w ′ = (X v \ (X w ⊔ X w ′ )) ∪ X w ′ = X v \ X w .Case II: w is a product node. Next, assume w is a product node. In this case, u is a sum node and deg(u) = deg(w) = deg(w ′ ), and X u = X w = X w ′ . Let the weight of the edge u → w be a, and the weight for u → w ′ be b. Then, f v (y) = f v (ay + bf w ′ ), andEQUATIONClearly, by the inductive hypothesis, both ∂ u f v and ∂ w f v are homogeneous, and they have the same degree and set of variables. Specifically, deg(∂ We now prove the statement by induction on L, the length of the longest directed path from v to G m , i.e.w f v ) = deg(∂ u f v ) = deg(v) -deg(u) = deg(v) -deg(w), and X w,v = X u,v = X v \ X u = X v \ X w . ■ A.3EQUATIONNow suppose the statement is true for all L, and now the longest directed path from v to G m has length L + 1.Case I: v is a sum node. First, assume v is a sum node andf v = a 1 f v1 + a 2 f v2 . Recall that, since v is a sum node, we have m < deg(v 1 ) = deg(v 2 ) = deg(v) ≤ 2m, so we may apply the inductive hypothesis on v 1 and v 2 . Therefore,EQUATIONHence, using the chain rule of the partial derivative, we haveEQUATIONCase II: v is a product node. Next, assume v is a product node and deg(v1 ) ≥ deg(v 2 ). If v ∈ G m, then the statement trivially holds like the base case, so we assume v / ∈ G m , and therefore m < deg(v 1 ) ≤ 2m and the longest directed path from v 1 to G m has length L, while such a path does not exist from v 2 to G m . So, by the inductive hypothesis,EQUATIONBy definition, if t ∈ G m , then we must have 2 deg(t) > 2m ≥ deg(v), and by Lemma 3.4,EQUATIONA.5 Proof of Lemma 3.7We again write v 1 and v 2 as the children of v, and again induct on L, the length of the longest directed path from v to G m in the network. If L = 0, then v ∈ G m , and same as the previous case, every other node t in G m is not a descendant of v, which impliesEQUATIONSuppose the statement is true for all L, and now the longest directed path from v to G m has length L + 1.Case I: v is a sum node. First, assume v is a sum node and f v = a 1 f v1 + a 2 f v2 . Again, since v is a sum node we may apply the inductive hypothesis on v 1 and v 2 :EQUATIONAgain, by the chain rule, we haveEQUATION)Case II: v is a product node. Now assume v is a product node and deg(v1 ) ≥ deg(v 2 ). If v ∈ G m ,then the statement trivially holds like the base case, so we assume v / ∈ G m , and therefore m < deg(v 1 ) < 2 deg(w) and the longest directed path from v 1 to G m has length L, while such a path does not exist from v 2 to G m . So, by the inductive hypothesis,EQUATION)Since deg(v) < 2 deg(w), and for all nodes t ∈ G m , we have 2 deg(t) > 2m > deg(v), so by applying Lemma 3.4 twice, we haveEQUATION) + × × x2 = ∂u 1 v1 + × × + + x1 x1 x1 x2 x2 v v1 u v2 v3 u1 = ∂x 2 v1 = ∂u 2 v2 u2 = ∂u 2 v3 = ∂x 1 v3 + × × × x2 + + x1 x1 x1 x2 x2 v1 v2 v3 u1 = ∂x 2 v1 = ∂u 2 v2 u2 = ∂u 2 v3 = ∂x 1 v3Figure 3 : The of converting an arbitrary DAG to a DAG with depth restriction. The red nodes are those in G 2 and their relationships imply the computational procedure.A.6 Proof of Lemma 3.8Suppose the network is smooth. Recall that if the root of a probabilistic circuit contains n variables, then the network computes a multi-linear polynomial of degree n. If the root is a sum node, then its children must be homogeneous with degree n. If the root is a 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 on the depth d of the network. If d = 1 and the root is a sum node, then the polynomial must be linear and therefore there can only be one variable x and x; as a result, this simple network is smooth. Now suppose the statement is true for any d, and we have a probabilistic circuit with depth d + 1. If the root is a product node, we are 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 two children with different scopes, because each sum node is in the induced sub-network rooted at a grandchild of the root of depth at most d -1 so the inductive hypothesis must hold. So, we only need to show X R = X R1 = • • • = X R k ,During iteration i + 1, a polynomial f v is in consideration if and only if 2 i < deg(v) ≤ 2 i+1 .Naturally we shall apply Lemma 3.6, and therefore choosing an appropriate m and the corresponding G m is essential. Here we choose m = 2 i . Moreover, we define a set T = G m ∩ Φ v for each v being considered; for every t ∈ T , we use t 1 and t 2 to denote its children. By Lemma 3.6 and the definition that all nodes in G m are product nodes, we haveEQUATION)Since t ∈ T , we must have max {deg(t 1 ), deg(t 2 )} ≤ m = 2 i , and therefore If a subset of the three terms {f t1 , f t2 , ∂ t f v } is a constant, then their product will be the weight of the edge connecting the product node f t1 • f t2 and the new sum node.EQUATIONWe now verify the validity of this updated circuit. Because Φ is decomposable and t is a product node, we conclude X t1 ∩ X t2 = ∅ and X t = X t1 ⊔ X t2 . By Lemma 3.3, we have Xt,v = X v \ X t = X v \ (X t1 ⊔ X t2). Therefore, every summand in Equation ( 15) is a product node whose children are sum nodes with pairwise disjoint scopes, and thus, the updated circuit must be decomposable as well. Also, since f v is a homogeneous polynomial, so must be every summand for each t. As a result, the updated circuit is also homogeneous. Thanks to Lemma 3.8, the updated circuit is valid. A.EQUATIONFurthermore, we may safely assume deg(w) ≤ deg(t 1 ), otherwise w is not a descendant of t 1 nor t and therefore ∂ w f t1 = ∂ w f t = 0. Next, by analyzing their degrees and differences in degrees, we show that for each t, the terms f t2 , ∂ w f t1 , and ∂ t f u in that summand have all been computed by earlier iterations or the step one during this iteration i + 1.EQUATIONwe haveEQUATIONHence, f t2 has already been computed during the first step of this current iteration or even earlier.Term ∂ w f t1 : Recall that deg(t 1 ) ≤ m = 2 i + deg(w), so deg(t 1 ) -deg(w) ≤ 2 i . Moreover, deg(t 1 ) ≤ deg(t) ≤ deg(u) < 2 deg(w).Therefore, the pair (t 1 , w) satisfies both requirements to be computed during iteration i or earlier.EQUATIONwhere the second inequality follows from deg(u)deg(w) ≤ 2 i+1 , the requirement of choosing u and w for iteration i + 1. Finally,EQUATIONThese two facts together ensure that ∂ t f u must have been computed during iteration i or earlier.Finally, we verify the validity of the updated circuit after this step. The new objects introduced in this step are only |T | product nodes whose children are f t2 , ∂ w f t1 , and ∂ t f u for each t ∈ T , and one sum node whose children are those |T | product nodes. It is easy to see that the sets X t2 , X t1 \ X w and X u \ X t are pairwise disjoint since X w ⊆ X t1 and X t1 ∩ X t2 = ∅; therefore, the updated circuit is 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.Case I: s -r > 1. In this case, the set scope(v r ) is {X 2r-1 , X 2r , X 2r+1 , X 2r+2 } if r is odd, {X 2r-3 , X 2r-2 , X 2r-1 , X 2r } if itis even; similarly, the set scope(v s ) depends on the parity of s. If sr = 2, then they have an identical parity. If they are both odd, then scope(v s ) = X 2(r+2)-1 , X 2(r+2) , X 2(r+2)+1 , X 2(r+2)+2 = {X 2r+3 , X 2r+4 , X 2r+5 , X 2r+6 }, and is disjoint with scope(v r ). The argument is identical if they are both even. If sr > 2, then the largest index among the elements in scope(v r ) is 2r + 2, and the smallest index among the elements in scope(v s ) is 2s -3 ≥ 2(r + 3) -3 = 2r + 3; hence, scope(v r ) ∩ scope(v s ) = ∅.Case II: sr = 1 and r is even. In this case, scope(v r ) = {X 2r-3 , X 2r-2 , X 2r-1 , X 2r } and scope(v s ) = {X 2s-1 , X 2s , X 2s+1 , X 2s+2 } = {X 2r+1 , X 2r+2 , X 2r+3 , X 2r+4 } because s = r + 1 is odd. Clearly, scope(v r ) ∩ scope(v s ) = ∅.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(i + 1)-1 = 2i + 1, which contains 2 2k-2i-1 product nodes, denoted by v 1 , • • • , v 2 2k-2i-1 .They must have non-leaf children, and we denote these nodes without their leaf nodes byv ′ 1 , • • • , v ′ 2 2k-2i-1. By construction, the layer 2i below contains 2 2k-2i sum nodes, denoted by w 1 , • • • , w 2 2k-2i ; and the layer 2i -1 contains 2 2k-2i+1 product nodes, denoted by z 1 , • • • , z 2 2k-2i+1 . For each 1 ≤ r ≤ 2 2k-2i-1 , the product node v r has children w 2r-1 and w 2r , and is their unique parent. Similarly, w 2r has children z 4r-1 and z 4r and is their unique parent; w 2r-1 has children z 4r-3 and z 4r-2 , and is their unique parent.We prove a simple fact that will simplify the induction step. We claim that, given two integers r, s ∈ {1, • • • , 2 2k-2i-1 } and r ̸ = s, the scopes scope(v ′ r ) and scope(v ′ s ) are disjoint. Without loss of generality, we assume r < s. By construction,Ch(v ′ r ) = {w 2r-1 , w 2r } and Ch(v ′ s ) = {w 2s-1 , w 2s }; fur- thermore, Ch(w 2r-1 ) = {z 4r-3 , z 4r-2 }, Ch(w 2r ) = {z 4r-1 , z 4r }, Ch(w 2s-1 ) = {z 4s-3 , z 4s-2 }, Ch(w 2s ) = {z 4s-1 , z 4s }.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(w 2r-1 ), scope(w 2r ), scope(w 2s-1 ), and scope(w 2s ) are pairwise disjoint. As a result, the scopes scope(v ′ r ) = scope(w 2r-1 ) ⊔ scope(w 2r ) and scope(v ′ s ) = scope(w 2s-1 ) ⊔ scope(w 2s ) are disjoint. Now we prove the induction step. In the first case, suppose v r and v r+1 are sibling, i.e. r is odd so v r+1 is the only sibling of v r . We have shown that scope(v ′ r ) ∩ scope(v ′ r+1 ) = ∅. However, step six enforces that scope(v r ) = scope(v ′ r ) ⊔ scope(v ′ r+1 ) = scope(v r+1 ), as desired. Next, suppose 1 ≤ r < s ≤ 2 2k-2i-1 and v r and v s are not siblings. Denote the siblings of v r and v s by v r ′ and v s ′ , respectively; by definition, r ′ ∈ {r -1, r + 1} and s ′ ∈ {s -1, s + 1}, depending on the parity of r and s. Clearly, the four nodes v r , v r ′ , v s , v s ′ are distinct, and consequently the four sets scope(v r ), scope(v r ′ ), scope(v s ), and scope(v s ′ ) are pairwise disjoint. Step six enforces that scope We first realize the polynomial P returned by Algorithm 3 without adding those leaves representing negation variables. Recall that layer one contains 2 2k-1 product nodes, and before adding negation variables, the bottom layer (layer zero) contains 2 2k leaves. If for every odd integer i ∈ {1, 3, 5, . . . , 2 2k -1}, we denote the monomial by f i,i+1 = x i x i+1 , then without adding negation variables, the polynomial can be constructed by the following recursion with 2k + 1 steps:(v r ) = scope(v ′ r ) ⊔ scope(v ′ r ′ ) and scope(v s ) = scope(v ′ s ) ⊔ scope(v ′ s ′ ),• Construct 2 2k-1 monomials x 1 x 2 , . . . , x 2 2k -1 x 2 2k .• Sum up 2 2k-2 pairs of consecutive monomials, and return 2 2k-2 polynomials with two monomials x 1 x 2 + x 3 x 4 , . . . , x 2 2k -3 x 2 2k -2 + x 2 2k -1 x 2 2k .• Multiply 2 2k-3 pairs of consecutive polynomials, and return 2 2k-3 polynomials.• Repeat the operation until only one polynomial is returned.Observe that this polynomial is exactly H (k,2) defined in Section 4 with an alternative set of indices for the variables ([2] k × [2] k versus [2 2k]). To prove Proposition 4.4, it is sufficient to show that for every minimum tree-structured probabilistic circuit Π 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 H (k,2) . To show this, we need the following lemma. Lemma B.2. In any tree-structured probabilistic circuit Π that computes P , no sum node has a negation indicator as a child, and no product node has only negation indicators as its children.The proof of Lemma B.2 relies on the following lemma on monotone arithmetic formulas. Lemma B.3. A monotone arithmetic formula computing a homogeneous polynomial must be homogeneous.Proof. If a formula is rooted at a sum node, then clearly every child of its must be homogeneous.If the root is a product node with k children, then denote the polynomials computed by them asf 1 , • • • , f k and write f = k i=1 f i . Furthermore, for each i ∈ [k], further assume f i contains q i monomials, and write it as Suppose Π does have a sum node u that has a negation indicator xi as a 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 i + 1, which is not homogeneous.EQUATIONSimilarly, 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 as v does, and without loss of generality we may assume none of its siblings computes the same polynomial as v does, so their degrees are higher than one. As a result, the replacements of all negation indicators to one will force the parent of v to compute a non-homogeneous polynomial, which contradicts Lemma B.3. ■ Now Proposition 4.4 can be confirmed, because the removal strategy will indeed produce a tree that computes H (k,2) , and no internal nodes will be affected, because Lemma B.2 ensures that, no internal node in Π ′ computes a constant one and can be removed.Algorithm 5: Construction of the tree Data: a binary DAG-structured PC Φ with V nodes and n variables Result: a tree-structurd PC with size 2 O(log 2 n) T ← ∅;P i ← ∅, Q i ← ∅, G 2 i ← ∅, G 2 i ,w ← ∅ for i ∈ {1, • • • , log n} and w ∈ Φ; Φ v ← ∅ for v ∈ Φ; m ∈ N isnot defined yet Operate Algorithm 4 and return G 2 i and G 2 i ,w for all i ∈ {1, • • • , log n} and those w ∈ Φ that were selected for computing partial derivatives.for i = 1 to log n do m ← 2 i . for v ∈ P i do T ← G 2 i ∩ Φ v ; for t ∈ T do Create a product node ⊗ t computing f t1 • f t2 • ∂ t f v . end Create a sum node ⊕ v that sums over all ⊗ t ; for t ∈ T such that ∂ t f v is a non-zero-or-one constant, the edge ⊕ v → ⊗ t has weight ∂ t f v . end for (v, w) ∈ Q i do m ← 2 i + deg(w), T ← G 2 i ,w ∩ Φ v ; for t ∈ T do Create a product node ⊗ t computing f t2 • ∂ w f t1 • ∂ t f v . endCreate a sum node ⊕ (v,w) that sums over all ⊗ t ; for t ∈ T such that ⊗ t contains a constant multiplier, the edge ⊕ (v,w) → ⊗ t 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.NeurIPS Paper ChecklistJustification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper studies the expressive power (i.e., expressive efficiency) of tree-structured probabilistic circuits (PCs). Specifically, this paper shows that:
- 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.
- 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)}.
strength_weakness: strength_weakness: n/a
questions: questions: n/a
limitations: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: - Could the authors provide some new insights on how this work can help further research in PC structure learning?
- 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: limitations: The authors have discussed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Sometimes, 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.
questions: 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.

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.

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.

The linebreak in Lemma 3.6 can be confusing to the reader.

Algorithm 1: Definition of $m_2$ is unclear, since $w$ is not specified.

Oliver Broadrick, Honghua Zhang, Guy Van den Broeck:
Polynomial Semantics of Tractable Probabilistic Circuits. CoRR abs/2402.09085 (2024)
limitations: limitations: Authors discuss the limitations briefly but sufficiently.

Comments: comment: Thanks for the response. I am happy to keep my score.
Thank you for the response. I'll keep my score.