ENAHPool: The Edge-Node Attention-based Hierarchical Pooling for Graph Neural Networks
Authors: Zhehan Zhao
Lu Bai
Lixin Cui
Ming Li
Ziyu Lyu
Lixiang Xu
Yue Wang
Edwin Hancock
Venue: ICML 2025 poster (2025)
Keywords: Graph Pooling
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a novel graph pooling operation, namely the Edge-Node Attention-based Hierarchical Pooling (ENAHPool), for GNNs to learn graph representations.

Abstract: Graph Neural Networks (GNNs) have emerged as powerful tools for graph learning, and one key challenge arising in GNNs is the development of effective pooling operations for learning meaningful graph representations. In this paper, we propose a novel Edge-Node Attention-based Hierarchical Pooling (ENAHPool) operation for GNNs. Unlike existing cluster-based pooling methods that suffer from ambiguous node assignments and uniform edge-node information aggregation, ENAHPool assigns each node exclusively to a cluster and employs attention mechanisms to perform weighted aggregation of both node features within clusters and edge connectivity strengths between clusters, resulting in more informative hierarchical representations. To further enhance the model performance, we introduce a Multi-Distance Message Passing Neural Network (MD-MPNN) that utilizes edge connectivity strength information to enable direct and selective message propagation across multiple distances, effectively mitigating the over-squashing problem in classical MPNNs. Experimental results demonstrate the effectiveness of the proposed method.

ENAHPool: The Edge-Node Attention-based Hierarchical Pooling for Graph Neural Networks
Zhehan Zhao
Lu Bai
Lixin Cui
Ming Li Ziyu Lyu
Lixiang Xu Yue Wang? Edwin R. Hancock
Abstract
and time series. However, real-world data in many domains often involve complex relationships that cannot be easily captured by regular grid formats, such as those found in social networks and molccular structures. To effectively handle such irregular data, which are typically modeled as graphs, Graph Neural Networks (GNNs) have been intro- duced. In recent years, GNNs have been widely adopted in various fields, including knowledge graphs (Schlichtkrull et al., 2018 2018), drug discovery (Sun et al., 2020), and recom- mendation systems (Wu et al., 2023).
Graph Neural Networks (GNNs) have emerged powerful tools for graph learning, and one key challenge arising in GNNs is the development of effective pooling operations for learning meaning- ful graph representations. In this paper, we pro- pose novel Edge-Node Attention-basee Hierar- chical Pooling (ENAHPool) operation for GNNs. Unlike existing cluster-based pooling methods that suffer from ambiguous node assignments and uniform edge-node information aggregation, ENAHPool assigns each node exclusively to a cluster and employs attention mechanisms to per- form weighted aggregation of both node features within clusters and edge connectivity strengths between clusters, resulting in more informative hierarchical representations. To further enhance the model performance, we introduce a Multi- Distance Message Passing Neural Network (MD- MPNN) that utilizes edge connectivity strength information to enable direct and selective message propagation across multiple distances, effectively mitigating the over-squahhig problem in classi- cal MPNNs. Experimental results demonstrate the effectiveness of the proposed method.
One challenge arising in GNNs is extracting meaningful representations for graph-level tasks, such as graph classi- fication (Errica al., 2020) and graph regression (Bianchi et al., 2020). To address this challenge, various graph pool- ing operations have been proposed, which can generally be categorized into two categories. The first category consists of global pooling methods, which aggregate all node embed- dings collectively. However, these methods fail to capture the hierarchical structures inherent graphs.
To address this issue, hierarchical pooling methods have been developed to preserve the hierarchical structure of graphs by progressively reducing their size. This reduction is typically achieved using two strategies (Ju et al., 2024). The first is the Top-K strategy, which ranks nodes based on a scoring function and retains only the Top-K nodes and their associated edges as the coarsened graph. In contrast, the cluster-based strategy groups nodes into clusters and gener- ates the coarsened graph by aggregating both node features within clusters and edge connectivity strengths between clus- ters. Since the Top-K strategy suffers from information loss due to the direct removal of nodes and edges, the cluster- based strategy is generally considered more effective.
1. Introduction
Convolutional Neural Networks (CNNs) are powerful tools for processing gridtsttuctuued data, such as text, images,
'School of Artificial Intelligence, Beijing Normal University, Beijing. China. "School of Information, Central University of Fi- nance and Economies, Beijing, China. *Zhejiang Institute of Opto- electronics, Jinhua, China. *Zhejiang Key Laboratory of Intelligent Education Technology and Application, Zhejiang Normal Univer- sity, Jinhua, China. "School of Cyber Science and Technology, Sun Yat-Sen University. Shenzhen, China. "School of Artificial Intelli- gence, Hefei Institute of Technology, Hefei, China. 'Department of Computer Science, University York, York, United Kingdom. Correspondence to: Lu Bai @aailuubbu.du...........
Unfortunately, many cluster-based methods rely on soft node assignment (Ying al., 2018), where node features are probabilistically assigned to different clusters and then summed to form cluster representations. This approach can lead to influential nodes being split across multiple clusters, while less influential nodes are assigned entirely to a single cluster, potentially causing the latter to dominate the cluster representations. Although some alternative methods, such as SEP-G (Wu al., 2022), can assign nodes single clus- ters, they still employ simple summation for aggregation,
@
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

ENAT|Pool: The Edge-Node Attention-bace based Hierarchical Pooling for Graph Neural Networks
Layeri
Hard Assignment
SH
Layer (i+1)
Node-based
MPNN Layer MD MPNN for embedding
Attention
Layer
Pooling g
Layer
Layer
MD OPNN for pooling
Edge-based based
Attention
A00
Pooling
Embeddings
...
Embedding,
...
Embedding.
Concatenation
Graph Embedding
Pigure The framework of the proposed ENAHPool operation associated with the MD-MPNN architecture.
overlooking the importance of individual nodes. To address this limitation, several studies (Liu et al., 2022; Ye et al., 2023) have introduced attention mechanisms to aggregate mode features within clusters. However, these approaches computationally expensive, due to the fact that they lack the ability process graphs in parallel way.
of the graph. As result, the receptive field of each node grows exponentially, incorporating a large amount of re- dundant information from its neighbors. Eventually, the information from such an exponentially growing receptive field is squashed into fixed-size representation, severely limiting the ability of MPNNs to capture long-range infor- mation (Alon & Yahav, 2021; Dwivedi et al., 2022).
On the other hand, when performing convolution on the coarsened graphs generated by cluster-based methods, edge connectivity strengths can naturally serve as attention weights, guiding selective information aggregation. How- ever, existing cluster-based methods typically divide each edge into different cluster pairs based the assignment probabilities of its connected nodes, and aggregate the con- nectivity strengths between identical cluster pairs via simple summation. This overlooks the importance of individual edges, resulting in aggregated edge connectivity strengths that fail to accurately reflect the influence between clusters. For example, for social network, the edge connectivity strengths between the leadership teams of Companies A and B may be equal to that between the employees of Compa- nies A and C, but the influence of B and C on A could be significantly different. Therefore, it is essential for cluster- based methods to accommodate the importance of edges when aggregating their connectivity strengths.
To overcome this limitation, some graph rewiring strate- gies have been developed. One category comprises local rewiring methods, which allows direct message passing be- tween nodes at different distances (Abboud et al., 2022: Gutteridge et al., 2023; Ding al., 2024). However, these methods treat all nodes at the same distance equally, ignor- ing the actual edge connectivity strength information among them. Another strategy is based on global rewiring, such as graph Transformers (Ying et al., 2021; Zhang et al., 2023), which construct fully connected graphs and apply attention mechanisms for information aggregation. However, these approaches tend to disregard the original graph topology.
The aim of this work is to address the aforementioned short- comings by introduce novel Edge-Node Attention- Hierarchical Pooling (ENAHPool) operation, that is pro- posed based on the Multi-Distam Distance MPNN MMDMPPNN architecture. The framework of the proposed method is illus- trated in Figure 1, and the main contributions are threefold.
Furthermore, most graph pooling operations are integrated with Message-Passing Neural Networks (MPNNs) (Gilmer et al., 2017), which often suffer from the notorious over- squashing problem (Topping et al., 2022; Giovanni et al., 2023) and influence the effectiveness of pooling methods (e.g., Figure 2). This drawback arises because MPNNs primarily rely on the iterative aggregation of information from neighboring nodes capture signals from distant parts
First, we introduce novel cluster-based hierarchical pool- ing operation, namely ENAHPool, that assigns each node exclusively to a cluster and incorporates attention mecha- nisms to identify the importance of nodes within clusters and edges between clusters. This design addresses the limi- tation of uniform edge-node information aggregation aris- ing in existing cluster-based methods and results more
2

---

ENAT|Pool: The Edge-Node Attention-base Hierarchical Pooling for Graph Neural Networks
DiffPool (Ying al., 2018) employs GNNs to generate assignment matrices, while StructPool (Yuan & Ji, 2020) captures higher-order structural relationships to guide node assignments. MinCutPool (Bianchi et al., 2020) applies spectral clustering for node grouping, and SEP-G (Wu et al., 2022) minimizes structural entropy to construct a hierarchi- cal coding tree from nodes. DMoN (Tsitsulin et al., 2023) leverages the modularity measure evaluate clustering qual- ity, whereas WGDPool (Xiao et al., 2024) introduces dif- ferentiable k-means clustering mechanism. However, these methods perform uniform aggregation by summing node features within clusters and edge connectivity strengths be- tween clusters, without considering the varying importance of individual nodes and edges. Although some methods, such as ABDPool (Liu al., 2022) and C2N-ABDP (Ye et al., 2023), incorporate attention mechanisms for node aggregation, they still overlook the importance of edges.
G1
Figure An example of the expressive limitations of conventional MPNNs, where G1 and G2 cannot be distinguished.
informative hierarchical representations. Second, pro- pose Multi-Distance MPNN architecture that works in conjunction with the proposed ENAHPool. This architec- ture enables direct message propagation between nodes at different shortest distances, effectively mitigating the over- squashing problem conventional MPNNs. Moreover, it leverages edge connectivity strength information to selec- tively aggregate information from equidistant nodes, further enhancing the representational capacity of the architecture. Third, we evaluate the classification performance of the pro- posed ENAHPool operation associated with the MD-MPNN architecture, the experiments demonstrate its effectiveness.
2.2. Message-Passing Neural Networks
Dossage-Passiigg Neural Networks (MPNNs) (Gilmer et al., 2017) are widely used framework for graph-related tasks. The message passing process consists of two main steps: (1) Initialization: node embeddings are initialized using their attributes or predefined rules, such as node degrees; and (2) Updating: node embeddings are iteratively updated by aggregating the embeddings of their adjacent nodes. After k iterations of message passing, corresponding to k layers in the network, each node incorporates information from its h-hop neighborhood. This process can be mathematically written as (Ju et al., 2024)
2. Related works
2.1. Graph Pooling
Graph pooling operations typically classified into two main categories. The first category consists of global pooling operations, which aggregate information from all node embeddings in a single step, commonly known as read- out functions. Such operations can be implemented using connutatioo-invariant functions (Duvenaud et al., 2015; Xu et al., 2019) or neural networks (Vinyals et al., 2016; Zhang et al., 2018; Baek al., 2021). However, these methods overlook the inherent hicrarchical structure characteristics of graphs (Knyazev et al., 2019; Bianchi & Lachi, 2023).
A = UPDATESA
AGGREGATE(( U
(())))))
where ! is the embedding of node u after being updated by the 1-th layer, where h is the original node feature and (u) denotes the set of adjacent nodes of node u. This message-passing paradigm has been adopted in many in- fluential works, e.g., GCN (Kipf & Welling, 2017), Graph- SAGE (Hamilton et al., 2017) and GIN (Xu et al., 2019).
To overcome this problem, hierarchical pooling operations have been developed. These operations can capture the hier- archical structures of the graph by progressively coarsening it, which is achieved through the TopK-based strategy and the cluster-based strategy. Nevertheless, these hierarchical pooling methods still rely on readout functions to extract graph representations from the coarsened graphs
However, this iterative message-passing paradigm gives rise to the over-squashing problem, which severely limits the capacity of MPNNs to capture long-range dependencies (Topping et al., 2022). To mitigate this issue. MixHop (Abu- El-Haija et al., 201 2a:b)) utilizes powers of the normalized adjacency matrix to directly aggregate information within k- hop neighborhoods. The thortest-path-unn path-aware MPNNs, such as SPN (Abboud et al., 2022) and GRED (Ding et al., 2024), directly aggregate information from nodes at different short- est path lengths, further alleviating the over- squsssqu issue. In addition, graph Transformer models, such as Graphormer (Ying et al., 2021) and GPS (Rampásek et al., 2022), can in- herently capture global context, addressing the challenge of long-range dependency modeling in conventional MPNNs.
The TopK-based strategy involves learning the importance values of nodes and selecting the Top- K nodes, along with their corresponding edges, to form the coarsened graph (Gao & Ji, 2019; Lee al., 2019). However, such methods often discard many nodes and edges, resulting in the loss of valuable information within the graph (Liu et al., 2023).
The cluster-based strategy progressively compresses the graph by clustering nodes while preserving the connections between clusters. Existing cluster-basee methods primarily foeus on optimizing the clustering process. For example,
3

---

ENAl|Pool: The Edge-Node Attention-based Hierarchical Pooling for Graph Neural Networks
1-1
Hard assignment
Aggregate with node attention
Compuie node attention
the graph
Normalize node attention each cluster
1
softmax
Figure 3. The process of hard node assignment and node aggregation using node-based attention mechanism.
However, these approaches generally overlook the edge con- nectivity strength information in the graph. Notably, the edge connectivity strengths in coarsened graphs generated by cluster-based methods reflect the influence of information propagation between clusters. Therefore, existing MPNNs are not well-suited for cluster-based pooling methods, as they fail to exploit this critical structural information.
Definition (The Hard Node Assignment). To assign
each node exclusively to a single cluster, we first employ the MD-MPNN model (as shown in Eq.(1)) to compute
the assignment matrix 5(0) E NNNN444
s MD-MPNN (A ())
(1)
where S represents the probability that the i-th node assigned the j-th cluster. Subsequently, we transform this matrix by setting the maximum value in each row of 5()) to 1 and all other values to 0, resulting in the hard assignment matrix s(I) E {0. 1) No11, which ensures that each node is uniquely assigned to the cluster with the highest probability. The (i.j)-th entry S (i. satisfies
3. The Proposed Methods
3.1. Preliminaries
We denote the input graph as ((O F)(0), where V represents the nodes and E represents the edges. Since hierarchical pooling operations alter the number of nodes at each pooling layer, we define the graph at the /-th layer as GO (V(), E()). The connectivity strengths between nodes in GO) are represented by an adjacency matrix A() E R N,,, where N₁ [(() the number of nodes I-th layer. The node feature matrix is denoted as ( E N.xid
loc, ( = argmax, (S
(2)
and
(i.) 1 io 10
{
(i. (1.)) 0 otherwise.
where di is the feature dimension at 1-th layer.
It is important to note that for these non-differentiable oper- ations, we apply the straight-through estimator (STE) algo- rithm (Yin et al., 2019) enable gradient backpropagation.
3.2. The ENAHPool Operation
An overview of the proposed ENAHPool operation is il- lustrated in Figure I, with the computational process for each /-th pooling layer comprising three main steps. First, for the input graph G(), we assign the set of nodes (() completely into N441 clusters, resulting in hard node as- signment matrix s(f) N Second, by using the node- bade- attention mechanism, we compute weights for the nodes within each cluster and aggregate them to form the compressed node feature matrix ((++1) E No+1 xd; for the coarsened graph G(++1), Third, we apply the edge-based attention mechanism assign weights to each edge, produc- ing the compressed adjacency matrix A ((+1) Ni- XN for the next layer. Details of each step defined follows.
Definition 2 (The Node-based Attention Mechanism). The process of this computational step is illustrated in Fig- ure 3. Specifically, we first calculate the importance of each node the entire graph G The input consists of a set of node embeddings z { (1) 22 ..... 2N. (9) }, which are also computed by specified MD-MPNN architecture in (16) as
(1)
z MD-MPNN, embed (x)()))))
(4)
where 27 E 4 To obtain sufficient expressive power, we commence by transforming the input embeddings ( into more meaningful representations. This is achieved by

---

ENAl|Pool: The Edge-Node crention-basce Hierarchical Pooling for Graph Neural Networks
AAC
A
C
A
C
FAC
22 +52 1)
B
D
B
D
App
E00 Axc
Ago
(1)
A BD
00)
P
Q
P
Q
(a)
(b)
Figure 4. The aggregation of edge connectivity strengths via edge-based attention mechanism.
applying shared linear transformation to every node, pa- rameterized by the weight matrix / Rd xd, where di' denotes the dimensionality of the transformed embed- dings. To introduce nonlinearity, the high-level embeddings are then passed through LeakyReLU activation function with a negative input slope of a = 0.2. Subsequently, self-attention mechanism is employed, which can be im- plemented using a fully connected layer parameterized by (!)) TRdd'. Accordingly, the importance of the i-th node in the entire graph m;
between each pair of nodes e!!) E RRNxx
! egg = =
( (w (1) w!'
(9)
Subsequently, we treat these values as edge attention co- efficients and normalize the coefficients of actual edges belonging the same pair of clusters
exple
E softmax py
(e]))= p(()))
(10)
(t) be calculated
ExEp. exp(e2))
(1) a LeakyyeLL
(5)
where the i-th and j-th nodes belong to the p-th and g-th clusters, respectively. Since the attention mechanism de can be implemented as a fully connected layer, parameter- ized by weight vector aE E R22d'. The resulting edge attention coefficients E.
Then, normalize the importance of nodes assigned to the same cluster by applying the softmax function as
can be defined as
= softmax,(m! (m))))
(6)
exp (LeakyReLU (L) (W!D 11
where p denotes the p-th cluster, and represents the i-th node assigned that cluster. Finally, we obtain the p-th cluster representation sp (f++1) of the coarsened graph ((++) by computing the weighted sum of the node embeddings within the p-th cluster, using their attention coefficients o;
E
Drepve exp [LeakyReT.U a: [ W
Finally, utilize these edge attention coefficients weights to aggregate the edge connectivity strengths be- tween each pair of clusters, resulting in the adjacency matrix Al++) of the coarsened graph ((I+1) as
(1+1) 2p
1 ())
(7)
EEP
10+1) = = (E OOOOO A
(12)
The resulting cluster representation matrix, i.e., node feature matrix ((+1) E -R-N-1xd xd of the coarsened graph G(++) can be computed by row-wisely concatenating all the coars- ened node features as
Moreover, is crucial to mention that intentionally avoid using the edge-based attention mechanism in the first pool- ing layer. The reason for this is that applying it would result in the connectivity strengths of all edges being consistently after each pooling step, which will lead to the loss of valuable information contained in the edges.
(1++1= = 11 (1+1)
(1) α 2
KEP
(The Edge-based Attention Mechanism). The process of this computational step is shown in Figure 4. Specifically, first utilize weight matrix ! E gd/ xdi and self-attention mechanism ( caleulate the attention
Definition 3
3.3. The MD-MPNN Architecture
Graph pooling operations function in conjunction with MPNNs, as they rely on the node embeddings generated
5

---

ENAT|Pool: The Edge-Node Attention- based Hierarchical Pooling for Graph Neural Networks
g
indicates that the random walk departing from the i-th node can arrive the j-th node within h steps, i.e,, may also include less than h steps. Moreover, we compute another family of binary matrices U//] E (0,1) as
Concatenation
5D=0 Message Passing
SD m1 Message Passing
SD 2 Message Passing
SD Mossage Passiing
U CLIP(R > R
(14)
where the function CLIP(s) is used to restrict the values in Un to the range [o, 1]. Specifically, (i.j) = 1 indicates that there exists random walk from the i-th node to the j-th node with walk length of at least h. In other words, it means that there are paths with shortest distance of h between the i-th and j-th nodes. With Ulll available, we construct the new topology structures T for G(D) using U masks for A i.e.,
Figure 5. The architecture of MD-MPPN, where SD=n Message- Passing indicates that message passing occurs from all nodes that are at a Shortest Distance n from the target node.
T = U + A00A
(15)
As a result, Tn contains only the edges between node pairs with a shortest path distance of h, where the edge connec- tivity strength reflects the number of such paths between them. A greater number of paths suggests a stronger influ- ence on information propagation between nodes. With Th (0 S h S H) available, the MD-MPPN architecture can be defined in terms of the node feature matrix x()) and the adjacency matrix A as
()
(
Figure 6. (a) An illustration of the graph rewiring process. Each color representing a different shortest distance from node O. For SD=n Message-Passing, direct connections are established be- tween the target node and all nodes whose shortest distance to is whose connectivity strength is the number of shortest paths. (b) The strength of a direct connection is determined by the number of shortest paths. In this example, the shortest distance between nodes O and 1 is 3, because there are three different shortest paths from node 0 node 1. highlighted in red, green, and purple.
MD-MPNN (A), ()) = 11 MPNN(T") ,.)). (16)
where the backbone of MPNN must aggregate neighbor- hood information directly from the adjacency matrix (e.g.. GCN and GIN). Other variants, such as GAT, tend to ig- nore the edge connectivity strength information in the graph structure, potentially leading to suboptimal performance.
by MPNNs. To address the over-squashing issue in conven- tional MPNNs and to effectively leverage the edge connec- tivity strength information in the coarsened graphs produced by ENAHPool, we propose a novel MD-MPNN architecture. The architecture of MD-MPNN is illustrated in Figure 5, and the graph rewiring process is shown in Figure 6.
3.4. The Computational Complexity
In our proposed method, the complexity of the MD-MPNN is O(N3), primarily due to adjacency matrix multiplica- tions. The complexities of the node and edge attention mechanisms are both O(N), as they are computed based node embeddings. The pooling operation incurs a time complexity of O(K N where K is the number of nodes in the next pooling layer, typically set to rN, with r denoting the pooling ratio. Overall, the method maintains a computa- tional complexity of ((N3), which is comparable to that of existing cluster-based hierarchical pooling approaches.
Specifically, A is obtained by raising A to the power of h, where A11) (i represents the number of h-step random walk paths from the i-th node to the j-th node in the graph. In order to propagate message on nodes at different shortest distances, we introduce mask mechanism to filter the connections in A(1) To this end, we commence by computing a family of binary matrices (!()) e {0, 10.NN, where the (ith entry (2(((,)) (1,j) satisfies
4. Experiments
- {
R (1.))
if A (1.5)>0. 0: 0 otherwise.
1
(13)
We empirically compare the proposed method with other deep learning approaches for graph classification across eight benchmark datasets: D&D (Dobson & Doig, 2003), PROTEINS (Borgwardt et al., 2005), NCII (Wale et al.,
where h varies from 0 to H, and H is a hyperparameter that represents the number of MD-MPNN layers. j) =
6

---

ENAT|Pool: The Edge-Node Aitention-based Hierarchical Pooling for Graph Neural Networks
Table J. Dataset Statistics.
Dataset
Graphs
Classes
VerticestAvg..
Edges(Avg.
Diameter(Avgg)
Clustering cocfficient(,Arg)
Label/AAttributes
Domain
D&D
1178
2
284.32
715.66
18.73
0,480
Labels
Biochemical
PROTEINS
1113
2
39,06
72.82
11.59
0,513
Labels
Blochemical
NCTI
4110
2
29.87
32.30
13.43
0.003
Labels
Biochemical
FRANKENSTEIN
4337
2
16.90
17.88
8.45
0.01
Attributes
Biochemical
IMDE-B
1030
96.53
1.86
0.947
Social
IMDB-M
1500
3
13,00
65.94
1.47
0.969
Social
COLLAB
5000
74.49
2457.78
1,86
Social
REDDIT-B
2000
2
429.63
497.75
8.49
0.059
Social
Table 2. Classification Accuracy (In % + Standard Error) for Comparisons.
D&D
PROTEINS
NCT1
FRANKENSTEIN
IMDR-B
IMDB-M
COLLAB
REDDIT-B
Se12Set
71.94 0.56
73.27 0.85
68.55 1 1.92
61.46 0.47
72.90
0.75
50.19 1: 0.39
79.55
0.39
SoriPool
75.58 0.72
73.17
0.88
73.82 1: 1.96
63.44 0.65
72.12 4: 1.12
48.18
+ 0.83
77.87
0.47
76.02 1,73
GAGPool(G)
71.54 0.91
72.02 + 1.08
74.18 +: 1.20
62,57 0.60
72.16 0.8
49.47
2 0.56
78.85 + 0.56
74.45 + 1.73
GMT
0.59
0.59
4.62
62.69 0.25
73:48 0.76
00.66:0..0 0.82
80.74 0.54
DiftPool
07.56:
73.03 1.00
62.32 4: 1.90
60.60 1.62
73.14
51.31 0.72
78.68
0.43
82.12 1.06
SAGPool(H)
74.72 0.82
71.56
1.49
67.45
1.11
61.73
0.76
72.35 + 1.28
50.23 - 0.44
78.03
0.31
75.33 + 3,53
Top
73.63 0.55
70.48
1.01
67.02
2.25
61,46
0.84
71.58 4: 0.95
48.59 +: 0.72
77.58
0.85
85.12 0.34
ASAP
76.58 11 1.04
73.92
1.922.000 0.63
71.48
0.42
66.26 0.47
72.81 1. 0.50
50.78
0.75
78.64
0.50
StructPool
78.45 +: 0.40
75.16
0.86
78.64
1.53
72.06 + 0.64
50.23
- 0.53
77.27
+ 0.51
MinCulPool
0.48
0.72
0.75
0.34
SEP-G
77.98 :: 0.57
0.39 73.24
76.42
78.35
0.33
74.12 1: 0.56
51.53 +: 0.65
81.28 +: 0.15
ABDPool
74.13 0.52
0.91
71.54
1.28
0.71 70.58
50.63 1: 1.47
82.75 0.82
ENAHPoolI-MD)
79.21 + 0.51
77.06
0.09
78.93
+ 0.47
65.43 0.21
74.44 + 0,23
51.26 + 0.38
78.37 + 0.24
85.60 + 1.06
ENAHPool
79.91
+ 0.25
77.12
1::2::000 0.15
79.34
0.31
67.68 + 0.13
74.54 = 0.42
51.74 = 0.16
81.09 + 0.51
88.56 +: 0.25
The best and second best results on each dataset in hold and underlined respectively. ENAHPool--MD) indicates the use of conventional MPNNs for computing node embeddings and assignment matrices.
standard deviation over 10 runs. For the proposed model, we perform hyperparameter tuning using a grid search strategy, as detailed in Table 3. Moreover, to ensure a fair comparison with other methods, the backbone of MPNNs is GCN.
Table 3. The Grid Search Space for the Hyperparameters.
Hyperparameter
Range
Pooling ratio
0.125, 0.25, 0.5
Pooling layer
1, 2, 3
MPNN layer
3,4,5, 6,
4.2. Results and Discussions
Table 2 demonstrates that the proposed ENAHPool oper- ation associated with the MD-MPNN architecture outper- forms all alternative methods
2008), FRANKENSTEIN (Orsini et al., 2015), IMDB-B, IMDB-M, COLLAB, and REDDIT-B (Yanardag & Vish- wanathan, 2015). Detailed statistics for these datasets are provided in Table 1. Note that when nodes in a graph lack labels or attributes, the node degree can be used as the label.
of the eight datasets. Additionally, even when the MD-MPNN architecture is omitted and conventional MPNNs are used to compute node embeddings and assignment matrices, the single ENAHPool operation still performs better than most alternative methods. The effectiveness can be attributed to two key factors.
4.1. Baselines and Experimental Settings
First, ENAHPool is the first cluster-based hierarchical pool- ing method to introduce novel attention mechanism that si- multaneously captures the importance of both nodes within clusters and edges between clusters. This effectively ad- dresses the limitation of uniform edge-node information ag- gregation in existing approaches, resulting in more informa- tive hierarchical representations. Second, the MD-MPPN architecture only alleviates the notorious over-squashing problem in conventional MPNNs, but also leverages the edge connectivity strength information computed by the edge attention mechanism, further enhancing the represen- tational power of the model.
We adopt eight hierarchical pooling methods as baselines for comparison, including DiffPool (Ying et al., 2018), SAG-
Pool(H) (Lee et al., 2019). TopKPool (Gao & Ji, 2019), ASAP (Ranjan et al., 2020), StruetPool (Yuan & Ji, 2020), MinCutPool (Bianchi al., 2020), SEP-G (Wu et al., 2022),
and ABDPool (Liu et al., 2022). Moreover, we consider four global pooling methods for comparison: Set2Set (Vinyals et al., 2016), SortPool (Zhang et al., 2018), SAGPool(G) (Lee et al., 2019), and GMT (Baek et al., 2021).
In our experiments, we employ 10-fold cross cross-valideee validation for evaluation and report the average accuracy along with the
7

---

ENAT|Pool: The Edge-Node Attention-basee Hierarchical Pooling for Graph Neural Networks
Table 4. Classification Accuracy (In % Standard Error) for validating the effectiveness of node assignment strategy.
Strategy
D&D
PROTEINS
NCI1
FRANK.
IMDB-B
IMDB-M
COLLAB
REDDIT-B
Soft assignment
77.33 +: 0.43
75.49 + 0.03
77.08
0.38
63.80 + 0.04
72.73 + 0.49
51.13
0.35
76.67
0.14
82.12 + 1.06
Hard assignment
78.34 1 0.62
76.54 1: 0.13
78.22
0.91
65.24
0.18
73.92 + 0.05
51.18 0.07
78.06
0.25
83.31 +: 1.01
Table 5. Classification Accuracy (In % Standard Error) for validating the effectiveness of attention mechanisms.
Node Att.
Edge Att.
D&D
PROTEINS
NCI1
FRANK.
IMDB-B
IMDB-M
COLLAB
REDDIT-B
0.21
0.65
0.62
0.64
4
79.50
0.52
76.73
0.33
78.85
0,42
66.09
0.58
74.31 + 1.80
51.60 + 1.00
79.38 0.13
88.21
0.51
79.88 0.16
76.79
+: 0.09
79.22 + 0.51
66.03 1: 0.16
74.29 + 0.08
51.43 1: 0.09
78.80 1 0.17
88.38
0.41
79.91 0.25
77.12
0.15
79.34 0.31
67.38 0.13
74.54 0.42
51.74 0.16
81.09
+ 0.51
88.56
0.25
D4D w00/201l
Number Pooling Layers
The Number of MD-MPNN Layers
Rc00rs0
87.20
88.6
#6.31
16.55
07.76
08.64
88.06
Accurey (1)
Accuracy (96)
86.
$0:05
31:02
72.00
80 09
9.35
02
78.51
78.89
80.09
79.43
78
0.25
5.5
0.5
5
6
Figure 7. Sensitivity analysis of the number of pooling layers and the pooling ratio.
Figure 8. Sensitivity Analysis the number of MD-MPNN layers.
thermore, both excessively large and small pooling ratios negatively affect performance. Over-compression leads to loss of structural information, whereas insufficient compres- sion results redundancy.
4.3. The Ablation Study
To further evaluate the effectiveness of each module in the proposed ENAHPool operation, we conduct ablation studies on all datasets and report the average accuracy and standard deviation over runs of 10-fold cross-validation.
Additionally, we examine the effect of the number of MD- MPNN layers (H (3, 4,5, 6, 7}). The results Figure suggest that increasing the number of MD-MPNN layers improves model performance, indicating its effectiveness in alleviating the over squashing issue in MPNNs. However, beyond a certain threshold, performance begins to decline slightly, which could be attributed to overfitting. Moreover, the optimal number of MD-MPNN layers depends on the graph size, larger graphs require more layers capture long-range node information.
Specifically, Table presents the impact of the hard node ussignment strategy (note that neither setting employs atten- tion mechanisms), and the results demonstrate its effective- ness. Table 5 evaluates the contributions of both the node and edge attention mechanisms. The results indicate that each mechanism individually improves performance, with the best results achieved when they are combined.
4.4. Hyperparameter Sensitivity Analysis
In this section, we perform three sensitivity analyses to evaluate the impact of hyperparameters on the proposed ENAHPool operation associated with the MD-MPNN ar- chitecture, using two representative datasets: D&D (from the biochemical domain with node labels) and REDDIT-B (from the social domain without node labels attributes).
5. Conclusion
In this paper, we have proposed a novel cluster-based hier- archical pooling operation (i.e., ENAHPool) for graph clas- sification. Our method employs attention mechanisms to aggregate node features within clusters and edge connectiv- ity strengths between clusters, resulting in more informative hierarchical representations. Moreover, we develop new MD-MPNN architecture to effectively alleviate the over- squashing problem arising in MPNNs, further enhancing the model performance. Experimental results indicate the effectiveness of the proposed method.
First, we examine the effect of the number of pool- ing layers (L E (1)),3)) and the pooling ratios (k E (0.125, 0.25,0.5)) 0.5}). The results in Figure indicate that model performance slightly deteriorates when more than two pooling layers are used, likely due to overfitting. Fur-
8

---

ENAt|Pool: The Edge-Node Attention-basee Hierarchical Pooling for Graph Neural Networks
Acknowledgement
Bai, L.,, Jiao, Y., Cui, L.,, Rossi, L., Wang, Y., Yu, P. S., and Hancock, E. R. Learning graph convolutional networks based on quantum vertex information propagation. IEEE Transactions on Knowledge and Data Engineering, 35 (2):1747-1760, 2023.
This work is supported by the National Natural Science Foundation of China under Grants T2122020, 61602535, and 62172370. This work also supported in part by the Jinhua Science and Technology Plan (No. 2023-3-003a), and the Program for Innovation Research in the Central University of Finance and Economics.
Bai, L., Cui, L.,, Wang, Y., Li, M., Li, J., Yu, P., and Hancock, E. R. HAQISK:
srtarchical-alignee quantum jensen-shannon kernels for graph classification. IEEE Transactions on Knowledge and Data Engineering, 36 (11):6300-384, 2024.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bianchi, F. M. and Lachi, V. The expressive power of pooling in graph neural networks. In NeurlPS, pp. 71603- 71618, 2023.
Bianchi, F. M., Grattarola, D., and Alippi. C. Spectral
References
clustering with graph neural networks for graph pooling, In ICML, volume 119, pp. 874 374-883,0 2020.
Abboud, R., Dimitrov, R., and Ceylan, i. f. Shortest path networks for graph property prediction. In LoG, volume 198, pp. 5, 2022.
Borgwardt, K. M., Ong. C. S., Schönauer, S., Vishwanathan, S. V. N., Smola, A. J., and Kriegel, Protein function prediction via graph kernels. In ISMB, pp. 47-56, 2005.
Abu-El-Haija, S., Kapoor, A., Perozzi, B., and Lee, N- GCN: multi-scale graph convolution for semi-supervised node classification. In UAI, volume 115, pp. 841-851, 2019a.
Cui, L., Bai, L., Bai, X., Wang, Y., and Hancock, Learning aligned vertex convolutional networks for graph classification. IEEE Transactions on Neural Networks and Learning Systems, (000)442224443,, 2024.
Abu-aalHaija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Steeg, G. V., and Galstyan, A. Mixhop: Higher-order graph convolutional archi- tectures via sparsified neighborhood mixing. In ICML, volume 97, pp. 21-29, 2019b.
Ding, Y., Orvieto, A., He, B., and Hofmann, Recur- rent distance filtering for graph representation learning. In ICML, 2024. URL https: / opwnrevvee.eeeeee////eeeeeoomwwe net/ forum?id forum2id=5kG.m3PP44
Dobson, P. D. and Doig, A. Distinguishing enzyme struc- tures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-78,, 2003.
Alon, U. and Yahav, E. On the bottleneck of graph neu- ral networks and its practical implications. In ICLR, 2021. URL https: /ttp//eeeeeeeee.eee/oomuu net/forum? id=1800PhoCYS
Duvenaud, D., Maclaurin, D., Aguilera-Iparraauineen Iparraguirre, J., Gómez-Bombarelli R., Hirzel, T., Aspuru-Guzik A., and Adams, R. P. Convolutional networks on graphs for learn- ing molecular fingerprints. In NeurlPS, pp. 2224-2232. 2015.
Back, J., Kang, M., and Hwang, S. J. Accurate learn- ing of graph representations with graph multiset pooling. In ICLR, 2021. URL https://// httpps:://ppeeneee /pwp///eeeee.eeeeeeeeee net/
Dwivedi, V. P., Rampásek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. In NeurIPS, volume 35, pp. 22326-22340, 2022.
Bai, L., Jiao, Y., Cui, L., and Hancock, E. R. Learning aligned-spatial graph convolutional networks for graph classification. ECML-PKDD, volume 11906. pp. 464- 482, 2019.
Errica, F., Podda, M., Bacciu, D., and Micheli, A. A fair comparison of graph neural networks for graph classifi- cation. In ICLR, 2020. URL
Bai, L., Cui, L.., and Hancock, E. R. A hierarchical transitive- aligned graph kernel for un-attributed graphs. In JCML, volume 162, pp. 1327-1336, 2022a.
net net/forund www.ooruummidddnggiegee 6NFPB.
Gao, H. and Ji, S. Graph u-nets. In ICML, volume 97, pp. 2083-2092, 2019.
Bai, L.,, Cui, L., Jiao, Y., Rossi, I.., and Hancock, E. R. Learning backtrackless aligned-spatial graph convolu- tional networks for graph classification. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 44 (2):783-798, 2022b.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In ICML., volume 70, pp. 1263-1272, 2017.
9

---

ENAt|Pool: The Edge-Node Attention-basee Hierarchical Pooling for Graph Neural Networks
Giovanni, F. D., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In ICML, volume 202, pp. 7865-7885, 2023.
Sun, M., Zhao, S., Gilvary, C., Elemento, O., Zhou, J., and Wang, F. Graph convolutional networks for compu- tational drug development and discovery. Briefings in Bioinformaties, 21(3):919-99) 2020.
Gutteridge, B., Dong, X., Bronstein, M. M., and Giovanni, F. D. Drew: Dynamically rewired message passing with delay. In ICML, volume 202, pp. 12252-12267, 2023.
Topping, J., Giovanni, D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks graphs via curvature. In ICLR, 2022. URL https: /openreview wwt. formm??rm id=7UmjRGZp-A?
Hamilton, W. L.,, Ying. 7., and Leskovec, J. Inductive representation learning on large graphs. In NeurlPS, pp. 1024-1034, 2017.
Tsitsulin, A., Palowitch, J., Perozzi, B., and Müller, Graph clustering with graph neural networks. Journal of Machine Learning Research,
Ju, W., Fang, Z., Gu, Y., Liu, Z., Long, Q. Qiao, 7., Qin, Y., Shen, J., Sun, F,, Xiao, Z., Yang, J., Yuan, J., Zhao, Y., Wang, Y., Luo, X., and Zhang, M. comprehensive survey on deep graph representation learning. Neural Networks, 173:106207, 2024.
2023.
Vinyals, O., Bengio, S., and Kudlur, M. Order matters:
Sequence to sequence for sets. In ICLR, 2016. URL
http: /tte:///rxvvv. org.oog//aaao... 51 06391.
Wale, N., Watson, I. A., and Karypis, G. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14 (3):347-375, 2008.
Kipf, T. and Welling, M. Semi-supervised classifi- cation with graph convolutional networks. In ICLR, 2017. URL pettps://openreeee wtt.r/iuwweee/oounmn 1d=SJU4ayYgl.
Wu, J., Chen, X., Xu, K., and Li, S. Structural entropy guided graph hierarchical pooling. In ICMI, volume 162, pp. 24017-24085 2022.
Knyazev, B., Taylor, G. W., and Amer, M. R. Understanding attention and generalization in graph neural networks. In NeurIPS, pp. 4204-4214 2019.
Wu, S., Sun, F., Zhang, W., Xie, X., and Cui, B. Graph neu- ral networks in recommender systems: A survey. ACM Computing Surveys, 55(5))9:11997:33 2023.
Lee, J., Lee, and Kang, J. Self-attention graph pooling. In ICML, volume 97, pp. 7734-3743, 2019.
2019.
Liu, C., Zhan, Y., Yu, Liu, L., Du, B., Hu, W. and Liu, T. On exploring node-feature and graph-structure diversities for node drop graph pooling. Neural Networks, 167:559-535 5711 2023.
Xiao, Z., Chen, H., Xiao, L.., Wei, P., Wang, T., and Li, K. Wgdpool: a broad scope extraction for weighted graph data. Expert Systems with Applications, 249:123678, 2024.
Xu, K., Hu, W., Leskove,, J., and Jegelka, S. How powerful are graph neural networks? ICLR, 2019. URL https: /
Liu, Y., Cui, L., Wang, Y., and Bai, L. Abdpool: Attention- based differentiable pooling. In ICPR, pp. 3021-3026, 2022.
Gar 61A5km.
Yanardag, P. and Vishwanathan, S. V. N. Deep graph kemels. In SIGKDD, pp. 1365-1374, 2015.
Orsini, F., Frasconi, P., and Raedt, L. D. Graph invariant kemels. In IJCAI, pp. 3756-3700 7756-7762 2015.
Ye, R., Cui, L., Rossi, L., Wang, Y., Xu, Z., Bai, L., and Hancock, E. R. C2N-ABDP: cluster-to-note attention- based differentiable pooling. In GbRPR, volume 14121, pp. 70 80, 2023.
Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, pow- erful, scalable graph transformer. In NeurlPS, volume 35, pp. 14501-14515, 2022.
Yin, P., Lyu, J., Zhang, S., Osher, S.J., Qi, Y., and Xin, J. Un- derstanding straight-through estimator training activa- tion quantized neural nets. In ICLR, 2019. URL https: //openreview rtt/foouumiiiiioe 4 RRC.
Ranjan, E., Sanyal, S., and Talukdar, P. P. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. AAAI, pp. 5470-5477, 2020.
Schlichtkrull, M. S., Kipf. N.N., Bloem, P., van den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. ESWC, volume 10843, pp. 593-607, 2018.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T. Do transformers really perform badly for graph representation? In NeurIPS, pp. 28877-28888 2021.
10

---

ENAt|Pool: The Edge-Node Attention-based Hierarchical Pooling for Graph Neural Networks
Ying. Z., You, J., Morris, C., Ren, X., Hamilton, W. L., and Leskovec, J. Hierarchical graph representation learning with differentiable pooling. In NeurlPS, pp. 4805-4815, 2018.
Yuan, H. and Ji, Structpool: Structured graph pooling via conditional random fields. In ICLR, 2020. URL https: //openreview
BJxg hVtwh.
Zhang, B., Luo, S., Wang, I.., and He, D. Rethinking the expressive power of gnns via graph biconnectiv- ity. In ICLR. OpenReview.net, 2023. URL https: 6.
Zhang, M., Cui, Z., Neumann, M., and Chen, Y. An end-to- end deep learning architecture for graph classification. In AAAL, pp. 4438-4445, 2018.


Reviews:
[{"review_id": "HGGek4bc7B", "reviewer": "Reviewer_PecS", "summary": "The paper proposes a cluster-based pooling method for graph neural networks (GNNs). The main feature of the proposal is that it performs an hard assignment of the input nodes, i.e., each node belongs to one cluster. Also, attention mechanism are employed to build node features and adjacency matrix of the coarsened graph.\n\nAdditionally, the author proposes a new GNN to mitigate the over-squashing problem of GNNs\n\nThe effectiveness of the combination between the proposed pooling and GNN is demonstrated with a set of experiment.\n\n### Update after rebuttal\nI would like to keep my score as it is since the author's response does not completely address my main concerns.\n\nI suggest the authors to add more details about the experiments to make sure that the comparison is fair. For example, the proposed architecture employs more parameters (given the same hidden size and number of layers) than the baseline methods. This was also my concern about the hard vs. soft comparison: it is not clear if only the argmax of the assignment matrix $S$  has been removed leaving everything else the same.\n\nFinally, I suggest always including the anonymized code repository in the paper.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: Convincing evidence is needed to claims that soft-assignment worsens the performance.\n\nA1: Thanks for the suggestion. We conducted comparative experiments on all datasets to verify the positive impact of the hard assignment operation on model performance. However, due to time constraints, we only report the average results from 5 runs of 10-fold cross-validation here.\n\n|Assignment strategy|D&D|PROTEINS|NCI1|FRANK.|IMDB-B|IMDB-M|COLLAB|REDDIT-B|\n|-|-|-|-|-|-|-|-|-|\n|Soft assignment|77.33 $\\pm$ 0.43|75.49 $\\pm$ 0.03|77.08 $\\pm$ 0.38|63.80 $\\pm$ 0.04|72.73 $\\pm$ 0.49|51.13 $\\pm$ 0.35|76.67 $\\pm$ 0.14|82.12 $\\pm$ 1.06|\n|Hard assignment|**78.34 $\\pm$ 0.62**|**76.54 $\\pm$ 0.13**|**78.22 $\\pm$ 0.91**|**65.24 $\\pm$ 0.18**|**73.92 $\\pm$ 0.05**|**51.18 $\\pm$ 0.07**|**78.06 $\\pm$ 0.25**|**83.31 $\\pm$ 1.01**|\n\nQ2: Convincing experiments and discussions are needed to verify the significance of different attention mechanisms.\n\nA2: Theoretically, the aim of using edge-node attentions is to obtain a more meaningful coarsened graph, capturing more accurate hierarchical representations. These two attention mechanisms are indispensable. First, without the node attention, hierarchical pooling would flatten the aggregation of nodes within a cluster, disregarding their varying importance. Second, the edge connectivity strengths between clusters naturally serve as attention during graph convolution. To better leverage this property, we propose an edge attention mechanism, which enhances the aggregation weights of important edges and prevents the neglect of rare but highly valuable connections between each cluster. \n\nThe misunderstanding may have arisen because we only presented the ablation results for two datasets in the paper. To clarify this, we conducted comparative experiments on all datasets. However, due to time constraints, we only report the average results from 5 runs of 10-fold cross-validation here. The results show that both the node and edge attention mechanism have a positive impact on model performance, though their degree of influence varies across datasets. Moreover, the best results are consistently achieved when both node and edge attention mechanisms are used together, which demonstrates the effectiveness of our approach.\n\n|Node Att.|Edge Att.|D&D|PROTEINS|NCI1|FRANK.|IMDB-B|IMDB-M|COLLAB|REDDIT-B|\n|-|-|-|-|-|-|-|-|-|-|\n|$\\times$|$\\times$|79.20 $\\pm$ 0.48|76.63 $\\pm$ 0.21|78.68 $\\pm$ 0.65|65.32 $\\pm$ 0.62|74.21 $\\pm$ 0.64|51.27 $\\pm$ 0.09|78.29 $\\pm$ 0.49|88.15 $\\pm$ 0.15|\n|$\\checkmark$|$\\times$|79.50 $\\pm$ 0.52|76.73 $\\pm$ 0.33|78.85 $\\pm$ 0.42|66.09 $\\pm$ 0.58|74.31 $\\pm$ 1.80|51.60 $\\pm$ 1.00|79.38 $\\pm$ 0.13|88.21 $\\pm$ 0.51|\n|$\\times$|$\\checkmark$|79.88 $\\pm$ 0.16|76.79 $\\pm$ 0.09|79.22 $\\pm$ 0.51|66.03 $\\pm$ 0.16|74.29 $\\pm$ 0.08|51.43 $\\pm$ 0.09|78.80 $\\pm$ 0.17|88.38 $\\pm$ 0.41|\n|$\\checkmark$|$\\checkmark$|**79.91 $\\pm$ 0.25**|**77.12 $\\pm$ 0.15**|**79.34 $\\pm$ 0.31**|**67.38 $\\pm$ 0.13**|**74.54 $\\pm$ 0.42**|**51.74 $\\pm$ 0.16**|**81.09 $\\pm$ 0.51**|**88.56 $\\pm$ 0.25**|\n\nQ3: Evaluation criteria is reasonable, but the proposed methodology is not justified enough.\n\nDue to space limitations, please refer to our response Q2 to Reviewer FuAf.\n\nQ4: The experimental design is not clear.\n\nTo minimize the impact of data partitioning on model evaluation, we followed the testing methodology from [1]. Specifically, we performed 10 random splits of each dataset and conducted 10-fold cross-validation on each split. The model was evaluated on every validation set, resulting in a total of 100 evaluation results for each method on each dataset. The experimental setup of MinCutPool differs from ours. Although it also performs 10 random splits of the dataset, it does not conduct cross-validation. This operation may make the results more sensitive to the partition, which could explain the differences in reported accuracy.\n\nIn addition, for the baselines and benchmarks that were tested in [1], we directly cite the reported results, as we follow the same experimental setup. For those not covered in [1], we adhere to the hyperparameter settings specified in the paper for evaluation.\n\nAdditionally, regarding the auxiliary classifiers, we sincerely apologize for this oversight. In the initial version of our experiments, we attempted to include this module. However, after further discussion, we decided to remove it to ensure fair comparisons with the baselines. Unfortunately, due to insufficient proofreading of the final manuscript, this change was not properly reflected in the text. We will correct this in the final version and ensure that all experimental descriptions align with our code. If necessary, we can also submit the code with anonymous link, then you can check.\n\n[1] Wu, J. et al. Structural entropy guided graph hierarchical pooling. In *ICML*, volume 162 of *Proceedings of Machine Learning Research*, pp. 24017–24030, 2022.", "claims_and_evidence": "- The paper claims that soft-assignment worsens the performance of cluster-based pooling method. Nevertheless, I did not find convincing evidence in the paper's results since Table 4 shows the results on only 2 datasets. I believe that this is a key point that justifies the proposal; thus, the difference between hard and soft assignments should have been computed on all the datasets.\n- The paper claims that coarsened graphs are usually built without considering the importance of edges. To this end, it introduces an attention mechanism to build both node features and the structure of the coarsened graph. Nevertheless, the ablation study in Table 5 does not show that employing such a mechanism is always beneficial. For example, by looking at the statistical significance of the differences among the results, it seems that node attention is unnecessary.\n\nIn general, I did not understand the idea behind the proposal, and the results were not convincing enough to justify alone the methods proposed.", "methods_and_evaluation_criteria": "The evaluation criteria is reasonable, but the proposed methodology is not justified enough.", "theoretical_claims": "Ther are no theoretical claims.", "experimental_designs_or_analyses": "The experimental design is not clear since:\n- There is no mention of how the baseline methods have been trained, and how their hyper-parameters selected;\n- It is not clear how the data have been split in training validation and test. There is onluy a mention to 10-fold cross-validation , but it is not clear if it is for model assessment or model selection\n- There is a mention to auxiliary classifiers during training, but it is not clear how they are used, and if they have been applied also for baseline methods.\n- The results of baseline method are different from the ones obtained in other papers. For example, MinCut (Bianchi et al., 2020) reaches an accuracy of 80.8 +/- 2.3 on D&D dataset, that is higher than the one reported in the paper.", "relation_to_broader_scientific_literature": "I did not carefully check if the key contributions have been discussed adequately with respect to the existing literature.", "essential_references_not_discussed": "I do not have other papers to suggest.", "other_strengths_and_weaknesses": "The paper is clear and well-written.\n\nTo the best of my knowledge, the idea is novel. However, the methodology proposed has no substantial basis.", "other_comments_or_suggestions": "Nothing.", "questions_for_authors": "Nothing.", "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": "ICoG839Az2", "reviewer": "Reviewer_foip", "summary": "This paper develops a novel graph pooling method, namely the ENAHPoo, for graph classification associated with GNNs. Different from the previous graph pooling methods, the ENAHPool simultaneously integrtes either node or edge attention for the hierarchical sturcutre learning. In addition, it also design an associated MD-MPNN mode to further mitigate the over-squashing problem through different distance relationship. Experimental evaluations demonstrates the effectiveness", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: The abstract is a little long.\n\nA1: We will update the abstract in the final version to make it more concise and easier to understand.\n\nQ2: More dataset is preferred for Ablation Study.\n\nA2: Thank you for your constructive suggestion. We have conducted the ablation experiments on all datasets. However, due to time constraints, we only report the average results from 5 runs of 10-fold cross-validation here.\n\n|Assignment strategy|D&D|PROTEINS|NCI1|FRANK.|IMDB-B|IMDB-M|COLLAB|REDDIT-B|\n|-|-|-|-|-|-|-|-|-|\n|Soft assignment|77.33 $\\pm$ 0.43|75.49 $\\pm$ 0.03|77.08 $\\pm$ 0.38|63.80 $\\pm$ 0.04|72.73 $\\pm$ 0.49|51.13 $\\pm$ 0.35|76.67 $\\pm$ 0.14|82.12 $\\pm$ 1.06|\n|Hard assignment|**78.34 $\\pm$ 0.62**|**76.54 $\\pm$ 0.13**|**78.22 $\\pm$ 0.91**|**65.24 $\\pm$ 0.18**|**73.92 $\\pm$ 0.05**|**51.18 $\\pm$ 0.07**|**78.06 $\\pm$ 0.25**|**83.31 $\\pm$ 1.01**|\n\n|Node Att.|Edge Att.|D&D|PROTEINS|NCI1|FRANK.|IMDB-B|IMDB-M|COLLAB|REDDIT-B|\n|-|-|-|-|-|-|-|-|-|-|\n|$\\times$|$\\times$|79.20 $\\pm$ 0.48|76.63 $\\pm$ 0.21|78.68 $\\pm$ 0.65|65.32 $\\pm$ 0.62|74.21 $\\pm$ 0.64|51.27 $\\pm$ 0.09|78.29 $\\pm$ 0.49|88.15 $\\pm$ 0.15|\n|$\\checkmark$|$\\times$|79.50 $\\pm$ 0.52|76.73 $\\pm$ 0.33|78.85 $\\pm$ 0.42|66.09 $\\pm$ 0.58|74.31 $\\pm$ 1.80|51.60 $\\pm$ 1.00|79.38 $\\pm$ 0.13|88.21 $\\pm$ 0.51|\n|$\\times$|$\\checkmark$|79.88 $\\pm$ 0.16|76.79 $\\pm$ 0.09|79.22 $\\pm$ 0.51|66.03 $\\pm$ 0.16|74.29 $\\pm$ 0.08|51.43 $\\pm$ 0.09|78.80 $\\pm$ 0.17|88.38 $\\pm$ 0.41|\n|$\\checkmark$|$\\checkmark$|**79.91 $\\pm$ 0.25**|**77.12 $\\pm$ 0.15**|**79.34 $\\pm$ 0.31**|**67.38 $\\pm$ 0.13**|**74.54 $\\pm$ 0.42**|**51.74 $\\pm$ 0.16**|**81.09 $\\pm$ 0.51**|**88.56 $\\pm$ 0.25**|\n\nQ3: Detailed discussion of the computational efficiency.\n\nA3: In our proposed method, each pooling layer primarily involves the following steps. First, the MD-MPNN model performs convolution operations to obtain node embeddings. The computational complexity of MD-MPNN is $O(N^3)$ due to the need for matrix multiplications on the adjacency matrix to filter node information at different distances, helping to mitigate over-squashing issue. Second, the computational complexity of both node and edge attention mechanism are $O(N)$, as they are computed based on node features. Finally, the pooling operation has a time complexity of $O(KN^2)$, where $K$ represents the number of nodes in the next pooling layer, generally set as $rN$, with $r$ denoting the pooling ratio. Overall, the proposed method maintains an overall computational complexity of $O(N^3)$, which is comparable to other classic cluster-based hierarchical pooling methods such as StructPool [1] and MinCutPool [2].\n\nIt is worth noting that our paper repeatedly emphasizes the inefficiency of using attention mechanisms for node aggregation in existing cluster-based hierarchical pooling methods. For example, ABDPool [3] computes scaled dot-product self-attention for nodes within each cluster, while C2N-ABDP [4] extracts cluster representations via singular value decomposition and then computes attention between each cluster and its nodes for weighted aggregation. These methods require iterating over every cluster, leading to high computational complexity. In contrast, the attention mechanisms we propose are significantly more computationally efficient.\n\n[1] Yuan, H. et al. Structpool: Structured graph pooling via conditional random fields. In *ICLR*, 2020. URL https://openreview.net/forum?id=BJxg_hVtwH.\n\n[2] Bianchi, F. M. et al. Spectral clustering with graph neural networks for graph pooling. In *ICML*, volume 119 of *Proceedings of Machine Learning Research*, pp. 874–883, 2020.\n\n[3] Liu, Y. et al. Abdpool: Attention-based differentiable pooling. In *ICPR*, pp. 3021–3026,2022.\n\n[4] Ye, R. et al. C2N-ABDP: cluster-to-node attention-based differentiable pooling. In *GbRPR*, volume 14121 of *Lecture Notes in Computer Science*, pp. 70–80, 2023.", "claims_and_evidence": "Yes, the claims of this paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the evaluation makes sense. Specifically, the proposed graph pooling method is very fundamental and important in the field of graph neural networks.", "theoretical_claims": "I have checked. And, all proofs of theoretical claims are correct.", "experimental_designs_or_analyses": "Yes, the experimental setting is completer and results/analyses are convincing.", "relation_to_broader_scientific_literature": "A novel framework to simultaneously capture both the node and edge attention for hierarchical structure learning, i.e. for the resulting coarsened graph by compress the nodes belonging to the same cluster.", "essential_references_not_discussed": "It seems that there is no necessary reference missed. The current references cited in this work provide sufficient contents for the proposed ENAHPool method.", "other_strengths_and_weaknesses": "Strengths:\n\nS1. A novel hierarchical pooling method associated with the node and edge attention, for learning hierarchical structures. \n\nS2. Efficient computational procedures for the node and edge attentions. \n\nS3. reduce the over-squashing problem therough the associated MD-MPNN associated with the ENAHPool.\n\nWeakness:\n\nW1. The abstract is a little long, the authors should briefly summarize the contribution, and make it shorter.\n\nW2. Although the experiments demonstrate the effectiveness, for the Ablation Study, the author only evaluate the performance on two of the datasets for classification performance comparisons. More dataset for this study is prefered, and the author can put them in the supplementary material if the space is not enough.", "other_comments_or_suggestions": "See the weakness.", "questions_for_authors": "This paper mentioned several times that the classical method is not efficient, however how about the the computational efficiency of the propose methods? I didn’t see any detailed discussion about the issue.", "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": "xJRFwF760j", "reviewer": "Reviewer_PjzN", "summary": "This paper introduces a novel graph pooling (ENAHPool), by combining the hard node assignment and the attention machnism in an interesting way. Different from other pooling operations, the new ENAHPool can compress the nodes and edges into hierarchical graphs associated with the node and edge attention rather than simply summing them up. The experiments on some standard datasets have demonstrated that the new ENAHPool can significantly improve the graph classification performance for the GNN models.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: References for the new pooling operations.\n\nA1: Thank you for your valuable suggestion. We have further investigated more recently proposed pooling operations and will refine the related work section in the final version. \n\nRecent research on graph pooling has primarily focused on cluster-based hierarchical methods. MathNet [1] leverages Haar-like wavelet multiresolution analysis to construct hierarchical graph representations. Tsitsulin et al. [2] introduced Deep Modularity Networks (DMoN), an unsupervised approach that optimizes the clustering process using the modularity measure. Bacciu et al. [3] proposed a pooling method based on Maximal k-Independent Sets (k-MIS), ensuring that selected nodes maintain a minimum pairwise distance of *k*. Zhou et al. [4] proposed Cross-View Graph Pooling, which integrates pooled graph information from both node and edge perspectives. WGDPool [5] utilizes a differentiable *k*-means clustering mechanism with Softmin assignments based on node-centroid distances.\n\n[1] Zheng, X. et al. Mathnet: Haar-like wavelet multiresolution analysis for graph representation learning. *Knowl. Based Syst.*, 273: 110609, 2023.\n\n[2] Tsitsulin, A.et al. Graph clustering with graph neural networks. *J. Mach. Learn. Res.*, 24:127:1–127:21, 2023.\n\n[3] Bacciu, D. et al. Generalizing downsampling from regular data to graphs. In *AAAI*, pp. 6718–6727, 2023.\n\n[4] Zhou, X. et al. Edge but not least: Cross-view graph pooling. In *ECML PKDD*, volume 13714 of *Lecture Notes in Computer Science*, pp. 344–359, 2022.\n\n[5] Xiao, Z. et al. Wgdpool: A broad scope extraction for weighted graph data. *Expert Syst. Appl.*, 249:123678, 2024.\n\nQ2: Detailed time complexity analysis.\n\nA2: In our proposed method, each pooling layer primarily involves the following steps. First, the MD-MPNN model performs convolution operations to obtain node embeddings. The computational complexity of MD-MPNN is $O(N^3)$ due to the need for matrix multiplications on the adjacency matrix to filter node information at different distances, helping to mitigate over-squashing issue. Second, the computational complexity of both node and edge attention mechanism are $O(N)$, as they are computed based on node features. Finally, the pooling operation has a time complexity of $O(KN^2)$, where $K$ represents the number of nodes in the next pooling layer, generally set as $rN$, with $r$ denoting the pooling ratio. Overall, the proposed method maintains an overall computational complexity of $O(N^3)$, which is comparable to other classic cluster-based hierarchical pooling methods such as StructPool [1] and MinCutPool [2].\n\n[1] Yuan, H. et al. Structpool: Structured graph pooling via conditional random fields. In *ICLR*, 2020. URL https://openreview.net/forum?id=BJxg_hVtwH.\n\n[2] Bianchi, F. M. et al. Spectral clustering with graph neural networks for graph pooling. In *ICML*, volume 119 of *Proceedings of Machine Learning Research*, pp. 874–883, 2020.\n\nQ3: Improve the performance of other GNN associated with ENAHPool?\n\nA3: Of course! Our proposed ENAHPool operation is compatible with any GNN architecture, as it focuses on aggregating nodes and edges during pooling, without constraining the choice of GNN. However, it is preferable to use a GNN that aggregates neighborhood information based on the adjacency matrix. Otherwise, it may fail to leverage the edge connectivity strengths between clusters learned by the edge attention mechanism (such as GAT), potentially causing our method to degrade into a purely node attention-based hierarchical pooling operation.\n\nQ4: Address the over-squashing problem when perform the module for multiple times?\n\nA4: To address the over-squashing issue, we analyzed the impact of the number of MD-MPNN layers on model performance (as shown in Figure 7 of the paper). The results demonstrate that, unlike traditional MPNNs, increasing the number of MD-MPNN layers gradually improves model performance, mainly due to its novel message-passing mechanism. However, once the number of layers exceeds a certain threshold, performance begins to decline slightly. This is likely because information from excessively distant nodes introduces noise, which diminishes the effectiveness of feature representation.", "claims_and_evidence": "I think the claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed ENAHPool makes sense.", "theoretical_claims": "I have checked.", "experimental_designs_or_analyses": "I have checked the experimental setups.", "relation_to_broader_scientific_literature": "The new ENAHPool can capture either node and edge attentions to re-weight the importance of the nodes belonging to the same cluster or the edges between tow clusters. So, the new pooling operation can adaptively discriminant the most significant node and edge information. This can provide useful structure feature information for the GNNs.", "essential_references_not_discussed": "The references should be completed, and well support for the new pooling operation.", "other_strengths_and_weaknesses": "This paper has some strengths, such as  \n1. This paper is well organized and easy to follow.\n2. Different from the current graph pooling operation, the new proposed ENAHPool propose a new edge-based attention to discriminate the importance of the edges between two clusters.\n3. To further improve the performance of the proposed ENAHPool, this paper also proposes a MPNN module to directly propagate the node information based on different distances, so that the new pooling operation can avoid the over-squashing problem.\nHowever, I still have some concerns for this paper, please refer to the following rebuttal questions.", "other_comments_or_suggestions": "See my rebuttal questions below.", "questions_for_authors": "1.  Can you provide some detailed time complexity analysis for the proposed ENAHPool operation? \n2. Excluding the GIN and GCN architecture, I wonder whether the proposed ENAHPool operation can be used for other GNN architecture, and improve the performance?\n3. The authors stated that the MD-MPNN medule can address the over-squarshing problem, how about perform the medule for mutiple times?", "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": "czw1STdYvI", "reviewer": "Reviewer_FuAf", "summary": "The paper proposes a methodology to perform hierarchical pooling in GNNs along with a message-passing layer that aims at reducing oversquashing (actually oversmoothing).", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: There is an ablation study but I don't feel it covers all the claims and components of the proposed methodology.\n\nA1: Due to space limitations, please refer to our response Q2 to Reviewer foip.\n\nQ2: The contribution to the basic ML research.\n\nA2: This paper proposes a new graph pooling that can overcomes the drawbacks of many existing pooling methods. Specifically, we would like to clarify that GNNs are always a crucial research direction for machine learning, and their development relies on continuously optimizing existing technologies.\n\nSpecifically, graph pooling is an essential subfield of GNNs, and most existing methods still suffer from some theoretically drawbacks. For instance, global pooling methods fail to capture hierarchical structural features of graphs. Hierarchical pooling methods based on Top-K selection discard a significant amount of node information, influencing the connectivity construction of the coarsened graph. Cluster-based hierarchical pooling methods can solve the above problems, but they typically aggregate node features and edge connectivity strengths using simple summation, ignoring the differences between nodes and edges. Thus, we propose applying attention mechanisms for weighted aggregation, resulting in more effective coarsened graph representations.\n\nThe attention mechanism has been widely applied across various fields. Its core idea is to dynamically assign weights to capture key information, enhancing the model's representation capability. Recently, attention mechanisms have gained traction in graph tasks. For instance, [1] and [2] employ multi-head attention to assess neighbor importance, enabling differentiated aggregation for effective node representations. In graph pooling, [3] uses soft attention to weight node importance, while [4] applies multi-head attention to identify task-relevant parts of the input data and learn each node’s global significance after pooling. [5] integrates attention into second-order pooling, further boosting model expressiveness. Inspired by these works, we introduce a node attention mechanism akin to the self-attention mechanism  in [6], whose success highlights its ability to focus on graph-relevant nodes, providing a solid theoretical foundation for our approach.\n\nAmong existing methods, edge attention mechanisms remain underexplored. A notable example is [7], which leverages attention to compute edge contraction scores. Another approach, [8], suggests assigning higher importance to edges connecting more different nodes. Inspired by these works, we introduce an edge attention mechanism akin to the edge information scoring function in [9]. The success of [9] demonstrates its ability to identify important edges in a graph, providing a strong theoretical foundation for our edge attention aggregation strategy.\n\nHowever, it is important to note that while GAT can be seen as an exploration of edge attention mechanisms, it essentially computes node attention to selectively aggregate neighboring node information, without directly processing edges. This differs from ours, which is designed to aggregate edge connectivity strengths between clusters. The connectivity strengths in the coarsened graph reflects the influence of the information propagation between clusters, determined by both edge importance and quantity. For instance, in a social network, the number of edges between the leadership teams of Companies A and B may be the same as that between the employees of Companies A and C, yet B and C’s influence on A could differ. Our edge attention mechanism aims to capture such differences.\n\nIn conclusion, we believe this study provides both practical improvements and a new perspective for theoretical research in machine learning.\n\n[1] Velickovic, P. et al. Graph attention networks. In *ICLR*, 2018. URL https://openreview.net/forum?id=rJXMpikCZ.\n\n[2] Zhang, J. et al. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In *UAI*, pp. 339–349, 2018.\n\n[3] Li, Y. et al. Gated graph sequence neural networks. In *ICLR*, 2016. URL http://arxiv.org/abs/1511.05493.\n\n[4] Xu Y. et al. Multistructure graph classification method with attention-based pooling. In *IEEE TCSS*, 10(2): 602-613, 2022.\n\n[5] Wang Z. et al. Second-Order Pooling for Graph Neural Networks. In *TPAMI*, vol. 45, no. 6, pp. 6870-6880, 2023.\n\n[6] Lee, J. et al. Self-attention graph pooling. In *ICML*, volume 97 of *Proceedings of Machine Learning Research*, pp. 3734–3743, 2019.\n\n[7] Diehl, F. et al. Towards graph pooling by edge contraction. In *ICML workshop*, 2019.\n\n[8] Gao, Z. et al. Lookhops: light multi-order convolution and pooling for graph classification. *CoRR*, 2020. URL https://arxiv.org/abs/2012.15741.\n\n[9] Yu H. et al. Not all edges are peers: Accurate structure-aware graph pooling networks. In *NN*, 156: 58-66, 2022.\n\nQ3: There are several references missing.\n\nA3: Due to space limitations, please refer to our response Q1 to Reviewer PjzN.", "claims_and_evidence": "No. There is an ablation study but I don't feel it covers all the claims and components of the proposed methodology.\nAnyway, that is not the main issue.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "There are no theoretical contributions in this work.", "experimental_designs_or_analyses": "The experimental evaliuation is rather standard.", "relation_to_broader_scientific_literature": "The components of the proposed methodology are not novel as they appear in one or more papers from the GNN literature of the last 9 years.", "essential_references_not_discussed": "There are several references missing.", "other_strengths_and_weaknesses": "All the methods proposed in this paper are not new and appear in one or more papers from the GNN literature of the last 9 years.\nThese include:\n- using straight-through estimator to make S binary\n- using attention in pooling (see e.g., Understanding attention and generalization in graph neural networks from 2019)\n- Using attention mechanism to weight the edges (see GAT)\n- using heat kernels and random walk in message passing (e.g., Diffusion Improves Graph Learning from 2019)\n\nAs is, the paper is more a collection of tricks and optimizations rather than a proposal of a new idea and methodology. That would be OK if this was an applied work to solve a specific problem, which is not the case.\nI do not see a contribution to the basic ML research.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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:

Meta-review: This paper proposes a method called ENAHPool to enhance Graph Neural Networks (GNNs). It performs hard node assignments to clusters and aggregates node features and edge connectivity with learned attention weights, which reduces ambiguity compared to soft assignments.  The dual attention mechanism helps to learn more expressive coarsened graph representations. The paper also proposes a companion architecture called MD-MPNN to alleviate the over-squashing problem. However, there are concerns that it combines too many components, which increases complexity and makes it hard to isolate each contribution. There is no strong theoretical justification or proof provided. Overall, this is a good paper and should be considered if there is room in the program.
Decision: Accept (poster)