The expressive power of pooling in Graph Neural Networks
Authors: Filippo Maria Bianchi
Veronica Lachi
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Graph pooling
Expressive power
TL;DR: Formal conditions for the expressiveness of pooling operators in graph neural networks.

Abstract: In Graph Neural Networks (GNNs), hierarchical pooling operators generate local summaries of the data by coarsening the graph structure and the vertex features. Considerable attention has been devoted to analyzing the expressive power of message-passing (MP) layers in GNNs, while a study on how graph pooling affects the expressiveness of a GNN is still lacking. Additionally, despite the recent advances in the design of pooling operators, there is not a principled criterion to compare them. In this work, we derive sufficient conditions for a pooling operator to fully preserve the expressive power of the MP layers before it. These conditions serve as a universal and theoretically-grounded criterion for choosing among existing pooling operators or designing new ones. Based on our theoretical findings, we analyze several existing pooling operators and identify those that fail to satisfy the expressiveness conditions. Finally, we introduce an experimental setup to verify empirically the expressive power of a GNN equipped with pooling layers, in terms of its capability to perform a graph isomorphism test.

The expressive power of pooling in Graph Neural Networks
Filippo Maria Bianchi"
Veronica Lachi"
Dept. of Mathematics and Statistics UiT the Arctic University of Norway NORCE, Norwegian Research Centre AS filippo... m. bianchi no
Dept. of Information Engineering and Mathematics University of Siena
veronica. www.lllahhhhsseeeee unisi. it
Abstract
In Graph Neural Networks (GNNs), hierarchical pooling operators generate local summaries of the data by coarsening the graph structure and the vertex features. While considerable attention has been devoted to analyzing the expressive power of pressage-passing (MP) layers in GNNs, study on how graph pooling affects the expressiveness of a GNN is still lacking. Additionally, despite the recent advances in the design of pooling operators, there not principled criterion to compare them. In this work, we derive sufficient conditions for pooling operator to fully preserve the expressive power of the MP layers before These conditions serve as universal and theoretically grounded criterion for choosing among existing pooling operators or designing new ones. Based on our theoretical findings, we analyze several existing pooling operators and identify those that fail to satisfy the expressiveness conditions. Finally, we introduce an experimental setup to verify empirically the expressive power of a GNN equipped with pooling layers, in terms its capability to perform a graph isomorphism test.
1 Introduction
Significant effort has been devoted to characterizing the expressive power of Graph Neural Networks (GNNs) in terms of their capabilities for testing graph isomorphism [34]. This has led to a better understanding of the strengths and weaknesses of GNNs and opened up avenues for developing advanced GNN models that go beyond the limitations of such algorithms [32]. The more powerful GNN, the larger the set of non-isomorphic graphs that it can distinguish by generating distinet representations for them. GNNs with appropriately formulated meessgge-passigg (MP) layers are as effective as the Weisfeiler-Lehmar isomorphism test (WL test) in distinguish graphs [38], while higher-order GNN architectures can match the expressiveness of the k- WL test [29]. Several approaches have been developed to enhance the expressive power of GNNs by incorporating random features into the nodes [33, 1]. by using randomized weights in the network architecture [42], or by using compositions of invariant and equivariant functions [27]. Despite the progress made in understanding the expressive power of GNNs, the results are still limited to flat GNNs consisting of stack of MP layers followed by a final readout [38, 5].
Inspired by pooling in convolutional neural networks, recent works introduced hierarchical pooling operators that enable GNNs to learn increasingly abstract and coarser representations of the input graphs [39, 9]. By interleaving MP with pooling layers that gradually distill global graph properties through the computation of local summaries, it is possible to build deep GNNs that improve the accuracy in graph classification [8, 4] and node classification tasks [18, 26].
"Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

It is not straightforward to evaluate the power of a graph pooling operator and the quality of the coarsened graphs it produces. The most common approach is to simply measure the performance of GNN with pooling layers on downstream task, such as graph classification. However, such an approach is highly empirical and provides an indirect evaluation affected by external factors. One factor is the overall GNN architecture: pooling is combined with different MP layers, activation functions, normalization or dropout layers, and optimization algorithms, which makes it difficult to disentangle the contribution of the individual components, Another factor is the dataset at hand: some classification tasks only require isolating a specific motif in the graph [23, 7], while others require considering global properties that depend on the whole graph structure [15]. Recently, two criteria were proposed to evaluate a graph pooling operator in terms of i) the spectral similarity between the original and the coarsened graph topology and ii) its capability of reconstructing the features of the original graph from the coarsened one [20]. While providing valuable insights, these criteria give results that are, to some extent, contrasting and in disagreement with the traditional evaluation based on the performance of the downstream task.
To address this issue, we introduce universal and principled criterion that quantifies the power of a pooling operator as its capability to retain the information in the graph from an expressiveness perspective. In particular, we investigate how graph pooling affects the expressive power of GNNs and derive sufficient conditions under which the pooling operator preserves the highest degree of expressiveness. Our contributions summarized follows.
We show that when certain conditions are met in the MP layers and in the pooling operator, their combination produces an injective function between graphs. This implies that the GNN can effectively coarsen the graph to learn high-level data descriptors, without compromising its expressive power.
Based on our theoretical analysis. we identify commonly used pooling operators that do not satisfy these conditions and may lead to failures in certain scenarios.
We introduce a simple yet effective experimental setup for measuring, empirically, the expressive power of any GNN in terms of its capability perform a graph isomorphism test.
Besides providing criterion for choosing among existing pooling operators and for designing new ones, our findings allow us to debunk criticism and misconceptions about graph pooling.
2 Background
2.1 Graph neural networks
Let G = EV,E) be graph with node features X E RNF,, where |/ N. Each row x E R of the matrix X represents the initial node feature of the node i, Vi = 1 JI....,N. N. Through the MP layers GNN implements local computational mechanism to process graphs [19]. Specifically, each feature vector x, updated by combining the features of the neighboring nodes. After iterations, x!, embeds both the structural information and the content of the nodes in the (-hop neighborhood of v. With enough iterations, the feature vectors can be used to classify the nodes or the entire graph. More rigorously, the output of the /-th layer of MP-GNN is:
COMBINE (1) (x!-1. AGGREGATE ((xL)) U E ((o)))
where ( is a function that aggregates the node features from the neighborhood. A/oe] at the (1 - 1)-th iteration, and (DMBINE()) is a function that combines the own features with those of the neighbors. This type of MP-GNN implements and the information propagation is isotropic [35]. In graph clasiffcation//egression tasks, a READOUT function typically transforms the feature vectors from the last layer L to produce the final output:
innvaration-invaiiant feature aggregation functions
o = READOUT ( U V)).
The READOUT is implemented as the sum, mean, or the maximum of all node features, or by more elaborated functions [11, 40, 22].

---

2.2 Expressive power of graph neural networks
When analyzing the expressive power of GNNs, the primary objective is to evaluate their capacity to produce different outputs for non non-isomorphic graphs. While an exact test for graph isomorphism has combinatorial complexity [2]. the WL test for graph isomorphism [37] is a computationally efficient yet effective test that can distinguish broad range of graphs. The algorithm assigns to each graph vertex a color that depends on the multiset of labels of its neighbors and on its own color. At each iteration, the colors of the vertices are updated until convergence is reached.
There a strong analogy between an iteration of the WL-test and the aggregation scheme implemented by MP in GNNs. In fact, it has been proven that MP-GNNs are at most as powerful as the WL test in distinguishing different graph-structured features [38, 29]. Moreover, if the MP operation is injective, the resulting MP-GNN is as powerful as the WL test [38]. The Graph Isomorphism Network (GIN) implements such an injective multiset function as:
= MLP(() (1 + (1+c)x)
E
Under the condition that the nodes' features are from a countable multiset, the representational power of GIN equals that of the WL test. Some GNNs can surpass the discriminative power the WL test by using higher-order generalizations of MP operation [29], or by using a composition of invariant and equivariant functions [27], at the price of higher computational complexity. In this work, we focus on the standard MP-GNN, which remains the most widely adopted due to its computational efficiency.
2.3 Graph pooling operators
A graph pooling operator implements a function POOL: G + - 9p (Vp, Ep) such that [Vp] = K, with K S N. We let X R be the pooled nodes features, i.e., the features of the nodes Vp in the pooled graph. To formally describe the POOL function, we adopt the Senect-Redue--Coomee (SRC) framework [20], that expresses a graph pooling operator through the combination of three functions: selection, reduction, and connection. The selection function (SEL) clusters the nodes of the input graph into subsets called supernodes, namely SEL G + S (S ,,,,,...SS Sk} with
S, = { i=1 where sf is the membership score of node to supernode j. The memberships are
conveniently represented by a cluster assignment matrix S, with entries [S]; = s!_ Typically, a node can be assigned to zero, one, or several supernodes, each with different scores. The reduction function (RED) creates the pooled vertex features by aggregating the features of the vertices assigned to the same supernode, that is, RED: (G, S) + Xp. Finally, the connect function (CON) generates the edges, and potentially the edge features, by connecting the supernodes.
3 Expressive power of graph pooling operators
We define the expressive power of a graph pooling operator its capability of preserving the expressive power of the MP layers that came before it. We first present our main result, which is a formal criterion to determine the expressive power of pooling operator. In particular, we provide three sufficient (though not necessary) conditions ensuring that if the MP and the pooling layers meet certain criteria, then the latter retains the same level of expressive power as the former. Then, analyze several existing pooling operators and analyze their expressive power based on those criteria.
3.1 Conditions for expressiveness
Theorem 1. Ler G1 (V1, E with [Vil= N and G2 (V2, E2) with \V2l M with node features X and Y respectively, such that G1 #WL Gz. Let G and G be the graph obtained after applying block of L MP layers such that X E XXF and Y E IR. M are the new nodes features. Let POOL a pooling operator expressed by the functions SEL, RED, CON, which is placed after the MP (OO and G2p POOL(Gh)) with |V -122
K. Let Xp E KF and Yp E RK*F be the nodes features of the pooled graphs so that the rows xp, y represent the features of supernode in graphs Gip and G2p, respectively. the following conditions hold:
layers. Let G1p
3

---

1. Σ x y!:
2. The memberships generated by SEL satisfy Σj=1 Si = X, with X > 0 foror each node i, i.e., the cluster assignment matrix S is a right stochastic matrix up to the global constant X;
3. The function RED is of type RED (X", X. x
then Dip and G2p will have different nodes features, i.e, for all rows' indices permutations {1, K} [I....K], X, + r)), where (TT(Y r) yrowr
The proof can be found in Appendix A and schematic summary is in Fig. 1.
Cond. 2
$1
A, v6
91
91p tWE
FWL G2
GNN
X x
xf
g2,
Cond.
X S
Cond.
Figure I: A GNN with expressive MP layers (condition 1) computes different features X and X for two graphs Gi, G2 that WL-distinguishable A pooling layer satisfying the conditions 2 and generates coarsened graphs Gip and O2p that are still WL--istinguishable
Condition 1 is strictly related to the theory of multisets. Indeed, major breakthrough in designing highly expressive MP layers was achieved by building upon the findings of Deep Sets [41]. Under the assumption that the node features originate from a countable universe, has been formally proven that there exists a function that, when applied to the node features, makes the sum over a multiset of node features injective [38]. The universal approximation theorem guarantees that such a function can be implemented by an MLP. Moreover, if the pooling operator satisfies conditions 2 and 3, it will produce different sets of node features. Due to the injectiveness of the coloring function of the WL algorithm, graphs with different multisets of node features will be classified non-isomorphic by the WL test and, therefore, G1p FWL G2p- This implies that the pooling operator effectively coarsens the graphs while retaining all the information necessary to distinguish them. Therefore, our Theorem ensures that there exists a specific choice of parameters for the MP layer that, when combined with pooling operator satisfying the Theorem's conditions, the resulting GNN architecture is injective.
Condition implies that all nodes the original graph must contribute to the supernodes. Moreover, letting the sum of the memberships siy to be constant À (usually, À 1), places restriction the formation of the super-node nodes. Condition 3 requires that the features of the supernodes Xp are convex combination of the node features X It is important to note that the conditions for the expressiveness only involve SEL and RED, but not the CON function. Indeed, both the graph's 's topology embedded in the features of the supernodes by MP and pooling layers
and the nodes' features satisfying the conditions Th. 1. Nevertheless, even a behavebe CON function does not affect the expressiveness of the pooling operator, it can still compromise the effectiveness of the MP layers that come afterward. This will be discussed further in Sections 3.3 and 4.
3.2 Expressiveness of existing pooling operators
The SRC framework allows building a comprehensive taxonomy of the existing pooling operators, based on the density of supermodes, the trainability of the SEL, RED, and CON functions, and the adaptability of the number of supernodes K [20]. The density of pooling operator is defined as the expected value of the ratio between the cardinality of supernode and the number of nodes in the graph. method is referred to as dense if the supernodes have cardinality O(N), whereas a pooling operator is considered sparse if the supernodes generated have constant cardinality O(1) [20].

---

Pooling methods can also be distinguished according to the number of nodes K of the pooled graph. If K is constant and independent of the input graph size, the pooling method is fixed. On the other hand, if the number of supernodes is a function of the input graph, the method is adaptive. Finally, in some pooling operators the SEL, RED, and CON functions can be learned end-to-end along with the other components of the GNN architecture. In this case, the method is said to be trainable, meaning that the operator has parameters that are learned by optimizing a task-driven loss function. Otherwise, the methods are non-trainable.
Dense pooling operators Prominent methods in this class of pooling operators are DiffPool [39], MinCutPool [8], and DMoN [36]. Besides being dense, all these operators are also trainable and fixed. DiffPool, MinCutPool, and DMoN compute cluster assignment matrix S E IK N* either with an MLP or an MP-layer, which is fed with the node features X" and ends with a sof The main difference among these methods is in how they define unsupervised auxiliary loss functions, which are used to inject a bias how the clusters are formed. Thanks to the softmax normalization, the cluster assignments sum up to one, ensuring condition 2 of Th. 1 to be satisfied. Moreover, the pooled node features are computed as Xp = x making also condition 3 satisfied.
There are dense pooling operators that use algorithms such non-negative matrix factorization [3] to obtain a cluster assignment matrix S, which may not satisfy condition 2. Nonetheless, it is always possible to apply a suitable normalization to ensure that the rows S sum up to a constant. Therefore, we claim that all dense methods preserve the expressive power of the preceding MP layers.
Non-expressive sparse pooling operators Members of this category are Top-k [18, 23] AS- APool [31], SAGPool [24] and PanPool [26]. which are also trainable and adaptive. These methods reduce the graph by selecting a subset of its nodes based on ranking score and they mainly differ in how their SEL function computes such a score. Specifically, the Top-k method ranks nodes based on a score obtained by multiplying the node features with a trainable projection vector. A node i is kept (s; = 1) if among the top-K in the ranking and is discarded (s; 0) otherwise. SAGPool simply replaces the projection vector with an MP layer to account for the graph's 's structure when scoring the nodes. ASAPool, instead, examines all potential local clusters in the input graph given a fixed receptive field and it employs an attention mechanism to compute the cluster membership of the nodes. The clusters are subsequently scored using particular MP operator. Finally, in PanPool the scores are obtained from the diagonal entries of the maximal entropy transition matrix, which is generalization of the graph Laplacian.
Regardless of how the score is computed, all these methods generate a cluster assignment matrix S where not all the rows sum constant. Indeed, if a node not selected, it is not assigned to any supernode in the coarsened graph. Therefore. these methods fail to meet condition 2 of Theorem 1. Additionally, in the RED function of all these methods the features of each selected node are multiplied by its ranking score, making condition 3 also unsatisfied.
20A
Mp<0
Figure 2: Example of failure of Top-k pooling. Given two WL- distinguishable graphs with node fea- tures x1 S x2 S 23 I4,, two scor- ing vectors $1 and 82 are computed using projector p. Then, the two nodes associated with the highest scores are selected. If p < 0, nodes 1 and 2 are chosen in both graphs. Conversely, if p > O, nodes 3 and 4 are selected. Therefore, regardless of the value learned for the projec- tor the two input graphs will be mapped into the same pooled graph.
81
472
23
# WL
WL
274
Mps0
82
.3
1p30
3
Intuitively, these operators produce a pooled graph that is a subgraph of the original graph and discard the content of the remaining parts. This hinders the ability to retain all the necessary information for
5

---

preserving the expressiveness of the preceding MP layers. The limitation of Top-k is exemplified in Fig. 2: regardless of the projector p. Top-k maps two WL-distinguishable graphs into two isomorphic graphs, meaning that it cannot preserve the partition on graphs induced by the WI. test.
Expressive sparse pooling operators Not all sparse pooling operators coarsen the graph by selecting a subgraph. In fact, some of them assign each node in the original graph to exactly one supernode and, thus, satisfy condition 2 of Th. 1. In matrix form and letting À = 1, the cluster assignment would be represented by a sparse matrix S that satisfies S k = 1v and where every row has one entry equal to one and the others equal to zero. Within this category of sparse pooling operators, notable examples include Graclus [13], ECPool [14], and k-MISPool [4].
Graclus is a non-trainann non-trainable, greedy bottom-up spectral clustering algorithm, which matches each vertex with the neighbor that is closest according to the graph connectivity [13]. When Graclus is used to perform graph pooling, the RED function is usually implemented as a max_pool operation between the vertices assigned to the same cluster [12]. In this work, to ensure condition of Th. to be satisfied, we use sum_pool operation instead. Contrarily from Gralcus, ECPool, and k-MISPool are trainable. ECPool first assigns to each edge et-j a score rsj f(r 2 θ). Then, iterates over each edge Ez-ij, starting from those with higher scores, and contracts it if neither nodes and j are attached to an already contracted edge. The endpoints of contracted edge are merged into a new supernode S₁ riy (z: + æ.)). while the remaining nodes become supernodes themselves. Since each supernode either contains the nodes of a contracted edge or is node from the original graph, all columns of S have either one or two entries equal to one, while each row sums up to one. The RED function can be expressed as r O X where r[A] = Tiy if is the contraction of two nodes i j. otherwise r[k] 1. As result, ECPool met the expressiveness conditions of Th. 1. Finally, k-MISPool identifies the supernodes with the centroids of the maximal k-independent sets of graph [6]. To speed up computation, the centroids are selected with a greedy approach based ranking vector и. Since π can be obtained from a trainable projector p applied to the vertex features, =X'p". k-MISPool is trainable pooling operator. k-MISPool assigns each vertex to one of the centroids and aggregates the features of the vertex assigned to the same centroid with a sum_pool operation create the features of the supernodes. Therefore, k-MISPool satisfies the expressiveness conditions of Th. 1.
A common characteristic of these methods is that the number of supernodes K cannot be directly specified. Graclus and ECPool achieve a pooling ratio of approximately 0.5 by roughly reducing each time the graph size by 50%. On the other hand, k-MISPool can control the coarsening level by computing the maximal independent set from G which is the graph where each node of g is connected to its h-hop neighbors. As the value of k increases, the pooling ratio decreases.
3.3 Criticism on graph pooling
Recently, the effectiveness of graph pooling has been questioned using as argument set of empir- ical results aimed at exposing the weaknesses of certain pooling operators [28]. The experiments showed that using randomized cluster assignment matrix S (followed by a tmax normalization) gives comparable results to using the assignment matrices learned by Diffpool [39] and MinCut- Pool [8]. Similarly, applying Graclus [13] on the complementary graph would give performance similar to using the original graph.
We identified potential pitfalls in the proposed evaluation, which considered only pooling operators that are expressive and that, even after being modified, retain their expressive power. Clearly, even if expressiveness ensures that all the information is preserved in the pooled graph, its structure is corrupted when using a randomized S or a complementary graph. This hinders the effectiveness of the MP layers that come after pooling, as their inductive biases no longer match the data structure they receive. Notably, this might not affect certain classification tasks where the goal is to detect small structures, such as motif in molecule graph [25, 21J, that are already captured by the MP layers before pooling.
To address these limitations, first, we propose to corrupt pooling operator that is not expressive. In particular, we design a Top-k pooling operator where the nodes are ranked based on a score that is sampled from a Normal distribution rather than being produced by trainable function of the vertex features. Second, we evaluate all the modified pooling operators in a setting where the MP layers after pooling are essential for the task and show that the performance drop is significant.

---

4 Experimental Results
To empirically confirm the theoretical results presented in Section 3, we designed a synthetic dataset that is specifically tailored to evaluate the expressive power of GNN. We considered GNN with MP layers interleaved with 10 different pooling operators: DoffPool [39], DMoN [36], MinCut [8], ECPool [14]. Graclus, k-MISPool [4], Top-k [18], PanPool [26], ASAPool [31], and SAGPool [24]. For each pooling method, we used the implementation in Pytorch Geometric [17] with the default
configuration. In addition, following the setup used to criticize the effectiveness of graph pooling [28], we considered the following pooling operators: Rand- Rand-Dense, dense pooling operator where the cluster assignment a normalized random matrix; Rand-Sparse, sparse operator that ranks nodes based score sampled from Normal distribution; Cmp-Graclus, an operator that applies the Graclus algorithm on the complement graph.
4.1 The EXPWL1 dataset
Our experiments aim at evaluating the expressive power of MP layers when combined with pooling layers. However, existing real-world and synthetic benchmark datasets are unsuitable for this purpose as they are not specifically designed to relate the power of GNNs to that of the WL test. Recently, the EXP dataset was proposed to test. the capability of special GNNs to achieve higher expressive power than the WL test [1]. which, however, goes beyond the scope of our evaluation. Therefore, we introduce a modified version of EXP called EXPWLI, which comprises a collection of graphs [GI...., GN. H1, :..... H.N representing propositional formulas that can be satisfiable or unsatisfiable. Each pair (g,. H() in EXPWL1 consists of two non-isomorphic graphs distinguishable by WL test, which encode formulas with opposite SAT outcomes. Therefore, any GNN that has an expressive power equal to the WL test can distinguish them and achieve approximately 100% classification accuracy on the dataset. Compared to the original EXP dataset, we increased the size of the dataset to a total of 3000 graphs and we also increased the size of each graph from an average of 55 nodes to 76 nodes. This was done to make it possible to apply aggressive pooling without being left with a trivial graph structure. The EXPWL1 dataset and the code to reproduce the experimental results are publicly available?.
4.2 Experimental procedure
To empirically evaluate which pooling operator maintains the expressive power of the MP layers preceding it, we first identified a GNN architecture without pooling layers, which achieves approx- imately 100% accuracy on the EXPWLI. We tried different baselines (details in Appendix C.I) and we found that GNN with three GIN layers [38] followed by ggloblllssus sum_ sum__pool reaches the desired accuracy. Then, we inserted a pooling layer between the 2nd and 3rd GIN layer, which performs an aggressive pooling by using a pooling ratio of 0.1 that reduces the graph size by 90%. The details of the GNN architectures are in Appendix C.2. Besides 0. we also considered additional pooling ratios and we reported the results in Appendix C.3. To ensure fair comparison, when testing each method we shuffled the datasets and created 10 different train/validaa validatioon/esst splits using the same random seed. We trained each model on all splits for 500 epochs and reported the average training time and the average test accuracy obtained by the models that achieved the lowest loss on the validation set. To validate our experimental approach, we also measured the performance of the proposed GNN architecture equipped with the different pooling layers on popular benchmark datasets for graph classification [30, 10].
4.3 Experimental Results
Table reports the performances of different pooling operators on EXPWL1. These results are consistent with our theoretical findings: pooling operators that satisfy the conditions of Th. achieve the highest average accuracy and, despite the aggressive pooling, they retain all the necessary information to achieve the same performance of a GNN without a pooling layer. On the other hand, non-expressive pooling operators achieve significantly lower accuracy as they are not able to correctly distinguish all graphs.
www.reseeeeeeeeeeeeeeeeeeeee www.eee--owwoo-ee pfwer-of-pooling in- GNNs
7

---

Pooling
s/epoch
GIN layers
Pool Ratio
Test Acc
Expressive
No-pool
0.33s
99.3
DifiPool
0.69s
2+1
0.1
97.0+2.4
DMoN
0.75s
2+1
0.1
99.010.7
MinCut
0.72s
2+1
0.1
98.8+0.4
ECPool
20.71s
2+1
0.2
100.0=0.0
Graclus
1.00s
2+1
99.9
k-MIS
1.17s
2+1
0.1
99.9+0.1
Top-k
0.47s
2+1
0.1
67.9+13.9
X
PanPool
3.82s
2+1
0.1
63.2+7.7
ASAPool
1.11s
1+1
83.5+2.5
SAGPool
0.59s
1+1
0.1
79.529.6
Rand-dense
0.41s
2+1
0.1
91.7+1.3
Cmp-Graclus
8.08s
2+1
0.1
91.9+1.2
Rand-sparse
0.47s
241
0.1
62.8
X
Table 1: Classification results on EXPWLI.
Table also shows that employing pooling operator based on a normalized random cluster assign- ment matrix (Rand-dense) or the complement graph (Cmp-Graccus) gives a lower performance. First of all, this result disproves the argument that such operators are comparable the regular ones [28]. Additionally, we notice that the reduction in performance is less significant for Rand- mende and Cmp-Grachie than for Rand-sparse. This outcome expected because, in terms of expressiveness. Rand-dense and Cmp-Graclus still satisfy the conditions of Th. 1. Nevertheless, their performance is still lower than their regular counterparts. The reason is that even a hadly-behaved CDN function does not compromise the expressiveness of the pooling operator, the structure of the pooled graph corrupted when utilizing a randomized or a complementary graph. This, in return, reduces the effectiveness of the last GIN layer, which is essential correctly classify the graphs in EXPWLI.
There are remarks about the experimental evaluation. As discussed in Section 3.2, it is possible to explicitly specify the pooling ratio in Graclus, ECPool. and k-MISPool. For k-MISPool, setting k 5 gives pooling ratio of approximately 0.09 on EXPWLI. However, for Graclus, Cmp-Gra Cra--Gral and ECPool, the only option is to apply the pooling operator recursively until the desired pooling ratio of 0.1 reached. Unfortunately, this approach is demanding, both terms of computing time and memory usage. While in EXPWLI it was possible to do this for Graclus and Cmp-Graclan we encountered an out-of-memory error after a few epochs when running ECPool on an RTX A6000 with 48GB of VRAM. Thus, the results for ECPool are obtained with recursion that gives pooling ratio approximately 0.2. While this simplifies the training ECPool we argue that, due to its expressiveness, ECPool would have reached approximately 100% accuracy on EXPWL1 if implementing a more aggressive pooling was feasible.
The second remark is that in EXPWLI when using too many MP layers, at least one node ends up containing enough information accurately classify the graphs. This was demonstrated model with 3 GIN layers followed by lalooallma_ppooee in Appendix C. Note that the baseline model Tab. with GIN layers equipped with the more expressive global_sune ssu_poollll_ppppppppppppppossoll achieves a slightly higher accuracy of 19.3...3. In contrast, a model with only GIN layers and global ______a__o________ gives significantly lower accuracy of 66.5.1.8 Therefore, to ensure that the evaluation is meaningful, no more than 2 MP layers should precede the pooling operator. Since ASAPool and SAGPool implement an additional MP operation internally, we used only GIN layer before them, rather than 2 as for the other pooling methods.
which achieved an accuracy of 98.3#006 (more details
Finally, Fig. shows the average accuracy and the average run-time obtained on several bench- mark datasets by GNN equipped with the different pooling methods (the detailed results are in Appendix C.5). These benchmarks are not designed to the expressive power and, thus, GNN equipped with a non-expree -xpeesseess pooling operator could achieve good performance. Specifically, this happens in those datasets where all the necessary information captured by the first two GIN layers that come before pooling or in datasets where only small part of the graph is needed to determine the class. Nevertheless, this second experiment serves two purposes. First, demonstrates the soundness of the GNN architecture used in the first experiment, which achieves results comparable to those of GNNs carefully optimized on the benchmark datasets [16]. Second, and most importantly, shows that the performances the benchmark datasets and EXPWLI are aligned; this underlines the

---

accuracy
60
s/epoch
PanPool SAGPool ASAPool
Top-k
DiffPool
Graclus
k-MIS
DMoN
ECPool
MinCut
Figure 3: Average accuracy (and std.) V.s. average runtime on the benchmark datasets.
relevance of our theoretical result on the expressiveness practical applications. It is worth noting that the benchmark datasets, it was possible to obtain pooling ratio of 0.1 for both Graclus and ECPool. Using pooling ratio of 0.5 gives Graclus and ECPool an advantage over other methods, which makes the comparison not completely fair and shows important limitation of these two methods.
As concluding remark, comment the training time of the dense and sparse pooling methods. popular argument in favor of sparse pooling methods is their computational advantage compared to the dense ones. Our results show that this not the case in modern deep-leaming pipelines. In fact, ECPool, Graclus, PanPool, and even ASAPool are slower than dense pooling methods, while the only sparse method with training times lower than the dense the sparse methods save memory by avoiding computing intermediate dense matrices, this is relevant only for very large graphs that are rarely encountered in most applications.
is M-MIS. Even if it is true that
5 Conclusions
In this work, we studied for the first time the expressive power of pooling operators in GNNs. We identified the sufficient conditions that pooling operator must satisfy fully preserve the expressive power of the original GNN model. Based on our theoretical results, we proposed a principled approach to evaluate the expressive power of existing graph pooling operators by verifying whether they met the conditions for expressiveness.
To empirically test the expressive power of a GNN, we introduced a GNN architecture achieves the same discriminative power of the WL. test. We used such a dataset evaluate the expressiveness of a GNN equipped with different pooling operators and we found that the experimental results were consistent with our theoretical findings. We believe that this new dataset will be valuable tool it allows, with minimal effort, to empirically of any GNN architecture. In our experimental evaluation, we also considered popular benchmark datasets for graph classification and found that the expressive pooling operators achieved higher performance. This confirmed the relevance in practical applications of our principled criterion to select pooling operator based on its expressiveness. Finally, we focused on the computational time of the pooling methods and found that most sparse pooling methods not only perform worse due to their weak expressive power but are often not faster than the more expressive pooling methods.
dataset that allows verifying
the expressive power
We hope that our work will provide novel insights into the relational deep learning community and help to debunk misconceptions about graph pooling. We conclude by pointing to three limitations of our work. Firstly, the conditions of Th. are sufficient but not necessary, meaning that there could be non-expressive pooling operator that preserves all the necessary information. similar consideration holds for EXPWLI: methods failing to achieve 100% accuracy are non-expressive, but the opposite not necessarily true. fact, reaching 100% accuracy on EXPWL1 is necessary condition for expressiveness, though not sufficient. Secondly, condition is not guaranteed to hold for continuous node features, which is theoretical limitation not necessarily relevant practice. Finally, our investigation focused on the scenario where the MP operation before pooling is as powerful as the 1- test. Even layers more powerful than 1- test are rarely used in practice, would be interesting to extend our approach to investigate the effect of pooling in these powerful architectures.

---

Acknowledgements
This research was partially funded by the MUR PNRR project "THE Tuscany Health Ecosystem". We gratefully acknowledge the support of Nvidia Corporation with the donation of the RTX A6000 GPUs used in this work. Finally, we thank Daniele Zambon, Caterina Graziani, and Antonio Longa for the useful discussions.
References
[1] R. Abboud, i. Í. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artifical Intelligence (IJCAI), 2021. 2021.
[2] L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth anmual ACM symposium on Theory of Computing, pages 684-697, 2016.
[3] D. Bacciu and L. Di Sotto. A non non-negative factorization approach to node pooling in graph convolutional neural networks. In AI* IA Advancesse in Artificial Intelligence: XVIIlth International Conference of the Italian Association for Artificial Intelligence, Rende, Italy, November 19-22, 2019, Proceedings 18, pages 294-306. Springer, 2019.
[4] D. Bacciu, A. Conte, and F. Landolfi. Graph pooling with maximum- weight k-independent sets. In Thirty-Seventie AAAI Conference on Artificial Intelligence, 2023.
[5] J. Baek, M. Kang, and S. Hwang. Accurate learning of graph representations with graph mul- tiset pooling. Proceedings of the 9th International Conference on Learning Representations, 2021.
[6] T. Barnard and D. Simon. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and experience, 6(2):101-117, 1994.
[7] B. Bevilacqua, F. Frasca, D. Lim, B. Srinivasan, C. Cai, G. Balamurugan, M. M. Bronstein, and Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
[8] M. Bianchi, D. Grattarola, and C. Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference machine learning, pages 874-883. PMLR, 2020.
[9] M. Bianchi, D. Grattarola, L. Livi, and Alippi. Hierarchical representation learning in graph neural networks with node decimation pooling. IEEE Transactions on Neural Networks and Learning Systems, 33(5):2195-22077 2020.
[10] F. M. Bianchi, C. Gallicchio, and A. Micheli. Pyramidal reservoir graph neural network. volume 470, pages 389-404. Elsevier, 2022.
[11] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 2.602 2013.
[12] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[13] I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 1941171194411977, 2007.
[14] Dichl. Edge contraction pooling for graph neural networks. arXiv preprint arXiv:1905. 2019.
[15] V. Dwivedi, C. Joshi, Laurent, Bengio, and X. Bresson. Benchmarking graph neural networks. 2020.
10

---

[16] F. Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020.
[17] M. Fey and J. E. Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[18] H. Gao and S. Ji. Graph u-nets. In international conference on machine learning, pages 2083-2092. PMLR, 2019.
[19] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry, In International conference machine learning, pages 1263-1272 PMLR, 2017.
[20] D. Grattarola, D. Zambon, F. M. Bianchi, and C. Alippi. Understanding pooling in graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[21] M. Guerra, I. Spinelli, S. Scardapane, and F, M. Bianchi. Explainability in subgraphs-cnhance graph neural networks. arXiv preprint arXiv:2209.07911 2022.
[22] A. H. Khasahmadi, K. Hassani, Moradi, L.. Lee, and Q. Morris. Memory-based graph networks. In International Conference on Learning Representations, 2020.
[23] B. Knyazev, G. W. Taylor, and M. Amer. Understanding attention and generalization in graph neural networks. Advances in neural information processing systems, 32, 2019.
[24] Lee, I. Lee, and Kang. Self-attention graph pooling. In International conference on machine learning, pages 3734-3743. PMLR, 2019.
[25] D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33:1 33:19620-19631, 2020.
[26] Z. Ma, J. Xuan, Y. G. Wang, M. Li, and P. Liò. Path integral based convolution and pooling for graph neural networks. Advances in Neural Information Processing Systems, 33:16421-11633, 2020.
[27] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[28] D. Mesquita, A. Souza, and S. Kaski. Rethinking pooling in graph neural networks. Advances in Neural Information Processing Systems, 33:2220-2233 2020.
[29] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI conference artificial intelligence, volume 33, pages 4602-4609, 2019.
[30] C. Morris, N. M. Kriege, Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.0866 0.6666, 2020.
[31] E. Ranjan, S. Sanyal, and P. Talukdar. Asap: Adaptive structure aware pooling for learning hier- archical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 34, pages 5470-5477, 2020.
[32] R. Sato. A survey on the expressive power of graph neural networks. arXiv preprint Ttiv:2003.040773 2020.
[33] R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
[34] N. Shervashidze, Schweitzer, E. Van Leeuwen, K. Mehlhorn, and M. Borgwardt. Weisfeiler-lchmarl graph kemeels. Journal of Machine Learning Research, 12(9), 2011.
11

---

[35] S. A. Tailor. F. Opolka, P. Lio, and N. D. Lane. Do we need anisotropic graph neural networks? In International Conference on Learning Representations, 2021.
[36] A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller. Graph clustering with graph neural networks. J. Mach. Learn. Res., 24:127:1-127:21, 2023.
[37] B. Weisfeiler and A. Leman. The reduction of graph canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
[38] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[39] Z. Ying, J. You, Morris, X. Ren, W. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[40] H. Yuan and Ji. Structpool: Structured graph pooling via conditional random fields. In Proceedings of the 8th International Conference on Learning Representattons, 2020.
[41] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
[42] D. Zambon, C. Alippi, and L. Livi. Graph random neural features for distance- preseeving graph representations, In International Conference on Machine Learning, pages 10968-10977. PMLR, 2020.
12

---

Appendices
A Proof of Theorem 1
Proof. Let S RNK and T M be the matrices representing the cluster assignments generated by SEL(GF) and SEL(G2) respectively. When condition 2 holds, we have that the entries of matrices S and T satisfy Σ Sij = i, = N. and ΣØ= tig X, Vi M.
condition 3 holds, then the j-th row of Xp is Xr; = E X 8ij- The same holds for the M j-th row of Yp, which is YP; E== y le.. Suppose that there exists rows' permutation T: {1, [I....,K] K} (I,...,45 such that Xr, = yPac) vi ==....... I,..., M, that is:
N
Sij Σ yf (im()) Vj = -i......, K
1=1
which implies
K
N
M
ΣΣ
Σ
(n( B
81j
8ij
i=
i=1
1=1
j=l
N
M
N
M
3
X +
1=1
1=1
1=1
which contradicts condition 1.
Note that there [V2] = M.. Indeed, since the proof does not depend on the number of nodes in the original graphs, N can either be equal to M not. Additionally, number of nodes, i.e., Vipl = 122p K. The case where |Vp11 * [V2pl is trivial since two graphs with different numbers of nodes are inherently not WI. equivalent.
restrictions the cardinality of the original sets of nodes, [1 N and
only focused pooled graphs with the same
B Examples from the EXPWL1 dataset
In Figure 4 we report four graph pairs from the EXPWLI dataset. Each pair contains graphs with a different SAT outcome, which are WL-1 distinguishable. In the Figure, used different color map for each pair but the node features always assume a binary value in {0, 1} in each graph.
C Experimental details
C.1 Baseline models
To identify a GNN architecture that achieves approximately 100% accuracy on EXPWL1, we tried configurations with a different number of GIN layers followed by allbbalmmx__pppe or laobaalssu_pool_ For the sake of comparison, we also considered a GNN with GCN layers, which are not expressive. The results are shown in Table 2.
As expected, the architectures with GIN layers outperform those with GCN layers, especially when the layers are two. This is due to the fact that GCN implements mean pooling as an aggregator, which a well-defined multiset function due its permutation invariance, but lacks injectiveness, leading to loss of expressiveness. Similarly, the GNNs with _lobal_sum_p___ with global_max _pool, since the former more expressive than the latter. An architecture with GIN layers followed by ctlobal_sum_ppt making it the ideal baseline for our experimental evaluation. Perhaps more importantly, there is significant difference in the performance of 2-layers GNN followed by global pooling layer that is more or less expressive. For this reason, the node embeddings generated by GIN layers are good candidate to test the expressiveness of the pooling operators considered in analysis.
perform better than those
achieves approximately 100% accuracy on EXPWL1,
13

---

Class
Class
Class
Cloos 1
Cass 0
Clss 1
C
Chess 1
Figure 4: Four pairs of graphs from the EXPWLI dataset. Each pair consists of two graphs with different classes that are 1-WL distinguishable.
MP layers
Global Pool
Test Acc
2 GIN
Alobal_max_poo
6..5
2 GIN
global_sum_poo
92.1:1.0
GCN
global_max_po
62.3+2.4
GCN
global_sum_ppol 76.7:2.4
3 GIN
global_max_pov 98.310.6
3 GIN
global_sum_pool 99.3:0.3
GCN
global_max_pool 97.410.5
GCN
global_sum_pon
98.720.0
Table 2: Performance of baseline architectures EXPWL1.
C.2 Hyperparameters of the GNN architectures
The GNN architecture used in all experiments consists of: [2 GIN layers] [1 pooling layer with pooling ratio 0.1] [I GIN layer] [glloaa_sum__pa
- [dense readout]. Each GIN layer is configured with an MLP with 2 hidden layers of 64 units and ELU activation functions. The readout 3-layer MLP with units [64, 64, 32]. ELU activations, and dropout 0.5. The GNN is trained with Adam optimizer with an initial learning rate of le-4 using batches with size 32. For SAGPool or ASAPool we used only one GIN layer before pooling. For PanPool we used 2 PanConv layers with filter size instead of the first GIN layers. The auxiliary losses in DiffPool, MinCutPool, and DMoN are added to the cross-entropy loss with weights [0. 1,01, [0.5, 1.0]. [0.3, 0.3, 0.3], respectively. For K-MIS we used k = 5 and we aggregated the features with the sum. For Graclus, we aggregated the node features with the sum.
C.3 EXPWL1 with different pooling ratios
In Table we report the classification results obtained with different pooling ratios. Since in K-MIS we cannot specify the pooling ratio directly, we report the results obtained for k = 3, that gives approximately a pooling ratio of 0.19. 0.09, and 0.07 respectively. As discussed in the experimental section, Graclus, Cmp-Craprr Graclus and ECPool roughly reduce the graph size by half. Therefore, obtain the desired pooling ratio we apply them recursively. This creates a conspicuous computational overhead, especially in the case of ECPool which triggers an out-of-memory error for lower pooling ratios. Importantly, the results not change significantly for expressive pooling methods, while we notice a drastic improvement in the performance of the non-expressive ones for higher pooling ratios. Such sensitivity to different pooling ratios further highlights the practical difference between expressive and non-expressive operators.
14

---

Pooling
Pool Ratio 0.05
Pool Ratio 0.1
Pool Ratio 0.2
DiflPool
95.2+2.1
97.0+2.4
97.4+2.2
DMoN
98.5+1.1
99.0+0.7
18.1
MinCut
98.3
98.8+0.4
98.4+0.6
ECPool
0OM
0OM
100.0=0.0
Graclus
100.043.0
99.9+0.11
99.940.1
k-MIS
99.8+0.2
99.9+0.1
100.0#00
Top-k
69.7+7.1
67.9=13.9
89.4
PanPool
61.3+5.5
63.217.7
15.4
ASAPool
84.3
23.5
87.317.2
SAGPool
61.6#10.6
79.5+9.6
12.4+11.1
Rand-dense
91.3+1.
91.711.3
91.610.8
Cmp-Graclus
91.7+1.1 59.6+3.3
91.911.2
92.1+1.4
Rand-sparse
62.8+1.8
67.1+2.3
Table 3: Classification results on EXPWL1 using different pooling ratios.
C.4 Statistics of the datasets
Table 4 reports the information about the datasets used in the experimental evaluation. Since the COLLAB and REDDIT-BINARY datasets lack vertex features, assigned constant feature value of to all vertices.
Dataset
#Samples
#Classes
Avg. #vertices
Avg. fedges
Vertex attr.
Vertex labels
EXPWL1
3,000
76.96
186.46
yes
NCII
4,110
29.87
64.60
yes
Proteins
1,113
39.06
72.82
1
yes
COLORS-3
10,500
61.31
4
110
Mutagenicity
4,337
30.32
61.54
yes
COLLAB
5,000
74.49
4,914.43
n1
REDDIT-B
2,000
429.63
995.51
n0
B-hard
1,800
148.32
572.32
yes
MUTAG
188
17.93
19.79
yes
PTC
344
14.29
14,69
yes
IMDB-B
1,000
19.77
96.53
no
IMDE-MULTI
1,500
13.00
65.94
no
ENZYMES
600
32.63
62.14
18
yes
REDDIT-SK
4,999
508.52
594.87
no
Table 4: Details of the graph classification datasets.
C,5 Detailed performance on the benchmark datasets
DiffPool DMoN MinCut ECPool Graclus
k-MIS
Top-k
PanPool ASAPool SAGPool
0.96s 0.88s
1.02s
18.85s
6.44s
0.75s
0.87s
8.89s
1.29s
0.76s
71.4+3.7
72.3+3.4
72.8=3.7
72.4=3.s
71.6+3.8
72.2+3.3
145.2
61.6+5.2
63.9 62.644..9
Table 5: Average run-time in seconds per epoch (first row) and average classification accuracy (second row) achieved by the different pooling methods on the benchmark datasets.
The test accuracy of the GNNs configured with the different pooling operators the graph classifica- tion benchmarks is reported Table 6, while Table reports the run-timg time each model expressed in seconds per epoch. The overall average accuracy and average run run-time computed actoss all datasets are presented in Table For each dataset, we use the same GNN configured as described in C.2, interested in validating the architecture used to classify EXPWL1. Clearly, by using less aggressive pooling, by fine-tuning the GNN models, and by increasing their capacity it is possible to improve the results several datasets. Such results reported in the original papers introducing the different pooling operators.
15

---

Pooling
NCT1
PROTEINS
COLORS-3
Mutagenity
COLLAB
REDDIT-B
B-hard
DiffPool
77.8+3.9
72.8+3.3
87.621.
80.0+1.9
76.6+2.5
89.942.8
70.2
DMoN
78.5+14
73.1
88.4=14
81.3+0..
80.9
91.3+1.
71.1=1.0
MinCut
80.1+26
76.043.6
88.7=1.6
81.2+1.9
79.241.5
91.9+18
71.2+1.1
ECPool
79.8+3.3
69.5
81.423.3
82.0=1.6
80.911.4
90.7+1.7
74.521.6
Graclus
81.2+33.4
73.0=5.9
77.6=1.2
81.9+1.
80.4+1.5
92.9+1.7
72.3+1.3
k-MIS
77.6133.0
75.9:2.9
82.9=17
82.611.
73.71:1.4
90.6114
71.710.9
Top-
72.6+33.1
73.2+2.7
57.4+2.5
74.4+4.7
77.9+2.1
87.443.5
68.1
PanPool
66.1+22.
75.246.2
40.7411.5
67.2+20
78.241.5
83,6+19
44.2+8.0
ASAPool
73. 73.1:22.5
75.513.2
43.0=4.7
76.512.8
78.411.8
88.015.6
67.5
SAGPool
79.1+33.0
75.2+2.7
43.1+11.1
77.9+2.8
78.1+1.8
84.5444
54.0=6.8
Rand-dense
78.242.0
75.3213
83.320.9
81.4218
69.3
89.322.1
71.0=22
Cmp-Graclus
77.8118
73.614.7
84.720.9
80.7
OOM
OOM
OOM
Rand-sparse
69. 143.3
74.644.2
35.5a11
69.8+10
68.8+1.8
84.5+19
50.1
Pooling
MUTAG
PTC_MR
IMDB-B
IMDB-MULTI
ENZYMES
REDDIT-SK
DiffPool
86.8+9.7
54.7=6.1
71.3+a.1
+3.4
62.3+7.3
1..7
DMoN
86.3+7.1
55.5=7.3
71.943.3
47.0
61.045.0
56.6+2.3
MinCut
83.1
57.9=7.7
71.9+5.7
46.624.0
62.3+1.8
56.2+2.8
ECPool
90.0+7.2
54.7-8.4
71.3+33.4
49.2+2.9
59.6+3.7
53.6+222
Graclus
85.2+8.0
55.2-6.4
72.3+3.8
46.2+4.4
61.0+6.6
52.3+1.4
k-MIS
85.7=6.2
59.7=6.7
73.1
16.8+4.6
63.5+7.1
56.4+2.3
Top-k
78.4111.8
58.2-8.9
70.923.3
44.8+2.9
45.5
50.4:3.7
PanPool
83.111332
53.5=7.7
73.913.5
48.313.7
40.515.0
46.512.4
ASAPool
74.216.8
50.5112.1
71.4
46.114.2
44.8.1..6
48.8 18.8111.6
SAGPoo!
73.7+6.6
58.8-8.0
71.044.00
44.0+3.4
41.643.2
49.9+2.9
Rand-dense
88.924.3
56.1-9.7
70.5#3.4
45.2+6.6
62.1+5.0
54.5+2.1
Cmp-Graclus
83.219.1
55.9-4.6
OOM
OOM
63.5+5.0
OOM
Rand-sparse
68.9117.3
56.4_5.9
71.623.6
45.8
62.115.0
50.622.4
Table Graph classification test accuracy on benchmark datasets.
Pooling
NC11 PROTEINS
COLORS-3
Mutagenity
COLLAB REDDIT-B
B-hard
DiffPool
0.83s
0.23s
1.67s
0.90s
1.68s
1.74s
0.29s
DMoN
1.01s
0.28s
1.94s
1.06s
1.83s
1.04s
0.33s
MinCut
0.95s
0.28s
1.82s
1.10s
1.82s
1.78s
0.35s
ECPool
4.39s
1.97s
10.30s
4.22s
44.11s
3.17s
6.90s
Graclus
0.95s
0.27s
2.47s
0.98s
3.01s
0.75s
0.31s
k-MISPool
0.88s
0.25s
2.48s
0.95s
1.38s
0.48s
0.43s
Top-k
1.04s
0,29s
2.78s
1,04s
2.79s
0.47s
0.30s
PanPool
2.81s
0.81s
7.16s
5,48s
7.67s
46.15s
6.27s
ASAPool
1.83s
0.52s
4.48s
1.80s
3.97s
0.79s
0.52s
SAGPool
1.09s
0.30s
2.52s
1.07s
2,81s
0.43s
0,28s
Rende
0.54s
0.145
1.448
0.558
0.888
1.448
0.268
Cmp-Graclus
7.94s
3.27s
34.05s
1.94s
Rand-sparse
0.64s
0.18s
1.72s
0.68s
1.00s
0.47s
0.31s
Pooling
MUTAG
PTC MR
IMDB-B IMDE-MULTI ENZYMES REDDIT-SK
DiffPool
0.04s
0.07s
0.14s
0.28s
0.12s
4.52s
DMoN
0.05s
0.09s
0.17s
0.37s
0.15s
3.21s
MinCut
0.04s
0.08s
0.16s
0.35s
0.14s
4.45s
ECPool
0.08s
0.12s
1.66s
1.01s
0.54s
37.
Graclus
0.09s
0.14s
0.24s
0.33s
0.14s
74.02s
K-MIS
0.06s
0.10s
0.28s
0,21s
0.12s
2.02s
Top-k
0.04s
0.08s
0.24s
0.32s
0.13s
1.75s
PanPool
0.26s
0.49s
1.30s
1.92s
0.98s
34.3s
ASAPool
0.14s
0.10s
0.43s
0.40s
0.16s
1,89s
SAGPool
0.04s
0.05s
0.23s
0,27s
0.08s
1.09s
Rand-dense
0.04s
0.06s
0.13s
0.19s
0.12s
3,48s
Cmp-Graclus
0.17s
0.47s
1.38s
Rand-sparse
0.04s
0.08s
0.15s
0.23
0.14s
1.67s
Table 7: Graph classification test run-time in s/epoch.
16


Reviews:
[{"review_id": "JMwnim8k5a", "reviewer": "Reviewer_utJZ", "summary": "Studies on the expressive power of Graph Neural Networks (GNNs) have garnered extensive attention. However, these studies have been limited to flat GNNs. Some hierarchical pooling methods, such as diff-pool, have been proposed. Evaluating the ability of pooling operations directly is challenging, so the performance of downstream tasks is often used as a measure. However, this approach is overly empirical and susceptible to other factors.\n\nIn this paper, the authors propose to use the ability to retain graph information to measure the power of pooling operations. Specifically, this paper first provides sufﬁcient conditions for a pooling operator to fully preserve the expressive power of the MP layers before it. Then, it reviews, classifies existing pooling operators. \n", "questions": "Could you please clarify the relationship between preserving all information after pooling, as defined in this paper, and the ability to distinguish graphs, which is the common definition of expressiveness? In this paper, the diff-pool aims to retain all information. However, from my perspective, the clustering process might lead to a loss of the graph's inherent structural information, which aligns with the description provided in line 244  (arguments against the evaluation approach in Paper [27]).", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper first studied on the expressive power of graph pooling in graph neural networks.\n\n2. This paper categorizes the existing pooling methods based on whether they preserve the expressive ability of the Message Passing (MP) layer.\n", "weaknesses": "1. Given that simple global sum pooling can attain the same expressive capability as 1-WL (e.g., GIN), the rationale behind employing a complex pooling method that achieves no gain in expressive ability might be questioned.\n\n\n2. The research lacks adequate experimentation. Ultimately, the investigation into enhancing or maintaining the expressive ability of Graph Neural Networks (GNNs) is driven by their impact on downstream tasks. However, the paper's classification performance is only evaluated on an extremely small dataset, which fails to provide sufficient convincing evidence.\n\n3. The presentation requires improvement. For instance, reporting averages on different types of datasets in graph classification experiments, as shown in Figure 3, seems unusual and could be better structured. \n\n4. There exists a disparity between Condition 1 of Theorem 1 and the corresponding explanation in line 137, i.e., $\\mathcal{X}_1^L \\neq \\mathcal{X}_2^L $. The summation of the sets is not equal, is not equivalent to the formula in line 137.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. There are important misunderstandings that, hopefully, are clarified in the following.\n\n> 1. The rationale of hierarchical pooling vs. simpler global pooling.\n\nThe rationale for using hierarchical pooling rather than global pooling is not to improve the expressive power, but to generate local summaries of the nodes, to gradually distill global information, and, above all, to enable further MP operations. Applying MP on a coarsened graph has a series of benefits, such as facilitating the exchange of information between distant parts of the graph.\n\nArguing for the effectiveness of hierarchical pooling is not the focus of our work since it is extensively discussed and demonstrated in the original papers proposing the different pooling methods that we analyze.\n\n> 2. The classification performance is only evaluated on an extremely small dataset, which fails to provide sufficient convincing evidence.\n\nWith due respect, we find this critique non-factual and incorrect:\n\n- The difference in the results obtained on EXPWL1 is statistically significant, so **there is** sufficient and convincing evidence to reject the null hypothesis that all pooling methods perform equally (the $p$-value is less than 0.001 for several differences of population means).\n- Is not true that we evaluate the performance **only on one dataset**. In fact, we consider 7 other datasets (plus 4 added in this rebuttal) that contain up to 10,000 graphs.\n- Since the size of EXPWL1 is aligned with common benchmark datasets for graph classifications, calling it **extremely small** seems inappropriate. Most importantly, being a synthetic dataset the size of EXPWL1 can be easily increased but it seemed unnecessary as, by doing that, we did not observe significant changes in the results.\n\n> 3. The presentation requires improvement. For instance, reporting averages on different types of datasets in graph classification experiments, as shown in Figure 3, seems unusual and could be better structured.\n\nPlease, note that the details of each experiment are in the supplementary material.  \n\nSince we performed **a lot** of experiments, we needed a way to summarize the results in a synthetic yet meaningful way. The purpose of Fig. 3 is to give an overview of the overall performances. To improve the presentation, we added the error bars in Fig. 3 (see attached PDF). We are happy to hear suggestions to further improve the presentation of the results.\n\n> 4. There exists a disparity between Condition 1 of Theorem 1 and the corresponding explanation in line 137, i.e., $X_1^L \\neq X_2^L$. The summation of the sets is not equivalent to the formula in line 137.\n\nWhen using GIN layers, both Condition 1 of Theorem 1 and $X_1^L \\neq X_2^L$ are satisfied.  We have made this clarification in the paper.\n\n> Could you please clarify the relationship between preserving all information after pooling, as defined in this paper, and the ability to distinguish graphs, which is the common definition of expressiveness? \n\nAn expressive MP layer distinguishes two graphs by generating node embeddings that are distinct. If a pooling layer preserves all information the embeddings remain distinct and, consequently, the graphs remain distinguishable.\n\n> DiffPool keeps all information but the clustering process might lead to a loss of the graph's inherent structural information, which aligns with the description provided in line 244 (arguments against the evaluation approach in Paper [27]).\n\nOne thing is to preserve the information in the node embeddings $\\mathcal{X}^L$, another is to generate a coarsened graph with a structure compatible with the inductive bias of the next MP layer (e.g., nodes with similar features are connected). The latter task is deferred to the CONNECT function that, however, does not contribute to the definition of expressiveness and, thus, is not part of our theorem.\n\nAn approach to estimate the capability of a pooling operator to preserve the structure of the original graph in the coarsened graph has been proposed in the SRC paper [1]. However, as we discuss in the introduction, this performance measure is often not aligned with the actual classification accuracy.\n\n[1] Grattarola, Daniele, et al. \"Understanding pooling in graph neural networks.\" IEEE Transactions on Neural Networks and Learning Systems (2022).\n"}, {"review_id": "snXwDKhkI6", "reviewer": "Reviewer_DheR", "summary": "This paper presents a study on the performance and expressiveness of various pooling operators in Graph Neural Networks (GNNs) in both theoretical and empirical ways. In detail, the authors identify the sufficient conditions that a pooling operator must satisfy to fully preserve the expressive power of the original GNN model. The authors also propose an experimental approach to evaluate the performance of various graph pooling operators and their theoretical results. The empirical results align with the theoretical findings, showing that pooling operators that satisfy the aforementioned conditions achieve the highest average accuracy. Despite aggressive pooling, these operators retain all the necessary information and perform as well as the GNN without a pooling layer. On the other hand, non-expressive pooling operators achieve significantly lower accuracy. The paper also demonstrates that pooling operators based on a normalized random cluster assignment matrix or the complement graph yield lower performance, which challenges the notion that such operators are comparable to regular ones. In summary, this paper makes a valuable contribution to the field of GNNs by investigating the expressive power of pooling operators in GNNs.", "questions": "- I'm wondering why only choosing a pooling ratio of 0.1 in the experiment. Would using larger pooling ratios affect the alignment between theoretical analysis and empirical findings? If using larger pooling ratios (e.g. 0.5), it is possible to compare the pooling operators more fairly in Table 1. Besides, a larger pooling ratio that doesn't reduce the graph size so aggressively can be possibly applied on the EXP dataset as an extension.\n\n- For the claim in section 3.3: \"Notably, this might not affect certain classification tasks, e.g., when the goal is to detect small structures that are already captured by the MP layers before pooling.\", are there deeper investigations to support this when analyzing the empirical results?", "limitations": "The authors have not explicitly discussed the potential negative societal impacts of their work, which is not directly applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality**: The paper is highly original in its focus on the performance and expressiveness of various pooling operators in GNNs. The authors propose a novel experimental approach to evaluate these operators, and they derive sufficient conditions for a pooling operator to fully preserve the expressive power of the message-passing layers before it. This provides a universal and theoretically-grounded criterion for choosing among existing pooling operators or designing new ones. The exploration of unconventional pooling operators also adds to the originality of the work.\n\n**Quality**: The quality of the paper is good in the rigorous theoretical analysis and comprehensive empirical evaluation. The authors align their empirical findings with their theoretical predictions well. \n\n**Clarity**: The paper is organized and well-written. The theoretical analysis is clearly explained, and the presentation of the experimental results is easy to follow.\n\n**Significance**: The findings in this paper contribute to a solid and necessary step in the understanding of pooling operators in GNNs. The theoretical conditions they propose for preserving the expressive power of message-passing layers and the new dataset could guide the design of new pooling operators.", "weaknesses": "- Since the proposed EXPWL1 dataset serves as an important contribution to the paper, the authors could provide more information about the dataset, i.e. at least provide certain example graph pairs.\n\n- The experiments are kind of insufficient. First, the results in Table 1 are conducted under limited conditions with a pool ratio = 0.1 (excluding the pool ratio = 0.5 for Graclus and ECPool due to issues in implementation). It would be more comprehensive to see and discuss how the pooling operators compare to each other under different pool ratios. Second, the results in Table 3 in supplementary material do not contain the ones for Rand-dense, Cmp-Graclus, and Rand-sparse pooling operators. The comparison to these operators is necessary since the authors want to disprove the argument in [1] that such operators are comparable to the regular ones. Currently, the comparison is only done on a synthetic dataset.\n\n\n[1] D. Mesquita, A. Souza, and S. Kaski. Rethinking pooling in graph neural networks. Advances in Neural Information Processing Systems, 33:2220–2231, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback. We believe to have addressed all the reviewer's concerns and requests, as discussed in the following.\n\n> Provide examples of EXPWL1.\n\nWe inserted in the supplementary material figures showing pairs of WL-1 distinguishable graphs from the EXPWL1 dataset. A few examples are in the PDF uploaded as part of the rebuttal.\n\n> Compare the operators using different pool ratios.\n\nWe followed the suggestion of the reviewer and performed additional experiments using pooling ratios of 0.05 and 0.2 (see Table 2 in the PDF attached to the rebuttal).\nFor higher pooling ratios the results do not change significantly for the expressive pooling methods, while we notice a drastic improvement in the performance of the non-expressive ones. These findings are aligned with our theoretical results since the sensitivity to different pooling ratios highlights the practical difference between expressive and non-expressive operators. \n\nPheraps more importantly, after optimizing the code for memory usage, we managed to achieve a pooling ratio of approximately 0.2 with ECPool and 0.1 with every other method, making the comparison direct and fair. \n\n> Larger pooling ratios (e.g., 0.5).\n\nA ratio of 0.5 is not suitable for EXPWL1. As we discuss in the second remark of the experiments (section 4.3), 2 GIN layers are powerful enough to embed into **a single node** enough information to achieve a 92.1 accuracy on EXPWL1. Clearly, with a pooling ratio of 0.5 every method can embed the information in half of the nodes, achieving almost perfect accuracy no matter how such half is chosen. For this reason, a high ratio of 0.5 is not appropriate for comparing the pooling methods on EXPWL1.\n\n> Results for Rand-dense, Cmp-Graclus, and Rand-sparse in Tab. 3.\n\nWe added the requested comparisons. See Table 5 in the PDF attached.\n\n> Consider the EXP dataset as an extension.\n\nThe EXP dataset contains graphs that are not WL-1 distinguishable and is specifically designed for GNN architectures more powerful than the WL-1 test. Those go beyond the theoretical analysis done in this work and they are not designed to work with the hierarchical pooling layers analyzed.\n\n> Support the claim in section 3.3.\n\nTo support our claim we added a reference to PGExplainer[1], which shows tasks where is sufficient to identify a small motif in the graph to correctly determine its class.\nOn these tasks, a sparse method such as Topk can perform well by keeping only the part of the graph containing the motif of interest.\n\n[1] Luo, Dongsheng, et al. \"Parameterized explainer for graph neural network.\" Advances in neural information processing systems 33 (2020): 19620-19631.\n"}, {"review_id": "aSKCSVsxev", "reviewer": "Reviewer_KM5y", "summary": "This paper analyzes the expressive power of pooling operators in Graph Neural Networks (GNNs) and derives three conditions for a pooling operator to fully preserve the expressive power of the Message Passing (MP) layers preceding it. The derived conditions are as follows: \n\na) The pooling operator should extract different features for non-isomorphic graphs that are distinguishable using the Weisfeiler-Lehman (WL) test. \n\nb) All nodes in the original graph must contribute to the creation of supernodes.\n\nc) The features of the supernodes (denoted as X^P) should be a convex combination of the features of the nodes X^L.\n\nThe paper presents controlled experiments along with theoretical support to validate and support their findings.", "questions": "1 - I found the figure 2 slightly difficult to understand. I believe that adding some additional information, if applicable, could be helpful in making it easier to comprehend.\n\n2 - I appreciate that the running times are provided, but I was wondering if it would be possible to derive their computational complexities (pooling operators) and include them in Table 2.\n\n3 - The quality of Figure 3 could potentially be improved.", "limitations": "- ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1 - The paper is well-written and easy to follow. \n2 - The hypothesis is nicely executed in a controlled set of experiments. \n3 - Theoretical analysis has been provided to support the findings. \n4 - Sufficient review of the literature and pooling operators is provided. \n5 - Clear categorization and analysis of the pooling operators are provided.", "weaknesses": "1 - Selected real-world graph classification datasets are chosen. I was wondering why MUTAG, PTC_MR, IMDB-B are IMDB-MULTI left out\n2 - A comparison with pooling operators such as global_add, global_sum and global_max might provide a better overview of the effectiveness of these pooling operators.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and suggestions.\n\n> MUTAG, PTC-MR, IMDB-B, and IMDB-MULTI were left out.\n\nWe performed the experiments on these datasets. In addition, we also performed experiments on ENZYMES and REDDIT-5K (the latter is still running and will be completed in a few days). Table 5 with the updated results is in the PDF attached to the rebuttal.\n\n> Comparison of different global pooling operators. \n\nPlease note that in the experimental section, we were already discussing the results obtained using global-sum-pool rather than global-max-pool.  \nOn top of that, now we added Table 2 (see attached PDF) which shows a detailed comparison between architectures with GIN e GCN layers (which were asked by another reviewer) followed by global-max-pool and global-sum-pool.\n\n> Figure 2 is difficult to understand.\n\nThanks for the suggestion. We simplified the figure and we provided a more detailed description in the caption. The new figure is in the PDF attached.\n\n> Adding computational complexities in Table 2.\n\nWe reviewed several papers to obtain the computational complexities of the pooling methods under consideration. Dense pooling methods typically have a computational complexity of $\\mathcal{O}(k(m + nk))$ where $n$ is the number of nodes, $m$ is the number of edges and $k$ is the number of supernodes. In contrast, sparse pooling methods generally have a complexity $\\mathcal{O}(m+n)$. However, each paper relies on different definitions and calculations to estimate the complexity, making a direct comparison challenging and prone to errors. For example, [1] and [2] report different complexities for MinCut, while [3] and [5]  report different complexities for ECPool. In addition, the complexity of some methods depends on specific software implementations and hardware acceleration. Indeed, the actual computing times do not reflect well the differences in the algorithmic complexity. For these reasons, we found it more meaningful and transparent to report the computing time obtained with the methods implemented in Pytorch Geometric.\n\n[1] Bianchi et al., Spectral clustering with graph neural networks for graph pooling, 2020.\n\n[2] Tsitsulin et al., Graph Clustering with Graph Neural Networks, 2023.\n\n[3] Landolfi, Revisiting Edge Pooling in Graph Neural Networks, 2022.\n\n[4] Dong at al., MeGraph: Graph Representation Learning on Connected Multi-scale Graphs, 2023.\n\n> Improve the quality of Figure 3.\n\nThanks for the suggestion. We included error bars and enlarged the fonts to make Fig. 3 more readable. The updated figure is in the PDF attached.\n\n"}, {"review_id": "ygqplX7NgV", "reviewer": "Reviewer_UT1a", "summary": "The authors present a comprehensive analysis of pooling operations in Graph Neural Networks (GNNs) from both theoretical and practical perspectives. Additionally, they introduce a refined dataset, EXPWL1, specifically designed to facilitate the analysis of the expressiveness of pooling operations. Remarkably, the empirical evaluation aligns with the theoretical discoveries.", "questions": "\n1. In line 128 of Theorem 1, it is unclear what the inequality refers to. Could you please clarify if each element of the vector needs to be different or if it is sufficient for only one of them to be different?\n\n2. Regarding the limitations, I would like to inquire whether the results apply universally to cases where the features of the nodes are continuous. \n\n3. In Figure 3, if my understanding is correct, each bar represents the average accuracy (in blue) and runtime (in gray) across six different datasets. It would be beneficial to include the standard deviation of these averages. Specifically, the accuracy values may exhibit significant variability between datasets.\n\nMINOR POINTS\n\n- There is a typo in Equation (2), with a missing opening curly bracket.", "limitations": "The authors have not explicitly mentioned the limitations of their work, particularly in terms of the cases where their theory does not apply and any potential limitations of the proposed EXPWL1 method. It would be beneficial for the authors to address these aspects in order to provide a comprehensive understanding of the scope and potential constraints of their research.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The content is presented in a clear and organized manner, and the figures are well-drawn and visually appealing.\n2. The theoretical portion of the work is effectively presented and explained.\n3. The experimental section contains a thorough explanation of the setup and a comprehensive evaluation of the results.\n", "weaknesses": "1. The discussion on the limitations of the work is absent.\n2. Figure 3 is missing std bars.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive evaluation of the paper and for the useful suggestions. \n\n> Discuss the limitations and whether the results apply to continuous features.\n\nThanks for the suggestion. In the conclusions, we now discuss the following limitations:\n\n\"*Firstly, the conditions of Th.1 are sufficient but not necessary, meaning that a non-expressive pooling operator could be able to preserve all the necessary information. A similar consideration holds for EXPWL1: methods failing to achieve 100% accuracy are non-expressive, but the opposite is not necessarily true. In fact, reaching 100% accuracy is a necessary condition for expressiveness, though not sufficient. Secondly, condition 1 is not guaranteed to hold for continuous node features, which is a theoretical limitation not necessarily relevant in practice. Finally, our investigation focused on the scenario where the MP operation before pooling is as powerful as the 1-WL test.  Even if layers more powerful than 1-WL test are rarely used in practice, it would be interesting to extend our approach to investigate the effect of pooling in these powerful architectures.*\"\n\n> Clarify line 128 of Theorem 1.\n\nThanks for the suggestion. We clarified that it is sufficient that only one element of the vectors is different. \n\n> Include standard deviations in Figure 3.\n\nThanks for the suggestion. We included error bars and enlarged the fonts to make the figure more readable. The updated figure is in the PDF attached to the rebuttal.\n\n> Typo in Equation 2.\n\nThanks, we corrected the typo. "}, {"review_id": "7L1Oj0vDIw", "reviewer": "Reviewer_QuJp", "summary": "The paper analyzes the expressive power of pooling (not to be confused with readout) in message passing GNNs (MP-GNNs). The paper gives a condition (in Theorem 1) on the construction of the POOL function, under which there is a choice of the MP-GNN which can separate the same graphs that the 1-WL test can separate. Using these conditions, well known pooling methods are classified as expressive and non-expressive. A new dataset of pairs of graphs that can be separated by 1-WL is introduced, on which the theoretical results are demonstrated.", "questions": "I would replace the non-standard notations of multi-sets and multi-sets of multi-sets with standard notations of 1D and 2D arrays, as these are the objects you actually deal with in this paper. For example:\n\nLine 65: the node features should be represented as a vector (ordered sequence) of feature values, which is equivalent to a mapping from the nodes to features, not as a multiset. A multiset does not have the information of which feature belongs to which node.  Same in line 99, and throughout the paper. For example, 3 in line 130 is a 2D array, not a multiset of multisets, since nodes i and j have identities.\n\nTheorem 1 is important and correct, but it cannot directly be called an expressivity theorem.\nThe logic in the paragraph of line 133 is backwards in a sense. In condition 1 of Theorem 1 you ASSUME a condition on the input of pooling that is similar, or at least stronger, than “two feature vectors on which pooling gives two different outputs.’’ It is almost like giving a condition for the injectivity of a function f by saying “the function f(x) gives different values on points such that $f(x)\\neq f(y)$.’’ Injectivity is not a property of specific inputs, it is a property of the function. An appropriate injectivity analysis should say that, under some assumptions on the model of pooling, for ANY two distinct graphs+node features, the pooling of the two gives two distinct graphs+node features. The theorem you stated is a theorem about which inputs can be separated by pooling, not about which pooling method can separate any pair of inputs. \nThe theorem is still meaningful, as it is used later to discuss expressivity in case features are computed in such a way that sum is injective, but it should be described in the correct context.\nIn this context: in Line 135:\n“there are theorems for functions defined on sets that guarantee condition 1 to be met. In particular, the sum over a multiset that is countable is an injective function”\nThere are indeed very specific (using very high dimensional feature spaces) ways to design by hand specific MP mappings that satisfy this, but when training a MP-GNN there is no known (at least to my knowledge) practical way to guarantee this property.\nHence, this paragraph should also be put in the right context. Namely, there is a way to predefine the MP functions such that POOL is injective (when combined with these predefined MP functions). This is different from saying that POOL is injective on a trained network, or a network with generic weights.\nTo make this clear, it would be good to write an appendix that explains in detail the description around line 133, that is currently quite implicit, citing results from [37] and [40] and formulating the results in a mathematical language. The appendix should show that there exists a construction of MP-GNN with pooling which separates points. This is a type of analysis that directly extends the expressivity analysis of [37] to GNNs with pooling.\n\nIn the new dataset, what feature is put on the nodes of the graphs?\n\nTable 1 - can you add for comparison non expressive networks like GCN (without pooling), so we see what the “baseline” is, and how hard it is to separate graphs when you do not use pooling?\n\n\nMinor comments and suggestions:\n\nLine 129 : (suggested terminology) this is called a right stochastic matrix up to the global constant $\\lambda$.\n\nLine 3: this is the multiplication of the feature vector from the left by the right stochastic matrix S.\n\n", "limitations": "The paper should clarify that expressivity does not mean that POOL is injective for some class of MP function, but that there is a specific choice of the parameters of the MP function such that POOL is injective, similarly to the analysis of [37] and [40].", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is mostly clear, and the topic of pooling in GNNs has practical importance. The theoretical analysis is sound (up to some issue with its interpretation that I discuss below). The classification of well known pooling methods as expressive and non-expressive, in view of Theorem 1, is potentially useful for practitioners, especially as the experimental results on the new dataset strongly support this theoretical classification. The approach is a natural extension of expressivity analysis such as in \"How powerful are graph neural networks?\" and “Deep sets.”\n", "weaknesses": "The discussion on the injectivity of pooling should be put in the right context and setting. What is shown around Theorem 1 is that there is a specific way to predefine the MP functions in such a way that the whole network, including POOL, is injective. The construction does not show that POOL is injective for general message passing functions with trainable parameters (for any choice of the parameters). See more details on this point in “Questions” below. Once this is fixed, I can improve my rating.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments and detailed review.\n\n> Put the injectivity of pooling in the right context and setting. The construction does not show that POOL is injective for general message-passing functions with trainable parameters.\n\nWe completely agree that the objective of Theorem 1 is not to establish sufficient conditions for the injectivity of the pooling operator.\nIndeed, our goal is to study the expressive capabilities of pooling layers **within** a GNN architecture. Our focus lies in identifying sufficient conditions under which a set of MP parameters exists, leading to an injective composition of message-passing and pooling layers. \n\nWe have provided further clarification on this matter in Section 3.1.\n\n> Replace the notation of multi-sets and multi-sets of multi-sets with standard notations of 1D and 2D arrays.\n\nWe agree that 1D and 2D arrays are what we deal with.\nHowever, since the GNNs that we consider implement operations that are permutation invariant, node features can be equivalently represented with multisets.\nWe found it advantageous since the multisets notation facilitates both the discussion and the formal derivations.\nWe clarified this in section 2.1 where we introduce the notation.\n\n> Injectivity is a property of the function, not of the input. \n\nWe agree that injectivity is a property of the function, and not of the input. However, we would like to clarify that the function for which we aim to ensure injectivity is not just the POOL function, but is the **composition of MP layers and pooling layers**. We would like to stress that none of the three conditions put constraints on the input of the architecture composed of MP layers and pooling layers. In particular, the input of MP layers and pooling layer can be any graph. Then, the three conditions guarantee that for any two distinct graphs+node features, the composition of MP layers and pooling gives two distinct graphs+node features. \n\n> Put in the right context Theorem 1 and the discussion that follows.\n\nThese comments were very useful to us. Thank you.\n\nWe clarified that Theorem 1 ensures that there exists a specific choice of parameters for the MP layer that, when combined with a pooling operator satisfying the Theorem's conditions, the resulting GNN architecture is injective. In particular, we modified the first paragraph of the discussion about Th.1 as follows.\n\n*Condition 1 is strictly related to the theory of multisets. Indeed, a major breakthrough in designing highly expressive MP layers was achieved by building upon the findings of Deep Sets [40]. \nUnder the assumption that the node features originate from a countable universe, it has been formally proven that there exists a function that, when applied to the node features, makes the sum over a multiset of node features injective [37]. The universal approximation theorem guarantees that this function can be modeled using an MLP. Moreover, if the pooling operator satisfies conditions 2 and 3, it will produce multisets of node features so that $\\mathcal{X}_ {1_P} \\neq \\mathcal{X}_ {2_P}$.  Due to the injectiveness of the coloring function of the WL algorithm, two graphs with different multisets of node features will be classified as non-isomorphic by the WL test and, therefore, $\\mathcal{G}_ {1_P} \\neq_\\text{WL} \\mathcal{G}_ {2_P}$. This implies that the pooling operator effectively coarsens the graphs while retaining all the information necessary to distinguish them.  Therefore, our Theorem ensures that there exists a specific choice of parameters for the MP layer that, when combined with a pooling operator satisfying the Theorem's conditions, the resulting GNN architecture is injective.*\n\nWe also added more details from references [37] and [40] in the appendix.\n\n[37] Xu et al., How powerful are graph neural networks?, 2019 \n\n[40] Zaheer et al., Deep Sets, 2017\n\n> Node features in the new dataset\n\nThe node features assume a binary value in {0,1} in each graph. We clarified it and showed examples of graph pairs from different classes. See Figure 4 in the PDF attached as part of the rebuttal.\n\n> Baseline with GCN layers.\n\nWe performed the experiment requested. The results are in Table 2 in the PDF attached.\n\n> Minor comments and suggestions.\n\nWe implemented them, thanks."}]

Author rebuttal:
We thank the reviewers for recognizing the value of our work and for the useful feedback, which allowed to improve our paper.

Summary of changes:

- We addressed all the reviewers' requests by introducing explanations and several modifications in the text and the figures.
- We added an experiment with different pooling ratios. 
- After a code optimization, we managed to achieve on EXPWL1 a pooling ratio of 0.2 with ECPool and 0.1 with every other method.
- We performed experiments on 6 new datasets: MUTAG, PTC-MR, IMDB-BINARY, IMDB-MULTI, ENZYMES, and REDDIT-MULTI-5K.
- We added results for Rand-Sparse, Rand-Dense, and Cmp-Graclus on every benchmark dataset.
- We added results on EXPWL1 with a GCN baseline.

Meta-review: This paper delves into the expressive capabilities of pooling operations in Graph Neural Networks (GNNs). The authors propose specific conditions for a pooling operator to fully retain the expressive capability of preceding MP layers and classify existing operators based on this criteria. The paper integrates both theoretical and empirical analyses and introduces a new dataset, EXPWL1, to support their claims. While the study holds promise, there are concerns regarding the comprehensiveness of experiments, presentation clarity, and the theoretical context in which the results are framed. The major concern lies on the limited experimentation. The datasets used for evaluating classification performance are reportedly small, raising questions about the robustness of the results. Thus, the authors are strongly encouraged to compare different pooling operators on larger datasets such as OGB and zinc, and also with vanilla sum/mean pooling, to broaden the impact of the work.
Decision: Accept (poster)