Graph Parsing Networks

Thank you for the thoughtful feedback on our manuscript. We provide the following detailed responses to your major concerns.

(Weakness 1) Time complexity. Though the paragraph above Proposition 4 claims that the time complexity of each pooling layer is $O(n^{(k)})$, the computation of edge score $C$ still takes $O(m^{(k)})$ time.

The computation of the edge score $C$ indeed has complexity $\mathcal{O}(m^{(k)})$. However, it occurs before Algorithm 1, and in the paragraph above Proposition 4, we specifically focused on the time complexity of Algorithm 1 as $\mathcal{O}(n^{(k)})$. The computation of $C$ is dominated by message passing, which can be computed in parallel on GPU. On the other hand, the parsing algorithm must be executed sequentially. That's why, in our time efficiency tests, even EdgePool with $\mathcal{O}(m^{(k)})$ complexity runs very slowly when dealing with densely connected graphs.

(Weakness 2) Proposition 5 is doubtful. The argmax operator may not produce unique output when the multiset has several equal maximum elements.

Thank you for pointing this out! Yes, if there are two nodes with common neighbors and their node features are exactly the same, then the output of the argmax operator cannot guarantee uniqueness. Based on your suggestion, we edited Proposition 5 and it's corresponding proof (paragraph 2 in Appendix A.2) in the updated submission, please refer to the red-colored text. Specifically, we suppose the row-wise non-zero entries in $C$ are distinct. In practice, we find that the potential violation of the permutation invariance caused by the argmax operator has a limited impact on model performance.

(Weakness 3) The performance gain in ablation study is not significant. In Table 4, the performance difference between the origin model and the model with Mean pool is smaller than the score deviation.

In our ablation study, we aim to verify that the performance improvement is primarily due to the parsing algorithm we proposed and to show that our model is robust to changes in the backbone. After replacing the DeepSets module with a simpler Mean pool, the model continues to deliver strong performance, confirming its robustness to the choice of backbone and supporting our claim.

---

(Question) The argmax operator in DOM is not differentiable. How to train the whole model end-to-end?

Here we describe the forward and backward passes of our model to clarify the training process:

• During the forward pass, we first use GNN and MLP to compute the edge scores (Equation 1). Then we run Algorithm 1 to obtain the assignment matrix (Equation 2) and performs the multiset computation to obtain the coarsened graph (Equation 3). The final step is to compute the edge score mask (Equation 4) to ensure the gradients can flow into GNN and MLP.
• Here, we further present the details of Equation 4 to enhance understanding:
  • Induce subgraph $\hat{G}_i^{(k)} \subseteq G^{(k)}$ from node $v_i$ means: each node $v_i$ in graph $G^{(k+1)}$ is a cluster generated by the $k$-th pooling layer, thus it corresponds to a connected subgraph $\hat{G}_i^{(k)}$ in $G^{(k)}$.
  • In order to allow gradients to flow into the MLP used for calculating edge scores, we aggregate the scores of all the edges $\hat{\mathcal{E}}\_i^{(k)}$ in each subgraph $\hat{G}\_i^{(k)}$. We then obtain a vector $\mathbf{y}^{(k)}\_{i} \in \mathbb{R}^{n^{(k+1)}}$ represents the score of clusters.
  • This vector is then replicated into a mask matrix $\mathbf{y}^{(k)} \mathbf{1}^{\mathrm{T}} \in \mathbb{R}^{n^{(k+1)} \times d}$, which matches the shape of the node feature matrix $\mathbf{\hat{X}}^{(k+1)}$. Finally, this mask is element-wise multiplied with the node feature matrix.
• During the backward pass, Algorithm 1 does not run. Instead, the gradient backpropagation is performed directly. The GNN and MLP can be updated through the gradients of the edge score mask.

We sincerely appreciate the reviewer's constructive feedback and positive remarks on our work. We provide the following detailed responses to your major concerns.

(Weakness 1) It seems that GPN works well on small-sized graphs from the experimental results. Discussion on large-sized graphs is expected to be included in the paper.

(Weakness 2) If the tree is high for some large-sized graph, the performance might be worse due to over-smoothing.

It is worth noting that, the PubMed dataset we tested already contains 18,717 nodes, which is not that small-sized. Following your suggestion, in the updated submission (please refer to the red-colored text), we further strengthen the discussion on large graphs in Appendix E. In short, our node classification model architecture already includes residual connections from the encoder to the decoder (see Section 2.3 and Figure 3), which can help mitigate potential over-smoothing issues on large graphs by preserving local information.

(Weakness 3) For the model itself involving GNNs, it is not clear how you train this model.

Since the Reviewer UKss raised the same question, we kindly request that you refer to Response to Reviewer UKss - Question.

---

(Question) What does a different GNN mean in node classification? $\mathbf{H}^{(k)}$ in Eq. 3 is the same as $GNN^\prime(\mathbf{X}^{(k)}, \mathbf{A}^{(k)})$ in eq. 10.

In Equation 3, the multiset computation module directly use the node feature $\mathbf{H}^{(k)}$, which is encoded by the GNN in Equation 1. While in Equation 10, the input node feature is $\mathbf{X}^{(k)}$, and we use another GNN' (different from the GNN in Equation 1) to encode it.

We sincerely appreciate the reviewer's considerate feedback. Here, we provide detailed responses to your concerns.

(Weakness 1) This work may be similar to the idea of [1] which considers and manipulates edges during graph pooling (i.e., making the cluster assignment matrix with edges), since this work also performs edge-centric graph pooling with the cluster assignment matrix that is generated from edges.

Thank you for mentioning this work. In our updated submission (please refer to the red-colored text), we have introduced it in Introduction (paragraph 3 in Section 1) and Related Works (paragraph 1 in Appendix B).

(Weakness 2) Equation (4) lacks details on motivation. I understand that, in order to perform backpropagation with edge scores, edge scores should be added or multiplied with other learnable variables. On the other hand, it is unclear why the edge scores should be multiplied in this way (Equation (4)) and what may be the effect of this multiplication on node features.

• Yes, the multiplication is for backpropagation, this approach is similar to [1] (see the last equation in Equation 2).

• In this way (adding the score and then multiplying), the output cluster from graph pooling can be aware of the number of edges assigned to it through its features.

• Here, we present the details of Equation 4 to enhance understanding:

  • Induce subgraph $\hat{G}_i^{(k)} \subseteq G^{(k)}$ from node $v_i$ means: each node $v_i$ in graph $G^{(k+1)}$ is a cluster generated by the $k$-th pooling layer, thus it corresponds to a connected subgraph $\hat{G}_i^{(k)}$ in $G^{(k)}$.
  • In order to allow gradients to flow into the MLP used for calculating edge scores, we aggregate the scores of all the edges $\hat{\mathcal{E}}\_i^{(k)}$ in each subgraph $\hat{G}\_i^{(k)}$. We then obtain a vector $\mathbf{y}^{(k)}\_{i} \in \mathbb{R}^{n^{(k+1)}}$ represents the score of clusters.
  • This vector is then replicated into a mask matrix $\mathbf{y}^{(k)} \mathbf{1}^{\mathrm{T}} \in \mathbb{R}^{n^{(k+1)} \times d}$, which matches the shape of the node feature matrix $\mathbf{\hat{X}}^{(k+1)}$. Finally, this mask is element-wise multiplied with the node feature matrix.

(Weakness 3) The authors may further perform the statistical test on the main results (Table 1 and Table 2) since the performance of the proposed GPN is comparable against other performant baselines when considering mean and standard deviations together.

Following you suggestion, we performed t-tests and report the best model and its comparable models (p > 0.05) here:

• Table 1:

  Dataset	Best model	Comparable models
  NCI1	GPN	-
  NCI109	GPN	-
  FRANKENSTEIN	GPN	EdgePool
  PROTEINS	GPN	GMT, SPGP, MinCutPool, HoscPool, SEP
  DD	GMT	SPGP

• Table 2:

  Dataset	Best model	Comparable models
  Film	GPN	GCNII, GGCN, NSD
  Cora	GCNII	GPN, MixHop, H2GCN, GPRGNN, GGCN, NSD
  CiteSeer	Geom-GCN	GPN, GCNII, H2GCN, GPRGNN, GGCN, NSD
  PubMed	GCNII	Geom-GCN

---

(Question 1) In Equation (10), it may be better to represent the superscript on GNN' according to its layer index, since GNN' is different across different layers.

The GNN' in Equation 10 is shared across the pooling layers, thus we omitted the superscript.

(Question 2) In Figure 5, the proposed GPN is memory efficient compared to the baseline that uses the cluster assignment matrix for graph pooling. However, the GPN also uses the cluster assignment matrix for graph pooling. In this vein, I am wondering why there exists a significant difference in efficiency while both methods are similar in using the cluster assignment matrix.

This is because the clustering-based methods need to store a dense assignment matrix with quadratic memory complexity (see Section 1 and Figure 1), while our model ensures linear memory complexity through the graph parsing algorithm (see paragraph 5 in Section 2.2).

---

[1] Graph U-Nets, ICML 2019

Thank you for your comments. Here is our response.

(Weakness 1) Graph pooling can elegantly be cast into a compression framework and would hence benefit from an analysis of its fundamental limits based on information theory. The pooling of a graph structure (potentially with some side information as considered) here is a classical information-theoretic problem, i.e., how to best store all the information characterizing the graph in a vector of finite length or even better a bitstring of finite length. It may well be that the entire field of graph pooling as currently considered in the ML literature does not take this perspective, but reading this paper makes it clear that many of the questions asked here would benefit from such a perspective.

We didn't mention the "information theory" in our paper, and the graph pooling problem we studied is not close to it.

(Weakness 2) Generally, this reviewer finds the paper to be quite ad-hoc and also it uses a lot of jargon, not always defined or consistently used. The language is also confusing in many places.

Our paper is not ad-hoc. We didn't use jargon in our paper, and we have defined the symbols we used. We didn't use confusing language in our paper.