Expressive Pooling for Graph Neural Networks
Authors: Veronica Lachi
Alice Moallemy-Oureh
Andreas Roth
Pascal Welke
Venue: Accepted by TMLR ()

Abstract: Considerable efforts have been dedicated to exploring methods that enhance the expressiveness of graph neural networks. Current endeavors primarily focus on modifying the message-passing process to overcome limitations imposed by the Weisfeiler-Leman test, often at the expense of increasing computational cost. In practical applications, message-passing layers are interleaved with pooling layers for graph-level tasks, enabling the learning of increasingly abstract and coarser representations of input graphs. In this work, we formally prove two directions that allow pooling methods to increase the expressive power of a graph neural network while keeping the message-passing method unchanged. We systemically assign eight frequently used pooling operators to our theoretical conditions for increasing expressivity and introduce a novel pooling method XP, short for eXpressive Pooling, as an additional simple method that satisfies our theoretical conditions. Experiments conducted on the Brec dataset confirm that those pooling methods that satisfy our conditions empirically increase the expressivity of graph neural networks.

Published in Transactions on Machine Learning Research (07/2025)
Expressive Pooling for Graph Neural Networks
Veronica Lachi" Pondazione Bruno Kessler
vlachi@fbk.er eu
Alice Moallemy-Oureh" University of Kassel
amoallenyy@uni--kssee...
Andreas Roth" TU Dortmund
andreas www.rrottttooooooooooooooooo
Pascal Welke*
p.welke alaneestrattststrcc..u.
Lancaster University Leipzig and TU Wien
Reviewed on OpenReview:
Abstract
Considerable efforts have been dedicated to exploring methods that enhance the expressive- ness of graph neural networks. Current endeavors primarily focus on modifying the message- passing process overcome limitations imposed by the Weisfeile=-Leman test, often at the expense of increasing computational cost. In practical applications, message-passing layers are interleaved with pooling layers for graph-lovel tasks, enabling the learning of increasingly abstract and coarser representations of input graphs. In this work, we formally prove two directions that allow pooling methods to increase the expressive power of a graph neural network while keeping the message-passsing method unchanged. We systematically assign eight frequently used pooling operators to our theoretical conditions for increasing expres- sivity. Experiments conducted on the Brec dataset confirm that those pooling methods that satisfy our conditions empirically increase the expressivity of graph neural networks.
1 Introduction
With the growing availability of graph data and the success of neural networks, graph neural networks (GNNs) (Scarselli et al., 2008) have emerged as a key research area. Most common among GNNs, message- passing neural networks (MPNNs) update node representations by aggregating information from neighbors, analogous to the 1- Lemss (1-WL) coloring test used for graph isomorphism. This similarity limits MPNNs' expressive power to that of the 1-WL test (Maron ct al., 2019; Morris et al., 2019; Xu et al., 2019). MPNNs like the graph isomorphism network (GIN) (Xu et al., 2019) improve aggregation functions to achieve the same expressivity as 1-WL. This limitation has prompted the design of GNNs that do not follow this message-passing scheme (Zhang et al., 2023). Advancements include k-GNNs (Morris et al., 2019), which use higher-order message passing, and methods like ESAN (Bevilacqua et al., 2022) and GSN (Bouritsas et al., 2023) that encode subgraph structures. Zhang et al. (2023, Table 2) provide an overview including these approaches. These are often referred to as higher-order GNNs.
Jogl et al. (2023) show that MPNNs achieve the same expressivity higher-order GNNs by simulating higher-order GNNs with MPNNs using graph transformations. They prove that many recent higher-order GNN models, including those by Morris et al. (2019; 2020; 2022); Qian et al. (2022), can be simulated by MPNNs on transformed graphs. However, all graph transformations presented by Jogl el al. (2023) increase the input graph size and consequently incur a higher computational cost for the resulting subsequent message-
All authors contributed equally.

---

Published in Transactions on Machine Learning Research (07 (07/2025)
passing phase. Similarly, the computational cost of non-simulated higher-order GNNs increases in practice and in asymptotic runtime analysis, compared to MPNNs.
Pooling operators (Ying et al., 2018; Diehl, 2019; Gao & Ji, 2019; Lee et al., 2019; Ranjan et al., 2020), on the other hand, aim to coarsen graphs by reducing the number of nodes or edges. Here, MPNNs are interleaved with graph transformations which decrease the graph size. By combining sets of nodes into a single supernode, MPNNs can identify relations between coarsened structures and combine the features of distant nodes. These also aim to improve the runtime of learning inference and have achieved practical predictive performance improvements (Bianchi et al., 2020b; Ying et al., 2018; Liu et al., 2023). This line of work has long remained disconnected from expressivity rescarch. Only recently, Bianchi & Lachi (2023) established conditions under which pooling operators retain the expressivity of an MPNN. It remains unclear if and under which conditions adding a pooling operator can increase the expressivity of an MPNN.
To our knowledge, no pooling operator that decrcases graph size has yet been designed to increase expres- sivity. Conversely, we are not aware of any expressivily-nnereaii considering its underlying graph transformation. It seems natural that improving the expressive power of message passing requires increased computational resources and that, hence, the goals of pooling operators and higher-order GNNs are incompatible. In this work, we refute this assumption. We identify two suf- ficient conditions for pooling operators to increase the expressivity of MPNNs. First, expressivity can be improved by utilizing a sufficiently expressive node selection operation that identifies structurally different sets of nodes. Second, we prove that local pooling operators can also construct WL distinguishable coarsened graphs by only considering node features and their connectivity. As negative result, we prove that pool- ing operators that only utilize node features obtained by MPNNs cannot improve expressivity. We survey existing pooling operators that satisfy the positive negative conditions and present multiple illustrative pooling operators. Furthermore, we construct an exemplary, practical pooling operator XP that increases the expressivity of MPNNs and experimentally confirm on synthetic datasets that XP enhances the expres- sivity of MPNNs. Our positive conditions and their practical implementation in XP may serve as guidelines for designing further expressiilly-incresing pooling methods in the future.
GNN that reduces the graph size when
2 Preliminaries
Most of our notation is taken from Bianchi & Lachi (2023). We use {(-B to denote multisets, i.c., unordered collections that allow repeated entries. Let G (V, H) be a graph with V the set of nodes such that n [V], E the set of edges, and H E Raxd a matrix of node features. For a given node v, the v-th row of H is denoted by hr and the set of neighboring nodes is denoted by No.
A messagg-passing graph neural network (MPNN) is a neural network architecture computing a function in the graph domain. MPNNs provide a flexible framework and are end-to-end differentiable, allowing their parameters to be adapted to a given task using gradient descent. Formally:
Definition 2.1 (MPNN). An MPNN is neural network architecture that, at each iteration updates the embeddings of all nodes by aggregating their embeddings and those of their neighbors in the previous iteration. After T20 0 iterations, the node embeddings are aggregated into the graph embedding æg:
(1) (P
1 (11111) (H((t-)) voNo))))
GG = READ (( : VEV (1)
with (0) = hn and TT xe e (d(()) and ag e Rd are the embedding of node e after the t-th layer and the graph embedding, respectively.
MPNNs typically implement ( as permutation invariant aggregation function and UPD() using a multilayer perceptron (MLP). Sum and mean pooling are popular for READ, When a method utilizes additional other operations, we refer to those more generally GNNs.
2

---

Published in Transactions on Machine Learning Research (07 (07/2025)
2.1 Expressivity of GNNs
When studying the expressive power of GNNs, the aim is to understand their ability to distinguish non-isomorphic graphs. MPNNs are known to be limited by the Weisfeiler-Leman isomorphism test (Leman & Weisfeiler, 1968), i.e,, they cannot distinguish graphs that this test cannot distinguish (Xu et al., 2019).
Definition 2.2 (Weisteiler-Leman test). The Weisfeiler-Leman test is iterative node feature (color) refinement algorithm to test whether two graphs are isomorphic. Let E be a set of node colors. At iteration 0, let 40 HASHo(h,)) where HASH is an injective function that maps node features to colors in E. For any iteration t, let
s00 = HASH ((c uEN.B)
C = vEV
The algorithm terminates if the number of colors belween two iteralions does not change, equivalently when there exists a bijection between Cg (t-1) and c
Definition 2.3 ( (WL distinguishable). 91 and 92 are WL distinguishable (91 tWL 92) there exists an (t)
iteration for which (1) S Cg
If two graphs are WL distinguishable, the WL algorithm (correctly) concludes that they are not isomorphic after termination. MPNNs are at most expressive as the WL test in distinguishing between graphs (Xu et al., 2019) in the following sense:
Definition 2.4. Let 4, be permutation invariant functions from the set of graphs to vector domain and G1 G2 G3. G4 be graphs. Then
y is at least as expressive as & if ((G)) + +(); (92).
o and v are equally expressive if (G1) (GG2) = ((9)) * (G2))
p is more expressive than v. if y is at least expressive sb and there exist G1.92 with (G)) (G2) and (GG) = (G2).
Finally, s, 4b are incomparable if there exist 91 Ga. 94 such that (G)) # ((92) with ((G))= (G2)
=(()))+(())))))) and ((Ga) = (GG) with ((Ga) (G4).
For example, the WL test is at least expressive as any MPNN defined in Equation (1) (Xu et al., 2019).
To obtain an MPNN that is expressive the WL Lest, UPD and AGG need to be injective functions on the input domain. A suitable multilayer perceptron and sum aggregation achieve this (Xu et al., 2019).
In our subsequent discussion, we will analyze the application of graph pooling operators after t itcrations of message passing. To simplify notation, we will from now on ignore the number of such iterations. We will formulate our expressivity results for graphs G (V,E, H) where H = x(1), ie., the node features are obtained by running iterations of MPNN. To compare the expressivity of such composite GNNs before and after applying pooling operator, introduce current distinguishabilit::
Definition 2.5 (currently distinguishable). Two graphs G1 (Vi, VV, and G2 = (V2, E, with (hidden) node representations H, and H2 are currently distinguishable (with respect to H, and H2), denoted G +CD G2, if their multisets of node representations Kh,, u ViB + (h2, u V2 are different.
Note that currently distinguishable graphs, by definition, WL distinguishable.
2.2 Pooling in GNNs
Despite the large body of work on the expressive power of GNNs, insights into the interplay between GNNs and pooling operators are missing. In this work, we analyze the capabilitics of pooling operators enhance the expressive power of GNNss We follow Grattarola al. (2022) and write pooling operators as triplet (SEL,RED, CON) of Select-Reddue--onneed functions.
3

---

Published in Transactions on Machine Learning Research (07/202) 2025)
PC)
SEL h+
RED
CON
Jedge
Figure Example a pooling operator that clusters all nodes of identical color and checks if there exit edges between the clusters: creates a supernode for each node color appearing in G. RED assigns new colors to the supernodes, hashing each individual color multiset to new color. CDN checks if there exit edges between nodes of different colors in and sets an edge belween supernodes in POOL(G).
Definition 2.6 (SEL, RED, CDN functions). A pooling operator POOL: G - ========:v ,H)) is function that maps a graph to a new graph with |V] | = (V) POOL can be written as select-reduuce-commeed triplet.
SEL
The select function SEL G e Ra*k clusters the input graph nodes into A 2 so-called supernodes S (s/) where s; is the vector containing the contributions of node all the supernodes and oe indicates the contribution of node on supernode j.
RED The reduce function RED (S, H) + H. aggregates the features of the nodes assigned to the same supernode to produce its features.
CON The connect function CON (G + & generates the edges, by connecting the supernodes S.
See Figure for an example.
While various pooling operators have been proposed (Ying al., 2018; Luzhnica al., 2019; Bianchi al., 2020a;b; Fey et al., 2020; Sanders et al., 2023; Tsitsulin et al., 2023), their impact the expressive power of GNNs with respect to the WL Lest has largely remained unexplored. To the best of our knowledge, prior work has analyzed conditions expressivity beyond that of the underlying MPNN. The recent work by Bianchi & Lachi (2023) introduced a first formal treatment of expressivity in the context pooling, establishing sufficient conditions under which pooling operator preserves the expressive power given GNN. In this paper, we go one step further: we demonstrate that, under appropriate assumptions, pooling can in fact enhance the expressive power of the network, enabling it distinguish graphs that the original MPNN could not.
the SEL, RED, and CON functions that allow pooling to increase
3 Pooling Maintains Expressivity
We start by providing our formal definition of pooling operators that maintain expressivity. Definition 3.1 (Maintaining Expressivity). A pooling operator POOL (SEL, CON) is maintaining expressivity if it maps any pair of currently distinguishable graphs to a pair of currently distinguishable graphs, Le., if 91 #CD G2 = PO) #CD POOL(G2).
When using WL or MPNN iterations, it is important highlight that maintaining expressivity meaningful when WL distinguishable graphs Gi and Ga have different node representations Hi and H2 or colors assigned. Indeed, if an insufficient number of WL MPNN iterations has been performed, the graphs may be WL distinguishable in principle, yet their node representations are equal. In this case, regardless of the power of the pooling operator, the resulting graphs may remain indistinguishable.
Bianchi & Lachi (2023) established three conditions on the SEL and RED functions, which are sufficient to ensure that a GNN incorporating a pooling layer maintains the expressive power of the GNN without pooling, As a first contribution, we generalize these properties. In what follows, we show that the discriminative power of the WL. test after pooling is maintained when injectivity of the reduce step ensured.

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Proposition 3.2. Let G (V,E,H) be a graph. Let j Vp be supernode of pooled graph POOL(G). Let [RED(S, S, H = f( ( (be, sy)) ue VB)
where J is injective on mellissess. Then, POOL ( (RED, SEL, CON) is mainlaining expressivily.
Proof. Let 9i = (Vi, E Hi) and 92 (V2, H2) be two currently distinguishable graphs w.r.t. H1 and H2. Let ()) E ,Hr) and PO) (Vg . H²) be the corresponding pooled graphs. We denote by H4 (he e Vi the multiset of node representations given by H. Analogously, H2, HI, H2. Now assume, for contradiction, that POOL(Gi) and POOL(G2) are not currently distinguishable w.r.t. H. and H That is, we have
veVi Hf (H( : jevl ([(h,)) : vE ; = -H2
As f is injective, it follows that
(h sy) VEVi : jev (1. st) ve j v
(2)
By our initial assumption, we have Hi H2. We make case distinction:
There exists an element h Hi with h é Hz. Then it follows that the equality in Equation (2) cannot hold: For every supernode j E VI', we have (h. {f (h w E Vi but no node j' Vo" with (ha: we weV,y V2]]-- This implics that the equality in Equation (2) does not hold.
(h,-) {
There exists element h that appears k times in Hi and I k times in H2. Then, we have
(b. 2 WE vi j VI" h = hbll = = #1= (hw: sny w EE j Vo b = hb]
which implies that the equality in Equation (2) does not hold.
Both cases result in a contradiction to the claimed equality of multisets HP and H2, hence it follows that POOL(Gi) #cwI. PO) must instead hold.
We note that this proof is not specifically formulated for node representations obtained by WL or MPNNs, and the expressivity is maintained even when the original representations are more discriminative. Based on Xu et al. (2019), injectivity on multisets can be achieved by combining the sum aggregation with an wlement-wise function:
Proposition 3.3. Let G (Gx he N) be countable set of graphs with G. (Vk, Ex, H()) and bounded number of nodes. For any SEL(GE) S(k), there exists a function di Rdd R RR. such that
(SE H())) = Σ (((H(())). ) (S()))
is injective over all multisets ((H(())) (()))) U V.J.
Proof. As the union of countably many sets of bounded size countable, this proof is analogous to (Xu et al., 2019), which proves injectivity on multiscts from a countable space. There exists map- ping Z: ((H(()) (S()))) + that assigns different natural number to each unique node element ((H()) ),, ()).) Then, the function ((HH))).. (S()))) = n ((())) where n is the max- imum number of nodes in a graph, can be seen as a continuous one-hot encoding. Thus, any sum Ever, ((HH())) (S())))) is an injective function on multisets.
We will refer to this choice of RED as M-RED as it maintains expressivity. We can model ó by an MLP for all practical purposes due to the universal approximation theorem (Hornik et al., 1989). From now on, we assume that the RED employed in the pooling operator adheres the previously defined M-RED, ensuring the fulfilmmnt of the maintaining expressivity condition. We note that this result, in Xu et al. (2019),
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
holds in non-umiform sense: the MLP used to approximate o depends the function being learned and may need to grow in size (ie., number of parameters) with the size or complexity of the input graphs in order to preserve injectivity, and hence expressivity. Some of the existing pooling methods utilize the sum aggregation without an MLP as RED. These can still maintain and increase expressivity when an MLP is applied before RED by another operation, e.g,; as the final part preceding MPNN layer. For example, a GIN layer applies an MLP as its last operation. In the next section, we discuss conditions on SEL that lead to pooling operator that not only maintains but increases expressive power.
4 Conditions for Increasing the Expressive Power
Definition 4.1 (Incrcasing Exprcssivity). A pooling operator POOL = (SEL, RED, CON) is increasing expres- sivity if it is maintaining expressivity and if there is a pair of graphs that are WL indistinguishable, which become Wi.ddistinuushhbbl after pooling, i.e., if there exist 91 w 92 with POOL(G:) twz POOL()).
In what follows, we assume that the RED operator is M-RED as in Proposition 3.3. Whenever we can obtain different supernode assignments for two graphs, an injective M-RED will correspondingly construct different aggregated features. Finding such assignments for some pair of WL indistinguishable graphs allows us to construct pooling method that distinguishes those graphs. Combining this insight with Proposition 3.2, we also know that all cases distinguished by WL on the original graphs can remain distinguishable after pooling the graphs. Thus, to achieve a strictly increased expressivity of model utilizing pooling, it is sufficient to use M-RED and to select suitable SEL function that can assign two Wl-indistinguishable graphs to different. supernode assignments. Notably, the SEL operation does not need to be more expressive than WL; mere incomparability sufficos. We formalize this in the following statement.
Theorem 4.2. Let POOL be pooling operator expressed by the functions SEL, M-RED, CON, where SEL is incomparable to or more expressive than the WL lest, then POOL increases the expressive power and is al least as expressive as SEL.
Proof. By Proposition 3.3, POOL maintains the expressivity; thus, in order to prove that POOL in- creases expressivity we need find two graphs G1 =WL G2 such that the corresponding pooled graphs POOL(G1) (VP, Hf)) and POOL(G2) (VL,, E. H²²) are WL distinguishable. By hypothesis, SEL is in- comparable to more expressive than the WL test. By Definition 2.4, in both cases, there exist graphs G1, G2 with G =wr. G2 and (G,) #WI. (E)) By Definition 2.6 of SEL this implies
{[ v ViB je jeVP HMs : u Ve je V.
We can make case distinction:
There exists a supernode j e vf such that:
reVi # ( v V2B Vie V.P
Since 91 F G2, then [V1 = M2l, D2], so Equation (3) implics that there exists an s for which the multiplicitics are different, i.e.,
K (h,,,)) : BEEE =sB| =k k
(Kh, (.) |
VeVEAs = =tl Vie V.P.
(4)
This implies
(()),,))) VEVID j V. (K,,,,.)) 123 je D
which due to injectivity of M-RED (Proposition 3.2 and Proposition 3.3) and the use of SEL that is incompa-
rable or more expressive than WL implies that gi #CD g
The two pooled graphs have different number of supernodes, i.e., | oE Vi : J HI ue V2 : je V BIl
which implies of #CD J.P
As this proof holds for any 91,92 with I1 FWL G2 and SEL(G;) #WL SEL)) POOL also at least expressive SEL.
6

---

Published in Transactions on Machine Learning Research (07/202) 2025)
POOL(C1)
POOL(92)
a.b.c
WL
a.b,c,d.e,f
FWL
d,e.f
SEL: Cluster connected vertices together
Figure 2: Two WL-indistinguushable graphs G1, G2 which can be distinguished after merging all connected components. This combines the two cycles G2 to a two supernode graph, while maps 91 to a single supernode graph, which are WL distinguishable.
Given this insight, we now have the theoretical confirmation that graph pooling can increase the expressivity of GNNs by utilizing powerful node selection operator. Note that Theorem 4.2 identifies lower bound on the expressivity. Setting CDN to return no edges at all, specific choice of SEL implies that the expressivity of POOL = (SEL, M-RED, CON) is bounded by the direct sum of the equivalence relations defined by WT. and by SEL. That is, two graphs that differ in either WL colors the output of SEL, both, be distinguished by WL on the pooled graphs, while otherwise they cannot. Adding nontrivial CON, however, complicates this analysis dramatically, and providing an upper bound is an open question.
As an example of a powerful SEL, consider a function that clusters together nodes that lie on the same cycle as visualized in Figure 2. This SEL funetion incomparable WL, as it cannot distinguish non-isomorphic trees of the same size. Figure shows that two triangles and a cycle of length six become Wi-distinguishable after pooling with such SEL function, although these graphs WL-inndsstinguishable before pooling. Several existing methods utilize SEL functions that are incomparable to WL, such CliquePool (Luzhnica et al., 2019) selecting based on cliques and CurvPool (Sanders et al., 2023) selecting based on graph curvature. It is worth noting that these methods utilize additional time-consuming graph algorithms to select nodes and are not able to take node representations into account. For instance, CliquePool identifies cliques in a given graph using an algorithm by Bron & Kerbosch (1973) which has worst-case runtime (33/33) for n nodes.
4.1 Edge- Basee Pooling Improves Expressivity
So far, we have shown that with an injective RED and powerful SEL, we can enhance expressivity beyond the WL test, without any conditions on the CON function. In the following, we prove how leveraging a suitable CON further improve expressivity when combined with SEL operator that exploits the connectivity.
Definition 4.3 (M-CON). Let. SEL: G S be select function with Sj (z) where sf indicates the contribution of node supernode j. We define the M-CON function connecting two supernodes if and only if they contain nodes that were connected in the original graph follows:
M-CON(G.S) {(m1, S
th + 0, (u.v) EE}.
Given M-CON as in Definition 4.3 and M-RED, as in Proposition 3.3, we can now show that there are some cases that Theorem does not cover where the resulting pooled graphs are distinguishable.
Theorem 4.4. Let POOL = (SEL, M-RED, M-CON) with M-CON as in Definition 4.3 and M-RED, as in Propo- sition 3.3. Then, there exists a SEL function and two graphs G1 =WL G2 such that SEL(G1) SEL(G2) but POOL(G1) #wr. PO)L(Ga).
Proof. Let 9 be composed of two triangles connected by an edge. Let G2, be hexagon with an additional odge between two nodes with distance three. We have 91 =WL Gz. This scenario is visualized in Figure Now, let SEL be constructed such that for all adjacent pairs of nodes u, u V with degree two, we create

---

Published in Transactions on Machine Learning Research (07/202) 2025)
POOL(Ge)
c,d
a.c
WWL
#WL
a,f
d,f
SEL: Cluster connected (OO) together
CON: Add an edge between supernodes if constituents were connected
Figure 3: Two WL-indistinguushable graphs G1, G2 which can be distinguished after pooling as in the proof of Theorem 4.4. Supernodes correspond to connected components of subgraphs induced by individual node colors. Supernodes a, b are connected by an edge if and only if there is an edge v, w in the original graph where v is pooled into a and w is pooled into b. Here, this results in pooled graphs with different numbers of edges, which are WL distinguishable.
supernode j and set sy + 0 and si, + Using the aforementioned construction of SEL, we observe (cf. Figure 3 the right) that SEL(G1) (E2) while POOL(G:) and POOL(G2) have different number of edges. Thus, POOL(G1) #wo. POOL
In the proof, identified two graphs that could not be distinguished using pooling function defined as in Theorem 4.2. However, they can be distinguished when specific CON, that is, M-CON, is applied. Therefore, employing M-CON function makes the pooling mechanism more expressive. The proof emphasizes the signifi- cance of including the node connectivities when clustering to supernodes. While the pooled multisets of node reprosentations may still be equal, the graph's structure can differ. This would allow message- message-passing to distinguish two graphs as we consider each node's neighborhood. Therefore, pooling operators are more pow- erful regarding their separation ability of graphs if the selection is based on the node's representations and the graph's 's topology, ef. Section 4.2. Consequently, pooling methods that consider topological information when forming supernodes are desired. Appendix A.1 shows further examples of SEL functions that increase expressivity when combined with M-RED and M-CON. Forming a supernode from h nodes is similar to k-Wl. as the graph resulting from kL equivalently contains a supernode formed by these nodes. However, as the expressivity depends on CON, we cannot provide a general upper bound based on the WL hierarchy.
4.2 Bode-Based Pooling Cannot Improve Expressivity
In this soction, we show that pooling methods, taking just the node representations or topological information that do not go beyond WL for SEL, camnot increase expressivity when combined with M-RED and M-CON. This implies that some practical pooling operators such DMoN (Tsitsulin et al., 2023) do not increase expressivity. This also applies to methods like DifiPool (Ying et al., 2018), as we show in Section 5.3. We start by defining a generic node-based select operator:
Definition 4.5. bNsde-based Select) For given graph (V.E, H) where H is computed by MPNN, node-based select operator is defined as
NB (E) S rock with S, = ( 9, (h,,) Vj [1,.,....
i... the contribution functions gy: Rd + R take only MPNN-computed node representations as arguments.
In the following proposition, show that not considering the edge as argument in the SEL function, together with using the M-CON function, makes it impossible to increase expressivity.
Proposition 4.6. Let POOL (NB-SEL M-RED, M-CON), with NB-SEL, M-RED, M-CON as defined in Defini- tions 4.3 and 4.5 and Proposition 3.9. Then, POOL does not increase expressivily.
8

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
PO
PO0L(92)
WL
a,c.d.f
b,e
FWL
a,c,d,f
b.e
SEL: Assign to and
M-CON: Add an edge between supernodes if constituents were connected
Figure 4: Two WL-indistinguussabbe graphs G1, G2 which camnot be distinguished after pooling with node based SEL function as in Definition 4.5.
Proof. Let 91 E, G2 EV2, be two non-isomorphic but WL indistinguishable graphs, i.c. 91 FWL G2. Let Y1 Y/2 be the labels after convergence of the WL algorithm on 91 and G2, respec- lively. Further, let POOL(C)) = (Vf H()), POOL(G2) (V/ E H²)) be the pooled graphs. Since the contribution functions 9p: R - IR for the supernodes take only node representations as arguments, for every V1 E V1 and U2 E 1/2 with h. bag we have s s for all supernodes j E Df and k E V... As such the multisets |f (h,, s() w Vi : je VP = =1 (h,, st) ee V2 : jE D are equal. By definition of M-RED we have H. = H.. For every (01, u1) E & there exists a u2 e V2 with h h with corresponding u2 E Nr, and h = has. Due to HP = -H2, there also exists a bijection t/e VP + Vi2" between supernodes such that for every supernode uy = o(ff)) we have h., h For every supernode of Vf and uf Vf of with taj # and suj # 0, let uy (uf') and up <ufu"). For these, we also have 8 # 0 and s # 0 as 9, takes only the equal node representations as arguments. Thus, for every pair of connected supernodes vf" there exists a corresponding pair of connected supernode in V/P"
"ff
Many existing methods, e-g., MinCutPool (Bianchi et al., 2020a), DMoN (Tsitsulin et al., 2023) or Diff- Pool (Ying et al., 2018) be directly expressed using node-based select because they exclusively utilize MPNNs within the SEL operator. When the SEL operator does not use topological information (beyond WL) of the graph but only node representations resulting from message- passing, this is equivalent to performing additional message-passing steps before applying the pooling operator. We provide the formal details on this equivalence in Section 5.3. Figure shows a node-based SEL function that does not increase expressivily.
This example confirms that methods like DiffPool (Ying et al., 2018), MinCutPool (Bianchi al., 2020a), or DMoN (Tsitsulin et al., 2023) are unable to improve the expressivity of GNN. Based on Bianchi & Lachi (2023), these methods can be constructed to maintain expressivity. Contrarily, Bianchi & Lachi (2023) have shown that methods like Top-k pooling (Gao & Ji, 2019) and SAGPool (Tee et al., 2019) do not maintain expressivity in certain cases. As these methods can similarly be expressed as node- pooling, Proposition 4.6 provides the complimentary result that expressivity cannot be improved in any case. Thus, these methods are strictly less expressive than WT.
Our findings in this section show that pooling methods can increase the expressivity of GNNs. We outlined two directions. In Theorem 4.2, showed that whenever SEL assign two nodes with identical WL- colors to different supernodes, this leads to increase in expressivity of the GNN after pooling, This is the case when SEL is more expressive than WL or incomparable to WL. The pooling then incrcases the expressivily as resulting equal graphs are combined with discriminative supernode representations by M- RED. Based on Theorem 4.4, the second option to increase expressivity is to include the connectivity of node representations. This docs not require a complex SEL function as it suffices to combine only connected nodes based on given node representations. Contrarily, when selecting node representations without considering topological information beyond WL, expressivity cannot. be increased, as shown in Proposition 4.6.
9

---

Published in Transactions on Machine Learning Research (07/2025)
5 Systematization of Pooling Operators
This section describes how existing pooling methods align with our theoretical analysis. To further illustrate our theoretical insights, we introduce XP - pooling strategy that contracts a single edge per graph. XP is not intended as state-of-the-art method, but rather as an example showing how even simple operations can satisfy the eepressivity--ncceasiin criteria derived from the theory. It demonstrates that incrcasing expressivity can be achieved with minimal structural intervention and serves as proof of concept among many possible constructions.
5.1 Expressive SEL functions (Theorem 4.2)
We describe several existing methods capable of obtaining different supernode assignments for two WL indistinguishable graphs by utilizing a powerful node select function. This corresponds to Theorem 4.2. These methods utilize M-CON as defined in Definition 4.3.
CliquePool CliquePool (Luzhnica et al., 2019) aggregates nodes into maximal cliques, ensuring that each supernode represents set of fully connected nodes. Using the Bron-Kerbosch algorithm, maximal cliques are detected and prioritized by size. Each node is greedily assigned to the largest unassigned clique, and pooled features are computed via average or max operations. As the WL test cannot identify cliques in a graph, CliquePool increasing expressivity. However, the Bron-Kerbosch algorithm for a graph with n nodes has worst-case runtime of O(37/3).
CurvPool In CurvPool (Sanders et al., 2023), sets of nodes clustered into supernode when these are connected by a high low graph curvature. The considered Balanced Forman curvature (BFC) indicates whether the two adjacent nodes are densely or sparsely connected for cach edge. As the BFC can be different for WL indistinguishable graphs (Topping et al., 2022), CurvPool can increase expressivity. While clustering densely connected sets of nodes is similar to CliquePool, computing the BFC has a significantly reduced complexity of ((E))dnax) where dmax the maximum node degree.
ASAPool ASAPool (Ranjan et al., 2020) first. identifies all potential local clusters within given graph. A self-attention mechanism is employed to learn cluster assignment matrix for each cluster. To do so, new self-attention variant, Master2Token (M2T), is introduced. The clusters are evaluated using an MPNN, and the highest-scoring clusters are selected to create the nodes of the pooled graph. By only allowing supernodes to be formed within local clusters, ASAPool can obtain different supernode assignments for WT. indistinguishable graphs as these can form different clusters. However, not all node representations contribute in the RED operation, resulting in potentially decreasing expressivity, as shown by Bianchi & Lachi (2023).
ASAPool has linear runtime complexity of O(n + +|8)).
5.2 Edge-based Pooling (Theorem 4.4)
Based on Theorem 4.4, expressivity-ineressing pooling operators can also be constructed by selecting edges for which the adjacent nodes are combined into supernodes. While the aforementioned pooling operators based on an expressive SEL may also be categorized as edge-based, we group methods that closely follow the scheme described in Theorem 4.4 here. We introduce a novel pooling operator that closely follows our theory and describe how two existing pooling operators already follow similar ideas without being explicitly designed to increase expressivity.
EXpressive Pooling (XP) By following the constructive proof of Theorem 4.4 in combination with M-CON, from Definition 4.3, obtain the expressivity- espressivity-hnccessingg pooling operator XP. For each edge, calculate edge score Pu,u utilizing an MLP on the representations h ha of adjacent nodes u.u. The two nodes adjacent to the edge with the highest score are combined into single supernode, while all other nodes form their own supernode. This corresponds to a minimal loss of information about the graph structure. Note that in the case of repeated maximal edge scores, their ordering and the corresponding node selection may be non-deterministic, and a graph can be pooled in multiple ways. Also, note that this particular odge selection is not differentiable but rather serves as a proof of concept. The new graph is constructed as given by M-CON in Definition 4.3. Thus, two supernodes are connected if and only if they result. from nodes
10

---

Published in Transactions on Machine Learning Research (07/2025)
connected in the original graph. To assure that expressivity is maintained in all cases, we approximate the expressvily-mainnaiinngg reduce operator M-RED given by Proposition 3.3 using MLP. This process has runtime complexity O (E))
ClusterPool Similarly to XP, ClusterPoll (Snelleman et al., 2024) calculates edge scores based on the adjacent node representations. However, all edges above a tunable threshold are selected. Based on the selected edges, each connected component merged into single supernode and nodes for which none of the adjacent edges is selected form their own supernode. While XP is special case of ClusterPool, ClusterPool may significantly reduce the size of the graph, which can cause information to be lost. The runtime complexity is also Onn+ [8]) (Snelleman et al., 2024).
EdgePool The EdgePool (Diehl, 2019) similarly computes a score for each edge. Ieeaativlly the edge with the highest score is selected, and adjacent nodes are combined into a supernode. Edges for which one of the nodes was already selected are discarded after each iteration. This repeated until all edges are either selected or discarded. As SEL contracts many edges possible, much struct information will be lost. EdgePool is non-deterministic. As with XP and ClusterPool, runtime complexity is Onn (h++)e))) (Diehl, 2019).
5.3 Node-based Pooling Operators
We now discuss several existing approaches for graph pooling that can be expressed by a node-based select operator. Therefore, these methods cannot increase expressivity.
DiffPool DifiPool (Ying et al., 2018) is a differentiable pooling operator that learns soft cluster assign- ment for cach node to a fixed number of supernodes. It utilizes an additional MPNN to map the state X to new node representations X' and then maps each node representation to assignment probabilities sy (x,) for each supernode j. Tt has a theoretical runtime complexity of Onn²). While the supernode assignment considers the graph topology, we now show that it can be equivalently expressed as a node-based pooling operator and that the topological information do not go beyond WL and therefore DiffPool cannot increase expressivity:
Example 5.1 (DiffPool node-based). Given are a graph 9 = (V,E,X) and hidden node representations H f()) obtained by message-passe passeegganig layers v. DifiPool utilizes additional message-passing layers gi and the node-wise softmax operation within the SEL operation to obtain node assignment scores
S = ((,,
based on the graph topology. The RED function obtains the new node representations by multiplying the supernode assignment scores S with H, on which another set of messagg-passsng layers g2 applied, i.c.,
H' S S-SSSgg(000 (2V,E,
These additional message- pasanig operations can be factored out of the pooling operation by redefining the initial da as
(G) = H2) (91 ((2,E, v(G))) 32
Consequently, the supernode assignment scores and updated node representations can then equivalently be obtained without using the graph topology as a node-based pooling by
S = (oftmax(HH), H' = SSH
Top-k The Top-k pooling operator (Gao & Ji, 2019) starts with assigning scores to each node. The k nodes with the highest score, identified as the most informative, are retained, while the rest are discarded. As the node scoring is based solely on node features, Top-k pooling is sode-based select mothod. The runtime complexity of Top-k pooling is Onn + +[)) (Gao Ji, 2019).
SAGPool SAGPool (Lee al., 2019) employs self-attention mechanism with graph convolution effectively discern which nodes should be retained dropped. Unlike Top-k, the self-attention mechanism
11

---

Published in Transactions on Machine Learning Research (07 (025))
is based on graph convolutions which enables SAGPool to consider both node features and graph topology. However, when the graph's topology is considered through message-passing layers, SAGPool can be stated equivalently as a node- based pooling operator similar to DiffPool (Example 5.1). However, SAGPool has an improved runtime complexity of On + [E]) (Lee et al., 2019).
6 Experiments
To validate our theoretical findings and evaluate the expresivitx-iecresing capabilities of various pooling operatons, we compare their empirical expressivity using the BREC framework (Wang & Zhang, 2024). Our reproducible implementation is publicly available 1
6.1 BREC Framework
We evaluate the empirical expressivity of all considered methods using the BREC framework (Wang & Zhang, 2024). The BREC dataset comprises 400 pairs of non-isomorphic, WL-indistinguishable graphs, which allows for an empirical evaluation of various methods in their ability to distinguish those graphs. The graphs are divided into four main categories: Basic, Regular, Extension, and CFI graphs. Basic Graphs include 60 pairs of 10-node graphs, Regular Graphs consist of 140 pairs, including simple and strongly regular graphs, Extension Graphs are made up of 100 pairs inspired by GNN extensions, and CFI Graphs, the most complex category includes 100 pairs based on the graphs are 3- WL distinguishable. The BREC dataset stands out for its range of graph difficulties, different assessments of GNNs, and large scale, making it significant benchmark for studies in GNN expressivily.
method (Cai al., 1992). 270 of these
The framework takes pairs of WL indistinguishable graphs, creates multiple permutations of both graphs and optimizes the parameters of a given GNN using contrastive learning to distinguish these. The framework compules a distance score ween embeddings and counts each pair as distinguished if the score is larger than a predefined threshold. If pair is distinguished, the framework also requires embeddings of additional permutations of the same graph be sufficiently close. Otherwise, the sample is considered to be unreliable, and the total score will not be increased.
6.2 Evaluated Methods
All hierarchical pooling architectures use uniform structure to ensure consistency across different imple- mentations. The initial feature of each node is determined by its degree. We apply a total of twelve MPNN layers, with one pooling layer added after four and after eight MPNN layers. Global sum pooling, followed by a two-layer MLP, is used to produce graph-level embeddings that are optimized to differ between non- isomrppiic graphs. As MPNN layers, we used the GIN layer (Xu et al., 2019) due to its ability to match the expressivity of the WL test. As pooling layers, we evaluate all methods described in Scction 5, which can be divided into node-based operators, edge-based operators, and operators using an expressive SEL function.
6.3 Experimental Results
The maximum scores over ten runs, as proposed by Wang & Zhang (2024) are displayed in Table 1. Addi- tionally, we show the average runtime in seconds for evaluating the BREC framework for single seed. We provide implementation details and more fine-grained results in Appendix A.
The results confirm our theoretical findings. Node-based pooling approaches fail to enhance expressivity, as evidenced by their inability to distinguish any graph structures across all tested scenarios. This aligns with our theoretical predictions, given that these methods primarily operate at the node level without significantly leveraging the graph topology. In contrast, edge-based methods successfully improve expressivity, with XP demonstratinng the highest performance. This can be attribtedd to its minimal structural modifications, which may preserve more relational information. As ClusterPool requires fixed threshold, we observed most edge scores to be either below or above this threshold. We expect results to be more similar when modifying ClusterPool to only the maximal edge scores.
hhtpp://gtthubb.om/aalae bbwee///rreeeioinnngg
12

---

Published in Transactions on Machine Learning Research (07 (025)
Table 1: Number of graph pairs from the BREC dataset correctly distinguished by different pooling operators in combination with GIN messago-passing.. Maximum scores ten runs, proposed by Wang & Zhang (2024). For comparison, we report results for some higher-order GNNs taken from Wang & Zhang (2024).
However, their runtimes were obtained on different hardware and are not directly comparable with our runtimes.
BASIC (60)
REGULAR
EXTENSION
CFI (100)
TOTAL (400)
RUNTIME
POoLING METHODS
(140)
(100)
(s)
GloBal SUM PooLING
0
227
DIFFPoot
0
330
NODE-BASHR PROPOSITION 4.6
ToP-K
0
267
SACPOOL
0
290
EDGEPOOL
0
23
1539
EDGE-BASE BASED THEOREM 4.4
CLUSTERPOOL
12
0
27
2703
XP
1
124
CLiQuEPooL
44
46
32
0
122
2579
EXPRESSIVE SEL
CURVPOOL
4
157
11657
THEOREM 4.2
ASAPOOL
2
13
1290
HIGHER ORDER CNNS (WANG & ZHANG, 2024)
PPGN
60
50
100
23
233
477*
GSN DSS-GNN
60
99
95
0
254
>5381*
58
48
100
15
221
3351*
S-N-LGNN
60
50
100
6
216
2537*
GRAPHORMER
16
12
41
10
79
>> 13747*
Expressive SEL methods increase expressivity, particularly excelling distinguishing rogular graphs due to their ability to detect triangles. ASAPool, despite leveraging a powerful SEL mechanism, does not achieve good results because, as explained Section 5.2, the RED function does not guarantee the preservation of expressivity. Despite the good performance of CliquePool and CurvePool in graph distinction, these methods exhibit the longest runtime. Conversely, XP achieves comparable graph differentiation performance while maintaining a low runtime, on par with node-based methods. This balance between expressivity and computational efficiency makes XP compelling choice for practical scenarios where both expressivity and execution time are critical factors.
For comparison, we also include expressivity results for oigher-order GNNs reported in Wang Zhang (2024), namely PPGN (Maron al., 2019), GSN (Bouritsas et al., 2023), DSS-GNN (Bevilacqua et al., 2022), 6-k-LGNN (Morris al., 2020), and Graphormer (Ying al., 2021). We also report the combined runtime of preprocessing and evaluation reported in Table 11 of Wang & Zhang (2024). Note that the runtimes were obtained on different hardware (indicated by in Table 1) and that GSN and GRAPHORMER runtimes only include subset of the data. We observe that most higher-order methods achieve near-perfect separation on both Basic and Extension graphs, and they consistently outperform the pooling methods on subsets. While the runtimes are not directly comparable, the higher-order GNNs have a much larger theoretical runtime complexity. PPGN, as the fastest higher-order GNN, has a cubic runtime complexity, whereas the edge-based pooling methods have linear runtime complexity.
7 Conclusion
In this work, we identified two sufficient conditions for pooling operators to increase the expressivity of MPNNs while reducing the size of the computational graph. Pooling operators can either utilize sufficiently powerful select operators or the locality of representations by only selecting connected nodes. While, until now, methods that increase the expressivity beyond the limit imposed by WL were based on modifications of messago-passingg typically incurring substantial computational costs this work represents the first attempt increase the expressive power of GNNs by exploiting the pooling mechanism. We also proved that pooling methods based only node representations cannot. increase expressivity.
13

---

Published in Transactions on Machine Learning Research (07 (07/2025)
We propose examples of sxpressivity-inereaasee pooling operators that reduce the size of the pooled graphs. It follows that the computational complexity of MPNN training and inference the resulting graph is bounded by the complexity of the operations on the original graph if the architecture is not changed. The specific methods that we propose as examples are almost all linear time. This implics that the computational complexity of building and training the pooled architecture is bounded by the computational complexity of building and training the original architecture. If one employs more expensive select operators (e.g. identifying triangles), the computational complexity may slightly increase.
Additionally, categorized the most common pooling operators from the literature into three distinct categorics based on their contribution to expressivity, i.c. operators that increase expressivity through an expressive SEL function, edge-based pooling methods leveraging graph connectivity to enhance discrimina- tion and node-based pooling methods, which do not increase expressivity due to their limitation of relying solely on node representations. Our empirical evaluation confirmed our theoretical findings, demonstrating that various pooling operators can increase the expressivity of GNNs by varying degrecs. Our conditions for increasing expressivity and categorizing into the different expressivily-incressing groups offer systematic guideline for developing future pooling strategies.
The main limitation of our work is that the benefits of the identified increase in expressivity need to be confirmed for practical purposes. However, as our theory can be applied to many different pooling operators, we leave open for future work to find the best- pest-performin pooling operator for real-world datasets.
Acknowledgments
PWs work has been partially funded by the Vienna Science and Technology Fund (WWTF) and the City of Vienna [Grant ID: 10.47379/ ICT22059] (StruDL). AMs work has been partially funded by the Ministry of Education and Rescarch Germany (BMBF), under the funding code 01IS20047A, according to the 'Policy for the funding of female junior researchers in Artificial Intelligence'. ARs work is funded by the Federal Ministry of Education and Research of Germany under grant no. 01TS22094F. WEST-AI.
References
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Bal- amurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. In Advances in Neural Information Processing Systems, 2023.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, 2020a.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Hicrarchical represcntation learning in graph neural networks with node decimation pooling. IEEE Transactions on Neural Networks and Learning Systems, (315) 2207, 2020b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeirion, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-668, 2023. doi: 1LL.0//TTAA..2022.3552220
Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9):575 577, 1973. doi:
Jin- Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410 1992. doi:
Frederik Diehl. Edge contraction pooling for graph neural networks. arXiv preprint ar Xiv: 109.00990, 2019.
14

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint Xiv: 1903.990.0000 02428, 2019.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molec- ular graphs. In Graph Representation Learning and Beyond Workshop, 2020, doi: 10.48550/ 10.48550/ar1iv22006 2a00 12179.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In International Conference on Machine Learning, PMLR, 2019.
Daniele Grattarola, Danicle Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks 2(5):359 366, 1989. doi: 1211016/0822-0000(8))00000000 URL https:
//doi.org/10... wwtpo///////////////..///////.// 001111199066008888 (89) 90020-8.
Fabian Jogl, Maximilian Thicssen, and Thomas Gärtner. Expressivity-pprseree GNN simulation. In Advances in Neural Information Processing Systems, 2023.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling, In International Conference on Machine Learning, 2019.
AA Leman and B Weisfeiler. A reduction of a graph to canonical form and an algebra arising during this reduction. Nauchno- Teeitbnoo-Tcnniihhssakaao Informatsiya, 2(9):12- 16, 1968.
Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. In International Joint Con- ference on Artificial Intelligence, pp. 6712-6722, 2023. doi: 10.24963 222993//JCCA22223///77
Enxhell Luzhnica, Ben Day, and Pictro Lio. Clique pooling for graph classification. In Representation Learning Graphs and Manifolds Workshop, 2019. doi: 10.48350/arXiv.. 00.50///arxi..111.0007....
Haggai Maron, Heli Ben-Hamm,, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher- order graph neural networks. In AAAI Conference Artificial Intelligence, 2019. doi: 10. 10.1609/amn v:3i0..33.....m 15300113304622.
Christopher Morris, Gauray Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems, 2020.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-aware cermutation-equuivriann graph networks. In International Conference on Machine Learning, 2022.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. In Advances in Neural Information Processing Systems, 2022.
Fkagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning
hicrarchical graph representations. In AAAI Conference on Artificial Intelligence, 2020.
Cedric Sanders, Andreas Roth, and Thomas Liebig. Curvature-hased pooling within graph neural networks. wet..ivvv.v..1ee.. 2656.16516.
In Mining and Learning with Graphs Workshop, 2023. doi:
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2008.
Thijs Snelleman, Bram M. Renting, Holger H. Hoos, and Jan N. van Rijn. Edge-basod graph component pooling. CoRR, abs/ abs/2409. /20//2199.11., 2024. doi: 10.48550/ ARXIV. 14409.118566 URL https://doi, org/10. 48550/arXiv 2409. 11856.
15

---

Published in Transactions on Machine Learning Research (07 (025)
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bron- stein. Understanding over-squashing and bottlenecks graphs via curvature. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReevee.nnet A.
2022. URL
Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127):1 21, 2023.
Yanbo Wang and Muhan Zhang. An empirical study of realized gan expressiveness. In International Con- ference on Machine Learning, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jemnifer Wortman Vaughan (eds.), Advances in Newral Information Processing Systems 34: Annual Conference on Newral Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pp. 28877-28858 2021. URL https: https://proceedingg c33 -at-aattdddtt----aaaaaataea
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with diffcrentiable pooling, In Advances in Neural Information Processing Systems, 2018.
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey. CoRR, abs/ ARXIV. 2308.08235.
2023. doi: 10.48550/
16

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
2
POOL(C1)
POOL(92)
WLL
#WL
a.b,c,d,e.f
G3
POOL(G3)
POOL(G4)
WW.
a.b.e,f.g.j
#WL
SEL: Cluster vertices on a triangle, retain other vertices
CON: Add an edge between supernodes if constituents were connected
Figure 5: Two pairs of Wi-indisttiguuishbll graphs 91992 which can be distinguishod after clustering all nodes on triangles logether.
A Appendix
This appendix provides additional (training) details and an ablation study on the interplay of the number of message-passing or pooling layers of our XPpooling and GIN.
A.1 Further SEL Examples
Example A.1. Any POOL method retaining disconnected components when repeatedly applied until all edges are contracted is increasing expressivity.
Proof. The ability to maintain expressivity for all graphs follows from Proposition 3.2. In addition, any such POOL method maps two disconnected triangles to two nodes, while the hexagon mapped to single node. This is visualized Figure 2.
It may seem that crrressvvity-nccrasiin pooling operators exclusively leverage connoctivity by clustering (some) connected nodes while keeping different connected components separate supernodes. However, this is not necessary condition to increase expressivity. Figure 5 shows example pooling operator in which all nodes contained in triangles are clustered into a single supernode. In contrast, nodes that are not triangles are retained. Other biconnected components into supernodes, as shown in Figure 6. Necessary for increasing expressivity, at least for our choice of the CON function, seems to be the incorporation of the edge set in some form.
musssivvty-incrraiinn pooling operators can be obtained, e.g., by clustering
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
g
PO0L((1)
POOL(92)
a.b,c,d,e
WL
#wL aab.c.....f................
(gg.bi.j
SEL: Cluster vertices in the same biconnected component
CON: Add edge between supernodes if constituents connected
Figure 6: Two WL-indistinuuishabl graphs G1 that become WL-distinguishable after pooling, where nodes in the same bicomnected component are clustered into the same supernode. A biconnected component is a maximal subgraph where any two nodes lie on a cycle.
A.2 Training Details
Our implementation is based on the BREC framework (Wang & Zhang, 2024) and PyToorc Geometric (Fey & Lenssen, 2019). All experiments were run in parallel, with each instance on a Platinum 8468 CPU and GB RAM, apart from the experiments with ASAPool, as those required 100 GB RAM. All processes combined take 57 hours. We repeated all experiments ten times with different. random seeds. The source code is reproducable and available https///ggthuu.oomaaaiiaao http/brreeppooooo
A.3 Ablation Study
In the following, we evaluate how different numbers of message-passing iterations and pooling steps affect the empirical gains in expressivity. As in Table 1, GLN layers are used for message-passing and the BREC dataset is considered. We apply & GIN layers followed by one pooling step, and repeat this process 1 times. After these steps, another & GIN layers are employed. Thus, the model consists of total of / pooling steps and k (7+ (1+1)* 1) GIN instantiations. Global sum pooling, followed by a two-layer MLP, produces graph-level representations.
Results for XPare presented in Table These results indicate that expressive power mostly improves with more GIN layers and pooling steps. This matches our theory as expressivity can always be maintained. Further, we observe trade-off between the increase in expressivity and stability regarding the number of message-passing and pooling layers. Keeping the number of one of these two layer types fixed and
Table 2: Number of graph pairs in the BREC dataset correctly distinguished by XP combined with GIN layers. The model consists of h GIN layers and one pooling step, repeated times. Mean and standard deviation over three runs are shown. Best result in bold. NAN refers to numerical runtime errors.
& GIN layers between pooling layers
XP
7
10
26 4
61 =
3
=
99
90 +
2
37
98
109 = 6
112
114 + 3
114 6
114
NAN
NAN
3
82
10
113+2
110+4
118
117 2
NAN
NAN
NAN
NAN
4
93+8
112#2
113=3
123 =
NAN
NAN
NAN
NAN
NAN
I pooling layers
5
96+3
114#9
119
NAN
NAN
NAN
NAN
NAN
NAN
6
102
12145
119 9
NAN
NAN
NAN
NAN
NAN
NAN
7
95
11641
NAN
NAN
NAN
NAN
NAN
NAN
NAN
8
96+4
116+7
NAN
NAN
NAN
NAN
NAN
NAN
NAN
9
9
113+4
NAN
NAN
NAN
NAN
NAN
NAN
NAN
18

---

Published in Transactions on Machine Learning Research (07/2025)
increasing the other first comes with notable improvement while adding further layers leads to more less stable results. However, the deeper the network gets, the more frequent numerical errors become. These observations suggest that finding an optimal number of message-passing and pooling layers is key to reliable performance. As the stability of deep models a general issue, we refer to studying the connections between the expressivity of deep models and vanishing or exploding gradients and over-smoothing to future work.
19


Reviews:
[{"review_id": "kzico2fCgR", "reviewer": "Reviewer_agXC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1) studying the expressivity of pooling is relevant and useful in practice. Section 4 contains the interesting results, in particular Theorem  4.4 and Proposition 4.6 about examples of pooling operations that can or cannot improve expressivity.\n\n2) The article's contributions are stated very clearly.\n\n3) The article contains a comparison of their results to some existing pooling methods in Section 5.2 and 5.3\n\nWeaknesses: 1) Results of Section 3 are a direct consequence of the existence of a combine-sum function to be injective on multisets (Xu et Al., 2019). Also, the definition of GNNs of the authors allows for any UPD^{t} function (sometimes called combine function). In Section 3, the authors do not discuss if this UPD function is arbitrarily complicated or restricted to MLPs, for example. \n\n2) The insight of Proposition 4.6 is limited in the following sense: It starts with ``Let G1, G2 be two non-isomorphic but WL indistinguishable graphs''. This represents a (very) small proportion of graphs, in particular for applications: the experiments do not showcase limitations or illustrations on datasets for practical applications (only the BREC dataset is used).\n\n3) The computational complexity of pooling is not discussed, in particular the cost of increasing expressivity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This article studies the impact of pooling on the expressivity of GNNs. Pooling is defined as a collection of generic operations that scales down the input graph's order by selecting and reducing parts of the graphs, and then connecting the obtained information them in a new smaler graph structure. The pooling operation is summarized in a triplet (SEL, RED, CON).\n\nThe authors study when formal expressivity (in the ability to distinguish inputs) is maintained or increased for certain types of pooling.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Restate the beginning of Part 2 as a formal definitions of GNNs.\n\nI suggest the authors to mention that expressivity here is studied non uniformly (in the case where update functions are neural networks), in the sense that the number of weights of these functions has to grow with the size of the input graphs, to maintain expressivity. For example, it is also the case in (Xu et Al., 2019). \n\nCaption of Figure 3: Change the sentence: ``[...] single superedge between supernodes iff any original nodes were connected results in pooled graphs with different numbers of edges [...]'' (meaning is not clear and syntax incorrect)", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DB6UeH2CBg", "reviewer": "Reviewer_XapJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors provide a theoretical framework for pooling layers in GNNs by dividing them into three distinct operations. They derive conditions under which these operations must meet to maintain or increase expressiveness. This framework is highly general and applies to a wide range of commonly used pooling methods in the literature.\n- The authors evaluate various pooling methods on a synthetic dataset and demonstrate that their proposed XP achieves both efficiency and comparable performance. These results offer valuable insights for designing graph neural network architectures.\n- The paper is well-written, with numerous illustrative examples that simplify the theory.\n\nWeaknesses:\n- The authors’ characterization of pooling layers appears to be a special case of higher-order GNNs. Specifically, pooling layers combine nodes into supernodes, apply a reduce operation to generate their features, and then assign edges between the supernodes. This process is quite similar to higher-order GNNs, which also conduct message passing on supernodes. It would be beneficial for the authors to discuss the relationship between their characterization of pooling layers and higher-order GNNs. For instance, it is known that the expressiveness of $k$-GNNs is upper-bounded by $k$-WL. Can we conclude that the expressiveness of pooling layers that selects at most $k$ nodes is also bounded by $k$-WL? If not, where does the expressiveness of pooling layers lie within the WL hierarchy?\n- As mentioned in the previous point, the authors only propose conditions that “increase” the expressivity of GNNs, but they do not provide an analysis of the actual expressiveness of GNNs after incorporating such pooling layers.\n- The proposed XP appears to be a specific case of ClusterPool, and I don’t perceive the need to introduce it as a distinct pooling method. The authors contend that ClusterPool could potentially reduce the graph size and lead to information loss, but this can be mitigated by selecting an appropriate threshold for edge selection. Consequently, I fail to comprehend why the performance of ClusterPool is significantly lower compared to XP in the experiment, considering that XP is a special case of ClusterPool.\n- Furthermore, the proposed XP is non-deterministic, resulting in distinct representations for the same graph. This deviation from the permutation invariant inductive bias of GNNs may have adverse effects on real-world applications. Moreover, since XP is not differentiable, how can it be applied to GNNs for practical tasks? The authors mentioned that they only trained the MLP layers in their experiment. While this is acceptable for evaluating the expressive power of GNNs on a synthetic task, it is impractical to generalize these findings to real-world applications.\n- The authors’ experiments are confined to a small synthetic task, and the performance of the pooling layers is not assessed on real-world tasks. The distinction between non-isomorphic graphs and real-world graph representation learning is vastly different. Therefore, the results obtained on a synthetic dataset cannot provide reliable guidance for designing GNNs for practical applications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the expressive power of pooling layers in graph neural networks. The authors begin by examining the sufficient conditions for pooling layers to preserve expressivity and also propose the conditions under which they can increase expressivity. Then, they conduct an investigation into the expressivity of eight commonly used pooling layers in the literature and introduce a novel pooling method called XP, which aims to increase the expressive power of message passing graph neural networks. Finally, the authors evaluate the performance of XP and several other pooling methods on a synthetic dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to suggest the following changes:\n- The authors should discuss the theoretical upper bound of the expressivity of pooling layers, rather than merely stating that they increase expressivity.\n- The authors should provide justification for proposing XP as a distinct pooling method and explain why it achieves significantly higher performance on the synthetic task.\n- The authors should elucidate how XP can be applied to GNNs in practical settings, considering their non-deterministic and non-differentiable nature.\n- The authors should validate the performance of various pooling layers on real-world tasks.\n\nA few minor typos:\n- There’s an extra “graph” on the second line of the second graph in the Preliminaries section.\n- There’s a missing space at the end of the first paragraph following Definition 2.3, between the word “this” and the citation.\n- On the first line of the proof of Proposition 3.2, the spacing after “w.r.t.” is incorrect. For guidance on producing the correct spacing after periods in LaTeX, refer to this page: https://tex.stackexchange.com/questions/2229/is-a-period-after-an-abbreviation-the-same-as-an-end-of-sentence-period.", "broader_impact_concerns": "The authors study the expressive power of pooling layers in GNNs, offering insights into the design of GNN architectures. I don’t see any ethical concerns of this work that necessitate a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PpOF6ZqSc4", "reviewer": "Reviewer_aN64", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Despite the contributions, there are several crucial concerns: \n\n- Lack of Novelty in Theoretical Contributions\n\nWhile the authors provide a formalization of expressivity-enhancing pooling, the results largely extend known principles from the WL hierarchy and graph transformations. The proposed expressivity conditions seem incremental rather than groundbreaking.\n\n- Overemphasis on Synthetic Benchmarks\n\nThe evaluation is limited to distinguishing WL-indistinguishable graphs using synthetic datasets. The practical benefits of increased expressivity on real-world tasks remain unclear. The paper does not address whether improving expressivity through pooling leads to tangible performance gains in graph classification or regression tasks.\n\n- Limited Practical Impact of XP\n\nWhile XP achieves improvements in expressivity over baseline pooling methods, its real-world usability is uncertain. The proposed approach lacks rigorous complexity analysis, and it remains unclear how well it scales to large graphs or whether it provides benefits beyond synthetic benchmarks. Besides, it is outperformed by other pooling algorithms in some metrics (e.g., REGULAR, CFI, TOTAL), which failed to convince the audience of the effectiveness of this XP. \n\n- Potential Methodological Weaknesses in Experiments\n\nThe paper does not sufficiently discuss hyperparameter tuning or provide a detailed analysis of how results might vary across different GNN architectures beyond GIN. It is unclear whether the findings generalize to more powerful GNNs such as transformer-based graph models.\n\n\n- Unclear Differentiation from Related Work: \n\nThe paper does not sufficiently position itself against prior work in expressive GNN architectures, particularly methods that use subgraph-based approaches to increase expressivity. There is little discussion on whether pooling fundamentally offers advantages over existing higher-order message-passing techniques.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. Theoretical Analysis: The paper presents a well-structured theoretical framework, offering conditions under which pooling operators can improve expressivity. This contributes to the understanding of the interplay between pooling and expressivity in GNNs.\n\n\n2. New Pooling Method (XP): The introduction of XP as a theoretically motivated pooling method is a valuable contribution. XP aligns with the provided theoretical conditions and demonstrates improved expressivity on synthetic benchmarks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The experimental part is very insufficient, and I found little description of the benchmark dataset BREC. How large is this dataset? What is the sota architecture or method in this dataset? What is the significance of achieving certain metrics in this dataset? etc. Besides, I found little implementation details in the appendix. \n\n- Demonstrate Practical Benefits\n\nShow how expressivity improvements translate to better performance in real-world graph learning tasks,  such as OGB and zinc. Otherwise, this research lacks adequate experimentation. \n\n- Compare with Stronger Baselines\n\nEvaluate against higher-order GNNs or subgraph-based models rather than just pooling methods. Besides, why is the vanilla sum/mean pooling not compared? \n\n- Scalability Analysis\n\nProvide complexity analysis and empirical results on large-scale datasets. Besides, what is the impact of some hyperparameters over the model performance, such as pool ratio and GNN layers? \n\n- Clarify Theoretical Novelty\n\n Better differentiate contributions from prior work in graph expressivity and pooling theory. Specifically, [A].\n\n[A] The expressive power of pooling in Graph Neural Networks. NIPS 2023.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)