
SPN Frequently Asked Questions
 Can you convert between SPNs and graphical models?

Yes, any graphical model can be represented by an SPN. The naive approach is to create a root sum node with a child product node over the factors for each possible joint state of the variables. A better way is to construct a junction tree from the graphical model and then translate this to an SPN.
The benefit of SPNs is not that they somehow make existing GMs tractable; if a graphical model requires approximate inference, then it will translate to a very large SPN.
What's special about SPNs is that they can perform fast inference on hightreewidth dependencies. These hightreewidth SPNs cannot be represented by GMs. The following diagram may be helpful:
Compactlyrepresentable probability distributions:
 GM  GMs with hightreewidth require approximate inference. Converting these GMs results in very large SPNs (not compactly representable).
 GM ∪ SPN  Existing tractable models typically have low treewidth (e.g., thin junction trees, HMMs).
 SPN  These are hightreewidth SPNs with fast, exact inference. Converting them to GMs often yields complete cliques (not compactly representable).
 How do you create an SPN from a junction tree?

If R is the root of the junction tree, run BuildSPN(R, {})
BuildSPN(Cluster C, Evidence e):
If key (C, e) exists in M, return M(C, e)
Create sum node S
For each joint state x of variables X = (Va(C) \ e):
Create product node P
For each variable setting v in x:
Create univariate distribution with mass on v as child of P
Set w to be the product of all factors in C with state (x ∪ e)
For each child C' of C:
Add BuildSPN(C', (x ∪ e) ∩ Sepset(C, C')) as child of P
Add P as child of S with edgeweight w
Store (C, e) → S in map M
Return S
Va(C) denotes the variables in cluster C
M is a map that caches solutions.
Key is clusterevidence pair, and value is an SPN node.
Sepset(C,C') is the set of variables in the sepset between clusters C and C'.
Bold denotes a vector.
 If you convert a graphical model to an SPN, is it just a single product layer that computes the product of all the factors?
No. There is a big difference between the productoffactors description of a GM and the graph of computations in an SPN. An SPN represents all possible inference queries (computable in linear time) whereas the factorization of a GM only tells us the (unnormalized) probability of a complete state. To perform inference on a graphical model, we put an outer summation around the productoffactors. With most graphical models, we can "push" the summation of certain variables to cover a smaller set of factors. This means that a corresponding SPN will not be "flat" (root sum over a product of factors for each variable state) and will have multiple layers that leverage the distributive law. While there are some intractable GMs that would translate to flat or otherwise unwieldy SPNs, this is just a reflection of the computations required to perform inference on a model described by conditional independencies.
 Are SPNs just trees?
No; in general they are directed acyclic graphs. See the experiments in Poon & Domingos 2011 for an example architecture.
 What are the drawbacks of treestructured SPNs? Are they similar to treestructured graphical models?
A treestructured SPN has the same representational power as an SPN that is a DAG. The advantage of a DAG SPN is that it reuses computation, which requires fewer nodes and results in faster inference. A treestructured SPN can represent hightreewidth dependencies that would result in a complete clique if converted to a GM. A treestructured GM is limited to representing lowtreewidth dependencies.
 Can SPNs represent convolution?
Yes, you can use weighttying for nodes at different locations. See the experimental architecture in Gens & Domingos 2012.
 What are the drawbacks of SPNs?

It takes more effort to handdesign local independencies than global independencies. This would appear to give graphical models (GMs) an advantage, but the simplicity of a graph of variables belies the true inference and learning cost. This has motivated several papers on learning the structure of SPNs from data. Not only do these papers show that automaticallylearned SPN structure performs better than handdesigned SPNs [Dennis & Ventura 2012 ] but also that the resulting SPNs are more accurate and orders of magnitude faster at inference when compared to learned Graphical Models [Gens & Domingos 2013].
