Linear Time Computation of Moments in Sum-Product Networks
Bayesian online algorithms for Sum-Product Networks (SPNs) need to update their posterior distribution after seeing one single additional instance. To do so, they must compute moments of the model parameters under this distribution. The best existing method for computing such moments scales quadratically in the size of the SPN, although it scales linearly for trees. This unfortunate scaling makes Bayesian online algorithms prohibitively expensive, except for small or tree-structured SPNs. We propose an optimal linear-time algorithm that works even when the SPN is a general directed acyclic graph (DAG), which significantly broadens the applicability of Bayesian online algorithms for SPNs. There are three key ingredients in the design and analysis of our algorithm: 1). For each edge in the graph, we construct a linear time reduction from the moment computation problem to a joint inference problem in SPNs. 2). Using the property that each SPN computes a multilinear polynomial, we give an efficient procedure for polynomial evaluation by differentiation without expanding the network that may contain exponentially many monomials. 3). We propose a dynamic programming method to further reduce the computation of the moments of all the edges in the graph from quadratic to linear. We demonstrate the usefulness of our linear time algorithm by applying it to develop a linear time assume density filter (ADF) for SPNs.
I thank the authors for their response. As mentioned in my review, I also see the contributions of this paper on an algorithmic level. Nevertheless I would encourage the authors to at least comment on the existing empirical results to give readers a more complete picture.
--
The submitted manuscript develops a linear time algorithm for computation of moments in SPNs with general DAG structure, improving upon the quadratic time complexity of existing algorithms.
I like the contributions of this paper and I think the proposed algorithms are novel (given that the authors are the same as those of an arXiv paper from a couple of months ago) and could turn out to be useful. On the other hand, the contributions of the paper are somewhat limited. It would be beneficial to demonstrate the usefulness of the algorithms on some task like parameter estimation. In particular, it would be interesting to see whether the uncertainties that can be computed from the approximate posterior are useful in some way, e.g. to quantify uncertainty in queries etc. 
Regarding "remark 3" in lines 228-236. Given that the authors draw this close connections, the neural networks with products unit studied in the past should be mentioned. These product units are more general than the products computed in SPNs (they have tuneable parameters). 
A couple of more comments:
* Lines 251 to 254 give the impression that the stated result about moment matching in the case of exponential family distributions as approximating distributions is novel/from the authors. I found the same result in 
    Shiliang Sun, "A review of deterministic approximate inference techniques for Bayesian machine learning", 2013
and expect there are even older similar results.
* There seems to be an arXiv version of the same paper which I have seen some time ago that goes beyond the submitted paper, e.g. it includes experiments. In these experiments, the method proposed in this paper do "only" compare favourably to other methods in terms of runtime, but not in terms of model fit. That is ok, as I see the contribution of this paper on a different level. However, as these results are known, I feel that they should have been mentioned somewhere (could have been anonymous).