Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks
Authors: Federico Errica
Mathias Niepert
Venue: ICLR 2024 poster (2024)
Keywords: Deep Graph Networks
Graph Neural Networks
Bayesian Networks
Sum-Product Networks
Graph Representation Learning
Missing Data
Graph Classification
Weak Supervision
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce Graph-Induced Sum-Product Networks (GSPNs), a new probabilistic framework for graph representation learning that can tractably answer probabilistic queries on graphs

Abstract: We introduce Graph-Induced Sum-Product Networks (GSPNs), a new probabilistic framework for graph representation learning that can tractably answer probabilistic queries. Inspired by the computational trees induced by vertices in the context of message-passing neural networks, we build hierarchies of sum-product networks (SPNs) where the parameters of a parent SPN are learnable transformations of the a-posterior mixing probabilities of its children's sum units. Due to weight sharing and the tree-shaped computation graphs of GSPNs, we obtain the efficiency and efficacy of deep graph networks with the additional advantages of a probabilistic model. We show the model's competitiveness on scarce supervision scenarios, under missing data, and for graph classification in comparison to popular neural models. We complement the experiments with qualitative analyses on hyper-parameters and the model's ability to answer probabilistic queries.

Published as a conference paper at ICLR 2024
TRACTABLE PROBABILISTIC GRAPH REPRESENTATION LEARNING WITH GRAPH-INDUCED SUM-PRODUCT
NETWORKS
Federico Errica NEC Laboratories Europe Heidelberg, Germany
Mathias Niepert University of Stuttgart Stuttgart, Germany
ABSTRACT
We introduce Graph-Induced Sum-Product Networks (GSPNs), new probabilistic framework for graph representation learning that can tractably answer probabilistic queries. Inspired by the computational trees induced by vertices in the context of message-passing neural networks, we build hicrarchies of sum-product networks (SPNs) where the parameters of parent SPN are learnable transformations of the a- posterior mixing probabilities of its children's 's sum units. Due to weight sharing and the tree-shaped computation graphs of GSPNs, obtain the efficiency and efficacy of deep graph networks with the additional advantages of a probabilistic model. We show the model's competitiveness on scarce supervision scenarios, under missing data, and for graph classification in comparison to popular neural models. We complement the experiments with qualitative analyses on hyper- parae--prrmeters and the model's 's ability to answer probabilistic queries.
INTRODUCTION
As the machine learning field advances towards highly effective models for language, vision, and applications in the sciences and engineering, many practical challenges stand in the way of widespread adoption. Overconfident predictions are hard trust and most current models are not able to provide uncertainty estimates of their predictions (Pearl 2009 Hüllermeier & Waegeman 2021 Mena et al., 2021). Capturing such functionality requires the ability to efficiently answer probabilistic queries, e.g.. computing the likelihood or marginals and, therefore, learning tractable distributions (Choi) ctt al. 2020). Such capabilities would not only increase the trustworthiness of learning systems but also allow us to naturally cope with missing information in the input through marginalization. avoiding the use of ad-hoc imputation methods; this is another desideratum in applications where data (labels and attributes) is often incomplete (Dempster al. 1977 Zio al. 2007). In numerous application domains, obtaining labeled data is expensive, and while large unlabeled data sets might be available, this does imply the availability of ground-truth labels. This is the case, for instance, in the medical domains (Tajbakhsh et al. 2020) where the labeling process must comply with privacy regulations and in the chemical domain where one gathers target labels via costly simulations or in-vitro experiments (Hao et al. 2020).
In this work, we are interested in data represented graph. Graphs are a useful representational paradigm in a large number of scientific disciplines such as chemistry and biology. The field of Graph Representation Learning (GRL) concerned with the design of learning approaches that directly model the structural dependencies inherent in graphs (Bronstein et al. 2017: Hamilton et al.) 2017b) Zhang et al. 20T8b Wu et al.] 2020 Bacciu et al. (020b)). The majority of GRL. methods implicitly induce computational directed acyclic graph (DAG) for each vertex in the input graph, alternating learnable message passing and aggregation steps (Gilmer et al. 2017 Bacciu et al. (2020b). Most of these approaches exclusively rely neural network components in these computation graphs, but cannot answer probabilistic queries nor exploit the vast amount of unlabeled data.
Motivated by these considerations, we propose class of hierarchical probabilistic models for graphs called GSPNs, which can tractably answer a class of probabilistic queries of interest and whose computation graphs are also DAGs. While GSPNs are computationally efficient Deep Graph

---

Published as a conference paper at ICLR 2024
Networks (DGNs), they consist of hierarchy of interconnected Sum-Product Networks (SPNs) Poon & Domingos (2 GSPNs can properly marginalize out missing data in graphs and answer probabilistic queries that indicate change in likelihood under variations of vertex attribute values. The learned probabilistic graph representations are also competitive with state-of-the-ard deep graph networks in the scarce supervision and graph classification settings. Overall, provide evidence that it is possible to build a tractable family of SPNs to tackle learning problems defined on complex, non-Euclidean domains as compositions of simpler ones.
2 RELATED WORK
Unsupervised learning for graphs is under-explored relative to the large body of work on supervised graph representation learning (Scarselli et al., 2009) Michelli 2009; Niepert et al. [2016] Kipf &
Welling 2017; Velickovic et al. 2018]XX et al. 2019 Ying et al. (021) Contrary to self supe-suued
pre-training (Hu al. 2020b) which investigates ad-hoc learning objectives, unsupervised learning encompasses broader class of models that extract patterns from unlabeled data. Most unsupervised approaches for graphs currently rely on i) auto-encoders, such as the Graph Auto-Encoder (GAE) (Kipf & Welling 2016) and ii) contrastive learning, with Deep Graph Infomax (DGI) (Velickovic (et (019)) adapting ideas from computer vision and information theory to graph graph-structured data. While the former learns reconstruct edges, the latter compares the input graph against its corrupted version and learns to produce different representations.
Existing probabilistic approaches to unsupervised deep learning on graphs often deal with clustering and Probability Density Estimation (PDE) problems; a classic example is the Gaussian Mixture Model (GMM) [Bishop| 2006) capturing multi-modal distributions of Euclidean data. The field of Statistical Relational Learning (SRL) considers domains where we require both uncertainty and complex relations; ideas from SRL have recently led new variational frameworks for (un-)supervised vertex classification (Qu et al., 2019). Other works (Zheng et al. 2018) decompose the original graph into sub- sub-graphs that are isomorphic to pre-defined templates solve node-classification tasks. The Contextual Graph Markov Model (CGMM) (Bacciu et al. 2020a) and its variants (Atzeni et al., 202T CCastellana al. 2022) are unsupervised DGNs trained incrementally, i.e., layer after layer, which have been successfully applied to graph classification tasks. Their incremental training grants closed-form learning equations at each layer, but it comes at the price of no global cooperation towards the optimization of the learning objective, i.e., the likelihood of the data; this makes it impractical for answering missing data queries.
So far, the literature on missing data in graphs i.e., using the graph structure to handle missing attribute values, has not received as much attention as other problems. Recent work focuses on mitigating "missingness" in vertex classification tasks (Rossi al. 2022) or representing missing information as a learned vector of parameters (Malone et al. 1,, but the quality of the learned data distribution has not been discussed so far (to the best of our knowledge). There are some attempts at imputing vertex attributes through GMM (Taguchi et al. 202I). but such a process does not take into account the available graph structure. Similarly, other proposals (Chen et al.) 2022) deal with the imputation of vertices having either all or none of their attributes missing, rather unrealistic assumption for most cases. In this work, we propose an approach that captures the data distribution under missing vertex attribute values and requires no imputation.
BACKGROUND
We define a graph g as a triple EY), where V= {I,.... N) denotes the set of N vertices, is the set of directed edges (u, v) connecting vertex to v, and X' {x,, E Rd, Rd,d E N, Vu E V) represents the the set of vertex attributes. When an edge is undirected, it is trasformed into two opposite directed edges (Bacciu et al. 2020b). In this work, we do not consider edge attributes. The neighborhood of a vertex e is the set N, = [u E V (u, v) E E}. Also, access to the i-th component of vector æ shall be denoted by (i) and that of function f's output as f(-);.
Graph Representation Learning Learning graph-structured data typically means that one seeks a mapping from an input graph to vertex embeddings (Frasconi et al., 1998), and such a mapping should be able to deal with graphs of varying topology. In general, vertex v's representation is
2

---

Published as a conference paper at ICLR 2024
SPN
X/
whi
fr (AQ.Ag)
L=1
SPN
X--Ia
L-9
Figure 1: Inference on the graphical model on the left is typically unfeasible due to the mutual dependencies induced by cycles. Therefore, approximate the learning problem using probabilistic computational trees of height L modeled by hierarchy of tractable SPNs (right). Note that trees of height L 1 are used in the construction process of trees of height L. Also, for each tree rooted at we visualize the mapping (-)()) using colors and indices corresponding to the original graph (left).
vector hy E RC, C E N encoding information about the vertex and its neighboring context, so that predictions about o can be then made by feeding h. into a classical ML predictor. In graph classification or regression, instead, these vertex representations have to be globally aggregated using permutation invariant operators such as the sum or mean, resulting in a single representation hg E R of the entire graph that is used by the subsequent predictor. At the time of this writing, message- passing neural networks (MPNN) (Gilmer et al. 2017) are the most popular class of methods to compute vertex representations. These methods adopt local and iterative processing of information, in which each vertex repeatedly receives messages from its incoming connections, aggregates these messages, and sends new messages along the outgoing edges. Researchers have developed several variants of this scheme, starting from the two pioneering methods: the recurrent Graph Neural Network (GNN) of Scarselli et al. (2009) and the feedforward Neural Network for Graphs (NN4G) Micheli (2009).
Tractable Probabilistic Models Probabilistic Circuits (PCs) are probabilistic models that can tractably, i.e. with polynomial complexity in the size of the circuit, answer large class of probabilistic queries (Choi al.] (2020) and can be trained via backpropagation. A PC is usually composed of distribution units, representing distributions over one or more random variables, product units computing the fully factorized joint distribution of its children, and the sum unīts encoding mixtures of the children's distributions.
-rn-Prrduct Networks (SPNs) (Poon & Domingos 2011 Gens
& Domingos 2012 Trapp et al., 2019 Shao et al., 2020) are a special class of PCs that support tractable computation of joint, marginal, and conditional distributions, which we will exploit to easily handle missing data. Informally, a (locally normalized) SPN is a probabilistic model defined via a rooted computational DAG, whose parameters of every unit add up 1 (Vergari al., 2019a). Furthermore, the scope of an SPN is the set of its distribution units, and valid SPNs represent proper distributions. For instance, GMM and Naïve Bayes model (NB) (Webb al. 2010) can both be written as SPNs with a single sum unit. While the class of PCs is equivalent to that of deep mixture models, where each sum unit is associated with some latent variable (Peharz al.) 2016). PCs are not probabilistic graphical models (PGMs) (Koller & Friedman] 2009): the former specify an operational semantics describing how compute probabilities, whereas the representational semantics of the latter specifies the conditional independence of the variables involved. Crucially, for valid SPNs and an arbitrary sum unit j with C children, is always possible to tractably compute posterior distribution, parametrized by the vector h E RC (Peharz et al.) 2016). Here, we are voluntarily abusing the notation because in the following we will consider posterior distributions sum nodes our latent representations. Due space constraints, provide more detailed introduction to PCs in Section A.I
GSPN: LEARNING TRACTABLE PROBABILISTIC GRAPH REPRESENTATIONS
When one considers a cyclic graphical model such as the one on the left-hand of Figure I probabilistic inference is computationally infeasible unless we make specific assumptions to break
3

---

Published as a conference paper at ICLR 2024
the mutual dependencies between the random variables (x..)) Q. depicted as white circles. To address this issue, we approximate the intractable joint probability distribution over the E.V. attributed graph of any shape as products of tractable conditional distributions, one for each vertex in the graph; this approximation is known as the pseudo likelihood (Gong & Samaniego 1981, Liang & Yu 2003). The scope of these tractable distributions consists of the I.-hop neighhorhoods induced by a traversal of the graph rooted at said vertex. Akin to what done for DGNs, the parameters of the conditional distributions are shared across vertices.
We propose class of models whose ability to tractably answer queries stems from a hierarchical composition of sum-produce networks (SPNs). To describe the construction of this hierarchical model we consider, for each vertex in the input graph, a tree rooted at e of height L. that is the length of the longest downward path to leaf from v, treated as a hyper-parameter Analogously, an internal node in the tree is said to have height 0 < L S T.. To distinguish between graphs and trees, we use the terms vertices for the graphs and nodes for the trees. Moreover, because graph cycles induce repetitions in the computational trees, we have to use new indexing system: given tree rooted at with T. nodes T = {[n1...., Rr, J. we denote by m.(+) : T + V a mapping from its node index n to vertex in the input graph g.
We now formally define the tree of height L rooted at vertex v as follows. First, we have one root node with my (n) we have that a node n' is a child of n with height e - if and only if vertex v' = (n'))) is in the 1-hop neighborhood of vertex u (n). When vertex u does not have incoming edges, we model it as a Icaf node of the tree. Finally, every node n at height & = 0 is leaf node and has no children. Figure I| (center) depicts examples of trees induced by the nodes of the graph on the left.
and having height L. Second, for a node in the tree at height 1 < & & L,
We use the structure of each graph-induced tree as a blueprint to create a hierarchy of normalized SPNs, where all SPNs have the same internal structure. Every node of a tree is associated with a valid SPN whose scope consists of the random variables .I.... Aa modeling the vertex attributes, meaning the distribution units of said SPN are tractable distributions for the variable X = (AI..., Aa). To distinguish between the various distributions for the r.v. X modeled by the SPNs at different nodes, we introduce for every node n and every height L, the r.V. X with realization Øm((n) Crucially, these E.v. are fundamentally different even though they might have the same realization of the m. for root node. This is because each node of the tree encodes the contextual information of a vertex after a specific number of message passing steps.
The parameters of the tractable distribution units in the SPN of node n at height & are denoted by w', which are shared across the nodes the same height. Moreover, the mixture probabilities of the S sum nodes in the SPN of node n at height E are denoted by و 1 S j < S. To obtain a hierarchical model, that is, to connect the SPNs according to the tree structure, we proceed as follows. For every SPN of a non-leaf node n, the parameters Th of sum unit j are learnable transformations of the posterior probabilities of the (latent mixture component variables of) sum units j in the children SPNs. More formally, let mi,..., Nr be the children of a node n and let h h be the vector of posterior probabilities of sum unit j for the SPN of node ng. Then, وम. foş (h f-1 mi...........................m.. h h
with learnable parameters 0f shared across level f. The choice of f does not depend on the specific SPN template, but has be permutation invariant because it acts as the neighborhood aggregation function of message-passing passing methods. The parameters of the sum units of leaf nodes, T.. are learnable and shared. Figure [ (right) illustrates the hierarchical composition of SPNs according to tree in Figure | (center). Moreover, Figure 2 iillustrates how the prior distribution of the SPNs at height parametrized by a learnable transformation of posterior mixture probabilities of its children SPNs, similar to what is done by Vergari et al. (2019b) with fixed Dirichlet priors.
A graph g in the training data specifies (partial) evidence a, for every one of its vertices v. The hierarchical SPN generated for u now defines tractable probability distribution for the root node conditioned on the (partial) evidence for its intermediate nodes, which we can compute by evaluating the hierarchical SPNs tree in a bottom-up up fashion. For each vertex in the graph g. let n2,.... nr, be the nodes of the graph-inducee tree rooted at e, without the root node n1 itself. For each graph in the dataset, the objective is maximize the following pseudo likeeihhhoodd:
log II VEV
Pe Pa (m)))))) (ma((na):-. ...; (nr, 1);
(1)
4

---

Published as a conference paper at ICLR 2024
SPN
P.(Q
p(x] mxxa)
PL(XIQ)
A
A
(A5, A
A
(2(0)
Q
A
A
A
A
A
Ani
12-40
Pu
- ay
Figure 2: (Left) We expand the example of Figure illustrate how the prior distribution of the top SPN (here the Naive Bayes on the right) is parametrized by a learnable transformation of the children's SPNs posterior mixture probabilities. (Right) A Gaussian Naive Bayes graphical model with X A2) and its equivalent SPN with scope A2}.
where Pe is the conditional probability defined by the hierarchical SPN for the tree rooted at v with parameters ④ When clear from the context, in the following omit the subscript v from m.(.).
4.1 NAIVE BAYES GSPNS
An instance of the proposed framework uses Naïve Bayes models as base SPNs, shown in Figure in both their graphical and SPN representations for two continuous vertex attributes. For each SPN. there is a single categorical latent Ev. Q with C' possible states. Let us denote this latent Ev. for node height in the tree as Q and its prior distribution as P (Q.). Due to the assumption that all r.s.S. X have tractable distributions, we have, for all É, n and i, that the conditional distribution Pag. (X, Qh is tractable. Moreover, for each child node n at height we have that
A (i) P( = i X = Fm(())-
(2)
For each leaf n of a tree, the posterior probabilities for the SPNs sum unit are given by
(2 1 = Pr ( (Qa =
(1) P(Q. x Im((n))
Eg Pag (#m(n) Q% Prg (Q% =
where = is learned and shared across leaf nodes. For l 2 the latent priors Px4 (0%) are parametrized by the output of a learnable transformation of the posterior probabilities of the sum units of the child SPNs. More formally, for node n' at height E 1, 2 0, and with children ch we compute the prior probabilities π (+1
as
h.)(1) = Put (Im(n) ΣS Pwr, (Fm(n) 1 = 1') Prr (0 = =²)
Q = i) (Q =
2+1 = Sor+ (hf, h Mo n''
(4)
noting that the posterior h is tractable as the quantities of interest are obtained with single backward pass in the SPN (Peharz al. 2016). Figure 2 visualizes how før acts on the prior probabilities the example of Figure In the experiments,
define Tpt=i(hf... hf f Teh..] Eneck., Q h for a learnable transition matrix ge+1 E RCCC that specifies how much child's (soft) state k contributes to the weight of state in the new prior distribution +Q i). Each row k of 0 must specify valid probability over C' possible states, enforced through normalization techniques. The function is motivated by the observation that it corresponds to applying the "Switching Parent" decomposition to the conditional mixture model defined in (Bacciu et al. 2020a) (deferred to Section due to space constraints). Likewise, show in Section A.3 that Equation produces valid parametrization for the new prior distribution.
This iterative process can be efficiently implemented in the exact same way message passing is implemented in neural networks, because the computation for trees of height can be reused in trees the number of
of height é + 1. In practice, the height L of the computational tree corresponds layers classical message passing. Furthermore, our choice of fer leads to a fully probabilistic formulation and interpretation of end-to-end message passing on graphs. Motivated by studies
5

---

Published as a conference paper at ICLR 2024
the application of gradient ascent for mixture models and SPNs (Xu & Jordan 1996 Sharir et al.) Peharz et al. 2016; Gepperth & Pfülb (02T), 1, we maximize Equation | with backpropagation. We can execute all probabilistic operations on GPU to speed up the computation, whose overall complexity is linear in the number of edges as in most DGNs. For the interested reader, Section [A.4 describes how GSPN can be applied to more general SPNs with multiple sum units and provides the pseudocode for the general inference phase; similarly, Section A.5 proposes a probabilistic shortcut mechanism akin residual connections (Srivastava et al.) | al. 2016) in neural networks that mitigates the classical issues of training very deep networks via backpropagation. Finally, we refer the unsupervised version of GSPN as GSPNy.
4.2 MODELING MISSING DATA
With GSPNs can deal with partial evidence of the graph, missing attribute values, in probabilistic manner. This is a distinctive characteristic of our proposal compared to previous probabilistic methods for vectors, as GSPNs can tractably answer probabilistic queries on graphs by also leveraging their structural information. Similarly, typical neural message passing models deal with missing data by imputing its values before processing the graph (Taguchi et al. (202I). whereas GSPN takes the partial evidence into account while processing the graph structure. We take inspiration from the EM algorithm for missing data (Hunt & Jorgensen 2003): in particular, let us consider a multivariate E.V. of root node X (dropping other indices for ease of notation) as tuple of observed and missing sets of variables, i.e., X =(x obs
X X When computing the posterior probabilities of sum nodes h, we have modify Equations 3 and 4 to only account for X Xbbs; in SPNs, this equals to setting the distribution units of the missing attributes to when computing marginals, causing the missing variables to be marginalized out. This can be computed efficiently due to the decomposabilityy property of the SPNs used this work (Darwiche) 2003). Additionally, if we wanted to impute missing attributes for vertex v, we could apply the conditional mean imputation formula Zio et al. (007)) to the corresponding root EV. of the tree X = (Xpbe, x which, xi = = X Of = i] (i). Hence, to impute the missing attributes of xu, we sum the (average) predictions of each mixture in the top SPN, where the mixing weights are given by the posterior distribution. The reason is that the posterior distribution carries information about our beliefs after observing Xohs.
for the specific case of NB, translates to
4.3 A GLOBAL READOUT FOR SUPERVISED LEARNING
Using similar arguments as before, we can build probabilistic and supervised extension of GSPN for graph regression and classification tasks. It is sufficient to consider new tree where the root node r is associated with the target y.W. Y and the children are all possible trees of different heights rooted at the N vertices of graph g. Then, we build an SPN for r whose sum unit j is parametrized by learnable tansformation ग = fo, (-). This function receives the set hy of outputs h",, associated with the top SPN related to the graph-induced tree of height rooted at u, for 0 < l L.L. In other words, this is equivalent to consider all vertex representations computed by a DGN at different layers. For NB models with one sum unit, given (partial) evidence 2I,..., EN
VN for all nodes, we write
C2 Σ Pw. y Q Q= -0. (Q= 1=1
Ply 21............ 2N)
i), Tr def fo(br) a Σ nEV
8² (h)))
(5)
where W, and n. are the parameters of the NB and Q is a latent categorical variable with C, states. Computing ग,, essentially corresponds to a global pooling operation, where o E RCCxCC is another transition matrix and Ω can be I (resp. the softmax function) for mean (resp. sum) global pooling. We treat the choice of ((-) as a hyper- parameter, and the resulting model is called GSPNs.
4.4 LIMITATIONS AND FUTURE DIRECTIONS
Due to the problem of modeling an inherently intractable probability distribution defined over a cyclic graph, GSPNs rely composition of locally valid SPNs to tractably answer probabilistic queries. At training time the realization of the observable z. of vertex o at the root might be conditioned on the same realization of a different observable r.v. in the tree, which is meant to capture the mutual

---

Published as a conference paper at ICLR 2024
dependency induced by cycle. To avoid conditioning the same realization, which could slightly bias the -ikulioo in some corner cases, future work might consider an alternative, albeit expensive, training scheme where, for each node and observable attribute, different computational tree is created and the internal nodes n with m()) = v are marginalized out.
From the point of view of expressiveness in distinguishing non-isomorphic graphs, past results tell us that more powerful aggregations would be possible we explored a different neighborhood aggrega- tion scheme (Xu et al., 2019). In this work, keep the neighborhood aggregation functions fa as simple as possible to get a fully probabilistic model with valid and more interpretable probabilities. Finally, GSPN currently unable model edge types, which would enable us to capture a broader class of graphs.
EXPERIMENTS
We consider three different classes of experiments as described in the next sections. Code and data to reproduce the results is available at the following link: https://github: ctm.
Scarce Supervision Akin to Erhan et al. (2010) for non-structured data, we show that unsuper- vised learning can be very helpful in the scarce supervision scenario by exploiting large amounts of unlabeled data. We select seven chemical graph regression problems, namely benzene, ethanol, naphthalene, salicylic acid, toluene, malonaldehyde and uracil (Chmiela al. 2017). using cate- gorical atom types as attributes, and oghg-molpcbu, an imbalanced multi-label classification task (Hu al., 2020a). Given the size of the datasets, perform a hold-out risk assessment procedure (90% training, 10% test) with internal hold-out model selection (using 10% of the training data for validation) and a final re-training of the selected configuration. In the case of ogbg-mode holomm,,pbba, we use the publicly available data splits. Mean Average Error (MAH) is the main evaluation metric for all chemical tasks except for oghg-molpche (Average Precision AP averaged across tasks). We first train GSPN on the whole training set to produce unsupervised vertex embeddings (obtained through a concatenation across layers), and then we a DeepSets (DS) (Zaheer et al. 2017 classifier on just 0.1% of the supervised samples using the learned embeddings (referred as GSPNU+Ds). We do not include GSPN y in the analysis because, as expected, the scarce supervision led to training instability during preliminary experiments.
We compare against two effective and well-known unsupervised models, the Graph Auto-Encoder (GAE) and Deep Graph Infomax (DGI). These models have different unsupervised objectives: the former is trained to reconstruct the adjacency matrix whereas the second is trained with a contrastive learning criterion. Comparing GSPNu, which maximizes the vertices' pseudo likelioo,ood, against these baselines will shed light on the practical usefulness of our learning strategy. In addition, we consider the GIN model (Xu al., 2019) trained exclusively on the labeled training samples as it is one of the most popular DGNs in the literature. We summarize the space of syper-parameter configurations for all models Table
Modeling the Data Distribution under Partial Evidence We analyze GSPN's ability at modeling the missing data distribution real-world datasets. For each vertex, we randomly mask proportion of the attributes given by a sample from a Gamma distribution with concentration 1.5 and rate 1/2). We do to simulate plausible scenario in which many vertices have few attributes missing and few vertices have many missing attributes. We train all models on the observed attributes only, and then we compute the negative log-likelihood of Equation (NLL) for the masked attributes understand how good each method is at modeling the missing data distribution. We apply the same evaluation, data split strategy, and datasets of the previous experiment, focusing on their 6 continuous attributes (except for ogbg-molpcha that has only categorical values).
The first baseline a simple GAUSSIAN distribution, which computes its sufficient statisties (mean and standard deviation) from the training set and then computes the NLL on the dataset. The second baseline a structure-age -agnosti Gaussian Mixture Model (GMM). which does not rely on the structure when performing imputation but can model arbitrarily complex distributions; recall that model configurations
behaves like a GMM when the number of layers is set to 1. The set of tried for each baseline is reported in Table 5
7

---

Published as a conference paper at ICLR 2024
Model
GIN
GA
DS
4 DB
Eval. Process
Sup.
Unsup + Sup. Unsup - Sup.
Unsup -> Sup.
Aloge siter change
benzeme
41.4 1: 45.6
2.00
+ 0.1
6.22
: 1.2
2.24 = 0.5
1,00
ethanol
4,00
+
7.79
78
5.35
= 3.5
3.36
malomaldehyde
8.00 5.3
5.49
1: 1.3
4.31
18
4.31
+ 1,4
0.75
maphthalene
34,9 1: 19.4
4,45
0.3
6.34
1
4.44 0.1
0.30
salicylic acid
36.7
134
233.3
173
4.5
toluene
29.6
18.0
4.83
= 0.3
9.18 0.3
4.87
= 1.4
0.25
oghg mulpcha (1) 4.12
uracil
19.7
1
0.2
387.7
3,36
0.3
13.7
3.00
10.5
4,00
0.0.5
N CEENNNNG CANNNCCOO SMILES: Nww.llini-
0.00
Table I: Mean and std results on scarce supervision tasks averaged over 10 runs, with 0.1%. The best and second- best average results are bold and underlined, respectively.
Figure 3: Relative change in vertices pscudo log-likelihood when replac- ing Cl in the SMILES with an O.
Graph Classification Among the graph classification tasks of Errica et al. (2020), we restrict our evaluation to NCII (Wale al. 2008), REDDIT-BINARY REDDIT-MULTI-SK and COLLAB (Yanardag & Vishwanathan 2015) datasets, for which leveraging the structure seems to help improv- ing the performances. The empirical setup and data splits are the same as Errica et al. (2020) and Castellana et al. (2022), from which we report previous results. The baselines we compare against are a structure-agnostic baseline (BASELINE), DGCNN (Zhang et al. 20)8a), DiffPool (Ying et al. 2018). ECC (Simonovsky & Komodakis 2017). GIN (Xu et al., 2219)) GraphSAGE (Hamilton et al. 2017a), CGMM, E-CGMM (Atzeni et al. 202T), and iCGMM (Castellana et al. 2022). CGMM can be seen connections. Table 6 shows the set of prper-parameters tried for GSPN, and Table shows that the time to compute a forward and backward pass of GSPN is comparable to GIN.
incrementally trained version of GSPN that cannot use probabilistic shortcut
RESULTS
We present quantitative and qualitative results following the structure of Section 5 For all experiments we used a server with 32 cores, 128 GBs of RAM, and Tesla-V100 GPUs with 32 GBs of memory.
Scarce Supervision In Table we report the performance of GSPN& combined with DeepSets (DS) in the searce supervision scenario. We make the following observations. First, a fully supervised model like GIN is rarely able perform competitively when trained only on a small amount of labeled data. This is not true for ogbg-molpeba, but the AP scores are also very low, possibly because of the high class imbalance in the dataset. Secondly, on the first seven chemical tasks the unsupervised embeddings learned by GAE and DGI sometimes prevent DS from converging to a stable solution. This is the case for ethanol, salicylic acid, and uracil, where the corresponding MAE is higher than those of the GIN model. GSPN is competitive with and often outperforms the alternative approaches, both in terms of mean and standard deviation, and it ranks first or second place across all tasks. These results suggest that modeling the distribution of vertex attributes conditioned on the graph is good inductive bias for learning meaningful vertex representations in the chemical domain and that exploiting a large amount of unsupervised graph data can be functional to solving downstream tasks in scarce supervision scenario.
Contrarily the other baselines, GSPN answer probabilistic queries about the graph as depicted in Figure 3 Here we replace the Chlorine (CI) atom in the SMILES of an ogbg-molpcba sample with Oxygen (O) and ask the model to compute again the pseudo log-likelihood of each vertex (Equation] D. In this case, it makes intuitive sense that the relative likelihood increases because Cl is deactivating, so is more unlikely to observe it attached to the all-carbon atom group. Being able to query the probabilistic model subject to changes in the input naturally confers a degree of interpretability and trustworthiness to the model. For the interested reader, we provide more visualizations for randomly picked samples in Section A.9
Modeling the Data Distribution under Partial Evidence We demonstrate that is beneficial to model structural dependencies with GSPN to handle missing values in Table The first observation is that modeling multimodality using a GMM already improves the NLL significantly over the unimoda GAUSSIAN baseline; though this may not seem surprising first, we stress that this result
8

---

Published as a conference paper at ICLR 2024
berzeeee
ethanol
malonaldehyde
naphihalene
salicylic acid
tolueme
uracil
GAUSSIAN
0.0
5.72 + 0.0
5.88 0.0
6.18 0.0
6.91
0.0
6.00 = 0.0
7.51 0.0
4.31
0.01
3.81
3.93
0.01
3.31 0.10
3.21
0.13
3.59
0.06
0.5
GSPNN
4.17 0.02
3.77
1 0.03
3.88 0.001
3.18 0.07
3.06
0.21
3.35 1 0.05
3.17 0.17
/
Table 2: We report the mean and std NLL under the missing data scenario, averaged over 3 runs. Symbols and M stand for "uses structure" and "captures multimodality", respectively.
NCII
REDDIT-B
REDDIT-SK
COLLAB
Raseline
69.8 = 2.2
82.2 3.0
52.2 1.5
70.2 2
1.5
DGCNN
76.4 = 1.7
87.8
49.2
1.2
712
DIRRPODI.
76.9 = 80.1
58.8
68.9
2.0
ECC
76.2 = 1.4
GIN
89.9
56.1
75.6
GRAPHSAGE
76.0 = 1.8
84.3
113 19
50.0 1 13
73.9
1.7
CGMM Ds
88.1
B-CGMM DS
78.6
1.7
80.5
1.3
53.7
= 1.0
77.5
2.3
ICGMMU4DS
77.6
91.6
21
55.6
78.9
1.7
GS
76.6 + 1.9
190.5
+ 1.1
15..3
2.0
78.1
2.5
GSPNs
177.6 + 3.0
189.7
+ 2.3
64.22
74.1 2.5
Table 3: Mcan and std results graph classification datasets. The best and second-best performances are bold and underlined, respectively. A means that GSPN improves over CGMM.
a good proxy to measure the usefulness of the selected datasets in terms of different possible values, and it establishes an upper bound for the NLL.
Across almost all datasets GSPN improves the NLL score, and we attribute this positive result to its ability to simultaneously capture both the structural dependencies and the multimodality of the data distribution. The only dataset where the GMM has better NLL is uracil, and we argue that this might be due to the independence of the node attributes from the surrounding structural information. These empirical results seem to agree with the considerations of Sections 4.2 and shed more light on research direction worthy of further investigations.
Graph Classification The last quantitative analysis concerns graph classification, whose results are reported in Table 3 As we can see, not only is GSPN competitive against consistent set of neural and probabilistic DGNs, but it also improves almost always w.r.t. CGM M, which can be seen as the layer-wiee wise counterpart of our model. In addition, the model ranks second on two out of five tasks, though there is no clear winner among all models and the average performances are not statistically significant due high variance. We also observe that here GSPN, y does not bring significant performance gains compared to GSPNu+ As mentioned in Section 4.4 we attribute the global aggregation function. We also carry out
this to the limited theoretical expressiveness qualitative analysis the impact of the number of layers, C' and CG for GSPNs (with global sum pooling) on the different datasets, to shed light on the benefits of different arper-parameters.. The results show that on NCI1 and COLLAB the performance improvement is consistent as add more layers, whereas the opposite true for the other two datasets where the performances decrease after five layers. Therefore, the selection of the best number of layers use remains a non-trivial and dataset-specific challenge. In the interest of space, we report visualization of these results in Appendix A.8
CONCLUSIONS
We have proposed Graph-Induced Sum-Product Networks, deep and fully probabilistic class of models that can tractably answer probabilistic queries on graph-structured data. GSPN is composition of locally valid SPNs that mirrors the message-passing mechanism DGNs, and works an unsupervised or supervised model depending on the problem at hand. We empirically demonstrated its efficacy across a diverse set of tasks, such as scarce supervision, modeling the data distribution under missing values, and graph prediction. Its probabilistic nature allows it to answer counterfactual queries on the graph, something that most DGNs cannot do. We hope our contribution will further bridge the gap between probabilistic and neural models for graph-structured data.

---

Published as a conference paper at ICLR 2024
REFERENCES
Daniele Atzeni, Davide Bacciu, Federico Errica, and Alessio Micheli. Modeling edge features with deep bayesian graph networks. Proceedings of the International Joint Conference on Neural Networks (LJCNN), 2021.
Davide Bacciu, Alessio Micheli, and Alessandro Sperduti. Bottom-up generative modeling of tree-structured data. In Proceedings of the 17th International Conference on Neural Information Processing (ICONIP), 2010.
Davide Bacciu, Federico Errica, and Alessio Micheli. Probabilistic learning on graphs via contextual architectures. Journal of Machine Learning Research, 21(14)):1-3, 2020a.
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 29:203-221, 9 2020b.
Christopher M Bishop. Puttern recognition and machine learning. Springer, 2006.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):25. 18-42, 2017.
Daniele Castellana, Federico Errica, Davide Bacciu, and Alessio Micheli. The infinite contextual graph Markov model. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
Xu Chen, Siheng Chen, Jiangehao Yao, Huangjie Zheng. Ya Zhang, and Ivor W. Tsang. Learning on Attribute-Missing Graphs. JEEE Transactions on Pattern Analysis and Machine Intelligence, 44 (2):740-757, 2022.
Stefan Chmiela, Alexandre Tkatchenko, Huziel E Sauceda, Igor Poltavsky, Kristof Schütt, and Klaus-Robert Müller. Machine learning of accurate energy-conserving molecular force fields. Science advances, 365)ee 2017.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. Preprint, 2020.
Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50(3):280- 1008800-3,,00 2003.
Arthur P Dempster, Nan M Laird, and Donald Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent. Why does unsupervised pre-training help deep learning? In Proceedings of the 13th International Conference Artificial Intelligence and Statistics (AISTATS), 2010.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. 8th International Conference on Learning Representations (ICLR), 2020.
Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing of data structures. IEEE Transactions on Neural Networks, 9(5):768-786, 1998.
Robert Gens and Pedro Domingos. Discriminative learning of sum-product networks. Proceedings of the 26th Conference on Neural Information Processing Systems (NeurIPS), 2012.
Alexander Gepperth and Benedikt Pfülb. Gradient-based training of gaussian mixture models for high-dimensional streaming data. Neural Processing Letters, 53(6))4331-4344, 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICMI), pp. 1263-1272, 2017.
10

---

Published as a conference paper at ICLR 2024
Gail Gong and Francisco J Samaniego. Pseudo maximum likelihood estimation: theory and applica- tions. The Annals of Statistics, pp. 861-869, 1981.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS), 2017a.
William L.. Hamilton, Rex Ying, and Jure Leskovee. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3):52-74, 20176.
Zhongkai Hao, Chengqiang Lu, Zhenya Huang, Hao Wang, Zheyuan Hu, Qi Liu, Enhong Chen, and Cheekong Lee. Asgn: An active semi-supervised graph neural network for molecular property prediction. In Proceedings of the 26th International Conference on Knowledge Discovery and Data Mining (SIGKDD, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the 29th IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Proceedings of the 34th Conference Neural Information Processing Systems (NeurlPS), 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In 8th International Conference on Learning Representations (ICIR), 2020b.
Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning, 110(3)457--56, 2021.
Lynette Hunt and Murray Jorgensen. Mixture model clustering for mixed data with missing informa- tion. Computational statistics & data analysis, 41(3-4):429-444 2003.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. In Workshop on Bayesian Deep Learning, Neural Information Processing System (NIPS), 2016.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations (ICLR), 2017.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Gang Liang and Bin Yu. Maximum pseudo likelihood estimation in network tomography. IEEE Transactions on Signal Processing, 51(8):2043-200 2003.
Brandon Malone, Alberto Garcia-Duran, and Mathias Niepert. Learning representations of missing data for predicting patient outcomes. In Workshop on Deep Learning on Graphs: Method and Applications (AAAI), 2021.
José Mena, Oriol Pujol, and Jordi Vitrià. A survey on uncertainty estimation in deep learning classification systems from bayesian perspective. ACM Computing Surveys (CSUR), 54(9):1-35, 2021.
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498-511 2009.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In Proceedings of the 33th International Conference on Machine Learning (ICML), 2016.
Judea Pearl. Causality. Cambridge university press, 2009.
Robert Peharz, Robert Gens, Franz Pernkoff, and Pedro Domingos. On the latent variable interpreta- tion sum- product networks. IEEE transactions on pattern analysis and machine intelligence, 39 (10):2030-2044, 2016.
11

---

Published as a conference paper at ICLR 2024
Hoifung Poon and Pedro Domingos. Sum-produce networks: A new deep architecture. In IEEE International Conference on Computer Vision (ICCV), Workshops, pp. 889-690. IEEE, 2011.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov Neural Networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
Emanuele Rossi, Henry Kenlay, Maria I. Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features. In Proceedings of the 1st Learning on Graphs Conference (LoG), 2022.
Lawrence K Saul and Michael I Jordan. Mixed memory Markov models: Decomposing complex stochastic processes as mixtures of simpler ones. Machine Learning, 37(1):75-87, 1999.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Newral Networks, 20(1):61-80, 2009.
Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Thomas Liebig, and Kristian Kersting. Conditional sum-product networks: Imposing structure on deep probabilistic architectures. In Proceedings of the 9th International Conference on Probabilistic Graphical Models (PGM), 2020.
Or Sharir, Ronen Tamari, Nadav Cohen, and Amnon Shashua. Tensorial mixture models. arXiv preprint arXiv:1610.04166 2016.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters convolutional neural networks on graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway networks. In Deep Learning Workshop, 32nd International Conference on Machine Learning (ICML), 2015.
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph Convolutional Networks for Graphs Con- taining Missing Features. Future Generation Computer Systems, 117:155-168, April 2021. ISSN 0167739X. doi: 10.
1.016.
22007 2007
04583
Nima Tajbakhsh, Laura Jeyaseelan, Qian Li, Jeffrey N Chiang, Zhihao Wu, and Xiaowei Ding. Embracing imperfect datasets: A review of deep learning solutions for medical image segmentation. Medical Image Analysis, 63:101693, 2020.
Martin Trapp, Robert Peharz, Hong Ge, Franz Pernkopf, and Zoubin Ghahramani. Bayesian learning of sum-product networks. Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations (ICLR), 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep Graph Infomax. In 7th International Conference on Learning Representations (ICLR). New Orleans, LA, USA, May 6-9, 2019, 2019.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum-product networks. Machine Learning. 108(4):551-573, 2019a.
Antonio Vergari, Alejandro Molina. Robert Peharz, Zoubin Ghahramani, Kristian Kersting, and Isabel Valera. Automatic bayesian density analysis. In Proceedings of the 33rd AAAI Conference Artificial Intelligence (AAAI), pp. 5207-5215, 2019b.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):3473355, 2008.
12

---

Published as a conference paper at ICLR 2024
Geoffrey Webb, Eamonn Keogh, and Risto Mikkulainenn. Naive bayes. Encyclopedia of machine learning, 15:713-714, 2010.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? 7th International Conference on Learning Representations (ICLR), 2019.
Lei Xu and Michael Jordan. On convergence properties of the em algorithm for gaussian mixtures. Neural computation, 6()):129-151, 1996.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings the 2/th International Conference on Knowledge Discovery and Data Mining (SIGKDD, 2015.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS), 2021.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Proceedings of the 32nd Conference Neural Information Processing Systems (NeurIPS), 2018.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Proceedings of the 31 Conference on Neural Information Processing Systems (NIPS), 2017.
Muhan Zhang. Zhicheng Cui, Marion Neumann, and Yixin Chen, An end-to-end deep learning architecture for graph classification. In Proceedings of the 32nd AAAI Conference Artificial Intelligence (AAAI), 2018a.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. arXiv preprint arXiv: 1812.04222 2018b.
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 (AAAI), 2018
Marco Di Zio, Ugo Guarnera, and Orietta Luzi. Imputation through finite gaussian mixture models. Computational Statistics and Data Analysis, 51(11):5305-531 2007. doi: 10.10166f.csdaa2000 10.002.
13

---

smooth and decomposable Published as a conference paper at ICLR 2024
A APPENDIX
We complement the discussion with theoretical and practical considerations that facilitate understand- ing and reprodueibility.
A.1 HIGH-LEVEL. DEFINITIONS OF PROBABILISTIC CIRCUITS
We introduce basic concepts of PCs to ease the understanding of readers that are less familiar with this topic.
A probabilistic circuit (Choi et al. 2020) over set of r.s. X = (Ai..... Ad) is uniquely determined by its circuit structure and computes (possibly unnormalized) distribution P(X). The circuit structure has the form of rooted DAG, which comprises a set of computational units. In particular, input units are those for which the set of incoming edges is empty (i.e., no children), whereas the output unit has no outgoing edges.
The scope of a PC is a function that associates each unit of the circuit with a subset of X. For each non-input unit, the scope of the unit is the union of the scope of the children. It follows that the scope of the root is X.
Each input (or distribution) unit encodes parametric non-negative function, e.g., a Gaussian or Categorical distribution. A product unit represents the joint, fully factorized distribution between the distributions encoded by its children. Finally, sum unit defines weighted sum of the children's s distributions, i.e., a mixture model when the children encode proper distributions. The set of parameters of probabilistic circuit is given by the union of the parameters of all input and sum units in the circuit.
There are different kinds of probabilistic queries that PC answer. The first is the complete evidence query, corresponding to the computation of P(X = æ). A single feedforward pass from the input units to the output unit is sufficient to compute this query. Another important class of queries is that of marginals, where we assume that not all r.V.S are fully observed, e.g., missing values. Given partial evidence C X and the unobserved variables Z X E, a marginal query is defined as P(E = e) p(e, ddz. Finally, we mention the conditional query, sharing the same complexity as the marginal, where we compute the conditional probability P(Q q E e) of a subset of r.s. Q C X conditioned on partial evidence E and Z X X (E QQ).
To be able to tractably compute the above queries, one usually wants the PC to have specific structural properties that guarantee linear time complexity for marginal and conditional queries. A product unit is said to be decompesable when the scopes of its children are disjoint, and a PC decomposable if all its product units are decomposable. Instead, sum unit is smooth if all its children have identical scopes, and a PC is smooth (or complete (Poon & Domingos 2011 1 if all its sum units are smooth. For instance, the NB model considered in our work is implemented PC.
A PC that is smooth and decomposable can tractably compute marginals and conditional queries (one can prove that these are necessary and sufficient conditions for tractable computations of these queries), and we call such SPNs valid. A generalization of decomposability. namely consistency. is necessary to tractably compute maximum a posteriori queries of the form arg maxq P(Q q, E =)..
PCs have an interpretation in terms of latent variable models (Peharz al. 2016), and in particular
it is possible to augment PCs with specialized input units that mirror the latent variables of the associated graphical model. However, it is not immediate at all to see that valid SPNs allow tractable computation of the posterior probabilities for the sum units, and we indeed refer the reader to works the literature that formally prove it. stated (Poon& & Domingos, 2011 Peharz et al.. 2016), inference in unconstrained SPNs is generally intractable, but when an SPN is valid efficient inference is possible. Concretely, one can get all the required statistics for computing the posterior probabilities h; of any sum unit in a single backpropagation pass across the SPN (Equation 22 of Peharz et al. (2016)). The posterior computation involves the use of tractable quantities and hence stays tractable. Of course, the computational costs depend the size of the SPN and might be impractical if the SPN is too large, but we still consider it tractable in terms of asymptotic time complexity.
14

---

Published as a conference paper at ICLR 2024
A.2 THE SWITCHING PARENT DECOMPOSITION
The decomposition used in Equation known as "Switching Parent" (SP) in the literature (Bacciu al. 2010), was formally introduced in (Saul & Jordan 1999) in the context of mixed memory Markov models. We report the original formulation below. Let i E {1....,P) n) denote a discrete random variable that can take on n possible values. Then we write the SP decomposition as
P(ie 11-1...... R) Σ P(u) hepp)
(6)
The connection Equation emerges by observing the following correspondences: P(μ) is treated as constant [eh.,] (i = it-p" j) implements the transition conditional probability table, which we model in "soft" version (see also (Bacciu et al. 2020a)) as 0 h and the conditional variables on the left-hand-side of the equation intuitively correspond to the information f-1 we use
to parametrize the prior (Q)) Moreover, we assume full stationarity and ignore the position of the child in the parametrization, meaning we use the same transition weights O for all neighbors; this is crucial since there is usually no consistent ordering of the vertices across different graphs, and consequently between the children in the SPN hierarchy.
A.3 PROOF THAT EQUATION IS A VALID PARAMETRIZATION
To show that the computation ग. ,e outputs valid parametrization for the categorical distribution
P
x eta (Q="") ), is sufficient to show that the parameters sum to
Σ foc he ch
Σ
cchall
i=1
nEch,
1=1
C
1
o++1 ki
h (k)
|cha'l
nech R= i=1
1
(k)
1=1, (7)
ccha'l
cchn' nEch,,
nEch
k=
where we used the fact that the rows of 0f and the posterior weights h--1 are normalized.
15

---

Published as a conference paper at ICLR 2024
A.4 DEALING WITH MORE GENERAL SPN TEMPLATES
In Section 4 we have introduced the general framework of GSPN for arbitrary SPNs, but the explicit h k and the computation of the posterior probabilities
implementation of . = Soz (h
h has only been shown for the Naive Bayes model (Section 4.1 with a single sum unit j in its "n.
corresponding SPN template. Despite that the computation of the posterior depends on the specific template used, we can still provide guidelines on how to use GSPN in the general case.
Consider any valid SPN template with S units, and w.l.o.g. we can assume that all sum units have C' different weights, i.e., each sum unit implements mixture of C distributions. Given computational tree, we consider an internal node n with T children 71...... .....,77 Rr,, and we recall that all SPNs associated with the nodes of the tree share the same template (although different parametrization). Therefore, there a one-to-one correspondence between unit, j of node n,, Vi {I, .......... T). at level é - 1 and unit of its parent at level L, mcaning that the parametrization n. E IR can be computed using a permutation invariant function such as
1 L (1......
T.o = -So (h (
(8)
that acts similarly to the neighborhood aggregation function of DGNs.
All that remains to describe how we compute the posterior probabilities hh E RC for all sum units j E (1,....S) S) of a generic node n at level (now that the reader is familiar with the notation, can abstract from the superscript l since it can be determined from n2). As discussed in Section terms of latent variable models, so we can think of sum unit j as latent random variable and we can augment the SPN make this connection explicit (Peharz et
A.1 SPNs have an interpretation
2016). Whenever the SPN is valid, the computation of the posterior probabilities of all sum units is tractable and it requires just one backpropagation pass across the augmented SPN (see Equation 22 Peharz et al. (2016)). This makes it possible to tractably compute the posterior probabilities of the sum units that will used to parametrize the corresponding sum units of the parent node the computational tree. Below we provide pseudocode summarizing the inference process for generic GSPN, but we remind the reader that the message passing procedure is equivalent to that of DGNs.
Algorithm 1 GSPN Inference on a Single Computational Tree
Input: Computational tree with T nodes and height L, valid SPN template with S sum units and C weights for each sum unit.
Output: Set of posterior probabilities [hn.j Vn E (I,...,?) T), Vj E (1,
for ........... L do
2:
for all nodes n at height do for all sum units j of SPN of node n do:
3:
4:
if é > 0 then:
5:
Compute nn. (Eq, g
> message passing, parallelized
6:
else
7:
Use learned n..
D leaf node, no children
8: end if
9:
Compute and collect Jnn.j (Equation 22 (Peharz et al. 2016 >> computation reused
across sum units
10: end for
end for
12: end for
return (hn, Vn E (I,.., e
On a separate note, when it comes to handling missing data, it is sufficient to marginalize out the missing evidence by substituting in place of the missing input units. This allows to compute any marginal or conditional query (including the computation of the posterior probabilities) in the presence of partial evidence.
16

---

Published as a conference paper at ICLR 2024
A.5 PROBABILISTIC SHORTCUT CONNECTIONS
In GSPNu, we also propose probabilistic shortcut connections to set the shared parameters wh as convex combination of those at height .w...... w For instance, for a continuous ER X of the root node modeling choice would be take the mean of the 1 Gaussians implementing the distributions, leveraging known statistical properties to obtain
( (
(of)² -
1-1
1-1
1-1
(o1)²
( 0H i) def N
w'= - of...o.............. (9)
i=1
Instead, when the r.. is categorical, we consider a newly parametrized Categorical distribution:
Pule (X 0 = def Cat (::
Σ E=1 L- w/ C-I-probabbilyy simplex Vi E [1, C1 (10)
Akin residual connections in neural networks (Srivastava et 2015 He et al. 2016). these shortcut connections mitigate the vanishing gradient and the degradation (accuracy saturation) problem, that is, the problem of more layers leading higher training error. In the experiments, treat the choice of using residual connections as weighted residual connections, to future work.
and postpone more complex design choices, such
A.6 HYPER-PARE PARAMETERS TRIED DURING MODEL SELECTION
The following tables report the cypeer-parameert tried during model selection.
Embedding Construction
avg emission
C Iatent
layers
learning rate
batch size
epochs
ES patieace
across layers
GAE
32, 128, 256
2,3.5
0.1. 0.01
1024
100
50
DGI
32. 128, 256
2,3,5
0.1. 0.01
1024
100
50
GSPN
5,10,20,40
5,10,20
0.1
1024
100
50
true, Galse
Graph Predictor
decay (MLP)
global pooling
dropout (GIN) O, 0.0001 0.5
MLP
8,16.32.64
0.01
1024
1000
500
sum,, meun
GIN
32,256.512
0.011 0.0001
8,32,128
1000
500
Table Scarce supervision experiments. We found that large batch sizes caused great instability in GIN's training, so we tried different, smaller options. DGI and GAE used the Atom Embedder of size 100 provided OGBG, whereas GSPN deals with categorical attributes through a Categorical distribution. The range of hyper- tried for GAE and DGI follows previous works.
avg emission params across layers
layers learning rate batch epochs
patience
GAUSSIAN
GMM
5.15.20.40
0.1. 0.01
32
200
50
GSPN
0.1.0.11
False
Table Missing data experiments. Gaussian mixtures of distributions are initialized with k-means on the first batch of the training set. The maximum variance at initialization is set to 10.
17

---

Published as a conference paper at ICLR 2024
Embedding Construction
C/ latent dim
layers
learning rate
hatch size
# epochs
ES parience
agg emission params
layers
GSPNg
5,10,20
5. 10, 15, 20
0,1
32
500
50
true, false
Graph Predictor
global pooling sum, mean
32,
1,,,10020
0g=32,128
sum, mean
Table 6: Graph classification experiments. The emission distribution is categorical for NCII and univariate Gaussian otherwise. Gaussian mixtures of distributions to be learned (social datasets) are initialized using k-means on the training set.
A.7 DATASETS STATISTICS
Below report the set of datasets used in our work together with their characteristics.
# graphs
# vertices
# edges
# vertex attributes
task
metric
benzene
527984
12.00
64.94
categorical + cont.
Regression(1 ()
MAE/NLL
ethanol
455093
9.00
36.00
3 (1 cat.) + 6 cont.
Regression( ()
MAE/NLL
naphthalene
226256
18,00
127.37
31 cat.) + 6 cont.
Regression(] I)
MAE/NLL
salicylic acid
220232
16.00
104.13
31 cat.) 6 cont.
Regression( 1)
MAE/NLL
toluene
342791
15.00
96.15
3 (1 cat.)
Regression( ()
MAFANLL
malonaldhyyde
893238
9.00
36.00
(1 cat.) + cont.
Regression( ()
MAE/NLL
uracil
133770
12.00
64,44
(1 cat.) + 6 cont.
Regression(1 ()
MAE/NIL
Multi-Label
ogbg-molpcba
437929
26.0
28.1
83 (9 cat.)
AP
Classification( (28)
NCII
4110
29.87
32.30
37 cat.)
Classification(()
ACC
REDDIT-B
2000
429.63
497.75
cont.
Classification
ACC
REDDIT-5K
5000
508.52
594,87
cont.
Classification(
ACC
COLLAB
5000
74.49
2457.78
cont.
Classification(3)
ACC
Table Dataset statistics.
A.8 GRAPH CLASSIFICATION EXPERIMENTS: ABLATION AND HYPER-PARAMETER STUDIES
Ablation Study The following table shows the performance GSPNG+D2 DS when removing the use shorteut connections from the ssper-paramtter space. The results show that using shortcut connections consistently leads better mean classification accuracy on these tasks.
NC11
REDDIT-B
REDDIT-5K
COLLAB
GSPNU+DS (no shortcut)
76.5
88.9 + 3.9
52.3 + 5.2
75.7 2.6
GSPNU4DS
76.6 + 1.9
90.5 + 1.1
55.3 + 2.0
78.1 2.5
Table 8: Impact of shorteut connections on the creation of unsupervised embeddings for graph
classification.
Impact of Hyper-parameters Figure 4 shows how the validation performance of GSPNg changes for specific parammerrsesterss C and Cg add more layers. Please refer to the main text for discussion.
A.9 SCARCE SUPERVISION EXPERIMENTS: ADDITIONAL VISUALIZATIONS
Figure provides a few, randomly picked examples of molecules from the ogbg-molpet dataset, modified to show the relative change in pseudo ligelikll of some of the vertices according to GSPN.
18

---

Published as a conference paper at ICLR 2024
61
voloatkn ScCuPCY
veltletenn atca
P9
20
75
20
14
20
validattin accurecy
90-
vallisation sccursty
85
45
90
32
40
32
128
128
72
30
10
14
16
20
10
14 number layers
16
20
number layers
Figure 4: Impact of GSPNs layers, C and CG on NCII (top left), COLLAB (top right), REDDIT- BINARY (bottom left), and REDDIT-5K (bottom right) performances, averaged across all configura- tions in the 10 outer folds.
Bloge sher change
alog alte sharge
075
0.50
025
ENCCON C COCCE 2EN.CCEEEE222222
0.00
SHI CNCCI-OIN www.eeeeeeCd -i
SMILES: CONLCCC@O10C-CCC O12.01112 CICC (CC--UCC--CCC OUCCCCCCcooooaa
COCCECCCCEE
bioge after change
DCCGENCCC WWW.CCCCCEEECCCCCCCCCC
SMILES: CJocccnnc decccc2le) cbccccchol1l00cccocccCeettt
SMILES: www.rooiddecccheeeeeeeeeeeee.e
Figure 5: Additional visualizations of randomly picked molecules from ogbg-molpchu for specific GSPN configuration. The heatmap shows pseudo log-likelihood variations in the vertices when operating specific atomic changes (from left right). Nearby atoms affected by the change as well, and this allows us to understand which groups are more common, or make more sense, than others.
19

---

Published as a conference paper at ICLR 2024
A.10 TIME COMPARISON
Table 9 shows the time comparison of forward and backward passes on a batch of size 32 between GSPN and GIN. We used 10 layers for both architectures and adapted the hidden dimensions obtain a comparable number of parameters. Despite the GIN's implementation being more sample efficient than GSPN, the table confirms our claims on the asymptotic complexity of GSPN.
# parameters
forward time (ms)
backward time (ms)
GSPN
GIN
GSPN
GIN
GSPN
GIN
NCII
36876
36765
30
12
17
14
REDDIT-B
34940
35289
35
14
24
15
REDDIT-SK
34940
35289
35
14
22
15
COLLAB
34940
35289
36
21
15
Table 9: Time comparison between GSPN and GIN on graph classification tasks.
20


Reviews:
[{"review_id": "UuFbxEbVEI", "reviewer": "Reviewer_ReHv", "summary": "While sum-product networks have been well-studied and proven to be efficient in tractable learning and answering probabilistic queries, all previous studies focus on data in the standard forms (e.g. numerical values or discrete classes). However, it has not been well-studied for graph representation learning and related areas. This paper introduces a new probabilistic framework Graph-Induced Sum-Product Networks (GSPNs), which achieves efficiency and efficacy by utilizing hierarchies of SPNs that allow transferable parameters. Extensive experiments are conducted to analyze the role of hyper-parameters and the model's ability to answer probabilisitic queries.", "questions": "1. Please refer to the second paragraph in the weakness section in case I missed any substantial theoretical justifications.\n\n2. For Equation 1 on page 4, what exactly is the function $m_v(\\cdot)$? Also, since $n_1$ is the root, it makes sense so that all other nodes are conditioned. However, when we infer other nodes, e.g. $m_v(n_2)$, do we try to optimize $\\log \\prod_{v \\in V} P_{\\Theta} (x_{m_v(n_2)} | x_{m_v(n_2)}, \\cdots ) $?\n\n3. In Section 4.2, how is the equation $x_v^{mis} = \\sum_{i}^{C} \\mathbb{E} [X_1^{mis} | Q_1^L = i] \\times h_1^L(i) $ derived?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies an interesting and important problem, which is probabilistic queries for graph learning. Like standard sum-product networks, GSPNs can properly marginalize out missing data in graphs and provide more interpretability, in contrast to deep graph neural networks.\n\nThe construction of the networks (page 4 to 6) is detailed, and the hierarchical relationship is well-described. The optimization objective (Equation 1) is expected.\n\nSection 4.2 emphasizes a major advantage of GSPNs, or probabilistic circuits in general, which is the ability to infer with incomplete data. The content in the section also provides the justifications on why certain operations are chosen (summing the average predictions of each mixture in the top SPN).", "weaknesses": "The writing of the beginning of Chapter 4 and Section 4.1 could be improved to a reasonable extent. The construction of the tree is highly technical and such a compact text makes the understanding difficult. The authors may consider the following two improvements: 1) write the process in a more rigorous way like a mathematics or TCS paper, i.e. formal definitions of the function $m(\\cdot)$ and the heights $\\ell$ of the tree; 2) add more figures to illustrate the construction process.\n\nThe subject of sum-product networks has a rich theoretical background, while this paper has little theoretical justifications, unless I missed anything. Many operations (such as the construction of the tree, transforming parameters, and summing top SPNs for inference with incomplete data in Section 4.2) are only justified in the hand-wavy way. Although ML is a highly empirical subject, probabilistic circuits are involved for interpretable inference and therefore, a reasonable amount of theoretical justifications may be necessary.", "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": "nrcyJAIUsJ", "reviewer": "Reviewer_KgLo", "summary": "The paper suggests a framework for using Sum-Product Networks (SPNs) as Deep Graph Networks (DGNs). That is, the framework establish methods for representing a computation graph, such as the ones used in neural network architectures, as an SPN. The practical motivations for the work comes from DGNs, in general: (i) having overconfident predictions due to lack of uncertainty consideration, (ii) ad-hoc imputation method of missing data due to lack of probabilistic queries.\nThe authors suggest solving these issues by representing a DGN as a hierarchy of interconnected SPN and, therefore, being capable of answering probabilistic queries in a tractable manner.", "questions": "* How do imputation methods compare with the formal way of dealing with missing data through probabilistic inference?\n* Could you comment on the empirical convergence of the model? Was the model susceptible to variations on parameter initialization? And how did hyper-parameters were tuned?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "* Tractable inference in DGNs: the tractable assumption over input distributions and SPN graphical properties enforcement allows for tractable probabilistic inference. This feature allows for a sound way of dealing with missing data.\n* Probabilistic modeling of distributions over vertexes is beneficial in some specific applications, as it seems to be the case in the chemical domain. These are encouraging results for graph-based solutions in downstream tasks.\n* Throughout and convincing experiments while exploiting well-established deep learning techniques such as residual connections.", "weaknesses": "* The manuscript would benefit from a theoretical discussion on the implications of generating tree SPNs from induced graphs, for instance, when capturing cyclic information.\n* The paper does a good job motivating the work from the DGN perspective by bringing tractable probabilistic inference capabilities. However, the manuscript's relevance could be improved by highlighting the other way around: novel theoretical results to SPNs.\n* Please fix the \"Scarce Supervision\" paragraph under Section 6: it currently contains a \"Lorem ipsum\" placeholder.", "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": "NWDteP3gMY", "reviewer": "Reviewer_GF8k", "summary": "The paper suggests utilizing tractable probabilistic models (TPMs) in graph representation learning. More precisely, the proposed graph-induced sum-product networks (GSPNs) are a class of hierarchies of sum-product networks (SPNs) that are capable of answering many types of probabilistic queries in a polynomial time in the size of the model. Further, the authors show that GSPNs are capable of dealing with missing data in the graph. The theoretical results are complemented by empirical experiments, where the authors show that are GSPNs are competitive on the tasks of scarce supervision, modeling data distributions with missing values, and graph classification.", "questions": "If I understood correctly, a small height L of the trees for graphs with a large diameter (consider, e.g., an n-cycle) would result in the trees containing only few of the vertices of the graph. On the other hand, a large L leads to an exponential blowup in the size of the trees, which is computationally infeasible. Is having the trees contain only few of the vertices of the graph detrimental, and if yes, then how harmful is it?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I was unable to grasp every detail of the paper due to my limited knowledge of some of the topics, so please take my review with a grain of salt.\n\nThe main contribution of the paper is introducing the GSPN framework on the active area of graph representation learning with the following important properties:\n- Efficiently computable probabilistic queries\n- The ability to deal with missing data\n- The ability to approximate the joint distribution over the random variables, where the graph can have arbitrary structure\n\nFurther, the empirical experiments demonstrate that the proposed class of structures is not only theoretically interesting but also in practice.", "weaknesses": "The paper could be more polished:\n- As per formatting instructions, the citations should be in parenthesis when they are not part of a sentence.\n- \"The neighborhood of a vertex $v$ is the set $N_v = \\lbrace u \\in V | (u, v) \\in E\\rbrace$ of incoming edges\": the neighborhood is not a set of edges but vertices.\n- Section 6 starts with a lorem ipsum paragraph", "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)