On the Expressive Power of Tree-Structured Probabilistic Circuits

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.

Strengths

The paper is well-motivated and, in general, written well. PCs are an active area of research. The 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. 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

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)

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Authors discuss the limitations briefly but sufficiently.

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.

Strengths

- This paper is well-organized and logically coherent. - This paper provides novel theoretical insights into a relatively under-explored topic (DAG-structured PCs). - 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.

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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors have discussed the limitations of their work.

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)}.

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

Questions

n/a

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

n/a