Dear reviewer Unwn,

thanks for the review!

We are afraid there has been a serious misunderstanding that might have put our work under the wrong perspective. We try our best to address this incomprehension in the following and we remain available for further clarifications.

W1 The definition of differentiability refers specifically to how gradients flow through the score computation and auxiliary loss, not the top-$K$ selection itself. As described in the methods section, our Hadamard product with the score vector $\mathbf{s}$ in the $`RED`$ operation is either

$\mathbf{X}' = \mathbf{s_i} \odot [\mathbf{X}]_{\mathbf{i}}$

or

$\mathbf{X}' = \mathbf{s}_{\mathbf{i}} \odot \mathbf{S}^\top\mathbf{X}$

This ensures that gradients can flow back through the ScoreNet during backpropagation, thus making our architecture fully differentiable. This is common practice for the top-$K$ pooling operators, as shown e.g., in

• https://ieeexplore.ieee.org/document/9432709
• https://arxiv.org/abs/1811.01287
• https://arxiv.org/abs/1905.02850

This allows the model to learn an effective scoring function that is directly influenced by both the auxiliary loss, which acts as a regularization term, and the downstream task.

We also note that such a differentiability is a key difference between our method and existing algorithms to compute the MAXCUT. It is also what makes it possible to adapt the MAXCUT solution to the content of the node features and to other downstream task losses.

W2-1, W2-2, W3, Q2, Q3 It seems that these comments share a common underlying incomprehension, which we try to clarify in the following.

The reason why we developed MaxCutPool was not to outperform traditional MAXCUT algorithms in terms of cut size, but rather to create a differentiable, scalable, and feature-aware pooling operator that can be trained end-to-end within a GNN.

The results in Table 2, where our gradient-based approach achieves comparable (even superior!) performance to specialized MAXCUT algorithms, serve primarily to validate that our architecture and auxiliary loss effectively capture the essence of the MAXCUT objective. This is particularly noteworthy given that our method lacks the theoretical guarantees of traditional algorithms and, as noted by the reviewer, could potentially get stuck in local minima. The fact that we achieved such strong results demonstrates that our model achieves its purpose in implementing an effective maxcut-based regularization objective to perform pooling in a GNN.

We note that it would not be possible to use traditional MAXCUT algorithms within MaxCutPool, because they are not differentiable, they cannot account for node features, and cannot be trained end-to-end with the rest of the GNN. Moreover, while traditional MAXCUT algorithms focus solely on optimizing the cut size, our approach can balance this objective with other learning goals by combining multiple losses. This flexibility is essential in a data-driven setting, where the optimal pooling strategy might need to prioritize preserving certain feature patterns or structural properties over maximizing the cut size. The empirical results show that our method, when needed, can achieve high-quality cuts while simultaneously learning to pool nodes in a way that benefits the downstream task.

On the other hand, established MAXCUT algorithms like Goemans-Williamson that offer approximation guarantees, cannot adapt to these task-specific requirements or incorporate node feature information in computing the solution. In addition, the theoretical guarantees about the MAXCUT solution are less relevant in downstream tasks such as graph or node classification, where the MAXCUT objective serves only as a regularizer.

W2-3 The improvement in the expressive power of any score-based pooling operator that adopts the proposed aggregation scheme is guaranteed by the theoretical result on the expressiveness of pooling operators (https://arxiv.org/abs/2304.01575). As such, our claim does not require the support of an experimental evaluation.

W4-1, Q6 We created an anonymous version of our repository, which can be accessed at https://anonymous.4open.science/r/MaxCutPool/.

W4-2, Q5 We believe there is a misunderstanding here. We did not just use a train-validation split. Instead, we used a rigorous 10-fold cross-validation procedure where the training set was further split into 90-10% train-validation sets.

Regarding the hyperparameters optimization, as shown in the Appendix, the hyperparameter search space for MaxCutPool was actually quite constrained, resulting in a relatively small grid of configurations compared to the complexity of the model. Most of the other pooling methods do not have hyperparameters, except for the soft-clustering methods. For them, we rely on the thorough hyperparameters optimization performed by their respective authors on the different datasets, which we refer to as "default" values.

Dear reviewer E67D,

thank you very much for the positive and very detailed review. There are a lot of interesting comments and suggestions that we appreciate.

Weakness 1 We improved the computational complexity analysis and comparison with the other methods. We now included in Appendix F a detailed report about the time and memory consumption of different pooling layers.

Weakness 2 Thanks for bringing up this important point.

Traditional score-based methods are renowned for their efficiency and scalability. However, they select nodes based on scores that are obtained from node features produced by homophilic MP operations. As such, the selected nodes usually come from the same part of the graph. This is a well-known problem because the rest of the graph is not represented.

On the other hand, selecting the nodes belonging to one side of the maxcut partition provides a much more uniform sampling, ensuring that all the parts of the original graph are represented after pooling. In addition, when applying standard homophilic MP layers before MaxCutPool, the stronger the association between a pair of nodes, the more similar their features will be. Keeping them both will, thus, be redundant, and one of them can be dropped. This is precisely what is done by MAXCUT, which selects nodes with few direct links.

We inserted this explanation in the new section 3.2 of the revised paper.

Weakness 3 The "No pool" baseline is used to establish whether pooling in general can improve performance on a given dataset, which is not always the case. This is a rather standard procedure in graph pooling evaluations. For example, if the graphs are too small, using graph pooling can lower the performance w.r.t. the baseline. Nevertheless, in those cases, it is still meaningful to compare different pooling operators to evaluate their capability of retaining enough information. That is why the ranking only focuses on those comparisons.

Given this context, the results consistently demonstrate that our method outperforms existing approaches, with statistically significant improvements across the evaluation metrics. In particular, statistical analysis (ANOVA followed by Tukey-HSD tests, both with p-value 0.05) revealed that our method is consistently equal or superior to every other pooling operator.

Weakness 4 We added the "No pool" baseline to Table 4.

We would like to point out that this experiment is inspired by the test "Preserving node attributes" from section 5 in the SRC paper (https://arxiv.org/abs/2110.05292). There, the goal is to check the capability of a pooling method to retain as much information as possible from the input data. As such, and similarly to the graph classification experiment, the "No pool" should be intended as a baseline to provide context rather than a competitor.

Question 1 Some of the PyGSP graphs had 2-D coordinates used for plotting that we used as surrogate features. All the remaining graphs had no features and we used a constant value. The details can be found in Appendix C.2.

We would like to comment that the point of this experiment was to show that our model can produce MAXCUT partitions that are comparable, or even better, to those of traditional algorithms specifically designed to compute the MAXCUT. Using learnable vertex features would have added additional capacity to our model and arguably improved its performance. However, this would have been different from the setting used for graph and node classification, which is our main focus.

Question 2 Our model scales linearly with the vertices and edges of the graph. This experiment is provided in Appendix F, alongside with other computational cost assessments.

Question 3 In addition to the answer provided to Weakness 2, we would like to add the following.

While the MAXCUT objective does promote high-frequency signals through node differentiation, it's more sophisticated than just a high-frequency projection. The MAXCUT auxiliary loss $\mathcal{L}_{cut}$ acts as a regularization term that is optimized jointly with the downstream task loss. This allows the model to find a partition that adaptively balances between preserving distinct node information through the MAXCUT objective and is optimal for task performance. The task loss can even guide the model to ignore the MAXCUT objective when beneficial, as demonstrated by datasets like COLLAB where the auxiliary loss converges to near zero -- instead of its minimum value of -1.

Question 4 Please, refer to our answer to Weakness 4.

Dear reviewer ka5D,

We sincerely thank you for the review and for the useful comments that pointed out some lack of clarity in our paper. This is much appreciated.

Question 1 Indeed, the supernode selection in $`SEL`$ is explicitly designed to be heterophilic. This is done to sample the graph uniformly, differently from other score-based poolers that select nodes concentrated in a single region because they compute the scores directly from homophilic propagation.

As correctly noted by the reviewer, the assignments $\mathbf{S}$ are computed through the nearest-neighbor aggregation, which follows a homophilic assumption. Assignments built in this way synergize well with the uniform sampling of the supernodes and are what allow the pooled adjacency $\mathbf{S}^\top\mathbf{A}\mathbf{S}$ to be connected yet sparse.

A tension between heterophilic and homophilic operations might appear when looking at how the features of the supernodes are computed by $`RED`$. However, it should be stressed that the homophilic assignments can be leveraged by $`RED`$ to ensure expressiveness when summarizing the graph content, but that is not mandatory. In fact, for heterophilic datasets, the non-expressive variant of our method offers a more suitable alternative. In the latter case, $\mathbf{S}$ is not used and the formation of supernodes is consistent with the heterophilic operation of the HetMP layer.

We clarified this point in the new section 3.2 of the paper.

Question 2 The operator defined in Equation (4) is extremely simple as it is based on a standard GCN, yet it gives us exactly what we need to get a MAXCUT partition. Even if other heterogeneous MP layers could have been used, they would have been arguably more complex and bring no additional benefits that we could think of.

Regarding performance on homophilic graphs, the architectures we use for graph and node classification can also handle these cases effectively. The GIN layers that precede the pooling layer perform standard homophilic propagation, allowing the network to identify and leverage similarity patterns when they are present in the data. This is empirically validated by our experimental results, where MaxCutPool achieves competitive performance even on strongly homophilic datasets like GCB-H (reported in the graph classification section) and MUTAG (reported in the Appendix), which have high $\bar{h}(\mathcal{D})$ values of 0.8440 and 0.7082, respectively. In COLLAB (the extreme case of homophily where all the nodes have the same feature) our method adapts by letting the auxiliary loss converge to zero instead of its minimum theoretical value of -1.

Question 3 Our method scales very well, much better than pooling methods that use dense operations. We improved our scalability analysis including more detailed comparisons of time and memory requirements of our pooling layer compared to others. This can be found in Appendix F of the revised manuscript.

Dear reviewer iy7r,

Let us first thank you for the review and for appreciating the relevance of our work and our efforts in the experimental evaluation.

Weakness 1 We added a new Section F in the appendix dedicated to theoretical and empirical analysis of the complexity. The section includes:

• Algorithmic complexity (we report the theoretical complexity using the big-O notation)
• Execution times (we report the execution times of different pooling methods on the 5 datasets considered in the node classification task, which are the most demanding in terms of resources)
• Memory usage (we report the utilization of the GPU memory on the node classification datasets and on a controlled experiment where we gradually increase the size of a synthetically generated graph and measure the memory consumption).

Regarding the execution times and GPU utilization, we note that one-over-$K$ methods such as Graclus, NDP, and $k$-MIS perform a preprocessing step on the CPU before training starts. Those are not reported in the measurement, but they can take significant time and be a bottleneck in those cases that require operations such as eigenvalue decomposition.

Weakness 2 We created an anonymous version of our repository, which can be accessed at https://anonymous.4open.science/r/MaxCutPool/

Weakness 3 We agree that this is an important point and we added a clarification in section 3.2 of the revised paper.

Rather than conflicting, the homophilic nature of traditional message passing is actually leveraged by our method. The basic idea is that after a standard homophilic message-passing, the stronger the association between a pair of nodes, the more they will end up containing the same information. Therefore, keeping both is redundant and one of them can be dropped following the strategy implemented by our pooling operator.

In addition, we note that combining a homophilic network with a heterophilic pooling strategy provides extra flexibility to our model. As an example, let's consider the COLLAB dataset which is highly homophilic. The downstream task is able to guide the model even towards ignoring the auxiliary loss if needed.

With that said, we showed that our model is particularly good in amplifying the node differences where present, making it perform particularly well in the case of heterophilic graphs.

Weakness 4 The "No pool" baseline is used to establish whether pooling -- in general -- can improve performance on a given dataset, which is not always the case. This is a rather standard procedure in graph pooling evaluations. For example, if the graphs are too small, using graph pooling can lower the performance w.r.t. the baseline. Nevertheless, even in those cases, it is still meaningful to compare different pooling operators to evaluate their capability of retaining enough information. That is why the ranking only focuses on those comparisons.

We understand that the term "satisfactory" can be subjective. To address this, we have grounded our claims in objective measurements and rigorous statistical analyses. Our results consistently demonstrate that our method outperforms existing approaches, with statistically significant improvements across the evaluation metrics. In particular, statistical analysis (ANOVA followed by Tukey-HSD tests, both with p-value 0.05) revealed that our method is consistently equal or superior to the other pooling operators.

Weakness 5 Yes, the interpretation of MaxCutPool-NL is correct. However, the core concept of MaxCut is still there. In fact, the HetMP layers still provide the MAXCUT architectural bias that encourages dissimilarity between connected nodes. As shown by the experimental results, such architectural bias can be sufficient in some cases, even though the addition of an explicit optimization objective is often more effective than the sharpening operator alone.

Weakness 6 There seems to be a misinterpretation. The $h(\mathcal{D})$ is a measure of homophily, not heterophily, and GCB-H and MUTAG are strongly homophilic datasets. The advantage of MaxCutPool on heterophilic graphs is demonstrated by its superior performance on highly heterophilic datasets used in the node classification experiments and the Multipartite dataset.

Weakness 7 Also in this case, we note that $h(\mathcal{D})$ is a measure of homophily.

Planetoid and OGB graphs are extremely homophilic:

As such, to achieve high performance on those datasets it is sufficient to apply a few layers of homophilic MP rather than using the proposed node classification architecture with pooling layers.

Thank you for your feedback and for raising the score.

We built this figure (https://imgur.com/a/evolution-of-scores-node-selection-maxcutpool-Nf1MkMo) from our experiment's logs on the Multipartite dataset, which is completely heterophilic by design (each node is connected only to nodes of different colors). The plot shows how the HetMP layers in ScoreNet can assign similar scores to nodes that are completely disconnected, demonstrating how MaxCutPool effectively handles heterophilic structures.

We note that the GNN is the same as used in our experiments with GIN layers. Clearly, using heterophilic MP layers would facilitate the learning even further and is a viable option in some special cases. However, our goal was to provide a general-purpose pooling layer that can be a drop-in replacement in standard GNNs, turning them into powerful models that can handle both homophilic and heterophilic graphs.