Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks

We thank the reviewer for highlighting the strengths of GSPNs, and for giving us actionable feedback to improve the manuscript. Below, we answer each comment or question in order.

Fixes:

• We have adjusted the citations’ style as suggested.
• We have removed the incorrect statement about the definition of the neighborhood.
• We have removed the lorem ipsum paragraph. Apologies for this.

Questions:

Q: 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?

A: The understanding of the reviewer is correct, $L$ controls the “receptive field” of each vertex akin to standard message-passing neural networks of depth $L$ (GSPN is in fact implemented as a message-passing architecture of depth $L$). Due to space reasons, we had to defer the impact of the depth for some tasks to Appendix A.8. In general, we observed that $L$ is a crucial hyper-parameter of the network that needs to be appropriately chosen for a given task. A small height $L$ might suffice in some cases (for instance the two REDDIT datasets) and not in others (for instance in NCI1 and COLLAB), where more information needs to be propagated across the graph.

--

We hope our answers have clarified the doubts of the reviewer. Thank you again for helping us improve the manuscript, and we hope that with the current modifications the reviewer will consider raising the score.

Thank you for the positive assessment of our work. Below we address the comments and questions posed by the reviewer.

Q: The manuscript would benefit from a theoretical discussion on the implications of generating tree SPNs from induced graphs, for instance, when capturing cyclic information.

A: In Section 4.4, we discuss the theoretical implications of generating a hierarchy of SPNs from cyclic graphs; in particular, the pseudo-likelihood might result in over-optimistic behavior in seriously degenerate cases (e.g., a dataset of graphs that are made of self-loops only). Note that all message-passing architectures, including GSPNs, rely on some approximation of the mutual dependencies induced by cycles in the graph.

Q: 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.

A: This is a great suggestion, thank you. We have highlighted the relevance of our contribution in terms of the SPN literature, namely how to build SPNs as the composition of simpler ones to tackle problems in more complex domains, at the end of the Introduction section.

Q: Please fix the "Scarce Supervision" paragraph under Section 6: it currently contains a "Lorem ipsum" placeholder.

A: We have fixed the placeholder, apologies about this.

Questions:

Q: How do imputation methods compare with the formal way of dealing with missing data through probabilistic inference?

A: It is possible that we did not fully understand the question. To the best of our knowledge, there is no formal way of dealing with missing data in the context of topologically varying graphs (that is, Markov Networks are not an option here). In particular, GSPN is the first proposal to model missingness while conditioning on the graph structure. Dealing with missingness without conditioning on the graph leads to a degradation of performances as reported in Table 2 (Gaussian/GMM baselines). From a more technical standpoint, the major difference compared to classical imputation methods is that we adopt classical probabilistic inference from missing data at the local level of a node in the tree, but we propose a probabilistically tractable way to propagate the information of missingness globally across the graph.

Q: 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?

A: Regarding convergence, we did observe some light instability when training with higher learning rates, meaning sudden bumps in the training curves that were quickly compensated, but that did not affect our result in the end. As discussed in Section 5 (please refer to the paper for more details), we tuned hyper-parameters automatically with a grid search, and we selected the best configuration on the validation set. Such configuration is then re-trained and eventually evaluated on the test set, which is never seen, directly or indirectly, by the model.

--

We hope to have adequately addressed the questions and concerns of the reviewer so that the final score might be increased. Many thanks again for helping us strengthen our contribution.

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 $**x**_v^{mis} = \sum_i^C \mathbb{E}\big[**X**_1^{mis} \mid Q^{L}_1=i\big] * **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.