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

## Abstract

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 is robust to the underlying graph topology and is fully differentiable, making it possible to 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, differentiable, and particularly suitable for downstream tasks on heterophilic graphs.

## 1 Introduction

The MAXCUT is the problem of partitioning the nodes of a graph such that as many edges as possible connect nodes from different sides of the partition.
The MAXCUT is orthogonal to the more commonly encountered minCUT, which aims at partitioning the nodes into strongly connected groups.
While minCUT is closely related to clustering, MAXCUT relates to the concept of downsampling, *e.g.*, keeping one-every-$K$, under the assumption that there is a redundancy among the $K$ samples.
Like the minCUT, the MAXCUT is a combinatorial optimization problem that, in practice, is approximated by approaches that find suboptimal or unstable solutions for a large class of graphs (Makarychev et al., ).

Pooling is ubiquitously used in deep learning for gradually reducing the size of the data while retaining important information. In Convolutional Neural Networks (CNNs), pooling is typically implemented by selecting the maximum within a contiguous patch (max-pool) or by computing an average (avg-pool). These strategies are naturally related to MAXCUT and minCUT problems, respectively.
Similarly to CNNs, Graph Neural Networks (GNNs), which can be seen as a generalization to irregular data, are typically built by alternating Message Passing (MP) and graph pooling layers (Zhou et al., ). A hierarchy of pooling layers gradually extracts global graph properties through the computation of local summaries and is key to building deep GNNs for graph classification (Khasahmadi et al., ), node classification (Gao & Ji, ; Ma et al., ), graph matching (Liu et al., ), and spatio-temporal forcasting (Cini et al., ; Marisca et al., ).

Two important approaches are followed when implementing hierarchical graph pooling.
One is to account for the node features with trainable functions that are adapted to a downstream task at hand. The other is to optimize graph theoretical objectives, such as the minCUT or the MAXCUT, to guide the computation of the coarsened graph.
Combining the first approach with minCUT objectives is relatively straightforward, as they complement the smoothing effect of MP layers (Hansen & Bianchi, ).
Conversely, objectives such as MAXCUT that select sparse and uniformly distributed subsamples of nodes have been implemented so far only within non-differentiable frameworks, which account neither for node features nor for task objectives (Luzhnica et al., ).

### 1.1 Contributions

#### MAXCUT for attributed graphs.

Our first contribution is graph theoretical and consists of a novel GNN-based approach to compute a MAXCUT partition in attributed graphs. Being completely differentiable, our method can be seamlessly integrated into a deep-learning framework where other loss functions can influence the MAXCUT solution.
Remarkably, our method is also more robust than traditional approaches in computing the MAXCUT on non-attributed graphs, as it finds a better cut on most graph topologies.
This makes our contribution relevant to *every* application of the MAXCUT problem, such as quantum computing (Zhou et al., ), circuit design (Bashar et al., ), statistical physics (Borgs et al., ), material science (Liers et al., ), computer vision (Abbas & Swoboda, ), and quantitative finance (Lee & Constantinides, ).

#### Graph pooling and coarsening.

The MAXCUT application we focus on is the problem of learning a coarsened graph within a GNN. In particular, we design a new hierarchical pooling layer that reduces the graph by keeping the nodes from one side of the MAXCUT partition. Our layer is the first to combine a graph theoretical MAXCUT objective with a differentiable and features-aware approach for pooling. When we include the newly proposed pooling layer in GNNs for graph and node classification, we achieve similar or superior performances compared to state-of-the-art pooling techniques.

#### Improved score-based pooling framework.

We propose a simple and efficient scheme to assign node to supernodes when computing the pooled graph.
Our scheme can be applied not only to our method but to the whole family of sparse score-based graph pooling operators enhancing, in principle, their representational power.
Importantly, we bridge the gap between score-based and dense pooling methods by using the same operations to compute the features and the topology of the pooled graph.

#### Heterophilic graph classification dataset.

Differently from the existing differentiable pooling operators, the nature of the MAXCUT solution makes our graph pooling operator particularly suitable for heterophilic graphs.
While there are benchmark datasets for node classification on heterophilic graphs, there is a lack of such datasets for graph classification.
To fill this gap, we introduce a novel synthetic dataset that, to our knowledge, is the first of its kind.

## 2 Background

### 2.1 The MAXCUT problem and the continuous relaxations

Let ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$ be an undirected graph with non-negative weights on the edges, and let $N$ be the number of nodes in ${\mathcal{G}}$. A cut in ${\mathcal{G}}$ is a partition $({\mathcal{S}},{\mathcal{V}}\setminus{\mathcal{S}})$ where ${\mathcal{S}}\subset{\mathcal{V}}$. The MAXCUT problem consists of finding a cut that maximizes the total volume of edges connecting nodes in ${\mathcal{S}}$ with those in ${\mathcal{V}}\setminus{\mathcal{S}}$.
The MAXCUT objective can be expressed as the integer quadratic problem

$$ $\max_{{\bm{z}}}\sum\limits_{i,j\in\mathcal{V}}w_{ij}(1-z_{i}z_{j})\;\;\text{s. t.}\;\;z_{i}\in\{-1,1\},$ (1) $$

where ${\bm{z}}\in\{-1,1\}^{N}$ is an assignment vector indicating to which side of the partition each node is assigned to and $w_{ij}$ is the weight of the edge connecting nodes $i$ and $j$.

Like other discrete optimization problems of this kind, MAXCUT is NP-hard.
The Goeman-Williamson (GW) algorithm (Goemans & Williamson, ) provides a semidefinite relaxation of the integer quadratic problem, which makes it tractable:

$$ $\max_{{\bm{X}}}\sum\limits_{i,j\in\mathcal{V}}w_{ij}(1-{\bm{x}}_{i}\cdot{\bm{x }}_{j})\;\;\text{s.t.}\;\;\|{\bm{x}}_{i}\|=1,$ (2) $$

where ${\bm{X}}\in{\mathbb{R}}^{N\times D}$ is a matrix whose rows are the continuous embeddings of the nodes in ${\mathcal{G}}$.
The vectors ${\bm{X}}$ are projected on a random hyperplane to split the nodes and assign them to the two sides of the partition. This algorithm guarantees an expected cut size of $.868$ of the maximum cut.

Another simple yet effective continuous relaxation is the largest eigenvector vertex selection (LEVS) method (Shuman et al., ).
Let ${\bm{L}}$ be the Laplacian matrix associated to the graph ${\mathcal{G}}$ and let ${\bm{u}}_{\max}$ be the eigenvector of ${\bm{L}}$ associated to the largest eigenvalue $\lambda_{\max}$. A cut in ${\mathcal{G}}$ can be found based on the polarity of the components of ${\bm{u}}_{\max}$, for instance by letting ${\mathcal{S}}=\{i:{\bm{u}}_{\max}[i]\geq 0\}$.
In the field of graph signal processing, the eigenvectors related to the largest eigenvalues of ${\bm{L}}$ are closely related to the operation of high-pass filtering of a graph signal (Tremblay et al., ). Specifically, they are used to design graph filters that amplify high-frequency components of a signal, *i.e.*, the components that vary the most across adjacent nodes (Shuman et al., ).

The MAXCUT problem is closely related to graph coloring, which aims at assigning different colors to adjacent nodes.
In particular, the 2-color *approximate coloring* (Aspvall & Gilbert, ), is the problem of identifying subsets of nodes such that the connections within each subset are minimized. Such coloring is a high-frequency graph signal and induces a partition that is orthogonal with respect to spectral clustering (von Luxburg, ).

Figure: (a)
Refer to caption: x1.png

A MAXCUT partition that cuts every edge exists only for bipartite graphs. Conversely, in fully connected graphs no more than half of the edges can be cut.
Algorithms relying on continuous relaxations to find the MAXCUT partition tend to be unstable and perform poorly, especially as the graph topology departs from the bipartite case (Trevisan, ).
Fig. 1(a-h) shows the performance of the LEVS method on bipartite and non-bipartite graphs: numerical issues typically occur in more dense and less regular graphs, making it difficult to identify the optimal MAXCUT solution.

### 2.2 Message passing in GNNs

Let us consider a graph ${\mathcal{G}}=\left({\bm{X}}\in{\mathbb{R}}^{N\times F},{\bm{A}}\in{\mathbb{R}
}^{N\times N}\right)$. A basic MP operator can be described as

$$ ${\bm{X}}^{\prime}=\sigma\left({\bm{P}}{\bm{X}}\bm{\Theta}\right)$ (3) $$

where $\sigma$ is a non linear activation function, $\bm{\Theta}$ are trainable parameters, and ${\bm{P}}$ is a propagation operator matching the sparsity pattern of ${\bm{A}}$.
Each MP layer relies on a specific propagation operator.
For instance, in Graph Convolutional Networks (GCNs) (Kipf & Welling, ), the propagation operator is defined as ${\bm{P}}=\hat{{\bm{D}}}^{-\frac{1}{2}}\hat{{\bm{A}}}\hat{{\bm{D}}}^{-\frac{1}{
2}}$, where $\hat{{\bm{A}}}={\bm{A}}+{\bm{I}}$ and $\hat{D}_{ii}=\sum_{j=0}\hat{{\bm{A}}}_{ij}$.

Due to the fixed, non-negative smoothing nature of most propagation operators, the repeated application of ${\bm{P}}$ can lead to over-smoothing.
If that happens, the feature representations of nodes become increasingly similar,
hindering the function approximation capabilities of a GNN, which can only learn smooth graph signals (Wu et al., ; Wang et al., ).
In contrast, by using a *sharpening* propagation operator, any kind of gradients can be learned (Eliasof et al., ).
Since there is no universal definition for such an operator, we rely on the formulation introduced by Bianchi ():

$$ ${\bm{P}}={\bm{I}}-\delta\left({\bm{I}}-{\bm{D}}^{\frac{1}{2}}{\bm{A}}{\bm{D}}^ {\frac{1}{2}}\right)={\bm{I}}-\delta{\bm{L}}^{\text{sym}}$ (4) $$

where $\delta$ is a smoothness hyperparameter and ${\bm{L}}^{\text{sym}}$ is the symmetrically normalized Laplacian of ${\mathcal{G}}$.
As observed by Bianchi (), when $\delta=0$ the MP behaves like a simple Multilayer Perceptron (MLP). Instead, when $\delta=1$ the behavior is close to that of a GCN.
Finally, as noted by Eliasof et al. (), when $\delta>1$ the propagation operator favors the realization of non-smooth signals on the graph and we refer to this variant as a Heterophilic Message Passing (HetMP) operator. We note that this can be seen as a graph-equivalent of the Laplacian sharpening kernels for images, mapping connected nodes to different values (Mather & Koch, ).

### 2.3 Graph pooling

While there are profound differences between existing graph pooling approaches, most of them can be expressed through the Select-Reduce-Connect (SRC) framework (Grattarola et al., ).
Specifically, a pooling operator $\texttt{POOL}:({\bm{A}},{\bm{X}})\mapsto({\bm{A}}^{\prime},{\bm{X}}^{\prime})$ can be expressed as the combination of three sub-operators:

- •
$\texttt{SEL}:({\bm{A}},{\bm{X}})\mapsto{\bm{S}}\in{\mathbb{R}}^{N\times K}$, is a selection operator that defines how the $N$ original nodes are mapped to the $K$ pooled nodes, called *supernodes*, being ${\bm{S}}$ the *selection matrix*.
- •
$\texttt{RED}:({\bm{X}},{\bm{S}})\mapsto{\bm{X}}^{\prime}\in{\mathbb{R}}^{K
\times F}$, is a reduction operator that yields the features of the supernodes. A common way to implement RED is ${\bm{X}}^{\prime}={\bm{S}}^{\top}{\bm{X}}$.
- •
$\texttt{CON}:({\bm{A}},{\bm{S}})\mapsto{\bm{A}}^{\prime}\in{\mathbb{R}}^{K
\times K}_{\scalebox{0.7}{$\geq 0$}}$, is a connection operator that generates the new adjacency matrix and, potentially, edge features. Typically, CON is implemented as ${\bm{A}}^{\prime}={\bm{S}}^{\top}{\bm{A}}{\bm{S}}$ or ${\bm{A}}^{\prime}={\bm{S}}^{+}{\bm{A}}{\bm{S}}$.

Different design choices for SEL, RED, and CON induce a taxonomy of the operators.
For example, if SEL, RED, and CON are learned end-to-end the pooling operators are called *trainable*, *non-trainable* otherwise.
Relevant to this work, are the families of pooling methods described in the following.

Soft-clustering methods, sometimes referred to as *dense* (Grattarola et al., ), assign each node to more than one supernode through a soft membership.
Representatives methods such as DiffPool (Ying et al., ), MinCutPool (Bianchi et al., ),
StructPool (Yuan & Ji, ),
HoscPool (Duval & Malliaros, ),
and Deep Modularity Networks (DMoN) (Tsitsulin et al., ), compute a soft cluster assignment matrix ${\bm{S}}\in\mathbb{R}^{N\times K}$ either with an MLP or an MP-layer operating on node the features and followed by a softmax.
Each method leverages different unsupervised auxiliary loss functions to guide the formation of the clusters.
Trainable soft-clustering methods usually perform well on downstream tasks due to their flexibility and *expressive power*, which is the capability of retaining all the information from the original graph (Bianchi & Lachi, ).
However, storing the soft assignments ${\bm{S}}$ is a memory bottleneck for large graphs (see, *e.g.*, the analysis of memory usage in Appendix E.3) and soft memberships cause pooled graphs to be very dense and not interpretable.
Additionally, each graph is mapped to the same fixed number of supernodes $K$, which can hinder the generalization capabilities in datasets where the size of each graph varies significantly.

Score-based methods select supernodes from the original nodes based on a node scoring vector ${\bm{s}}$.
The chosen nodes correspond to the top $K$ elements of ${\bm{s}}$, where $K$ can be a ratio of the nodes in each graph, making these methods adaptive to graph size.
Representatives such as Top-$k$ Pooling (Top-$k$) (Gao & Ji, ; Knyazev et al., ), ASAPool (Ranjan et al., ), SAGPool (Lee et al., ), PanPool (Ma et al., ), TAPool (Gao et al., ), CGIPool (Pang et al., ), and IPool (Gao et al., ) primarily differ in how they compute the scores or in the auxiliary tasks they optimize to improve the quality of the pooled graph.
Despite a few attempts to encourage diversity among the selected nodes (Zhang et al., ; Noutahi et al., ), score-based methods derive the scores from node features that tend to be locally similar, especially after being transformed by MP operations.
As such, the pooled graph often consists of a chunk of strongly connected nodes that possess similar characteristics.
Consequently, entire sections of the graph are usually not represented, leading to reduced expressiveness and lower performance in downstream tasks (Wang et al., ).

One-every-$\bm{K}$ methods leverage graph-theoretical properties to select supernodes by subsampling the graph uniformly.
For instance, $k$ Maximal Independent Sets Pooling ($k$-MIS) (Bacciu et al., ) identifies as supernodes the members of a maximal $K$-independent set, *i.e.*, nodes separated by at least $K$-hops on the graph.
Graclus (Dhillon et al., ; Defferrard et al., ) creates supernodes by merging the pairs of most connected nodes in the graph.
SEP (Wu et al., ) partitions the node hierarchically according to a precomputed tree that minimizes the structural entropy of the graph.
Node Decimation Pooling (NDP) (Bianchi et al., ) divides the graph into two sets, ${\mathcal{V}}_{+}$ and ${\mathcal{V}}_{-}$, according to the partition induced by the components of ${\bm{u}}_{\max}$ (see Section 2.1).
One of the two sides of the partition is dropped (${\mathcal{V}}_{-}$), while the other (${\mathcal{V}}_{+}$) becomes the set of supernodes.
While both Graclus and NDP can only reduce the number of nodes by approximately half, higher pooling ratios (one-every-$2^{K}$) are achieved by applying them recursively $K$ times.
Nevertheless, they lack the same control of soft-clustering and score-based methods in fixing the size of the pooled graphs.
Like the score-based methods, one-every-$K$ methods are adaptive and produce crisp cluster assignments.
However, they are not trainable and they precompute the pooled graph based on the topology without accounting neither for the node features nor the downstream task.
Tab. 1 summarizes the drawbacks of the existing families of pooling methods.

**Table 1: Drawbacks of different types of pooling operators.**
| Soft-clustering | Score-based | One-every-$\bm{K}$ |
| --- | --- | --- |
| ✗  Not adaptive to graph size | ✗  Pooling not uniform | ✗  Limited flexibility |
| ✗  Dense and not interpretable pooled graphs | ✗  Not expressive | ✗  Features agnostic |
| ✗  High memory cost | ✗  Worse performance | ✗  Task agnostic |

## 3 Method

We leverage a GNN to generate a MAXCUT partition while accounting for node features and additional objectives from a downstream task.
In particular, we let node features and task-specific losses influence the selection of the MAXCUT solution, creating partitions that not only maximize the number of cut edges but also prioritize nodes that are optimal for the downstream task.
To reach this goal, it is necessary to overcome a tension between the effect of a standard MP layer and the MAXCUT: the first applies a smoothing operation that makes adjacent nodes as similar as possible, which is orthogonal to the objective of the latter.
Therefore, to implement MAXCUT with a GNN we rely on HetMP, implemented by setting $\delta>1$ in the MP operation in Eq. 4.
As discussed in Sec. 2.1, solving the MAXCUT problem is equivalent to coloring adjacent nodes differently. Notably, this is an intrinsic effect of HetMP that makes features of adjacent nodes as different as possible, effectively acting as a high-pass filter.
Therefore, optimizing a MAXCUT loss on features generated by HetMP layers addresses the limitation of traditional score-based methods that compute the scores from features produced by homogeneous MP operations.

The layer we propose is called (MaxCutPool) and we present it through the SRC framework.
The SEL operation in MaxCutPool identifies as supernodes a subset ${\mathcal{S}}$ of the nodes in the original graph. An auxiliary GNN, called *ScoreNet*, consists of a stack of HetMP layers that map the node features into a vector $\bm{s}=\text{ScoreNet}({\bm{X}},{\bm{A}})\in[-1,1]^{N}$ that assigns a score to each node.
The indices ${\bm{i}}=\text{top}_{K}({\bm{s}})$ associated with the highest scores identify the $K$ supernodes.
Additional details about the ScoreNet are in Appendix C.1.
Fig. 1(i-l) shows the histograms of the score vectors $\bm{s}$ generated by the ScoreNet for the $4$ example graphs.
Compared to the histograms of ${\bm{u}}_{\text{max}}$ in Fig. 1(e-h), the values in $\bm{s}$ always follow a distribution with two sharp and well-separated modes, yielding a clear node partition.

After the $K$ supernodes are selected, the remaining $N-K$ nodes are assigned to one of the supernodes via the nearest neighbor aggregation.
An assignment matrix ${\bm{S}}$ is built by performing a breadth first visit of the graph where, starting from the supernodes, all the remaining nodes are assigned to their nearest supernode (see Figure 2).

Figure: (a)
Refer to caption: x13.png

More formally, the assignment matrix ${\bm{S}}$ is defined as

$$ $\texttt{SEL}:[{\bm{S}}]_{ij}=1\iff j=\phi({\mathcal{S}},{\bm{A}},i),$ $$

where $\phi({\mathcal{S}},{\bm{A}},i)$ returns the nearest supernode of node $i$.
The visit of the graph is iterated until all nodes are assigned to a supernode or until a maximum number of iterations is reached.
In the latter case, nodes that are still unassigned are assigned at random, which ensures that the pooled graph is always connected.
Keeping the maximum number of iterations small (*e.g.*, $2$ or $3$) prevents pointless attempts to reach a supernode, *e.g.*, when there are no supernodes within a disconnected graph component, and also injects randomness acting as a regularizer that helps to move away from suboptimal configurations often encountered at the beginning of the training stage.
The pseudo-code for a GPU parallel implementation of the proposed assignment scheme is in Appendix A.

The RED operation for computing the features of the supernodes can be implemented in two ways:

RED: $[{\bm{X}}^{\prime}]_{i:}=s_{i}\odot[{\bm{X}}]_{i:}$    or
RED: ${\bm{X}}^{\prime}={\bm{s}}\odot{\bm{S}}^{\top}{\bm{X}}$.

When the first and second options are used to implement RED, we refer to the pooling operator as MaxCutPool and MaxCutPool-E, respectively.
The suffix “-E” indicates the pooling operator satisfies the sufficient conditions for expressiveness defined by Bianchi & Lachi ().

Finally, having defined a cluster assignment matrix ${\bm{S}}$, the CON operation can be implemented as

$$ $\texttt{CON}:{\bm{A}}^{\prime}={\bm{S}}^{\top}{\bm{A}}{\bm{S}}.$ $$

### 3.1 Auxiliary loss

Each MaxCutPool layer is associated with an auxiliary loss that encourages the top-$K$ selected nodes to belong to the same side of the MAXCUT partition.
The loss is defined as:

$$ $\mathcal{L}_{\text{cut}}=\frac{{\bm{s}}^{\top}A{\bm{s}}}{|E|}$ (5) $$

where $|E|=\sum_{ij}w_{ij}$ is the total edge weight of the graph. Since $-1\leq s_{i}\leq 1$, we have $-|E|\leq{\bm{s}}^{\top}A{\bm{s}}\leq|E|$, hence $-1\leq\mathcal{L}_{\text{cut}}\leq 1$.
This loss evaluates the ratio between the volume of the cut and the total volume of the edges.
Minimizing $\mathcal{L}_{\text{cut}}$ encourages the nodes to be assigned to different partitions if and only if they are connected.
The loss reaches its minimum $-1$ when all connected nodes are assigned to opposite sides of the partition, *i.e.*, when all the edges are cut.
Clearly, this can happen only in bipartite graphs. The details about the derivation of the loss are in Appendix B.

A GNN model consisting of MP layers interleaved with MaxCutPool layers can be trained end-to-end to jointly minimize a task loss $\mathcal{L}_{\text{task}}$ and the auxiliary loss $\mathcal{L}_{\text{cut}}$.
The total loss is then defined as

$$ $\mathcal{L}=\mathcal{L}_{\text{task}}+\sum_{l}\beta\mathcal{L}^{(l)}_{\text{ cut}}$ (6) $$

where $\beta$ is a scalar weighting each auxiliary loss $\mathcal{L}^{(l)}_{\text{cut}}$ associated with the $l$-th MaxCutPool layer.

### 3.2 Relation with other pooling methods

MaxCutPool belongs to the score-based pooling family from which inherits the possibility of specifying any desired pooling ratio adaptable to the size $N_{i}$ of the $i$-th graph, *i.e.*, $K^{(i)}=\lfloor N^{(i)}*0.5\rfloor$.
Differently from the other score-based methods and thanks to the HetMP layers, MaxCutPool selects supernodes that are not concentrated in the same section of the graph but are, instead, distributed more uniformly over the whole graph, which is similar to the one-over-$K$ methods.
In methods like $k$-MIS the flexibility provided by trainable functions is only used to choose between a small set of maximal solutions that do not break the hard constraint of the supernodes to be $K$-independent.
On the other hand, in MaxCutPool any set of supernodes can, in principle, be chosen making MaxCutPool more flexible and able to better adapt to the requirements of the downstream task.
Finally, MaxCutPool is the only score-based pooler with a graph-theoretical auxiliary regularization loss.

The proposed method for constructing the cluster assignment matrix ${\bm{S}}$ from the selected supernodes can be applied to other score-based pooling methods.
This naturally enhances their expressiveness by enabling the use of the same CON and RED operations adopted by soft-clustering approaches, which retains all the information from the original graph.
By addressing the key limitation in expressiveness of score-based pooling methods, our approach retains the benefits of sparsity and interpretability of score-based poolers while narrowing the gap with soft-clustering methods.

## 4 Experimental evaluation

We consider three different tasks to demonstrate the effectiveness of MaxCutPool.
The code to reproduce the reported results in publicly available(^1^11 [https://github.com/NGMLGroup/MaxCutPool](https://github.com/NGMLGroup/MaxCutPool)).
The details about the architectures used in each experiment and the hyperparameters selection procedure are described in Appendix C.

### 4.1 Computation of the MAXCUT partition

This experiment focuses on computing a MAXCUT partition by training a simple GNN consisting of a MP layer followed by MaxCutPool and trained by minimizing only the loss in Eq. 5 (details in Appendix C.2).
We use a Graph Isomorphism Network (GIN) layer (Xu et al., ) as the MP layer.
We compare our model against the LEVS approach based on ${\bm{u}}_{\text{max}}$, the GW algorithm, and a GNN with GCN layers that minimize a MAXCUT loss, as proposed by Schuetz et al. ().
For a fair comparison, ours and this GNN architecture have a comparable number of learnable parameters.

We considered $9$ graphs generated via the PyGSP library (Defferrard et al., ), including bipartite graphs such as the Grid2D and Ring, and $7$ graphs from the GSet dataset (Ye, ), including random, planar, and toroidal graphs, typically used as benchmark for evaluating MAXCUT algorithms (details in App. D.1).
Results are shown in Tab. 2.
Performance is computed in terms of the percentage of cut edges: the higher, the better.
With one exception, MaxCutPool always finds the best cut.

**Table 2: Size of the graph cuts obtained with MaxCutPool, a GNN with GCN layers, and two common algorithms to compute the MAXCUT. GW results are absent for some entries of the PyGSP datasets and for GSet because the solver failed to converge.**
| Dataset | GW | NDP | GCN | MaxCutPool |
| --- | --- | --- | --- | --- |
| BarabasiAlbert | 0.6875 | 0.6589 | 0.7240 | 0.7292 |
| Community | 0.6767 | 0.6429 | 0.6805 | 0.6814 |
| ErdősRenyi | 0.6920 | 0.6858 | 0.6797 | 0.7105 |
| Grid (10$\times$10) | 1.0000 | 1.0000 | 0.9222 | 1.0000 |
| Grid (60$\times$40) | - | 0.9787 | 0.1862 | 0.9815 |
| Minnesota | - | 0.9104 | 0.8904 | 0.9130 |
| RandRegular | 0.4827 | 0.8760 | 0.8733 | 0.9040 |
| Ring | 1.0000 | 1.0000 | 0.4200 | 1.0000 |
| Sensor | 0.6000 | 0.5719 | 0.6281 | 0.6406 |

### 4.2 Graph classification

For this task, we evaluate the classification accuracy of a GNN classifier with the following structure: MP (32)-Pool-MP (32)-Readout, using GIN as the MP layer.
The Pool operation is implemented either by MaxCutPool or by the following competing methods:
Diffpool (Ying et al., ), DMoN (Tsitsulin et al., ),
MinCutPool (Bianchi et al., ),
Top-$k$ (Gao & Ji, ),
Graclus (Dhillon et al., ),
$k$-MIS (Bacciu et al., ).
We also consider Edge-Contraction Pooling (ECPool) (Diehl, ) that pools the graph by contracting the edge connecting similar nodes.
For MaxCutPool, we evaluate three variants:
(i) MaxCutPool, the standard version;
(ii) MaxCutPool-E, the variant with expressive CON;
(iii) MaxCutPool-NL, where “NL” stands for “no loss”, meaning we do not optimize the auxiliary loss in the GNN. This serves as an ablation study to assess the importance of the auxiliary loss.
Whenever edge attributes are available, the first GIN layer is replaced by a GINE layer (Hu et al., ), which takes into account edge attributes. Further implementation details are in Appendix C.3.

As graph classification datasets we consider $8$ TUD datasets (COLLAB, DD, NCI1, ENZYMES, MUTAG, Mutagenicity, PROTEINS, and REDDIT-BINARY) (Morris et al., ), the Graph Classification Benchmark Hard (GCB-H) (Bianchi et al., ), and EXPWL1 (Bianchi & Lachi, ), which is a recent dataset for testing the expressive power of GNNs.
In addition, we introduce a novel dataset consisting of $5,000$ multipartite graphs:
each graph is complete $10$-partite, meaning that the nodes can be partitioned into $10$ groups so that the nodes in each group are disconnected, but are connected to all the nodes of the other groups.
To the best of our knowledge, this is the first benchmark dataset for graph classification with heterophilic graphs.
While the Multipartite dataset consists of complex graph structures, the classification label is determined solely by the node features, allowing us to assess whether the GNN can effectively isolate relevant information despite the presence of misleading topological information.
The construction of the Multipartite dataset and a further discussion about its properties are reported in Appendix D.2.

Whenever the node features were not available, we used node labels.
If node labels were also unavailable, we used a constant as a surrogate node feature. Further details about the remaining datasets can be found in Appendix D.3.
The datasets were split via a $10$-fold cross-validation procedure.
The training dataset was further partitioned into a 90-10% train-validation random split.
This approach is similar to the procedure described by Errica et al. ().
Each model was trained for $1,000$ epochs with early stopping, keeping the checkpoint with the best validation accuracy.

Table: Table 3: Mean and standard deviations of the graph classification accuracy. For each dataset the best performing method and those that are not significantly different from it are colored in green. If a method is in the top-performing group is assigned with a score of $1$, 0 0 otherwise.

The results are reported in Tab. 3.
For completeness, we also reported the performance of the same GNN model without pooling layers (“No pool”).
We conducted a preliminary ANOVA test ($p$-value $0.05$) for each dataset followed by a pairwise Tukey-HSD test ($p$-value $0.05$) to group models whose performance is not significantly different.
Those belonging to the top-performing group are colored in green.
The ANOVA test failed on ENZYMES, PROTEINS, MUTAG, and DD, meaning that the difference in the performance of the GNNs equipped with different poolers is not significant. For this reason, the results on these datasets are omitted from Tab. 3 and reported in Appendix E.1.

MaxCutPool consistently ranks among the top-performing methods across all evaluated datasets.
Notably, on the EXPWL1 even the non-expressive variant of MaxCutPool achieves a perfect accuracy (100%), outperforming the competitors. 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 ().
On the Multipartite dataset, MaxCutPool performs significantly better than every pooling method.
When compared to the “No pool” baseline, on most datasets MaxCutPool improves the classification performance by increasing the receptive field of the MP layers while retaining only the necessary information and enhancing the overall expressive power of the GNN model.
It is worth noting that the EXPWL1 and Multipartite are the least homophilic datasets (see Appendix D.3), indicating that MaxCutPool is particularly effective for heterophilic graphs.
On the COLLAB dataset, all MaxCutPool variants achieve the top accuracy of $77\%$, showing a statistically significant improvement over other methods. Notably, in the MaxCutPool and MaxCutPool-E variants the auxiliary loss term plateaued around 0 0, making them equivalent to the MaxCutPool-NL variant that, in this case, achieves the same performance.
This indicates that our method remains robust even when the auxiliary loss is not needed for the downstream task.
Overall, the MaxCutPool-E variant, which satisfies expressiveness conditions, exhibits similar or better performance compared to MaxCutPool across most datasets. In contrast, the performance decline observed in the MaxCutPool-NL variant demonstrates the importance of the auxiliary loss.

### 4.3 Node classification

For this task, we adopted a simple auto-encoder architecture for node classification: MP ($32$)-Pool-MP ($32$)-Unpool-MP ($32$)-Readout, with GIN as MP.
The Unpool operation (also referred to as *lifting* (Jin et al., )) is implemented by copying in each node $i$ the value of the supernode $j$ to which the $i$ was assigned by the SEL operation in the pooling phase.
Zero-padding is used when lifting nodes not assigned to any supernode, like in the case of Top-$k$.
Further details about the architecture for node classification and the unpooling procedure are deferred to Appendix C.4.

For this experiment, we considered the $5$ heterophilic datasets presented in Platonov et al. () (details in Appendix D.4).
As pooling methods we considered Top-$k$ (Gao & Ji, ), $k$-MIS (Bacciu et al., ), NDP (Bianchi et al., ), and MaxCutPool.
We did not consider Graclus or any soft-clustering poolers, as they were exhausting the RAM and GPU VRAM, respectively, given the large size of the graphs.
On the other hand, MaxCutPool is very parsimonious in terms of computational resources and scales very well with the graph size.
To systematically estimate the space complexity of the different pooling methods we performed an experimental evaluation of the GPU VRAM usage, which can be found in Appendix E.3.

Following Platonov et al. (), in Tab. 4 we report the means and standard deviations of the accuracy for Roman-empire and Amazon-ratings, and of the ROC AUC for Tolokers, Minesweeper, and Questions.
The results are computed on the $10$ public folds of these datasets.

Table: Table 4: Node classification accuracy (Roman-empire, Amazon-ratings) and AUROC (Minesweeper, Tolokers, Questions). The best performing models in each dataset are in green and get 1 score point, 0 otherwise.

When configured with MaxCutPool and MaxCutPool-E, the node classification architecture achieves significantly superior performance on the Roman-Empire dataset, which is notably the most heterophilic among all the datasets (see Tab. 11).
On the remaining datasets, our method performs well overall.
Unlike the other pooling methods that achieve top performance only on a subset of the datasets, MaxCutPool-E is consistently in the top tier.

## 5 Conclusion

This work contributes significantly to both the MAXCUT optimization and the development of specialized GNN architectures to solve combinatorial optimization problems with GNNs.
Our proposed GNN-based MAXCUT algorithm not only extends the MAXCUT optimization to attributed graphs and combines it with task-specific losses but also surpasses the performances of traditional methods on non-attributed graphs.
While a conventional GNN with a huge capacity manages to optimize a MAXCUT loss (Schuetz et al., ), our model is much more efficient thanks to the Heterophilic Message Passing layers.
This results highlight the importance of aligning the GNN architecture with the problem’s inherent structure: in this case, leveraging heterophilic propagation to solve problems that seek dissimilarity between neighboring nodes.

Our second contribution is to utilize the proposed MAXCUT optimizer to implement a graph pooling method that combines the flexibility of soft-clustering approaches with the efficiency of score-based methods and with the theoretically-inspired design of one-every-$K$ strategies. GNNs for graph and node classification equipped with our proposed pooling layer consistently achieves superior performance across diverse downstream tasks.
Differently from existing graph pooling and graph coarsening approaches that aim at preserving low-frequencies on the graph (Loukas, ), our method performs exceptionally well also on heterophilic datasets.
While our pooling layer can implement any pooling ratio, the auxiliary loss is optimized for the node partition induced by the MAXCUT, whose size might not be aligned with the specified pooling ratio. When the distribution of the nodes’ degree is approximately uniform, the MAXCUT induces an approximately balanced partition corresponding to a pooling ratio of $\approx 0.5$, which is, thus, generally a good choice.

Looking forward, we see great potential in pretraining GNNs with auxiliary losses. This aligns with the principles of foundational models (Bommasani et al., ) and could facilitate the development of more effective and general-purpose graph pooling techniques.

## Appendix

## Appendix A Nearest neighbor association algorithm

As discussed in Sec. 3, each node is associated to one of the supernodes (preferably the closest in terms of path-distance on the graph).
Naively searching for each node the closest supernode is computationally demanding and becomes intractable for large graphs.
Therefore, we propose an implementation of the assignment scheme that is efficient and can be easily parallelized on a GPU.
The proposed algorithm is based on a Breadth First Search (BFS) of the graph and is detailed in the pseudo-code in Algorithm 1.

Figure: Algorithm 1 Pseudo-code for the assignment scheme to the supernodes

The algorithm takes as input the graph ${\mathcal{G}}$ (in particular, its topology described by the adjacency matrix ${\bm{A}}$), the set of $K$ supernodes ${\mathcal{S}}$ identified by the SEL operation, and a maximum number of iterations ($MaxIter$), which represent the maximum number of steps a node can traverse the graph to reach its closest supernode before being assigned at random.

In line 2, an encoding matrix ${\bm{E}}$ of size $N\times K+1$ is initialized so that row $i$ is a one-hot vector with the non-zero entry in position $k+1$, if the node $i$ of the original graph is the $k$-th supernode. Otherwise, row $i$ in a zero-vector of size $K+1$. This matrix will be gradually populated when supernodes are encountered during the BFS. It’s important to note that the 0 0-th column in matrix ${\bm{E}}$ (and subsequently in ${\bm{E}}^{\prime}$) serves a special purpose. This column represents a “fake” supernode, which plays a crucial role in the assignment process.

A Boolean mask ${\bm{m}}\in\{0,1\}^{N}$ indicating whether a node already encountered the closest supernode is initialized in line 3 with $1$ in position $i$ is nodes $i$ is a supernode and 0 0 otherwise.
Finally, an empty list indicating to which supernode each node is assigned is initialized (line 4).

Until the maximum number of iterations is reached or until all nodes are assigned (line 6), the encoding matrix ${\bm{E}}$ is propagated with an efficient message passing operation (line 9) that can be parallelized on a GPU. As soon as a $1$ appears in position $k$ within a line $i$ of ${\bm{E}}$ previously full of zeros, node $i$ is assigned to supernode $k$ and the assignments and mask ${\bm{m}}$ are updated accordingly (lines 10 and 11).
The *ParallelAssignment* function (line 10), in particular, takes the rows of the newly generated embeddings ${\bm{E}}^{\prime}$ that have not yet been assigned and performs an argmax operation on the last dimension. If the argmax doesn’t find any valid supernode for a node (*i.e.*, all values in the row are zero), it returns 0, effectively assigning the node to the “fake” supernode represented by the 0 0-th column. This allows to filter out the unassigned nodes in line 11.

If there are still unassigned nodes at the end of the iterations, the remaining nodes are randomly assigned to one of the $K$ supernodes (line 15).
Finally, all the assignments are merged (line 17).

## Appendix B Derivation of the auxiliary loss

Let us consider the MAXCUT objective in Equation 1.
It can be rewritten as

$$ $\displaystyle\max_{{\bm{z}}}\Bigg{(}\sum\limits_{i,j\in\mathcal{V}}w_{ij}-\sum \limits_{i,j\in\mathcal{V}}z_{i}z_{j}w_{ij}\Bigg{)}=\max_{{\bm{z}}}\Bigg{(}|E| -\sum\limits_{i,j\in\mathcal{V}}z_{i}z_{j}w_{ij}\Bigg{)},$ $$

which is equivalent to

$$ $\max_{{\bm{z}}}\Bigg{(}1-\sum\limits_{i,j\in\mathcal{V}}\frac{z_{i}z_{j}w_{ij} }{|E|}\Bigg{)}.$ $$

The solution ${\bm{z}}^{*}$ for the original objective is thus the solution for

$$ $\min_{{\bm{z}}}\frac{{\bm{z}}^{\top}A{\bm{z}}}{|E|}.$ $$

## Appendix C Implementation details

### C.1 MaxCutPool layer and ScoreNet

A schematic depiction of the MaxCutPool layer is illustrated in Fig. 3, where the SEL, RED, and CON operations are highlighted.

Figure: Figure 3: Scheme of the MaxCutPool layer.
Refer to caption: x18.png

SEL first computes a score vector $\bm{s}$ using the auxiliary GNN, ScoreNet, based on the node features $\mathbf{X}$ and the connectivity matrix $\mathbf{A}$.
A top-$K$ operation is used to find the indices $\bm{i}$ of the $K$ nodes with the highest scores that become the supernodes, *i.e.*, the nodes of the pooled graph.
The remaining $N-K$ nodes are assigned to the nearest supernode through a nearest-neighbor (NN) aggregation procedure that yields an assignment matrix $\mathbf{S}$, whose $jk$-th element is $1$ if nodes $j$ is assigned to supernode $k$, and zero otherwise.
The score vector $\bm{s}$ is used to compute the loss ${\mathcal{L}}_{\text{cut}}$, which is associated with each MaxCutPool layer.

The RED operation computes the node features of the pooled graph ${\bm{X}}^{\prime}$ by multiplying the features of the selected nodes ${\bm{X}}_{i}$ with the scores $\bm{s}$.
This operation is necessary to let the gradients flow past the top-$K$ operation, which is not differentiable.
In the expressive variant, MaxCutPool-E, RED computes the new node features by combining those from all the nodes in the graph through the multiplication with matrix ${\bm{S}}$.
We combine the features by summing them instead of taking the average since the sum enhances the expressiveness of the pooling layer (Bianchi & Lachi, ).

The CON operations always leverage the assignment matrix to compute the adjacency matrix of the pooled graph.
In particular, the edge connecting two supernodes $i$ and $j$ is obtained by coalescing all the edges connecting the nodes assigned to supernode $i$ with those assigned to supernode $j$.
Also in this case, we take the sum as the operation to coalesce the edges.
The resulting edges in the pooled graph are associated with a weight $w_{ij}$ that counts the number of combined edges.

The details of the ScoreNet used in the MaxCutPool layer are depicted in Fig. 4.
The ScoreNet consists of a linear layer that maps the features ${\bm{X}}$ to a desired hidden dimension.
Afterward, a stack of HetMP layers gradually transforms the node features by amplifying their high-frequency components with heterogeneous MP operations.
Finally, an MLP transforms the node features of the last HetMP layer into score vector ${\bm{s}}$, which is a high-frequency graph signal.

Figure: Figure 4: Scheme of the ScoreNet.
Refer to caption: x19.png

We note that while the simple HetMP we adopted works well in our case, different heterophilic MP operators could have been considered (Chien et al., ; Dong et al., ; Fu et al., ).

The ScoreNet is configured with the following hyperparameters:

- •
Number of HetMP layers and number of features in each layer. We use the notation $[32,16,8]$ to indicate a ScoreNet with three HetMP layers with hidden sizes $32$, $16$, and $8$, respectively. We also use the notation $[32]\times 4$ to indicate $4$ layers with $32$ units each. As default, we use $[32,32,32,32,16,16,16,16,8,8,8,8]$.
- •
Activation function of the HetMP layers. As default, we use TanH.
- •
Number of layers and features in the MLP. As default, we use $[16,16]$.
- •
Activation function of the MLP. As default, we use ReLU.
- •
Smoothness hyperparameter $\delta$. As default, we use $2$.
- •
Auxiliary loss weight $\beta$. As default, we use $1$.

The optimal configuration has been identified with the cross-validation procedure described in Sec.4.
Depending on the experiment and the GNN architecture, some parameters in the ScoreNet are kept fixed at their default value while others are optimized.

### C.2 Cut model

The model used to compute the MAXCUT is depicted in Fig. 5. The model consists of a single MP layer followed by the ScoreNet, which returns the score vector $\bm{s}$.

Figure: Figure 5: Scheme of the model used for computing the MAXCUT.
Refer to caption: x20.png

The MAXCUT partition is obtained by rounding the values in the score vector as follows

$$ $y_{i}=\begin{cases}1&\text{if}\;s_{i}>0,\\ -1&\text{otherwise}.\end{cases}$ $$

The model is trained in a completely unsupervised fashion only by minimizing the auxiliary loss ${\mathcal{L}}_{\text{cut}}$.

As MP layers we used a GIN (Xu et al., ) layer with $32$ units and ELU activation function. The model was trained for $2000$ epochs with Adam optimizer (Kingma & Ba, ), with the initial learning rate set to $8e-4$. We used a learning rate scheduler that reduces by $0.8$ the learning rate when the auxiliary loss does not improve for $100$ epochs. For testing, we restored the model checkpoint that achieved the lowest auxiliary loss.

The best configuration was found via a grid search on the following set of hyperparameters:

- •
HetMP layers and units:
–
$[32]\times 4$,
–
$[4]\times 32$,
–
$[8]\times 16$,
–
$[16]\times 8$,
–
$[32,32,32,32,16,16,16,16,8,8,8,8]$.
- •
HetMP activations:
–
ReLU,
–
TanH.
- •
Smoothness hyperparameter $\delta$:
–
2,
–
3,
–
5.

In Tab. 5 we report the configurations of the ScoreNet used for the different graphs in the MAXCUT experiment.

**Table 5: Hyperparameters configurations of the ScoreNet for the MAXCUT task.**
| Dataset | MP units | MP Act | $\delta$ |
| --- | --- | --- | --- |
| G14 | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | ReLU | 2.0 |
| G15 | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | ReLU | 2.0 |
| G22 | $[4]\times 32$ | TanH | 2.0 |
| G49 | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | TanH | 2.0 |
| G50 | $[8]\times 16$ | ReLU | 2.0 |
| G55 | $[4]\times 32$ | ReLU | 2.0 |
| G70 | $[8]\times 16$ | ReLU | 2.0 |
| BarabasiAlbert | $[4]\times 32$ | TanH | 2.0 |
| Community | $[4]\times 32$ | TanH | 2.0 |
| ErdősRenyi | $[4]\times 32$ | TanH | 2.0 |
| Grid2d (10$\times$10) | $[4]\times 32$ | TanH | 2.0 |
| Grid2d (60$\times$40) | $[4]\times 32$ | ReLU | 2.0 |
| Minnesota | $[4]\times 32$ | TanH | 2.0 |
| RandRegular | $[4]\times 32$ | TanH | 2.0 |
| Ring | $[4]\times 32$ | ReLU | 2.0 |
| Sensor | $[4]\times 32$ | TanH | 2.0 |

### C.3 Graph classification model

The model used to perform graph classification is depicted in Fig. 6.
The model consists of an MP layer, followed by a pooling layer, an MP acting on the pooled graph, a global pooling layer that sums the features of all the nodes in the pooled graph, and an MLP that produces the label $y$ associated with the input graph.

Figure: Figure 6: Scheme of the graph classification model.
Refer to caption: x21.png

The model is trained by jointly minimizing the cross-entropy loss between the predicted graph labels and the true ones and the auxiliary losses associated with the different pooling layers.
The models are trained using a batch size of $32$ for $1000$ epochs, using the Adam optimizer with an initial learning rate of $1e-4$.
We used an early stopping that monitors the validation loss with a patience of $300$ epochs. For testing, we restored the model checkpoint that achieved the lowest validation loss during training.

The best configuration was found via a grid search on the following set of hyperparameters:

- •
HetMP layers and units:
–
$[32]\times 8$,
–
$[32]\times 4$,
–
$[8]\times 16$, $[16]\times 8$,
–
$[32,32,16,16,8,8]$,
–
$[32,32,32,32,16,16,16,16,8,8,8,8]$.
- •
Auxiliary loss weight $\beta$:
–
1,
–
2,
–
5.

**Table 6: Hyperparameters configurations of the ScoreNet for the graph classification task.**
|  | MaxCutPool | MaxCutPool-E |  |  |
| --- | --- | --- | --- | --- |
| Dataset | MP units | $\beta$ | MP units | $\beta$ |
| GCB-H | $[8]\times 16$ | 3.0 | $[32]\times 8$ | 5.0 |
| COLLAB | $[32]\times 8$ | 1.0 | $[32]\times 8$ | 1.0 |
| DD | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | 1.0 | $[8]\times 16$ | 5.0 |
| ENZYMES | $[8]\times 16$ | 3.0 | $[16]\times 8$ | 3.0 |
| EXPWL1 | $[32,32,16,16,8,8]$ | 1.0 | $[16]\times 8$ | 1.0 |
| MUTAG | $[8]\times 16$ | 1.0 | $[16]\times 8$ | 3.0 |
| Multipartite | $[32]\times 8$ | 3.0 | $[32]\times 8$ | 1.0 |
| Mutagenicity | $[32,32,16,16,8,8]$ | 1.0 | $[32]\times 8$ | 5.0 |
| NCI1 | $[32,32,16,16,8,8]$ | 1.0 | $[8]\times 16$ | 3.0 |
| PROTEINS | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | 3.0 | $[32,32,16,16,8,8]$ | 5.0 |
| REDDIT-B | $[32]\times 8$ | 1.0 | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | 1.0 |

In Tab. 6 we report the configurations of the ScoreNet used in the graph classification architecture for the different datasets in the expressive and non-expressive variant of MaxCutPool.

### C.4 Node classification model

Figure: Figure 7: Scheme of the node classification model.
Refer to caption: x22.png

The model used to perform node classification is depicted in Fig. 7.
The model consists of an MP layer, followed by a pooling layer, an MP acting on the pooled graph, an unpooling (lifting) layer, an MP on the unpooled graph, and an MLP that produces the final node labels $\bm{y}$.

The entry $y_{i}$ represents the predicted label for node $i$.
The model is trained by jointly minimizing the cross-entropy loss between the predicted node labels and the true ones and the auxiliary loss of the pooling layer.

Figure: Figure 8: The two possible strategies for performing unpooling (lifting).
Refer to caption: x23.png

When using MaxCutPool, the unpooling/lifting procedure can be implemented in two different ways, illustrated in Fig. 8.
The first strategy, *broadcast* unpooling, copies the values ${\bm{X}}^{\prime}$ of the nodes of the pooled graph to both the corresponding supernodes and to the nodes associated with the supernodes according to the assignment matrix ${\bm{S}}$, obtained as described in Sec. 3 and Appendix A. Formally, the unpooled node features $\tilde{{\bm{X}}}$ are:

$$ $\tilde{{\bm{X}}}={\bm{S}}{\bm{X}}^{\prime}.$ $$

We note that this is the commonly used approach to perform unpooling in cluster-based poolers.

In the second strategy, *padding* unpooling, the values ${\bm{X}}^{\prime}$ are copied back only to the supernodes, while the remaining nodes are padded with a zero-valued vector:

$$ $[\tilde{{\bm{X}}}]_{i}=\begin{cases}[{\bm{X}}^{\prime}]_{i}&\text{if $i$ is a supernode}\\ \bm{0}&\text{otherwise}.\end{cases}$ $$

This is the approach to perform unpooling used by score-based approaches such as Top-$k$ and by one-over-$K$ approaches such as NDP that only select the supernodes and leave the remaining nodes unassigned.

For the node classification task presented in Sec. 4.3, as MP layers we used a GIN (Xu et al., ) layer with $32$ units and ReLU activation function.
The MLP has a single hidden layer with $32$ units, a ReLU activation function, and a dropout layer between the hidden and output layers with a dropout probability of $0.1$.
The unpooling strategy used in this architecture is the broadcast one for $k$-MIS and MaxCutPool and the padding one for Top-$k$ and NDP.

The best configuration was found via a grid search on the following set of hyperparameters:

- •
HetMP layers and units:
–
$[32]\times 4$,
–
$[4]\times 32$,
–
$[32,32,32,32,16,16,16,16,8,8,8,8]$.
- •
MLP activations:
–
ReLU,
–
TanH.

The configuration of the ScoreNet for the MaxCutPool pooler used in the different datasets is reported in Tab. 7.

**Table 7: Hyperparameters configurations of the ScoreNet in the node classification task.**
| Dataset | MP units | MLP Act. |
| --- | --- | --- |
| Roman-Empire | $[32,32,32,32]$ | ReLU |
| Amazon-Ratings | $[32,32,32,32]$ | ReLU |
| Minesweeper | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | ReLU |
| Tolokers | $[32,32,32,32,16,16,16,16,8,8,8,8]$ | ReLU |
| Questions | $[32,32,32,32]$ | ReLU |

The node classifier was trained for $20,000$ epochs, using the Adam optimizer with an initial learning rate of $5e-4$.
We used a learning rate scheduler that reduces by $0.5$ the learning rate when the validation loss does not improve for $500$ epochs.
We used an early stopping that monitors the validation loss with a patience of $2,000$ epochs. For testing, we restored the model checkpoint that achieved the lowest validation loss during training.

We considered also an additional architecture for node classification with skip (residual) connections, depicted in Fig. 9.

Figure: Figure 9: Scheme of the node classification model with skip connections.
Refer to caption: x24.png

This architecture is similar to the Graph U-Net proposed by Gao & Ji ().
The node features obtained after the first MP layer are concatenated to the node features generated by the unpooling step.
In this architecture, we used the broadcast unpooling for $k$-MIS and padding unpooling for MaxCutPool, Top-$k$, and NDP.
The results obtained with this architecture are reported in App. E.
In Tab. 8 we report the configurations of the ScoreNet used in the architecture with skip connection in the different datasets.

**Table 8: Hyperparameters configurations for the node classification task based on the architecture with skip connections.**
| Dataset | MP units | MLP Act. |
| --- | --- | --- |
| Roman-Empire | [32, 32, 32, 32] | ReLU |
| Amazon-Ratings | [32, 32, 32, 32] | ReLU |
| Minesweeper | [32, 32, 32, 32] | TanH |
| Tolokers | [32, 32, 32, 32] | ReLU |
| Questions | [32, 32, 32, 32] | ReLU |

### C.5 Implementation of other pooling layers

The pooling methods Top-$k$, Diffpool, DMoN, Graclus, and MinCutPool are taken from PyTorch Geometric (Fey & Lenssen, ).
For $k$-MIS we used the official implementation (^2^22[https://github.com/flandolfi/k-mis-pool](https://github.com/flandolfi/k-mis-pool)).
For ECPool, we used the efficient parallel implementation (^3^33[https://github.com/flandolfi/edge-pool](https://github.com/flandolfi/edge-pool)) proposed by Landolfi ().
For NDP we adapted to PyTorch the original Tensorflow implementation (^4^44[https://github.com/danielegrattarola/decimation-pooling](https://github.com/danielegrattarola/decimation-pooling)).
All pooling layers were used with the default hyperparameters.
Since $k$-MIS does not allow to directly specify the pooling ratio, we set $k=\lfloor 1/k\rfloor$.

## Appendix D Datasets details

### D.1 Cut datasets

The statistics of the PyGSP and the Gset datasets used to compute the MAXCUT partition in Sec. 4.1 are reported in Tab. 9.
While the PyGSP graphs are built from the library (Defferrard et al., ), the Gset dataset is downloaded from the original source (^5^55 [http://web.stanford.edu/~yyye/yyye/Gset/](http://web.stanford.edu/~yyye/yyye/Gset/)).

**Table 9: Statistics of the PyGSP datasets used to compute the MAXCUT.**
| Dataset | # Nodes | # Edges | Vertex attr. |
| --- | --- | --- | --- |
| Barabasi-Albert | 100 | 768 | 2 |
| Community | 90 | 532 | 2 |
| Erdős-Renyi | 100 | 974 | 2 |
| Grid2d (10$\times$10) | 100 | 360 | 2 |
| Grid2d (60$\times$40) | 2,400 | 9400 | 2 |
| Minnesota | 2642 | 6608 | 2 |
| RandRegular | 500 | 1500 | 2 |
| Ring | 100 | 200 | 2 |
| Sensor | 64 | 640 | 2 |

### D.2 Multipartite dataset description

Figure: Algorithm 2 Multipartite graph dataset generation

The Multipartite graph dataset is a synthetic dataset consisting of complete multipartite graphs. The nodes of each graph can be partitioned into $C$ clusters of independent nodes, such that every node is connected to every node belonging to every other cluster.
The generation of the graphs and the class labels is formally described by the pseudo-code in Algorithm 2 and is discussed in the following.

- 1.
A set of $C$ cluster centers with 2D coordinates $(x,y)$ is initially arranged in a polygon shape. Each center is associated with a label, *i.e.*, a color.
- 2.
The graph class is determined by the position and the color of the cluster centers. Specifically, the graph class is given by the color of the cluster whose center is on the positive $x$-axis.
- 3.
For each class, we generate multiple graphs using these cluster centers. A graph is created by drawing at random the position of the nodes around each cluster center. The number of nodes per cluster varies randomly up to a maximum. Nodes within a cluster share the same color, which is determined by the cluster center.
- 4.
The topology of each graph is obtained by connecting nodes from one cluster to the nodes of all the other clusters, but not to the nodes of the same cluster. Therefore, a node is connected only to nodes with different colors, making the graphs highly heterophilic.
- 5.
After generating graphs for one class, the cluster centers are rotated, and this rotated configuration is used for the next class. Indeed, each rotation brings a different cluster to the positive $x$-axis.
- 6.
The rotation process continues until the graphs for all the $C$ different classes, whose number is equal to the number of clusters, are generated.

Figure: Figure 10: Example of multipartite graphs with $C=3$ cluster centers generated via our procedure. The graph class corresponds to the color of the nodes from the group to the right.
Refer to caption: x25.png

Examples of multipartite graphs obtained for $C=3$ are shown in Figure 10.

The process depends on a few parameters that determine the number of clusters, the maximum nodes per cluster, and the number of graphs per class, providing control over the dataset size and complexity. The specific instance of the dataset used in our experiments has $10$ centers, $500$ graphs per center, and a maximum of $20$ nodes per cluster, and is available online (^6^66 [https://zenodo.org/doi/10.5281/zenodo.11616515](https://zenodo.org/doi/10.5281/zenodo.11616515)).

The Multipartite dataset is intentionally designed so that the class label is determined solely by node features: specifically, the color and one of the 2D coordinates (the node’s position along the $x$-axis). Although the graph’s topology is structured to ensure that each graph is multipartite, this structure is independent of the class label. This creates an intriguing dichotomy between the graph’s topology and its classification labels.
In theory, a simple MLP focusing exclusively on node features could accurately solve the classification task, as the graph’s topology is essentially irrelevant for determining the correct labels. However, when processed by GNNs, this dataset allows us to explore whether the model can correctly identify and utilize the relevant node features for classification, despite the presence of potentially misleading or noisy topological information.
Through this carefully constructed dataset, we aim to highlight the strengths and potential limitations of certain GNNs architectures, particularly in scenarios where the relationship between graph structure and classification labels is non-trivial, such as in heterophilic datasets.

### D.3 Graph classification datasets

In addition to the novel Multipartite dataset introduced in Sec. D.2, we consider $10$ additional datasets for graph classification in our experimental evaluation.
The TU Datasets (Morris et al., ) (NCI, PROTEINS, Mutagenicity, COLLAB, REDDIT-B, DD, MUTAG, and Enzymes) are obtained through the loader of PyTorch Geometric (^7^77[https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.datasets.TUDataset.html](https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.datasets.TUDataset.html)).
The EXPWL1 and GCB-H datasets, respectively introduced by Bianchi & Lachi () and by Bianchi et al. (), are taken from the official repositories (^8^88[https://github.com/FilippoMB/The-expressive-power-of-pooling-in-GNNs](https://github.com/FilippoMB/The-expressive-power-of-pooling-in-GNNs)) (^9^99[https://github.com/FilippoMB/Benchmark_dataset_for_graph_classification](https://github.com/FilippoMB/Benchmark_dataset_for_graph_classification)).
The statistics of each dataset are reported in Tab. D.3.

**Table 10: Details of the graph classification datasets.**
| Dataset | #Samples | #Classes | Avg. #vert. | Avg. #edg. | V. attr. | V. lab. | $\bm{\bar{h}({\mathcal{D}})}$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 5pt.<br>EXPWL1 | 3,000 | 2 | 76.96 | 186.46 | – | yes | 0.2740 |
| NCI1 | 4,110 | 2 | 29.87 | 64.60 | – | yes | 0.6245 |
| PROTEINS | 1,113 | 2 | 39.06 | 72.82 | 1 | yes | 0.6582 |
| Mutagenicity | 4,337 | 2 | 30.32 | 61.54 | – | yes | 0.3679 |
| COLLAB | 5,000 | 3 | 74.49 | 4,914.43 | – | no | 1 |
| REDDIT-B | 2,000 | 2 | 429.63 | 995.51 | – | no | 1 |
| GCB-H | 1,800 | 3 | 148.32 | 572.32 | – | yes | 0.8440 |
| DD | 1,178 | 2 | 284.32 | 1,431.32 | – | yes | 0.0688 |
| MUTAG | 188 | 2 | 17.93 | 19.79 | – | yes | 0.7082 |
| ENZYMES | 600 | 6 | 32.63 | 62.14 | 18 | yes | 0.6687 |
| Multipartite | 5000 | 10 | 99.79 | 4,477.43 | 3 | yes | 0.1101 |

### D.4 Node classification datasets

The datasets are the heterophilic graphs introduced by Platonov et al. () and are loaded with the API provided by PyTorch Geometric (^10^1010[https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.datasets.HeterophilousGraphDataset.html](https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.datasets.HeterophilousGraphDataset.html)).
The nodes of each graph are already split in train, validation, and test across 10 different folds.
The statistics of the five datasets are reported in Tab. 11.

**Table 11: Statistics of node classification datasets.**
| Dataset | # Nodes | # Edges | # Classes | $\bm{h({\mathcal{G}})}$ |
| --- | --- | --- | --- | --- |
| Roman-Empire | 22,662 | 32,927 | 18 | 0.021 |
| Amazon-Ratings | 24,492 | 93,050 | 5 | 0.127 |
| Minesweeper | 10,000 | 39,402 | 2 | 0.009 |
| Tolokers | 11,758 | 519,000 | 2 | 0.180 |
| Questions | 48,921 | 153,540 | 2 | 0.079 |

The column $h({\mathcal{G}})$ is the class insensitive edge homophily ratio as defied by Lim et al. (), which represents a measure for the level of homophily in the graph.

## Appendix E Additional results

### E.1 Graph classification

In Tab. 12 we report the additional graph classification results for the dataset where GNNs equipped with different pooling operators did not achieve a significantly different performance from each other.

Table: Table 12: Graph classification accuracy values (subset)

### E.2 Node classification

Tab. 13 presents the results for node classification using the architecture with skip connections described in Appendix C.4. For this architecture, we focused on the non-expressive variant of MaxCutPool, which consistently delivered superior performance in this context.
The improved results can be attributed to the architecture’s ability to preserve the original node information through skip connections. Additionally, by avoiding the combination of neighboring node features (as is done in the expressive variant) the model is better equipped to learn high-frequency features, which is particularly advantageous for heterophilic datasets.

Table: Table 13: Node classification accuracy (Roman-empire, Amazon-ratings) and AUROC (Minesweeper, Tolokers, Questions) obtained when using the architecture with skip connections.

For the Minesweeper dataset, we chose to use a GIN layer with $16$ units as the MP layer, instead of the usual $32$ units. This decision was made because, regardless of the pooling method used, the architecture with skip connections consistently achieved nearly $100$% ROC AUC whenever configured with a higher capacity.

### E.3 Memory usage

In Figure 11 we report the GPU VRAM usage of the different poolers. This has been evaluated on randomly generated Erdős-Renyi graphs with a $0.01$ probability of connection.

Figure: Figure 11: The GPU VRAM usage of the different poolers.
Refer to caption: extracted/5844878/figs/gpu_usage_plot.png

The plot shows that in soft-clustering methods the GPU VRAM usage grows exponentially with the graph size.
On the other hand, for score-based methods, including the proposed MaxCutPool, the growth is sublinear, making these approaches extremely suitable for working with large graphs.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: See weaknesses.
soundness: 3
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.
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.
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.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 3
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?
soundness: 3
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.
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.
weaknesses: Please refer to the questions below.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 2
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
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.
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.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
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?
soundness: 3
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.
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.
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.

Meta-review: **(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.

Decision: Accept (Poster)