Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs
Authors: Milan Papez
Martin Rektoris
Vaclav Smidl
Tomáš Pevný
Venue: ICLR 2024 poster (2024)
Keywords: Sum-product networks
graph neural networks
probabilistic circuits
tree-structured graphs
supervised learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We propose sum-product-set networks, an extension of probabilistic circuits for tree-structured graphs.

Abstract: Daily internet communication relies heavily on tree-structured graphs, embodied by popular data formats such as XML and JSON. However, many recent generative (probabilistic) models utilize neural networks to learn a probability distribution over undirected cyclic graphs. This assumption of a generic graph structure brings various computational challenges, and, more importantly, the presence of non-linearities in neural networks does not permit tractable probabilistic inference. We address these problems by proposing sum-product-set networks, an extension of probabilistic circuits from unstructured tensor data to tree-structured graph data. To this end, we use random finite sets to reflect a variable number of nodes and edges in the graph and to allow for exact and efficient inference. We demonstrate that our tractable model performs comparably to various intractable models based on neural networks.

Published as a conference paper at ICLR 2024
SUM-PRODUCT-SET : DEEP TRACTABLE MODELS FOR TREE-STRUCTURED GRAPHS
Milan Papež, Martin Rektoris, Václav Smídl & Tomás Pevný Artificial Intelligence Center, Czech Technical University (papezmil 1, rektomar, smi vlval, pevnyt.om) @feel cvut.cz
ABSTRACT
Daily internet communication relies heavily on tree-structured graphs, embodied by popular data formats such XML. and JSON. However, many recent gener- ative (probabilisstic) models utilize neural networks to learn a probability distri- bution over undirected cyclic graphs. This assumption of a generic graph struc- ture brings various computational challenges, and, more importantly, the presence of non-linearities in neural networks does not permit tractable probabilistic in- ference. We address these problems by proposing sum- cum-product-sel networks, an extension of probabilistic circuits from unstructured tensor data to tree-structured graph data. To this end, we use random finite sets to reflect a variable number of nodes and edges in the graph and allow for exact and efficient inference. We demonstrate that our tractable model performs comparably to various intractable models based on neural networks.
INTRODUCTION
One of the essential paradigm shifts in artificial intelligence and machine learning over the last years has been the transition from probabilistic models over fixed-size unstructured data (tensors) to prob- abilistic models over variable-size structured data (graphs) (Bronstein et al., 2017; Wu al., 2021). )). Tree-structured data are specific type of generic graph-structured data that describe real or abstract objects (vertices) and their hierarchical relations (edges). These data structures appear many sci- entific domains, including cheminformatics (Bianucci et al., 2000), physics (Kahn et al., 2022), and natural language processing (Ma et al., 2018). They are used by humans in data-collecting mecha- nisms to organize knowledge into various machine-genenn 2016), XML (Tekli et al., 2016) and YAML (Ben-Kie Kiki et al., 2009) to mention few. Designing a probabilistic model for these tree-structured file formats is one of the key motivations of this paper.
formats, such as JSON (Pezoa et al.,
The development of models tree-structured data has been thoroughly, but almost exclusively, pursued in the NLP domain (Tai et al., 2015; Zhou et al., 2016; Cheng et al., 2018; Ma et al., 2018). Unfortunately, these models rely solely on variants neural networks (NNs), are non non-generative, and lack clear probabilistic interpretation. There has also recently been growing interest in designing generative models for general graph-structured data (Simonovsky & Komodakis, 2018; De Cao & Kipf, 2018; You et al., 2018; Jo et al., 2022; Luo et al., 2021). However, the underlying principle of these generic models is to perform the message passing over a neighborhood of each node in the graph, meaning that they visit many of the nodes several times. Directly applying them to the trees and not adapting them to respect the parent-child ancestry of the trees would incur unnecessary computational costs. Additionally, these models assume that the features are assigned to each node and all have the same dimension. More importantly, they preclude tractable probabilistic inference, necessitating approximate techniques to answer even the most basic queries.
In sensitive applications (e.g., healthcare, finance, and cybersecurity), there is an increasing legal concern about providing non-approximate and fast decision- mrriiiin-making.. Probabilistic circuits (PCs) (Vergari et al., 2020) are tractable probabilistic (generative) models that guarantee to answer large family of complex probabilistic queries (Vergari et al., 2021) exactly and efficiently. For instance, the marginal queries form the fundamental part of many more advanced queries. Their practicality lies in allowing us to consistently address various tasks, including dealing with missing data (Peharz al., 2020) and explaining anomalous samples (Lüdtte et al., 2023). This paper is interested in

---

Published as a conference paper at ICLR 2024
"Rogpts
Reconeics toty Scarçett -3.227, "bondhi To taccaty
feloowsch Schaagef 3,040, "bond"s by "accafy
"hhaggtt -5.117,
Mecement toty fcharpefs -3,03, "bonot: Sa "atceff
0.142,
Figure 1: Tree-structured graphs. Left: example of molecule from the Mutagenesis dataset (Debnath al., 1991) encoded in the JSON format. Right: the corresponding, tree-structured graph, T (Definition I), describing relations between the atoms and their properties, and xchema (dashed line), (Definition 2). Here, A is the heterogeneous node (green), 7 is the homogeneous node (orange). and x is the leaf node (blue).
specific sub-type of PCs--sum-rrouuc networks (SPNs) which represent probability density over fixed-size unstructured data (Poon & Domingos, 2011).
To our knowledge, SPN is designed to represent probability distribution over variable-size, tree-structured graph. Here, it is essential to note that an SPN is also graph. To distinguish between the two graphs, we refer to the former as the data graph and the latter the computational graph. Similarly, to distinguish between the vertices of these two graphs, we refer to vertices of the data graph and computational graph as data nodes and computational units, respectively. We propose a new SPN (i.e., a new type of PCs) by sceing the data graph as recursive hierarchy of sets, where each parent data node undirected cyclic graphs, our model respects the parent-child direction when processing the data graph. We use the theory of random finite sets (Nguyen, 2006) to induce a probability distribution over repeating data subgraphs, ie.. sets with identical properties. This allows to extend the computational graph with an original computational unit, sel unit. Our model provides an efficient sampling of new data graphs and exact marginal inference over selected data nodes, which allows us to deal with missing parts of the JSON files. It also permits the data nodes to have heterogeneous features, where each node can represent data of different dimensions and modalities.
set of its child data nodes. Unlike the aforementioned models for the
In summary, this paper offers the following contributions:
We propose sum-product-set networks (SPSNs), extending the predominant focus of PCs from unstructured tensor data to tree-structured graph data (Section 3).
We show that SPSNs respecting the standard structural constraints of PCs are tractable under mild assumptions on the set unit (Section 3.
We investigate the exchangeability of SPSNs, concluding that SPSNs are permutation invariant under the reordering of the arguments the set units and input units (if the input units admit some form of exchangeability) and that the invariance propagates through SPSNs fundamentally based on the structural constraints (Section 3.2).
We show that SPSNs deliver competitive performance to intractable models relying on much more densely connected and highly nonlinear NNs, which are unequipped to provide exact answers to probabilistic queries (Section 5).
2 TREE-STRUCTURED DATA
A single instance of tree-structured, heterogeneous data is given by attributed data graph, T. In contrast to a fixed-size, unstructured, random variable, x = (#1...., Fn)) E X S R", this graph forms hierarchy of random-size sets.
Definition 1. (Data graph). T= EV,E,X) is an attributed, tree-structured graph, where V is set of vertices, E is a set of edges, and X a set of attributes (features). == [L, O) splits into three subsets data nodes: leaf nodes, L. heterogeneous nodes, H, and homogeneous nodes, O. Let ch(v) and pa(v) denote the set of child and parent nodes of v E V, respectively. All elements of ch(v) are of identical type if O, and some or all elements of ch(v) are of a different type
2

---

Published as a conference paper at ICLR 2024
SPSN block
08
SPSN block
SPSN block
(a) Schema
SPSN
(e) SPSN black
Figure 2: Sun-product-ser networks. (a) The schema (Definition 2) from the example in Figure 1. (b) The SPSN network comprises SPSN blocks that correspondingly model the heterogeneous nodes depicted (a). (c) The SPSN block embodies the computational (sub)graph, G, (Definition 3), where +, x, {.} and p are the sum unit, product unit, sef unit and input unit of G. respectively. The elements of the heterogeneous node in (a) modeled by the corresponding parts of G in (c), displayed in green, orange, and blue.
if U H. We assume that only the leaf nodes are attributed by x. E N. S IR"", with possibly different space and its dimension for each v E L.
Definition 2. (Schema). Let T be a rre-structured, heterogeneous data graph (Definition 1). Then, subtree, S, which results from T by following all children of each v E H and only one child of each U E O-such that it allows us to reach the deepest level of T is referred to as the schema'.
We model each heterogeneous node, Tp = (TT,....,Tw..) E To. U H, as a finite set. ordered set of features other sets, Tue E Tu. where the elements random but their number, m E Ng, is fixed. For v E H, To is the Cartesian product space composed of the spaces corresponding to the elements of Tę. Importantly, we propose model each homogeneous node, T, := {Tw...... Twm E T., E O, as a finite random set (RFS), i.e., a simple, finite point process (Van Lieshout, 2000; Daley et al., 2003; Nguyen, 2006; Mahler, 2007). This is an unordered set of distinct features or other sets, such that not only the individual elements, Ter E Te, are random, but also their number, m E No. is random. For v E O, To = F(Tw) is the hyperspace of all finite subsets of some underlying space Th (which is common to all elements). We refer to Section B for more details on RFSs. The leaf node, Tg = X, (.1...., Tm)) E Tu, L, contains feature vector (i.e., it is also finite set). For e L. To is usually subspace of Rm.. We show an example of single instance of tree-structured data in Figure I, where T (I, T,, x, (xx, (Zz, x, 2, 2), (2z, 2, 2)) r)...., (z, {(1, ær x, x, x)) x, x,,,),) x)}). The whole tree T lives a hybrid space T, i.e., a product space composed of continuous spaces, discrete spaces, and hyperspaces of other RFSs. Each T is thus hierarchy of several RFSs. Indeed, such constructions are possible and are used to define "random cluster processes" (Mahler, 2001; Mahler & MN, 2002).
It follows from Definition 1 and Definition 2 that, for heterogeneous nodes, E H, each child subtree, T.. has different schema for all w E ch(u); whereas for homogeneous nodes, E O, each child, T. has the same schema for all w ch(v). This further implies that can defined recursively by a subtree, T. == [Ta, .... Tww.. rooted at v E V, where the parentheses [-] instantiate into } for homogeneous nodes, and into (-) for heterogeneous nodes, to distinguish if the number of elements is random or not. Note also that the number of elements in homogeneous nodes, v E O, differs for each instance of T. while remains the same for all heterogeneous nodes, E H.
Problem definition. Our objective is to learn a probability density over tree-structured graphs (Def- inition 1), P(T), given collection of observed graphs (Ti,..., Tm,), where each T, contains a different number of vertices and edges but follows the same schema.
Recall that one the key motivations of this paper is to design a probabilistic model for the tree-structured file formats (Section 1). The intuition hehind Definition 2 follows from the schema of the JSON files (Pezoa al., 2016). We do not consider the schema used in the relational databases.
3

---

Published as a conference paper at ICLR 2024
3 SUM-PRODUCT-SET NETWORKS
A sum-product-set network (SPSN) is a probability density over a tree-structured graph, p(T). This differs from the conventional SPN (Poon & Domingos, 201 1), which is a probability density over the unstructured vector data, p(x). For short introduction to SPNs, see Section A in the supplementary material. We define an SPSN by a parameterized computational graph, G. and a scope function, v..
Definition 3. (Computational graph). G (V,E,0) 0) is parameterized. directed, acyclic graph, where V is a set of vertices, & is set of edges, and 0 E θ are parameters. V = (S, P, B, 1) contains four subsets of computational units: sum units, S. product units, P. set units, B. and input units, I. The sum units and product units have multiple children; however, as detailed later, the set unit has only two children, ch(u) := b), and normalized weights, (wu.o)eEchtu). Wa,e 2 O, Eeech(u) Wu,e = 1, u E S, and parameters of imput wnits which are specific to possibly different densities.
B. 9 contains parameters of sum units, i.e., non-negative
Definition 4. (Scope function). The mapping Vh : ->>> F(T)-from the set of units to the power set of T T-outputs a subset of I for each V and is referred to as the scope function. If is the root unit, then tha = T. If u is a sum unit, product unit, or set unit, then thu = Ungeh(a) Vo-
Each unit of the computational graph (Definition 3), w E V. induces a probability density over a given (subset of) node(s) of the data graph (Definition 1), V. The functionality of this density, (T,)). v), depends on the type of the computational unit.
The sum unit computes the mixture density, Pi, = Eecchtu) Wu,cPe(Ti), u E S. U (L, where Wu.e the weight connecting the sum unit with child unit. The product unit computes the factored density, (T,, = Ieeech(w) Pe(W)c), u E P. (L. It introduces conditional independence among the scopes of its children, te. establishing unweighted connections between this unit and its child units. The input unit computes a user-defined probability density, pa (x,), E I, L. It is defined over a subset I, of == x,, corresponding to the scope, thu which can be univariate or multivariate (Peharz et al., 2015).
The newly introduced set unit computes a probability density of an RFS,
(I) E B, u E O, where p(m) is the cardinality distribution, and p(Twiy..... Tw...) is the feature density (conditioned on m). These are the two children of the set unit (Definition 3), spanning computational subgraphs on their own (Figure 2). The proportionality factor, m! I i, comes from the symmetry of p(Tw..................... , It reflects the fact that p p(Tw........ Twn. ) is permutation invariant, i.e., it gives the same value to all mn! possible permutations of (Tm...... T Tw... J. Recall from Section that T, E F(TT),, where To is the underlying space of the RFS. e is a constant with units of hyper-volume of Tw. which ensures that (1) unit-less by canceling out the units of p(Tw....... ) with the units of cm This mechanism is important when computing integrals with (1). Section B provides more details on the subject of integrating functions of RFSs. Note that, contrary to the other units, the set unit is defined only for the homogeneous node, v E O.
(T(T,) = plm))"mmppTTw... mlp(Tu....... Tw...:
Assumption 1. (Requirements on the set unit). We make the following requirements on the proba- bility density of the set unit: (a) each element T == {Tw,,... wwy..... Twm) } resides in the same space, i.e. Tw E Tw for all w E ch(e); (b) the realizations {Tw,:... Twnn I are distinct; (c) the nality distribution p(n) = for a sufficiently large m; and (d) the elements (Twp...., Tw... are independent and identically distributed (i.i.d)).
=T
Assumptions 1(a-c) are the standard assumptions on RFSs (Section B). Assumption 1(d) reduces the feature density in (1) to the product of m densities over the identical scope, p(T TT...) P(T w::) (i.e., not the disjoint scope and, therefore, it is not the product unit), where each p( (T)))) is indexed by the same set of parameters. Consequently, the feature density treats {Tu,, w; iis as i..d. instances, aggregating them by the product of densities. Note that, if Assumption (d) holds, and p(m) is the Poisson distribution, then (1) is the Poisson point process (Grimmett & Stirzaker, 2001). We provide more comments on Assumption (d), including a possible way to relax it, in Remark 2.
Constructing SPSNs. We illustrate the design of SPSNs in Figure 2. The construction begins with extracting the schema of the data graph (Figure 2(a) which corresponds to the example of in Fig- ure 1). Then, starting from the top of the schema, we create SPSN block for each heterogeneous
4

---

Published as a conference paper at ICLR 2024
node (Figure 2(b)). The SPSN block (Figure 2(c)) alters many layers of sum units and product units (green). Every time there is a product layer, the heterogeneous node, T, == (Tw,,... Twmm) ). is the number of children of the product units) parts, T,, and
split into two (or multiple depending Thg. This process is repeated recursively until Tep and Te, are either singletons or subsets that result from user-defined limit on the maximum number of product layers in the block. Each of these subsets or singletons is then modeled by the input unit (blue). Importantly, this reduction always has to separate all homogeneous nodes out of the heterogeneous node, T., as single elements modeled by the ser unit (orange). Note that the sum units create duplicate parts of the computational graph (children have an identical scope), which we leave out in our illustration for simplicity (the dashed line). The consequence is that there will be multiple set units. We gather all edges leading from the feature density of these set units and connect them to the block (Figure 2(b)) modeling the subse- quent heterogeneous node in the schema (Figure 2(a)). We provide detailed algorithm to construct SPSNs in Section E, along with a simple example without the block structures (Figure 4).
The key hyper- syper-parameter is the number of layers of the SPSN block, ny, We consider that a single SPSN layer comprises one sum layer and one product layer. The other hyper- parameters are the number of children of all sum units, ng. and product units, Ng. which common across all layers (n- = 2, n2 = 2, and Rp = 2 in Figure ((c)).
Hlype-parameete
3.1 TRACTABILITY
Tractability is the cornerstone of PCs. A PC tractable if it performs probabilistic inference exactly and efficiently (Choi et al., 2020; Vergari et al., 2021). In other words, the probabilistic queries are answered without approximation (or heuristics) and in time, which is polynomial in the number of edges of the computational graph. Various standard probabilistic queries (e.g., moments, marginal queries, and conditional queries) can be defined in terms of the following integral:
v(f) =
w(f) ((T))(T)((T))
(2)
where f: + R is a function that allow us to formulate probabilistic queries, and v is a reference measure on T (Section 2). The composite nature of T imposes rather complex structure on v. It contains measures specifically tailored for RFSs, which makes the integration different compared to the standard Lebesgue measure (see Section B and Section D.2 for details).
Structural constraints. If (2) admits an algebraically closed-form solution, then SPSNs are tractable. This is what we demonstrate in this section. To this end, both p and f have to satisfy certain restrictions on their structure, which we present in Definition 5 and Definition 6.
Definition 5. (Structural constraints on p). We consider the following constraints on G. Smooth- ness: children of any sum unit have the same scopes, i.e., each u E S satisfies Va, b ch(u): V. = 2b.. Decomposability; children of any product unit have pairwise disjoint scopes, i.e., each u E satisfies Va, b E ch(u): v/a O 1/6 Ø
The SPSNs inherit the standard structural constraints used in PCs (Shen et al., 2016; Vergari et al., 2021). The set unit does not violate these constraints since the cardinality distribution and the feature density are computational subgraphs given by the SPSN units (Definition 3).
Definition 6. (Structural constrains on f.) Let fTT =
FuueLf((e be a factorization of f. where (Wa)aEL are pairwise disjoint scopes that are unique among all the input units.
Note that the scopes of all input units, (Wu)set, form a multiset since there are usually repeating scopes among all u E I. These repetitions result from the presence of sum units in the computational graph, as they have children with identical scopes (Definition 5). The collection (Ww)eet, on the other hand, contains no repeating elements, i.e., L C I, are the input units with unique scope. We obtain this set if we follow only single child of each sum unit when traversing the computational graph from the root to the inputs (as in the induced tree (Zhao et al., 2016; Trapp et al., 2019)).
Definition 6 allows us to target an arbitrary part of the data graph, T, which is spanned from given data node, V E V. (Definition 1). That is, we can define T = T_ U T., where T, is composed of the subsets of T that are reachable from v and T_ is the complement. Consider f(T) = (T)),, where the indicator function 1 (T) == 1 T E A, for measurable subset A C T, or 1 A (T) = otherwise. Now, let A F.p x A,, where E_p, T-p is an evidence assignment (a specific
5

---

Published as a conference paper at ICLR 2024
realization) corresponding to T-v. and A. C To is measurable subset corresponding to T. Then, the integral (2) yields the marginal query P(E-v, Av). This query is useful if there is a (subset of) node(s) with missing values, e.g., a leaf node, L, which we demonstrate in Section 5.
Proposition 1. (Tractability of SPSNs). Let p(T) be an SPSN sutisfying Assumption 1 and Desini- tion 5, and let ((T) be a function satisfying Definition 6. Then, the integral (2) is tractable and can be computed recursively as follows:
O 1, Eocch(w) Wayeles HoEch(()) Te S S (tbbu))putteeeeee Pm
for u E B, for E S, for u P;
I
for u EI, where the measure vn (u(d))) instantiates itself either as the Lebesgue measure or the counting mea- sure, depending on the specific form of the scope Va-
Proof. See Section D.2 in the supplementary material.
Proposition starts the integration by finding a closed-form solution for the integrals w.r.t. the input units, I. The results, Lu. are then recursively propagated in the feed-forward pass through the computational graph and are simply aggregated based on the rules characteristic to the sum, product, and set unit. Specifically, the integration passes through the set unit similarly the sum and product units. It computes an algebraically closed-fone form solution consisting of a weighted sum of products of integrals passed from the feature density (i.e., tractable sub-SPSN). Note that the integration reduces to the one used in the conventional SPNs there are no set units, see Proposition 5.
The infinite sum in the aggregation rule of the set unit (u B) in Proposition 1 might give an impression that SPSNs are intractable. However, recall from Assumption I that p(k) = 0 for sufficiently large & (consider, e.g., the Poisson distribution), and the infinite sum therefore becomes finite one (Remark 1). This is commonly the case in practice since p(k) is learned from collections of graphs with finite number of edges.
3.2 EXCHANGEBILITY
The study of probabilistic symmetries has attracted increased attention in the neural network liter- ature (Bloem-Reddy & Teh, 2020). On the other hand, the exchangeability of PCs has been inves- tigated marginally. The relational SPNs (Nath & Domingos, 2015) and the exchangeability aware SPNs (Lüddtke et al., 2022) are, to the best of our knowledge, the only examples of PCs introducing exchangeable computational units. However, exchangeability: Under what constraints is it possible to permute the arguments of a PC?
of them answers the fundamental question about
To define the notion of finite fill exchangeability of a probability density (see Section C for details), we use the finite symmetric group of set of n elements, Sn. This is a set of all n! permutations of [n] := (1.....n). .n), and, any of its members, x Sn,, exchanges the elements of an n-dimensional vector, x = (21...., ), in the following way: X = (I.(I)...., In(n)).
Definition 7. (Full exchangeability. The probability density p is fully exchangeable iff p(x) p( x) for all π E Sn We say that x is fully exchangeable if (x) is.
The full exchangeability (complete probabilistic symmetry) sometimes unrealistic in practical applications. The relaxed notion of finite partial exchangeability (de Finetti, 1937; Aldous, 1981; Diaconis & Freedman, 1984; Diaconis, 1988a;b) admits the existence of several different and related groups where full exchangeability applies within each group but not across the groups.
To describe the partial exchangeability, we rely on the product of m finite symmetric groups, Sn... = Sn, X .... S.... where nm = (nI, Amm) ). Any member, E S : permutes each of m elements in the collection, X == (xi...., x,),, individually as follows: π X = (TI Xx,..., Fm xm.).
Definition (Partial exchangeabilityy. The probability density p is partially exchangeable iff P(X)= = p(π X) for all π E Spm. We say that X is partially exchangeable if p(X) is.
Definition 8 allows us to study the exchangeability of probabilistic models in situations where they follow structural limitations that prevent the direct use of full exchangeability. SPSNs respecting

---

Published as a conference paper at ICLR 2024
Assumption 1 and Definition 5 have a constrained computational graph, which imposes limitations on their input-output behavior. Therefore, it does not apply that exchanging any two nodes in the data graph. T, has no impact on the value of p(T). We present Proposition 3 to describe under what restrictions the data nodes can be exchanged, how the permutations propagate through the computa- tional graph, and in what sense the exchangeability affects the different types of computational units.
Proposition 2. (Structurally constrained permutaaions.. Consider PC satisfying Definition 5. Then, qa E Q is a permutation operator which targets a specific computational unit, a E V, and propagates through the computational graph G --rrom the root to the inputs- in the following way:
for a + u and u 55 Moreh (u) Polav - v/)) (M) Po(Ve), for F and E P, PT th).
Exeehits) Wn,ePolaa Vu),
Pulqa Vu))
=
for a = u and u $ P},
where ch,, (u) and (u) are children of that are and are not the ancestors of a, respectively. Con- sequently, Q is group that results from the structural restrictions on the computational graph G.
Proof. See Section C.I.
Proposition 2 shows that 4a propagates through each sum unit to all its children, passes through each product unit only to those children that are the ancestors of a, and instantiates itself to the permutation, π, when reaching the targeted unit, a. This recursive mechanism allows us to formulate the exchangeability of SPSNs in Proposition 3.
Proposition 3. (Exchangeability of SPSNs). Let p(T) be an SPSN satisfying Assumption and Definition 5. Let lE E I be a subset of input units that are exchangeable in the sense of Desinition 7 or Definition 8, Then, the SPSN is partially exchangeable, p(ta .T)= = )(T),, for each E {lE, B}.
Proof. See Section C.2.
Proposition 3 states that changing the order of the arguments corresponding to exchangeable input units and set units does not influence the resulting value of p(T), i.e., the SPSNs invariant under the reordering of the elements in the scopes of these units. There must be at least one input unit that is multivariate and exchangeable in the sense of Definition 7 or Definition ity w.r.t. le: otherwise, SPSNs are exchangeable only w.r.t. B. This implies that T can always be exchanged w.r.t. the homogeneous nodes and only the leaf nodes admitting exchangeability. The heterogeneous nodes are not exchangeable. Full exchangeability is possible only when there are no product units, and the input units are fully exchangeable. The presence of product units thus al- ways imposes partial exchangeability. The structural constraints of SPSNs impose specific type of probabilistic symmetry. In other words, an SPSN can be seen as a probabilistic symmetry structure invariant under the action of a group, Q, resulting from the connections in the computational graph.
satisfy exchangebil-
4 RELATED WORK
Non-probabillittc models (NPMs). Graph neural networks (GNNs) have become powerful ap- proach for non-probabilistic representation learning on graphs. Variants of GNNs range from their original formulation (Gori et al., 2005; Scarselli et al., 2008) to GCN (Kipf & Welling, 2017), MPNN (Gilmer et al., 2017), GAT (Veličković et al., 2018) and GraphSAGE (Hamilton et al., 2017), among others. They encode undirected cyelic graphs into low-dimensional representation by aggregating and sharing features from neighboring nodes. However, they waste computational resources by re- peatedly visiting the nodes when applied to structurally constrained graphs. This led to GNNs for directed acyclic graphs (Thost & Chen, 2021), and for trees, which traverse the graph bottom-up (or up-bottom) and update the nodes only via their children. Examples of tree-GNNs are RNN (Socher et al., 201 I; Shuai et al., 2016). Tree-LSTM (Tai et al., 2015) and TreeNet (Cheng et al., 2018).
Intractable probabilistic models (IPMs). Extending deep generative models from unstructured to graph-structured data has recently gained significant attention. Variational autoencoders learn probability distribution over graphs, P(G), by training an encoder and a decoder to map between space of graphs and continuous latent space (Kipf & Welling, 2016; Simonovsky & Komodakis, 2018; Grover et al., 2019). Generative adversarial networks learn PG) by training (i) generator to map from latent space space of graphs and (ii) discriminator distinguish whether the graphs
7

---

Published as a conference paper at ICLR 2024
Table 1: Graph classification. The test accuracy (higher is better) for the MLP. GRU, LSTM. HMIL, and SPSN networks. is displayed for best model in the grid search. which was selected based on the validation accuracy. The results are averaged over 5 runs with different initial conditions. The accuracy is shown with its standard deviation. The average rank is computed as the standard competition ("1224") ranking (Demšar, 2006) on each datasct (lower is better).
dataset
GRU
LSTM
HMIL
SPSN
chess
0.41
0.15
0.34::0.04
0.39=0.02
0.39::0.03
citeseer
0.69.10.02
0.74:10.11
0.74.10.02
0.75 0.01
0.75
0.75=:0.03
0.86::0.1
0,84100011
0.85=0.00
0.86:1-0001
genes
0.99::0.01
1.0010.01
0,98100.01
1.00:0.01
0.95:100.01
hepatitis
0.86:20.02
0.88:10.01
0.87100.33
0.88=0.02
0.88
mutagenesis
0.84=00.22
0.83+:0.02
0.82++0.04
0.83=0.00
0.84-10.02
uwcac
0.84=00022
0.87==0.03
0.85++0.02
0.86=0.03
0,84+40.02
webkp
0.77:10.02
0.82
0.811:0.22
0.82 0.01
0.81:10002
rank
3.62
1.62
3.88
1.62
2.38
synthetic real (De Cao & Kipf, 2018; Bojchevski et al., 2018). Flow models the change of variables formula to transform a base distribution on latent space to a distribution on space of graphs. p(G), via an invertible mapping (Liu al., 2019; Luo al., 2021). I). Autoregressive models learn PG) by using the chain rule of probability to decompose the graph, G, into a sequence of subgraphs. constructing G node by node (You et al., 2018; Liao et al., 2019). Diffusion models learn p(G) by noising and denoising trajectories of graphs based on forward and backward diffusion processes, respectively (Jo et al.. 2022; Huang al., 2022; Vignac et al., 2022). NMPs are used in all these generative models, so computing probabilistic (e.g., marginal) queries is intractable.
Tractable probabilistic models (TPMs). There has yet to be a substantial interest in probabilistic models facilitating tractable inference for graph-structured data. Graph-structured SPNs (Zheng et al., 2018) decompose cyclic graphs into subgraphs that are isomorphic to pre-specified set of possibly cyclic templates, designing the conventional SPN for each of them. The sum unit and layer of the product units aggregate the roots of these SPNs. Graph-induced SPNs (Errica & Niepert, 2023) also decompose cyclic graphs, constructing a collection of trees based on a user- specified neighborhood. The SPNs are not designed for the trees but only for the feature vectors in the nodes. The aggregation is performed by conditioning the sum units at upper levels of the tree by the posterior probabilliiess at the lower levels. Relational SPNs (RSPNs) (Nath & Domingos, 2015) are TPMs for relational data (a particular form of cyclic graphs). Our set unit is similar to the exchangeable distribution template of the RSPNs. The key difference that SPSNs model cardinality. The RSPNs do not provide this feature, making them unable to generate new graphs. The mixture densities over finite random sets are most related to SPSNs (Phung & Vo, 2014; Tran et al., 2016; Vo et al., 2018). They can be seen as the sum unit with children given by the set units. These shallow models are designed only for sets. SPSNs generalize them to deep models for hierarchies of sets, achieving higher expressivity by stacking the computational units. SPNs are also used to introduce correlations into graph variational autoencoders (Xia et al., 2023), which intractable models. Logical circuits can be used to induce probability distributions over discrete objects via knowledge compilation (Chavira & Darwiche, 2008; Ahmed et al., 2022). However, they assume fixed-size inputs, making them applicable only to fixed-size graphs, such grids.
5 EXPERIMENTS
We illustrate the performance and properties of the algebraically tractable SPSN models compared to various intractable, NN-based models. In this context, we would like to investigate their perfor- mance in the discriminative learning regime and their robustness to missing values. We provide the implementation of SPSNs at https: / / thub. com/ a center SumP roductSet. j1.
Models. To establish the baseline with the intractable models, we choose variants of recurrent NNs (RNNs) for tree-structured data. Though these models are typically used in the NLP domain (Section 1), they are, too, applicable to the free-structured data in Definition 1. These tree-RNNs differ in the type of cell. We consider the simple multi-layer perceptron (MLP) cell, the gated recurrent unit (GRU) cell (Zhou et al., 2016), and the long-short term memory (LSTM) cell (Tai et al., 2015). The key assumption of these models is that they consider each leaf node to have the same dimension. This requirement does not hold in Definition 1, Therefore, for all these NN-based models, we add
8

---

Published as a conference paper at ICLR 2024
citeseer
0.8
0.8
0.8
0.88
0.6
GRU
MLP
0.6
GRE
0.6
GREE
0.6
MLP
GRU
0.4
LSIM
0.4
0.4
0.4
LSTM
HMI.
HM
HM-T
HMIL
0.2
SPSN
0.2
SPSN
0.2
SPSN
0.2
SPSN
0. 0.20.40.60
0.20.4 0.8
1
0.2.0..... 2.04 0.6 0.8 1
0 0.200. 0.6 0.5
fraction missing values ()
fraction missing Valuess (+)
fraction missing valuess (-)
fraction missing values (+)
bepatits
matageneuis
wehlip
0.8
0.8
0.8
0.8
szcurayy
GRU
GRU
GRU
0.6
0.4
LSIM
0.4
LSIM
0.4
LSTM
0.4
HMIL
HMIL
HMIL.
HMII.
0.2
SPSN
0.2
SPSN
0.2
SPSN
0.2
SPSN
0,20.40.60.8
0.20.40.00.3
0.20..4.6022
0.200400 0.6 fraction missing values
fraction missing valuee
fraction missing values (+)
fraction massing values (-)
Figure 3: Missing values. The test accuracy (higher is better) versus the fraction of missing values for the MLP, GRU, LSTM, HMIL, and SPSN networks. It is displayed for the best model, which was selected based on the validation accuracy. The results are averaged over five runs with different initial conditions.
single dense layer with the linear activation function in front of each leaf node, v E L, to make the input dimension the same. As another competitor, we the hierarchical multiple-instanee learning (HMIL) network (Pevný & Somol, 2016), which is also tailored for the tree-structured data.
Settings. We convert eight publicly available datasets from the CTU relational repository (Motl & Schulte, 2015) into the ISON format (Pezoa et al., 2016). The dictionary nodes, list nodes, and atomic nodes of the JSON format directly correspond to the heterogeneous nodes, homogeneous nodes, and leaf nodes of the tree-structured data, respectively (Definition 1, Figure 2). We present the rest of the settings in Section F, including the schemata of the datasets. All models and experiments are implemented in Julia, using COONGrinder: j1 and Mill. ji (Mandlik et al., 2022).
Graph classification. Table shows the test accuracy of classifying the tree-structured graphs. The HMIL and GRU networks deliver the best performance, while the SPSN falls slightly behind. If we look closely at the individual lines, we can see that the SPSN is often very similar to (or the same as) the HMIL and GRU networks. We consider these results unexpectedly good, given that the (NN- based) MLP, GRU, LSTM, and HMIL architectures are denser than the sparse SPSN architecture.
Missing values. We consider an experiment where we select the best model in the grid search based on the validation data (as in Table 1) and evaluate its accuracy on the test data containing a fraction of randomly-placed missing values. Figure 3 demonstrates that the SPSN either outperforms or is similar to the NNs. Most notably, for cora and webkp, the SPSN keeps its classification performance longer compared to the NN models, showing increased robustness to missing values. This experiment applies Proposition to perform marginal inference on the leaf nodes, v E L,, that contain missing values. The marginalization is efficient, taking only one pass through the network. Note that the randomness in placing the missing values can lead to situations where all children of the heterogeneous node are missing, allowing us to marginalize the whole heterogeneous node.
CONCLUSION
We have leveraged the theory of finite random sets develop a new class of deep learning models- sum-product--st networks (SPSNs)-that represent probability density over tree-structured graphs. The key advantage of SPSNs is their tractability, which enables exact and efficient inference over specific parts of the data graph. To achieve tractability. SPSNs have to adhere to the structural con- straints that are commonly found in other PCs. Consequently, the computational graph of SPSNs has much less connections compared to the computational graph of highly interconnected and non- linear NNs. Notwithstanding this, SPSNs perform comparably to the NNs in the graph classification task, sacrificing only small amount of performance to retain their tractable properties. Our findings reveal that the tractable and simple inference of SPSNs has also enabled us to achieve results that are comparable to the NNs regarding the robustness missing values. In future work, plan to hance the connectivity within the SPSN block by vectorizing the computational units. We anticipate that this modification will close the small performance gap to the NN models.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors acknowledge the support of the GAČR grant no. GA22-32620S and the OP VVV funded project C22.2.1111/0.000001111111///0000 "Research Center for Informatics".
REFERENCES
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Seman- tic probabilistic layers for neuro-symbolic learning. Advances in Neural Information Processing Systems, 35:29944-29959, 2022.
Oren Ben- Kiki, Clark Evans, and Brian Ingerson. YAML ain't 't markup language (YAMLTM) version 1.1. Working Draft 2008, 5:11, 2009.
Anna Maria Bianucci, Alessio Micheli, Alessandro Sperduti, and Antonina Starita. Application of cascade correlation networks for structures chemistry. Applied Intelligence, 12:1 12:117-147, 2000.
Benjamin Sloem-RRedy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. The Journal of Machine Learning Research, 21(1):3535-355 3595, 2020.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. NetGAN: Generating graphs via random walks. In International conference machine learning, pp. 610- 619. PMLR, 2018.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geo- metric deep learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4): 18 18-42, 2017.
Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Arti- ficial Inielligence, 172(6-7)7722-799 2008.
Zhou Cheng, Chun Yuan, Jiancheng Li, and Haiqin Yang. TreeNet: Learning sentence representa- tions with unconstrained tree structure. In IJCAI, pp. 4005-4011, 2018.
Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: unifying framework for tractable probabilistic models. UCLA. URL: http://starai. cs. ucla. eduipapers/ProbCire0 pdf. 2020.
Daryl J Daley, David Vere-Jones, et al. An introduction to the theory of point processes: volume I: elementary theory and methods. Springer, 2003.
Nicola De Cao and Thomas Kipf. MoIGAN: An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805.1197. 2018.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debmath, Alan J Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
Janez Demšar. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research, 7:1-30, 2006.
Federico Errica and Mathias Niepert. Tractable probabilistic graph representation learning with graph-induced sum-product networks. arXiv preprint arXiv:2305. 10544, 2023.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Nenworks, 2005., volume 2, pp. 729-734. IEFE, 2005.
10

---

Published as a conference paper at ICLR 2024
Geoffrey Grimmett and David Stirzaker. Probability and random processes. Oxford university press, 2001.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pp. 2434-2444, PMLR, 2019.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, 2017.
Han Huang, Leilei Sun, Bowen Du, Yanjie Fu, and Weifeng Lvv. GraphGIDP: Generative diffusion processes for permutation invariant graph generation. arXiv preprint arXiv:2212.01184. 2022.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, pp. 10362-10383. PMLR, 2022.
James Kahn, Iaa Tsaklidis, Oskar Taubert, Lea Reuter, Giulio Dujany, Tobias Boeckh, Arthur Thaller, Pablo Goldenzweig, Florian Bernlochner, Achim Streit, et al. Learning tree structures from leaves for particle decay reconstruction. Machine Learning: Science and Technology, 3(3):
035012, 2022.
Thomas N Kipf and Max Welling. 1rXiv:161.007308, 2016.
Variational
graph auto-encoders.
arXiv preprint
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations (ICLR), 2017.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William I. Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 4255-4265, 2019.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 13578-13588, 2019.
Stefan Lüdtke, Christian Bartelt, and Heiner Stuckenschmidt. Outlying aspect mining via sum- product networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 27-38. Springer, 2023.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. GraphDF: A discrete flow model for molecular graph generation. In International Conference on Machine Learning, pp. 7192-7203. PMLR, 2021.
Stefan Lüdtke, Christian Bartelt, and Heiner Stuckenschmidt. Exchangeability-wwar sum- con-product networks. In Proceedings of the Thirty-First International Joint Conference on Artificial In- telligence, IJCAI-22, pp. 4864 International Joint Conferences on Artificial Intelligence Organization, 2022.
Jing Ma, Wei Gao, and Kam-Fai Wong. Rumor detection twitter with tree-structured recursive neural networks. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1980-1999 2018.
Ronald P Mahler and LOCKHEED MARTIN TACTICAL DEFENSE SYSTEMS-EAGAN
ST PAUL MN. Information-theorrticc information fusion. 2002.
Ronald PS Mahler. Detecting, tracking, and classifying group targets: A unified approach. In Signal Processing, Sensor Fusion, and Target Recognition X, volume 4380, pp. 217-228. Spie, 2001.
Ronald PS Mahler. Statistical multisource-mllitareee information fusion, volume 685. Artech
House Norwood, MA, USA, 2007.
Šimon Mandlík, Matěj Račinský, Viliam Lisý, and Tomáš Pevný. Jsongrinder,i:: Automated dif- ferentiable neural architecture for embedding arbitrary JSON data. Journal of Machine Learning Research, 23(298):155, 2022.
11

---

Published as a conference paper at ICLR 2024
Jan Motl and Oliver Schulte. The CTU Prague relational learning repository. arXiv preprint arXiv:1511.03086 2015.
Aniruddh Nath and Pedro Domingos. Learning relational sum uum-product networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Hung Nguyen. An introduction random sets. Chapman and Hall/CRC, 2006.
Robert Peharz, Sebastian Tschiatschek, Franz Pernkoff and Pedro Domingos. On theoretical prop- erties of sum-product networks. In 18th International Conference Artificial Intelligence and Statistics, pp. 742-752. PMIR, 2015.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kersting, and Zoubin Ghahramani. Random sum-product networks: A simple and effec- tive approach to probabilistic deep learning. In Uncertainty in Artificial Intelligence, pp. 334-344. PMLR, 2020.
Tomáš Pevný and Petr Somol. Discriminative models for multi-instance problems with struc- ture. In Proceedings of the 2016 ACM Workshop on Artificial Intelligence and Security, pp. 83-91, 2016.
Felipe Pezoa, Juan L Reutter, Fernando Suarez, Martín Ugarte, and Domagoj Vrgoë. Foundations of JSON schema. In Proceedings of the 25th international conference on World Wide Web, pp- 263-273, 2016.
Dinh Phung and Ba-Ngu Vo. A random finite set model for data clustering. 17th International Conference Information Fusion (FUSION), pp. 1-8. IEEE, 2014.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689-690. IEEE, 2011.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-8)) 2008
Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of prob- abilistic models. Advances in Neural Information Processing Systems, 29, 2016.
Bing Shuai, Zhen Zuo, Bing Wang, and Gang Wang. DAG-recurrent neural networks for scene labeling. In Proceedings of the IEEE conference computer vision and puttern recognition, pp- 3620-3629, 2016.
Martin Simonovsky and Nikos Komodakis. Gra:
VAB: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Coaminn-IIAANA 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 27, pp. 412-422. Springer, 2018
Richard Socher, Cliff C Lin, Chris Manning, and Andrew Ng. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 28th international conference machine learning (ICML-11), pp. 129-136, 2011.
Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meet- ing of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1556-1566, 2015.
Joe Tekli, Nathalie Charbel, and Richard Chbeir. Building semantic trees from XML documents. Journal of Web Semantics, 37:1-24, 2016.
Veronika Thost and Jie Chen. Directed acyclic graph neural networks. In 9th International Confer- ence on Learning Representations (ICLR), 2021.
Nhat-Q Nhat-Quang Tran, Ba-Ngu Vo. Dinh Phung, and Ba- Ba-Tuong Vo. Clustering for point pattern data. In 2016 23rd International Conference Pattern Recognition (ICPR), pp. 3174-3179. IEEE, 2016.
12

---

Published as a conference paper at ICLR 2024
Martin Trapp. Robert Peharz, Hong Ge, Franz Pernkoff, and Zoubin Ghahramani. Bayesian learning of sum- sum-product networks. Advances in neural information processing systems, 32, 2019.
MNM Van Lieshout. Markov point processes and their applications. World Scientific, 2000.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Antonio Vergari, YooJung Choi. Robert Peharz, and Guy Van den Broeck. Probabilistic circuits: Representations, inference, learning and applications. In Tutorial at the The 34th AAAI Confer- ence on Artificial Intelligence, 2020.
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A composi- tional atlas of tractable circuit operations: From simple transformations to complex information- theoretic queries. arXiv preprint arXiv:2102.06137, 2021.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. DiGress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
Ba-Ngu Vo, Nhan Dam, Dinh Phung, Quang Tran, and Ba- Tuong Vo. Model- based learning for point pattern data. Pattern Recognition, 14:136-151, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2021.
Riting Xia, Yan Zhang, Chunxu Zhang, Xueyan Liu, and Bo Yang. Multi-head variational graph autoencoder constrained by sum-product networks. In Proceedings of the ACM Web Conference 2023, pp. 641-650, 2023.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generat- ing realistic graphs with deep auto-regressive models. In International conference machine learning, pp. 5708-5717. PMLR, 2018.
Han Zhao, Pascal Poupart, and Geoff Gordon. A unified approach for learning the parameters of sum-product networks. Proceedings of the 30th Advances Neural Information Processing Systems, pp. 433-441, 2016.
Kaiyu Zheng, Andrzej Pronobis, and Rajesh Rao. Learning graph-structure sum-product networks for probabilistic semantic maps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Yao Zhou, Cong Liu, and Yan Pan. Modelling sentence pairs with tree-structured attentive encoder. In Proceedings of COLING 2016, the 26th International Conference on Computational Linguis- tics: Technical Papers, pp. 2912-2922, 2016
13

---

Published as a conference paper at ICLR 2024
A PROBABILISTIC CIRCUITS
A probabilistic circuit (PC) is a deep learning model representing a joint probability density, p(x), over fixed-size, unstructured, random variable, x (21,.... Fnn E X' C IR.. The key feature of PC is that-under certain regularity assumptions-it permits exact and efficient inference scenarios. We define a PC by a parameterized computational graph, G, and scope function, v².
Definition 9. (Compulational graph). G : (V,E, 0) is parameterized, directed, acyclic graph, where V is a set of vertices, & is set of edges, and 0 E @ are parameters. V == P. contains three different subsets of computational units: sum units, S. product units, P. and input units, I. Let ch(u) and pa(u) denote the set of child and parent units of u E V, respectively. If pf/p))) = Ø, then is the root unit. If ch(u)
2, then is input unit. We consider that V contains only a single root unit, and each product unit has only a single parent. The parameters == (6s, 0t) are divided into (i) parameters of all sum units, 0g (ww,e)cEch(ol which contain non-negative and locally normalized weights (Peharz al., 2015), Wu.e 2 0, Eeech(u) Wa.e = 1; and (ii) parameters of all imput units, O2 which are specific a given family of densities, with possibly different density for each u E.
the set of units to the power set of x- outpuls subset of x E X for each u E V and is referred to as the scope function. If is the root unit, then tha = x. If u is a sum unit or a product unit, then Vy = Uoech(u)) Vc.
Definition 10. (Scope function). The mapping thu : F(x)
PCs are an instance of neural networks ( (Vergari et al., 2019; Peharz et al., 2020), where each compu- tational unit is probability density characterized by certain functionality. Input units are the input of a PC. For each u E I, they compute (user-specified) probability density, P.).). over a subset of x given by the scope, v'a. which can be univariate or multivariate (Peharz et al., 2015). Sum units are mixture densities that compute the weighted sum over its children, (-) = Σ Ecech(u) Wu,cPo('), where Wy.e (Definition 9) weights the connection between the sum unit and a child unit. Product units are factored densities that compute the product of its children, Pu (vba) = [Tgeh((w) Pe( es- tablishing an unweighted connection between u and and introducing the conditional independence among the scopes of its children, vic- It is commonly the case that (layers of) sum units interleave (layers of) product units. The computations then proceed recursively through & until reaching the root unit-the output of PC.
PCs are generally intractable. They instantiate themselves into specific circuits- and thus permit tractability of specific inference scenarios by imposing various constraints on 9, examples include smoothness, decomposability, structured decomposability, determinism, consistency (Chan & Dar- wiche, 2006; Poon & Domingos, 2011; 1; Shen et al., 2016). In this work, we use only the first two of these constraints, as summarized in Definition 5.
A PC satisfying Definition 5 can be seen as a polynomial composed of input units (Darwiche, 2003). This construction guarantees that any single-dimensional integral interchanges with a sum unit and impacts only single child of product unit (Peharz et al., 2015). The integration is then propagated down to the input units, where it can be computed under a closed-form solution (for a tractable form of u E D). The key practical consequence lies in that various inference tasks such as integrals of p(x) over (Za..... Z2,)) C x are tractable and can be computed in time which is linear in the circuit size (i.e., the cardinality of V). p(x) is guaranteed to be normalized if Definition holds and input units are from the exponential family (Barndorff-Nielsen,, 1978). PCs that fulfill Definition 5
are commonly referred to as sum cum-product networks.
B RANDOM FINITE SETS
Random Finite Sets. A random finite set (RFS), X x= (xi...., Xm), is a random variable taking values in F(X',, the hyperspace of all finite (closed) subsets of some underlying space, X. The randomness of this mathematical object originates from all the elements in the set, x; E X, and also from the cardinality of this set, = |X], i.e., the number of the elements is itself random. This is the key difference to the standard fixed-size vector, x = (I1..... Tm), where 2; 's are stochastic but m is deterministic. The example realizations of an RFS are X Ø (empty set), X = fx1) } (singleton), X = X2] (tuple), etc. They are points in the hyperspace, X E F(X', and each of them is finite subset of X. The elements of an RFS, X X are assumed distinet (non-
14

---

Published as a conference paper at ICLR 2024
repeated) and unordered. An RFS is then equivalent to simple point process (Van Lieshout, 2000; Daley et al., 2003; Nguyen, 2006; Mahler, 2007).
A more formal definition of RFS is as follows. Let Ω be sample space, ( be sigma algebra of events on Ω2 and P' be a probability measure on the measurable space (S2, (S2),, i... P(22) 1. Let X' be locally compact, Hausdorff, separable metric space (e.g., X' C ")", F(X) be the hyperspace of all finite subsets of X, o(F) be a sigma algebra of events on F(X), and be dominating (reference) measure on the measurable space (F(X),o(FF) which we specify later on. Now consider the probability space and the measure space (S2, (S2,, and (F(X), P), respectively. Then, an RFS is a measurable mapping"
X
To have the ability to build probabilistic models of the RFS (3), we need tools that characterize its statistical behavior. These tools include a probability distribution, a probability density, and suitable reference measure to perform the integration. The hyperspace F(X) does not inherit the standard Euclidean topology, but the Mathéron "hit-or-miss" topology (Mathéron, 1974), which implies that some of these tools are built differently compared to those designed purely for X. However, demonstrated in this section, can work with them in a way consistent with the conventional probabilistic calculus.
Probability distribution. The probability law of the RFS (3) is characterized by its probability distribution,
P(A) = P(X ((A) P(W E ( A)).
for any Borel-measurable subset A (F).
Reference measure. A measure λ on the measurable space (x))) is countably-additive func- tion A: (Xt) + [0, oo]. It generalizes the notions of length, area, and volume to the subsets of X, which typically involves physical dimensions expressed in the units of X. However, not all mea- sures have units, e.g., the probability measure is unitless. When working with an RFS, one cannot simply use a conventional measure on (X, (X)), but it is necessary to extend it to (F(X), (F)). We aim to show how to extend the Lebesgue measure on (X, (x)) to a measure (F(X), Let A(S) be the Lebesgue measure on (X, (X)), for any measuabee subset S E (X)) and let (S") be the extension of the Lebesgue measure to the Gartesian-produce measurable space (X", (2)"), ) for any subset S' E ((2'). Furthermore, consider a mapping X bizod - F(2) from vectors of elements to sets of elements given by X(xI..... xx)
where denotes disjoint union. The mapping X is measurable (Goodman et al., 1997; Van Lieshout, 2000), and, therefore, X (A) is a measurable subset of "2 for any subset A E (F). Consequently, the reference measure on the measurable space (F(A"), (FF) -hicch which is commonly adopted in the theory of finite point processes defined as follows:
m(A)= = Σ X'xx (A))xx))
(5)
ctil
where (A) n X E (X**) restricts (A) into ith Cartesian product of X, respecting the convention X := Ø. Consider that the unit of measurement in X' i, then the unit of measurement of X2 is t'. This is why (5) contains the constant whose unit of measurement is Without this constant, each term in (5) would have different units of measurement, and the infinite sum would be undefined. The measure (5) is therefore unitless.
Say that the units of p(x1) are em cm and the units of p(x1, X2) are cm 2, then it holds that p(x1) > X2), see (Vo et al., 2018) for illustrative example. c thus prevents the incompatibility between the probabilities of two sets with different cardinalities.
Integral. The integral of unitless function f F(X)) R over subset A E (FF) with respect to the measure 1 is (Geyer, 1999; Mahler, 2007)
S [(x))((x))=
- ==0 chil (X-)(A)
dxx)).
(6)
Note the difference to the standard random variable X Ω + X' defined directly the measure space (X)) n)), where X is typically equipped with the standard Fuclidean topology.
15

---

Published as a conference paper at ICLR 2024
Remark 1. (Tractable integration.) The analytical tractability of (6) depends on whether the in- tegral of f(x x:}) w.Et. X allows us to find a closed-form solution and whether the infinite sum becomes a finite one. These requirements satisfied by designing based on a suitable family of functions and ensuring that _((xi,...,, xx)) = ffror sufficiently large (Goodman et al., 1997).
Probability density. The probability density function is the central tool in probabilistic modeling. is obtained from the Radon-Nikodýmn theorem (Billingsley, 1995). Its definition states that for two o-finite measures μl and #2 on the same measurable space (F(Z), there exists an almost everywhere unique function f F(X)) [0, oo) such that [2(AA) = ( (dX) if and only if μ12 << [4,, i.e., l12 is absolutely continuous w.r.t. Mi, or, in other words, nn (A) 0 implies diz is then referred to the density (A) 0 for any subset A (FF). The function f 2/4
function the Radon-Nikodým derivative of μ22 w.r.t. fa, This allows define the probability density function of an RFS as the Radon-Nikodým derivative of the probability measure (4) w.r.t. the reference measure (5),
p(X) = dP
du (X),
(7)
establishing the relation between the two measures as follows: P(A) = JAp(X))uddX The probability density function (7) has no units of measurement since the probability distribution (4) is unitless and the reference measure (5) is also unitless. This contrasts the standard probability density function defined on X, which gives probabilities per unit of X.
Exchangeability of RFSs. In point process theory (Daley et al., 2003), the probability density of an RFS (finite point process) is often constructed based on an mth-order, non-probabilistic measure, defined on the measurable space (X' (XTT), as follows:
Jm (AI,..., Am) =p(m) Σ
Aim.)
for any A; E (At). Here, p(m) is the cardinality distribution, which determines the total number of elements in the RES; Pn, is the joint distribution (X describing the positions of the elements in the RFS conditionally on m; Epmm denotes the summation over all m!! possible permutations of ; The measure (8) is exchangeable (permutation invariant), i.e., it gives the same value to all permutations of - Am- Following this prescription in its full generality would be computationally very expensive, as it requires m! evaluations of Pm- Fortunately, we assume that the elements of the RFS follow no specific order, and that we can make a symmetric version of Pm as follows: p (-) ml Epem (-). which is simply an equally weighted mixture over all possible permutations. Consequently, after substituting for Epem Pm in (8), we obtain fully exchangeable-yet computationally more paaveeiientJJnnsssy measure,
Jm (AI...... Am) p(m)m! tn (Ai...,, Am).
(9)
If (9) is absolutely continuous w.r.t. the reference measure An, then there exists the Janossy density,
Imm (x....., xm) ppm) (x1,..., Xm))
(10)
Note that (9) and (10) are not probability measure and a probability density, respec- tively. Indeed, it holds that Jm (X = Jm (X1,...,
(dxi..... (x,)) * 1. How- ever, they are favored for their reduced combinatorial nature and easy interpretability, i.e., mi Jm Xm ) (dx), the m distinct infinitesimal regions. To ensure that (10) is the probability density (7) of an RFS, X X-which is taken w.r.t. the reference measure i5) has to hold that
I
dxm) is the probability of finding exactly one element in each of
p((x xm,) = cm Jm (X]....... X.m)
(11)
Independent and identically distributed clusters. The feature (joint) density, pm in (10) allows us to model the dependencies among the elements of the RFS, X. In certain applications, it is more suitable (or simplifying) to assume that the elements, X1 X1...., Xm, are independent and identically sym distributed (i...d). The feature density then reads pm (x1,..., Xm) == II p(x,). where p is
a probability density on X indexed by the same parameters for all i E (1....,m) Note that the assumption of independent elements, but, more importantly, the assumption of identically distributed
16

---

Published as a conference paper at ICLR 2024
elements (the same parameters for all i {1...., m)), ensures the symmetry of the feature density under all permutations of the elements. The density (11) then becomes
12
p((xI,...,, x xm)) = p(()ml II [(x)).
(12)
which is commonly referred to the i..dd cluster model. In the special case, where the cardinality distribution p(m) is the Poisson distribution, (12) represents the Poisson point process (Grimmett & Stirzaker, 2001).
Remark 2. (Independence assumption.) Assumption I(d) is simple way to ensure the exchange- ability of the set unit. However, it comes at the cost of not capturing the correlations among (Tw:) ym Despite this fact, we show in Section 5 that the SPSNs deliver solid performance and are very competitive to the NNs. To relax Assumption I(d), one would need to impose the exchange- ability in a different way. For example, a fully general approach would be to use the mixture over m! permutations of (Tw: ) as indicated by (8). Since this would be computationally intensive, is preferable to introduce only approximate exchangeability, which means that one would need to reduce the number of permutations. Albeit such an approach can limit the exchangeability of the set unit to some degree, does not sacrifice the tractability as long as the components of this mixture form of the feature density are tractable sub-SPSNs.
C EXCHANGEABILITY
Probabilistic symmetries. Probabilistic symmetry the most fundamental one of which is changeability- is a long-standing subject in the probability literature (Zabell, 2005). The notion of probabilistic symmetry is useful for constructing probabilistie models of exchangeable data struc- tures, including graphs, partitions, and arrays (Orbanz & Roy, 2014). Infinite exchangeability is re- lated to the conditionally i.i.d. sequences of random variables via the de Finetti's 's theorem (de Finetti, 1929; 1937). It states that an infinite sequence of random variables 1 T2, ................................ is exchangeable if and only if (iff) there exists a measure À on θ such that p(.,,.... Fnn) I Po Po(x;) (x,))((0)) Conse- quently, conditionally i.i.d. sequences of random variables are exchangeable. The converse of this assertion true in the infinite case, n - oc. Finite exchangeability does not satisfy the converse as- sertion. It defines that for extendable finite sequence", I,,..., .n. the de Finetti's representation holds only approximately, i.e., there is bounded error between the finite and infinite representations (Diaconis, 1977; Diaconis & Freedman, 1980). We are not interested in finite exchangeability from the perspective of its asymptotic properties. However, we use it to investigate whether a probabilistic model is structurally invariant under the action of compact group operating on its input, which is considered non- extendaee......
Exchangeability PCs. As discussed in Section 3.2, the study (and application) of exchangeability in (to) PCs has attracted limited attention. The exchangeability-wwall SPNs (Lüdtke et al., 2022) use the mixtures of exchangeable variable models (Niepert & Domingos, 2014; Niepert & Van den Broeck, 2014) as the input units, proposing a structure-learning algorithm that learns the structure by statistically testing the exchangeabilityy within groups of random variables. The relational SPNs (Nath & Domingos, 2015) introduce the exchangeable distribution templates, which are similar in certain aspects to SPSNs. However, though these approaches adopt exchangeable components, none of them investigates how the exchangeability propagates through PC. Therefore, we characterize the exchangeability of PCs in Proposition 4.
Proposition 4. (Exchangeability of PCs). Let p(x) be a PC satisfying Definition 5 and let lE I be subset of input units that are exchangeable in the sense of Definition 7 or Definition 8. Then, the PC partially exchangeable, p(g, x) = p(x), for each a E lE.
Proof. The result follows from the recursive application of Proposition 2.
of Proposition 4 says that PCs satisfying Definition 5 preserve the exchangeability of their input units. holds only when there is at least one input unit that is multivariate and exchangeable in the sense
This means that the sequence Ti Tn is statistical properties.
part of the longer sequence, Z1, Ime with the
17

---

Published as a conference paper at ICLR 2024
of Definition 7 Definition 8. Note that the ordering of the scopes (blocks) in the product units remains fixed in the computational graph, i.., the scopes representing the children of the product units not exchangeable (only the variables in them).
An alternative way to prove Proposition 4 would be to convert a PC to its mixture representation (Zhao et al., 2016; Trapp et al., 2019). This converted model is mixture of products of the in- put units, for which the partial exchangeability can be proven in a way similar to the mixtures of exchangeable variable models (Niepert & Domingos, 2014; Niepert & Van den Broeck, 2014).
C.I. PROOF OF PROPOSITION
Sum units. The exchangeability of the sum unit follows from the smoothness assumption (Defini- tion 5). The fact that the scope of all children of any sum unit identical ensures that any permuta- tion (Definition 8), E Sm... propagates through the sum unit, pT th.) = Leech(u) Wo,ePe(TT ala), u E In other words, the probability density of the sum unit is partially (or fully) exchange- able, Pa (T ...)) Pa (Va.), if and only if the probability densities of all its children are partially (or fully) exchangeable, (TT (bw) = (.(t.), for all e E ch(u). If we replace æ by la the operator targeting& specific computational unit, come to the same conclusion.
Product units. The exchangeability of the product unit is based on the decomposability assumption (Definition 5). The consequence of that the scopes of all children of any product unit pairwise disjoint is that no matter the type of exchangeability of the child units, the product unit is always only partially exchangeable under the partition of the scopes of its children, Pu( r/w)) Pu( Per...., Am Von.) = [ooeeh(t)) Pe Vo),, for all π E Sn... and u E P. Therefore, we can say that the product unit, (TT vhw)) = Pa (M.)), preserves the exchangeability of its children.
The product group Sn... can be designed such that some of its elements can an identity group, Sn, = ln, In this case, there exists an identity operator, ei which does not permute the entries of x = (I....., TT,,) i.c, we have e; X = (II,.... In,) Consequently, π E Sn... permutes only some of m elements in the collection, X == (X1..... X.n). e.g., follows: X2...., Tm Xmm This allows us to target the permutations only to certain children the product unit Pm (T (b.) [weeh((w) (o ( [leech(u)) Pe(())), where ch(u) are the children targeted with permutations, and ch(u) are the children that are supposed to stay intact. If we consider replacing π by la. then this principle reveals how to propagate qa only to those children of the product unit that the ancestors of a. For example, can have: qu the (4vz -ee Euz Vo ..... 9um. Ven.) ).
X (mı X1, e2
Input units. The input units are user-specified probability densities, Pu (t)), for each u E The exchangeability of any input unit thus depends the choice of its density, which can be fully exchangeable (Definition 7), (v.)) = Pu( v.). or partially exchangeable (Definition 8), (u() Pu( vh)) This also implies that Ja if u. The leaf units terminate the propagation through the computational graph.
C.2 PROOF OF PROPOSITION 3
The result follows from the recursive application of Proposition and the fact that the set unit fully exchangeable by design (Section B). That is, for any homogeneous node, T, = (Tw....., ... I Tw.n holds that ( T,)) (T.) where u E O, u E B, and π E Sm.
D TRACTABILITY
The primary purpose of training (learning the parameters of) probabilistic models is to prepare them to answer intricate iiformation-thoorttii queries (questions) about events influenced by un- certainty (e.g., computing the probability of some quantities of interest, expectation, entropy). This procedure-referred to as probabilistic inference- requires calculating integrals of, or w.r.t, the joint probability density representing the model. Many recent probabilistic models deployed in machine learning and artificial intelligence rely on neural networks. The integrals in these mod- els do not admit closed-form solution, and the inference procedure is, therefore, intractable. To answer even the basic queries with these intractable probabilistic models, we are forced to resort to numerical approximations. The inference procedure is then computationally less efficient, more
18

---

Published as a conference paper at ICLR 2024
complex, and brings more uncertainty into the answers. Tractable probabilistic models, the other hand, provide a closed-fore solution to the integrals involved in the inference procedure and thus answer queries faithfully to the joint probability density without relying on approximations or heuristics. The inference procedure is then less complicated and computationally more efficient.
Tractability of PCs. PCs have become canonical part of tractable probabilistic modeling. They can answer a range of probabilistic queries exactly, i.e., without involving any approximation, and efficiently, i.e., in time which is polynomial in the number of edges of their computational graph. The range of admissible probabilistic queries varies depending on the types of structural constraints satisfied by the computational graph (Choi al., 2020).
We recall only some standard probabilistic queries that are feasible under the usual structural con- straints of Definition and can collectively be expressed in terms of the following integral:
X()= = / ((x)p(x)((xx).
(13)
We refer the reader to (Choi et al., 2020; Vergari et al., 2021) for more complex and compositional probabilistic queries.
Even when a PC, p(x), satisfies Definition 5, it does not directly mean that (13) admits closed-form solution. For this to be the case, the function f(x) has to satisfy certain properties.
Definition 11. (Tractable function for PCs.) Let f X - R be a measurable function which factorizes as f(x) == II [u())), where L C is the subset of imput units with unique and presumably multivariate scopes such that UWEL Vu Under this factorization, it follows from the properties of the scope function (Definition 10) that fu().) [lleech(a) fol()) for each P.
To show how to define various probabilistic queries in terms of the integral (13), we provide exam- ples of S. If f(x) = (x),, where 1 is the indicator function, and A = A1 x ... X Am then (13) yields P(A), the probability of A. Given == e1 X 22 X ... x Am-1 x Am. where e, are evidence assignments, A, measurable subsets of X, and
[L]. obtain the marginal query e2...,,, Am,) which can easily be used to build a conditional query of interest. The full evidence query is obtained for A
X Cm- To compute the first-order moment of any u E L, we define fu(t(v) == th and fa(va) = for E L/(n).
Proposition (Tractability of PCs). Let p(x) be a PC satisfying Definition 5 and let f(x) be a function satisfying Definition 11. Then, the integral (13) is tractable and can be computed recur- sively as follows:
Encon(n)) Wu,cees IlTcchiw) Ter S Su( (v Da (dvb),, (nnss..,,
for E S, for u E P,
for E
where the measure X (d))))) defined on the space V.. which corresponds to the scope tha and instantiates itself for all u. E V into either the Lebesgue measure the counting measure.
Proof. See Section D.1.
Proposition 5 states that, to compute the integral (13), we have to first compute the resulting values, T., of the integrals for each input unit, и E Then, T, is recursively propagated in the feed-forward manner (from the inputs to the root) throughout the computational graph and updated by the sum and product units.
D.1 PROOF OF PROPOSITION 5
We aim to demonstrate that the integral (13) is tractable. We show this in a recursive manner, considering how the integral propagates through each computational unit of p(x).
Before we start, let us remind Definition 11, which shows that f(x) = l (a(r).. Consid- ering Definition satisfied; then. based on Definition 10, the partial factorization fx((2)) = IeeL, fe(1/) can be extracted from f(x) for any u E (S, P). Here, L, C L contains only the input
19

---

Published as a conference paper at ICLR 2024
units that are reachable from and have a unique scope. The partial factorization, fu(Vu), leads to the definition of the following intermediate integral:
Xu(fu)=
(14)
which acts on a given computational unit u. In (14), (u()) ) is the probability density of u, and X is the reference measure on the measurable space (4 (Vv)), We will see that the proof consists of seeking an algebraic closure (recursion) for the functional form of the integral (14).
Input units. The existence of a closed-form solution of the integral (14) for E I is ensured if (1(
selected from a family of tractable probability densities (e.g.. the exponential family (Barndorff- Nielsen, 1978)) and (th.) is an algebraically simple function that does not prevent the solution to be found. The solution, therefore, depends purely on our choice. We use la to denote a concrete value of the integral.
Sum units. Consider that the smoothness assumption (Definition 5) is satisfied. Then, after substi- tuting the probability density of the sum unit for (v))) into (14), and exchanging the integration and summation utilizing the Fubini's theorem (Weir, 1973), we obtain
I (u(Vn)Da(V)))
E wa,e f FalWh)palsssssaada.
cEch(u)
where S. The smoothness assumption (Definition 5) states that the children of the sum unit have an identical scope. implies that the integration affects each child of the sum unit in the same way. Consequently, the integral w.r.t. Ps. can be solved if the integrals w.r.t. Pe can be solved for all è E ch(u). In other words, the sum unit is tractable if all its children (i.e., other sub-PCs) are tractable. The tractability of the sum unit thus propagates from its children. We can see that the functional form of the l.h.s. integral is the same as the functional form of the r.h.s. integrals representing the children of the sum unit. Therefore, we can replace these functional prescriptions with concrete realizations I, (l.h.s.) and Ta (r.h.s.). The sum unit then propagates already realized values of these integrals and multiplies them by the weights.
Product units. Assume that the decomposability assumption (Definition 5) holds. Then, af- ter substituting the probability density of the product unit for Pu (v)) into (14), and factoriz- ing the function (u(w) in accordance with the pairwise disjoint scopes of the product unit, i.e..
fu (v.) = IIeech(w) fe(e)). we have
I (u(WW))pu
II (Ech(u))
fe(bhe)
II (Ech(u)
II cEch(u)
where u E P. The decomposability assumption (Definition 5) says that children of the product unit have independent scopes. The consequence is that the integral reduces the product of simpler integrals. The integral w.r.t. Pu. is tractable if the integrals of all its children Pe are tractable for all E ch(n), i.e., the tractability of the product unit propagates from its children. Similarly as before, the functional forms of the l.h.s. integral of the product unit and the r.h.s. integrals of its children are the same, which allows to replace them with concrete realizations I,, (l.h.s.) and Le (r.h.s.).
If the tractability holds for each unit u E (S, P,13 in the computational graph, then a PC is tractable and (13) admits a closed-form solution.
D.2 PROOF OF PROPOSITION 1
Our goal is to show that the integral (2) can be computed recursively under closed-form solution. To this end, we proceed analogously as in the proof of Proposition 5. Recall from Definition 6 that f(T) == llktt f(()) and if Definition 5 and Assumption hold, then it follows from the properties of Definition 4 that the partial factorization fu (v/.) == Iliet. f(()) can be extracted from fT) for any и E PS,P.B) where L,, L is the set of the input units that can be reached from u and have
20

---

Published as a conference paper at ICLR 2024
the unique scope. Similarly before, the existence of fu(w)) allows us to define the intermediate integral, which acts on a given computational unit u, as follows:
(u(( = f fu (w (dvv))
(15)
where Pu (1(a)) is the probability density of u, and Vu is the reference measure on the measurable space (V.. a (.))). v, can take various forms depending on whether the scope duu is the homoge- neous node, part of) the heterogeneous node or the leaf node. If vh, is the homogeneous node, then I is the hyperspace of all finite subsets of some underlying space, V, which characterizes the fea- ture density of the unit. If thu the heterogeneous node, then V u is the Cartesian product space composed of, e.g., continuous spaces, discrete spaces, but also hyperspaces defining other RFSs. If Vh is the leaf node, then V. can be the Cartesian product of continuous and (or) discrete spaces. For this reason, the reference measure instantiates itself depending on given computational unit, u, and can take various forms based on the space, V..
In the case th, is (subset of) leaf node(s), the proof is carried out in the same way for Proposi- tion This is also true when vi is a (subset of) heterogeneous node(s). The difference is that Xu in (14) is replaced by more general measure Vu- This leaves us to prove only the last case where thu is a homogeneous node.
Set units. Consider the scope of the set unit, Vu. F(W.), the hyperspace of all finite subsets of some underlying space, Vw That is, we have d/u f&b, ...,, Vwe where Vur, E V w are & distinct instances of the identical scope of the feature density of the set unit u. Furthermore, let v. be the unitless reference measure (5) on (V,,, o (V.))) associated the set unit, (Vh.), and let vie be the reference measure (V (V).)) correspond- ing to the feature density, p(vw.). Now, from the properties of f, we have fu(bb) = II fi f.(W..)) and, after substituting this function, along with the density of the set unit (1), into (15), obtain
B, is RFS taking values in Vu =
J (W(W))p((Vu))al
fullWwr..... thw. DP (foen.... Dane Du (deben drbwa)
ck. v/
II filw (elpp)) klp(k) II p(ii: Mew (ditws) i=1
ck!
Σ p(k)) II
Sely (e Nu (deppoe)
k=
$=1 Vi
A
Σ p(k) 0=
II 1=1
/
where T == Th x ... x Vp Once again, we can see that the functional form of the l.h.s. integral the same as that of the r.h.s. integrals, allowing us to replace them with l and I,.
E IMPLEMENTATION
There are multiple ways implement SPSNs. However, the construction of the computational graph always has to follow from the properties of computational units (Definition 3) and respect the structural constraints (Definition 5). We provide more details on the layer-wise implementation in- troduced in Section 3. However, before that, we first present an intuitive description of constructing SPSNs a node-wise manner.
E. NODE-WISE APPROACH
Let us consider the example in Figure 4. The left part (Figure 4(a)) shows the data graph (Defini- tion 1) and its schema (Definition 2) highlighted by the dashed line. We can see that the schema is in fact simplified graph that excludes the structurally identical children of the homogeneous nodes
21

---

Published as a conference paper at ICLR 2024
(a) Data graph
(b) Computational graph
Figure 4: Sum--product-sel networks. (a) The tree-structured, heterogeneous, data graph, T, (Definition 1), and the schema (dashed line), S. (Definition 2). Here, A is the heterogeneous node, v is the homogeneous node, and x denotes the leaf node of (b) The computational graph. G, of an SPSN (Definition 3) designed based on S. where x. } and p are the sum unit, product unit, of in are modeled by the corresponding parts of G in (b), as displayed in green, orange, and blue. The dashed arrow (b) (the second child in the top sum units) represents the same sub-network as in the first child.
unit and leaf unit of G. respectively. The subtrees
In this example, we consider ni = 1, n, = 2, and =
and keeps only the child that allows to reach the deepest level of the tree. The construction of an SPSN follows from the schema. We start at the root heterogeneous node. Any heterogeneous node can be modeled by possibly many alterations of units and product unis. is possible to recursively split the heterogeneous node as long as it still contains enough elements since, every time we apply the product unit, we split the heterogeneous node into parts (or more depending on np). The right part (Figure 4(b)) displays that the root heterogeneous node is modeled by only single sum unit whose children are two product units (the right one indicated by the dashed arrow, which we hide for simplicity). This is due to the fact that the root heterogeneous node contains only two children and the product unit separated the children into two singletons: homogeneous node and heterogeneous node depicted in the left and right child of the root heterogeneous node of the data graph. The homogeneous node can modeled only by the set units; therefore, we add a set unit into the first child of the aforementioned product unit. The heterogeneous node has again only two children, which means that we will model it the same way as the root one, i.e., by using a single sum unit with product unit in each of its children. Now, if we go back to the homogeneous node, then we can see that, in the schema, its child another heterogeneous node with two children. Therefore, we repeat the same process before. Since of the children of this heterogeneous node is the leaf node, we place an input unit into the computational graph. This continues until we traverse all parts of the schema, extending the computational graph in the process.
E.2 LAYER-WISE APPROACH
The node-wise approach is simple mechanism construct SPSNs. Nonetheless, it is often compu- tationally inefficient for the implementation with modern automatic differentiation tools. The reason for this lies that these tools have to produce their own computational diagram (graph) from the computational graph of the SPSN. Therefore, we provide a layer-wise approach to construct SPSNs, simplifying the underlying differentiation mechanisms.
Algorithm 1 contains the procedure spsn network(t) (b), Ne, n4, Rg. Rpp)) which constructs an SPSN based on the following inputs: vé is the scope of the root unit (which we applying the procedure), n,, is the number of root units of the network (we set the network for classification), and nı, n.. and np are the number of layers, children the sum units, and children of the product units, respectively, which common to all blocks in the network. This imposes a regular structure on the network and makes it suitable to the layer-wise ordering of the computational units. The resulting computational graph is consequently more efficient for the implementation with the automatic differentiation tools and also more convenient for parallelization on the contemporary computational hardware.
the schema when 1 when using
The key procedure is spsn block, which recursively constructs the computational graph of an SPSN in the block-by-blode manner depicted in Figure 2. We first create empty block (line 1). Then,
22

---

Published as a conference paper at ICLR 2024
continue by creating layers of scope functions in scope (line 2). We provide more details on this procedure below. For each layer of these scopes, we add (via t-) two layers of computational units into the block. (i) The layer of sum units, slayer, where the first argument is the number of children of each sum unit and the second argument is the number of sum units. (ii) The layer of product units, player, where the meaning of the arguments is the same as with slayer. We repeat this until ny = 1. Then, we add the layer of input units, ilayer. This layer assigns an input unit to each scope in based on its type. That is, if the scope represents the leaf nodes, then it checks the type of data (floats, integers, strings) and creates appropriate probability density. If the scope is the homogeneous node, then it creates the set unit. The feature densities of all set units in this input layer are not connected to any other part of the computational graph at this moment. The procedure then proceeds by gathering all these unconnected scopes via scope set units, All these steps are now repeated by calling spsn_block again (line 14). Every iteration, spsn_block returns the network that was created to this moment, N, and the scopes of the unplugged set units that are provided to the next iteration. The network that has been generated so far, N, is connected to the unplugged scopes of the set units in the current block B by using connect.
Algorithm 2 presents the scope scope_layers procedure. It starts by assigning the input set of scopes ei into L, a structure holding all layers of scopes, creating the first layer scopes. The next layer is made by the scope slayer and scope player procedures. scope slayer uses repeat make n, copies of each element in w to reflect the fact that the children of the sum unit have the identical scope. Similarly, scope-player splits each element v into np parts, reflect the fact that the children of the product unit have disjoint scopes. This process is repeated until we either (i) reach maximum allowable number of layers or (ii) there is scope in e represented by singleton. The latter is realized by minimum length, which first evaluates the number of elements in each scope of g) and then finds their minimum.
The block size. The regular structure of the SPSN block allows us to find a closed-form solution for its size terms of the number of computational units containing parameters. The number of sum units is given by K, = |ها E in spsn.block. The number of input units is K; = (n,,))) While K₃ can directly be used to compute the number of parameters in all sum units, K2 serves only complete an intuition about the size of each block. To obtain a concrete number of parameters in the input layer, we need to count the parameters in each of its units due to the differences in the data types.
" (n.T.,)), where | is the cardinality of the input set scopes
23

---

Published as a conference paper at ICLR 2024
Algorithm 2 Procedures
procedure scope.layera// Rzy
Algorithm Construct the SPSN network
1: I. = (1))
procedure apan ap newwork(( Rey T4, Ray Up)
2: while true do
I: v = repeat (1b; nh.)
3: v scope scope slayer (1), na)
2: N. spen block( (oc 1,, ny, mp)
4: f wcope-playeen (1) mp)
3: return N
5: L < y
6: if minimum lenght( is or my is then
block(()) procedure span spsn_block(s) 1b, n,, np))
7: break
1: B = Ø
else
2: I. scope layers ny; ney mp)
9: - -1
3: for all 1 L do
10: end if
4: A = length(()
11: end while
5:
if n4 > 1 then
12: return
6:
B - slayer(m,, k)
procedure scope slayer()),
7:
B player k n2)
1: e =0= Ø
8:
else
9:
B (1ayer(I)
for all E v do
3: 1 <- repeat n,)
10:
V = acope_set.unitee
end if
4: end for
5: return v
12:
Th - end for
procedure scope.player((..n)
14: N. v spsn_ spsssppscceeeec block( ni, U2 mp)
1: Ø = Ø
= connect(N, B)
for all E v do
16: return N,
3: v f- spplitss,n
end for
5: return 3b
F EXPERIMENTAL SETTINGS
The leaf nodes, L, contain different data types, including reals, integers, and strings. We use the default feature extractor from CSONGrinder j1 (v2.3.2) to pre-process these data. We perform the models mentioned Section 5. For the MLP, GRU, and LSTM networks, set the dimension of the hidden state(s) and the output in {10, 20, 30, 40). For the HMIL network, we use the default settings of the model builder from Mill. j1 (v2.8.1), only changing the number of hidden units of all the inner layers in (10, 20, 30, 40). We add single dense layer with the linear activation function to adapt the outputs of these networks to the number of classes in the datasets. For the SPSN networks, distribution and the following hyper-parameters: Tu E {1, 2,3, n. E (2, 3, 10}. and n, := 2. We use the ADAM optimizer (Kingma & Ba, 2014) with fixing 10 samples in the minibatch and varying the step-size in 10.1,00 0.01, 0.001 The datasets are randomly split into 64%, 16%, and 20% for training, validation, and testing, respectively.
the grid search over the
choose the Poisson distribution as the cardinality
We performed the experiments on computational cluster equipped with 116 CPUs (Intel Xeon Scalable Gold 6146). The jobs to perform the grid search over the admissible range of hyper- parameters were scheduled by SLURM 23.02.2. We limited each job to single core and 8GB of memory. The computational time was restricted to one day, but all jobs were finished under that limit (ranging approximately between 2-18 hours per dataset).
G DATASETS
The CTU Prague relational learning repository (Motl & Schulte, 2015) is rich source of structured data. These data form a directed graph where the nodes are tables and edges are the foreign keys. Some of these datasets cycles. As a part of the preprocessing, we decompose these cyclic graphs to tree graphs by selecting node and then reaching to the neighborhood nodes in the one-hop distance.
already in the form of threes; however, there also graphs containing
24

---

Published as a conference paper at ICLR 2024
Table shows the two main attributes of the datasets under study: the number of instances (i.e., the number of tree-structured graphs) and the number of classes of these instances. A detailed description of these datasets, additional attributes, and accompanying references are accessible at https: / re at inaal...... fit. wwwt.cc.....
Figure shows single instance of the tre-sstructured graph data in the JSON format (Pezoa al., 2016), and Figure illustrates the corresponding schema (Definition 2 of the main paper). As can be seen (and as also mentioned in the main paper), the leaf nodes contain different data types: integers, floats, and strings. In Figures 6-12, we provide the schemata of the remaining datasets in Table 2.
Table 2: Datasets. The number of instances (trees) and the number classes the datasets under study, no. wa, and nt, are the numbers of homogeneous nodes, heterogeneous nodes, and leaf nodes, respectively, in the whole dataset. no. ugg and üz show the corresponding average number of nodes tree. The last column is the size of the dataset in MiBs. For comparison, the full training MNIST dataset has around 45 MiBs.
dalaset
instances (trees)
# of classes
11.1r
T%g
[MiB
mulaggnessi
188
2
5081
15567
57575
27
83
305
3.3
genes
3544
17941
125712
cora
2708
7
16274
13566
247663
6
5
91
9.3
citeseer
3312
16071
12759
411929
4
124
14.4
wehkp
877
5
4970
4093
396890
5
453
13.2
chess
295
3
10325
590
53593
35
2
182
1.8
782
3128
0.170
bepatitis
500
2
1500
7008
65039
14
130
2.3
REFERENCES
David J Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11 11(4):881-59, 1981.
Ole Barndorff-Nielsen. Information and exponential families: In statistical theory. John Wiley & Sons, 1978.
Billingsley. Probability and Measure. Wiley Series in Probability and Statistics. Wiley, 1995.
Hei Chan and Adnan Darwiche. On the robustness of most probable explanations. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, pp. 63-71, 2006.
Y Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. UCLA. URL: hutp://starai. cs. ucla edulpapers/ProbCire2. pdf. 2020.
Daryl J Daley, David Vere-Jones, et al. An introduction to the theory of point processes: volume I: elementary theory and methods. Springer, 2003.
Adnan Darwiche. A differential approach inference in bayesian networks. Journal of the ACM (JACM), 50(3):280-305, 2003.
Bruno de Finetti. Funzione caratteristica di un fenomeno aleatorio. In Atti del Congresso Inter- nazionale dei Matematici: Bologna del 10 de settembre di 1928, pp. 179-190, 1929.
Bruno de Finetti. Foresight: Its logical laws, its subjective sources. In Breakthroughs Statistics:
Foundations and Basic Theory, pp. 134-174. Springer, 1937.
Persi Diaconis. Finite forms of de Finetti's theorem on exchangeability. Synthese, 36:271-281, 1977.
Persi Diaconis. Recent progress on de finetti's notions of exchangeability. Bayesian statistics, 1111-125):13-14, 1988a.
Persi Diaconis. Sufficiency as statistical symmetry. In Proceedings of the AMS Centennial Sympo- sium, pp. 15-26, 1988b.
Persi Diaconis and David Freedman. Finite exchangeable sequences. The Annals of Probability, pp- 745-764, 1980.
25

---

Published as a conference paper at ICLR 2024
Persi Diaconis and David Freedman. Partial exchangeability and sufficiency. Statistics: Applications and new directions, pp. 605-236,10 1984.
Charles J Geyer. Likelihood inference for spatial point processes: Likelihood and computation. In Stochastic Geometry: Likelihood and Computation, pp. 141-172. Chapman and Hall/CRC, 1999.
IR Goodman, RP Mahler, and Hung T Nguyen. Mathematics of Data Fusion, volume 37. Springer Science & Business Media, 1997.
Geoffrey Grimmett and David Stirzaker. Probability and random processes. Oxford university press, 2001.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 112. 2014.
Stefan Lüdtke, Christian Bartelt, and Heiner Stuckenschmidt. Exchangeability-awan sum-product networks. In Proceedings of the Thirty-First International Joint Conference on Artificial In- telligence, IJCAI-22, pp. 4864-4870. International Joint Conferences on Artificial Intelligence Organization, 2022.
Ronald PS Mahler. Statistical multisoure--mulitangee information fusion, volume 685. Artech House Norwood, MA, USA, 2007.
G. Mathéron. Random Sets and Integral Geometry. Wiley Series in Probability and Mathematical Statistics. Wiley, 1974.
Jan Motl and Oliver Schulte. The CTU Prague relational learning repository. arXiv preprint 2015.
Aniruddh Nath and Pedro Domingos. Learning relational sum con-product networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Hung T Nguyen. An introduction to random sets. Chapman and Hall/CRC, 2006.
Mathias Niepert and Pedro Domingos. Exchangeable variable models. In International Conference on Machine Learning. pp. 271-279. PMLR, 2014.
Mathias Niepert and Guy Van den Broeck. Tractability through exchangeability: A new perspective on efficient probabilistic inference. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 28, 2014.
Peter Orbanz and Daniel M Roy. Bayesian models of graphs, arrays and other exchangeable random structures. IEEE transactions pattern analysis and machine intelligence, 37(2):437-465 2014.
Robert Peharz, Sebastian Tschiatschek, Franz Pernkopf, and Pedro Domingos. On theoretical prop- erties of sum-product networks. In 18th International Conference Artificial Intelligence and Statistics, pp. 744-752 PMLR, 2015.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference on Machine Learning, pp- 7563-7574. PMLR, 2020.
Felipe Pezoa, Juan L Reutter, Fernando Suarez, Martín Ugarte, and Domagoj Vrgoë. Foundations of JSON schema. Proceedings of the 25th international conference on World Wide Web, pp. 263-273, 2016.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689-690. IEEE, 2011.
Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of prob- abilistic models. Advances in Neural Information Processing Systems, 29, 2016.
26

---

Published as a conference paper at ICLR 2024
Martin Trapp. Robert Peharz, Hong Ge, Franz Pernkoff, and Zoubin Ghahramani. Bayesian learning of sum-produce networks. Advances in neural information processing systems, 32, 2019.
MNM Van Lieshout. Markov point processes and their applications. World Scientific, 2000.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum-
product networks. Machine Learning. 108(4):551-573, 2019.
Antonio Vergari, Yoolung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A composi- tional atlas of tractable circuit operations: From simple transformations to complex information- theoretic queries. arXiv preprint arXiv:2102.061177 2021.
Ba-Ngu Vo, Nhan Dam, Dinh Phung, Quang Tran, and Ba-Tuong Vo. Model-based learning for point pattern data. Putlern Recognition, 84:136 84:136-151, 2018.
Alan J Weir. Lebesgue Integration and Measure, volume Cambridge University Press, 1973.
Sandy Zabell. Symmetry and discontents: Essays on the history of inductive probability. Cambridge University Press, 2005.
Han Zhao, Pascal Poupart, and Geoff Gordon. A unified approach for learning the parameters of sum-product networks. In Proceedings of the 30th Advances in Neural Information Processing Systems, pp. 433 441, 2016.
[Dict]
# inst 188
lumo: [F1oat64] n_unique 177, m_inst 188
inda: [1nt # n_unique 2, n_inst 188
log9: [Float64, InL64] A_unique 107, niinst
indl: [Int64] # n_unique = 2, n_inst 188
atoms:
[List]
[Dict] n_inst 4893
element: [String. n_unique 7, n_inst 4893
bonds: [List] inint 4893
[Uict]
niint 10486
[String]
n_unique
n_inst 10486
bond_ [int
t n_unique 6, n_inst 10486
typo_atom: [Int64]
n_uniqua 26, n_inst
charge: [Ploat64] 4 n_unique 444, n_inst 10486
sype_atons [InL64]
n n_unique 36, n_inst 4893
charge: [11cat64]
s_unique 444, n_inst 4893
Figure Schema. The schema of the mutagenesis dataset.
27

---

Published as a conference paper at ICLR 2024
[bict] # niinst 862
interactions: [1dst] nninst 862
[Dict] * n_inst 1820
type: [Steing] n_unique n_inst
expression_torr: 211at60,int600 n_unique 827, mninst 1820
records:
[Lise] s_inst 1920
[Dict] n_inst 10913
lacalizatien: [String]
n_unique 13, n_'rst 10913 complex: [Stzing]
n_unique 14, aiinst 10913 chremosome: [int64]
n_uniqua 17, n_'rst 10913 functien: [String]
n_unique 13, n_inst 10913 essential: [String]
n_unique 4, inint 10913 class: [String]
n_uniqua 22, niinst 10913 phenotype: [String]
n_unique 13, niinst 10913 motif: (String]
n_unique 183, iinntt 10913
records:
[List]
+ iiinst 862
[Dict]
n_inst 4346
loca localizat 1iz ion:
[String]
n_unique 15, n_inst 4346
complex:
[String]
n_unique 52, n_inst 4346
chromesome:
[Int64]
n_nniuu 17, niinst 4346
Funct lon:
[String]
n_unique 13, n_inst 4346
essential:
[Steing]
n_unique 4,
class:
[String]
n_unique 24, m_inst 4346
phenotypa:
[String]
n_unique
n_inst 4346
motif: [String]
# n_unique 236, n_inst 4346
Figure 6: The schema of the genes datasct.
[Dict] nninst 2708
citing: [List]
niinst 2708
[Dic=] niinst 10856
word_aited_id: [Matt] n_ins 10858
[String] n_unique 1432, n_inst 198447
word_cited_iad [List]
n_inss
[String]
n_ que 1432, n_inst 49216
Figure 7: The schema of the cora dataset.
[Dict]
n_inst
citting [Matt]
nnsnst 3312
[Dict] niinst 9447
word_nited_ids [T n_ins 9447
[String] n_unique 3703, n_inst 306764
word_citeddidt [List]
niins [String]
n_unique 3703, iiint 105165
Figure 8: The schema of the citeseer dataset.
[Dicc] nginst
eigting [Matt]
n_fnst 877
[Dic]]
ninnt 3216
cite_ [List] niins 3216
[String] n_unique 1703, n_inst = 317525
word_oited_ie Id: [Mdat]
fnst 877
[String]
umique = 1703, niins 79355
Figure 9: The schema of the wobkp dataset.
28

---

Published as a conference paper at ICLR 2024
[Dict] # Aiist = 278
person: [Dict]
nninst
haaPositions
[String]
r_nnique n_inst 278
student: [SLzing]
Aunnique iLins: 278
profeasor: [String]
A_unique
niinst 278
16: [nt664
n_unique 278, A_inat - 278
yearsIaProgzamm [String]
aLunique 12,
ccurses: [Liot]
inst 278
[ttiing]
n_uniqua nninst
Interactiona:
[List]
Inint 278
[Dict] # n_inst 226
hasPosition: :string]
n_unique ninst 226
aLudent:
[Stzing]
n_unique 2, Aninat 226
professor:
[String]
n_uniqus
id:
[int64]
R_unique 130, n_inst = 226
years InFrggra::
[string]
n_unique 12, n_inst 226
courses: [List]
n_ins: 226
[String] a_unique 3, in 415
Figure 10: The schema of the the uw_cse dataset.
[Dict]
n_inst
sex: [String]
n_anique 2, n_inst 5C0
age: [String]
n_anique 7, i_inst 5C0
inf: [List]
inst 500
[Dsct] n_inst 196
dur: [String]
n_unique n_inst
bio:
[List]
niinst 500
[osct]]
n_inat
activicy: [String]
$ n_unique 5, n_inst 621
Fibros: [String]
n_unique 5, iiinst 621
indis: [List]
inst 500
[Dsct]
# n_inst = 5691
dbf [String]
n_ que
2, n_ins:
tche: [SLring]
n_unique
4, n_ins 5591
gpt:: [String]
n_un" que
4, n_ins:
alb: [String]
# n_unique
2, n_ins: 5591
tp: [String]
n_unique
4, niins: 5591
[String]
n_unique
6, m_ins: 5591
got: [String)
# n_unique 5, n_inst 5591
[String]
f_inat n_unique 5691, n_inst 5691
n_uniqqe
in_id:
[Ent
2tt: [String]
n_uniqqe 6, n_ins: 5691
tbil;
[String]
# n_unique 2, iiins 5591
Figure 11: The schema of the hepati t dataset.
29

---

Published as a conference paper at ICLR 2024
[Diet] ins 295
w3: [List]
n_inst 295
[1nt64] f_anique 16, n_inst 793
[List]
n_inst
[Int64] R_unique 23, n_inst E66
b5: [Liot]
n_inst
[Tnt64] r_unique 23, ininst 836
b2: [Liat]
n_inst 295
[Int64] n_unique 15, n_inet 678
white: [List]
nninst 295
- [InL64] n_unique 54, nginst 4853
w6: [List] + n_inst 295
[1nt f_unique 23, m_inst
w4: [M
n_inst 295
[InL64] n_anique 22, n_inat 839
b8: [List]
n_inst 295
[int64] f_unique 24, n_inst 860
[List]
n_inst
[int64] R_unique 18, n_inst 6195
[1iat]
n_inst
[Tnt64]] n_unique 25, n_inst 897
whiteBlo:
[InL64]
q___iqque 83, inst 235
event_date:
[String]
>_aniiuee 2, iins 295
b1: [List]
n_inst 295
[Tnt64] n_unique 8, r_inat 681
wi: [Liot]
n_inst 295
[Ttt64] r_unique 8, r_inat 620
b6: [List]
n_inst 295
[Int64] + r_anique 23, inint B28
site:
[List]
n_inst 235
[Tnt64] r_unique
9, r_inat 2655
[Liat]
[Int64] r_unique 23, n_inst 830
800:
[Miat]
n_inst
[InL64] n_unique 15, n_inst 885
b10:
[List]
mninst 295
[Int64] n_unique 25, n_inst 878
open igg_d:
64)
n nn que 75, inat 295
openings:
[List]
insstt
[Dict:] inst 295
w3: [Litt]
inatt 295
IInt64] a_unique 15, ninnt 702
b2:
[List]
inst = 295
Tnt644] s_unique 16, n_inst 635
w4: [List]
nnina - 295
IInt64] a_unique 17, ninst
w1: [Tist]]
n_inat = 295
[Int64] A_unique 8, n_inst 620
variation:
[List]
miintt 295
1nt # =_unique 56, ninnt 8635
[14
inst 295
InL66] s_unique - 9, n_inst 713
opening_idt
n_unique 75, nins:
name:
[List] 4 n_inat - 295
[Int64] =_unique 43, ninst 4653 i_inst 235
b3: [List]
[Int64] =_unique 17, ninnt 719 inint 293
[1ist]
[Int64] 4 unigqu = 19, iiint 619
[List]
293
[InL64]
A_unique 14, ninnt 682
code: [List]
inst 295
[1nt64] s_unique n_inst 295
w8: [T.att] $ n_ins 295
[Int64]
n_unique
iinat
b3: [List]
n_inst 295
[int64] r_unique
niint
opening: [1 + n_inst 295
[int64] r_unique 44, niinst 4574
round: [1iot]
n_ins 295
[Tnt64] r_unique 11, n_inst 1149
black: [List]
n_inst
[int64] r_anique 55, iiint 4854
[Liot]
n_inst
[Tnt64] r_unique 12, fnsns 724
w10: [List] + inintt 295
[Tnt64] r_anique
Inst 888
b4: [List]
n_inst 295
[Int n_unique
inint
b7: [List]
inist 295
[Tnt64] r_unique 23, inst
BlackBlo:
[Int64] n_unique 89, inst 295
game_id:
(Int64)
inuuiquue 295, inst 295
[Liat]
I_nnss
[InL64] r_anique 24, inst 890
Figure 12: The schema the chess datasct. 30


Reviews:
[{"review_id": "4NFcCOtB73", "reviewer": "Reviewer_gTbZ", "summary": "This paper develops a sum-product-set networks (SPSNs) to study the tree-structured graphs. It develops new variant of probabilistic circuts to obtain tractable inference for SPSNs. In the experiments, it shows that SPSNs obtains comparable performance to Neural Networks in the graph classification task.", "questions": "Sorry I am not an expert in this topic, I did not have particular technical questions.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has the following strengths:\n\n**1** the problem this paper working on is important to the community. The way of extending the applicability of probabilistic circut to the tree-structured graph data would be interesting and promising to the community. \n\n**2** the presentation and writing are very well. Although I am new to this topic, I can easily understand the main points and the main mechanism of this SPSNs method. \n\n**3** I like the investigation of the exchangeability of SPSNs. The study seems complete.", "weaknesses": "Due to my limited expertise, I did not have identified meaningful weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mmEfGGCDjH", "reviewer": "Reviewer_k1pi", "summary": "The paper suggests a new type of probabilistic circuit (PC) that can be trained and perform inference in tree-structured graph data. Standard sum-product networks (SPNs), a PC, represent a probability density over unstructured data, which forms the input random variables. To model a density over tree-structure graphs, the manuscript introduces \"set units,\" nodes in the PC that allow for a variable number of nodes/edges in the data graph.", "questions": "* Were there any empirical boundaries or assumptions when implementing the recursive algorithm described in \"Building SPSNs\"? How do you deal with large data graphs with multiple heterogeneous nodes and size constraints?\n* Could you please expand on the \"(...) building a set of trees based on a user-specified neighborhood\" in Section 4 regarding the similar graph-based approach from (Errica & Niepert, 2023)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* Tractability and Exchangeability: The manuscript presents a theoretical foundation for the tractability of the method, based on PC results in Section 3.1 and SPSNs' exchangeability based on its node types in Section 3.2.\n* Using the theory of finite random sets in SPSNs yields a simple and elegant way of representing tree-structured graphs.", "weaknesses": "* Implementation: the manuscript does not provide a transparent discussion about the implementation of SPSNs. The non-formal description provided in \"Building SPNs\" raises relevant questions related to the convergence and size of the model. Moreover, from the setup, it is unclear how sensitive parameter initialization and/or hyper-parameter tuning the model is.\n* Experiments are encouraging but not convincing. Section 5 is unclear on how the tractability and exchangeability properties of SPSNs are exploited in the experiments. While the missing values results in Figure 3 are beneficial, they do not highlight \"efficient inference over\nspecific parts of the data graph,\" as stated in the Conclusion. Moreover, it might be helpful to the manuscript to compare the results with recent works, such as the ones discussed in Section 4.\n* Paper presentation\n    - The writing is unclear between PCs and SPNs, as the title evokes SPNs while the text uses PCs. The authors should clarify the difference between the two or assume interchangeable usage under assumptions.\n    - It could be beneficial to discuss the differences between SPNs and SPSn sooner in the paper, as it is a key contribution of the work. The sentence \"This differs from the conventional sum-product network...\" is helpful but only appears in Section 3.\n    - The manuscript could better articulate its motivation by connecting the problems presented in the introduction with some of the results. For instance, it is not clear in the paper how SPSNs take advantage of \"the parent-child ancestry inherent in tree-structured graphs\" in a different way than competitive generative models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9mIfNLJFiP", "reviewer": "Reviewer_snrr", "summary": "The authors propose sum-product-set networks, an extension of probabilistic circuits from unstructured tensor data to tree-structured graph data. Key to their approach is the use of random finite sets to reflect a variable number of nodes and edges in the graph and allow for exact and efficient inference. The empirically demonstrate that their approach is on par with other intractable neural models.", "questions": "- The first question that comes to mind is: can we not use knowledge compilation [1] to compile the distribution over tree-structured graphs into a logical circuit? One can use logical circuits to induce distributions over many different structured objects such as paths in a grid, hierarchies of classes, preferences, as well as subsets of size $k$ [2, 3, 4]. One can then learn the parameters of such a distribution from the data. It might very well be the case that the distribution over tree-structured graphs does not admit a tractable circuit, but such an assertion seems to be absent from the paper.\n\n- Could you please explain what a schema is? I understand how one could obtain a schema from a tree-structured graph, but aside from the definition, I was hoping for an intuitive explanation. ( I am familiar with the term in the context of databases, which does not seem to translate? )\n\n- Am I correct in my understanding that, according section, set units only apply to homogeneous nodes?\n\n- I really would've like to see a (toy) complete example of an SPSN. Could you please provide such an example?\n\n- Assumption 1 (Requirements on the set unit) \"states that the cardinality distribution vanishes for a sufficiently large $m$\", What exactly do you mean by that? As a follow up, am I correct in understanding that the elements of the set are independent given the cardinality? i.e. we do not consider the statistical correlations between the elements of a set? ~To me this consequently puts into questions the tractability of SPSNs laid out in proposition 1.~\n\n- Could you please say more regarding Definition 5? What structural constraint is being imposed here exactly? To me, \"follow only a single child of each sum unit\" reads as determinism?\n\nReferences:\n\n[1] On probabilistic inference by weighted model counting. Mark Chavira, Adnan Darwiche. Journal on Artificial Intelligence 2008.\n\n[2] Neuro-Symbolic Entropy Regularization. Kareem Ahmed, Eric Wang, Kai-Wei Chang, Guy Van den Broeck. UAI 2022.\n\n[2] Semantic Probabilistic Layers for Neuro-Symbolic Learning. Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, Antonio Vergari. NeurIPS 2022.\n\n[3] SIMPLE: A Gradient Estimator for k-Subset Sampling. Kareem Ahmed, Zhe Zeng, Mathias Niepert, Guy Van den Broeck. ICLR 2023.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is decently written, although, in my opinion, some important aspects seem to be missing.\n\n- Despite the potentially toyish nature of the experiments considered, the proposed models seem to be on par with other intractable neural models, as well as significantly more robust to missing data.", "weaknesses": "- The writing of the paper would be greatly improved by adding informal intuitions here and there, as well as a (toy) complete example of an SPSN.\n\n- The authors do not make it clear that one could not obtain a distribution over tree-structured graphs using e.g. knowledge compilation to compile the distribution over tree-structured graphs into a logical circuit whose parameters could then be learnt, inducing a distribution over the desired structured objects. If so, is one theoretical conclusion that there is an expressivity gap between PCs with and without set units?\n\n- The authors only remark in passing that the infinite sum required to evaluate the set unit reduces to a finite one in practice; an argument upon which their tractability results hold. This should be made more formal.\n\n- The writing doesn't really give us an idea of the scale of the experiments performed, but they seem toyish.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pQAdgIWS09", "reviewer": "Reviewer_9xzE", "summary": "This paper proposes sum-product-set networks (SPSN), a tractable probabilistic model for tree-structured data. Interestingly, the structure of the tree and dimensionality of the data is assumed to be random rather than fixed. This is achieved through the use of random feature sets (RFS), which allows for the specification of distributions over sets of varying length taking value in some domain. RFS are integrated with Sum-Product Networks (SPN) through the use of a schema/template for the data, which hierarchically specifies the fixed parts of the tree structure (heterogenous nodes) and the variable parts (homogenous nodes). Under some (strong) assumptions on the set unit distributions and the query, inference is shown to be tractable in SPSNs. Empirical results show that the classification performance is slightly worse than, but competitive with, approaches based on neural networks.", "questions": "- Is it possible to relax the assumption of full independence in a set unit, or is this a fundamental limitation? E.g. through partial exchangability for the set unit distributions?\n- Details on how SPSNs are learned seem to be missing. It seems the structure of the SPSN is fixed (Pg 4.), but how are the parameters learned? Is the cardinality distribution learned, and if so, how is it parameterized?\n- Is there any technical reason why the SPSN architecture cannot be extended to DAG, rather than tree structured data? \n- The related work section is thorough, but, especially considering that the tested datasets all come from a relational schema, it would be useful to better understand the relationship with relational SPNs. For example, how does one translate a relational schema to a tree schema as in Figures 4-11 (in what way is relational data \"a particular form of graph-structured data\")?\n- It is not clear what the result is in Proposition 2 (the statement seems more like a definition).\n\n============================\n*After rebuttal/discussion*\n\nAfter the author rebuttal and reviewer/AC discussion, I have mixed feelings about the work. I find the approach of SPSNs for probabilistically modelling tree structured data using RFS to be very promising, with some evidence for its utility through experiments. On the other hand, the manuscript does not fully justify/analyse key components of the approach, namely (1) providing concrete examples of interesting tractable inference queries when the number of variables is not fixed, besides marginalizing leaves (where the structure of the tree is already fixed); and (2) empirical or theoretical analysis of the impact of Assumption 1 on expressivity/modelling capacity. I still support acceptance but less enthusiastically given the mentioned weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper presents an (as far as I am aware) novel problem of developing a tractable probabilistic model for tree-structured data, where the graph of the tree is itself random. Such data structures naturally arise in many areas, such as XML/JSON, scientific domains, natural language (e.g. syntax trees), and relational data. The proposed solution, SPSNs, are a well-designed variant of sum-product networks that utilizes random features sets (set units) to allow tree nodes to have a random number of children while maintaining tractability.\n\n- Novel and adept application of RFS theory to deep tractable model architectures (SPNs). This enables the specification of distributions over hierarchical random trees.\n- The work could have significant impact in pushing the application of TPMs towards new domains, such as natural language processing. \n- The clarity and technical quality of the paper is excellent. In particular, Figure 2 was very useful for understanding the role of sum, product and set units in relation to the tree schema.", "weaknesses": "- The requirement of full independence in the distribution of a set unit seems quite stringent and potentially unrealistic. For example, for the mutagenesis example in Figure 1, this would correspond to atoms in a molecule being independent (conditional on the molecule size). \n- On the empirical side, to justify the importance of tractability it would be useful to test some example queries on the learned SPSNs, and their domain-specific interpretation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)