MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks

Authors: Carlo Abate, Filippo Maria Bianchi
Primary area: learning on graphs and other geometries & topologies
Keywords: graph neural networks, graph pooling, graph coarsening, maxcut

Abstract:
We propose a novel approach to compute the MAXCUT in attributed graphs, i.e., graphs with features associated with nodes and edges. Our approach works well on any kind of graph topology and can find solutions that jointly optimize the MAXCUT along with other objectives. Based on the obtained MAXCUT partition, we implement a hierarchical graph pooling layer for Graph Neural Networks, which is sparse, trainable end-to-end, and particularly suitable for downstream tasks on heterophilic graphs.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 3

Reviews and discussion:
<thread>
creation date:
1730134420609

thread_type:
official_review

<thread_object>
creator: reviewer_unwn

<content>
summary:
This paper proposes a novel graph pooling method based on the maxcut algorithm. As MaxCut assigns high scores to disconnected nodes, this paper motivates its connection to one-every-K pooling methods and score-based methods. They formulate a differentiable form of MaxCut which they integrate into a pooling layer that utilizes heterophilic message-passing layers. Several experiments comparing MaxCutPool to other pooling methods are conducted.

strengths:
The paper proposes an intuitive pooling method. It is very nicely written and nicely describes the current state-of-the-art for graph pooling. I understood almost all of the details.

weaknesses:
* W1: Auxiliarly loss: As with other top k pooling approaches, the selction is a discrete action and thus not differentiable. Optimizing $\mathcal{L}_{cut}$ may not lead to an s that is well-suited for the downstream task. Claiming that the proposed pooling operator is fully differentiable is thus misleading.
* W2: This paper proposes multiple parts without thoroughly analysing each of them:
    * i) Gradient descent for combinatorial problems are typically not preferred as the solution can arbitrarily bad due to local minima. As this paper proposes to use gradient descent for MAXCUT, there needs to be a more detailed comparison with existing methods, ideally in terms of time/space complexity, expected performance and guarantees. 
    * ii) It also remains unclear whether this gradient based approach is better for downstream-tasks. The only experiment that compares the proposed MaxCutPool with existing MAXCUT algorithms is in Table 2, which shows slight improvements. To me it is not convincing to use this gradient based approach vs. traditional algorithms within MaxCutPool.
    * iii) While the nearest neighbor aggregation is proposed as a algorithms for many pooling methods, it is only evaluated in combination with MaxCutPool. As the difference is rather small it is unclear whether this step is needed. If the authors decide to propose such an algorithm, a more detailed evaluation would be needed. 
* W3: The overall contribution is quite limited. As pointed out by the authors, many algorithms for graph pooling exist and the theoretical and empirical benefits of MaxCutPool do not convince me.
* W4 Experiments: 
    * i) There is no reproducible implementation provided.
    * ii) Graph classification: There seems to be a large hyperparameter optimization ofr MaxCutPool, while "all [other] pooling layers were used with the default hyperparameters". This does not seem to be a fair comparison. Especially when only spliiting into train and validation, the search space needs to be of similar size.
    * iii) Heterophilic tasks are only defined for node classification tasks as heterophily is typically defined as having mostly different labels between adjacent nodes. As node labels do not exist for graph-level tasks, it is unclear what heterophilic graph classification means. The authors also did not define what heterophilic graphs are.
    
Additional minor points:
l.156: Sharpening propagation operators cannot learn any kind of gradients, but sharp gradients.
l.425: "This is the first known instance of a non-expressive pooler passing the expressiveness test provided by this dataset, serving as a counterexample to Theorem 1 in Bianchi & Lachi (2023)". To my understanding, Theorem 1 provides a sufficient condition not a necessary one.

questions:
* l.289: Is CON always defined using the assignment matrix $\mathbf{S}$ based on nearest neighbor aggregation?
* How well does the differentiable MaxCut approximate MaxCut compared to more other algorithms in terms of approximation and time complexity? 
* Is the differentiable MaxCut required or does this method work with other algorithms for MaxCut?
* How important is the nearest neighbor aggregation?
* How do the other methods perform with the same level of hyperparameter tuning?
* Why is there no reproducible implementation provided?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730497357739

thread_type:
official_review

<thread_object>
creator: reviewer_e67d

<content>
summary:
Graph neural networks are constructed out of a few relatively simple building blocks -- A propagation operator, a message function, and a pooling function. These three components have received significant attention over the last few years, with both heuristic and graph theoretic approaches to improve the performance of GNNs on a variety of graph ML tasks. In this work, the authors present a novel pooling operator termed MaxCutPool, that is inspired by the classic graph theory problem of finding the max cut. They provide justification for the value of this pooling operator through robust experiments to find significant performance improvements.

strengths:
1. The paper is clearly presented
2. The experiments are well defined and clearly motivated
3. The authors make significant efforts to contextualize their work within the rest of the literature.
4. The algorithm is clearly outlined in enough detail to reimplement

weaknesses:
This paper is well written, but not without weaknesses. In particular:

1. The authors do not discuss the computational cost of running their pooling operators in comparison to others. While potentially less relevant for graph classification tasks, it is highly relevant for node classification tasks. Please include some discussion, at least in the appendix, of this.
2. The authors do not justify _why_ it is expected that the max cut should provide a better pooling operator.
3. The results in experiment 4.2 indicate only mild performance gains, and the presented method frequently underperforms the case with no pooling. It's was hard for me to understand from the text what the intuition for this is.
4. The experiments in section 4.3 are hard to understand without a no-pooling option.

questions:
1. In experiment 4.1, what were the features used for GNN? Were these learnable vertex embeddings?
2. How does maxcutpool scale with the number of vertices in a graph?
3. What is the intuition as to why learning the max cut operator provides a good pooling operator? Is it just that this is a high-frequency projection?
4. In experiment 4.3, could you provide the tuned baseline for a GNN with no pooling?
5. With $\delta$ set to 2 in your node classification experiments, your propagation operator is already tuned towards heterophilic settings, and the stated intuition for why maxcutpool works is because it is projecting out high frequency components. Could you provide a node-classification results as a function of delta? Given that these datasets are all heterophilic, it's hard to tease out whether the improvements are due to the pooling or the propagation operator.
6. How was hyperparameter tuning performed?
7. Can this work be extended to link prediction in any meaningful way? Would it be possible to view super-node membership as a labeling trick?
8. Does the unpooling operator involve any normalization?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730715435611

thread_type:
official_review

<thread_object>
creator: reviewer_ka5d

<content>
summary:
The paper introduces a novel GNN-based approach for solving the MaxCut problem in attributed graphs. The proposed method exhibits good performance across multiple experiments, particularly when evaluated on the newly introduced heterophilic graph benchmark dataset for graph classification tasks.

strengths:
- The writing is generally reader-friendly, featuring detailed illustrations such as figures and hyperparameters. Theoretical analyses are also provided.
- The proposed method is easy to understand yet remains effective, performing well in experiments.
- This work includes comprehensive experiments covering MaxCut partition computation, graph classification, and node classification, which lend credibility to the conclusions presented in the paper.

weaknesses:
Please refer to the questions below.

questions:
* The method uses HetMP, which can be interpreted as a Laplacian sharpening kernel that enhances differentiation between signals across nodes, thereby reducing smoothness. This approach performs well on heterophilic graphs. However, in Figures 2(b-c), the steps seem to be based on a homophily assumption—where neighboring nodes tend to belong to the same cluster. Could you provide further clarification on this?
* Beyond Equation (4), how does the proposed method perform when using other graph kernels or filters, such as high-pass filters? Additionally, how does the method perform on homophilic graphs?
* Can the proposed method scale to graphs of arbitrary size, or are there practical limitations on the scalability threshold?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731297141231

thread_type:
official_review

<thread_object>
creator: reviewer_iy7r

<content>
summary:
This paper introduces an innovative method for computing the MAXCUT in attributed graphs which is fully differentiable, enabling joint optimization of the MAXCUT with other objectives. Leveraging the resulting MAXCUT partition, the authors develop a hierarchical graph pooling layer tailored for Graph Neural Networks. The authors claim that the pooling layer is sparse, differentiable, and effective for downstream tasks on heterophilic graphs, addressing a key challenge in graph learning by providing a versatile and adaptable pooling strategy.

strengths:
- Introducing the concept of maxcut into attributed graph pooling is novel and meaningful, and it is worth noting the proposed method is feature-aware and differentiable.
- The background and related work are introduced in detail and accompanied by illustrations, which greatly aid in understanding the proposed method.
- It is encouraging that the proposed method was tested on three tasks, including maxcut partition, graph classification, and node classification.

weaknesses:
- The authors are advised to theoretically and empirically analyze the complexity of MaxCutPool, showing whether it introduces additional computational overhead to GNNs.
- It is also recommended that the authors provide the code to facilitate a better understanding of the proposed method and to ensure the reproducibility of the experiments.
- The authors claim that MaxCutPool is particularly effective for heterophilic graphs, but no detailed analysis is provided. What is the underlying interaction between MaxCutPool and heterophilic graphs? Additionally, considering that traditional message passing (including GIN) is designed for homophilic graphs and is regarded as a low-pass filter, could this conflict with MaxCutPool and potentially lead to poorer results?
- My primary concern is with the experimental section. In graph classification tasks, the proposed approach does not demonstrate satisfactory performance and even falls below the no-pooling baseline on nearly half of the datasets. In Table 3, the authors mark the performance of the no-pooling baseline in gray, even when it ranks highest, which is confusing.
- Is MaxCutPool-NL learning $\mathbf{s}$ solely with task loss after removing $\mathcal{L}_{cut}$? Does this imply that the core concept of MaxCut has been removed? If so, it still appears to be comparable.
- Although the work emphasizes its advantages on heterophilic graphs, it does not perform better than other pooling methods on the GCB-H and MUTAG datasets, which have the highest levels of heterophily.
- Compared to graph classification, the performance on node classification is satisfactory. However, it seems that datasets are not the commonly adopted ones for node classification (such as Planetoid or OGB) and exhibit very low levels of heterophily.

The method and idea are very interesting, but the experiment does not sufficiently demonstrate their effectiveness and necessity. I will consider increasing the score once this issue is addressed.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731879725945

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General comment and summary of major changes

comment:
We sincerely thank all reviewers for their thorough and constructive feedback.

We would like to clarify an important point that seems to have caused some confusion: MaxCutPool is designed as a drop-in replacement for pooling layers within GNNs with standard MP layers. Importantly, MaxCutPool deliberately *leverages*, rather than fights against, the properties of traditional message passing. 

After several MP layers, connected nodes tend to have similar features due to oversmoothing. MaxCutPool uses this to its advantage by selecting from each local neighborhood a node as a representative, dropping others that have become redundant. The heterophilic components of MaxCutPool (HetMP layers in ScoreNet and MAXCUT auxiliary loss) make this selection process more effective by encouraging diverse sampling, but this happens within the context of a traditional homophilic message passing GNN.

This perspective helps explain several observations in our results: the method's effectiveness on both homophilic and heterophilic graphs, the ability to ignore the auxiliary loss when the task requires it, and the complementary rather than conflicting relationship between traditional MP layers and our heterophilic pooling.

We acknowledge that we could have made this clearer in the original submission and appreciate the opportunity to clarify it now. We have extensively revised the paper to better reflect this concept and addressed all the reviewers' concerns. We uploaded the revised manuscript with a version with highlighted changes attached at the end.

The major modifications to the paper include:

- A new subsection 3.2, clarifying the interplay between heterophilic and homophilic operations in our layer.
- A new Section F in the appendix containing the algorithmic complexity of our method, as well as experimental comparisons of time and memory usage of the various pooling layers.
- A publicly accessible, anonymous version of our repository, containing the code supporting our experiments. It is available at https://anonymous.4open.science/r/MaxCutPool/
</content>
</thread_object>

</thread>


Metareview:
metareview:
**(a) Scientific Claims and Findings:**
The paper introduces a novel approach for computing the MAXCUT in attributed graphs—graphs with features associated with nodes and edges. This method is fully differentiable, enabling joint optimization of the MAXCUT alongside other objectives within a neural network framework. Leveraging the MAXCUT partition, the authors implement a hierarchical graph pooling layer for Graph Neural Networks (GNNs). This pooling layer is sparse, differentiable, and particularly effective for downstream tasks on heterophilic graphs, where connected nodes may have dissimilar features.

**(b) Strengths:**
* Innovative Pooling Mechanism: The introduction of a differentiable, feature-aware MAXCUT-based pooling mechanism addresses limitations in existing graph pooling methods, particularly in handling heterophilic graphs.
* Differentiability: The proposed approach's differentiable nature allows for seamless integration into end-to-end trainable GNN architectures, facilitating joint optimization with other network components.
* Applicability to Heterophilic Graphs: The method's suitability for heterophilic graphs expands the applicability of GNNs to a broader range of real-world scenarios where connected nodes may not share similar features.
* Computational Complexity: An analysis of the computational complexity of integrating a MAXCUT-based pooling mechanism into GNNs has been added to the appendix and is competitive with efficient pooling baselines. 

**(c) Weaknesses:**
* Empirical Evaluation Scope: While the paper demonstrates the effectiveness of the proposed method, the empirical evaluations could be expanded to include a wider variety of datasets and comparisons with more baseline methods to comprehensively assess performance. Often, the pooling operation itself does not add much merit to solving a task. This leaves doubts on the relevance of pooling for many tasks. 
* Empirical Results on Heterophilic Graphs: A deeper experimental analysis of the impact on heterophilic real world tasks would have been more supportive of the author’s claims. The baseline results in Table 4 are relatively low even in comparison with simple modifications either of the architecture or rewiring. The authors claim, the pooling layer is complementary to other approaches to improve GNN performance on heterophilic tasks, but do not support this claim by experiments. It could also be possible that other approaches are sufficiently strong and would not benefit from additional pooling.
* Theoretical Analysis: A deeper theoretical analysis of the proposed method's properties, such as stability and convergence, is lacking and could strengthen the paper's contributions.
* Computational Complexity: An experimental comparison of run-times with other methods could have been added to compare also the practical efficiency.

**(d) Reasons for Acceptance:**
After a thorough evaluation, I recommend accepting the paper based on the following considerations:
1. Novel Contribution: The paper presents a unique and innovative approach to graph pooling by introducing a differentiable, feature-aware MAXCUT mechanism, addressing a significant gap in current GNN methodologies.
2. Integration Capability: The differentiable nature of the proposed pooling layer allows for seamless incorporation into existing GNN architectures, facilitating end-to-end training and potential improvements in performance across various tasks.
While there are areas for improvement, such as expanding empirical evaluations, the paper's innovative approach and potential impact on the field justify its acceptance.