A Compositional Atlas for Algebraic Circuits

The high-level contributions are not very clear from the text (in particular in the first sections). [35] clearly listed their contributions at the end of their introduction, in contrast, I found lines 39-42 more vague in this sense, giving the (wrong) idea that the compositional approach is a novelty.

We will add a contributions statement at the end of the introduction. To summarize, the key contributions are (1) a more general compositional inference framework that covers circuits over arbitrary semirings, including logical and probabilistic circuits; (2) a conceptually simple, yet general formulation in terms of just three basic operations (aggregation, products, elementwise mappings), with associated tractability and composability conditions (Table 1); (3) novel and systematically derived tractability conditions for a range of existing inference problems (Table 2).

Q2 Could you similarly outline what are the key ideas / existing work this work builds upon?

Our work mainly draws on three lines of existing work.

• Firstly, work on new structural properties for tractable inference on circuits (e.g. $**X**$-determinism [6] for marginal MAP and compatibility [35] for products).
• Secondly, the compositional approach to inference [12, 35], which characterizes tractability conditions for individual operations and which properties are maintained by the output of the operations (composability conditions).
• Finally, algebraic model counting [21, 20], which casts many inference queries as aggregation over a particular semiring.

Our conceptual contribution is to combine the generality of compositional inference with semiring structure. In the process, we make use of many of the recently introduced circuit properties (and extend them where required).

Q1 Could you clearly outline what are the novel notions that enable this generalized compositional framework?

The key novel notions that enable the generalized compositional framework are (1) the elementwise mapping operation and (2) extended composability conditions. In more detail:

• Elementwise Mapping: A key novel contribution is our definition of elementwise mappings as a modular operation, which covers e.g. the (implicit) transformation from the Boolean circuit in algebraic model counting, 2AMC when moving from the inner to the outer semiring, and various mappings on the probability semiring such as reciprocals.

  • This abstraction is crucial in that it allows us to extend the compositional approach to inference to a much wider range of problems that were not addressed in [35]. In contrast to prior works on algebraic inference, this is independent of particular formalisms (e.g. labeling functions in AMC), whether the input circuit is a logic circuit (DNNF) or PC, etc.

  • In terms of the practical impact, the compositional approach provides a simple and robust recipe for finding sufficient tractability conditions: simply write down the inference query in math, and apply Table 1 to each operation. For example, this enabled us to discover a mistake in the 2AMC tractability conditions [20], and elegantly extends compositional inference for probabilistic circuits to maximization, which was mentioned in the conclusion of the PC atlas paper [35] as an open problem.

• Composability Conditions: A limitation of [35] is that the analysis of composability conditions was incomplete. In particular, there was no result on transitivity of compatibility (in fact, we show in Example 3 in the Appendix that this is actually not true). This is critical for the proofs of tractability for the queries in Table 2 using the compositional approach. To this end, we introduced $**X**$-compatibility and $**X**$-support-compatibility as new properties which do satisfy ``transitivity'' conditions, and prove these in Table 1/Section 3.2.

Q3 Could you provide examples (for the general NeurIPS audience rather than experts in AMC and AC) of the practical impact of this contribution?

The compositional queries we consider in this paper have many applications which are of interest to the NeurIPS community. For example, PCs have been used to compute interventional distributions in causal inference [36]. By reducing the complexity of backdoor adjustment for PCs from quadratic to linear (given $**Z**$-determinism), we open up the possibility of scaling up PC models for causal inference. The probabilistic ASP queries we consider are of significant interest in neuro-symbolic AI [b,c,d], where circuit representations are widely used to encode symbolic knowledge. Our work clarifies which circuit types can be used depending on the desired semantics.

Given the connections that we establish between these disparate queries, we believe that our work will motivate more research on compiling as well as learning expressive circuits satisfying the properties that we identify.

We believe that our work will also open up new applications for circuits within ML. For example, recent work has examined using circuits for generating text satisfying logical conditions [a], with quality comparable to LLM approaches; this relies on tractable products between the logical and probabilistic circuits. The PC used is a HMM, which is $**X**$-deterministic where $**X**$ are the hidden states (e.g. Figure 4 in the Appendix); our compositional algebraic atlas shows that it would be tractable to find the most likely hidden state conditional on the logical constraint, which could be used for model explainability.

[a] Zhang et al. ``Tractable Control for Autoregressive Language Generation'' ICML 2023.

[b] Zhun et al. ``NeurASP: Embracing Neural Networks into Answer Set Programming'' IJCAI 2020.

[c] Mahaeve et al. ``Neural probabilistic logic programming in DeepProbLog'' AIJ 2021.

[d] Huang et al. ``Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning'' NeurIPS 2021.

I think that some results requiring particular semirings and homomorphisms require so many properties that make me wonder their actual contribution. Tractable mapping (Theorem 4) requires the following combination of properties to be both true...

Please see response to Q1/Q2 below.

Theorem 3 claims that one can compute the product of support compatible circuits linearly in the maximum circuit size for both time and memory...

This is a good point, thanks. We agree and will make this clear in the revised draft.

In line L298-L300, the authors claim that for particular semirings and mappings, one could relax the determinism property from the circuit for tractable 2AMC. However, this does not seem to be reflected in table 2, where X-Det is present in all 2AMC queries...

By this we mean that one can relax determinism (i.e. $**V**$-determinism), while $**X**$-determinism is always required. For example, for the PASP (Max-Credal) query, determinism is not required. We will rephrase to make this clearer.

Looking at Algorithm 2 and 3, I think there are corner cases that are not covered neither by them nor by the proofs. For example, the case of multiplying a sum node and a product node is missing...

Thanks for pointing this out. For Algorithm 2, we have now added the cases of multiplying an input or product node with a sum node (this corresponds simply to multiplying the input/product with the children of the sum). We have also made minor changes to the proofs for Thm 2 and Thm 5.2 to account for this corner case. Please see the PDF response for the full details. As for multiplying an input with a product, this also seems to be an omission in [35]. We will address this by adding the condition that input nodes do not have scope overlapping with both children of a product to the compatibility definition.

As for Algorithm 3 (support-compatible products), these cases are disallowed by the isomorphism scope condition (i), since for smooth and decomposable circuits, sum nodes have children with the same scope, product nodes have children with disjoint scopes, and input nodes do not have children. We will add this point in the proof of Theorem 3.

I believe a minor weakness of the presentation of this paper is that it mixes two kinds of theoretical results. It contains some results that leverage algebraic circuits and specific properties regarding semirings and morphisms (e.g., Theorem 4)...

Thank you, this is very helpful feedback presentation-wise. The results for aggregation and products are indeed semiring-agnostic, depending only on the generic semiring $\oplus, \otimes$ and circuit scope/support properties, while the results for elementwise mappings do depend on the specific mapping/semirings. We will clarify this at the start of Section 3.

Q1/Q2: If we restrict to be both additive and multiplicative homomorphisms, then does this imply it can only be identity function?... Following Question 1, are there examples of both additive and multiplicative homomorphisms for some particular choices of source and destination semirings?

As noted in [35], over the probability semiring the only additive and multiplicative homomorphism is the identity function. For other semirings, there are more such functions (known as semiring homomorphisms). For example:

• Corollary 1 shows that the support mapping $$ [p \]$$_{\mathcal{S} \to \mathcal{S}'} always satisfies (Multiplicative), and satisfies (Additive) if (a) no element except $0 _{\mathcal{S}}$ has an additive inverse in $\mathcal{S}$ and (b) $\mathcal{S}'$ is idempotent. Examples of such $\mathcal{S}$ include the Boolean, probability and $(\max, \cdot)$ semirings, while examples of $\mathcal{S}'$ include the Boolean, $(\max, \cdot)$, and tropical $(\min, +)$ semirings. The support mapping is a semiring homomorphism in these cases, and is not the identity function unless $\mathcal{S}, \mathcal{S}'$ are both the Boolean semiring.
• For the semiring $\mathcal{S} = \mathcal{S}' = (\max, \times)$ semiring, any function $f(x) = x^{\beta}$ is a semiring homomorphism.
• For the tropical semiring $\mathcal{S} = \mathcal{S}' = (\min, +)$, any function $f(x) = c \cdot x$ is a semiring homomorphism.
• For the rings $\mathcal{S} = \mathbb{Z}$ and $\mathcal{S'} = \mathbb{Z} _{12}$ (the rings of integers, and integers modulo $12$), then $f(x) = 4 \cdot x \text{ mod } 12$ is a (semi)ring homomorphism.

That said, semiring homomorphisms are a very restricted class of functions and for most of the useful mappings we consider (aside from the support mapping) at least one of the circuit-specific conditions (determinism or the product node condition) will need to hold.

Q3 It seems the support-compatibility definition does not consider how scopes of products are factorized. What is the relationship between support compatibility between circuits and compatibility + determinism? Is structured decomposability PLUS determinism in a circuit more restrictive than support-compatibility with itself?

The reason that support-compatibility does not consider factorization of scopes is because of the isomorphism which requires scopes of isomorphic nodes to match; thus the necessary scope factorization is already satisfied. Support-compatibility and compatibility+determinism are different properties and incomparable in general; in particular, support-compatibility does not require compatibility (e.g. any decomposable, smooth, deterministic circuit is compatible with itself), while two circuits can be compatible and both deterministic, but not necessarily share the same "support decomposition". On the other hand, structured decomposability + determinism is strictly stronger than support-compatibility with itself (just decomposability + determinism would suffice).

My main problem with the paper is that it only discusses sufficient conditions (also acknowledged by the authors). This is contrast to the probabilistic circuit atlas [1].

Although we only discuss sufficient conditions, for Table 1, the necessity of these conditions in general follows from the results in the PC atlas, as those are special cases in the probabilistic semiring. The point we are trying to make is that, inevitably, even though the conditions are necessary in general, they might not be for a specific semiring (and a specific elementwise mapping).

For the specific compositional queries in Table 2, we show hardness for 2AMC without these conditions in Theorem 7, while hardness results for the causal inference queries are given in [36].

This in itself is not a problem, however, the paper does not discuss the problem of eighted model integratio, which has also been formulated as an AMC problem with integration as an extra operation [2]. In general WMI is intractable, however, it has been shown that there exist tractable fragments [3]. If I understand the paper correctly, the tractable fragment of WMI does not fall within the proposed framework. This is quite limiting as the framework does not even cover all tractable problems that can be formulated as 2AMC.

Thank you for bringing up these works on WMI. We will add these references and a discussion to our related work section.

In [2], the authors propose to solve hybrid WMI problems by (i) performing AMC over the probability density semiring; and (ii) performing symbolic computation of the resulting expression. The first step (i) is captured by AMC, and thus in our framework (cf. lines 255-262), showing that d-DNNF suffices for valid evaluation (aggregation). We note that the integration step (ii) here uses a symbolic inference engine (or sampler), as opposed to being part of the AMC itself.

[3] shows certain fragments of WMI are tractable through a message-passing algorithm; however, it is unclear if and how the WMI problems being considered could be represented as an AMC problem on circuits, and how the message-passing algorithm would translate to circuits. Our work concerns compositional inference problems (including AMC/2AMC) on circuit representations, and in particular it encompasses all AMC/2AMC problems on circuits, as we show in Theorems 7 and 8.

Tractable algebraic circuits seem to be highly related to performing tractable inference on first-order circuits. [4] This relationship is not discussed at all.

Our work focuses on circuits where the nodes are algebraic expressions (e.g. propositional formulae in NNFs); in particular, the expressions are not defined over a domain as in first-order circuits. We would be happy to clarify any specific questions the reviewer has about the relationship of our work with this paper.

the conditions under which the algorithms are efficiently applicable seem rather restrictive

We agree that the sufficient conditions for tractability of many compositional queries can be strong. However, part of our contribution is that our framework is able to derive weaker tractability conditions than were previously known. For example, we show that $**X**$-firstness is not necessary for probabilistic answer-set programming inference (under the max-credal or max-ent semantics), and that this can lead to exponentially smaller circuits (Thm 9).

Despite the high complexity of these problems, there already exist tools for compiling or learning circuits satisfying these properties (e.g. PySDD [a] and PSDD [b, c] for $**X**$-firstness and $**X**$-determinism, MDNets [36] for $**X**$-determinism). We believe that our work should motivate further study on compilation and learning algorithms for circuits satisfying these properties, given the generality of these properties across multiple inference tasks. j

[a] Meert & Choi (2017) PySDD. In Recent Trends in Knowledge Compilation, Report from Dagstuhl Seminar 17381, Sep 2017.

[b] Kisa et al. (2014) Probabilistic Sentential Decision Diagrams. In KR.

[c] Liang et al. (2017) Learning the structure of probabilistic sentential decision diagrams. In UAI.

what is an "atlas"? the word is never used in the text

We use "atlas" to refer to the collection of operations and corresponding tractability conditions we derive (Table 1); it also refers to a closely related recent work [35] that considered compositional inference for probabilistic circuits.

the classic circuit classes have an uniformity constraint, on the complexity of an algorithm that computes the circuit for a certain input length. do these algebraic circuits not need uniformity ?

Indeed, for Theorem 9, we use a family of algebraic circuits $C_1, ..., C_n$ to specify functions, such that the smallest $**X**$-first circuits have an exponential lower bound on size. This family is indeed logspace-uniform; note however that we don't make any claims in terms of membership of languages in complexity classes, merely on the size of the circuits computing the function. We will make this point clearer in the revised version.

Theorem 2 why not just add one new product node as root node, and then make both C and C' children of this new node. it is a much simpler construction and would also compute the product.

This is possible, but the resulting circuit would not be decomposable if $C$ and $C'$ share variables. As the queries we (and the majority of other works in the knowledge compilation/tractable model literature) consider require aggregation subsequent to products, we restrict to algorithms producing decomposable and smooth circuits.