MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks
Authors: Carlo Abate
Filippo Maria Bianchi
Venue: ICLR 2025 Poster (2025)
Keywords: Graph neural networks
graph pooling
graph coarsening
maxcut
Primary area: learning on graphs and other geometries & topologies
TL;DR: A GNN-based approach for computing MAXCUT on attributed graphs, used to implement graph pooling.

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.

Published as a conference paper at ICLR 2025
MAXCUTPOOL: DIFFERENTIABLE FEATURE-AWARE MAXCUT FOR POOLING IN GRAPH NEURAL NETWORKS
Carlo Abate
Filippo Maria Bianchi
Alma Mater Studiorum University of Bologna Fondazione Istituto Italiano di Tecnologia ca carlo. aba eeiit..i
UiT the Arctic University of Norway
NORCE Norwegian Research Centre AS fi filippo.. m bianchi bianchiiuii.....
ABSTRACT
We propose novel approach to compute the MAXCUT in attributed graphs, i.e., graphs with features associated with nodes and edges. Our approach works well 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 hierarchical graph pooling layer for Graph Neural Networks, which is spanse, trainable end-to-end, and particularly suitable for downstream tasks on heterophilic graphs.
INTRODUCTION
The MAXCUT' the problem of partitioning the nodes of a graph such that many edges possible connect nodes from different sides of the partition. The MAXCUT is orthogonal to the more commonly encountered minCUT, which aims 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 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., 2014).
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 naturally related to MAXCUT and mi min problems, respectively. Similarly to CNNs, Graph Neural Networks (GNNs), which can be seen as generalization to irregular data, can be built by alternating Message Passing (MP) and graph pooling layers (Zhou et al., 2020a). 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 al., 2020), node classification (Gao & Ji, 2019; Ma et al., 2020), graph matching (Liu et al., 2021). and spatio-temporal forcasting (Cini et al., 2024; Marisca et al., 2024).
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 computation of the coarsened graph. Combining the first approach with mi nCUT objectives relatively straightforward, as they complement the smoothing effect of MP layers (Hansen & Bianchi, 2023). Conversely, objectives such as MAXCUT that select sparse and uniformly distributed subsamples of nodes have been implemented far only within -in-eifferentiable frameworks, which account neither for node features nor for task objectives (Luzhnica et al., 2019).
1.1 CONTRIBUTIONS
MAXCUT for attributed graphs. Our first contribution is graph theoretical and consists of a novel GNN-based approach compute MAXCUT partition in attributed graphs. Being differentiable,
Equull contribution

---

Published as a conference paper at ICLR 2025
method can be seamlessly integrated into 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 topologies. This makes our contribution relevant to every application of the MAXCUT problem, such as quantum computing (Zhou et al., 2020b), circuit design (Bashar et al., 2020), statistical physies (Borgs et al., 2012), material science (Liers et al., 2004), computer vision (Abbas & Swoboda, 2022), and quantitative finance (Lee & Constantinides, 2023).
con-attrbbtted graphs, it finds better cut most graph
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 MAXCJT partition. Our layer is the first to combine a graph theoretical MAXCJT objective with a pooling approach that is features-aware and trainable end-to-end. 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-ar pooling techniques.
Improved mooiigg-based pooling framework. We propose a simple and efficient scheme to assign nodes supernodes when computing the pooled graph. Our scheme can be applied not only to our method but to the whole family of sparse scoring-based graph pooling operators enhancing, in principle, their representational power. Importantly, we bridge the gap between scoring- -ased 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 heterophilic graphs, there is lack such datasets for graph classification. To fill this gap, we introduce a novel synthetic dataset that, knowledge, is the first of its kind.
BACKGROUND
2.1 THE MAXCUT PROBLEM AND THE CONTINUOUS RELAXATIONS
Let G = (V,E( be an undirected graph with non-negative weights on the edges, and let N be the number of nodes in G. A cut in is partition (S, S) where S C V. The MAXCUT problem consists of finding cut that maximizes the total volume of edges connecting nodes in S with those in V S. The MAXCUT objective can be expressed the integer quadratic problem
max
wy (1 222) s.t. 2 (-1.1),
JJE
where 2 E (-1,13 is an assignment vector indicating to which side of the partition each node is assigned to and Wij is the weight of the edge connecting nodes and j.
Like other discrete optimization problems of this kind, MAXCUT is NP-hard. The Goeman- Williamson (GW) algorithm (Goemans & Williamson, 1995) provides semidefinite relaxation of the integer quadratic problem, which makes it tractable:
max
Σ JJEV
W1y(1 x; xz))) s.t. |
=
where X NDD vectors X projected random hyperplane to split the nodes and assign them the two sides of the partition. This algorithm guarantces an expected cut size of .868 of the maximum cut.
a matrix whose rows are the continuous embeddings of the nodes in G. The
Another simple yet effective continuous relaxation is the largest eigenvector vertex selection (LEVS) method (Shuman et al., 2015). Let L be the Laplacian matrix associated to the graph G and let umax be the eigenvector of L associated the largest eigenvalue Amax- A cut in & can be found based on the polarity of the components of Umax- for instance by letting S = {i: u [i] 2 0). In the field of graph signal processing, the eigenvectors related to the largest eigenvalues of L are closely related to
2

---

Published as a conference paper at ICLR 2025
the operation of high-pass filtering of graph signal (Tremblay et al., 2018). Specifically, they used to design graph filters that amplify frequecyy components a signal, Le., the components that vary the most across adjacent nodes (Shuman al., 2013).
The MAXCUT problem is closely related to graph coloring, which aims at assigning different colors to adjacent nodes. In particular, the 2-colors approximate coloring (Aspvall & Gilbert, 1984) 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 partition that is orthogonal spectral clustering (von Luxburg, 2007).
(a)
(d)
20
0.0
(e)
(f)
(h)
50
20
0.5
9.5
(i)
(k)
(I)
Figure 1: Top row: Partitions induced by the sign of the elements in Umax The nodes are colored based the partition, and the red edges those not cut (the fewer, the better). Middle row: histograms of Umax inducing the partitions above. While in bipartite graphs the separation is sharp, the more graph is irregular and dense, the more the values clustered around zero, making difficult to find the optimal MAXCUT. Bottom row: histograms of the score vectors generated by our model, which always produce clear and sharp partition.
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 when the graph topology departs from the bipartite case (Trevisan, 2009). Fig. (a-hh) 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 GNNS
Let us consider graph G (X R NXF A AERNE AERNNN.. A basic MP operator can be described as
X' x
(3)
where is non linear activation function, θ trainable parameters, and P is a propagation operator matching the sparsity pattern of A. Each MP layer relies on a specific propagation operator. For instance, in Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017), the propagation operator is defined P D A where À A + I and D2 Σ5= A.j-
Due to the fixed, non-negative smoothing nature of common propagation operators, the repeated application of P can lead to over smoothing If that happens, the feature representations nodes become increasingly similar, hindering the function approximation capabilities of GNN, which can only learn smooth graph signals (Wu et al., 2019; Wang et al., 2019). In contrast, by combining smoothing propagation operators with sharpening ones, any kind of gradients be learned (Eliasof
3

---

Published as a conference paper at ICLR 2025
et al., 2023; Bianchi al., 2021). Since there is no universal definition for such operator, we rely on the formulation introduced by Bianchi (2022);
P - 8 (I A
8L
(4)
where ó a smoothness hyperparameter and L the symmetrically normalized Laplacian of g. As observed by Bianchi (2022), when ē = 0 the MP behaves like simple Multilayer Perceptron (MLP). Instead, when 8 = 1, the behavior close to that of a GCN, Finally, as noted by Eliasof et al. (2023), when 8 >> 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 the graph counterpart of the Laplacian sharpening kernels for images, mapping connected nodes to different values (Mather & Koch, 2022).
2.3 GRAPH POOLING
While there are profound differences between existing graph pooling approaches, most of them can be expressed through the Specifically, pooling operator POOL (A, X) + (A', X') can be expressed as the combination of three sub-operators:
(SRC) framework (Grattarola et al., 2022).
SEL: : (A, X) + S E RNK, is a selection operator that defines how the N original nodes are mapped the K pooled nodes, called supernodes, being S the selection matrix.
RED: (X, S) X' RXXF,, is reduction operator that yields the features of the supernodes. A common way to implement RED is X' = S X.
CON: (A, S) + A' E E R
0 is a connection operator that generates the new adjacency matrix and, potentially, edge features. Typically, CON is implemented as A' S AS or A' = S AS.
Different design choices for SEL, RED, and CON induce a taxonomy of the operators. For example, if any of SEL, RED, and CON is learned end-to-end, the pooling operators are called trainable, non-trainable otherwise. Relevant to this work are the families of pooling methods described below.
Soft-chustering methods, sometimes referred as dense (Grattarola al., 2022), assign each node to more than one supernode through a soft membership. Representatives methods such as DiffPool (Ying al., 2018), MinCutPool (Bianchi et al., 2020a), StruetPool (Yuan Ji, 2020), HoscPool (Duval & Malliaros, 2022), and Deep Modularity Networks (DMoN) (Tsitsulin et al., 2023), compute soft cluster assignment matrix S E R either with an MIP or an MP-layer operating on the node features and followed by so ftmax. Most of these methods are trainable and leverage unsupervised auxiliary loss functions to guide the formation of the clusters. 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, 2023). However, storing the soft assignments S is memory bottleneck for large graphs (see, e.g., the analysis of memory usage in Appendix F.3), and soft memberships make pooled graphs 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.
Scoring- based methods select supernodes from the original nodes based on a node scoring vector 8. The chosen nodes correspond to the top A elements of 8, where K can be a ratio of the nodes in each graph, making these methods adaptive to the graph size. Representatives such as Top-k Pooling (Top-k) (Gao & Ji, 2019; Knyazev et al., 2019), ASAPool (Ranjan et al., 2020). SAGPool (Lee et al., 2019), PanPool (Ma et al., 2020), TAPool (Gao et al., 2021), CGIPool (Pang et al., 2021), and IPool (Gao et al., 2022) 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., 2019; Noutahi al., 2019), scoring-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 chunk of strongly connected nodes with similar characteristics. Consequently, entire sections of the graph are not represented, reducing the expressiveness and lowering performance in downstream tasks (Wang et al., 2024).
One-every-K K methods leverage graph-theorrticet properties to select supernodes by subsampling the graph uniformly. For instance, ls Maximal Independent Sets Pooling (k-MIS) (Bacciu et al., 2023)
4

---

Published as a conference paper at ICLR 2025
identifies supernodes the members of maximal K-independent set, i.e., nodes separated by least K K-hops on the graph. Graclus (Dhillon et al., 2007: Defferrard et al., 2016) creates supernodes by merging the pairs of most connected nodes in the graph. SEP (Wu et al., 2022) partitions the node hierarchically according to a precomputed tree that minimizes the structural entropy of the graph. Node Decimation Pooling (NDP) (Bianchi et al., 2020b) divides the graph into two sets, V+ and V_, according to the partition induced by the components of Umax (see Section 2.1). One of the two sides of the partition is dropped (V-), while the other (V+) becomes the set of supernodes. While both Graclus and NDP can only reduce the number of nodes by approximately half, higher pooling ratios cone-every-2" 22) are achieved by applying them recursively K times. Nevertheless, they lack the same control of soft-clustering and scoring-based methods in fixing the size of the pooled graphs. Like the scoring-based methods, one-every-K K methods are adaptive and produce crisp cluster assignments. However, they are not trainable and precompute the pooled graph based on the topology without accounting for the node features or 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-K
X Not adaptive to graph size
X Pooling not uniform
X Limited flexibility
X Dense and not interpretable pooled graphs
X Not expressive
X Features agnostic
x
High memory cost
X Worse performance
X
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 MAXCUT solution, creating partitions that not only maximize the number of cut edges but also prioritize the selection of nodes that are optimal for the downstream task at hand. To reach this goal, it is necessary to overcome a tension between the effect of a standard MP layer and the MAXCUT: the former applies a smoothing operation that makes adjacent nodes similar, which is orthogonal to the objective of the latter. Therefore, to implement MAXCUT with a GNN we rely on HetMP, implemented by setting d > 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 adjacent nodes as different as possible, effectively acting as a high-pass graph filter. Therefore, optimizing MAXCUT loss features generated by HetMP layers overcomes the limitation of traditional scoring- based methods that compute the scores from features produced by homogeneous MP operators.
The layer we propose is called MaxCutPool and we present it through the SRC framework. The SEL operation in MaxCutPool identifies supernodes subset 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 vector s ScoreNet( X, A) E [| which assigns score to each node. The indices i == top x (s) associated with the highest scores identify the K supernodes. Additional details about the ScoreNet are in Appendix C. Fig. 1(i-I) shows the histograms of the score vectors generated by the ScoreNet for the 4 example graphs. Compared to the histograms of Umuu in Fig. ((c-h), the values always produce 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 S is built by performing visit of the graph where, starting from the supernodes, all the remaining nodes are assigned to their nearest supernode (see Fig. 2). More formally, the assignment matrix S is defined as
treadth-first
SEL: [S] = + j = A,
where @(S A, i) returns the closest supernode to node The visit of the graph is iterated until all nodes are assigned to supernode or until maximum number of iterations is reached. In the latter case, nodes that are still unassigned are assigned at random to ensure that the pooled graph is always connected. Keeping the maximum number of iterations small (e.g., 2 or 3) prevents
5

---

Published as a conference paper at ICLR 2025
(d)
Figure 2: (a) The nodes with the K = 9 highest scores are selected. (b-c) Their ID is propagated to the unselected nodes until all covered until maximum number of iterations (2 here) reached. (d) The 4 remaining nodes are assigned randomly. (e) The pooled graph is obtained by aggregating the nodes with the same ID and coalescing the edges connecting nodes from different groups
pointless attempts to reach a supernode, e.g., when there are no supernodes within 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 GPU-parallel implementation of the proposed assignment scheme is deferred Appendix A.
The RED operation for computing the features of the supernodes can be implemented in two ways:
RED: X'
84 O X]:
RED: X'
+ S.X.
The Hadamard product O enables gradients flowing through the ScoreNet during back-pros back-propagation. making it possible for the gradients of the task loss to reach every component of our model, despite the dinfeffferentillle topx operation. When the first the second variant is used to implement RED, we refer to the pooling operator as MaxCutPool and MaxCutPool-E, respectively. The suffix "-E" indicates that the pooling operator satisfies the sufficient conditions for expressiveness defined by Bianchi & Lachi (2023).
Finally, the CON operation can be implemented as
CON ='= T AS.
3.1 AUXILIARY LOSS
Each MaxCutPool layer associated with an auxiliary loss that encourages the top- selected nodes to belong to the same side of the MAXCUT partition. The loss is defined as:
8 As
Leur
(5)
[3
s T As < (8). hence -1 S. Cau < 1. This loss evaluates the ratio between the volume of the cut and the total volume of the edges. Minimizing Leut encourages the nodes be assigned different partitions if and only if they are connected. The loss reaches its minimum -1 when all connected nodes are assigned to opposite sides 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.
where |1] Eig Wis the total edge weight of the graph. Since -1 -1 s; 1, we have -1E)
GNN model consisting MP layers interleaved with MaxCutPool layers can be trained end-to-end to jointly minimize task loss Lusk and the auxiliary loss Ceut- The total loss is then defined as
C Lrask
Escl
(6)
where 8 is scalar weighting each auxiliary loss cl) associated with the 1-th MaxCutPool layer.
3.2 HOMOPHILIC AND HETEROPHILIC OPERATIONS
Despite the presence of HetMP layers and the heterophilic loss, MaxCutPool can be inserted into GNNs equipped with traditional MP layers. In fact, our method leverages the homophilic nature of

---

Published as a conference paper at ICLR 2025
the latter. After standard homophilic MP, the stronger the association between pair of nodes, the more similar their features will be. Keeping them both will, thus, be redundant, and one of them can be dropped. This is precisely what is done by SEL that, thanks to its heterophilic design, samples nodes that share as few connections as possible and are uniformly distributed over the graph.
MaxCutPool contains additional homophilic operation: the computation of the assignments S through the nearest-neighbor aggregation, which synergizes with the repulsiveness in the supernodes' sampling. The assignments are used by CON to produce a connectivity matrix that is connected yet sparse, and they can also be leveraged by RED to ensure the expressiveness of the pooling layer. However, in heterophilic datasets where such homophilic assignment is not ideal, the non-expressive variant of MaxCutPool offers a more suitable alternative.
Overall, rather than creating tension, combining homophilic and heterophilic components provides a GNN with MaxCutPool the flexibility for handling different scenarios. As we show in the experimen- tal evaluation, our model can even switch to a completely homophilic setting by adjusting the values of 8 and 3 or by ignoring the auxiliary loss Lent.
3.3 RELATION WITH OTHER POOLING METHODS
MaxCutPool belongs to the scoring-base based pooling family from which it inherits the possibility of specifying any desired pooling ratio adaptable to the size N, of the i-th graph, i.e., K; = [N; * 0.5J. while achieving node selection patterns similar to one-every-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 ---iddependent. On the other hand, in MaxCutPool any set of supernodes can be chosen in principle, making MaxCutPool more flexible and able to adapt to the requirements of the downstream task. Finally, MaxCutPool the only scoring- based pooler with a graph-theoretical auxiliary regularization loss.
The proposed method for constructing the cluster assignment matrix S from the selected supernodes can be applied to other scoring-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 retain all the information from the original graph. By addressing the key limitation in the expressiveness of scoring- scoring-based pooling methods, our approach retains the benefits of sparsity and interpretability of scoring- 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 is publicly available'. The details of the architectures used in each experiment and the hyperparameter selection procedure are described in Appendix C.
4.1 COMPUTATION OF THE MAXCUT PARTITION
The main focus of this experiment is to evaluate the capability of the proposed loss L to optimize the MAXCUT objective, despite the potential risks getting stuck local minima due to its gradient-based nature. We compute MAXCUT partition with a simple GNN consisting of MP layer followed by MaxCutPool, which is trained by minimizing only the loss in Eq. 5 (details in Appendix C.2). We compare model against the LEVS approach based on Umax the GW algorithm, and GNN with GCN layers that minimize a MAXCUT loss, as proposed by Schuetz et al. (2022). For a fair comparison, ours and the latter GNN architecture have comparable number of learnable parameters.
We considered graphs generated via the PyGSP library (Defferrard et al., 2017), including bipartite graphs such the Grid2D and Ring, and 7 graphs from the GSet dataset (Ye, 2003), including random, planar, and toroidal graphs, typically used as benchmarks for evaluating MAXCUT algorithms (details in App. I) 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.
"https://g/i http:///gggthtooooocoo///ootrr//
7

---

Published as a conference paper at ICLR 2025
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 converge.
(a) PyGSP datasets
(b) GSet datasets
Dataset
GW
NDP
GCN
MaxCutPool
Dataset
NDP
GCN
MaxCutPool
BarabasiAlbert
0.6875 0.6589 0.7240
0.7292
G14
0.6155 0.6323
0.6412
Community
0.6767
0.6429 0.6805
0.6814
G15
0.5945 0.6288
0.6424
ErdósRenyi
0.6920
0.6858 0.6797
0.7105
G22
0.6441 0.6409
0.6577
Grid (10x 10)
1.0000 1.0000 0.9222
1.0000
G49
1.0000 0.9683
1.0000
Grid (60x40)
0.9787 0.1862
0.9815
G50
0.9800 0.9610
0.9750
Minnesota
0.9104 0.8904
0.9130
G55
0.7568 0.7865
0.8068
RandRegular
0.4827 0.8760 0.8733
0.9040
G70
0.8803 0.8945
0.9086
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 GNN classifier with the following structure: Pool-)-Pool-M)(32) -ie--oot)----eouuut, using Graph Isomorphism Network (GIN) (Xu et al., 2019) as the MP layer. The Pool operation is implemented either by MaxCutPool or by the following competing methods: Diffpool (Ying et al., 2018), DMoN (Tsitsulin et al., 2023), MinCutPool (Bianchi et al., 2020a), Top-k (Gao & Ji, 2019). Graclus (Dhillon et al., 2007), A-MIS (Bacciu al., 2023). We also consider Edge-Contraction Pooling (FCPool) (Diehl, 2019) that pools the graph by contracting the edge connecting similar nodes. For MaxCutPool, we evaluate three variants: (i) MaxCutPool, the standard version; (ii) MaxCu(Poll-E, the variant with expressive CON; (iii) MaxCuPPollNNL, 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 replaced by a GINE layer (Hu et al., 2020), which takes into account edge attributes. Further implementation details are in Appendix C.3.
As graph classification datasets we consider TUU datasets (COLLAB, DD,, NCII, ENZYMES, MUTAG, Mutagenicity, PROTEINS, and REDDIT-BINARY) (Moriis et al., 2020), the Graph Classi- fication Benchmark Hard (GCB-H) (Bianchi et al., 2022), and EXPWLI (Bianchi & Lachi, 2023), which is recent dataset for testing the expressive power of GNNs. In addition, we introduce novel dataset consisting of 5, 000 multipartite graphs: each graph is complete 10-partite, meaning that the nodes can be partitioned into 10 groups 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 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 90-10% train-validation random split. This approach is similar the procedure described by Errica et al. (2020). Each model was trained for 1, 000 epochs with early stopping, keeping the checkpoint with the best validation accuracy.
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 preliminary ANOVA test (p-value 0.05) for each dataset followed by 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 green. The ANOVA test failed ENZYMES, PROTEINS, MUTAG, and DD,, meaning that the
8

---

Published as a conference paper at ICLR 2025
Table Mcan 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 method is in the top-perfonee perpeefornnng group is assigned with score of 1, otherwise.
Pooler
GCB-H COLLAB EXPWL1
Mult.
Mutag.
NCI1
REDDIT-B Score
No pool
7424
7422
8712
14112
79
78
9012
DiffPool
51+8
70=2
69#3
9=1
78#2
75+2
90+2
DMoN
7413
68
73=3
5212
8012
7712
8812
3
EdgePool
7544
7223
90
55
8012
7713
9112
Graclus
75=3
72-3
90=2
25+18
8042
77+2
90
A-MIS
75:44
71
99#1
58
7942
7513
90
4
MinCutPool
75
70#2
71
5643
78
7343
87+2
Top-k
56
7222
73=2
4313
75
73+2
77
0
MaxCutPool
73+3
77=2
100+0
90+2
77+2
75+2
8943
5
MaxCutPool-E
74
77=2
100+a
8715
79
7642
8912
7
MaxCutPool-NI.
61
77
100+0
91+1
76#3
74+2
86+3
3
difference in the performance of the GNNs equipped with different poolers is not significant. For this reason, the results these datasets omitted from Tab. 3 and reported in Appendix E.
MaxCutPool consistently ranks among the top- pop-perfrrming methods across all evaluated datasets. Notably, the EXPWLI even the non-expressive variant of MaxCutPool achieves perfect accuracy (100%), outperforming the competitors. This is the first known example of non-expressive pooler passing the expressiveness performs significantly better than every pooling method. When compared to the "No poo!" 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, Max CutPoo variants achieve the top accuracy of 77%, showing statistically significant improvement over other methods. Notably, in the Max MaxCutPool and MaxCutPool-E variants the auxiliary loss term plateaued around 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 better performance compared to MaxCutPool across most datasets. In contrast, the performance decline observed in the MaxCutPooI-NL variant demonstrates the importance the auxiliary loss.
provided by this dataset. On the Multipartite dataset, MaxCutPool
4.3 NODE CLASSIFICATION
For this task, we adopted simple auto-encoder architecture for node classification: -PPol)-Pool- (BP()))Unnpol-MMP2)))RRaaa
with GIN as MP. The Unpool operation (also referred to as lifting (Jin al., 2020)) implemented by copying into each node the value of the supernode j to which node i was assigned by the SEL operation in the pooling phase. Zero-padding is used when lifting nodes not assigned 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 heterophilic datasets presented in Platonov al. (2023) (details in Appendix D.4). As pooling methods we considered Top-k (Gao & Ji, 2019), K-MIS (Bacciu et al., 2023), NDP (Bianchi et al., 2020b), and MaxCutPool. We did not consider Graclus or any soft-clustering poolers, they were exhausting the RAM and GPU VRAM, respectively, given the large size of the graphs. On the other hand, MaxCutPool 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 F.3.

---

Published as a conference paper at ICLR 2025
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 score point, 0 otherwise.
Pooler
Roman-e.
Amazon-r.
Minesw.
Tolokers
Questions
Score
No pool
59
4641
8642
8644
71
Top-k k-MIS
26
4644
94+1
8945
6423
23
48
75=2
8442
83+1
NDP
22+5
5342
9840
8846
68
3
MaxCutPool
56+3
53+1
9641
8743
82#4
4
MaxCutPool-E
60
5342
97+1
91+2
85
Following Platonov et al. (2023), in Tab. 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 public folds of these datasets. When configured with MaxCutPool and MaxCutPool-EE 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. 1).. Also on the remaining datasets, our method performs well: unlike the other pooling methods that achieve top performance only on a subset of the datasets, MaxCutPool-F consistently in the top tier.
5 CONCLUSION
This work contributes significantly to both the MAXCUT optimization and the development of special- ized GNN architectures solve combinatorial optimization problems. 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-altributed graphs. While conventional GNN with huge capacity manages to optimize MAXCUT loss (Schuetz al., 2022), our model is much more efficient thanks to the Heterophilic Message Passing layers. These results highlight the importance of aligning the GNN architecture with the problem's '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 scoring-based methods and with the theoretically-inspree 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. Unlike existing graph pooling and graph coarsening approaches that aim preserving wwwfrrequencies on the graph (Loukas, 2019), our method performs exceptionally well also on heterophilic datasets.
While pooling layer 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 the nodes' degree is approximately uniform, the MAXCUT induces an approximately balanced partition corresponding to a pooling ratio of so 0.5, which is, thus, generally a good choice.
Looking forward, we great potential in pretraining GNNs with auxiliary losses. This aligns with the principles of foundational models (Bommasani al., 2021) and could facilitate the development of more effective and perrpoe- graph pooling techniques.
ACKNOWLEDGMENTS
This work was supported by the Norwegian Research Council project 345017: RELAY: Relational Deep Learning for Energy Analytics. The authors wish to thank Nvidia Corporation for donating some of the GPUs used in this project.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ahmed Abbas and Paul Swoboda. Rama: A rapid multicut algorithm on gpu. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8193-8202, 2022.
Bengt Aspvall and John R. Gilbert. Graph coloring using eigenvalue decomposition. SIAM Journal on Algebruic Discrete Methods, 5(4):526-538 1984.
Davide Bacciu, Alessio Conte, and Francesco Landolfi. Graph pooling with maximum-weight k-independent sets. In Thirly-Seventh AAAI Conference on Artificial Intelligence, 2023.
Mohammad Khairul Bashar, Antik Mallick, Daniel S. Truesdell, Benton H. Calhoun, Siddharth Joshi, and Nikhil Shukla. Experimental demonstration of a reconfigurable coupled oscillator platform to solve the max-cut problem. IEEE Journal on Exploratory Solid-State Computational Devices and Circuits, ((2):116-1211 2020. doi: 10.1 10100/XXCDC.22220000225999
Filippo Maria Bianchi. Simplifying clustering with graph neural networks. arXiv preprint w7Xiv:2207.0877, 2022.
Filippo Maria Bianchi and Veronica Lachi.
The expressive power of pooling in graph neural networks In Advances in Neural Information Processing Systems, volume 36, pp. 71603-71618 2023.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, pp. 874-884 883. PMLR,
2020a.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Hierarchical represen- tation learning in graph neural networks with node decimation pooling. IEEE Transactions on Neural Networks and Learning Systems, 33(5):2195 2207, 2020b.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE transactions on pattern analysis and machine intelligence, 44(7)3396-3307,, 2021.
Filippo Maria Bianchi, Claudio Gallicchio, and Alessio Micheli. Pyramidal reservoir graph neural network. Neurocomputing, 470:389-404, 2022. ISSN 0925-2312. doi: https://doi.org/10.. 101
neucom.2021.04.131.
Derrick Blakely, Jack Lanchantin, and Yanjun Qi. Time and space complexity of graph convolutional networks. Accessed on: Dec, 31:2021, 2021.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportuni- ties and risks of foundation models. arXiv preprint 1xXiv22108.07258 2021.
Christian Borgs, Jennifer Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Conver- gent sequences of dense graphs ii multiway cuts and statistical physics. Annals of Mathematics, pp. 151-219, 2012.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021.
Andrea Cini, Danilo Mandic, and Cesare Alippi. Graph-based Time Series Clustering for End-to-End Hierarchical Forecasting. International Conference on Machine Learning, 2024.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Michaël Defferrard, Lionel Martin, Rodrigo Pena, and Nathanaël Perraudin. Pygsp: Graph signal pro- cessing in python, October 2017. URL https /ow. / 100. 5281 zenodo. 1003158.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 29(11): 1954-1957, 2007.
11

---

Published as a conference paper at ICLR 2025
Frederik Diehl. Edge contraction pooling for graph neural networks. arXiv preprint arXiv:1905.10990 2019.
Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Adagnn: Graph neural networks with adaptive frequency response filter. In Pruceedings of the 30th ACM international conference on information & knowledge management, pp. 392-401, 2021.
Alexandre Duval and Fragkiskos Malliaros. Higher-order clustering and pooling for graph neural networks. In Proceedings of the st ACM international conference on information & knowledge management, pp. 426 435, 2022.
Moshe Eliasof, Lars Ruthotto, and Eran Treister. Improving graph neural networks with learnable propagation operators. In International Conference on Machine Learning, pp. 9224-9245. PMLR, 2023.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Gruphs and Manifolds, 2019.
Guoji Fu, Peilin Zhao, and Yatao Bian, p-laplacian based graph neural networks. In International Conference on Machine Learning, pp. 6878-6917. PMLR, 2022.
H. Gao, Y. Liu, and S. Ji. Topology-awane graph pooling networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 43(12):512-4511 dec 2021. ISSN 1939-3539. doi: 10. 109/ TPAMI.2021.320 330679994.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pp. 2083-2092. PMLR, 2019.
Xing Gao, Wenrui Dai, Chenglin Li, Hongkai Xiong, and Pascal Frossard. inforaiiformatioon- based pooling in hierarchical graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 33(9):5032 5044, 2022. doi: 10. 1...1119NNNSSSS 2021.3664..........
Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6): nov 1995.
ISSN 0004-5411. doi: 10. 00.1144227663.2227666
Daniele Grattarola, Danicle Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling in graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Jonas Berg Hansen and Filippo Maria Bianchi. Total variation graph neural networks. In International Conference on Machine Learning, pp. 22445-12468 PMLR, 2023.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks, 2020.
Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2020.
Amir Hosein Khasahmadi, Kaveh Hassani, Parsa Moradi, Leo Lee, and Quaid Morris. Memory-based graph networks. In International Conference on Learning Representations, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Thomas N. Kipf and Max Welling. Semi- superviee classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
12

---

Published as a conference paper at ICLR 2025
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. Advances in neural information processing systems, 32, 2019.
Francesco Landolfi. Revisiting edge pooling in graph neural networks. In ESANN, 2022.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International conference on machine learning, pp. 3734-3743. PMLR, 2019.
W Bernard Lee and Anthony G Constantinides. Quantumized graph cuts in portfolio construction and asset selection. Springer-Nature Transactions on Computational Science and Compu-tational Intelligence, 2023.
Frauke Liers, Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi. Computing exact ground states of hard ising spin glass problems by branch-and-cut. New optimization algorithms in physics, pp. 47-69, 2004.
Derek Lim, Felix Hohne, Xiayu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Ning Liu, Songlei Jian, Dongsheng Li, Yiming Zhang, Zhiquan Lai, and Hongzuo Xu. Hierarchical adaptive pooling by capturing high-order dependency for graph representation learning. IEEE Transactions on Knowledge and Data Engineering, 35(4):395233965 2021.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20( 16: 42, 2019.
Enxhell Luzhnica, Ben Day, and Pietro Lio. Clique pooling for graph classification. arXiv preprint arXiv:1904.00374. 2019.
Zheng Ma. Junyu Xuan, Yu Guang Wang, Ming Li, and Pietro Liò. Path integral based convolution and pooling for graph neural networks. Advances in Neural Information Processing Systems, 33:
16421-16433, 2020.
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu-linial stable instances of max cut and minimum multiway cut. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 890-906. SIAM, 2014.
Ivan Marisca, Cesare Alippi, and Filippo Maria Bianchi. Graph-based forecasting with missing data through spatiotemporal downsampling. In Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 34846-3444 34865. PMLR, 2024.
Paul M Mather and Magaly Koch. Computer processing of remotely-sensed images. John Wiley & Sons, 2022.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Emmanuel Noutahi, Dominique Beaini, Julien Horwood, Sébastien Giguère, and Prudencio Tossou. Towards interpretable sparse graph representation learning with laplacian pooling. arXiv preprint arXiv: 11577. 2019.
Yunsheng Pang, Yunxiang Zhao, and Dongsheng Li. Graph pooling via coarsened graph infomax. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2177-2181, 2021.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? The Eleventh International Conference Learning Representations, 2023.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5470-5477, 2020.
13

---

Published as a conference paper at ICLR 2025
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013. doi:
10.1 N0.11009MSP222222355122
David Shuman, Mohammad Javad Faraji. and Pierre Vandergheynst. multiscale pyramid transform for graph signals. IEEE Transactions on Signal Processing, (4(8):21192213) 2015.
Nicolas Tremblay, Paulo Gonçalves, and Pierre Borgnat. Design of graph filters and filterbanks, In Cooperative and Graph Signal Processing, pp. 299-324. Elsevier, 2018.
Luca Trevisan. Max cut and the smallest eigenvalue. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 263-272, 2009.
Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. J. Mach. Learn. Res., 24:127: 2023.
Ulrike von Luxburg. A tutorial spectral clustering. 2007.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin-basse based constraints, 2019.
Pengyun Wang. Junyu Luo, Yanxin Shen, Siyu Heng, and Xiao Luo. A comprehensive graph pooling benchmark: Effectiveness, robustness and generalizability. arXiv preprint arXiv:2406.090:1 2024.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 6861-6877 PMLR, 09-15 Jun 2019.
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling. In International conference on machine learning, pp. 24017-24030. PMLR, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Yinyu Ye. The gset dataset, 2003.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Zhen Zhang, Jiajun Bu, Martin Ester, Jianfeng Zhang, Chengwei Yao, Zhi Yu, and Can Wang. Hierarchical graph pooling with structure learning. arXiv preprint arXiv:1911.05954 2019.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. doi: (0.10166j.aiooen.222..001
Al Open, 1:57-81, 2020a. ISSN 2666-6510.
Leo Zhou, Sheng-Tao Tao Wang. Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2):021067, 2020b.
14

---

Published as a conference paper at ICLR 2025
APPENDIX
A NEAREST NEIGHBOR ASSOCIATION ALGORITHM
As discussed in Sec. 3, each node is associated with 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 implementation of the assignment scheme that is efficient and can be easily parallelized on a GPU. The proposed algorithm is based on Breadth First Search (BFS) of the graph and is detailed in the pseudo-code in Algorithm 1.
Algorithm Pseudo-code for the assignment scheme to the supernodes
1: procedure ASSIGNNODSSOSSUPPNNODSSSCC S, Marzlerr)
2: E + InitaalizeEnncodingS(G....
One-hot encoding
3: m f InitializeeMssk(
4: Assignmentss <- Imitializeemptyyisttt)
5: for = 1 to MazIter do
6: if AllNodesAssiigedd(ne then break
7:
8:
end if
9:
E' < ParalelMessagePassnnggg
D E' = AE
As Assignments +- Parallel/Assiummett S m)
11:
m + UpdateMask(m, Assignments)
12:
E + E'
13:
end for if not AlNNodesAssinne((m) then
15:
RndAAsiggmennts <- PenllRRadoonkkiiimannnnssssnnnna end
16:
17:
Final Assignments GeffinalAsiiammeessssssinnnnttt Rnd Rnd.Assigmments)
18:
return Final Assilggiinesnts
end procedure
The algorithm takes input the graph G (in particular, its topology described by the adjacency matrix A), the set of K supernodes S identified by the SEL operation, and maximum number iterations (MoxIter), which represent the maximum number of steps node can traverse the graph to reach its closest supernode before being assigned at random.
In line 2, encoding matrix E of size N x K + is initialized so that row is one-hot vector with the non-zero entry in position & + 1, if the node of the original graph is the k-th supernode. Otherwise, row in 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-th column in matrix E (and subsequently in E') serves a special purpose. This column represents "fake" supernode, which plays a crucial role in the assignment process.
Boolean mask m E {0, 1 indicating whether a node has already encountered the closest supernode is initialized in line 3 with 1 in position if node i is a supernode and otherwise. Finally, an empty list indicating to which supernode each node assigned is initialized (line 4).
Until the maximum number of iterations is reached or until all nodes are assigned (line 6), the encoding matrix E propagated with an efficient message passing operation (line 9) that can be parallelized on GPU. As soon as a appears in position A within a line i of E previously full of zeros, node is assigned to supernode and the assignments and mask m are updated accordingly (lines 10 and 11). The ParallelAssigmment function (line 10), in particular, takes the rows of the newly generated embeddings E' that have not yet been assigned and performs an argmax operation on the last dimension. If the gramax doesn't find any valid supernode for node (i.e., all values in the row are zero), it returns O, effectively assigning the node to the "fake" supernode represented by the O-th column. This allows filter out the unassigned nodes in line 11.
15

---

Published as a conference paper at ICLR 2025
If there are still unassigned nodes the end of the iterations, the remaining nodes are randomly assigned to one the K supernodes (line 15). Finally, all the assignments are merged (line 17).
B DERIVATION OF THE AUXILIARY LOSS
Let consider the MAXCUT objective in Equation 1. It can be rewritten
max
Σ LJEV
Wij
Σ
Wiz
max
[8]
Σ
KJEV
LJEV
which is equivalent to
Σ
2i2g Wij
L.VV
The solution x" for the original objective is thus the solution for
=
min
[
C IMPLEMENTATION DETAILS
C.I MAXCUTPOOL LAYER AND SCORENET
schematic depiction of the MaxCutPool layer is illustrated in Fig. where the SEL, RED, and CON operations are highlighted.
Cent
Exprossivo?
ScoreNel
Top-k
NN Aggr.
cor
Figure 3: Scheme of the MaxCutPool layer.
SEL first computes a score vector using the auxiliary GNN, ScoreNet, based on the node features X and the connectivity matrix A. A top-K operation is used to find the indices of the K nodes with the highest scores that become the supernodes, ie.. the nodes of the pooled graph. The remaining N K nodes are assigned the nearest supernode through nearest-neighhor (NN) aggregation procedure that yields an assignment matrix S, whose jk-tth element is if node j is assigned to supernode k and zero otherwise. The score vector is used to compute the loss Lent- which is associated with each MaxCutPool layer.
The RED operation computes the node features of the pooled graph X' by multiplying the features of the selected nodes X, with the scores This operation is necessary to let the gradients flow past the top-K K operation, which is not differentiable. In the expressive variant, MaxCutPool-E RED computes the node features by combining those from all the nodes in the graph through the multiplication with matrix S. We combine the features by summing them instead of taking the average since the enhances the expressiveness of the pooling layer (Bianchi & Lachi, 2023).
16

---

Published as a conference paper at ICLR 2025
The CON operations always leverage the assignment matrix to compute the adjacency matrix of the pooled graph. In particular, the edge connecting two supernodes and j is obtained by coalescing all the edges connecting the nodes assigned to supernode with those assigned supernode j. Also in this case, we take the sum as the operation to coalesce the edges. The resulting edges in the pooled graph associated with weight Wij that counts the number of combined edges.
The details the ScoreNet used in the MaxCutPool layer are depicted in Fig. 4. The ScoreNet consists of linear layer that maps the features X to desired hidden dimension. Afterward, 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 the last HetMP layer into a score vector which is a high-frequency graph signal. We note that while
X
Linear
HetMP
HetMP
HetMP
MLP
Figure 4: Scheme the ScoreNet.
the simple HetMP we adopted works well in our case, different heterophilic MP operators could have been considered (Chien et al., 2021; Dong et al., 2021; Fu et al., 2022).
The ScoreNet is configured with the following hyperparameters:
Number of HetMP layers and number of features 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]
indicate layers with 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 the default, we use TanH.
Number of layers and features in the MLP. As default, use [16, 16).
Activation function of the MLP. As the default,
ReLU.
Smoothness hyperparameter ò. As default,
Auxiliary loss weight 3. 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 the ScoreNet are kept fixed at their default value while others optimized.
C.2
CUT MODEL
The model used compute the MAXCUT is depicted in Fig. 5. The model consists of single MP layer followed by the ScoreNet, which returns the score vector s. The MAXCUT partition is obtained
Cast
X
ScoreNet
Rounding
MP
A
Figure 5: Scheme of the model used for computing the MAXCUT.
17

---

Published as a conference paper at ICLR 2025
by rounding the values in the score vector follows
y/4 {
if 8; 0,
otherwise.
The model is trained in a completely unsupervised fashion only by minimizing the auxiliary loss Ceat
As MP layers, we used a GIN (Xu al.. 2019) layer with 32 units and ELU activation function. The model was trained for 2000 epochs with Adam optimizer (Kingma & Ba, 2015), with the initial learning rate set 4. We used 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 grid search on the following set of hyperparameters:
HetMP layers and units:
[32]
[4] x 32,
[8] x 16,
[16] X
[32, 32, 32, 32, 16, 16, 16,
HetMP activations:
ReLU,
TanH.
Smoothness hyperparameter d:
- 2.
3.
5.
In Tab. 5 we report the contigurations 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
G14
332, 32, 32, 16, 16, 16, 16, 8, 8,8,888 8,8
ReLU 2.0
G15
332, 32, 32, 32,
16, 16, 16, 16, 8, 8,8,88
ReLU
2.0
G22
[ x 32
TanH
2.0
G49
332, 32, 16, 16, 16, 16, 1,,8,888,8
TanH
2.0
G50
[8] X 16
ReLU
2.0
G55
X
ReLU
2.0
G70
X 16
ReLU
2.0
BarabasiAlbert
X 32
TanH
2.0
Community
4 X 32
TanH
2.0
ErdosRenyi
X 32
TanH
2.0
Grid2d (10x 10)
4 X 32
TanH
2.0
Grid2d 400
4 X 32
ReLU
2.0
Minnesota
X
TanH
2.0
RandRegular
4 X 32
TanH
2.0
Ring
X
ReLU
2.0
Sensor
X 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 pooling layer, MP acting the pooled graph, global pooling layer that sums
18

---

Published as a conference paper at ICLR 2025
X
Global Pool
MP
Pool
MP
MLP
A
Figure 6: Scheme of the graph classification model.
the features of all the nodes in the pooled graph, and an MLP that produces the label y associated with the input graph. 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 initial learning of Te 4. We used early stopping that monitors the validation loss with patience 300 epochs. For testing, we restored the model checkpoint that achieved the lowest validation loss during training.
The best configuration was found via grid search on the following set of hyperparameters:
HetMP layers and units:
[32] x 8,
[3] 4,
[8] x 16, [16] x 8
[32,32, 16, 8,,
[32,32, 32, 32, 16, 16, 16, 16, 8,8,8,
Auxiliary loss weight 3:
-
Table 6: Hyperparameters configurations the ScoreNet for the graph classification task.
MaxCutPool
MaxCutPool-E
Dataset
MP units
MP units
,
GCB-H
[8] 16
3.0
322 8
5.0
COLLAB
[32 x
1.0
32
8
1.0
DD
32, 32, 32, 32,
16, 16, 16, 1,,
1.0
[ x
16
5.0
ENZYMES
[8] 16
3,0
16 8
3.0
EXPWL.
[32, 32, 16, 16, 8,8)
1.0
16 8
1.0
MUTAG
8 16
1.0
16 8
3.0
Multipartite
32] x 8
3.0
32
8
1.0
Mutagenicity
332, 32,
16, 16, 8,
1.0
32
8
5.0
NCTI
32, 32, 16, 16, 8
1.0
8
x 16
3.0
PROTEINS
332, 32, 32, 32,
16, 16, 16, 16, 8, 8, 8, 8
3.0
[32, 32,
16,
16, 8, 8
5.0
REDDIT-B
[3
x
1.0
32,
32,
32,
32,
16,
16, 16,
16,
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 Max
C.4 NODE CLASSIFICATION MODEL.
The model used to perform node classification is depicted in Fig. The model consists an MP layer, followed by a pooling layer, MP acting the pooled graph, unpooling (lifting) layer, MP on the unpooled graph, and an MLP that produces the final node labels y.
The entry i represents the predicted label for node i. The model is trained jointly minimizing the cross-entropy loss between the predicted node labels and the true ones and the auxiliary loss of the pooling layer.
19

---

Published as a conference paper at ICLR 2025
X
Pool
MP
Unpool
MP
MLP
A
Figure 7: Scheme of the node classification model.
Unpool
(broadcast)
Supernodes
Node
assign.
Unpool
(padding)
Figure 8: The two possible strategies for performing unpooling (lifting).
When using MaxCutPool, the unpooling/litting procedure can be implemented in two different ways, illustrated in Fig. 8. The first strategy, broadcast unpooling, copies the values X' 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 S, obtained described in Sec. and Appendix A. Formally, the unpooled node features X are:
=
We note that this is the commonly used approach to perform unpooling in cluster-based poolers.
In the second strategy, padding unpooling, the values X' copied back only to the supernodes, while the remaining nodes are padded with zero-valued vector:
[x') if is supernode o
otherwise.
This is the approach perform unpooling used by scoring- based approaches such as Top-k and by one-over-K 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., 2019) layer with 32 units and ReLU activation function. The MLP has single hidden layer with 32 units, 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 the broadcast one for K-MIS and MaxCutPool and the padding one for Top-k and NDP.
The best configuration was found via grid search on the following set of hyperparameters:
* HetMP layers and units:
[32] x
[4] x 32,
322,3,,55 32, 32, 16, 16, 16,
MLP activations:
ReLU,
TaaHH.
The configuration of the ScoreNet for the MaxCutPool pooler used in the different datasets is reported in Tab. 7.
The node classifier was trained for 20, 000 epochs, using the Adam optimizer with an initial learning rate of 5e 4. We used learning rate scheduler that reduces by 0.5 the learning rate when the
20

---

Published as a conference paper at ICLR 2025
Table Hyperparameter configurations of the ScoreNet in the node classification task.
Dataset
MP units
MLP Act.
Noman-Empire
32, 32] 32,,2,,22, 32]
ReLU
Amazon-Rating
ReLU
Minesweeper
[32, 32, 32, 32, 16, 16, 16, 86,8,888,8
ReLU
Tolokers
[32, 32, 32, 32, 16, 16, 16, 16, 8,8,8
ReLU
Questions
[32, 32, 32, 32]
ReLU
validation loss does not improve for 500 epochs. We used an early stopping that monitors the validation loss with patience of 2, 000 epochs. For testing, we restored the model checkpoint that achieved the lowest validation loss during training.
We also considered an additional architecture for node classification with skip (residual) connections, depicted in Fig. 9. This architecture is similar to the Graph U-Net proposed by Gao & Ji (2019). The
X
Skip
MP
A
Pool
Unpool
MP
Figure 9: Scheme of the node classification model with skip connections.
node features obtained after the first MP layer are concatenated to the node features generated by the unpooling step. In this architecture, 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: Hyperparameter configurtioon for the node classification task based on the architecture with skip connections.
Dataset
MP units
MLP Act.
Roman- Camire
[32, 32, 32, 32]
ReLU
Amazon Ratings
[32, 32, 32, 32,
ReLU
Minesweeper
32,
TanH
Tolokers
32,
ReLU
Questions
[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, 2019), For M-MIS we used the official implementation 2, For ECPool, we used the efficient parallel implementation proposed by Landolfi (2022). For NDP we adapted
htttps://ggitubb.cmm//faanel/ hhtpp:://github.ccmm/f
21

---

Published as a conference paper at ICLR 2025
to PyTorch the original Tensorflow implementation 4. All pooling layers used with the default hyperparameters. Since k-MIS does not allow for direct specification of the pooling ratio, we set k [1/k].
D DATASETS DETAILS
D.1 CUT DATASETS
The statisties 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., 2017), the Gset dataset is downloaded from the original source"
Table 9: Statistics of the PyGSP datasets used to compute the MAXCUT.
(a) PyGSP datasets
(b) Gset
Dataset
# Nodes
Edges
Vertex attr.
Dataset
# Nodes
Edges
Vertex attr.
Berabasi-Alberr
100
768
G14
800
4, 694
Community
90
532
G15
800
4. 661
Erdós-Renyi
100
974
G22
2,000
19, 990
Grid2d (10x 10)
100
360
G49
3, 3,000
6, 000
Grid2d 40)
2,400
9400
2
G50
3, 3,000
6. 0.00
Minnesota
2642
6608
G55
5,000
12, 468
RandRegular
500
1500
2
G70
10, 000
9, 9,999
Ring
100
200
Sensor
64
640
2
D.2 MULTIPARTITE DATASET DESCRIPTION
The Multipartite graph dataset is 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 every node belonging 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:
A set C cluster centers with 2D coordinates (x, y) initially arranged polygon shape. Each center is associated with a label, i.e., 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 the positive z-axis.
3. For each class, we generate multiple graphs using these cluster centers. A graph is created by drawing random the position the nodes around each cluster center. The number of nodes per cluster varies randomly to maximum. Nodes within a cluster share the same color, which is determined by the cluster center.
4. The topology of each graph obtained by connecting nodes from cluster to the nodes of all the other clusters, but not to the nodes of the same cluster. Therefore, a node is connected only 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 used for the next class. Indeed, each rotation brings a different cluster the positive z-axis.
6. The rotation process continues until the graphs for all the C' different classes, whose number is equal to the number of clusters, generated.
Examples of multipartite graphs obtained for C = 3 are shown in Figure 10.
The process depends on few parameters that determine the number of clusters, the maximum nodes cluster, and the number of graphs per class, providing control over the dataset size and complexity.
22

---

Published as a conference paper at ICLR 2025
Algorithm 2 Multipartite graph dataset generation
Input: num.clusters, max max maax.nodes.per per cluster, graphs-per.clan pea.
Output: dataset
1: cluster centers
Initial arrangement of centers
dataset {
3: for class_label + 0 to num_clusters - do
4: for 1 to graphs_per_class do
5: graph +- GennrattMMllnpariicchnhhhhllalee centers, nodes per cluster)
6: gruph.lahel class label
Label hased current rotation
Add graph to dataset 8: end for
9: cluster.centers <- RouaeClockwiiscchussee..cc.t..
b Rotate for next class
10:
end for
return dataset
12:
function GENER TEIIERATTMUUUPPPAITTEEET TEETRRRTT....LTTTETTTTTTCCCCCCET
max modes_perrcclsseeee
13:
for each center in cluster centers do
14:
num nodes RandomInt(1, max nodes per cluster)
15:
node positions t- GeperraeeNaeessrronoCeCettetttee num nodes)
16:
node_color + [eCcoolofFocccuuueeeeeeettttee AddNNodesToGGraphuuddeee.p end for
> Each cluster has unique color
17:
node_color)
18:
19:
(
Create complete multipartite graph
20:
return graph
21:
end function
22:
function ROTATECLLOCKSWSSSCCeeeee
23:
return [centers[-1]] centers[:-]]
Move last center to front
24:
end function
The specific instance of the dataset used in experiments has 10 centers, 500 graphs per center, and a maximum of 20 nodes per cluster, and is available online 6
The Multipartite dataset is intentionally designed 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 r-axis). Although the graph's topology is structured ensure that each graph is multipartite, this structure is independent of the class label. This creates an intriguing dichotomy between the graph's 's topology and its classification labels, In theory, a simple MLP focusing exclusively on node features could accurately solve the classification task, 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 potentially misleading or noisy topological information. Through this
htttp:://eenooooorr///////
116165115
Class (red)
Class 1 (blue)
Class (green)
Figure 10: Example of multipartite graphs with C 3 cluster centers generated via our procedure. The graph class corresponds the color of the nodes from group the right.
23

---

Published as a conference paper at ICLR 2025
carefully constructed dataset, aim to highlight the strengths and potential limitations of certain GNNs architectures, particularly scenarios where the relationship between graph structure and classification labels is non-trivial, such in heterophilic datasets.
D.3 GRAPH CLASSIFICATION DATASETS
In addition to the novel Multipartite dataset introduced in Sec. D.2, we consider 10 datasets for graph classification in our experimental evaluation. The TU Datasets (Morris al., 2020) (NCI, PROTEINS. Mutagenicity, COLLAB. REDDIT-B, DD, MUTAG, and Enzymes) are obtained through the loader PyTorch Geometric The EXPWLI and GCB-H datasets, respectively introduced by Bianchi & Lachi (2023) and by Bianchi et al. (2022), are taken from the official repositories 8 The statistics of each dataset are reported in Tab. 10.
Table 10: Details of the graph classification datasets.
Dataset
#Samples
#Classes
Avg. #vert.
Avg. #edg.
V. attr.
V. lab. h(D)
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
I 1
REDDIT-B
2,000
2
429.63
497.75
no
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
Since the node labels are not available the graph classification setting, it is not possible rely on the homophily ratio h()) (Lim et al., 2021) considered in the node classification setting. Therefore, quantify the degree of homophily in the graphs, we look at the node features instead and introduce surrogate homophily score h(D), where D denotes the whole dataset. The new score is defined as the absolute value of the average cosine similarity between the node features connected nodes in each graph of the dataset:
h(D)
D
[g GED
(K.))EE
where [D] is the number of graphs in the dataset, Eg is the set of edges of the graph G and æ; 2. the feature vectors of the i-th and j-th node respectively.
D.4 NODE CLASSIFICATION DATASETS
The datasets are the heterophilic graphs introduced by Platonov al. (2023) and are loaded with the API provided by Py PyTorch Geometric 10 The nodes of each graph are already split in train, validation, and across 10 different folds. The statistics of the five datasets are reported in Tab. 11. The column h())) is the class-insensitive edge homophily ratio as defined by Lim et al. (2021), which represents a measure for the level of homophily in the graph.
hnttps: http::/cwee..cottteeeeeeeaeeeeee retetheeoos..eeeee//eeee//eeeeee
classifical http:p///poochhheeeeeteerrereeea
geometric. Heterogh tttatrrrat..as.srraaaaaaaaee.e.
24

---

Published as a conference paper at ICLR 2025
Table 1I: Statistics of node classification datasets.
Dataset
Nodes
# Edges
# Classes
h(9)
Roman- -amrre
22,662
32,927
18
0.021
Amazon- 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
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 12: Graph classification accuracy values (subset)
Pooler
DD
MUTAG
ENZYMES
PROTEINS
No pool
73
78+1a
33-6
71+4
Diffpool
77=4
81+1
36=7
75+3
DMoN
78
82+11
37=7
76+4
ECPool
73
84112
35
7415
Graclus
73
82112
33-7
7314
k-MIS
75_3
83+10
33=8
73+5
MinCutPool
78-5
81+12
34-9
7745
Top-k
72=5
82+10
29
7445
MaxCutPool
77=4
84+10
31-6
74+4
MaxCutPool-E
77=3
8529
34
74.4
MaxCutPool-NL
74=4
83+11
31=4
70+4
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, focused the non-expressive variant of MaxCutPool, which consistently delivered superior performance this context. The improved results can be attributed to the architecture's ability preserve the original node information through skip connections. Additionally, by avoiding the combination neighboring node features (as is done in the expressive variant), the model is better equipped to learn frehfrrueencyy features, which is particularly advantageous for heterophilic datasets. For the Minesweeper dataset, we chose to use GIN layer with 16 units 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 higher capacity.
Table 13: Node classification accuracy (Roman-empire, Amazon-ratings) and AUROC (Minesweeper, Tolokers, Questions) obtained when using the architecture with skip connections.
Pooler
Roman-e.
Amazon-r.
Minesw.
Tolokers
Questions
Score
Top-k 20
49+7
91+1
96*a
70
k-MIS
19-2
53+3
904a
91+2
82
NDP
19
56+5
9440
90+s
69+7
MaxCutPool
67+2
53+1
92+1
96+1
82+2
25

---

Published as a conference paper at ICLR 2025
F COMPLEXITY
We first discuss the algorithmic complexities and then report empirical measurements about processing time and memory usage. All measurements are done Nvidia RTX A6000.
F.1 ALGORITHMIC COMPLEXITY
The complexity of MaxCutPool depends on the complexities of the operations SEL, RED, and CON and of the auxiliary loss Leut-
SEL The complexity of the SEL operation depends on the ScoreNet, which consists of a stack of L HetMP layers followed by an MIP, and on the topx selection.
HetMP. Following the analysis in Blakely et al. (2021), for graph with N nodes, E edges, and F features, each HetMP layer has time complexity of O(N + EF) and space complexity of OEE NF + F2). This results in space and time complexity of O(N + E)) with respect the input.
MLP. The ML.P has a fixed structure with predetermined layer sizes. Since it operates independently each node's feature vector and the number of operations per node is constant, processing each node takes (1)) time. With N nodes to process, this results in a total time complexity O(N) with respect the input. The space complexity is also O(N), as we need store the MLP hidden and output features for each node.
topk The complexity sorting an array of N elements is O(N log(N)). However, we are interested in finding only the top- elements, the complexity can be lowered to O(N log( K)) or O(N + K)), depending on the algorithm adopted. Therefore, we can assume an almost-lineat complexity in time and space with respect to the number of nodes N.
For the non-expressive variant, RED involves Hadamard product between the scores and features of the K selected nodes, giving time complexity of O(K). The expressive variant requires an additional multiplication with the assignment matrix S, increasing the complexity to O(K + FN... When is function of N (e.g., K N/2), both variants have time complexity O(N) with respect to the input.
RED
The space complexity O(N), representing the storage of input and output data.
CON Our efficient implementation of the nearest neighbor assignment follows the complexity of BFS: O(N + E) time and O(N) space.
The auxiliary loss Leur requires computing quadratic form, with time complexity (EE) and space complexity O(N + E).
Auxiliary loss
Total complexity
The overall complexity of MaxCutPool is:
Time complexity: O NN)
Space complexity: O(E + NN)
These sub-quadratic complexities match those of the most efficient MP and trainable pooling opera- tors.
F.2 EXECUTION TIMES
Tab. 14 we report the number of seconds used by the architecture for node classification to process batch when configured with different pooling operators.
We note that one-over- methods such as Graclus, NDP, and K-MIS perform a preprocessing step on the CPU before the training starts. Such operations not accounted for in the measurements in Tab. 14, but they can take significant time and be a bottleneck in those cases that require operations such eigenvalue decomposition.
26

---

Published as a conference paper at ICLR 2025
Table 14: Execution times terms of batches processed per second (b/s) by the architecture for node
classification configured with different pooling methods.
Pooler
Roman-e.
Amazon-r.
Minesw.
Tolokers
Questions
Difipool
0.72 b/s
0.93 b/s
0.05 b/s
0.11 b/s
OOM
DMoN
0.66 b/s
0.83 b/s
b/s
0.11 b/s
OOM
MinCutPool
1.32 b/s
1.63 b/s
0.14 b/s
0.23 b/s
0OM
Top-k
0.01 b/s
0.01 b/s
0.01 b/s
0.01 b/s
0,03 b/s
Graclus
0.01 b/s
0.01 b/s
0.01 b/s
0.01 b/s
0.01 b/s
k-MIS
0.01 b/s
0.01 b/s
0.04 b/s
0.01 b/s
0.01 b/s
NDP
0.01 b/s
0.01 b/s
0.00 b/s
0.01 b/s
0.01 b/s
MaxCutPool
0.03 b/s
0.10 b/s
0.01 b/s
0.09 b/s
0.13 b/s
F.3 MEMORY USAGE
Table 15: Average and maximum GPU memory usage (in MB) by the architecture for node classifica-
tion when configured with different pooling methods.
Roman-e.
Amazon-r.
Minesw.
Tolokers
Questions
Pooler
Avg.
Max
Avg.
Max
Avg.
Max
Avg.
Max
Avg.
Max
Diffpool
7167.3
11277.2
8367.8
13165.6
1397,4
2199.4
1931.
3039.7
OOM
OOM
DMoN
5301.9
7359.5
6189.5
8591.2
1035.1
1438.2
1429.
1984.7
00M
OOM
MinCutPool
7167.8
11277.6
8367.9
13165.8
1398.0
2200.3
1932.
3040.0
0OM
0OM
Top-k
2.8
3.9
3.4
4.9
1.4
1.8
3.4
6.0
5.1
8.9
Graclus
2.5
2.6
4.0
4.1
1.5
1.5
14.6
15.1
10.4
10.6
A-MIS
1.3
1.3
0.7
0.8
0.3
0.3
2.4
2.5
5.2
5.3
NDP
1.8
9.7
0.6
2.4
70.8
2.4
26.1
MaxCutPool
13.7
25.7
16.8
31.2
6.9
12.7
27.9
52.2
32.6
61.6
EdgePool
x
Top-k MaxCutPool
8
NDP
MinCutPool
GPU VRAM usage (GB)
K-MIS
6
Graclus
DMaN
DiffPool
4
2
10
15
20
25
30
35
40
Number nodes (thousands)
Figure 11: The GPU VRAM usage the different poolers.
27

---

Published as a conference paper at ICLR 2025
In Tab. 15 report the average and maximum GPU VRAM used by the architecture for node classification on the different datasets. As for the time, the values reported for Graclus, NDP, and K-MIS do not include the SEL and CON operations performed in preprocessing.
To give a more interpretable demonstration of how the space complexity scales for the different pooling methods, in Fig. 11 report the GPU VRAM usage of the different poolers when processing a randomly generated Erdós-Renyi graph of increasing size. All the graphs are generated keeping 0.01 the probability of having edge between any pair of nodes.
The plot shows that in soft-clustering methods, the GPU VRAM usage grows exponentially with the graph size. On the other hand, for scoring-based methods, including the proposed MaxCutPool, the growth is sublinear, making these approaches extremely suitable for working with large graphs.
28


Reviews:
[{"review_id": "OyueBNpX76", "reviewer": "Reviewer_iy7r", "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.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n- The background and related work are introduced in detail and accompanied by illustrations, which greatly aid in understanding the proposed method.\n- 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.\n- 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.\n- 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?\n- 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.\n- 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.\n- 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.\n- 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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8CCT5TqZKh", "reviewer": "Reviewer_ka5D", "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.", "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?\n* 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?\n* Can the proposed method scale to graphs of arbitrary size, or are there practical limitations on the scalability threshold?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The writing is generally reader-friendly, featuring detailed illustrations such as figures and hyperparameters. Theoretical analyses are also provided.\n- The proposed method is easy to understand yet remains effective, performing well in experiments.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W9mNawr8mW", "reviewer": "Reviewer_E67D", "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.", "questions": "1. In experiment 4.1, what were the features used for GNN? Were these learnable vertex embeddings?\n2. How does maxcutpool scale with the number of vertices in a graph?\n3. 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?\n4. In experiment 4.3, could you provide the tuned baseline for a GNN with no pooling?\n5. 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.\n6. How was hyperparameter tuning performed?\n7. 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?\n8. Does the unpooling operator involve any normalization?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clearly presented\n2. The experiments are well defined and clearly motivated\n3. The authors make significant efforts to contextualize their work within the rest of the literature.\n4. The algorithm is clearly outlined in enough detail to reimplement", "weaknesses": "This paper is well written, but not without weaknesses. In particular:\n\n1. 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.\n2. The authors do not justify _why_ it is expected that the max cut should provide a better pooling operator.\n3. 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.\n4. The experiments in section 4.3 are hard to understand without a no-pooling option.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IcnUIB8KPt", "reviewer": "Reviewer_Unwn", "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.", "questions": "* l.289: Is CON always defined using the assignment matrix $\\mathbf{S}$ based on nearest neighbor aggregation?\n* How well does the differentiable MaxCut approximate MaxCut compared to more other algorithms in terms of approximation and time complexity? \n* Is the differentiable MaxCut required or does this method work with other algorithms for MaxCut?\n* How important is the nearest neighbor aggregation?\n* How do the other methods perform with the same level of hyperparameter tuning?\n* Why is there no reproducible implementation provided?", "limitations": "", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 1, "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.\n* W2: This paper proposes multiple parts without thoroughly analysing each of them:\n    * 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. \n    * 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.\n    * 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. \n* 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.\n* W4 Experiments: \n    * i) There is no reproducible implementation provided.\n    * 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.\n    * 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.\n    \nAdditional minor points:\nl.156: Sharpening propagation operators cannot learn any kind of gradients, but sharp gradients.\nl.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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)