Response to Reviewer ReHv
We are grateful for the constructive feedback and the positive assessment of our work. In the following, we provide answers to the points raised, hoping that the reviewer will consider raising the final score as a consequence.
**Q:** 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() and the heights \ell of the tree; 2) add more figures to illustrate the construction process.
**A:** We agree with the writing suggestions and we tried our best to change the manuscript accordingly despite the severe space limitations. In particular, we have provided a more formal description of the height of trees and nodes that follows the classical definitions in theoretical computer science, and we better formalized the mapping from nodes of a tree to vertices in the original graph. Accordingly, and due to the impossibility of adding extra figures, we opted for highlighting the recursive construction of the computational trees in Figure 1 and explicitly referred to the mapping $m_v(\cdot)$ in the caption. Thank you for helping us improve this part.
**Q:**: The 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.
**A:** The reviewer mentions the numerous theoretical results for SPNs, and we indeed make use of these results (locally valid distributions, ability to tractably compute marginals, etc.) in our work. This sets our proposed framework apart from prior work in the graph machine learning literature which does not rely on SPNs and graphical models. What we would like to highlight, in addition, is that the design of GSPN is theoretically motivated, as it builds on architectural biases, taken from the literature, which have well-known theoretical foundations [*,**]. The objective of our current work is to propose, for the first time and to the best of our knowledge, a new class of models integrating message-passing NNs and SPNs, and not to derive new theoretical results about SPNs. We agree, however, that this is interesting future work.
### Questions:
1. Please read above.
2. Thank you for spotting this: the text was ambiguous, as it talked about the optimization of a single computational tree while Equation 1 shows how to optimize the pseudo log-likelihood for an entire graph $g$. We have corrected the text accordingly in the revised version.
3. There is no derivation involved in the equation $\textbf{x}_v^{mis} = \sum_i^C \mathbb{E}\big[\textbf{X}_1^{mis} \mid Q^{L}_1=i\big] * \textbf{h}^L_1(i)$: because the SPN of the root node is a Naive Bayes model, which is a mixture model, we just applied the conditional mean imputation strategy defined in Zio et al. (2007) for finite mixture models to our context. We have clarified this in the updated manuscript.
[*] Micheli, Alessio. "Neural network for graphs: A contextual constructive approach." IEEE Transactions on Neural Networks 20.3 (2009): 498-511.
[**] Scarselli, Franco, et al. "The graph neural network model." IEEE transactions on neural networks 20.1 (2008): 61-80.
--
We hope to have addressed the concerns of the reviewer, especially those regarding the objectives of our work. We remain available should further clarifications be needed, and we thank the reviewer again for the valuable feedback.