Geometry-Aware Edge Pooling for Graph Neural Networks
Authors: Katharina Limbeck
Lydia Mezrag
Guy Wolf
Bastian Rieck
Venue: NeurIPS 2025 poster ()
Keywords: graph neural networks
graph pooling
metric space magnitude
geometric deep learning
Primary area: deep_learning
TL;DR: We propose novel graph pooling methods for structure-aware pooling via edge collapses.

Abstract: Graph Neural Networks (GNNs) have shown significant success for graph-based tasks. Motivated by the prevalence of large  datasets in real-world applications, pooling layers are crucial components of GNNs. By reducing the size of input graphs, pooling enables faster training and potentially better generalisation. However, existing pooling operations often optimise for the learning task at the expense of discarding fundamental graph structures, thus reducing interpretability. This leads to unreliable performance across dataset types, downstream tasks and pooling ratios. Addressing these concerns, we propose novel graph pooling layers for structure-aware pooling via edge collapses. Our methods leverage diffusion geometry and iteratively reduce a graph’s size while preserving both its metric structure and its structural diversity. We guide pooling using *magnitude*, an isometry-invariant diversity measure, which permits us to control the fidelity of the pooling process. Further, we use the *spread* of a metric space as a faster and more stable alternative ensuring computational efficiency.  Empirical results demonstrate that our methods (i) achieve top performance compared to alternative pooling layers across a range of diverse graph classification tasks, (ii) preserve key spectral properties of the input graphs, and (iii) retain high accuracy across varying pooling ratios.

Geometry-Aware Edge Pooling for Graph Neural Networks
Katharina Limbeck 1.1
Lydia Mezrag 33
Guy Wolf 3.4
Bastian Rieck
Helmholtz Munich
TTchnical University of Munich
Université de Montréal
MMila Quebec Al Institute
Université de Fribourg
Abstract
Graph Neural Networks (GNNs) have shown significant success for graph-based tasks. Motivated by the prevalence large datasets in real-world applications, pool- ing layers crucial components of GNNs. By reducing the size of input graphs, pooling enables faster training and potentially better generalisation. However, existing pooling operations often optimise for the learning task at the expense of discarding fundamental graph structures, thus reducing interpretability. This leads unreliable performance across dataset types, downstream tasks and pooling ratios. Addressing these concerns, we propose novel graph pooling layers for structure- aware pooling via edge collapses. Our methods leverage diffusion geometry and iteratively reduce a graph's size while preserving both its metric structure and its structural diversity. We guide pooling using magnitude, an isometry-inve -invaraann diversity measure, which permits us to control the fidelity of the pooling process. Further, we use the spread of a metric space as a faster and more stable alternative ensuring computational efficiency. Empirical results demonstrate that our methods (i) achieve top performance compared to alternative pooling layers across a range of diverse graph classification tasks, (ii) preserve key spectral properties of the input graphs, and (iii) retain high accuracy across varying pooling ratios.
Introduction
Graph pooling layers are important components of GNN architectures. They are implemented alongside convolutional layers to reduce the size of graph representations during training. Pooling thus enables GNNs to scale to large and complex real-world graphs while regularising the resulting representation. However, the choice of pooling method strongly influences and task- pakk-erffrrance. In fact, the question of which graph properties to preserve during pooling, just the question on the nature and quality of graph datasets in graph learning [15], remains an ongoing debate [41, 44, 55]. It is thus crucial to design expressive, efficient, and interpretable pooling layers that capable of reliably encoding task-relevant information while reducing the size of input graphs. Most graph pooling literature takes a node-centric view [41]. However, this focus on node- centric rather than edge-centric pooling often leads the loss of important structural information. Common pooling methods either drop nodes or optimise for a node clustering while treating graph connectivities secondary objective. As visualised in Figure I and further explored in our work, this frequently leads to counter-intuitive pooling decisions that fail to retain key geometric structures in graph. Addressing these concerns, topological and geometric descriptors of graphs are uniquely poised to interoperate structural information into graph pooling.
maaestrrammmplliccttion
"These authors contributed equally to this work. "These authors jointly supervised this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

orggall Hagtdgeroo
0
o
Examples of graphs pooled to approximately half their original size compared across pooling layers. Our proposed methods, MagEdgePool and SpreadEdgePool. respect the original graphs' geometry during pooling, Alternative approaches tend to obscure adjacency relationships to varying extents by creating counter-intuitive edges (Graclus, NMF), disconnecting entire portions of the graphs (TopK, SAGPool), or returning dense representations that do not preserve any geometric structure (DiffPool, MinCut).
Figure I:
Throughout this work, we treat graphs as metric spaces and assess their geometry via diffusion distances, which naturally work alongside message passing to effectively encode key graph structures. Motivated by ongoing research on novel geometric invariants, we find that generalised measures of size and diversity are especially promising candidates for guiding graph pooling. In particular, we use the magnitude of metric space [39], which measures a graph's 's structural diversity, to control the loss of structural information during edge pooling. Our work is motivated by successful applications of magnitude across range of machine learning tasks, such as the evaluation of diversity [40] for latent spaces, boundary detection for images [2], and the study of the generalisation behaviour of neural networks [3, 4]. Building up on this research, we are the first to propose the use of magnitude in the context of graph learning. We further advance on existing applications by investigating an alternative and closely-related measure, known as the spread of metric space [52], to substantially improve the computational efficiency our methods. Our main contributions are as follows:
We propose MagEdgePool and SpreadEdgePPol., two novel edge-contraction based pooling layers, which preserve graphs' structural diversity.
We investigate the spread of metric space as faster and more stable alternative to magnitude and ensure that our algorithms can be computed efficiently.
We evaluate our methods' capability preserve key structural properties during pooling.
We demonstrate that our pooling methods consistently perform well in graph classification tasks, achieving top accuracies among other pooling layers across wide range of experimental setups.
2
Background
We briefly provide background information on graph pooling, the magnitude of metric spaces, and diffusion geometry, taking care to point out related work and how it differs from ours.
2.1 Graph Pooling for Graph Neural Networks
As an ongoing field of interest for graph learning. a wide range of pooling methods has been proposed, which can be divided into global and hierarchical approaches. Global and hierarchical pooling methods fulfil fundamentally different but complementary roles distinct components of GNN architectures [32]. Global or flat pooling methods generate graph-level representations by reducing each graph single node and are commonly used as readout operations. Examples include mean- pool or sum-pool, which average or sum all node features, SOPool [51], which uses second-one -oddrr feature information, or DKEPool [13], which learns node distributions. However, global pooling methods discard all topological information, which can reduce the expressivity of these models and decrease their performance [8, 32, 34]. By contrast, hierarchical pooling methods sequentially coarsen graph representations while reducing their size, and are frequently used in alternation with

---

intermediate convolutional or message passing layers [41]. By reducing both features and adjacencies, hierarchical methods have the ability to preserve graphs' inherent geometry allowing GNNs to learn across multiple coarsening levels.
Research has traditionally focused on node-based hierarchical pooling via node clustering or node dropping. Amongst node drop pooling methods, Node Decimal Pooling (NDP) [10] is non-trainable, while TopK [12, 28] and SAGPool [36], are trainable approaches. However, all these methods inevitably lose information because they do not select all vertices but remove entire sections of the graph during pooling [41]. Node clustering approaches are similarly either non- con-trainable, such as Graclus [19] and Non-Negative Matrix Factorization (NMF) [6], or trainable, such as MinCUT [9] and DifiPool [56]. which output dense graph representations. In comparison to node drop pooling, clustering- -baend methods usually require high memory costs [41]. Overall, trainable methods have the potential to better optimise for a specific objective, but might overfit to the task at hand, especially for smaller datasets. By contrast, non-trainable methods can act as stronger inductive bias on the underlying graph representation, and do not introduce additional trainable parameters or optimisation objectives into the GNN [32]. Edge-based pooling methods have been studied less extensively than node-centric pooling [20, 35] despite their promising potential for encoding connectivities in a more faithful and natural manner. EdgePool [20], the most successful edge-based method, uses iterative edge-contraction based on edge scores, which are learnt from features of adjacent nodes. However, EdgePool always pools graphs to half their size, making it less flexible than more adaptive methods. Moreover, learning the edge scores during training is computationally expensive [8] necessitating the development of faster and more efficient edge pooling approaches. Further, EdgePool does not explicitly consider a graph's 's topology, beyond posing a constraint on not contracting adjacent edges. Thus, selecting edges based on node features can lead counter-intuitive decisions during pooling, for example by retaining local structures in grroggl-connecteo communities even high pooling ratios [20]. Interpretability remains leading concern [41], and non-trainable approaches are capable of being well-performing and traceable baseline pooling methods [32]. We edge pooling operations that make interpretable decisions on which aspects of the graph to retain. Figure I further illustrates how many of the aforementioned pooling methods inherently fail to preserve key p graph structures even for simple toy examples. Trainable methods in this overview were optimised for spectral loss following Grattarola al. [32]. but this does not ensure interpretable preservation of graphs' underlying geometry. Addressing these shortcomings, it is of interest to leverage alternative tools from computational geometry, which allow us to quantify the qualitative difference between graphs. While pooling based on spectral properties has been investigated extensively [10, 32], alternative geometric invariants like curvature or persistent homology have only been explored more recently [25, 55], and have not yet been applied to edge pooling specifically.
therefore find that there is strong potential for designing geometry-
2.2 The Magnitude and Spread of Metric Spaces
Magnitude is an invariant of (finite) metric spaces that measures the 'effective size' of space. It a measure of entropy and diversity [39] that has first been proposed in theoretical ecology [48]. Since its mathematical formalisation by Leinster [37], magnitude has been connected to numerous key geometric invariants, such as entropy, curvature, density, volume, and intrinsic dimensionality [39]. Because of its intriguing theoretical properties magnitude has received increasing interest for machine learning tasks [40]. However, the magnitude of graphs [38], despite being strong graph invariant, has not yet found its way into applications.
Throughout this paper, we consider an undirected finite graph G = (X, E) with n nodes as a finite metric space, consisting of the node set X equipped with a metric d: X x X + Rzo- Its similarity matrix Cx C RTx* is defined by (x y) = e d(z.y) for x, y E X. This allows us to introduce cemiearitydeependent notions of the diversity of metric spaces. To this end, we define a weighting on the metric space (X, d). which is vector E IR" such that (xw = I, where 1 is the column vector of ones. Whenever such weighting exists, the magnitude of the metric space (X, d) is uniquely defined by Mag(X)
>i=1 w(i). This is guaranteed if {x is positive definite, which essentially means that Çx invertible. A finite metric space with positive definite similarity matrix is called positive definite [43]. Metric spaces of negative type are positive definite [39]; this includes In" equipped with the Fuclidean distance [37], effective resistance distances
[18]. and diffusion distances [14]. Subsequently, we will refer to the magnitude of a graph G as the magnitude of its
3

---

associated metric space (X, That is. we define the magnitude of graph as
Mag(G)=
Σ (x' R.EEX
(I)
Closely related to magnitude, the spread of a metric space is another measure of "size' introduced by Willerton [52]. Given a metric graph G with the graph metric d, its spread is defined by
Sp(G) E ZEX EyEx E d
1
(2)
As diversity measures on graphs, both magnitude and spread summarise the number of distinct sub- communities in a network based on the distance metric and degree of similarity between nodes. This view on structural diversity naturally aligns with our goal of contracting redundant graph structures during pooling. Throughout this work, we investigate to what extent spread is a valid alternative to magnitude. This is motivated by the fact that computing magnitude in practice either requires inverting a matrix, solving a system of linear equations [40], or resort to approximations [5], which can be computationally expensive and numerically unstable. Metric-space spread in comparison can be computed given any distance (obviating the requirement of metric spaces of negative type), making it much more versatile [52]. Moreover, the sum of reciprocal mean similarities, spread can be calculated or approximated [23] much more efficiently than magnitude and does not require inverting a matrix. Although spread has been studied less extensively, there are strong reasons to assume that it shares the same advantages magnitude. In fact, for a positive definite metric space X, we have Sp(X)= < Mag(X) [52. Theorem 2]. Moreover, magnitude and spread coincide for finite homogeneous metric spaces [52, Theorem 3], such as the ring graph in Figure 1. In practice, as we further explore Appendix D.I, the magnitude and spread of graphs from real-world datasets, such as NCI1, exhibit nigh-perfect correlation when computed based on diffusion distances, underlining the strong connection between the two quantities.
2.3 Diffusion Geometry on Graphs
In this work, we use diffusion distances to compute magnitude and spread on graphs. This is motivated by their desirable theoretical properties and the capability of diffusion aid and act along message passing in GNNs: Diffusion operators are closely associated to random walks and are efficient identifying important structures in complex geometries while preserving local and non-linear structures [30]. The key idea is that the eigenvectors of the Markov matrices can be thought of as coordinates for the underlying graph structure [14]. This provides a vector-space representation of the graph that can be used to assess the dissimilarity between nodes.
We now briefly detail the type of diffusion distance used throughout this paper. Consider graph G and its adjacency matrix A. Let D be the diagonal degree matrix whose diagonal entries Dü = 2j=1 Aij
equal the degree of each vertex. The symmetrically normalised adjacency matrix À = D AD Markov transition matrix and represents the probability of moving from vertex to another. The normalised graph Laplacian is defined as i = - A= (D A)D 1. Since i is symmetric and positive definite, it has positive eigenvalues 2 Au > X1 > X2 > ... > An-1 2 0 with eigenvectors {1ht): This provides natural embedding of the graph G in Euclidean space given by:
(x)) = (Ar (z), ... An A for x E X.
(3)
The diffusion distance is then defined by the 1o-morm i.e.,
d(z, = (xx) 4(v)l22 f
Theorem 1. Any finite metric space (X, d) endowed with the diffusion distance positive definite.
As consequence of Theorem 1, the magnitude of any metric graph equipped with this diffusion distance is well defined. Leveraging diffusion distances for our methods has further benefits. The normalised graph Laplacian, which works with the relative connectivity between nodes, is robust to varying node degrees and graph sizes. This ensures that diffusion distances are on comparable scales across graphs, which enables us to compute and compare magnitude and spread directly. We note, however, that our pooling methods are flexible and can applied to a wider range of alternative distances similarities between nodes, which can be tailored to application domain.

---

Porting Roclo 92%
Porting Sario 60%
Poo Ret 60%
Poo Ing Rat 20%
Figure 2: Illustrating our proposed pooling method, MagEdgePool, on a graph from the ENZYMES dataset across varying pooling ratios. Each edge is coloured by its magnitude difference, which measures the impact its contraction would have on the graph's 's structural diversity. Edges with low magnitude differences are most redundant for the graph's geometry and collapsed first.
Methods
We first describe our magnitude-guider graph pooling methods in Section 3.1 while providing an in-depth theoretical analysis in Section 3.2.
3.1 Mauiie Graph Pooling
At the heart of our approach, use magnitude or spread monitor and control structural changes in the graph during edge contraction pooling. Edge contraction is chosen as pooling operation because respects graph connectivity, while outputting a sparsely-coneected graph representation. Conceptually, edge pooling thus aligns well with the goal of making minimal changes to the graph and keeping its diversity and geometry as unchanged as possible. Intuitively, pooled graphs with comparable magnitude will be similar in terms of effective size. That is, the effective number of distinct communities in the graphs are deemed similar based on their diffusion distance, i.e. based on the information flow between vertices.
Formally, let G = (X, E) be a graph and denote by G/e the graph resulting from the contraction of the edge e E E in G. We choose a pooling ratio r E (0, 1] and aim to reduce the graph to the denotes rounding the nearest integer. Initially, we set the pooled graph G' = (X', E") == G. To assess which edges to contract first, we determine their importance for the graph's 's global geometry by computing selection score for each edge, which we define as
corresponding number of nodes i.e. k = [r [X]] where
s(e) Mag () - Mag(G/e)).
(5)
That is, calculate the difference in magnitude between the original graph and the graph for which the edge has been collapsed. In this manner, we score an edge's 's relevance for the graph structure by the impact its collapse would have the graph's magnitude. In each iteration we then select the edge with the lowest magnitude difference
e E arg min s(e) CE E.
(6)
and assign G' = G' where E. E' the set of all edges that are adjacent an already contracted edge. The edge e; that we contract is selected at random whenever there is more than one valid option. all edges that meet this requirement have been collapsed, but the pooling ratio is not reached, we re-compute the edge scores on the new graph and repeat this procedure. We stop if the pooling ratio reached, i.c. |X' = [r []] or there are no edges left in the reduced graph, i.c. E' = 0. This approach allows to flcxibly reduce graphs to any desired size.
Edge pooling then gives a hard assignment of nodes, where each vertex is assigned single super-node in the output graph based on the neighbours it has been merged with. To compress the node features, we average the features of any node that contributed ensures that information on all nodes' features is preserved during pooling. Note that the feature aggregation function could easily be modified example. Restricting the number of times a vertex can be merged is enforced to prevent our methods from collapsing entire portions of a graph early in the pooling process. This enables more uniform pooling across the graph, which aids feature preservation and expressivity.
pooled super-node. This
use sum pooling instead of mean pooling, for
5

---

In nutshell: Our methods assume that the most redundant edges will be those whose removal would change the diversity of the graph the least. Magnitude informs us about the global importance of an edge. This implies that we want to start by merging edges from well-connected communities whenever their contraction does not notably change the graph's 's effective size.
As illustrated in Figure 2, our pooling method ensures that globally influential edges will be collapsed late in the pooling progress. For example, the edge which bridges the two parts of this enzyme graph is scored more highly and thus merged later than well-connected cliques. Redundant local structures collapsed first, and the overall (diffusion) geometry is respected. For the graph in Figure 2, this ensures that characteristic features of the enzyme, such as the cycle, are preserved across the pooling process. We provide a pseudocode implementation of our algorithm in Appendix C.4, Notice that we may use, mutatis mutandis, spread in lieu of magnitude. Whenever we use magnitude to compute the edge scores, we denote our algorithm by MagEdgePool, else we use the moniker SpreadEdgePool.
3.2 Theoretical Analysis
We now present theoretical properties of our pooling methods. First, we highlight fundamental invariances and properties of magnitude and spread used to design our algorithms. Further, we provide a bound on the difference in magnitude during pooling by the difference in spread, demonstrating the close relationship between the two. For a complete list or theorems and proofs, please refer to Appendix B.3.
Additivity for disjoint graphs. An important property of magnitude is that it behaves like the cardinality of sets. This behaviour is useful when computing the magnitude of a disconnected graph by splitting the problem into calculating the magnitude of the disconnected components.
Theorem 2. Consider a graph G G1 G2 consisting of the disjoint union of two graphs G1 and G2. Then Mag(G) Mag(G.) + Mag
Isomorphism invariance. Our pooling layers invariant under isometries of the input graph provided that the edge choice at each iteration is deterministic whenever the edge scores coincide. This is consequence of the following result.
Theorem For isomorphic graphs G1, G2, we have Mag(Gi) MMag(G2) and Sp(Gi) Sp(G2).
Edge contraction on graphs. Edge contraction is the main operation of our pooling methods and can be considered as a map f between graphs. The following result provides a sufficient condition to ensure that J remains compatible with the metric structure.
Theorem 4. Consider an edge-contraction map f: (Gi,d1) - (G2, d2) between positive definite metric graphs. If the map is 1-Lipschitz, i.e. d2( (vi), S (11, Vvi,u2 X1, then Mag(Ga) & M.g(Gr).
Starting from an initial metric graph G a I-Lipschitz edge-contraction map f yields a sequence of graphs {G.) where & the number edges that have been contracted. This sequence can be constructed as described by our algorithms in Section 1. We refer to the graphs resulting from the t edge-contraction using MagEdgePool G(A), Let A (k) Mag(G) |Mag(G(k-D)) Mag (+)) and let A Sp(G) = (Sp(G(k-1)) (p(G()))
Bounding magnitude by spread. We track the difference in magnitude and spread throughout the edge contraction process detailed above. This allows us to propose an inequality that describes the relation between the difference of magnitude and spread during pooling. The bound then demonstrate the close conceptual relationship between SpreadEdgePool and MagEdgePool.
Theorem 5. Consider a positive definite metric graph G with positive weights. Assume that the edge-contraction maps describing MagEdgePool and SpreadEdgePool induce distance decreasing surjections on the vertex sets. If
Sp(Gik))] < C' (k)
(k) Sp(()) then
A (k) Mag < 3CA (k) Sp(G).

---

Expressivity. Studying the expressive power of GNNs and their ability for distinguishing non- isomorphic graphs offers theoretical insights for understanding the theoretical capabilities of pooling operators. Bianchi and Lachi [8] state sufficient condition for a pooling layer to preserve the expressive power of the preceding pessage-passing (MP) layers. As demonstrated in Appendix B.4, MagEdgePool and SpreadEdgePool satisfy these conditions ensuring expressivity.
Computational Complexity. The time complexity of our pooling methods is independent of the GNN and is dominated by the cost of computing the edge scores in Equation (5), Given graph G= (X, E), magnitude has time complexity O (). In comparison, spread has time complexity O(LXP)) and can be more efficiently approximated [23]. Spread thus offers a considerably faster alternative. Now, let (Ca)) be the time complexity of computing the metric on G. The time complexity of SpreadEdgePool is dominated by O (Ca + | + log) El)) and MagEdgePool by + |X|3 + log E )). We note that on large graphs, it is possible to speed up the distance computations further to ensure scalability. See Appendix B.2 for full description of computational costs and Appendix D.2 for an empirical evaluation, which shows that our algorithm performs on-pa with existing pooling methods across the datasets evaluated throughout this work.
4 Experimental Results
Across our experiments, we address four key tasks, namely (i) graph classification performance, (ii) graph structure preservation during pooling, (iii performance across varying pooling ratios, and (iv) performance at graph property regression.
4.1 Graph Classification
The primary aim of using graph pooling layers is to preserve task-relevant information while reducing computational costs. In particular, useful pooling layers guarantee good performance across wide range of different datasets, thus capturing essential information for the task at hand. We thus investigate how well our aim to preserve structural diversity during edge pooling translates to practical performance at graph classification tasks. Note that our goal is not to reach state-of-the-art accuracies on all tasks, but to benchmark the performance gain or loss of different pooling operators.
Experimental Setup. We evaluate 8 different graph datasets, as detailed in Appendix C.2. input feature. To ensure
Whenever node features are not available, we use node degree fair comparison with alternative pooling methods, we follow the experimental setup by Grattarola et al. [32] and guidance by Errica et al. [24] for fair model comparison. Specifically, we plug in each pooling layer into the model architecture specified by Grattarola et al. [32], which is the following form:
MLP(X) - GNN(X, A) + POOL(X. A) + GNN(X, A) + GlobalSum X + MLP(X.
The model includes pre-processing and post-processing MLPs with 2 layers, 256 hidden units, ReL.U activation, and batch normalization. GNN(X, A) refers to graph neural network layer, more specifically a general convolutional layer [57] with parameters chosen according to the best results achieved by You et al. [57]. As an intermediate layer, POOL(X, A) corresponds to a specific pooling layer. All pooling layers are configured to pool each graph to around 50% of nodes. We also compare with 'No Pooling,' the same model architecture without any pooling layers. We use 10-fold stratified cross-validation and further partition the training data into 90% training and 10% validation data while keeping the labels balanced between splits. Finally, we report the best test accuracy of each model trained using Adam with a cross- cross-entropy loss (batch size 32, learning rate 0.0005, and early stopping based on the validation loss with a patience of 50 epochs). Further details are described in Appendix C.5.3.
Classification Results. Table 1 reports the mean and standard deviation of the test accuracy achieved by different pooling methods. We furthermore highlight which methods do not perform statistically significantly different from the best model (using pairwise Wilcoxon signed-rank tests applied to the accuracy scores and employing Holm-BBoferroni correction at significance threshold of = 0.05), thus permitting us to identify pooling methods that achieve top performance. Notably, both MagEdgePool and SpreadEdgePool achieve the best mean ranks across datasets in terms of their
7

---

Table 1: Mean and standard deviation of the graph classification accuracy. The best- pest-performing model is marked in bold. All models that did not perform significantly different from the best model are coloured green. The rightmost column shows the mean rank of each pooling method across datasets.
Method
ENZYMES
PROTEINS
Mutagenicity
DHER
IMDB-B
IMDB-M
NCI
NC1109
Mean Rank
Pooling
2.
0.88
80.1 1.3
1.44
6.77
4.70
76.5
74.3
913
76.4399
77,5
88.0
1.
4.
72.724
73.0
2,4
928 1,6
3311
76.0
90.7
71.8 1.5
47.3
734
7188
NDP
9.6
3.9
3.1
73.3 4.,6+
2.
70.6
70.022
3.6
Graclus
9.7
7.77
72.5 + 2.0
6..4
71.9 1.5
2.
68.8 14
6.15
5.6
NMF
8.0
8..
7..0
7.7
2.54
4.7
71.0
73.9 72.0
6.0
Tupk
7.5
73.2 1.4
75.8 4.7
68.9
1.59
45.6 1.0
75.3
4.9
SAGPoul
73.8
DiffPool MinCut
5.7
68.9 2.0
68.4
79.8
68.3+
0.8
68.9 1.0
6R.3+13
7.6
6..
75.6
1.3
70.9 1.5
6.7
0.7
4..
66.7 a
2.
accuracy. Further, they are always among the top-performing methods across evaluated datasets. Altogether, both their ranking and their individual accuracy scores thus demonstrate superior and consistently high performance across graph classification tasks. The performance benefits of our proposed pooling methods are most pronounced on DHFR [49], where our methods surpass even the GNN without pooling layer by around 17 percentage points. This provides evidence that the regularising effects of our pooling approach can help reduce overfitting, especially for small datasets and geometrically-riich graphs. For other biological datasets (Mutagenicity, NCII and NC109), methods show competitive performance with trainable layers, indicating that the introduction of additional trainable components into the pooling layer is not necessary to guarantee high task performance. On ENZYMES, DHFR, IMDB-BINAL and IMDB-MULT, non- -raintaie methods generally outperform trainable pooling layers, with MagEdgePool and SpreadEdgePov consistently reaching high accuracy.
Comparing pooling methods to using no pooling, we observe that MagEdgePool and SpreadEdgePPol reach similar or even higher performance across datasets. For six datasets, our inversity-guidde pooling methods improve mean accuracy, indicating that pooling retains task-relevant information while aiding the generalisation capabilities of the GNN. MagEdgePool and SpreadEdgePool act as interpretable and expressive pooling transformations (see Appendix D.3), which reduce the computational costs making GNNs learn from graphs' coarsened geometry. As reported in Table 1, MagEdgePool and SpreadEdgePool achieve very similar accuracies across datasets reaching top accuracies compared to alternative pooling layers. In practice, especially for large graphs, recommend using SpreadEdgePool due to its high predictive performance and superior computational efficiency.
4.2 Magnitude and Graph Structure Preservation
Motivated by the visual comparison graphs pooled using different pooling layers from Figure 1, we next set out to investigate the link between structure preservation and task performance. Specifically, we choose NCI1, dataset of 4, 10 graphs corresponding to chemical compounds, because has been shown to possess both informative features and task-relevant graph structures [15]. We follow the same classification procedure as before and extract the pooled graph representations after training the GNNs described in Section 1. Three pooling layers, MinCut, DiffPool and NMF, were removed from further comparison because they showed notably worse qualitative results for the motivating examples in Figure 1 and classification performance in Table 1. NDP and Graclus are evaluated across fewer pooling ratios than more adaptive methods, because they pool graphs to around half their size every step. To assess graph structure preservation, we use the spectral distance defined
as 1 22)2, i.e. the norm between the eigenspectra of the normalised Laplacians of the original and the pooled graphs [53]. We also report the magnitude difference between graphs to evaluate the preservation of structural diversity.
MagEdgePool and SpreadEdgePool exhibit small spectral distances across pooling ratios as visualised in Figure 3. This indicates that contracting edges guided by structural diversity preserves key spectral properties. Our methods also demonstrate low magnitude differences confirming that they perform as intended. In fact, the structure preservation scores for MagEdgePool and SpreadEdgePool coincide
8

---

Spectral Distance
Normal sed spectral distance pooling 0.5
Magnitude Difference
Relative magnitate diffrencce pooling ratto
Methood
specina datante
maghhtil d 0
NCP
Crackss
Task
SAGPool
Figure 3: Structure preservation for all graphs in the NCII dataset across varying pooling ratios. Left: The spectral distance between the normalised Laplacians of the original and the pooled graphs. Right: The relative difference in magnitude. which summarises the proportional difference in structural diversity after pooling, Violin plots show the variability across graphs at pooling ratio 0.5.
GIN ENZYYEE
NO1
EIK ENZYNES
3.0
2.-
0.40
0.80
MayEdggPool
SpriadEdgePool
NDP
0.70
Groclus
2.7
Topk
SWGPool
06-
0.40
2.4
3.2 6.1
0.2 0.2
0.5
2.4 pool Eg rado
O8
1.2
0.0
06 24
pooling D50
pocling 1986
packing mi
Figure 4: Classification performance across varying the pooling ratio for different pooling layers. Pooling is applied as part of a GIN architecture. Results are shown for the ENZYME and NCI1 datasets. Lines show the mean and shaded areas the standard deviation of the test accuracy.
almost perfectly, giving empirical evidence that spread offers an alternative to magnitude. Figure indicates that preserving magnitude corresponds to lower spectral distances and better retention of spectral properties. This link supports our motivation of guiding pooling by magnitude.
Alternative pooling layers fail to effectively preserve graphs' structural properties during both qualitative and quantitative comparisons varying extents. Node decimal pooling (NDP) [10] was specifically designed to preserve spectral properties during pooling. However, still reaches both higher spectral distances and higher magnitude differences than MagEdgePool on average across pooling ratios, as visualised in Figure 3. Finally, the sparse pooling layers Graclus, and SAGPool, all show higher spectral distances than our approach. This difference is even more pronounced in terms of magnitude differences, where all these three methods demonstrate high distortion of the underlying metric space diversity. These findings are repeated for further datasets (see Figure S.7 in the appendix) and agree with the qualitative comparisons between graphs pooled using different pooling layers as visualised in Figure 1. We thus conclude that MagEdgePool and SpreadEdgePoon successfully encode graphs' coarsened geometry during pooling, surpassing alternative pooling methods.
4.3 Pooling Ratio and Task Performance
From Table 1, we observe that it is possible to reach very high performance on benchmark datasets even while pooling each graph to half its size. Based this, we further investigate how the pooling ratio influences pooling layers and their classification performance. We consider two datasets, NCI1 and ENZYMES, which contains 600 graphs representing protein tertiary structures from 6 classes of enzymes and is selected as an example of a multi-class prediction task. We keep the same experimental setup described in Section 1. but use GIN layers instead of general convolutional layers to further assess whether the trends in performance differ across model architectures. Figure 4 reports the accuracy achieved by each pooling layer for varying pooling ratios. Notably, we observe that MagEdgePool and SpreadEdgePood consistently reach very high test accuracies even at low pooling rations. Meanwhile, the performance of other non- non-trainable methods drops notably more when graphs are pooled to up to 6.25% of their original size showing that they fail to preserve task-relevant information for both ENZYMES and NCII. We note that the trainable pooling layers, TopK and SAGPool, reach higher or comparable performance 50%, but decrease accuracy for more extreme pooling ratios. They consistently perform worse on ENZYMES, indicating that they distort important graph features or key graph structures during
NCI1 for pooling ratios above

---

pooling. MagEdgePool and SpreadEdgePool in comparison reach top performance and lower decreases in accuracy across varying pooling ratios demonstrating their potential to offer reliable, interpretable and stable pooling operations. Overall, the reported accuracies in Figure 4 agree with results in Table indicating that our observations hold for varying choices of GNN layers. We thus find across experiments that MagEdgePool and SpreadEdgePPoo constitute useful general-purpose pooling approaches, demonstrating their capability to faithfully encoding graphs' geometry, which ensures stable performance across pooling ratios, datasets and GNN architectures.
4.4 Graph Regression
We further apply our pooling methods to graph regression tasks. We modify the GNN architecture as described in Ap- pendix C.5.4 and plug in varying pooling layers. Table 2 reports the RMSE on the test dataset across pre-defined data splits and ten random seeds for three datasets from
Table 2: RMSE the test data for dif- ferent pooling methods.
Method
MolEsol
MolFreeSoly
MolLipo
No Pooling
1.44 0.30
2.98 0.78
0.88 + 0.30
OGB [33]. Overall, these results confirm that SdreadEdge- Pool and EagEdgePool constitute useful pooling opera- tions and reach comparatively low RMSEs across these three regression tasks. Our pooling methods successfully retain or improve task performance, indicating their ability to preserve task-relent musk-relevant information.
MagKdge SpreadEdge
1.47 0.11
281+ 0.30
0.23
1.15
2.83 0.244
0.22
NDP
1.11
3.17
0.09
Graclus
1.13
0.99
0.15
NMF
2.37
1
0.85
TopK
1.10
3.25
0.54
1.03 1
SAGPoul
1.61
2.77 0.188
DiffPool
1.7140.14
4.55
2.57
MinCut
1.88+0.51
0.33
0.12
4.5 Computational Efficiency
Finally, we evaluate the computational efficiency and scalability of pooling operators (see Ap- pendix D.2 for details). Our approaches scale reasonably well to the datasets evaluated in this study, both in terms of runtime and memory requirements, thus remaining applicable for graphs with up to few hundreds of nodes. Experiments confirm that SpreadEdgePool is notably faster than MagEdge- Pool and that distance approximations can be used to speed up the edge score computations used for pooling. Further, we find that pre-computing allows for notably lower GNN training costs compared to trainable methods; when comparing our methods EdgePool, our methods exhibit superior computational efficiency during training while ensuring similarly high classification performance.
5 Discussion
Despite its advantageous properties, our method exhibits certain limitations: We implicitly require redundancy and homophily in the graph representation to make it amenable to geometry-guided pooling. Our methods further assume that preserving graph structure is beneficial to the learning task. Otherwise, edge pooling still aggregates features faithfully (as evaluated in Appendix D.3), but the geometric objective might not necessary to ensure high performance (Appendix D.7 provides an extended discussion and ablation study on the importance of preserving graph structure or preserving expressivity during pooling). Moreover, our algorithm relies on efficient distance computations, and we only explore one specific case of diffusion distances, which could be sped up (see Appendix D.2) or generalised further in future work. Although the non-trainable nature of our pooling methods can be limiting, our experiments nevertheless demonstrate that trainable pooling layers do not guarantee higher performance on standard benchmark datasets for graph classification or regression.
Across experiments, we thus find that MagEdgePool and SpreadEdgePool constitute useful general- purpose pooling approaches: They are competitive compared to state-of ofte-----hhtttttt--e pooling layers for graph classification or regression tasks, and perform well for wide range of datasets and pooling ratios. Guiding edge pooling to preserve graphs' structural diversity successfully encodes key graph properties, ensuring stable and interpretable performance. Further, we overcome a major limitation of computing magnitude on large graphs by proposing spread as a substantially faster and closely-related alternative, which has the potential to aid research in geometric deep learning and efficient diversity evaluation beyond the scope this paper. For future work, we plan on applying our methods with alternative graph distances, to scale computations to large-scale graphs, or to determine ideal pooling ratio automatically, Our methods are available as a Python package on GitHub.
'tttp::// h/tps::///tttttt www.://.oommooooooocceoo
ppol available under a BSD 3-Clause License.
10

---

Acknowledgements
The authors are grateful for the stimulating discussions with the anonymous reviewers and the area chair, who believed in the merits of this work. K.L. is supported by the Helmholtz Association under the joint research school 'Munich School for Data Science (MUDS)."
Funding Disclosure
This work was partially funded by the Helmholtz International Lab Causal Cell Dynamics InterLabs- 0029 grant by the Initiative and Networking Fund of the Hermann von Helmholtz-Associaaion Deutscher Forschungszentreen V. [K.L.], Mila EDI scholarships [L.M.], Humboldt Research Fel- lowship, CIFAR AI Chair, NSERC Discovery grant 03267, FRQNT grant 343567, and NSF grant DMS-2327211 [G.W.]. This work has received funding from the Swiss State Secretariat for Education, Research, and Innovation (SERI). The content provided here solely the responsibility the authors and does not necessarily represent the views of the funding agencies.
References
[1] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, Dean, Devin, S. Ghemawat, Goodfellow, A. Harp. G. Irving, M. Isard, Y. Jia, R. Joze- fowicz, L. Kaiser, M. Kudlur, J. I Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, Tucker, V. Vanhoucke, V. Vas- udevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng, TensorFlow: Large-scale machine learning on heterogeneous systems. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI' 16, page 265-283, USA, 2016. USENIX Association. Software available from tensorflow.org.
[2] M. F. Adamer, E. De Brouwer, L.. O' O'Bray, and B. Rieck. The magnitude vector of images. Journal of Applied and Computational Topology, 8(3) 2024.
[3] R. Andreeva, K. Limbeck, B. Rieck, and R. Sarkar. Metric space magnitude and generalisation in neural networks. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 242-253, PMLR, 2023.
[4] R. Andreeva, B. Dupuis, R. Sarkar, T. Birdal, and Simsekli. Topological generalization bounds for discrete-time stochastic optimization algorithms. In Advances in Neural Information Processing Systems, volume 37, pages 7765-4815 Curran Associates, Inc., 2024.
[5] R. Andreeva, Ward, P. Skraba, J. Gao, and R. Sarkar. Approximating metric magnitude of point sets. In Proceedings of the AAAI Conference Artificial Intelligence, volume 39, pages 15374-15381, 2025.
[6] D. Bacciu and L. Di Sotto. non-negative factorization approach to node pooling in graph convolutional neural networks. In AI* IA A0v9-Adsances in Artificial Intelligence: XVIIhth International Conference of the Italian Association for Artificial Intelligence, volume 18, pages 294-306 Springer, 2019.
[7] M. Bechler- I. Amos, R. Bilaa-Bachrrach and A. Globerson. Graph neural networks use graphs when they shouldn't. In Proceedings of the 41st International Conference on Machine Learning, 2024.
[8] M. Bianchi and Lachi. The expressive power of pooling in graph neural networks. In Advances in Neural Information Processing Systems, volume 37, pages 71603-71618, 2023.
[9] F. M. Bianchi, D. Grattarola, and C. Alippi. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the 37th International Conference on Machine Learning, pages 874 883. PMLR, 2020.
[10] F. M. Bianchi, D. Grattarola, L. Livi, and C. Alippi. Hierarchical representation learning in graph neural networks with node decimation pooling. IEEE Transactions on Neural Networks and Learning Systems, 33(5):2195-22000 2020.

---

[11] K. M. Borgwardt, C. S. Ong. S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kemnels. Bioinformatics, 21:147-156, 2005.
[12) C. Cangea, P. Veličković, N. Jovanovic, T. Kipf, and P. Liò. Towards sparse hierarchical graph classifiers. arXiv preprint arXiv:/811.0125) 2018.
[13] K. Chen, J. Song, S. Liu, N. Yu, Z. Feng, G. Han, and M. Song. Distribution knowledge embedding for graph pooling. IEEE Transactions Knowledge and Data Engineering. 35(8): 7898-7908, 2022.
[14] R. R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5 30, 2006.
[15] C. Coupette, J. Wayland, E. Simons, and B. Rieck. No metric to rule them all: Toward principled evaluations of graph-learning datasets. Proceedings of the 42nd International Conference on Machine Learning, pages 14405-11434 PMLR, 2025.
[16] G. David and A. Averbuch. Hierarchical data organization, clustering and denoising via localized diffusion folders. Applied and Computational Harmonic Analysis, 33(1):1-22 2012.
[17] Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7(Jan):1-30, 2006.
[18] K. Devriendt and R. Lambiotte. Discrete curvature graphs from the effective resistance. Journal of Physics: Complexity, 3(2)022008,, 2022.
[19] I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE Transactions on Puttern Analysis and Machine Intelligence, 29111):1944-195, 2007.
[20] Diehl. Edge contraction pooling for graph neural networks. arXiv preprint 1rXiv:1905.10990 2019.
[21] Diehl, T. Brunner, M. T. Le, and A. Knoll. Towards graph pooling by edge contraction. In 36th International Conference on Machine Learning Workshop on Learning and Reasoning with
Data, 2019.
[22] P. D. Dobson and A. J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 530(4):771-783) 2003.
[23] K. Dunne. Efficiently approximating spread dimension with high confidence. arXiv preprint 2408 /4590, 2024.
[24] Errica, M. Podda, D. Bacciu, A. Micheli, al. A fair comparison of graph neural networks for graph classification. In Proceedings of the 8th International Conference Learning Representations, 2020.
[25] A. Feng and M. Weber. Graph pooling via Ricci Flow. Transactions on Machine Learning Research, 2024.
[26] M. Fey and J. E. Lenssen. Fast graph representation learning with PyT Porch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[27] M. Fey, J. Sunil, A. Nitta, R. Puri, M. Shah, B. Stojanovic, R. Bendias, B. Alexandria, V. Kocijan, 7. Zhang, X. He, J. E. Lenssen, and J. Leskovec. PyG 2.0: Scalable learning real world graphs. In Temporal Graph Learning Workshop, KDD, 2025.
[28] H. Gao and S. Ji. Graph U-Nets. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages
PMLR, 2019.
[29] D. Garreau, W. Jitkrittum, and M. Kanagawa. Large sample analysis of the median heuristic. arXiv preprint 17X00
12

---

[30] J. Gasteiger, S. Weißenberger, and S. Günnemann. Diffusion improves graph learning. In Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[31] D. Grattarola and C. Alippi. Graph neural networks in tensorflow and keras with spektral. IEEE Computational Intelligence Magazine, 16(1):99-106, 2021.
[32] D. Grattarola, D. Zambon, F. M. Bianchi, and C. Alippi. Understanding pooling in graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 35(2):2708-25 27188 2022.
[33] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, volume 34, pages 22118 22133,, 2020.
[34] B. Knyazev, W. Taylor, and M. Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, volume 32, pages 4202-4212, 2019.
[35] F. Landolfi. Revisiting edge pooling in graph neural networks. In ESANN, 2022.
[36] J. Lee, Lee, and Kang. Self-attention graph pooling. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3734-3743. PMLR, 2019.
[37] T. Leinster. The magnitude of metric spaces. Documenta Mathematica, 18:857-905,2013
[38] T. Leinster. The magnitude of a graph. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 166, pages 247-264. Cambridge University Press, 2019.
[39] T. Leinster. Entropy and Diversity: The Axiomatic Approach. Cambridge University Press, 2021.
[40] K. Limbeck, R. Andreeva, R. Sarkar, and B. Rieck. Metric space magnitude for evaluating the diversity latent representations. In Advances in Neural Information Processing Systems, volume 38, pages 123911-12332 1-123953. Curran Associates, Inc., 2024.
[41] C. Liu, Y. Zhan, Wu, C. Li, B. Du, W. Hu, T. Liu, and D. Tao. Graph pooling for graph neural networks: progress, challenges, and opportunities. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, pages 6712-6722, 2023.
[42] A. W. Long and A. L. Ferguson. Landmark diffusion maps (L-dMaps): Accelerated manifold learning out-of-sample extension. Applied and Computational Harmonic Analysis, 47(1): 190-211, 2019.
[43] M. W. Meckes. Positive definite metric spaces. Positivity, 17(3):333-757 2013.
[44] D. Mesquita, A. Souza, and S. Kaski. Rethinking pooling in graph neural networks. In Advances in Neural Information Processing Systems, volume 33, pages 2220-2233 Curran Associates, Inc., 2020.
[45] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08661, 2020.
[46] I. Schomburg, A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg. BRENDA, the enzyme database: updates and major new developments. Nucleic Acids Research, 32:D431-D433 2004.
[47] N. Shervashidze, Schweitzer, E. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Van Leeuwen. K. Mchlhorn, and K. M. Borgwardt.
[48] A. R. Solow and Polasky. Measuring biological diversity. Environmental and Ecological Statistics, 1:95-103, 1994.
13

---

[49] J. J. Sutherland, L. A. O'brien, and D. F. Weaver. Spline-fitting with genetic algorithm: A method for developing classification structure- activity relationships. Journal of Chemical Information and Computer Sciences, 43(6):1906-115,, 2003.
[50] M. A. Terpilowski. scikit-posthess: Pairwise multiple comparison tests in python. Journal of Open Source Software, 4(36):1169 2019.
[51] Y. Wang. W. Hou, N. Sheng, Z. Zhao, J. Liu, L. Huang, and J. Wang. Graph pooling in graph neural networks: Methods and their applications in omics studies. Artificial Intelligence Review, 57(11), 2024.
[52] S. Willerton. Spread: a measure of the size of metric spaces. International Journal of Computational Geometry & Applications, 25(03):207-225, 2015.
[53] Wills and G. Meyer. Metries for graph comparison: practitioner's guide. Plos one, 15(2): e0228728, 2020.
[54] P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACHh SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365-1374, 2015.
[55] C. Ying, X. Zhao, and Yu. Boosting graph pooling with persistent homology. In Advances in Neural Information Processing Systems, volume 38, pages 19087-19113, 2024.
[56] Z. Ying. J. You, C. Morris, Ren, W. Hamilton, and Leskovec. Hierarchical graph repres- entation learning with differentiable pooling. In Advances in Neural Information Processing Systems, volume 31, pages 4805 4815. Curran Associates, Inc., 2018
[57] You, Z. Ying, and J. Leskovec. Design space for graph neural networks. In Advances in Neural Information Processing Systems, volume 33, pages 17009-1700 17021. Curran Associates, Inc., 2020.
14

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We support all claims made in the introduction by empirical or theoretical
evidence.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the computational complexity, and the non trainable nature of our pooling approach. We further state our main assumptions on which edges in the underlying graph deemed redundant and merged during pooling throughout the paper and clearly state any assumptions made for our theoretical contributions. Further, we clearly describe how empirical results were derived.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an import- ant role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
15

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All proofs reference relevant mathematical literature, stated or referenced in the main text or included the supplementary materials.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We follow an established benchmark setting by Grattarola et al. [32] to evaluate our pooling methods, and explain all further design choices we make throughout the paper, such as the use of stratified cross-validation instead of random sampling. The benchmark setup we use is therefore easily reproducible. Further, we provide the code for our algorithm. Further, all benchmark datasets used for evaluation are publicly available under the TUDataset project [45].
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code reproduce the main experiments in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.
httl://guuides//deeubbbbiii cassssooooicyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttppp.ccppppiii/////tptppptptpp htte/uulicggguuiieee getge/uiee///ee httgggddd///oeeudmiiiiiia Swodeeuumissiiiiiiieic.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We follow the benchmark setting by Grattarola et al. [32] for our experiments and further explain the model architecture, all parameter choices and method choices throughout the paper. Design choices for our proposed pooling method, such as the choice graph distance, are explained in detail.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
17

---

Justification: We report standard deviations for our classification results and further use statistical testing to determine which models performed on-par to the best performing models across datasets. The structure preservation experiment further includes violin plots to plot the distributions of structure preservation scores. Finally, when varying the pooling ratio, we report the standard deviation of each model's accuracy.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confid- ence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We detail the computational resources used for our experiments in the supple- mentary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpp:://///riiii http///nerrrp.pee. cc http:/pubic/tthisssiiiiie
Answer: [Yes]
Justification:
We have read and follow the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
18

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We find that the proposal of novel pooling methods for GNNs unlikely to have direct negative societal impacts. We further aimed to design interpretable and reliable pooling operators, which should mitigate the risk of unintentionally providing mislcading results due to the pooling layer.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
19

---

Answer: [Yes]
Justification: We are careful to reference the code and dataset used throughout this work. Further details included in the supplementary materials.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide minimal implementation of our pooling methods in Python that can be easily integrated into existing workflows.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
20

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: http///ee.ppp///// for what should or should not be described.
/LLM)
21

---

Appendix (Supplementary Materials)
Technical Appendices and Supplementary Material
23
Theoretical Analysis
23
B.1
Diffusion Distances
23
B.2
Computational Complexity
23
B.3
Magnitude and Spread
24
B.3.1
Additivity for disjoint graphs
24
B.3.2
Isomorphism invariance
24
B.3.3
Edge contraction on graphs
25
B.3.4
Bounding magnitude by spread
25
B.4
Expressivity
27
Extended Methods
28
C.I Hardware and Software
28
C,2 Datasets
................................
28
C.3 Magnitude and Spread Computations
29
C.4 Pooling Algorithm
30
C.5 Extended Experimental Details
31
C.5.1
Overview Experiment
C.5.2
Structure Preservation Experiment and Pooling Ratios
31
C.5.3
Graph Classification Experiment
31
C.5.4
Graph Regression
D Extended Results
32
D.I
Correlation between Magnitude and Spread
32
D.2
Evaluating Computational Efficiency
................................
33
D.2.1
Training Costs
33
D.2.2 Pre-training Costs
................................
33
D.2.3
Runtimes across Pooling Ratios
D.3
Node Feature Preservation and Expressivity
35
D.4 Overview Experiment
36
D.5 Graph Classification..
36
D.6 Comparison with EdgePool
38
D.7 Comparison with Randomised Pooling
38
D.8 Preserving Graph Structure
39
22

---

A Technical Appendices and Supplementary Material
To elaborate the results reported in our main paper, we first detail extended theoretical results and proofs for our theoretical contributions. In particular, we investigate computational complexity as well as the relationship between magnitude and spread. Next, we detail our experimental evaluation, the assets used for our experiments, and the algorithm describing our pooling methods. Finally, we report extended results on the experiments included in our main paper.
B Theoretical Analysis
This section details full proofs and extended explanations for the mathematical theory introduced in Section and the theoretical analysis our pooling methods described Section 3.2.
B.1 Diffusion Distances
As detailed in Section 2.3, the diffusion distance is defined by
d(r, u) = [1((x)) - (by)ll2 for 2, E X.
Theorem 1. Any finite metric space (X, d) endowed with the diffusion distance is positive definite.
Proof. By definition of the diffusion distance, the map 4 X + R- in Equation (3) defines an isometry (X, d) + NN := (IR-11 d2), where d2 is the metric induced by the 1n-norm. Finally, by Theorem 2.5.3 in Leinster [37], subsets of Euclidean space 12 -1 are positive definite.
B.2
Computational Complexity
We next analyse the computational complexity of our pooling methods, which are described in Appendix C.4 and Section 3.1. Specifically, we expand on the statements in Section 3.2 by detailing the computational complexity of the pooling process. Given graph G (X, E), let k L(1 X) [1 be the number of nodes that should be contracted as determined by the pooling ratio r. The time complexity of our pooling approach can be split up into the following steps:
Computing magnitude or spread. Magnitude has time complexity O(IX))) and can further be approximated via iterative normalisation in O x |S; x x time assuming G has positive weighting where is the number of iterations and S, X [5]. Spread computations have time complexity ( which is a notable improvement to magnitude. It is possible to approximate spread computations via subsets [23] or iterative optimisation using mini- batching [5]. For iterations subsets S; C X, the time complexity of approximating spread reduces to Oii x |S|| x [X] [5, 23]. Spread thus offers much faster alternative to magnitude and can scale to large graphs considerably more efficiently.
Computing distances and similarities. For large datasets, it is key to speed up the distance calcula- tions. Diffusion distances have time complexity O((x))), but can be reduced x when restricting the computations to the top k eigenvectors. Diffusion maps can further be approximated via low-rank approximations. To reduce the cost of repeated distance computations, it is possible to approximate the metric on the reduced graph G/c by directly updating the distances for G. Given a distance matrix, computing the similarity matrix then has linear time complexity in the number of entries. Denote the time complexity of computing the distances and similarities by OCCa).
Edge contraction. To get G' G/e,, contracting an edge e E takes O(IX) time.
Edge score computations. For each edge, its edge score is computed by applying the edge con- traction and computing the magnitude or spread of the reduced graph, which takes O(XX + C2 + Cs) time, where Cs refers the cost of computing either magnitude or spread as detailed above. Note that the computation of these edge scores is independent across edges and can be parallelised.
Edge score sorting. The edge scores can be sorted from lowest to highest in O( log El) time.
23

---

Feature aggregation. The node features, F C RIXIF, can be aggregated in O[[X) x f) time.
Putting this all together, we get that the cost of our pooling algorithms can be described by a worst-case time complexity of
O( + C. + Cs Log|E)))) + IXI + +))
if k X and the graph not pooled to less than half its size. Otherwise, if ].5]X], we re-compute the edge scores whenever no valid edges are left as described in Section 3.1. In this scenario, the first term of the complexity expression is repeated, corresponding to re-computations on successively smaller graphs. In summary, the overall time complexity of our pooling method is dominated by the cost of calculating and sorting the edge scores. This cost is independent of the choice of GNN architecture, ensuring that the training costs remain stable and do not escalate with model complexity. In practice, as further explored in Appendix D.2, we thus find that our pooling algorithms perform on par with alternative pooling layers in terms of computational efficiency.
B.3 Magnitude and Spread
B.3.1 Additivity for disjoint graphs
As measure of the effective size, one appealing property of magnitude is that it behaves akin to cardinality. In fact, magnitude is additive when taking the disjoint union of multiple metric spaces.
Theorem 2. Consider a graph G G, L L22 consisting of the disjoint union of two graphs G₁ and G2. Then Mag(G) M.a + MMg(Ga))
Proof. Let G (X, F.) together with the metric be a positive definite metric graph. Assume G is disjoint union of two metric graphs (G1,d1 and (G2, d2) over the vertex sets X1 and X2, respectively, such that dxx, = di and d x2 d2 and d(z1, = oo for all #1 X1, X2 E X2. Then, Sa = Sa, @ Sa. and Mag(G) = Mag(G,) + Mag(G2).
This result applies graphs equipped with the shortest-path distance or the diffusion distance considered in this paper, because the distance between two nodes depends only on the connected component they belong to and is infinite if there no path between them. Therefore, we can naturally see the similarity matrix La as block-diagonal and compute the magnitude of G by summing up the magnitude of its disconnected subgraphs.
B.3.2 Isomorphism invariance
A key property of magnitude and spread is that they are isometry invariants of metric spaces. Note that by graph isometry mean an isometry on the underlying vertex set equipped with metric. Theorem 3. For isomorphic graphs G1, G2, we have Mag(Gi) Mag(G2) and Sp(Gi) Sp(G2).
Proof. Let f: (X1, d1) + (X2, d2) be bijective isometry between the metric graphs G1 and G2, respectively. Then, for all y E X1 we have that d2 (zr),,, f fw)) d, (x, y). A consequence of the bijectivity of f is that the distance matrices coincide (up to permutations) and that Çi = (2. This implies in turn that Mag(Gi) = Mag(G2) and that Sp(G1) Sp(G2).
Based on this property for magnitude and spread, we can show that isometry invariance also holds for proposed pooling algorithm further detailed in Appendix C.4.
Corollary 1. MagEdgePool and SpreadEdge are graphs provided the choice of edges contract at each iteration is deterministic whenever the edge scores coincide.
if applied to isomorphic
Proof. Let f: (G1, (G2, d2) be a graph isomorphism and an isometry. From Theorem 3, we know that the edge scores as defined in Equation (5) for e1 Ej and f(r) E E, will coincide, i.c. Because the choice of edges to contract at each iteration is further assumed to be deterministic if edge scores coincide, it follows that every edge contract in G2 corresponds to the image (e) of an edge e to contract in G and vice versa. Hence, the pooled graphs output by our algorithm are isomorphic.
s(e1) = =(f(er)
D
24

---

B.3.3 Edge contraction on graphs
We first recall important results about magnitude in the context of (strictly) positive definite finite metric spaces and refer the interested reader to Leinster [37] for further details.
Proposition (Proposition 2.4.3, Leinster [37]). Let (X,d) be a positive definite metric space with finite cardinality |X| n. Then
4)) v D'v
Mag(X)
sup ((R"((O)
(8)
Proposition implies that the magnitude of positive definite metric spaces is always positive. Another consequence of this result monotonicity property on subsets of these metric spaces.
Corollary 2 (Corollary 2.4.4, Leinster [37]). Let (X, d) be positive definite finite metric space and consider a subset Y C X (endowed with the induced metric). Then
MYg(Y)= Σ Mag(X).
We will now show an analogous result for graphs constructed via edge contraction.
Theorem 4. Consider an edge-contraction map f: (G), + (G2, d2) between positive definite metric graphs. If the map is 1-Lipschitz. i.e. d2(f(v1), s di di 02) Vul, U2 E X1, then (agg(G2) S Mag(G1).
Proof. Let f: (G1, d1) - (G2, be an edge-contraction map and let == |x1] and : [2]- We will identify I with a subset of IR = Rm ② RR-m using the map (#1, vm) E R -
(U1, Um, 0, ... 0) IR" Then,
v Sx v
Σ
UsSxi [8,10,
=
Σ
Us
1.
$
U:Sxa H...
i
and
1
V #
(10)
\x2"' u 21
u'Xx, 2
Finally, by Proposition and Equation (10), get that
Mag(Gn)
sup (ER
Uf (xx v
EE w4)
sup
v'xx, v
Em 2x
sup
v'xx2u
HR (0) (0)
Mag( G2)
B.3,4 Bounding magnitude by spread
Recall that for positive definite metric spaces, magnitude known to be an upper bound for spread.
Theorem 6 (Theorem 2.2. from Willerton [52]). Suppose that X is finite metric space. If X is positive definite then
Sp(X) < Mag(X).
25

---

We will now use this bound as well as the results in Appendix B.3.3 to investigate the relationship between MagEdgePool and SpreadEdgePool. Through a process of iterated edge contraction, our pooling algorithm produces sequence of hierarchically pooled graphs (as described in Section 3. and Appendix C.4). Note that is not guaranteed that MagEdgePool and SpreadEdgePool yield the same sequence. For this reason, we will refer to the graphs resulting from the h*hh adge-contraction with MagEdgePool and SpreadEdgePool by G and (()) respectively.
For each k, the edge contraction map G(k) + G(k+1) is surjection on the underlying vertex sets x(k) and (((+1) respectively, i.e ((++1) C x Moreover, we will assume that for any & this map is distance-decreasingg That is, 1(k++) (fxx), S ( (z)) for all z,, 25 E (
Recall that for any k, Mag(G(k)) the magnitude of a finite positive definite metric space (X(+), d. Then, by Theorem 4, we deduce that for any k,
(ag(G( < (ag(G
(11)
Note that by construction, scoring the edges in Algorithm translates into the following:
X (
argminy cxa D, 1) (ag((X(k
MMa((Y)
(12)
and,
X argminy y || (p(p- Sp(())-
(13)
Then, by the monotonicity of magnitude, i.e. Equation (11),
x
II Mag(Y) = c.t
Let A (k) Mag G) = Mag(GG - Mag (Ggg)(())) and let A (k) Sp(() = [Sp(G (p(G()) ) For the following result, we assume that scores are only computed once and that they are the only criterion for edge contraction. Furthermore, we will assume that spread is monotonically decreasing.
Theorem 5. Consider a positive definite metric graph G with positive weights. Assume that the edge-contraction maps describing MagEdgePool and SpreadEdgePool induce distance decreasing surjections on the vertex sets. If [Mg (G (() -ppp)) S CA (R) Sp(G), then
A (k) Mag(G) S 3CA (A) Sp(G). (p(G))
Proof. For any we have the following inequality:
(ag(G((-2)) (() & (pp(G(*-1)) Sp(( + Mag(GG()) Sp(G()))
+ (M -pp((t--)))SSC(t11
Assume that (ag(C((-1)) (p((( CA (p()s) for some constant C > 0. By the mono- tonicity of magnitude (Theorem 4), we get that Mag (aggG S Mag(C((-11) and.
Mag(G (p(G(H)) Mag(G(k-1)) Sp(G(() CC Sp(G).
Similarly, assuming monotonicity of spread yields Sp(G(k)) S Sp(G(k-1)) and,
(ag(G(k-11) 1)) (p( = (ag(G((-1))= - Sp(C S CA (K) (A
Since < Sp(G((-1))- - (p((())) < Mag(G(t-11) - Sp(G())), the constant C' must be greater than equal to 1. We conclude that
Mag(G) S (pCA)))(()).
26

---

B.4 Expressivity
While studying the expressive power of GNNs, we aim to evaluate their ability generate different outputs for non-isomorphic graphs. Here, we will analyse the expressive power of our pooling methods MagEdgePool and SpreadEdgePool within the -eeee--Reucc-C--n
framework introduced
by Grattarola et al. [32] for describing pooling operators. Let G = (x; F)) be graph and F E x be the node features associated to the nodes in G. Then, a graph pooling operator is regarded as a function POOL: (F, G) H> (FP.Cr Gp) where Fp denotes the pooled node features and Gp = (Xp, Ep) the pooled graph with pXpl S [.X]. Pooling is described as a combination of three elementary functions: selection (SEL), reduction (RED), and connection (CON). The selection function clusters the nodes of the input graph into super-nodes, so that SEL: G + S = {S, { !Xal
| and Sij is the membership score of the node i to super-node j. Node selection can be represented as the assignment matrix S E IR X |X|x with entries Sij. Based on this selection, the reduction function aggregates node features of all nodes that are assigned to the same super-node, i.e. RED: (F, .) + Fp. Then, the connection function, CON, generates the edges and determines the connectivities between super-nodes in the pooled graph. Finally, to study expressivity, we note that hierarchical graph pooling is typically applied in GNN architectures after some initial message passing layers. Let G denote the graph resulting from block of L MP layers and F E IR X the corresponding feature matrix [8].
where S |
Theorem 7. (Theorem from Bianchi and Lachi (8]) Let G1 = (X1, and G2 (X2, E2) be two graphs equipped with node features F; E R X.Ix/ for 1,2. Assume that G1 Fwi. G2 i.e. that G1 and G2 are distinguishable by the Weisfeiler-Lemar isomorphism test. Apply a block of LP layers to get G and G/ as well as F and F Let POOL be a pooling operator placed after these MP layers to get G1p = P and G2p = ( associated with the node features FiP and 22 in R Then, Gip and G2p will have different node features (up to permutation) provided the following conditions hold:
1. DIKil FL. *
E 2
2. The memberships generated by SEL satisfy Σ/=1 Sig = X, with X >> for each node i, i.e. the cluster assignment matrix S is a right stochastic matrix up to the global constant X
3. The reduction function satisfies RED: (F", S) + Fp = FT.
The WL test will identify that two graphs with different multisets of node features are non-isomorphic based on the injectivity of the colouring function of the WL algorithm. Theorem then guarantees that G1, FWL G2,, thus ensuring that the pooling operation POOL preserves expressivity.
Corollary 3. MagEdgePool and SpreadEdgePPoo satisfy the sufficient conditions outlined in The- orem 7 when using sum aggregation for pooling the node features.
Proof. Condition 1 is independent to the choice of pooling layer and instead relates to the expressivity of MP layers. is guaranteed for any MP layer that is powerful the 1-WL test [8, 25). Conditions 2 and 3 hold trivially by construction. Each super-node is the result of edge contractions and node features are aggregated via summation. Hence, each vertex is assigned the selection matrix is constructed as S3y = 1 if the node is contained in super-node j and S.y = O otherwise. This ensures that Σ Sig for every node i fulfilling condition 2. The resulting SEL product of these
unique super-node and
function can be represented using the cluster assignment matrix S obtained elementary (contraction) operations represented by matrices. This yields the RED function described in our algorithm in Algorithm map FL - S FL that respects condition 3.
27

---

C Extended Methods
C.1 Hardware and Software
The experiments reported in our study were implemented using spektral 1.3.1 [31]' and tensorflow 2.16.2 2 [1]². As further detailed in Appendix C.5.3 and Section 4.1, we base our the benchmark setup and code by Grattarola et al. [32]*, which also include implementations for the pooling layers compared across our study. By relying on this existing framework, we aim ensure the reproducibility of our results.
graph classification experiments
Further, to calculate magnitude and spread we rely on magnipy. a Python package by Limbeck et al. [40] for magnitude and diversity computations. Further, novel contribution of this paper, extend the computation of magnitude to graph data and novel graph metrics. Specifically, we modify the computations, so that the magnitude of disconnected subgraphs is computed separately (based on Theorem 2) using the NetworkX package. We also implement graph distances that have not previously been used to compute magnitude, such as the diffusion distances detailed in Section 2.3. Further details on the code for implementing our proposed pooling methods and our experiments can be found in our supplementary code submission as well as on GitHub. Finally, we publish reproducible PyTorch ch implementation of our pooling methods as pag_edde_pool" on GitHub.
All experiments were conducted a high- perforreformance cluster with hardware specifications as detailed in Table S.1. In particular, all experiment were run requesting a single GPU with 32 GB video memory or less.
Table S.1: Summary of the compute resources used for our experiments.
Inventory
Models
Available CPUs
Intel Xeon (Gold 6128, 6130, 6134, 6136, 6142, 6240, 6248R)
Intel Xcon Platinum (8280L, 8480+, 8468, 8562Y+)
Intel Xeon (E7-4850, E5620, 4114, 6126)
AMD EPYC (7262, 7413, 7513, 7713, 7742)
AMD Opteron (6128, 6164 HE, 6234, 6272, 6376 x2)
Available GPUs
NVIDIA Tesla (K80, P100, V100)
NVIDIA A100 (20GB, 40GB, 80GB PCIe)
NVIDIA H100 (80GB PCIe)
NVIDIA Quadro RTX 8000
C.2 Datasets
We briefly describe the graph datasets analysed throughout our work. Simulated graphs, as used for Figure 1, are created using either PyGSP or NetworkX" and all example graphs were created to consist of 64 nodes.
For our main graph classification experiments, we analyse six graph datasets taken from biological or chemical applications [11, 22, 46, 47, 49], and two datasets which represent social networks [54]. All datasets are taken either from the TUDataset benchmark [45] or the Open Graph Benchmark!! 11
hactps://grspheurrll.ccowo network/ www.ork/aaallabbbeeeceecc.. available under 2/ available under the Apache Software License
MIT license.
httppp///pppp..rrrppppp////tootp (Apache 2.0). http:////ggttttoc.coomaaaallele/ available to the research community (Grattarola
[32).
hattes///gtttbbu.ccm///llelll/ap available under BSD 3-Clause License.
under a BSD 3-Clause License.
httppp///httbbbbooooaaaaaolaaaap available under a BSD 3-Clause License.
httrg:///yygggp.aaaaedddaaaaaaas availaalaaaabbbaaaalllllall under a BSD-3-Clause license.
hattpp/://gttttblbccc//////////s available under BSD 3-Clause License.
1"nttpe:/cchemrre: github.
httpr/aarrrrgttab....aaaaattttte io/dataettaaaaaaeeaesaaaaaaatett available under a CC-B Y-4.0 license.
Phttps://ogb.statrt edu/ available under MIT licence.
28

---

More specifically, the results in Table 1, Table 2, and Table S.8 analyse the following graph datasets described in Table S.2. Note that we only consider node and not edge features for our experiments.
Table S.2: Summary of the graph datasets considered for our experiments.
dataset
library # classes
# node features
# graphs
# nodes
avg # edges
MUTAG
TUDataset
2
no
18
40
Enzymes
TUDatasct
6
18
600
33
62
COX2
DuDataset
2
3
467
41
44
DHFR
TUDataset
2
756
42
45
IMDB-B
TUDataset
2
1000
20
97
IMDB-M
TUDataset
3
no
1500
13
65
AIDS
TUDataset
2
4
2000
15
16
Proteins
TUDataset
2
29
1113
39
72
Mutagenicity
TUDataset
2
no
4337
30
31
NCII
TUDatasct
2
no
4110
30
32
NCT109
TUDataset
2
no
4127
30
32
OGBG-MOLHIV
OGB
2
9
41127
25
27
BZR
TUDataset
2
3
405
36
38
BZR MD
TUDatasct
2
no
306
225
COX2 MD
TUDataset
2
no
303
335
DHER MD
TUDataset
2
no
393
283
ER_MD
TUDataset
2
no
446
235
OGBG-MOIESOL
OGB
regression
1128
13
OGRG-MOIFREESOU
OGB
regression
642
9
OGBG-MOLLIPO
OGB
regression
4200
27
30
C.3 Magnitude and Spread Computations
Across our experiments, we compute magnitude and spread outlined in the main text, implemented in our code submission, and further described in Appendix C.I. Elaborating on these descriptions, we now aim to give an extended explanation of practical and theoretical considerations for computing the magnitude of graphs in practice.
Defining the magnitude of a graph. In mathematical literature, the magnitude of graphs is often studied with the shortest path metric [38]. However, shortest path distances are not guaranteed to be of negative type, thus leading to scenarios and well-known examples for which the similarity matrix is not invertible and magnitude based on this metric cannot be computed [37]. In comparison, resistance distances, diffusion distances, or Fuclidean distance always permit the computation of magnitude. Because of this difference in the choice of distance metric, we note that our definition of the magnitude of a graph in Section 2.2 differs from the definition used by Leinster [38]. While we choose investigate diffusion distances, note that the distance metric can easily be replaced if needed to explore alternative geometries.
Diffusion geometry. For further research, we believe that the usage of diffusion distances offers the chance to leverage a rich theory on approximation methods via landmarks [42], or localised diffusion computations [16], which can lead to further computational improvements and extension of our methods.
Magnitude and spread multi-scale functions. Note that magnitude and spread can also be defined as multi-scale functions i.e. f - Mag((X,1. dd) for a metric space (X, d) and a scale parameter& E IR+ This parameter can be likened choosing kernel bandwidth or the scale of distances or similarity determining when observations are considered to be distinct. In practical applications, is advisable carefully consider the choice of scaling factor or the type of normal- isation used to compare distances [40]. Limbeck et al. [40] propose a heuristic that uses root- root-finding to find suitably large t. However, this requires repeated computations of magnitude and increases the computational costs. A faster and more desirable default choice of would be based solely on the distance metric. For distances that are not otherwise scaled or normalised, we therefore recommend the usage of faster heuristics, such as the median heuristic for choosing the -andwibhn i.e. the scale parameter [29]. For diffusion distances, we find that setting = 1 is sufficient for our goals. This is because, as discussed in Section 2.3, diffusion distances computed from the normalised
29

---

graph Laplacians and are inherently comparable across graphs. Nevertheless, investigating magnitude and spread multi-scale functions on graphs remains an interesting extension for further work.
Magnitude and spread as diversity measures. We extensively discuss the relationship between magnitude and spread throughout our work. However, our main paper does not have the space to fully explain the theoretical motivations behind the formulations of magnitude, spread, and other generalised measures of diversity. For a more complete discussion we refer the interested reader to Leinster [39], an extensive reference work on the mathematical motivation behind entropy and diversity. Furthermore, Willerton [52] specifically discusses the spread of metric space, and Limbeck al. [40] describe the practical usage of magnitude give descriptions on how and why the magnitude or spread of metric space can be interpreted as an effective size i.c. the effective number of distinct points in a metric space the number of dissimilar nodes graph.
diversity measure in ML. These works also
C.4 Pooling Algorithm
We now detail our pooling algorithm introduced in Section 3.1 by describing pseudocode imple- mentation. Note that to describe the algorithm we assume we have pre-selected a distance metric for computing either magnitude or spread.
Algorithm 1 Graph Pooling Methods: SpreadEdgePool and MagEdgePool
Require: input graph
EX, E), node features F g|xXx,, pooling ratio (0, 1], diversity measure Mag(G) (G) or Sp(G)
Ensure: Pooled graph G" (X', E"), pooled features F
1: Initialise the super-node set S(x) < for all x E X
2: Initialise the of edges adjacent contracted edge E. +
3: Initialise the pooled graph G' +
4: Compute initial edge scores:
s(e) Mag((G) Mag(G/e)) Ve E
5: while |X| + [r|X]] AND E + 0 do
6:
Select edge (I,y) arg min,e E E. s(e)
7:
if is not adjacent to any previously contracted edge in E, then Contract edge e, update G' +- G' /c
8:
Add and any edges adjacent to to E, 10: Update the node selection: merge S(x) and S(y)
9:
11: end if
12: if more valid edges AND pooling ratio not reached then
13: Recompute the edge scores s()) on the updated graph G' Reset E, 0
15: end if
end while
17:
Initialize F" + 0
for each noder-node representative do
19: Let S. = {a E X S(x) w}
Compute the aggregated features:
F
F
S
W..S
Append F' F'
22: end for
23: return Pooled graph G", pooled features
30

---

C.5 Extended Experimental Details
We briefly describe extended details on the experimental setup used for our main experiments.
C.5.1 Overview Experiment
To create the illustration in Figure I and visually compare the outputs of different pooling methods, we follow the experimental setup by Grattarola et al. [32] on understanding structure preservation in graph pooling layers. Specifically, we simulate ring graph with 64 nodes, a barbell graph with 20 nodes on each side connected by 24 nodes in the middle, and sensor graph with 64 nodes. Graphs are then pooled to pooling ratio of approximately 50%. Because some pooling methods (e.g. Graclus or NDP) do not give exact control over the number of vertices, but pool graphs to approximately half of their original size, the number of nodes visualised in Figure 1 can vary across methods. All trainable pooling layers were then trained in a self-supervised manner to optimise the following spectral loss between the original graph G and the pooled graph G":
[(G,G") = Σ LT -.TT--FTLLR L'F.
(14)
where L, L' are the corresponding Laplacian matrices. The features are taken to be the top 10 eigenvectors of L concatenated with the coordinates of the nodes in G. F is the reduced version of F after pooling. Note that this type of spectral loss is one particular proposal on structure preservation and alternative objectives could be investigated.
C.5.2 Structure Preservation Experiment and Pooling Ratios
For reporting the structure preservation results described in Section 4.2, we considered multiple different proposals for what means to preserve graph structure during pooling. the end, we settled to compare the spectral distance between the symmetrically normalised graph Laplacians as an established measure spectral property preservation, and investigated the relative difference in magnitude between the original graph G and the pooled graph G" computed from diffusion distances. Specifically, the reported relative magnitude difference is calculated as
MagDiff G*) [Ma((G) Mag(G")
(15)
Mag(G)
For this experiment we further vary the pooling ratios across different pooling methods. However, some of the pooling layers considered in our study (NDP, Graclus and NMF) were configured to always pool graphs to around half their size. To allow to compare these methods across increasing pooling ratios, we choose to reapply these pooling operations repeatedly, which is why these three pooling methods are evaluated at pooling ratios that are powers of 0.5.
C.5.3 Graph Classification Experiment
Our graph classification architecture follows the experimental setup described in Section 4.1 and is based the benchmark by Grattarola al. [32]. Across our main classification experiment detailed in Section 4.1, different pooling layers are configured to reduce each input graph to around 50% of the number of nodes in the original graphs. Depending
the pooling method, this is chosen so each graph is reduced to 50% of its original size k = [0.5 * N1. (for NDP, Graclus, MagEdgePool SpreadEdgePool, TookPool, and SAGPool), or 50% the average size of all graphs the training dataset & = [0.5 * N] (for DiffPool, and MinCutPool). Interpreting the experimental results in Table is thus of interest that the sizes of the pooled graphs can vary across pooling layers, which might explain some of the difference in performance between the fixed-sia size methods DiffPool and MinCUT compared to more adaptive pooling methods.
C.5.4 Graph Regression
As further ablation study, we aim to assess whether the results reported in Table I for graph classification tasks remain consistent for further graph regression tasks. To this end, we use three molecular datasets from the OGB benchmark with their predefined test, training, and validation
31

---

splits [33]. Further, we adjust the GNN architecture described in Section 4.1 and Appendix C.5.3 to use the MSE as training loss, the RMSE for performance evaluation, linear final activation for the readout MLP, an early stopping patience of 100 epochs, and blocks of two convolutional layers instead of single layers. Similar to before, we only use node features as inputs. Note that stronger, domain-speciffe and purpose- built models exist for molecular regression tasks that utilise both atom and bond information [33]. Hence, our goal is not to reach state of the art performance. Rather, we aim to compare the performance of different pooling layers and evaluate the information loss due to the pooling operations themselves. Finally, Table 2 reports the RMSE on the test dataset across ten repeats using varying random seeds.
D Extended Results
Finally, we summarise extended experimental results beyond the scope of our main paper.
D.1 Correlation between Magnitude and Spread
As stated in Section 2.2, the magnitude and spread of a metric space are closely related with magnitude giving upper bound for spread when computed from the same positive definite metric space. Across our experiments on real graph datasets, we further find that this bound in practice can be very tight and magnitude and spread measure very related notions of effective size. More specifically, when computing both magnitude and spread from the diffusion distances detailed in Section 2.3, we observe that magnitude and spread almost coincide for all graphs from the NCII, ENZYME or IMDB-Multi datasets as illustrated in Figure S.I. In fact, magnitude and spread correlate almost perfectly across these three graph datasets (Pearson correlation r² 2 0.99). Further, we confirm that across these examples, magnitude is generally greater or equal to spread by relatively low multiplicative factor close to 1. We therefore find empirical evidence for the fact that spread offers valid and highly related alternative to magnitude in practice supporting our theoretical analysis of the relationship between spread and magnitude during pooling (Appendix B.3) as well as our observations on the similar performance of MagEdgePool and SpreadFdgePool.
Magnitude vs. Spread NCI1
Magnitude Spread ENZYMES
Magnitude vs. Spread IMDB-MULTI
140
120
250
200
100
200
150-
80
spread
spread
150
60
100
100
40-
20
50
0-
100
50
100
150
200
megnitude
magnitude
magnitude
Magnitude Spread NCI1
Magnitude vs. Spread ENZYMES
Magnitude Spread IMDB-MULTI
5020
35.0
50:00
number gragen
3000
sumber of STRPT
40000-
25:00
2000
20:00
1500-
2000
1000-
30000
500
1,02
1.35
Li0
ais
Figure S.1: Comparison between magnitude and spread computed from diffusion distances for all graphs in three graph datasets, NCI1, ENZYMES and MMDB-Multi.
32

---

D.2 Evaluating Computational Efficiency
As detailed in Appendix B.2, the computational costs of our algorithm are determined by the costs of computing the edge scores used for pooling. To illustrate how this theoretical discussion translates into practice, we now investigate computational costs empirically in comparison to alternative pooling methods considered throughout this study.
D.2.1 Training Costs
We first compare the runtime (in seconds) and memory usage (in MB per cross-validation run) of our pooling methods (MagFdgePool and SpreadEdgePPoo) to trainable pooling methods in Table S.3. Specifically, we train the GNN architecture specified in Appendix C.5.3 and Section 4.1 using GIN layers across 200 epochs using 10-fold stratified cross-validation. We compare our edge pooling methods (MagEdgePool, SpreadEdgePPoo) to trainable pooling methods from (EdgePool, PopKPool. SAGPool) or from torch wati--gemetrii--o -pool (DiffPool, MinCutPool), We record the mean and standard deviation of the runtimes in seconds in Table S.3 and GPU memory usage in MB per cross- volssavaii run in Table S.4. We note, in particular, that our proposed edge pooling methods, MagEdgePood and SpreadEdgePool, allow for significantly more efficient GNN training than EdgePool as highlighted in Table S.3. Similarly, our methods generally improve on the runtimes for dense pooling methods such as DiffPool and MinCutPool. To generalise this runtime comparison to other datasets sizes and experimental setups, we note that our algorithm will scale with dataset size as described in Appendix B.2.
D.2.2 Pre-training Costs
Having observed that pre-computed edge-pooling speeds up GNN training times, we further investig- ate the computational costs of this preprocessing step by comparing the runtime and memory costs of our methods against other non-trainable pooling operators (NDP, NMF and Graclus) prior training. Table S.5 and Table S.6 report the computational costs of computing the pooling assignment for all graphs in the datasets. We observe that SpreadEdgePool is generally more efficient than MagEdge- Pool. Beyond exact computations of our pooling methods (described in Appendix C.4), Table S.5 and Table S.6 also present upproximate versions that reduce the cost of distance computations. Spe- cifically, these approximate versions, referred to MagldgePool** and SpreadEdgePPolf use the minimum distance the original nodes to update the (diffusion) distances during edge contraction. This leads to a considerable improvement in runtime and memory usage during pre-training. The results reported in this section highlight one the limitations of our edge pooling approach, namely, it scales in the number of edges well as in the number of nodes as detailed in Appendix B.2. Nevertheless, our proposed pooling methods still outperform EdgePool in terms of computational efficiency when considering both pre-processing and training costs.
Furthermore, the pre-training costs of our method, range in a number of seconds, need be computed only once per dataset and the memory requirements remain below what is required by GNN training, Hence, while the scalability to very large graphs a limitation, we find that our proposed pooling methods scale sufficiently well to standard graph datasets. In practice, based on the computational complexity (Appendix B.2), we recommend that our pooling method is particularly suitable for small to medium graphs that show a certain degree of sparsity rather than being fully connected. As visualised in Appendix D.2.2, graphs with up to few hundred nodes can feasibly be processed with our method in matter of seconds. For future work, we believe that there is strong potential for adapting our methods to scale on large graphs. For instance, edge score calculations could be parallised, sampling heuristics could restrict the edge score computations to subset of candidate edges, or edge scores could be estimated from local subgraphs to improve the computations.
D.2.3 Runtimes across Pooling Ratios
Further, we compare the runtimes of training the models used in Section 4.3 to compare the accuracy of different pooling methods across varying pooling ratios. Appendix D.2.3 then reports the mean runtime of training the GNN one CV-fold for different choices of pooling ratios and pooling
http://ppoorrcgggmmme.......o wwwdeeeeeeeee....reeeeeeeeeeee.. htwpattheoocs..o/////teeeeeee available under an MIT license [26.
27].
:htttps//gitthbb hatpabb.ccommtgttee//tooooo htt.://orrccceemmmmmir----oooooo available under an MIT license.
33

---

Table S.3: Training times in seconds compared across pooling methods. The fastest methods are
marked in bold.
Method
DHER
ENZYMES
NCT109
Mutagenicity
IMDB-BINARY
IMDE-MULTI
MagEdge
6.0
22.0
186.0
180.3
75.4
89.6 6.1
SdreadEdge
34.8
0.7
181.3 29.4
206.7 20.6
62.7 0.9
99.7 + 4.3
EdgePool
184.1 + 4.0
20.
790.7 22.1
362.3 3.4
392.7 11.9
TopKPool
50.7 0.8
226.1 2..1
243.8 = 15.4
88.2
110.9 - 2.2
SAGPool
54.4
2.47
2
253.0 20.0
92.6
131.1 1.3
DiffPool
6.8
3..4333
242
274.0 21.5
106.7 +
74,9 + 2.0
MinCut
33.
28.2
201.0
93.2 1.6
132.8 = 3.2
Table S.4: Memory usage in MB compared across pooling methods. The most efficient methods are
marked in bold.
Method
DHER
ENZYMES
NCI109
Mutagenicity
IMDB-BINARY
IMDB-MULTI
MagEdge
84.0 # 0.1
91.2 = 2.5
97.0 = 1.1
94.8 = 1.0 95.2 = 1.0
283.4 28.0
197.6 # 17.8
SpreadEdge
84.0 + 0.1
90.6 # 2.3
96.8 = 1.0
283.4 28.0
197.4 17.8
EdgePool
125.6 10.4
15.0
118.6 7.7
118.0
666.6 + 106.6
526.2 89.2
TopKPool
9.0
1 9..4
1.5
273,4 259.4
193.8 17.5
SAGPool
0.6
= 9..2
8.1
209.0 # 17.9
DifIPol
90.2 10.2
2.56
103.8 = 1.1
299.8 + 31.9
258.0 = 40.3
240.8 26.4
MinCut
90.6 10.3
9.4
103.6 + 1.0
288.4 38.3
258.0 + 40.3
196.6 26.0
Table S.5: Pre-training times in seconds compared across non-trainable pooling methods. The fastest
method is marked bold. The fastest approximation of our pooling method is marked in italics.
Method
DHER
ENZYMES
NC1109
Mutagenicity
IMDE-BINARY IMDB-MULTI
MagEdge 61.9
197.4
4765.1
678.8
801.8
480.2
MagEdge*
24.6
21.0
81.3
74.9
77.4
69.9
SdreadEdge
66.7
68.3
316.1
208.8
287.2
243.8
SpreadEdge*
10.9
16.0
52.3
55.6
56.0
66.0
NDP
5.6
4.1
37.1
32.6
5.8
7.0
NMF
7.8
10.8
39.0
32.1
8.7
9.0
Graclus
3.8
2.9
54.5
18.2
4.5
6.0
Table S.6: Pre-training memory usage MB compared across non-trainable pooling methods. The most efficient method is marked in bold. The most efficient approximation of our pooling method is marked in italics.
Method
DHER
ENZYMES
NC1109
Mutagenicity
IMDE-BINARY
IMDB-MULTI
MagEdgePool
76.2
163.8
158.9
179.0
162.1
93.1
Pogoogeooof
83.7
34.8
47,0
72.2
11.5
65.2
SpreadEdgePool
61.9
60.1
177.9
204.1
75.8
SpreadEdgePool
33.6
54.1
60.5
72.9
53.2
23.8
NDP
3.0
5.0
7.0
13.4
5.1
6.5
NMF
3.8
5.9
39.9
10.5
4.2
5.9
Graclus
15.8
7.5
17.5
59.5
1.0
1.5
methods for the NCII dataset using either general convolutional layers or GIN layers. All models are trained as specified in Section 4.1 on a single GPU with 32 GB memory. Notably, we observe that MagEdgePool and SpreadEdgePool overall perform on par with alternative pooling methods in terms of runtimes. SpreadEdgePool has consistent advantage over MagEdgePool due to the higher computational efficiency of computing spread rather than magnitude. Notice that for increasing pooling ratios. our algorithm re-computes the edge scores repeatedly, leading to less pronounced decrease in computational costs than alternative methods. Nevertheless, we conclude that it generally more efficient to apply SpreadEdgePPoo than to rely on trainable approaches, such as TopK and SAGPool for this dataset, indicating the computational benefit of non-trainable graph pooling operations.
34

---

Rarniime Graph
Hemoay vs. Graph size
150
Pepoopetce PayCopalter
Migh Spenad
50
Magh dipenio
Soroedoil woveddilpptoot
Pot mummun
130
2.33
350
400
100
Figure S.2: Runtime and memory costs of computing the pooling assignment for Erdös-Rényi graphs with edge probability 0.005 for increasing numbers of nodes. Lines show the mean and shaded areas the standard deviation across five repeats. SpreadEdgePool is notably faster than MagEdgePool. Distance approximations (marked with *) further speed up computations.
520
532
458-
420-
Method
MagEdgePool
350
SpreadEdgeePol
930
322
NDP
230
258
TopK
Graclus
230-
278
SAGPool
150-
158
130
130
0.8
0.2
0.8
0.2
pool ng rallo
pooting rall
Figure S.3: Runtime comparison for training the GNNs reported in Section 4.1 for NCI1 using different pooling layers. Plots show the mean time in seconds per run using general convolutional layers (left) GIN layers (right).
D.3 Node Feature Preservation and Expressivity
Graph pooling should not only preserve graph structure, but also preserve relevant node feature information during pooling. That is, pooling is frequently used after initial rounds of message passing and data representations learnt by previous layers should be respected and effectively encoded by the pooling procedure [32]. One way of investigating node feature retention during pooling, is to evaluate how well a graph can be reconstructed from its pooled version. We follow the experimental setup by Grattarola et al. [32] to investigate. In particular, this experiment uses model architecture, similar the model proposed in Section 4.1, where each graph gets pooled to around 50% of nodes after the initial MLP and GNN layer. Then, the pooled graphs are up-scaled again by reversing the node selection step used by each pooling layer. From these unpooled graph representations, further GNN and proc-proesssing MLP layer are trained and the task is set to output the reconstructed node feature representation. This model is trained on each example graph using Adam to minimize the mean squared error (MSE) between the input and output node features with a learning rate of 0.0005 and early stopping on the training loss with a patience of 1000 epochs and a tolerance 10-6, Each experiment is repeated three times across different random seeds. See Grattarola et al. [32] for further explanations on the model architecture and experimental setup.
For this experiment, we expect SpreadEdgePool to perform comparably well as we specifically designed our pooling algorithm so that features are averaged during pooling. Further restricting the number of times node can be merged effectively prevents the collapse of entire portions of the graph, which aids reconstruction. SpreadEdgePool pooling thus successfully encodes node information while allowing for a flexible choice of pooling ratio. This is confirmed by the results in Table S.7, which highlight that SpreadEdgePPol overall performs well at the features reconstruction task, especially for the sensor graph reaching low reconstruction errors. Alternative methods, in particular node drop approaches such as TopK and SAGPool, show notably worse feature preservation during this experiment indicating the benefits of more expressive pooling operations, such as SpreadEdgePool.
35

---

Table S.7: Mean and standard deviation of the reconstruction MSE for reconstructing the original node positions from the pooled graph representations for different example graphs and pooling methods. Our proposed algorithm, SpreradEdgePooo, does well at faithfully encoding the feature representations.
Ring
Sensor
Barbell
Community
ExdGs-Réayi
Torus
SpreadEdge
0.47e-07 a 2.63e-07
2.78c-05 a: 3.04e-07
3.42e-04 1.42e 06
3.71e-03 a 5.80e-05
6.49e-07 3.333e-
5:29c-07 à: 1.33e 07
NDP
3,08e 0.57e-07
4.07e-05 a: 4.57c-06
4.54p-04 2:00::05
2.52e-01 a 9,50e-06
1.46e 06
0.18e-06
5.68-077
1.02;-07
Gradus
6.87c-01
7.56e-07
2.67c-06
-.316-06
1.82-00 3.22
2-42++00
4.76e-02 1.775e-77
7.10-07 8.60-00
NMP
4.78c-07 0.95
1.96-005
1.39--05
5.80c-04 4.533-07
6.06e-01 1 1.43-004
5.04c077 1 3.31e-07
2.50c-07
2.933-007
Topk
1.21c-01 8.23e-05
583e-45
+ 2.166-433
1.55e-02 = 1.100-402
6.1330400 + 2.21e400
5.300-43 + 4.45--55
1.72c-011 +.5.1e-41
SAGPool
1446-001 2.522-02
2.0ee413 + 2.7 2.73e-03
1222-022 44 18s-02
4.76ex000 1.57es00
9.600-455 + 1.35e-04
1.88-001
4.663--02
DiffPool
8.63e + 4.73e-06
3,50e-04
8.30e-05
6.50e-04 1.
2.14c
2.84e-01
3.74c-04
1.46--44
5.17e-05
8:900-06
2.55c 2.68c-05
6.56e-06 3.56c-06
2.35e-06 a 1.50e006
2.0
1.4e-06 5.22ee-7
1.49-066 9.81e-00
Magritude Difference
Normalised Spectral Difference
Spectral Loss
MagEdgaPool-
0.4 a
05 0.0 0.2 0.0
MagttSyehenl
-4.5 0.0
5a 0.1
6,9
0.0
MagEdguPool
0.1 6.0 0.1 0.0 0.4 0.0
Spreadfidge/eull
84
0.0
SpreadEdgePoll
44.5
521
SpreadEdgefcall
0.0
0.0 0.1
NDP
NDP
0.0
0.1
0.0
Graclus
Grarlus
5.9 0.1
5.4 0.2
5.1 0.
Grackus
1.0000
NMF
6.0
2.1 02
La
NMF
0.0
0.0
NMF 12 17.1
22.66.1
Thpk TMnK--10.771
1.7
1.2
42 0.2
Tops
Tapk 0.1 6.0. 0.3
0.0
1.1 0.0
SAGPoo!
37.
6.6
0.1
SAGPool
5.1 0.0
5.4 0.0
0.1
SAGRool 0.0 0.0 0.2
0.0
0.0 0.8
DefRcol
0.0
DffPPool
4.9
5.4 0.0
5 0.0
Offfcel 0.0
MinCut
MinCut
4.8
5.2
MinCut 0.0
0.2.0000
Ring
barbell
Sensor
Ring
barbal
Senger
Ring
barbell
Sensor
Figure S.4: Structure preservation measures for the examples in Figure 1. Pooling is repeated for three different random seeds and the annotations report the means and standard deviations of the structure preservation scores.
Note that the results in Table S.7 capture one specific aspect of feature preservation, namely how well the features of specific example graphs can be reconstructed. This experiment does not assess the generalisation capability of pooling layers. Further, the experimental setup assumes that it relevant to preserve all node features during pooling, which might not be realistic in practice, where the aim of pooling could be to solely encode task-relevant feature representations. Nevertheless, as discussed above, this extended experiment gives evidence support that our proposed pooling algorithm, SpreadEdgePool. is capable outputting expressive feature representations and aggregates node features in faithful manner, which is likely one of the reasons for its high performance in graph classification tasks.
D.4 Overview Experiment
Expanding on the qualitative comparison between the example graphs in Figure 1, Figure S.4 shows quantitative structure preservation measures for all example graphs and pooling methods. Specifically, we summarise the spectral loss by Grattarola et al. [32], the spectral distance between the normalised graph Laplacians, and the magnitude difference between the pooled and original graphs as further detailed in Section 4.2.
Figure S.4 demonstrates that SpreadFiggPPool and MagEdgePool do not only reach low magnitude differences across these three example graphs, they also show comparatively low spectral distances supporting our findings in Section 4.2. Further, observe that methods that show worse visual preservation of graph structures, such as NMF, TopK, DiftPool, and MinCut, also reach consistently higher magnitude differences and spectral distances supporting our claim that these methods fail to faithfully preserve graph structures during pooling to varying extents.
D.S
Graph Classification
Table S.8 further reports extended classification results on additional datasets extending on the results shown in Table 1. We chose not to report on these datasets the main text because they showed fewer and less notable differences between pooling methods. Note that for the open graph benchmark MolHIV dataset, instead of using stratified cross-validation, we evaluate each model across predefined training, test and validation splits and evaluate their performance across 5 random seeds. Further,
36

---

Table S.8: Classification performance different pooling layers across multiple datasets. For each dataset, the best performing model is marked in bold and models that do not perform significantly different from the best performing model are coloured green.
Method
MolHTV (AUROC)
MUTAG
COX2
BZR
BZR MD
COX2_MD
DHFR_MD
ER_MD
AIDS
Pooling
0.74
81.6
+ 388
76.1 9.1
53
71.3+11 19
74
990
MagEdge
64.6
7.4
10.0
6.
76.5
2..9
7.
9
SprendEdge
2.
7.4
87.4+
69.7
10.0
9.01
74.6 11.1
83.1
99.7
NDP
6..2173
86.1 24
8633194
12.
73.9 10.6
72.2 11:4
8.
9.
Gracuus
5..3
9.54
7 12.5
80.1
72.0
7..4
71.1 12.3
S1.7
9..
NMF
1.3
9.4
8.78
8
69.0 10.2
1.66
8.8
80.9
1.7
Topk
7.08
6.5
6..5
74.0+1.0
0.1
SAGPool
24.3
2.3
7
5.0
7.0
6.4
2.65
7
99.0
DiffPool
1.0
83.3
76.9 6.5
76.8 + 10.1
3..
0.1
2,69
73.4 1.1
9.2
MinCat
3.03
1.41
70.0
73.31:16
9.2
report AUROC the performance metric for MolHIV because is the suggested evaluation metric for this very imbalanced dataset. All other results are reported as in Table via the mean and standard deviation of the test accuracy across 10-fold stratified cross-validation. In agreement with our main results, we observe that MagEdgePool and SpreadEdgePool constitute high performing general-purposs pooling methods that reach top performance across these extended datasets. In particular, for smaller biological datasets, such as MUTAG, BZR, or COX2, pooling via magnitude or spread notably improves on the GNN that uses no pooling layer, which indicates the beneficial effects of structure- pooling for graph learning.
In order to further clarify the classification performance comparison between methods visualise the ranking of each model choice via a critical difference diagram. This visualisation uses the Friedman test, non-parametric test for the performance difference between multiple classifiers with repeat measurements, followed by the Nemenyi post-hoc test that facilitates the comparison across all classifiers [17]. In our case, we use the Python package scikit- talkit-posthoce [50] to apply this test to the mean performance scores across datasets. The critical difference plot then links all methods that are found not be statistically different by horizontal bar. The results reported in Figure S.5 confirm that our methods are amongst the best- bert-performing group of pooling layers for the datasets reported in Table 1. Similarly, Figure S.6 shows the critical difference diagram and mean ranks across all tasks included in Table or Table S.8. This extended ranking further strengthens our finding that MagEdgePool and SpreadEdgePPon reach top performance across classification tasks.
dagEdge (2.4)
(7.8) DifiPool
SpreadEdge (3)
MinCut
NDP
SAGPool (4.2)
(5.1) Topic
(.88) Graclus
Figure S.5: Critical difference diagram for the classification results from Table 1. Each label
corresponds choice of pooling method and the method's mean rank across classification tasks. Groups of methods that are found to not be statistically different are linked by horizontal bars.
SpreadE (2.9)
DifiPooll
MagE:
HDP (5.5)
6.21 Took
Graclus (4.3)
5.6) NMF
5.33) SAGPool
Figure S.6: Critical difference diagram for the classification results from Table and Table S.8. Each label corresponds to choice of pooling method and the method's 's mean rank across classification tasks, Groups of methods that are found to not be statistically different are linked by horizontal bars.
37

---

Table S.9: Mean and standard deviation of the graph classification aceuracy of different pooling methods across datasets.
Method
ENZYMES
PROTEINS
Mutagenicity
DHER
IMDR-B
IMDR-M
NCTI
NCT109
No Pooling
2.5
2.8
7 1.9
69.7 0.7
4.7
76.5
2.0
MagEdge
9..
76.4
2.7
88.0
72.4 1.7
1.7
12
7.30
SdreadEdge
92.8 1.6
7.6 3.11
7.00400
90.7
718
4.7
23
7188
EdgePuol
92.1 +
3.1
83.2+
7..9
4.3
71.9
2.6
Randou
8..1
1.
2.11
82.1
70.1 0.7
4..6
71.1
6.0
D.6 Comparison with EdgePool
To extend our evaluation, we compare with the gytorch_geomette implementation of Edge- Pool [20, 21J. To do so, we implement the GNN architecture specified in Section 4.1 in PyTorch and repeat our main experiment reported in Table 1. We find that there is no significant difference in performance between our methods and EdgePool when computed on e.g. IMDB-M, where EdgePool reaches an accuracy of 47.6 = 3.3,
IMDB-B, B, where EdgePool reaches accuracy of 70.9 + 4.5, As further reported in Table S.9, similar patterns hold across datasets with our proposed pooling methods reaching comparable accuracies to EdgePool across datasets. As major advantage, our methods have notably lower computational costs during training than EdgePool as reported in Appendix D.2 and permit choosing flexible pooling ratios. Our methods thus make cige-coontaction pooling scalable to larger datasets and enable significantly faster GNN training. On IMDB-B for example, EdgePool takes 362.2 seconds and 666.6 MB for 200 epochs during training, but our method SpreadEdgePool only requires 62.7 seconds and 283.4 MB. We thus find that learning feature-based edge scores as done by EdgePool. not necessary to ensure classification performance, but rather adds a notable computational burden.
D.7 Comparison with Randomised Pooling
Research by Mesquita et al. [44] has demonstrated that randomised ablations of Graclus and DiffPool using random cluster assignment can reach competitive performance to established pooling methods on frequently used graph classification datasets, such IMDB-B, PROTEINS. NCI109, DD and MOLHIV. Questioning standard assumptions of hierarchical pooling methods, Mesquita et al. [44] thus question the utility of localised graph pooling. We find that this discussion and the observations by Mesquita et al. [44] are closely connected to the following challenges:
Graph learning tasks do not necessarily need the graph structure to reach high performance [7, 15]. Evaluating the performance of pooling layers is dependent on the specific GNN architecture and benchmarking practices used [24, 44].
Randomised modifications of expressive pooling operators can retain the expressivity of the underlying pooling operation [8].
Hence, if all task-relevant information is already captured by the learnt features before pooling, randomised baselines can reach competitive performance. Nevertheless, destroying the structure of graphs during pooling can reduce the effectiveness of preceding sessaag-passingg layers [8]. Our pooling approach aims to mitigate this risk by presenting geometry-awant and expressive edge-pooling methods.
As an ablation study, we add randomised edge pooling to our main experiment (cf. Table 1) by randomly merging pairs of nodes into super-nodes to pre-compute the pooling assignment and averaging their features during training. We find that for NCT109 randomised pooling reaches an accuracy of 68.0 + 3.0 as compared 71.8 + 1.8 for SpreadEdgePool. On NCII random pooling reaches an accuracy of 71.1 + 2.2 compared to 73.4 + 2.5 for SpreadEdgePool. Thus, the random baseline performs worse than any alternative pooling method on NC1109 and decreases the accuracy on NCI1 slightly. We hypothesise that this decrease is due to graph structure being relevant for these learning tasks [15] and our pooling method better preserves structural properties. In contrast, we observe fewer performance differences for other standard datasets, such as ENZYMES, PROTEINS, IMDB-B, or IMDB-M. This confirms the findings by Coupette et al. [15] that on these datasets GNNs can reach competitive accuracies even when using completely randomised adjacencies as inputs. We thus find that an expressive aggregation of the node features during pooling can suffice [8] and preserving graph structure might not be necessary for solving these tasks to begin with.
38

---

D.8 Preserving Graph Structure
Extending on the results reported in Figure and Section 4.2, we further report the distribution of structure preservation measures across pooling ratios. Specifically, Figure S.8 shows line plots that summarise the mean magnitude difference relative to the original graph and the normalised spectral distance between all original and pooled graphs from the NCI1 dataset in the leftmost column. The remaining plots illustrate the quantiles of the same measures split up per pooling method. Overall, these individual plots support our assessment that MagEdgePool and SpreadEdgePPoo consistently reach low magnitude differences and comparably low spectral distances, with these trends being more pronounced in terms of the relative difference in magnitude after pooling. Further, we repeat the experiment reported in Figure for further datasets, specifically for DHFR, PROTEINS, and ENZYMES and summarise the results in Figure S.7. We observe consistent trends across these examples that support the results reported for NCII in Figure 3. Specifically we find that our proposed pooling methods, MagEdgePool and SPreadEdgePool. reach the lowest magnitude differences across pooling ratios and datasets, and that this corresponds to low spectral distances between the pooled and original graphs.
hormaloed Spactral Ebttanee BizNEE
Socdne Ditance for Eienees
Moon tude Differecce 9KZYMES
Paay Rade Offenea ENEING
30-
pedingmetc
Seoting tedo
Normallaed Spectrul Diitanos Ders
Npetto Dettare rewn
02
CA
Spediaal Desance MOOTERS
PROTEnS_
0.4 0.4
0.2
Figure S.7: Structure preservation for all graphs in the ENZYMES, DHFR, and PROTEINS datasets across pooling ratios. Left: The spectral distance between the normalised Laplacians of the original and the pooled graphs. Right: The relative difference in magnitude, summarising proportional differences in structural diversity after pooling. Violin plots show the variability across graphs at pooling ratio 0.5.
Spectral Distance
MagEdgoPool
SpeeodEdgeFool
NDP
Dradiu
Topk
SAGPool
Magritude Difference
Figure S.8: Structure preservation for the NCT1 dataset across pooling ratios. Top row: The spectral distance between the original and pooled graphs. Bottom row: The relative difference in magnitude. Bold lines show the mean values of each score across graphs and thin lines the 10% 25% 75% and 90% quantiles.
39


Reviews:
[{"review_id": "k1J8u3iY2y", "reviewer": "Reviewer_7pUv", "summary": "This paper proposes a novel structure-aware edge-pooling method that reduces the size of input graphs by collapsing redundant edges. The authors view a graph as a metric space (with a clever choice of metric) and use the mathematical concept of magnitude to measure the importance of each edge for the graph’s geometry. Furthermore, they introduce the notion of the spread of a metric space as an alternative to magnitude, offering better computational properties while also being applicable to the proposed pooling method. Both approaches demonstrate strong performance on graph classification tasks.", "questions": "1. The DHFR dataset was the single case where an expressive improvement was obtained. Do the authors have an explanation for this?\n\n2. As pointed out by the authors, Figure 3 indicates that preserving magnitude corresponds to lower spectral distances and better retention of spectral properties. Would you say this also corresponds to the lower difference between the MagEdgePool/SpreadEdgePool and No Pooling results reported in Table 1? Since Figure 3 only shows the results for the NCI1, could report the same analyses for another dataset such as DHFR?\n\n3. In general, do you have an intuition/experiment/theorem that explicitly relates the magnitude/spread (or magnitude’s difference between input and reduced graph) with the accuracy?", "limitations": "Please check \"Weaknesses\" and \"Questions\" above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The use of magnitude by the machine learning community is very recent and the authors are the first to introduce it in the context of graph learning. As far as I know, it is also the first time that the mathematical notion of spread is used in machine learning, contributing to previous (and future) works that use magnitude since it is a faster alternative.\n\n2. Presents a novel and structure-preserving form to reduce graphs.\n\n## Weaknesses:\n\n1. The authors say that EdgePool [1] is the most successful edge-based. Although they argue its major drawback of pooling graphs to half their size, there is no experimental comparison to support the superior performance of MagEdgePool/SpreadEdgePool with another edge-pooling method.\n\n2. The author cites [2] but they do not debate their argument that pooling methods (e.g GRACLUS and DIFFPOOL) are not significantly superior to baselines built upon randomized cluster assignments. A more thorough discussion and inclusion of randomized baselines in the experiments would improve the paper.\n\n3. The accuracy reported on Table 1 presents only slightly better results, i.e, the experimental results are not convincing.\n\n[1] F. Diehl. Edge contraction pooling for graph neural networks\n\n[2] Diego Mesquita, Amauri H. Souza, Samuel Kaski, Rethinking pooling in graph neural networks", "was_revised": true, "final_justification": "After the discussion, my remaining concerns are:\n\n(i) the claims of superior performance in the manuscript are overstated (c.f. comparison with EdgePool);\n\n(ii) there is a chance that this method is just as \"good\" as random pooling based on prior criticism of pooling methods --- and there is not enough evidence in this work to support otherwise.\n\nI feel (i) can be easily solved by softening the claims in this work. Furthermore, even with (ii) on the way, I appreciate the methodological novelty the method and still lean towards acceptance.", "rebuttal": "**Summary**\n\n**Extended experiments:**\n- *Comparison with EdgePool:* Extend experiments with EdgePool on IMDB-M, IMDB-B, and further datasets. Highlight runtime and memory efficiency improvements. \n- *Randomised baselines:* Add randomised edge pooling experiments (already partly reported for NCI1, NCI109). Expand to further datasets. \n- *Spectral preservation:* Reproduce Figure 3 analyses for further datasets to confirm consistent magnitude/spectral distance patterns. \n\n**Clarifications and revisions:**\n- *Positioning vs. EdgePool:* Emphasise that the main advantages are computational scalability and flexible pooling ratios, not raw accuracy gains. \n- *Accuracy interpretation:* Clarify that pooling aims at efficiency + structure preservation; contextualise improvements with stratified 10-fold CV and prior baselines. \n- *Link between magnitude/spread and accuracy:* Elaborate theoretical reasoning behind structure preservation; connect to expressivity results in existing work [3]. \n\n**Extended discussion:**\n- Add a dedicated subsection on *expressivity vs. structure preservation*. \n- Incorporate recent findings [2,3,4,6] to contextualise when structural preservation matters. \n- Discuss conditions under which randomised baselines can remain competitive, clarifying limits of structural information use. \n\n---\n\nWe thank the reviewer for the insightful and detailed questions and find they offer a great opportunity to discuss the reasons behind the robust performance of our pooling methods. \n\n> The authors say that EdgePool [1] is the most successful edge-based. Although they argue its major drawback of pooling graphs to half their size, there is no experimental comparison to support the superior performance of MagEdgePool/SpreadEdgePool with another edge-pooling method.\n\nTo extend our evaluation, we compare with the pytorch_geometric implementation of EdgePool. We find that **there is no significant difference in performance between our methods and EdgePool** when computed on e.g. IMDB-M, where EdgePool reaches an accuracy of 47.6  ± 3.3; and 70.9  ± 4.5 on IMDB-B. We expect this same pattern to hold across further datasets and will report extended results during revisions. \n\nAs a major advantage, **our methods have notably lower computational costs during training than EdgePool** (cf. the response to reviewer AV7X). Our methods thus make edge-contraction pooling scalable to larger datasets and enable significantly faster GNN training. On IMDB-B for example, EdgePool takes 362.2 seconds and 666.6 MB for 200 epochs during training, but our method SpreadEdgePool only requires 62.7 seconds and 283.4 MB. \n\nWe thus find that learning feature-based edge scores as done by EdgePool, is not necessary to ensure classification performance, but rather adds a notable computational burden. The main advantage of our pooling methods over EdgePool is thus improved scalability as well as the flexible choice of pooling ratio. \n\n> The author cites [2] but they do not debate their argument that pooling methods (e.g GRACLUS and DIFFPOOL) are not significantly superior to baselines built upon randomized cluster assignments. \n\nWe thank the reviewer for their insightful suggestion and **we will include further discussion and randomised ablations to the paper**. \n\nWe find that this discussion and the observations by [2] are closely connected to the following challenges: \nStandard graph learning **tasks do not necessarily require the graph structure to ensure high performance** [4, 6]. \nRandomised modifications of expressive pooling operators can retain the **expressivity of the underlying pooling operation** [3]. \n\nHence, if all task-relevant information is already captured by the learnt features before pooling, randomised baselines can reach competitive performance. Nevertheless, destroying the structure of graphs during pooling can hinder the effectiveness of the preceding message passing layers [3]. Our pooling approach aims to mitigate exactly this risk by presenting **geometry-aware and expressive edge-pooling methods**. \n\nAs preliminary results, we add randomised edge pooling to our main experiment reported in Table 1. We find that for NCI109 randomised edge pooling reaches an accuracy of 68.0 ± 3.0 as compared to 71.8 ± 1.8 for SpreadEdgePool. On NCI1 random edge pooling reaches an accuracy of 71.1 ± 2.2 compared to 73.4 ± 2.5 for SpreadEdgePool. Thus, the **random baseline performs worse than any alternative pooling method on NCI109** and decreases the accuracy on NCI1 slightly. We hypothesise that this decrease in accuracy is observed because graph structure is relevant for these learning tasks [4] and our pooling method better preserves structural properties. \n\n> The accuracy reported on Table 1 presents only slightly better results, i.e, the experimental results are not convincing.\n\nThe accuracies in Table 1 are computed for GNNs whose only difference is the choice of pooling layer to allow for a **comprehensive and fair comparison across pooling methods**. In this context, it is in fact a **challenging task to achieve very high performance gains solely based on the choice of pooling strategy**. We therefore argue that the goal of pooling is not necessary to beat any non-pooling baseline, but to enable more efficient training while preserving task-relevant structure or feature information. \n\nGiven we use stratified 10-fold cross validation to ensure a fair comparison, the reported accuracies are comparable to the baseline performance reported by [5] and **similar or higher than the degree of improvement reported by established pooling methods**, such as EdgePool [1]. Thus, our results show robust performance and realistic accuracy gains. \n\nWe are happy to extend our experimental setup with additional comparison partners or datasets in case the reviewer has specific suggestions. \n\n> The DHFR dataset was the single case where an expressive improvement was obtained. Do the authors have an explanation for this?\n\nDHFR most benefits from the regularising effect of structure-aware edge pooling due to two potential factors. First of all, DHFR shows structural and geometric differences between graphs representing active and inactive compounds. Our pooling method helps preserve key graph structures, such as rings and graph connectivity, during pooling as visualised in Figure 2 in our manuscript. This can aid the preceding layers’ capability to discriminate between the coarsened graphs. Second, our pooling method gives an expressive pooling operator as discussed above. Amongst other expressive operators, we hypothesise that the aggregation via edge collapse pooling might be most suitable for this task specifically.\n\n> Figure 3 indicates that preserving magnitude corresponds to lower spectral distances and better retention of spectral properties. Would you say this also corresponds to the lower difference between the MagEdgePool/SpreadEdgePool and No Pooling results reported in Table 1? Since Figure 3 only shows the results for the NCI1, could report the same analyses for another dataset such as DHFR?\n\n**Yes, we can reproduce the results from Figure 3 for other graph datasets**, such as DHFR, and will report further datasets as ablations in the revisions. The same patterns we report for NCI1 hold for other datasets in the sense that we can consistently show that MagEdgePool and SpreadEdgePool induce both low spectral distances and low differences in magnitude during pooling indicating superior preservation of the graph structure. \n\nWe argue that the more **faithful preservation of graph properties does contribute to the better performance** reported in Table 1. This is particularly relevant for classification tasks such as NCI1 that rely on the geometry of the input graph for task performance [3, 4]. \n\n> In general, do you have an intuition/experiment/theorem that explicitly relates the magnitude/spread (or magnitude’s difference between input and reduced graph) with the accuracy?\n\nThere is a strong **link between preserving magnitude/spread during pooling and preserving the graph structure** of the input graph. Magnitude can be expressed as a polynomial with variables given by the eigenvalues of the similarity matrix Z = [exp(-d(xi,xj))], which we compute from the diffusion distances d. We believe that under mild conditions small changes in the Laplacian matrix lead to small changes in the similarity matrix which then induce small spectral distances between the input and the pooled graph. We aim to analyse this relationship further in future work.        \n\nFurther, we find **theoretical links between the expressivity of pooling operators and the accuracies** reported in Table 1. Edge contraction pooling when for example using sum pooling for aggregating the features fulfills sufficient conditions laid out by [3] for preserving the expressive power of the preceding message passing layers. Thus our pooling methods fulfil theoretical guarantees for both expressive feature retention as well as graph structure preservation.\n\nWe hypothesise that structure preservation will be particularly beneficial in case labels (that is, tasks) are directly related to the structure. As recent research shows [6], this prerequisite is not necessarily given, warranting careful study. We will add an extended discussion on expressivity and structure-preservation during revisions.\n\n**References**\n\n[1] Diehl, F., et al., 2019. Towards graph pooling by edge contraction. \n\n[2] Mesquita, D., et al., 2020. Rethinking pooling in graph neural networks. \n\n[3] Bianchi, F.M. and Lachi, V., 2023. The expressive power of pooling in graph neural networks. \n\n[4] Coupette, C., et al., 2025. No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets. \n\n[5] Grattarola, D., et al., 2022. Understanding pooling in graph neural networks. \n\n[6] Bechler-Speicher, M., et al., 2024. Graph neural networks use graphs when they shouldn't."}, {"review_id": "2FOV6Fyc2i", "reviewer": "Reviewer_AV7X", "summary": "The paper \"Geometry-Aware Edge Pooling\" focuses on leveraging diffusion geometry to develop pooling layers that preserve both the metric structure and structural diversity of graphs in graph neural networks. The authors introduce two novel pooling methods, MagEdgePool and SpreadEdgePool, which outperform existing pooling layers across various graph classification tasks while retaining key spectral properties and maintaining high accuracy across different pooling ratios.", "questions": "- Is the code open-source and reproducible?\n- Can you provide more experimental results regarding the efficiency of the method?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper proposes novel pooling methods that consider graph geometry and structural diversity, leading to improved performance compared to existing approaches.\n\n- The empirical results demonstrate the superiority of MagEdgePool and SpreadEdgePool over alternative pooling layers across diverse graph classification tasks.\n\n- The paper is well-organized and easy to follow. Relevant theoretical proofs have been conducted.\n\n  \n\nWeaknesses：\n\n- The experimental results demonstrating the efficiency of the method should be presented.\n- The method becomes more challenging to apply as the size of the graph nodes increases.", "was_revised": true, "final_justification": "The authors should also address the overlooked scalability issue and enhance the analysis by comparing with global pooling methods such as SOPool and DKEPool to make the study more complete.", "rebuttal": "**Summary**\n\n**Extended experiments with preliminary results and additions:**\n- *Computational efficiency:* Evaluate runtime and memory usage across pooling methods. Report and contrast pre-training and training costs.\n- *Computational speed-ups:* Propose and benchmark approximation techniques for estimating diffusion distances to speed up graph pooling.\n\n\n**Extended discussion:**\n- *Computational efficiency:* Discuss further strategies for ensuring computational scalability. \n- *Reproducibility and usability:* Include details on the reproducibility and open-source implementation of our pooling method.\n\n---\n\n\nWe thank the reviewer for their positive feedback and concrete questions, which we are happy to address. Specifically, we are thankful for the review highlighting the rigorous mathematical and theoretical grounding and strong performance of our proposed pooling method. \n\n\n> Can you provide more experimental results regarding the efficiency of the method?\n\nWe will include **extended runtime and memory comparisons** in our revisions and want to present experimental results on the computational efficiency of our pooling method. Specifically, we train the GNN architecture specified in our manuscript using GIN layers across 200 epochs using 10-fold stratified cross-validation. We compare our edge pooling methods (MagEdgePool , SpreadEdgePool ) to trainable pooling methods from torch_geometric (EdgePool, TopKPool, SAGPool) or from torch-geometric-pool (DiffPool, MinCutPool). We record the mean and standard deviation of the runtimes in seconds and GPU memory usage in MB per cross-validation run.\n\nWe note that in particular our proposed edge pooling methods **MagEdgePool and SpreadEdgePool allow for significantly more efficient GNN training than EdgePool**. Similarly, our methods generally improve on the runtimes for dense pooling methods such as DiffPool and MinCutPool, and improve on the computational efficiency of TopKPool and SAGPool.\n\nTable of **training times in seconds compared across pooling methods**. The fastest methods are marked in bold.\n\n| Method         |      DHFR       |     ENZYMES     |     NCI109      |  Mutagenicity   |  IMDB-BINARY   |  IMDB-MULTI    |\n|----------------|------------------|------------------|------------------|------------------|----------------|----------------|\n| MagEdgePool    | 39.8 ± 6.0       | **22.0 ± 0.2**   | 186.0 ± 9.1      | **180.3 ± 29.0** | 75.4 ± 1.4     | **89.6 ± 6.1**  |\n| SpreadEdgePool | **34.8 ± 1.0**   | 23.0 ± 0.7       | **181.3 ± 29.4** | 206.7 ± 20.6     | **62.7 ± 0.9** | 99.7 ± 4.3     |\n| EdgePool       | 184.1 ± 4.0      | 209.3 ± 4.1      | 807.4 ± 22.2     | 790.7 ± 22.1     | 362.3 ± 3.4    | 392.7 ± 11.9   |\n| TopKPool       | 50.7 ± 0.8       | 24.1 ± 0.6       | 226.1 ± 21.3     | 243.8 ± 15.4     | 88.2 ± 1.1     | 110.9 ± 2.2    |\n| SAGPool        | 54.4 ± 1.3       | 25.7 ± 0.4       | 250.4 ± 25.7     | 253.0 ± 20.0     | 92.6 ± 2.1     | 131.1 ± 1.3    |\n| DiffPool       | 52.2 ± 6.8       | 36.4 ± 3.3       | 242.4 ± 12.5     | 274.0 ± 21.5     | 106.7 ± 5.5    | **74.9 ± 2.0** |\n| MinCutPool     | **33.8 ± 2.5**   | 28.2 ± 1.7  | 210.3 ± 34.4     | 201.0 ± 3.7      | 93.2 ± 1.6     | 132.8 ± 3.2    |\n\n\nTable of **memory usage in MB compared across pooling methods**. The most efficient methods are marked in bold.\n| Method         |      DHFR       |     ENZYMES     |     NCI109      |  Mutagenicity   |  IMDB-BINARY   |  IMDB-MULTI    |\n|----------------|------------------|------------------|------------------|------------------|----------------|----------------|\n| MagEdgePool    | **84.0 ± 0.1**   | **91.2 ± 2.5**   | **97.0 ± 1.1**   | **94.8 ± 1.0**   | **283.4 ± 28.0** | **197.6 ± 17.8** |\n| SpreadEdgePool | **84.0 ± 0.1**   | **90.6 ± 2.3**   | **96.8 ± 1.0**   | **95.2 ± 1.0**   | **283.4 ± 28.0** | **197.4 ± 17.8** |\n| EdgePool       | 125.6 ± 10.4     | 148.4 ± 15.0     | 118.6 ± 7.7      | 118.0 ± 7.4      | 666.6 ± 106.6   | 526.2 ± 89.2    |\n| TopKPool       | 89.6 ± 9.0       | 94.4 ± 4.0       | 105.0 ± 1.4      | 105.8 ± 6.5      | **259.4 ± 31.5** | **193.8 ± 17.5** |\n| SAGPool        | 104.2 ± 0.6      | 94.2 ± 3.8       | 105.2 ± 1.4      | 107.8 ± 8.1      | **273.4 ± 30.1** | **209.0 ± 17.9** |\n| DiffPool       | 90.2 ± 10.2      | 94.6 ± 2.5       | 103.8 ± 1.1      | 299.8 ± 31.9     | **258.0 ± 40.3** | 240.8 ± 26.4    |\n| MinCutPool     | 90.6 ± 10.3      | 94.2 ± 2.4       | 103.6 ± 0.8      | 288.4 ± 38.3     | **258.0 ± 40.3** | **196.6 ± 26.0** |\n\n\nHaving observed that pre-computed edge-pooling speeds up GNN training times, we further compare with the **runtime and memory costs of other non-trainable pooling operators prior to training**. We report the computational costs of computing the pooling assignment for all graphs in the datasets.\n\nAs reported in our manuscript, we find that **SpreadEdgePool is generally more efficient than MagEdgePool**. Beyond the exact computations of our pooling methods, we also approximate the change in diffusion distance during edge contraction by updating the contracted node’s distances to be the minimum distance to the original nodes. These approximate versions denoted MagEdgePool\\* and SpreadEdgePool\\* notably reduce computational costs. \n\nTable of **pre-training times in seconds compared across non-trainable pooling methods**. The fastest method is marked in bold. The fastest approximation of our pooling method is marked in cursive.\n\n| Method           |   DHFR   | ENZYMES | Mutagenicity | NCI109  | IMDB-BINARY | IMDB-MULTI |\n|------------------|----------|---------|---------------|---------|--------------|-------------|\n| MagEdgePool      |   61.9   |  197.4  |    4765.1     |  678.8  |    801.8     |    480.2    |\n| MagEdgePool*     |   24.6   |   21.0  |     81.3      |   74.9  |     77.4     |     69.9    |\n| SpreadEdgePool   |   66.7   |   68.3  |    316.1      |  208.8  |    287.2     |    243.8    |\n| SpreadEdgePool*  | *10.9*   | *16.0*  |   *52.3*      | *55.6*  |   *56.0*     |   *66.0*    |\n| NDP              |   5.6    |   4.1   | **37.1**      |  32.6   |     5.8      |     7.0     |\n| NMF              |   7.8    |  10.8   |    39.0       |  32.1   |     8.7      |     9.0     |\n| Graclus          | **3.8**  | **2.9** |    54.5       | **18.2**|  **4.5**     |  **6.0**    |\n\nTable of **pre-training memory usage in MB compared across non-trainable pooling methods**. The most efficient method is marked in bold. The fastest approximation of our pooling method is marked in cursive.\n\n| Method           |   DHFR   | ENZYMES | Mutagenicity | NCI109  | IMDB-BINARY | IMDB-MULTI |\n|------------------|----------|---------|---------------|---------|--------------|-------------|\n| MagEdgePool      |   76.2   |  163.8  |    158.9      |  179.0  |    162.1     |    93.1     |\n| MagEdgePool*     |   83.7   | *34.8*  |   *47.0*      | *72.2*  |   *11.5*     |    65.2     |\n| SpreadEdgePool   |   61.9   |  60.1   |    177.9      |  93.1   |    204.1     |    75.8     |\n| SpreadEdgePool*  | *33.6*   |  54.1   |    60.5       |  72.9   |    53.2      |  *23.8*     |\n| NDP              | **3.0**  | **5.0** |   **7.0**     |  13.4   |     5.1      |     6.5     |\n| NMF              |   3.8    |   5.9   |    39.9       | **10.5**|     4.2      |     5.9     |\n| Graclus          |  15.8    |   7.5   |    17.5       |  59.5   |  **1.0**     |  **1.5**    |\n\n\n\nThe presented results show one of the limitations discussed in our manuscript, namely that our edge pooling approach scales in the number of edges as well as the size of the graphs. Nevertheless, our proposed pooling methods still notably **outperform EdgePool in terms of computational efficiency** when considering both the preprocessing and training costs as reported above. Further, the pretraining costs of our method range in a number of seconds, only need to be computed once per dataset, and the memory requirements remain below what is required by GNN training. Hence, we find that **our proposed pooling methods scale sufficiently well to standard graph datasets**. \n\nWe look forward to presenting extended experiments on computational efficiency in revisions. For future work, we believe there is a strong potential to further speed up our pooling methods by investigating alternative graph metrics, testing sampling heuristics to restrict the edge score computations to a subset of candidate edges, or computing edge score on local subgraphs rather than on the whole graph. \n\n\n>  Is the code open-source and reproducible?\n\nWe will publish a light-weight implementation of our pooling method as an open-source package to allow users to try our pooling method on their own datasets. \n\nThis is in addition to our supplementary code submission, which can be used to reproduce our experiments."}, {"review_id": "L3Gubk8i2O", "reviewer": "Reviewer_rNzm", "summary": "This paper introduces MagEdgePool and SpreadEdgePool, two novel geometry-aware edge pooling methods for GNNs that address the challenge of reducing graph size while preserving structural information. Unlike existing pooling approaches that focus on node clustering or dropping, these methods use edge contraction guided by the magnitude and spread of metric spaces - measures that quantify a graph's structural diversity based on diffusion distances. The key insight is that edges whose removal minimally affects the graph's magnitude or spread are the most redundant and should be collapsed first, thereby preserving the graph's geometric properties during pooling. The authors provide theoretical analysis showing that their methods are isometry-invariant and preserve key properties like additivity for disjoint graphs.", "questions": "1. In the abstract, I am confused about this sentence: \"However, existing pooling operations often optimise for the learning task at the expense of fundamental graph structures and interpretability.\"\n2. Is the proposed method in this paper effective for the graph regression task?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper provides rigorous mathematical grounding with theorems on additivity, isomorphism invariance, and bounds relating magnitude and spread, giving the methods solid theoretical justification beyond empirical results.\n2. The proposed methods achieve top rankings across 8 diverse datasets, demonstrating robustness and generalizability rather than being tuned to specific graph types.\n\nWeaknesses:\n1. In some parts, the graph is defined as G = (X, E), while in some other parts it is G = (V, E). Besides, the definitions of X, V, and E are not given. \n2. In the visualization results from Figure 1, the pooling ratio of different pooling methods are not consistent.", "was_revised": true, "final_justification": "I have no further questions. I vote for acceptance.", "rebuttal": "**Summary**\n\n**New experiments with preliminary results and additions:**\n- *Regression experiments:* Report and compare the performance of our pooling method at regression tasks during revisions.\n\n**Clarifications and revisions:**\n- *Definition of a graph:* Correct the definition of a graph to be consistent across the manuscript. \n- *Changes in the abstract:* Clarify the sentence in the abstract.\n- *Figure 1:* Double-check the number of nodes. Specify that graphs are pooled to approximately half their size.\n\n---\n\n\nWe thank the reviewer for their positive feedback, in particular for highlighting that our pooling approach demonstrates robust and generalisable performance. \n\n> In some parts, the graph is defined as G = (X, E), while in some other parts it is G = (V, E). Besides, the definitions of X, V, and E are not given.\n\n> In the abstract, I am confused about this sentence: \"However, existing pooling operations often optimise for the learning task at the expense of fundamental graph structures and interpretability.\"\n\nWe thank the reviewer for pointing out specific revisions in the text and **we will clarify the definition of a graph and reformulate the sentence in the abstract**. Specifically, the sentence refers to the observation that existing trainable pooling operators tend to optimise for a task-specific loss. However, such methods might not preserve the structure of the graph during pooling and make counterintuitive choices on which graph properties to preserve. This is illustrated by the comparison between pooling methods in Figure 1, which shows that pooling methods such as TopKPool, SAGPool, DiffPool, or MinCutPool do not necessarily lead to interpretable graph coarsening.\n\n\n> In the visualization results from Figure 1, the pooling ratio of different pooling methods are not consistent.\n\nThe pooling ratios in Figure 1 are consistently set to 50%. However, some pooling methods (e.g. Graculus or NDP) do not give exact control over the number of vertices, but pool graphs to **approximately half** of their original size. This is why the exact number of nodes differ slightly. We will clarify this in the manuscript and aim to provide a revised version of Figure 1 with more comparable node numbers whenever possible. \n\n>  Is the proposed method in this paper effective for the graph regression task?\n\nOur method can be extended to regression tasks and flexibly plugged into any GNN. For revisions, **we plan to incorporate regression tasks into our analysis** and adjust our model architecture and evaluation to fit these tasks. **We expect regression performance to agree with the classification results.** The arguments why our proposed edge pooling methods perform well at graph classification, namely that features are aggregated in an expressive manner and that graph structure is preserved during pooling, similarly hold for graph regression tasks."}, {"review_id": "E61y41PNaV", "reviewer": "Reviewer_GecT", "summary": "The study proposes a novel magnitude and spread-guided edge pooling layer, incorporating metric space diversity measures into graph compression for the first time. This approach effectively preserves graph geometric structures while enhancing classification performance. The paper provides rigorous theoretical foundations, including error propagation bounds for both magnitude and spread metrics.", "questions": "1. **Runtime and Memory Usage:** Could the authors provide detailed runtime and memory usage data? Comparisons with other training-free methods (e.g., TopK and MinCut) would be valuable.\n\n2. **Scalability to Large-Scale Graphs:** Current experiments focus on small graphs. Testing on large-scale datasets, such as PDB for Enzyme Commission (EC) number prediction or Gene Ontology (GO) term prediction [1], would better demonstrate practical applicability.\n\n3. **Extension to Regression Tasks:** The study currently focuses exclusively on classification. Could the proposed method also be extended to regression tasks, such as Protein Localization Prediction on UniProt [2]?\n\n[1] José Juan Almagro Armenteros et al., DeepLoc: Prediction of protein subcellular localization using deep learning. Bioinformatics, 33 (21):3387–3395, 2017. https://www.nature.com/articles/s41467-021-23303-9#Sec27\n\n[2] Vladimir Gligorijević et al., Structure-based protein function prediction using graph convolutional networks. Nature Communications, 12(1):3168, 2021. https://pubmed.ncbi.nlm.nih.gov/29036616/", "limitations": "Experiments are confined to small graphs and classification tasks, lacking validation on large-scale datasets or regression problems.\nWhile computational complexity is mentioned, concrete runtime measurements are absent.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. **Improved Classification Accuracy:** Achieves superior performance on most datasets, with significant improvements noted on specific datasets like DHFR.\n\n2. **Robustness:** Demonstrates minimal performance fluctuations across a wide range of pooling ratios (6.25% to 100%), indicating strong adaptability for dynamic graph compression needs.\n\n3. **Interpretability:** Decision-making based on geometric invariants offers transparent and explainable results.\n\nWeaknesses:\n\n1. **Inconsistent Performance:** Although beneficial for most datasets, the proposed method underperforms on certain datasets (e.g., Mutagenicity), with only half achieving state-of-the-art (SOTA) results.\n\n2. **High Computational Complexity:** Despite being training-free, PCA computations introduce considerable complexity, potentially limiting scalability to large-scale graphs.\n\n3. **Lack of Novelty in Diffusion Distance:** The diffusion distance concept applied by the authors is not novel; rather, the contribution lies in its specific application to graph pooling.\n\n4. **Spelling Errors:** The manuscript contains several spelling errors (e.g., \"MagEgdePool\" instead of \"MagEdgePool\" on line 195; repeated \"SpreadEgdePool\" errors on lines 220, 229, and 341), suggesting the need for careful proofreading.", "was_revised": true, "final_justification": "I have revised my score upward after noticing that my initial assessment was based on a misreading of the performance table. Nevertheless, I remain concerned about the very high scalability of the proposed method, especially in the context of large-scale graph data.", "rebuttal": "**Summary**\n\n**New experiments with preliminary results and additions:**\n- *Computational efficiency:* Evaluate runtime and memory usage across pooling methods. Report and contrast pre-training and training costs. Highlight the computational improvements compared to EdgePool.\n- *Regression experiments:* Report and compare the performance of our pooling method at regression tasks during revisions.\n\n**Clarifications and revisions:**\n- *SOTA results:* Clarify the purpose of graph pooling. Contextualise the reported accuracy gains w.r.t. to baseline pooling methods and existing literature [1, 2].\n- *Novelty of diffusion distances:* Explain the conceptual benefits of using diffusion distances on graphs. Highlight potential extensions of our methods based on established theory on diffusion maps [4, 5].\n- *Typos:* Correct minor typos in the spelling of MagEdgePool.\n\n**Extended discussion:**\n- *Computational efficiency:* Add an extended discussion on the computational efficiency of our pooling method in comparison to alternative methods. \n- *Large-graphs tasks:* Discuss potential extensions to large-scale graphs.\n\n---\n\n\nWe would like to clarify the points raised by Reviewer GecT.\n\n> Improved Classification Accuracy: Achieves superior performance on most datasets, with significant improvements noted on specific datasets like DHFR.\n\nWe are thankful that this review acknowledges the superior classification accuracy and robust performance achieved by our pooling methods.\n\n>    Inconsistent Performance: Although beneficial for most datasets, the proposed method underperforms on certain datasets (e.g., Mutagenicity), with only half achieving state-of-the-art (SOTA) results.\n\n**The purpose of our evaluation is not to achieve SOTA results across all datasets and all potential GNN architectures**, but to give a consistent benchmark that enables a **fair comparison of pooling methods across tasks**. For that purpose we plug each pooling layer into the same GNN architecture as commonly done to compare pooling methods. However, it is unrealistic to believe that this setup could or should achieve SOTA results on every datasets without dataset-specific modifications. \n\nNevertheless, our results show consistent and robust performance across tasks, and reach very high accuracies above what is reported in most pooling benchmarks [1, 2]. In fact, **on Mutagenicity our pooling method outperforms all alternative pooling layers** included in our comparison. For this reason, we argue that **our pooling methods reach SOTA results amongst baseline pooling methods** and do not underperform. \n\n>    High Computational Complexity: Despite being training-free, PCA computations introduce considerable complexity, potentially limiting scalability to large-scale graphs.\n\nWe would like to clarify that **our pooling method does not compute PCA**. We compute the magnitude or spread of a graph as defined in Equations (1) and (2) for edge pooling and discuss the computational complexity of these calculations in our manuscript. However, this is not equivalent to PCA. This seems to be a misunderstanding about the computation of our algorithm. \n\nFurther, we provide additional results on the memory cost and computational complexity in our response to AV7X. We thus find that **the computational performance of our proposed pooling method is competitive** for most standard graph classification datasets. Overall, our pooling approach notably improves on the computational efficiency of EdgePool. Thus, we **address scalability limitations of existing (edge) pooling methods**, such as EdgePool, DiffPool, and MinCutPool, which scale notably worse to large-scale graphs. \n\n\n>    Runtime and Memory Usage: Could the authors provide detailed runtime and memory usage data? Comparisons with other training-free methods (e.g., TopK and MinCut) would be valuable.\n\nWe would like to clarify that **TopK and MinCut are trainable rather than training-free methods**. Considering the distinction between, trainable (TopK, MinCut, SAGPool, DiffPool) and training-free methods (ours, Graclus, NDP, NMF), **we are happy to provide runtime and memory comparisons** in the response to reviewer AV7X.\n\nSpecifically, we find that e.g. on IMDB-M our method SpreadEdgePool (99.7s per run) allows for notably faster training than MinCutPool (132.8s) and moderately faster training than TopKPool (110.9s). Thus, we find that **the improved computational efficiency of GNN training is an advantage of our pooling method**.\n\n\n>    Lack of Novelty in Diffusion Distance: The diffusion distance concept applied by the authors is not novel; rather, the contribution lies in its specific application to graph pooling.\n\n\nOur pooling method indeed leverages the diffusion distance, a well-studied metric on general measure spaces that leverages both geometrical and topological aspects of the input data. The **novelty of our method** lies in its formulation as a technique based on metric space magnitude, a recently introduced invariant for metric spaces. As reviewer 7pUv pointed out, we are the **first paper to study magnitude-informed approaches in the context of graph learning**. The **use of the diffusion distance**, which users can replace if they need to, **is rather a strength of our method**.\n\nFor further research, we believe that the usage of diffusion distances offers the chance to leverage a rich theory on approximation methods via landmarks [4], or localised diffusion computations [5], which can lead to further computational improvements and extension of our methods. We thus believe the established theory on diffusion maps is a benefit of our methodology.\n\n\n>    Spelling Errors: The manuscript contains several spelling errors (e.g., \"MagEgdePool\" instead of \"MagEdgePool\" on line 195; repeated \"SpreadEgdePool\" errors on lines 220, 229, and 341), suggesting the need for careful proofreading.\n\nWe thank the reviewer for pointing out specific typos and look forward to correcting them in the final manuscript. We are happy to rectify these minor mistakes in our revision.\n\n\n>    Scalability to Large-Scale Graphs: Current experiments focus on small graphs. Testing on large-scale datasets, such as PDB for Enzyme Commission (EC) number prediction or Gene Ontology (GO) term prediction [1], would better demonstrate practical applicability.\n\nExperiments on large-scale graphs would indeed be of interest, but truly massive graphs are rarely encountered for graph classification tasks [3] and offer a particular set of challenges regarding memory and computational costs. **Existing pooling methods** that process dense adjacency matrices, such as MinCut or DiffPool, **are unlikely to scale to such tasks** without major modifications [2, 3]. \n\nGiven these necessary architecture adjustments, **large-scale experiments remain outside the scope of our work for now.** However, for future work, we note that our edge pooling method could indeed be scaled to larger graphs by e.g. computing the edge scores in a localised or mini-batched manner on carefully chosen subgraphs rather than on the whole graph. The sparse pre-trained edge assignment could then be used efficiently for training on large-scale graphs. \n\nWe also note that already, **our pooling method notably outperforms EdgePool or dense pooling methods such as MinCut or DiffPool in terms of memory costs and computational efficiency**, improving the scalability of edge pooling in most practical applications to standard graph classification tasks. \n\n\n\n>    Extension to Regression Tasks: The study currently focuses exclusively on classification. Could the proposed method also be extended to regression tasks, such as Protein Localization Prediction on UniProt [2]?\n\nWe would like to note that **protein localisation prediction on UniProt is a node classification task** rather than a regression task. Working with the suggested datasets, PDB or UniProt, would require domain-specific preprocessing and careful evaluation beyond what is feasible in the scope of rebuttals. \n\n**Our pooling architectures can be extended to either node classification or graph regression problems.** However, we consider graph-level tasks to be the most relevant applications of pooling methods [1] and thus choose to focus on graph classification tasks for our analysis. \n\nOverall, we hope that our answer could clarify any misunderstandings.\n\n\n**References**\n\n[1] Wang, P., et al., 2024. A comprehensive graph pooling benchmark: Effectiveness, robustness and generalizability. \n\n[2] Grattarola, D., et al., 2022. Understanding pooling in graph neural networks. \n\n[3] Bianchi, F.M. and Lachi, V., 2023. The expressive power of pooling in graph neural networks. \n\n[4] Long, A.W. and Ferguson, A.L., 2019. Landmark diffusion maps (L-dMaps): Accelerated manifold learning out-of-sample extension. \n\n[5] David, G. and Averbuch, A., 2012. Hierarchical data organization, clustering and denoising via localized diffusion folders."}]

Author rebuttal:

Meta-review: This paper introduces two graph pooling layers for Graph Neural Networks (GNNs), MagEdgePool and SpreadEdgePool, designed to preserve fundamental graph structures during pooling by using edge collapses. These methods leverage diffusion geometry and are guided by magnitude and spread, which are measures of structural diversity, to iteratively reduce a graph's size while maintaining its metric structure. Empirical results show that these approaches outperform existing pooling layers on various graph classification tasks, effectively preserve key spectral properties of the input graphs, and maintain high accuracy across different pooling ratios. 


Overall, the reviewers all agreed that the method is elegant, novel and seems to work well. One reviewer (GecT) recommends rejection (3), but upon examination of their review, the reviewer (a) has made a lot of errors in their review (e.g. referring to PCA whilst PCA is not mentioned) and (b) has not appropriately engaged in the discussion. Consequently, we will down weight this reviewer's contribution. Most reservations from the other reviewers concerned the computational efficacy of the method, which was addressed (to a satisfactory extent) by the author during the rebuttal phase.  The authors have also provided new experiments during the rebuttal. The reviewers also expressed their interest in seeing other relevant benchmarks that were not included in the manuscript. Should this paper be accepted, these would constitute interesting additions to the camera ready version of the paper.
Decision: Accept (poster)