Boosting Graph Pooling with Persistent Homology
Authors: Chaolong Ying
Xinjian Zhao
Tianshu Yu
Venue: NeurIPS 2024 poster (2024)
Keywords: graph pooling
persistent homology
graph learning
Primary area: graph_neural_networks
TL;DR: We propose a persistent-homology-guided graph pooling scheme, which can be flexibly integrated into extant pooling methods and achieved remarkable performance improvement.

Abstract: Recently, there has been an emerging trend to integrate persistent homology (PH) into graph neural networks (GNNs) to enrich expressive power. However, naively plugging PH features into GNN layers always results in marginal improvement with low interpretability. In this paper, we investigate a novel mechanism for injecting global topological invariance into pooling layers using PH, motivated by the observation that filtration operation in PH naturally aligns graph pooling in a cut-off manner. In this fashion, message passing in the coarsened graph acts along persistent pooled topology, leading to improved performance. Experimentally, we apply our mechanism to a collection of graph pooling methods and observe consistent and substantial performance gain over several popular datasets, demonstrating its wide applicability and flexibility.

Boosting Graph Pooling with Persistent Homology
Chaolong Ying, Xinjian Zhao, Tianshu Yu' School of Data Science, The Chinese University of Hong Kong, Shenzhen
{chaolongying, sang.iinniiaaaaoooo @li. cuhk edu en, yutianshu@cuhk. edu. cn
Abstract
Recently, there has been an emerging trend integrate persistent homology (PH) into graph neural networks (GNNs) to enrich expressive power. However, naively plugging PH features into GNN layers always results marginal improvement with low interpretability. In this paper, we investigate a novel mechanism for injecting global topological invariance into pooling layers using PH, motivated by the observation that filtration operation in PH naturally aligns graph pooling in cut-off manner. In this fashion, message passing in the coarsened graph acts along persistent pooled topology, leading to improved performance. Experimentally, we apply our mechanism to a collection of graph pooling methods and observe consis- tent and substantial performance gain over several popular datasets, demonstrating its wide applicability and flexibility.
Introduction
Persistent homology (PH) is powerful tool in the field topological data analysis, which is capable of evaluating stable topological invariant properties from unstructured data in multi-resolution fashion [8. Concretely, PH derives an increasing sequence of simplicial complex subsets by applying
filtration function (see Fig. ((a) According to the fact that PH is at least expressive as Weisfeiler-
Lehman (WL) hierarchy 19) there recently emerged series of works seeking to merge PH into graph
neural networks (GNNs), delivering competitive performance specific tasks [52] [9] Standard schemes of existing works achieve this by employing pre-calculated topological features (52) or placing learnable filtration functions in the neural architectures [16 19] Such integration of PH features is claimed to enable GNNs to emphasize persistent topological sub-structures. However, is still unclear to what extent the feature-level integration of PH is appropriate and how empower GNNs with PH other than utilizing features.
Graph pooling (GP) in parallel plays an important role in series of graph learning methods [14], which hicrarchically aggregates an upper-level graph into a more compact lower-level graph. Typically, GP relies calculating assignment matrix taking into account local structural properties such as community (34] and cuts (2). Though the pooling paradigm in convolutional neural networks (CNNs) quite successful [27] some researchers raise concerns about its effectiveness and applicability in graphs. For example, 30 challenges the local-preserving usage GP by demonstrating that random pooling even leads similar performance. Till now, remains opaque what property should be preserved for pooled topology to better facilitate the downstream tasks.
From Fig. ((a) is readily observed that PH and GP both seek to coarsen/sparsify given graph hierarchical fashion: while PH gradually derives persistent sub-topology (substructures such as eycles) by adjusting the filtering parameter, GP obtains sub-graph by performing more aggressive cut-off. In a sense of understanding a graph through hicrarchical lens, PH and GP turn out to align with each other well.
Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Destnuatio
periiseesee
NCII
NCT109 PROTEINS ENZYMES IMDB-BINARY
Pendices
Pooling ratio
Creation
(a) Hierarchical view of GP and PH (b) Alignment of GP and PH
(c) Persistence diagrams
Figure I: Illustration Graph Pooling (GP) and Persistent Homology (PH). (a) GP and share similar hierarchical fashion by coarsening graph. (b) As motivating experiment, we gradually
change pooling ratio and count how persistence ratio (ratio of non-zero persistence) changes with (c) Illustration of persistence diagrams.
Driven by this observation, in this paper, we investigate the mechanism of aligning PH and GP so mutually reinforce each other. To this end, we conduct experiments by running a pioneer GP method DiffPool 50 to conduct graph classification
several datasets and at the same time use the technique in [6] to compute PH information. We manually change the pooling ratio and see what proportion of meaningful topological information (characterized by the ratio of non-zero persistence) naturally preserved at final training stage. Surprisingly, the correspondence is quite stable regardless of different datasets (see Fig. [(b).. which implies the monotone trend between the pooling ratio and non-zero persistence commonly shared by large range of graph data. As consequence, we develop natural way to integrate PH and GP in both feature and topology levels. Concretely, in addition to concatenating vectorized PH diagram as supplementary features, we further enforce the much as possible with a specially designed
coarsened graph to preserve topological information PH-inspired loss function. Hence we term our method Topology-Invariant Pooling (TIP). TIP can be flexibly injected into variety of existing GP methods, and demonstrates consistent ability to provide substantial improvement over them. We summarize our contributions as follows:
We for the first time investigate the way of aligning PH with GP, by investigating the monotone relationship in between.
We further design effective mechanism to inject PH information into GP at both feature and topology levels, with a novel topology-preseeeeeoooo preserving loss function.
Our mechanism can be flexibly integrated with a variety of GP methods, achieving consistent and substantial improvement over multiple datasets.
2
Related work
Graph pooling. Graph pooling has been used in various applications, which reduce the graph size while preserving its structural information. Early methods are based on clustering to coarsen graphs,
such the greedy clustering method Graclus [7], non-negative matrix factorization of the adjacency
matrix [1. and spectral clustering [29]. Recently, learnable graph pooling methods have gained popularity, which learn select important nodes in end-to-end manner. DiffPool (50] follows
a hierarchical learning structure by utilizing GNNs to learn clusters and gradually aggregate nodes into a coarser graph. MinCutPool (2) optimizes a normalized cut objective to partition graphs into clusters. DMoNPool (34] optimizes the modularity of graphs to ensure high-quality clusters. SEP (46) generates clusters in different hierarchies simultancously without compromising local structures. These methods are classified dense pooling due to the space complexity they incur. Despite their effectiveness, dense pooling methods have been criticized for high memory cost and complexity [5] Therefore, various sparse pooling methods have been proposed, such as Top- K [II] ASAPool [8]. and SAGPool (28) These methods coarsen graphs by selecting subset of nodes based on a ranking score. As they drop some nodes in the pooling process, these methods are criticized for their limited capacity retain essential information, with potential effects on the expressiveness of preceding GNN layers 3

---

Persistent homology in GNNs. PH is a technique to calculate topological features of structured data, and many approaches have been proposed to use PH in graph machine learning due to the high
expressiveness of topological features on graphs [8]] Since non-isomorphic graphs may exhibit different topological features, the combination of PH and the Weisfeiler-Lehmann (WI.) algorithm leads to stronger expressive power 40). This encourages further exploration equipping GNNs with topologiaal features. [52] propose that message passing in GNNs can be effectively reweighted using topological features. [16] and [19] provide theoretical and practical insights that filtrations in PH can be purely learnable, enabling flexible usage of topological features in GNNs. However, existing methods tend to view PH merely tool for providing supplementary information to GNNs, resulting in unsatisfactory improvements and limited interpretability.
3 Background
We briefly review the background of this topic in this section, as well as elaborate on the notations.
Let 9 = (V. F) be an undirected graph with n nodes and m edges, where V and are the node and the edge sets, respectively. Nodes in attributed graphs are associated with features, and we denote by V = {1V, x.yxx,JJee Joelm the set of nodes v with d dimensional attribute X It is also practical to represent the graph with an adjacency matrix A E {0, 1]nx* and the node feature matrix X E Raxd
Graph Neural Networks. We focus the general peessage-passing GNN framework that updates node representations by iteratively aggregating information from neighbors 12]. Concretely, the k-th layer of such GNNs can be expressed as:
x (*) M (4,
(I)
where ((k) is the trainable parameter, and M is the message propagation function. Numbers of M
have been proposed in previous research 25 [5]. A complete GNN typically instantiated by
stacking multiple layers of Eq. Hereafter we denote by GNN(.) an arbitrary such multi-layer GNN
for brevity.
Dense Graph Pooling. GP in GNNs is a special layer designated to produce coarsened or sparsified bub-graph. Formally, GP can be formulated as G + Gp = (Vp,Ep) Ep) such that the number of nodes |V < n. GP layers can be placed into GNNs in a hierarchical fashion to persistently rely on learning a soft cluster assignment matrix
coarsen the graph. Typical GP approaches 550 S(1) 1 X
(()) softmax (GNN')
(2)
Subsequently, the coarsened adjacency matrix at the I-th pooling layer is calculated as
A (1) S A ((1))
and the corresponding node representations are calculated as
x = S (NN(() (A (A'-"),x(-1)
These approaches differ from each other in the way produce S, which is used to inject bias in the formation of clusters. In our work, we select three GP methods, i.e., DiffPool [50), MinCutPool [2]. and DMoNPool (34). cope with. Details of the pooling layers in these methods are summarized in Appendix
Topological Features of Graphs. A simplicial complex K consists of set of simplices of certain dimensions. Each simplex E K has set of faces, and each face y has to satisfy T E K. An element 7 E K with hyl = le + 1 is called k-simplex, which we denote by writing dim 7 = Furthermore, if & is maximal among all simplices in K, then K is referred to as a k-dimensional simplicial complex. A graph can be seen as a dimeeninniional simplicial complex that only contains simplices (vertices) and I-simplices (edges) [99 The simplest kind of topological features describing graphs are Betti numbers, formally denoted as 3o for the number of connected components and 31 for the number of cycles.
3

---

(A 1 .
(A x(
S
(A (A
Topologg Sopology-Invariing Invariant Pooling
Pooling layes
Resample
Scllclure
Ey
PD
(A (0)
X
x
Liogo
Fig (6)
Reweigght
Figure 2: Overview of our method. The shaded part is one layer of Topology-Invariing Pooling.
Despite the limited expressive power of these two numbers, can be improved by evaluating them alongside filtration. Filtrations are scalar-valued functions of the form f V U E + IR monitored
Changes in the Betti numbers, named as persistent Betti numbers, can subsequently throughout the progress of the filtration: by considering threshold (a E R), can analyze the subgraph originating from the pre-image of ((-00, al) of denoted as (f-i((-oc, al)). The < On and generates sequence of nested subgraphs of the form C Go S ....g, Gb ... S Gn = G. where Gr= (Vi, Ex) is a subgraph of g with V {e V f (x,) a } and Eg == {(t, w) E max {f (x,), f (xw)) ) S ax). This process is also known as persistent homology (denoted as ph(()) on graphs. Typically, persistent Betti numbers summarized in a persistence diagram (PD) ph(G, f] Dr where i [0, 1,..] the dimension of topological features. PD is made up of tuples (a, a3) E R?, with ag and aj representing the creation and destruction of a topological feature respectively (see Fig. [[c]]. The absolute difference in function values |a, asl is called the persistence of a topological feature, where high persistence corresponds features of the function, while low persistence is typically
image of leads to finite set of values d1
considered as noise 199 39
4 Methodology
4.1
Overview
An overview of our method is shown in Fig. 2 where the shaded part corresponds one layer of Topology-Invariant Pooling. The upper part is the GP process and the lower part is the injection of PH. Let (A (0), (0)) be the input graph. We consider to perform a GP at the (1 1)-th layer. After obtaining a coarsened (densely connected) graph (A (1), X with a standard GP method, we resample the coarsened graph using Humbel--offtanl trick as A!)) in order make it adapt to PH. Then, this coarsened graph is further reweighted injecting persistence, and is optimized by minimizing the topological gap Liopo from the original graph. yielding (A (1), X!). By stacking multiple TIP layers, hierarchical pooling emphasizing topological information can be achieved. In the following sections, we elaborate on the detailed design of our mechanism.
4.2 Hopology-Invarian Pooling
In many real-world applications, the topology of graphs of utmost importance 44 However, typical GNNs fail to capture certain topological structures graphs, such as cycles 4 51 21 Moreover, in dense graph pooling, graphs are pooled without preserving any topology. Even if we manage to make GNN topology-awan the coarsened graph is nearly fully connected and has no meaningful topology at all, impairing the use of GNNs in these tasks. To overcome these limitations, we propose to inject topological information into GP. We resort to PH to characterize the importance of edges.
49
16]
The core of PH is the notion of filtration, the selection of which presents challenging task. As the coarsened graph evolves in each training step, integrating PH into GP demands multiple computations

---

of filtrations. To address this, we place recently proposed learnable filtration (LF) functions [[6] to incorporate PH information for flexibility and efficiency. LF relies on node features and graph topology, which are readily available in GP. Consequently, LF can be seamlessly integrated into GP with minimal computational overhead. Specifically, we employ an MLP network (t)) as the filtration function together with sigmoid(-) Recently, an increasing amount of attention has been devoted to cycles 4 31 21] significant relevance to downstream tasks various domains such as biology 26], chemistry [B5), and social network analysis [23]. Recognizing that cycles offer an intuitive representation of graph structure [3 17. and preliminary experiments, shown in Appendix [.5] indicate that the additional inclusion of zero-dimensional topological features merely increases runtime, thus we instead focus on the one-dimensional PDs associated with cycles. For those edges do not form eycles, their creation and destruction are the same, leading to zero persistence. Following the standard way in GP (Eq. 2 D. we additionally propose the subsequent modules to inject PH into GP at both feature and topology levels.
map node features X E [a into scalar values.
due to their
Resampling. One major limitation of utilizing LF proposed in []6] is that the computation process is unaware of edge weights, i.e. edges with non-zero weights will be treated equally, so PH cannot directly extract meaningful topology from A AO), Besides, rethinking GP in Eq. 3 the coarsened adja- cency matrix has limited expressive power for two reasons. First, although S is a soft assignment matrix obtained by softmax('), each element still has nonzero values, i.c. A is always densely connected. Second, the edge weights may span wide range by multiplication (refer Appendix for empirical evidence). These drawbacks hinder the stability and generalization power of the subsequent message passing layers (13]. None of the existing GP methods can handle these problems properly.
Therefore, we resample the coarsened adjacency A (!) obtained from a normal GP layer (Eq. 3
as:
(1) min(A (9)
(1) = resample max min (A))))
(5)
where A (1) is first normalized in the range of [o, 1]. and resample(-) is performed independently for each matrix entry using the Gumbel-softmax trick (22]. In practice, only the upper triangular matrix is resampled to make symmetric and we add self-loops to the graph.
Persistence Injection. Now A E {0, 1 is a sparse matrix without edge features can easily inject topological information into it. For a resampled graph with A (!) and ((), we formulate the persistence injection as:
D = ph(A (1) sigmoid (( ((x
(6)
A A (0) @ to dense [1] 1 (0))))
where @ is the Hadamard product, to, dense() means transforming sparse representations in terms of edges to dense matrix representations, Dj is the augmented 1-dimensional PDD by placing the tuples correspond self-loop edges on the diagonal part of original PDs D,, [i] is the i-th value in each tuple of Dj, and we denote the updated adjacency matrix after persistence injection still as (1) for notation consistency. Persistence injection can actually be regarded reweighting process. Since the filtration values are within [0, 1], A (0) after persistence injection is guaranteed to have edge weights in the range of [o, 1] and is passed to the next pooling layer.
Topological Loss Function. The afforementooeed mechanism can explicitly inject topological information into graphs, but it relies on the condition that the coarsened graph retains certain essential sub-topology. To this end, we propose an additional loss function to guide the GP process.
Intuitively, the coarsened graph should exhibit similarity to the original graph in terms of topology. Since the computation of PH is differentiable, one possible approach is to directly minimize the differ- ences between the PDs of the original graph and the coarsened graph. However, this implementation would require computing the Wasserstein distance between two PDs through optimal transport [48), which is intractable in training due to its complexity. Considering that our objective is to estimate the difference, we instead propose vectorizing the PDs and minimizing their high-order statistical
5

---

features [36]. Specifically, we use several transformations (denoted as transform(-)) and concatenate the output, including triangle point transformation, Gaussian point transformation and line point transformation introduced in 6 to convert the tuples in PD into vector h, (4 [1, m!]. We calculate the mean vector 1a as well as the second-order statistics as the standard deviation vector a as:
h transform(D))
TR
12 h h. -
In this manner, the difference between PDs can be estimated through the comparison of their statistics in the features, which the concatenation of the mean and variance vectors. To further regularize the topological difference between layers, we introduce topological loss term defined as:
L
((49109)) (44%)oo0))))
Liopo = Ld
(8)
where (-II-) stands for the concatenation operation, L is the number of pooling layers, and d the feature dimension. Note that the intuition behind Ltopo is different from the loss functions in existing graph pooling methods: the coarsened graph after pooling should be topologically similar to the original graph rather than having exact cluster structures.
4.3 Analysis
In this section, examine the validity of our proposed method, and in particular, analyze its expressive power and complexity.
Theorem 1.
The self-loop augmented I-dimensional topological features computed by PH is sufficient enough to be at least as expressive as 1-WL in terms of distinguishing con-isomorphic graphs, i.e. if the 1-WL label sequences for two graphs G and G' diverge, there exists an injective filtration f such that the corresponding 1-dimensional persistence diagrams Dj and Dí are not equal.
Proof Sketch. We first assume the existence of sequence of WL labels and show how to construct a filtration function f from this. Consider nodes and u' are nodes with unique label count in G and g'. then our filtration is constructed such that their filtration values fuu and fu') are unique and different. Consider all three cases: (1) and u' are both in cycles; (2) and u' are both not in cycles; (3) one of u and u' is in cycles and the other is not. For all the cases, f'(x) and f(u') will be revealed in their respective persistence diagrams. Since f(u) and f('') are unique and different, we can the augmented persistence diagrams to distinguish the two graphs.
This result demonstrates that the self-loop augmented I Iddimensional topological features contain sufficient information to potentially perform at least as well as 1-WL when it comes to distinguishing non-isomorphic graphs. We can then obtain the concluding remark that TIP is more expressive than other dense pooling methods by showing that there are pairs of graphs that cannot be distinguished by 1-WL but be distinguished by TIP. Besides, our proposed simple yet effective self-loop augmentation eliminates the necessity of computing O-dimensional topological features, thus reducing computational burdens.
Proposition 1. TIP is invariant under isomorphism.
Detailed proof and illustrations of the theorem and proposition can be found in Appendix C
Complexity. PH can be efficiently computed for dimensions O and 1, with worst-case time complexity of ((mo(m)) where m represents the number of sorted edges in a graph. Here, ax-) represents the inverse Ackermann function, which extremely slow- goowigroingg and can essentially be considered as a constant for practical purposes. Therefore, the primary factor that affects the calculation of PH is the complexity of sorting all the edges, which O(m log m). Our resampling and persistence injection mechanism ensures that the coarsened graphs are sparse rather than dense, making our approach both efficient and scalable. We provide running time comparisons in Appendix E.2 which indicates that the inclusion of TIP does not impose significant computational burden.

---

Experiments
In the experiments, we evaluate the benefits of persistent homology on several state-of-the-ar graph pooling methods, with the goal of answering the following questions:
Q1. Is PH capable of preserving topological information during pooling?
Q2. How does PH affect graph pooling in preserving task-specific information?
To this end, we showcase the empirical performance of TIP on two tasks, namely, topological similarity (Section 5.2) and graph classification (5.3). Our primary focus is to assess in which scenarios topology can enhance GP.
5.1 Experimental Setup
Models. To investigate the effectiveness of PH in GP, we integrate TIP with DiffPool, MinCutPool, and DMoNPool, which are the pioneering approaches that have inspired many other pooling methods. Additionally, as most pooling methods rely on GNNs as their backbone, we compare the widely used GNN models GCN 225] GIN 47 and GraphSAGE [5.. We also look into another two related and State-of-the-Ar GNN models, namely TOGL [9] and GSN 44, which incorporate topological information and graph substructures into GNNs to enhance the expressive power. Several other GP methods, namely Graclus 7 and TopK [I] are also compared. For model selection, guidelines provided by the original authors or benchmarking papers. Our method acts as an additional plug-in to existing pooling methods (referred to -TIP) without modifying the remaining model structure and hyperparameters. Appendix B.I provides detailed configurations these models.
follow the
Datasets. To evaluate the capabilities of our model across diverse domains, we assess its per- formance on a variety of graph datasets commonly used in graph related tasks. We select several benchmarks from TU datasets (32, OGB datasets (20] and ZINC dataset 45]. Specifically, we adopt molecular datasets NCII, NCI109, and OOBG-MOLHIV, bioinformatics datasets ENZYMES, PROTEINS, and DD, as well social network datasets IMDB- -IBBIIARRY and IMDB-MULT Fur- thermore, to investigate the several highly structured datasets (ring, torus, grid2d) obtained from the PyGSP library. Appendix B.2 provides detailed statistics of the datasets.
ability of our method, we conduct experiments on
Evaluation. In the graph classification task, all datasets are splitted into train (80%), validation (10%), and test (10%) data. Following the evaluation protocol in (50, [30,, we train all models using the Adam optimizer (24] and implement learning rate decay mechanism, reducing the learning rate from 10-3
3 to 10 10-5 with a decay ratio of 0.5 and a patience of 10 epochs. Additionally, we use early stopping based on the validation accuracy with patience of 50 epochs. We report statistics of the performance metrics over 20 runs with different seeds.
5.2 Preserving Topological Structure
In this experiment, we study Q1 about the ability of PH to preserve topological structure during pooling. Specifically, we assess the topological similarity between the original and coarsened graphs and G', by comparing the Wasserstein distance associated with their respective PDs D3 and Dj This evaluation criterion is widely used to compare the topological similarity of graphs [4]] 41]. We utilize Forman curvature on each edge of the graph as the filtration, which incorporates edge weights and graph clusters to better capture the topological features of the coarsened graphs 42
We consider the W-Wassesteein distance W (Di. Di = inf den ((a.y)=lll ylll as the
evaluation metric, where IT()) is the set of joint distributions 8(x,, y) whose marginals are D, and Dj, respectively. Note that we are not learning new filtration but keep fixed one. Rather, use learnable filtrations in training to enhance flexibility, and solely optimize Ltopo as the main objective.
We compare TIP with other pooling methods. Table Tableerepon reports the average W values on three datasets, demonstrating that TIP can improve dense pooling methods to large margin and have the best topological similarity. We visualize the pooling results in Fig. 3 for better interpretation, where isolated nodes with no links are omitted for clarity. It is evident that DiffPool, MinCutPool, and
7

---

Table I: Results to show the the topological similarity. bold value indicates the overall winner.
ability. Wasserstein distance (1) is used to assess
Datasets
Methods
ring
torus
grid2d
Graclus
37.62 +: 4.41
124.47 + 12.07
35.82 1: 0.93
TopK
14.24 1.06
35.15 - 4.78
84.12 + 2.21
DiflPool
234.57 + 9.49
237.89 + 20.66
146.91 = 6.05
DifiPoolTTPP
8.03 + 3.08
17.97 2.19
32.26 + 3.21
MinCutPool
232.60 + 10.81
248.51 + 15.69
155.16 + 21.79
MinCutPool-TII
18.11 5.59
11.38 2.21
58.71 = 9.84
DMoNPool
224.48 + 22.25
236.97 + 16.54
142.85 1 27.53
DMoNPool-TIP
16.10 4.80
17.34
4.76
52.26 + 5.75
Origzal
DaPPad
MaChatted
MrsCaPoo-TE1
DIAINPeed
Topk
Grada
Figure Coarsened graphs from different methods in the preserving topological structure experiment.
DMoNPool tend generate dense graphs and fail to preserve any topological structures. Conversely, our method, which incorporates topological features using PH, sparsifies the coarsened graphs and reveals certain essential topological structures. Notably, in the ring and torus datasets, large cycles clearly preserved by method. Besides, the grid2d dataset, despite having different spatial layout, exhibits similar topology to torus (with four adjacent nodes forming small cycle), resulting in similar shapes of their corresponding coarsened graphs. This indicates that the objective function indeed contributes to preserving topological similarity to some extent. Sparse pooling methods, which tend to preserve local topology, perform slightly better than the original dense pooling methods.
Table Test accuracy (1) of graph classification on benchmark datasets. bold value indicates the overall winner. Gray background indicates that TIP outperforms the base GP.
OCN
77,81 1.50
74.90
1.85
32.51
78.66 2.36
74,20 2.40
53.23 3.01
75.01 0.81
GIN
80.30
1.70
79.66
1.55
42.83 + 3.66
73.18 = 3.35
78.05 =: 3.00
72.65
3.04
55.28
3.16
76003
0.84
GraASAGE
80.85
1225
79.16
1.28
39.17
4: 3.28
76.67 4: 3.05
78.83 4: 3.07
76.80
2: 2.37
53.46 4: 2.39
76.18 1 1.27
TOGL.
80.53 2.20
78.27
1.39
46.09
+ 3.72
78.17 + 2,80
76.10 + 2.34
76.65 2.75
53.87 + 2.67
77.21 + 1.31
GSN
83.50
6.54
3.00
Graelus
3,46
75.60
3.70 72.60
Topk
DitiPool
77.64:t:1.6
76.50
73.15
7.09
76,60
DifPool-TiP
83,75 1:31
$1.09
1,65
65.05 1: 4.24
79.86 2: 3.12
82.12 2.53
76.50
3:13
$5.53 2.92
77.75
MinCuPeed
77.92+
75.88
2.06
39.83 2.63
78.25
3.84
79.15
73.80 3.54
53.87 2.95
75,60 0.54
MInCuPood-TIP
X0.17
1.20
79.48
1.37
46.34
3.88
79:33 + 3.27
90U.7 2:47
75.20 2.000-2.. 2.67
$4.47 2.27
77.18 0383
DMaePoool
78.03+11 1.64
76.63 1.94
40.82 +3.668
78.63 + 3.89
79.16 3.61
$4,07 + 3.08
76.30 1.34
DMcNPool-TIP
79:03
2:99
$4.23
76.70

---

PROTEINS
Figure 4: Graphs pooled with different methods in graph classification experiment.
5.3 Preserving Specific Information
In this experiment, we examine the impact of PH on GP in downstream tasks to answer Q2. We have observed in the former experiment that can preserve essential topological information during pooling. However, two additional concerns arise: (1) Does TIP continue to generate invariant sub-topology in the downstream task? (2) If so, does this sub-topology contribute to the performance of the downstream task? To address these concerns, benchmarks, where the accuracy achieved on these benchmarks serves as a measure of a method's ability to selectively preserve crucial information based the task hand.
evaluate TIP using various graph classification
We begin by visualizing the coarsened graphs this task, where edges are cut-off by a small value. From Fig. 4 we can clearly observe that our method manage to preserve the essential sub-topology similar to the original graphs, while dense pooling methods cannot preserve any topology. As discussed in [30), dense pooling methods achieve comparable performance when the assignment matrix is replaced by a random matrix. Here our visualization reveals that regardless the value of S. the coarsened graph always approaches to fully connected one. Sparse pooling methods, on the other hand, manage to preserve some local structures through clustering or dropping, but the essential global topological structures destroyed.
Table presents the average and standard deviation of the graph classification accuracy on benchmark datasets, where the results of GP and several baseline GNNs are provided. Experimental results demonstrate that TIP can consistently enhance the performance of the three dense pooling methods. While the original dense pooling methods sometimes underperform compared to the baselines, they are able to surpass them after integrating TIP.
Morcover, an intriguing observation can be found on ENZYMES dataset, where TOGL surpasses the baseline GNNs. TOGL in practice, incorporates PH into GNNs (GraphSAGE in our implementation). so this results underscores the significance of incorporating topological information for improved performance on ENZYMES. Further, our method demonstrates more significant improvements by augmenting the three dense pooling methods on the ENZYMES dataset. One possible explanation for the observed phenomenon that the coarsened graphs generated by our methods bear a striking resemblance to numerous frequent subgraphs present in this dataset [1O]. Such substructures may serve as indicators of unique characteristics within the graph, rendering them valuable for subsequent tasks. However, it is also worth noting that TOGL only exhibits marginal improvements or even undcrperforms on the other datasets. This suggests that simply integrating PH features into GNN layers does not fully exploit topological information. Conversely, injecting global topological invariance into pooling layers in our method yields superior performance.
To demonstrate the effectiveness of preserving the invariant sub-topology, we compared DiffPool-TIn with its variant counterpart, DiffPool-TIP-NL (no topological loss), by replacing Ltopo with the original C, in DiffPool (see Table/4in Appendix(M) A The training objective curve and the Wasserstein distance curve are presented in Figure both based on the ENZYMES dataset and fixed filtration (the same as in Section 5.2). From the figures, it is evident that the objective value decreases as the coarsened graphs become more similar in topology to the original graphs when using DiffPool-TIP However, when training without Ltopos the performance is inferior. Additionally, even when the

---

DIfPPoo-TTP DIMPoO--TIP-N
DiffPook- TIP
1.75
DiffPool-TPP TIP-NI
1.50
wacserstoin distance
abjective
1.25
200
160
0.75
0.50
100
0.25
50
20
40
60
100
120
0
20
40
6D
8D
100
120
Step
Step
Figure 5: The training curves of DiffPool-TIP and DiffPool-TIP-NL ENZYMES dataset. We show the average values and min-max range of objective and Wasserstein distance for multiple runs.
objective value converges, DiffPool-TIP-NL still exhibits changing topology, whereas DiffPool-TIP maintains stable topology, possibly benefiting from the stability of PH [4.. This also suggests that multiple suboptimal topologies may contribute equally to the objective. Our topology invariant pooling strategy consistently selects topologies similar to the original graph, which leads to better performance. Additional visualization results and analysis about the coarsened graphs obtained by DiffPool-TIP-NL can be found in Appendix
Aside from the graph classification task, Table presents the mean and standard deviation of prediction accuracy for the constrained solubility of molecules in the ZINC dataset, where mean square error is used as performance metric. We can observe that TIP can still boost the three pooling methods on regression task, which demonstrates that our proposed method can retain task-related informa- tion. Besides, we design an additional set of experiments in Appendix E.4] where the topological structure of the graph is highly relkvrelev.nt. Ablation study about the contributions of different modules are shown in Appendix
Table 3: Mean square error (L) of pre- diction results on ZINC dataset. A bold value indicates the overall winner.
ZINC
DiffPool DiffPool-TIP
0.34+0001
0.28
MinCutPool
0,42:10.01
MinCutPool-TIB
0.38+1001
E.5 Finally, to empirically demonstrate the expressive power of our proposed method, we provide experiment on distinguishing non-isomopppic graphs in Appendix E.6
DMoNPool
0.40+10.01
DMoNPool-TIP
0.35:10.01
Conclusion
In this paper, developed method named Topology-Invarian Pooling (TIP) that effectively integrates global topological invariance into graph pooling layers. This approach is inspired by the observation that the filtration operation in PH naturally aligns with the GP process. We theoretically showed that PH is at least as expressive as WL-test, with evident examples demonstrating TIP's s expressivity beyond dense pooling methods. Empirically, TIP indeed preserved persistent global topology information, and achieved substantial performance improvement on top of several pooling methods various datasets, demonstrating strong flexibility and applicability.
The potential limitation of our study is the heavy reliance of the proposed method on circular structures within graphs, potentially hindering its efficacy on tree-like graphs. Besides, our method lacks the ability to discriminate between graphs when the number connected components the only distinguishing factor. Our method can be extended to address this limitation by explicitly incorporating this information into the node features during the pooling process.
Acknowledgements
This work was supported by the National Key R&D Program of China under grant F022YFA 1003900. This work also supported by the Guangdong Provincial Key Laboratory of Mathematical Founda- tions for Artificial Intelligence (023312120100011
10

---

References
[1] Davide Bacciu and Luigi Sotto. A non-negative factorization approach to node pooling in graph convolutional neural networks. In AI IA 2019-Advances in Artificial Intelligence: XVIIIth International Conference of the Italian Association for Artificial Intelligence, Rende, Italy, November 19-22, 2019, Proceedings 18, pages 294-306. Springer, 2019.
[2] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, pages 874-883, PMLR, 2020.
[3] Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. Advances in neural information processing systems, 36, 2023.
[4] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving
graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-668, 2022.
[5] Cătälina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò. Towards sparse hierarchical graph classifiers. arXiv preprint arXiv:/811.0122 2018.
[6] Mathieu Carrière, Frédéric Chazal, Yuichi Ike. Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics, pages 2786-2796. PMLR, 2020.
[7] Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvec- tors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence. 29(11):1944-199 2007.
[8] Herbert Edelsbrunner and John I. Harer. Computational topology: an introduction. American Mathematical Society, 2022.
[9] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. 2019.
arXiv preprint arXiv:
[10] Tianyu Fu, Chiyue Wei, Yu Wang, and Rex Ying. Desco: Towards generalizable and scalable deep subgraph counting. arXiv preprint arXiv:2308. 08198, 2023.
[11] Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pages
PMLR, 2019.
[12] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1272. PMLR, 2017.
[13] Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceed- ings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9211-9219 2019.
[14] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling in graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[15] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[16] Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt. Graph filtration learning. International Conference on Machine Learning. pages 4314 4323. PMLR, 2020.
[17] Christoph Hofer, Roland Kwitt, Mare Niethammer, and Mandar Dixit. comnectiiit-oopimizze representation learning via persistent homology. In International conference on machine learning, pages 2751-2760. PMLR, 2019.
[18) Christoph Hofer, Roland Kwitt, Mare Niethammer, and Andreas Uhl. Deep learning with topological signatures. Advances in neural information processing systems, 30, 2017.
[19] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. arXiv preprint arXiv:2102.07835, 2021.
11

---

[20] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-13333,,, 2020.
[21] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with f2-guns. In The Eleventh International Conference on Learning Representations, 2022.
[22] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv: 1e..1/111000 1.01 2016.
[23] Chuntao Jiang, Frans Coenen, and Michele Zito. Finding frequent subgraphs in longitudinal social network data using a weighted graph mining approach. In Advanced Data Mining and Applications: 6th International Conference. ADMA 2010, Chongqing, China, November 19-21, 2010, Proceedings, Part I 6. pages 405-416. Springer, 2010.
[24] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 14/2.698)) 2014.
[25] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[26] Mehmet Koyuturk, Ananth Grama, and Wojeiech Szpankowski. An efficient algorithm for detecting frequent subgraphs in biological networks. In ISMB/ECCB (Supplement of Bioinfor- matics), pages 200-207, 2004.
[27] Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.
[28] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International conference machine learning, pages 3734-3743. PMLR, 2019.
[29] Yao Ma, Suhang Wang. Charu C Aggarwal, and Jiliang Tang. Graph convolutional networks with eigenpooling. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 723-731, 2019.
[30] Diego Mesquita, Amauri Souza, and Samuel Kaski. Rethinking pooling in graph neural networks. Advances in Neural Information Processing Systems, 33:2220-2231, 2020.
[31] Michael Moor, Max Hom, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In International conference on machine learning, pages 7045-7054. PMLR, 2020.
[32] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
[33] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[34] Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24: 1-21, 2023.
[35] Christopher W Murray and David C Rees. The rise of fragment-based drug discovery. Nature chemistry, 137 2009.
[36] Koji Okabe, Takafumi Koshinaka, and Koichi Shinoda. Attentive statistics pooling for deep speaker embedding. arXiv preprint 1rX1v:1803.10063, 2018.
[37] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitooo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
[38] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5470-5477, 2020.
[39] Bastian Rieck. On the expressivity of persistent homology in graph learning. arXiv preprint arXiv:2302.0980 09826, 2023.
12

---

[40] Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lhhman pro- cedure for graph classification. In International Conference on Machine Learning, pages $448-5458 PMLR, 2019.
[41] Joshua Southern, Jeremy Wayland, Michael M. Bronstein, and Bastian Rieck. Curvature filtrations for graph generative model evaluation. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[42] RP Sreejith, Karthikeyan Mohanraj, Jürgen Jost, Emil Saucan, and Areejit Samal. Forman curvature for complex networks. Journal of Statistical Mechanics: Theory and Experiment, 201 2016(6):063206, 2016.
[43] Teague Sterling and John J Irwin. Zinc 15-ligand discovery for everyone. Journal of chemical information and modeling, 55(11):2324-2333 2015.
[44] Nicolas Swenson, Aditi S Krishnapriyan, Aydin Buluc, Dmitriy Morozov, and Katherine Yelick. Persgnm: applying topological data analysis and geometric deep learning to structure-based protein function prediction. arXiv preprint (tth:201001602)) 2020.
[45] JunJie Wee and Kelin Xia. Forman persistent ricci curvature (fprc)- machine learning mod- els for protein-ligant binding affinity prediction. Briefings in Bioinformatics, 22(6))bbabl 136, 2021.
[46] Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierar- chical pooling. In International conference machine learning, pages 24017-24030. PMLR, 2022.
[47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018.
[48] Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, Yusu Wang, and Chao Chen. Neural approximation of graph topological features. Advances in Neural Information Processing Systems, 35:33357-33370, 2022.
[49] Chaolong Ying, Jing Liu, Kai Wu, and Chao Wang. A multiobjective evolutionary approach for solving large-scat scale network reconstruction problems via logistic principal component analysis. IEEE Transactions on Cyberettcss, 53(4):2137-2100, 2021.
[50] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[51] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 10737-10745. 2021.
[52] Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2896-2906. PMLR, 26-28 Aug 2020.
13

---

Table 4: Unsupervised loss functions of graph pooling
Method DiffPool
C
Le
A, S.
1 - 1= (S,)
H
MinCutPool
Tr(s AS)
$ S
1e
Tr(S DS)
||
vC
F
DMoNPool
1 .Tr (S BS)
ST |S S/S
1c
vC
|Σ 11
vC
p
A
Dense Graph Pooling Methods
Generally, dense graph pooling methods follow hierarchical architecture, but their motivations differ. DiffPool suggests that nearby nodes should be pooled together, drawing on insights from link prediction and the assignment matrix S should be approximate to one-hot vector that the clusters are less overlapped with each other. MinCutPool, on the other hand, adapts the normalized regularizer for pooling. This encourages strongly connected nodes to be pooled together, ensures orthogonal cluster assignments, and promotes clusters of similar size. Moreover, DMoNPool additionally proposes a regularization optimize the modularity quality of clusters so that the pooling can generate high quality clusters approach to ground truth. In summary, each of these methods introduces two types of unsupervised loss functions: the reconstruction loss L,, which regulates how the coarsened graph is reconstructed to retain some cluster structure, and the other is the cluster loss Le. which prevents convergence to local minima. The detailed formulations of these loss functions are provided in Table 4 where || || denotes the Frobenius norm, H denotes the entropy function, DD" the 2m
S, the i-th row of S, D is the degree matrix, C is the number of clusters, B A modularity matrix, respectively.
B Experimental Setup
B.1 Implementation detail
Hyperparameters. For dense pooling methods, the pooling ratio ranges from 0.5), the number of pooling layers is 2, and the hidden dimension selected from {32, 64]. For the Graclus method we use 2 pooling layers, while for TopK we use 3 pooling layers with a pooling ratio of 0.8. The batch size for all models is uniformly set to 20, and the maximum number of training epochs is 1000. For the graphs obtained from the PyGSP library (ring, torus, grid2d), the number of nodes in each graph is fixed at 64.
Model configuration. All the methods are implemented using PyTorch and PyG 37 9 The compared methods are implemented following the implementations provided in the PyG library In the case of DiffPool, it uses a 3-layer GraphSAGE in each pooling layer, while MinCutPool I-layer GCN before pooling and 1-layer GNN 33 in each pooling layer.
and DMoNPool Note that in DiffPool, the GNNs in Eqs. [ and 4 are different, while in MinCut and DNoNPool they are the same one, what their do in the original papers. TopK and Graclus a l-layer GNN 33 TOGL is implemented using a 3-layer GraphS as it has demonstrated superior performance on graph classification tasks (see Table For the baseline GNN models (GCN, GIN, and (raphSAGE), we use 3 layers with mean/max pooling. In our model, TIP is incorporated as a plugin to existing pooling methods, without modifying the remaining model structure and hyperparameters. We replace the reconstruction loss L, with Leopo while keeping the cluster loss L. unchanged. In the case of MinCutPool and DMoNPool, our resampling strategy is added after their original normalization of the coarsened graphs. In preserving topological structure experiments, we initialize node features as the concatenation of the first ten eigenvectors of graph Laplacian matrices. Moreover, we follow the settings in previous works 19 18 to extend D2 as follows: (I) each cycle is paired with the edge that created it; (2) edges that do not create cycle (still in this circle) are assigned 'dummy' tuple value, such as [[))) (3) all other edges will be paired with the maximum value of the filtration fmaz. In practice we set fmaz plus a constant as infinity
based on
14

---

Table 5: Statistics of datasets
Dataset
#Graphs
Nodes
#Avg. #Avg.Edges
#Features
#Classes
ENZYMES
600
32.63
62.14
18
PROTEINS
1113
39.06
72.82
2
NCII
4110
29.87
32.30
37
NC1109
4127
29.68
32.13
38
DD
1060
232.9
583
1000
19.8
193.1
2
IMDB-MULTI
1500
13
65.94
OGBG-MOLHIV
41127
25.5
27.5
2
ZINC
249456
23.2
49.8
of destruction time. Therefore, D consists as many tuples as the number of edges m. Code open-sourced at htttpp:://gttuub.coo/////te///e/
B.2 Dataset Statisties
The statisties of datasets used in this paper are summarized in Table where show the number of graphs, average number of nodes, average number of edges, number of features, and number of classes. We use the default dataset settings from PyG library Highly structured datasets (ring, torus, grid2d) are obtained from the PyGSP library
C Theoretical Expressivity of TIP
Theorem 1. The self-loop augmented I-dimensional topological features computed by PH is sufficient enough to be at least as expressive as I-WL in terms of distinguishing non-isomorphic graphs, i.e. if the 1-WL label sequences for two graphs G and G diverge, there exists an injective filtration f such that the corresponding 1-dimensional persistence diagrams D, and D' are not equal.
Proof. Assume that G and G' have and n' nodes, and the label sequences of them diverge some iteration h, which means there exists at least one label whose count is unique. Let nodes u and u' be the nodes with unique count G and g', respectively. Denote La ;= (71 12, ...} as an enumeration of the finitely many hashed labels at iteration h. We can build a filtration function by assigning vertex v with label ( to its index, i.e. f(v) == except that f(u) = n + n' + and f(''= + n' + 2. The filtration of edge (u, w) is defined as [u, w) max(f()) [(w),, and for isolated nodes v, the filtration of self-loop edges [(u, v) = f(v). Therefore, node with unique label count and its connected edges always correspond to the largest filtration value. Note that the 1 I-dimensional PD has been extended to have the same cardinality as the number edges. If node u' forms circle, the creation of this circle is related to the edge with the largest filtration; if node u' does not form circle, the corresponding edges lie the diagonal of D, with unique coordinates; otherwise node u constitute a circle while does not, then the corresponding edges lie in different parts in D and Dy. Hence, D, + D/.-
To demonstrate that TIP is more expressive than other dense pooling methods, we provide examples of graph pairs that cannot be distinguished by 1-WL but can be by TIP. We present an example of such non-isomorphic graphs in Fig. [ where in the second graph the edge connecting two triangles does not form a circle. This edge corresponds zero persistence and is eliminated TIP. Consequently, the two originally non-isomorphic graphs can be easily distinguished. Provided that the three sufficient conditions proposed in [3] are satisfied, the pooling layers retain the same level of expressive power GNN. In TIP, the reduction of node features remains unaltered, thereby fulfilling the three conditions. Additionally, TIP is capable of distinguishing certain non-isomorphic graphs,
html
15

---

indistinguishuble
TIP
distinguishable
Figure A pair of non-isomorphic graphs that cannot be distinguished by 1-WL but can be distinguished by TIP.
indicating its superior expressive power compared to conventional dense pooling methods such as DiffPool, MinCutPool, and DMoNPool.
Proposition 1. TIP is invariant under isomorphism.
To prove this statement, adopt the following lemma 39
show the isomorphic property of PH.
Lemma 1. Let 9n and G2 be two isomorphic graphs. For any equivariant filtration f, the corre- sponding persistence diagrams are equal.
In TIP, the filtration f implemented using MIP, ensuring the equivariant property of filtration. Moreover, our resampling operations Section 4.2 are equivariant. Therefore, the two isomorphic graphs after the resampling and persistence injection operations are still isomorphic to each other. Now we are able to prove Proposition 1.
Proof. For feature-level invariance, let X E Raxd be the node features, P E {0, 1]nxx be the permutation matrix, Roxx' be the assignment matrix, and PX be the permutated node features. The node feature map after pooling is denoted as X' Raa'xd then we have X' X.
we permute using a permutation matrix the permutated node features after pooling are
(S (PX) S
which proves the isomorphism invariant property of pooling at feature level.
For connectivity-level invariance, the connectivity after pooling is denoted as A' E ga'xn', then we have A' S AS. If permute using a permutation matrix P, the permutated connectivity after pooling is
A' - PST (PS) = T AS.
This completes the proof.
D Empirical Evidence
We conduct experiments on the NCII dataset and plot the heatmap of the coarsened adjacency matrix in Fig. 7 where we can observe that the edge weights DiffPool may span a wide range due the involvement of multiple multiplications in their generation. For MinCutPool and DMoNPool, the edge weights are normalized by degree to mitigate numerical explosion. However, this normalization leads to the edge weights becoming excessively smooth and lacking sparsity. Learnable filtration based performs effectively on unweighted graphs; however, none the existing GP methods are capable of appropriately handling the adjacency matrix.
16

---

70
15
10
(a) Difyrool-layer-
(b) DiffPool-layer-2
020
04
035
030
01
0.00
(c) MinCutPool-layer-1
(d) MinCutPool-layer-2
0.04
0.14
0.03
008
002
(c) DMMNPoolllayer-1
(f) DMoNPool-layer-2
Figure 7: Heatmap of the coarsened adjacency matrix in terms of DiffPool, MinCutPool, and DMoNPool on NCII dataset.
E
Additional Experiments
E.1
Visualization of persistence diagrams
We visually represent the I-dimensional PD of graphs before and after applying TIP in of ring and grid2d datasets, as shown in Fig. g As described in Appendix B.]] in the original graphs we initialize node features with the eigenvectors of the graph Laplacian matrices. Consequently. the features of different edges exhibit slight variations, resulting in multiple nonoverlapping points in the PDs. Upon applying TIP, we can clearly observe that the one-dimensional topological features related to cycles remain similar to those in the original graphs. This demonstrates TIP's ability to preserve cycles.
E.2 Running time comparison
We compare the rumning time (in seconds) of TIP on different datasets. The experiments are conducted using an AMD EPYC 7542 CPU and a single NVIDIA 3090 GPU. We utilize the default settings from the graph classification experiments. We report the average running time of 50 epoches training Table 6 worth noting that TIP performed times for pooling layers, thus the inclusion of TIP does not impose significant computational burden.
17

---

Original
DifPPool-TIP
MinCutPool-TIP
DMoNPool-TI
ring
peprttice aggn
grid2d
32
Figure 8: Persistence diagrams of graphs before and after applying TIP in terms of ring and grid2d datasets.
Table 6: Average running time (seconds) comparisons on different datasets.
Datasets
Methods
NCII
PROTEINS
ENZYMES
DiffPool
209.48
56.55
30.61
DiffPool-TIP
339.37
92.06
49.65
MinCutPool 145.99
38,22
27.34
MinCutPool-TII
296.06
79.42
41.17
DMoNPool 124.89
35.07
19.35
DMoNPool-TIP
305.63
81.34
43.82
E.3 Visualization of coarsened graphs without preserving topology
We present some coarsened graphs that do not preserve topology (Dif in Fig. 9 These graphs contribute equally to the objective in the graph classification task, but their topologies are different. A similar observation was made by 30), who found that randomly generated graphs show equivalent performance. In DiffPool-TIP-NL. other topology-related modules in TIP are preserved, allowing some topological information to be injected into the three results shown in Fig. 9 Guided by the Ltopo DiffPool-TIP tends to select the results that are most similar to the original graph among all the options. Experimental results in Fig. demonstrate that this type of topology is superior and leads to better performance on downstream tasks.
E.4 Topology relevant experiments
To further demonstrate that our proposed method can effectively capture the topological features in graphs, design experiment where the topological structure of the graph is highly relevant. We generate a synthetic dataset named Cycles, comprising two balanced 2-class sets of 1000 graphs each. This dataset consists of either single large eycle (class 0) connected large cycles (class 1),
Original
Result
Result
Result 3
ENZYMES
Figure 9; Several coarsened graphs with CMfPool-TIP-Ny. that contribute equally to the objective.
18

---

Table 7: Classification results on synthetic datasets
Cycles
2-Cycles
DiffPool
54.3 = 1.1
50.0 + 2.2
DiffPool-TIP
65.1 2.7
51.4 = 2.8
MinCutPool
54.2 = 2.6
49.0 = 3.6
MinCutPool-TIP
65.0 2.9
50.4 = 2.9
DMoNPool
55.0 2.7
50.0 2.6
DMoNPool-TIP
68.7 + 2.7
50.0 + 3.6
resembling digital numbers "0" and "8", respectively. The distinguishing factor between the classes lies in the presence of cycles. highlighting the significance of the graph's topological structure in classification. The node numbers range from 10 to 20, with 3-dimensional random node features generated. For model configuration, we uniformly use 1 1-GCN plus 1-pooling layer. The evaluation criteria remain consistent with those outlined in our paper. The experimental results in Table 7 demonstrate the effectiveness of TIP in leveraging topological features to significantly outperform the comparable pooling methods.
Additionally, to evaluate our method's performance on graphs with different number of connected components, we generated synthetic dataset named 2-Cycles, comprising two balanced two-class sets of 1,000 graphs each. This dataset consists of either two disconnected large cycles (class 0) or two large cycles connected by single edge (class 1). The distinguishing factor between the classes is the number of connected components. The node numbers range from 10 to 20, with three-dimensional random node features generated. For the model configuration. we uniformly employed one GCN layer plus one pooling layer. Experimental results in Table 7 indicate that our method is not effective in distinguishing similar graphs with different connected components. This aligns with our expectations, as our method does not explicitly incorporate such information, given that most graphs in real-world datasets are connected.
E.5 Ablation study
To assess the contributions of different modules in our TIP model, we conduct comprehensive ablation studies on NCII, PROTEINS, ENZYMES, and IMDB-BINARY datasets. We utilize examine five ablated variants of TIP: (i) with no resampling (TIP-NR), (ii) with no persistence injection (TIP-NP), (iii) with no topological loss function (TIP-NL), (iv) with O-dimensional topological features (TIP-0), (v) with fixed filtration (TIP-F). All these variants are applied on three baseline pooling methods.
As depicted in Table 8 ablating any of the above modules resulte in performance degradation compared to the full model, thus indicating the importance of each designed module in the success of TIP. Additionally, on all three datasets, the resampling module significantly enhance the classification outcomes, while its removal lead substantial performance drop. Without resampling, the learnable filtration will treat edges equally, resulting in the inclusion of nonsensical topological information. In some cases, this even impede the model's performance, observed in the injection variants which perform worse than their counterparts on the PROTEINS dataset.
Another noteworthy observation is that even in the absence of the topological loss function Lespo GP can still benefit from incorporating PH. This could attributed to the fact that the learnable filtration can inherently capture certain essential topological information to some extent. Furthermore, our model can still reap the benefits of the topological loss function, which indirectly guides the pooling process, even without explicitly injecting topological information using persistence.
Further, we provide an ablation study our topological loss term by replacing it with the Wasserstein distance. While the Wasserstein distance is a powerful metric for comparing persistence diagrams, its computation can be computationally intensive, particularly when dealing with high- -igeniinensi vectorized representations. Therefore, it significantly increases our training time in practice. We denote the variant of using Wasserstein distance as "TIP-W", Here we present the ablation study results on two datasets. We can observe that TIP-W has competitive performance compared with the full version TIP (with our proposed loss term), and outperforms the variant TIP-NI (no loss term). Initially, we design our Liopo to avoid the high computational complexity of Wasserstein distance, but
19

---

Table 8: Test accuracy of graph classification in ablation study experiments.
Datasets
Methods
NCI1
PROTEINS
ENZYMES
IMDB-BINARY
DifiPool
77.64 + 1.86
78.81 3.12
48.34 + 5.14
73.15 3.30
DifiPool-TIP-NR
80.82 1.71
77.89
4.07
55.43 + 2.81
75.00 + 2.64
DifiPool-TIP-N
81.99 1.15
79.30 1.26
62.22 3.13
75.85 2.85
DifiPool-TIP-NL.
=
79.11 2.01
58.77 5.15
76.10 3.78
DiffPool-TIP-W
$3.02
78.25 = 1.63
62.15 4.44 4.43
#3.66
OifiPool-TIPA
82.45 = 1.40
79.12 = 1.63
56.88 = 4.96
76.25 2.33
DiffPool-TIP
83.21 1.55
77.91 3.46
60.24 5.15
75.75
#319
DifiPool-TIP
83.75 1.70
3.12 79.86
65.05 + 4.24
76.40 3.13
MinCutPool
77.92 = 1.67
78.25
3.84
39.83 = 2.63
73.80 3.54
MinCutPool-TIP-NN
79.68 1.38
78.23
2.92
22.11
74.35 + 1.80
MinCutPool-TIP-NP
78,81 + 2.07
78.92 3.335
45,56 = 2.81
74.65 3.24
MinCutPool-TIPA..
78.48 1.86
78.40
45.26 = 4.14
74.90
MinCutPool-TII....
80.06 = 0.78
79.51 4.22
46.12 1.23
74.50
MinCutPool-TIPP
78.18 1.34
79.64
33.04
11.4+122
74.83 #
MinCutPool-TIP
76.65 + 1.72
19.40+3...
44.10 + 2.68
73.80 + 1.72
MinCutPool-TIP
80.17 1.29
79.73 +.22
46.34 + 3.85
75.20 2.67
DMoNPool
78.03 1.64
#3.89
40.82 = 3.68
73.50 3.01
DMONPool-TIP-NR
79.26 = 1.01
78.72 + 1.30
42.51 4.40
73.75 3333
DMoNPool-TTPP-N
79.60 0.97
79.44 1.68
44.36 + 3.98
73.50 3.35
DMoNPoool-IPP-NL
79.08 1.83
79.26
1.70
43.35 3.90
74.00 2276
DMoNPoollTIP--W
79.48 1.50
79.70
2.95
45.45 = 1.34
74.00 2.91
DMONPOol-TTP--0
79.23 0.89
79.24
3.44
41.67 2.04
73.60 2
DMoNPool-TIP--F
78.83 + 1.99
79.44 3.39
42.88
+ 2.25
73.60 2.87
DMONPPol-TTIP 79.68 1.38
79.73 3.66
45.84 + 5.32
74.25 2.93
we suprised to find that TIP also marginally outperforms TIP-W in numerous instances, potentially attributed efficacy feature transformation and high-order statistical features. These elements serve feature augmentation mechanism enhance the persistence diagrams.
In Section we provide theoretical analysis that I-dimensional topological features are powerful enough to distinguish non-isomorphic graphs, thus eliminating the necessity of incorporating 0- dimensional features. this section, we provide empirical evidence about incorporating additional O-dimensional features to support our claim. The results of variant TIP-0 indicates that the inclusion of O-dimensional topological features merely increases runtime and has no benefits for the overall performance. This explains why merely consider 1 I-dimensional topological features in our method.
As for the ablation of filtration functions, we employ an MLP with randomly initialized and fixed parameters the filtration function. Using learnable filtrations leads to significant gains over random filtration functions in more than half of the cases. In some cases, randomly initialized filtrations may happen to be close the learned filtrations, but this does not consistently occur.
Overall, our ablation study supports the indispensability and effectiveness each module in the TIP model, further underscoring their contributions to its success.
E.6 Evaluation of expressive power
The growing interest in the expressive capability of graph pooling has been prominent in recent studies [3] graph pooling model based GNNs is deemed more effective as it can differentiate larger set of non- -somoohhc graphs by producing unique representations for each. Graph pooling integrated with appropriately designed message-passing layers proves to as competent as the WL test in distinguishing graphs. Understanding the expressive capacity of graph pooling aids in selecting between existing pooling operators or crafting novel ones. Furthermore, empirically assess the expressive capacity of our proposed approach, TIP, conduct experiments on the EXPWLI dataset
20

---

Table 9: Classification results on EXPWLI dataset.
Pooling
Test Accuracy
DiffPool
97.0 + 2.4
DifiPool-TIP
99.3 = 0.5
MinCutPool
98.8 + 0,4
MinCutPool-TIP
99.9 0.1
DMoNPool
99.0 = 0.7
DMoNPool-TIP
99.7 = 0.1
following the experimental setup detailed in 13 Each graph pair (G;, H:) in EXPWL1 consists of two non-isomorphic graphs distinguishable by WL test, which encode formulas with opposite SAT outcomes. Therefore, any GNN that has an expressive power equal to the WL test can distinguish them and achieve approximately 100% classification accuracy the dataset. The classification outcomes on the EXPWL1 dataset are shown in Table g which reveal the notable improvement in the expressive capacity of graph pooling achieved through proposed method in empirical evaluations.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our focus aims towards boosting graph pooling with persistent homology, motivated by the observation that they two align very well.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 long 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: In Sec. 6 we mentioned that the proposed method relies on circular structures
within graphs, potentially hinders efficacy on tree-like graphs.
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn 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-tex, system might not be used reliably to 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification:
All assumptions and complete proof are provided in the Appendix
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 or referenced in the statement of any theorems.
The proof's 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 complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide implementation details and hyperparameters in Appendix B.1 We also submit codes to click and run.
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 be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If 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, 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 via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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 or instructions for how to construct the dataset).
(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 possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
23

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the datasets are obtained from open source libraries, and relevant links are provided in Sec. B.2 We also submit codes click and run.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
ollccy for more details.
While encourage the release of code and data, 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
Sonblii/g //nips.ccppbbll/ wwwcc//giiies/eeeee hat////oooSueiisseeeeeee weabbbimssiiee SttSSuabissoooooiiiioo.. onPolicy) 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, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental settings are provided in Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, 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]
Justification:
The error bars are provided each table related to experiments.
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, confi- dence intervals, statistical significance tests, 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, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call 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 or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror 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 or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: provide sufficient information on the computer resources Sec. E.2
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes.
Guidelines:
The answer NA means that the authors have not 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.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is advance the field of Machine Learning, There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 not 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 improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it 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 are 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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: No use of pretained models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Properly credited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the 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 are released, the license, copyright information, and terms use in package should be provided. For popular datasets, thcoe com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
26

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part 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 an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
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 the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
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 the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 we 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.
27


Reviews:
[{"review_id": "NisUffnd2b", "reviewer": "Reviewer_fBuZ", "summary": "The paper introduces TIP (topology-invariant pooling), a PH-based pooling layer. The proposed approach involves resampling graph connections from soft-cluster assignment matrices and adjusting edge weights using persistence information derived from 1-dimensional diagrams. TIP leverages a loss function designed to maintain topology by leveraging vectorizations of the 1-dimensional diagrams. Experimental evaluations conducted on synthetic and real classification datasets illustrate the performance of the proposed method.", "questions": "1. For the non-zero persistence tuples, are the death times always equal $\\infty$ (or f_max + constant)? If so, isn't TIP exploiting only (non-persistent) homology?\n2. Figure 2 does not show self-loops after the resampling procedure. \n3. Including the definition of simplicial complexes (SCs) would be helpful. Are graphs (with self-loops) 1-dimensional SCs? Do self-loops count as independent cycles?\n4. How can the hierarchical view of PH in Figure 1 be obtained from sublevel filtrations as defined in Section 3? In other words, how can we achieve a decreasing sequence of subgraphs using sublevel filtrations?\n5. Where does the proposed method's expressivity stand compared to other graph pooling layers (see [2])? The Appendix provides a brief discussion. I think that discussion could be added to the main paper.\n6. Consider the same setting as Theorem 4. Isn't PH based on $D_1$ **strictly** more expressive than 1-WL? To prove this additional gain, it suffices to show a pair of graphs $G, G'$ with $D_1(G) \\neq D_1(G')$ that 1-WL cannot distinguish. Wouldn't G=two triangles and G'=hexagon (where all nodes have the same features) be an example of such a pair?\n7. How does the proposed model perform using a fixed (non-trainable) random filtration function (e.g., an MLP where the parameters are fixed)?\n\n[1] - Topological GNNs, ICLR 2022.\n\n[2] - The expressive power of pooling in Graph Neural Networks, NeurIPS 2023.", "limitations": "The paper mentions as limitation the \"heavy reliance of the proposed method on circular structures within graphs\" in Appendix F.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Flexibility: TIP is agnostic to the GNN method and can be easily combined with GNN layers\n- Novelty: This combination of PH for graph pooling tasks is novel.", "weaknesses": "- The theoretical part of the paper does not seem very relevant and novel. Theorem 4.1 only states the **existence** of a filtration that is at least as expressive as the 1-WL test, which has limited impact in practice. Similar results are well-known in the literature (e.g., [1]). Also, in the analysis, we must allow filtration functions f to leverage graph structure, not only node features as defined in the paper. Finally, it seems that Theorem 4.1 can be easily turned into a strictly more expressive statement (see question below). \n- Another main concern revolves around the motivation for preserving cycles in general-purpose graph coarsening methods. Overall, I found the discussion/motivation for this design choice hand-wavy. \n- While the proposed method improves over the base pooling layers (e.g., DiffPool), it does not lead to significant gains over some (pooling-free) models in Table 2. Also, the experiments include only 1 OGB dataset --- I recommend adding ZINC or at least another OGB dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1:Concerns about theory and filtrations.\n\n>The theoretical analysis of the expressive power and other properties of graph pooling is crucial in this field, as it aids in selecting between existing pooling operators or developing new ones [1]. Beyond TOGL [2] that proves the expressivity of PH using **0-dim** features, our theoretical novelty lies in the further proof that PH with **1-dim** features is also as expressive as WL.  Additionally, in Appendix E.6, empirical results demonstrate that our proposed method can be more effective in distinguishing non-isomorphic graphs, indicating that our model can learn to approximate these filtrations in practice.  \n>\n>Furthermore, we apply the filtration function f to the hidden representations $\\mathbf{X}^{(l)}$ obtained through GNNs (see Eq. (4) and (6)), where graph structures are considered. This type of operation is also found in relevant literature [2, 5]. \n\nW2: Motivation for preserving cycles\n\n>In graph pooling, the notion of a good/useful latent graph topology is less obvious. Many efforts have been devoted to learning representations with additional regularizers, among which PH is frequently used for data with topological structures. Since preliminary experiments (in Table S3) showed that using 0-dim topological features merely increases runtime, our proposed method focuses only on 1-dim persistence diagrams, which is explained as preserving cycles in graph coarsening. This claim is also confirmed by Reviewer HRv2 with literature evidence [3, 4].\n\nW3: No significant gains over some pooling-free models. Experiments on ZINC.\n\n>Our primary objective is to devise a novel mechanism to **boost** graph pooling methods rather than proposing a new method to surpass existing GNN models. Our performance depends on how the original pooling methods perform. Experimental results demonstrate that the proposed method achieves substantial performance improvement when applied to several pooling methods. Additionally, our method outperforms strong pooling-free baselines such as GSN in all but one case.  \n>\n>Furthermore, we conducted an additional experiment on ZINC dataset. Following the settings in [7], we used the graph-level prediction task, and the results of MAE are shown in Table S1. Our models consistently outperform three dense pooling methods, demonstrating their ability to combine the benefits of both graph pooling and persistent homology.\n\nQ1: For the non-zero persistence tuples, are death times always equal\n>It is a well-established practice to extend persistence diagrams to mitigate numerical issues, as demonstrated in previous studies [2, 6]. The persistence tuples with non-zero values have identical death times but distinct birth times determined by their filtration values, resulting in varying persistences. Consequently, TIP leverages persistent homology to enhance graph pooling methods.\n\nQ2: Fig. 2 does not show self-loops\n>We have revised Fig. 2. The new version is provided in PDF. \n\nQ3: Definition of simplicial complexes. \n>A brief definition of simplicial complexes has already been discussed in Sec 3, lines 107-112. Graphs with self-loops can be considered low-dimensional simplicial complexes containing only 0-simplices (vertices) and 1-simplices (edges). Self-loops are counted as cycles.\n\nQ4: The hierarchical view of PH in Figure 1\n>In persistent homology, given a filtration function $f$, we can get a finite set of values $a_n > \\cdots > a_1$ and generate a sequence of nested subgraphs of the form $\\mathcal{G} = \\mathcal{G}_n  \\supseteq \\ldots  \\mathcal{G}_k \\ldots \\supseteq \\mathcal{G}_0 \\supseteq \\emptyset$, where $\\mathcal{G}_k = (V_k, E_k)$ is a subgraph of $\\mathcal{G}$ with $V_k:=$ { $v \\in V \\mid f(\\mathbf{x}_v) \\leq a_k$} and $E_k:=${$(v, w) \\in E \\mid \\max (f(x_v), f(x_w)) \\leq a_k$}. This process is interpreted as the hierarchical view of PH in Fig. 1. As the value decreases, a decreasing sequence of subgraphs is obtained.\n\nQ5: Expressivity issues\n>A theoretical discussion is provided in Sec 4.3, lines 209-213, asserting that the proposed method is more expressive than dense pooling methods, which are discussed in this paper. Additional empirical evaluation of expressive power is presented in Appendix E.6. In our revised manuscript, the empirical conclusions will be integrated into the main paper in Section 4.3.\n\nQ6: Isn't PH based on 𝐷1 strictly more expressive than 1-WL? \n>Our final conclusion aligns with your statement. The proof consists of two stages: First, we prove that the expressive power of PH is at least as strong as WL, which is Theorem 4.1; Second, we provide specific examples, as you mentioned, where PH exhibits greater expressive power than WL. Thus, the final conclusion is that PH's expressive power surpasses that of WL. In the discussion following Theorem 4.1 and in Appendix C, we present statements similar to yours. We apologize for any ambiguity in our previous statements. In our revised manuscript, we will integrate the two stages into Theorem 4.1.\n\nQ7: What if using a fixed (non-trainable) random filtration function?\n>Thank you for the valuable comment, which is instrumental in demonstrating the effectiveness of using learnable filtrations in our method. Following your suggestions, we employ an MLP with randomly initialized and fixed parameters as the filtration function, named as **TIP-F**. Additional experiments are conducted on four benchmark datasets, as shown in Table S2. Overall, learnable filtrations outperform TIP-F, although in some cases, TIP-F achieves similar performance.\n\n>[1] The expressive power of pooling in graph neural networks. NIPS 2023.  \n[2] Topological graph neural networks. ICLR 2022.  \n[3] Topological autoencoders. ICML 2020.  \n[4] Connectivity-optimized representation learning via persistent homology. ICML 2019.  \n[5] Graph filtration learning. ICML 2020.  \n[6] Deep learning with topological signatures. NIPS 2017.  \n[7] Rethinking pooling in graph neural networks. NIPS 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2Ia0egIpQy", "reviewer": "Reviewer_k5BH", "summary": "This paper proposes a new and systematic way to integrate persistent homology into GNNs for improved performance.  Rather than applying PH in a brute force manner as much existing work does, this work adapts the method based on the coincidence between the graph pooling mechanism and the filtration of PH.  The work takes advantage of the dynamic nature of PH via the filtration and results in improved performance in message passing.", "questions": "GNNs are known to encompass other NN models and architectures, such as CNNs and transformers.  Is the approach adaptable to these special cases of GNNs?  Does the performance also hold up in machine learning tasks, such as image classification?  Would the theoretical guarantees also need to be adapted?", "limitations": "Limitations were considered in the check list, however, I would like to see these concerns integrated into the paper.  In addition, it would be helpful to have examples and demonstrations of the limitations of the method.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This was a very nice paper that studies an important problem and proposes a novel approach using persistent homology.  In my mind, this is perhaps among the first most convincing applications and demonstrations of the relevance of persistent homology to deep learning theory and implementations.", "weaknesses": "The writing style of the paper could be improved, benefitting from a spell and linguistics check.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Questions: Is the approach adaptable to these special cases of GNNs? Does the performance also hold up in machine learning tasks, such as image classification? Would the theoretical guarantees also need to be adapted?\n\n>The proposed approach is adaptable as long as the data can be represented as graphs with specific topological structures. There is no need to modify the theoretical guarantees.\n\nLimitations: I would like to see these concerns integrated into the paper. In addition, it would be helpful to have examples and demonstrations of the limitations of the method.\n\n>Thanks for your valueable comment. In our revised manuscript, we will relocate the discussion of limitations to Section 6, Conclusion. The limitations are evident: tree-like graphs have no cycles, rendering the one-dimensional persistence diagram meaningless. Additionally, in our response to Reviewer 3dRY, we provide supplementary experiments on synthetic datasets, demonstrating that one limitation of our method is its inability to distinguish between graphs when the number of connected components is the only differentiating factor.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oxyCyuhrPn", "reviewer": "Reviewer_3dRY", "summary": "This paper proposes a topology-based graph pooling layer, TIP. TIP fits easily with the current graph pooling frameworks. Once the pooled graph is obtained from any existing graph pooling techniques, the authors make this pooled graph adaptable to persistent homology. They consider the PH of this graph and optimize it by minimizing the topological loss function between the current persistence diagram and  original persistence diagram. The authors show experimental results on some synthetic and real-world datasets.", "questions": "1. What happens when you consider graphs with more than one component? How does TIP perform in that scenario compared to other pooling mechanisms? \n\n2. Have you tried other ways to incorporate $L_{topo}$? For e.g., by choosing a different vectorization of PDs such as persistence images or rational hats?", "limitations": "Yes, the authors have discussed limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. It is, indeed, a new idea to combine PH for graph pooling to maintain topological information in the graph during pooling. \n\n2. Experiment to show that the proposed method preserves important topological features is well-chosen.\n\n3. The paper provides experimental evidence that addition of TIP into a standard GNN framework improves the performance on most datasets for graph classification.", "weaknesses": "1. Theorem 4.1 is incorrect as stated. Only the 1-dimensional topological features computed by PH cannot be as expressive as 1-WL test in distinguishing non-isomorphic graphs. Consider two graphs with no loops, with different numbers of vertices. 1-WL test will be able to distinguish these graphs while 1-dimensional topological features computed by PH will not be able to. One would need to use the 0-dimensional topological features computed by PH. Refer to [1]. Adding self-loops is just a proxy for counting the number of vertices, which can be done using 0-dimensional features. \n\n2. Moreover, the authors, in [1], have already shown that PH is at least as expressive as 1-WL test. Hence, the theoretical contribution of the paper does not seem significant.\n\n[1]: Topological Graph Neural Networks, Horn et.al", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: Theorem 4.1 is incorrect as stated. Only the 1-dimensional topological features computed by PH cannot be as expressive as 1-WL test in distinguishing non-isomorphic graphs. Consider two graphs with no loops, with different numbers of vertices. 1-WL test will be able to distinguish these graphs while 1-dimensional topological features computed by PH will not be able to. One would need to use the 0-dimensional topological features computed by PH. Refer to [1]. Adding self-loops is just a proxy for counting the number of vertices, which can be done using 0-dimensional features.\n\n>As stated in our proof of Theorem 4.1, adding self-loops results in additional cycles, which are reflected in the diagonal of one-dimensional persistence diagrams (PDs). Consequently, the augmented one-dimensional PDs can distinguish graphs with different numbers of nodes, as they correspond to different numbers of points in the one-dimensional PDs. Therefore, this distinction can be achieved using 0-dimensional or 1-dimensional features. Our method can be easily extended to integrate both 0-dimensional and 1-dimensional features, which we denote as TIP-0. Preliminary experiments, shown in Table S3, indicate that the inclusion of zero-dimensional topological features merely increases runtime. Thus, our proposed method focuses solely on 1-dimensional PDs.\n\nW2: Moreover, the authors, in [1], have already shown that PH is at least as expressive as 1-WL test. Hence, the theoretical contribution of the paper does not seem significant.\n\n>In our response to reviewer fBuZ, we have stated that our theoretical novelty lies in the further proof that PH with **1-dimensional** features is also as expressive as WL, while [1] only proved **0-dimensional** case. Moreover, we theoretically proved the **isomorphic invariant property** of our method.\n\nQ1: What happens when you consider graphs with more than one component? How does TIP perform in that scenario compared to other pooling mechanisms?\n\n>To address your concern, we generated a synthetic dataset named 2-Cycles, comprising two balanced two-class sets of 1,000 graphs each. This dataset consists of either two disconnected large cycles (class 0) or two large cycles connected by a single edge (class 1). The distinguishing factor between the classes is the number of connected components. The node numbers range from 10 to 20, with three-dimensional random node features generated. For the model configuration, we uniformly employed one GCN layer plus one pooling layer. The evaluation criteria remained consistent with those outlined in our paper. Experimental results in Table S4 indicate that our method is not effective in distinguishing similar graphs with different connected components. This aligns with our expectations, as our method does not explicitly incorporate such information, given that most graphs in real-world datasets are connected.\n\nQ2: Have you tried other ways to incorporate 𝐿𝑡𝑜𝑝𝑜? For e.g., by choosing a different vectorization of PDs such as persistence images or rational hats?\n\n>Thanks for the valuable comment. There are many topological descriptors, and we simply follow previous works [1, 2] and tried some of them. To make the best of PDs, we use several transformations and concatenate the output of them, including triangle point transformation, Gaussian point transformation and line point transformation. We have not tried rational hats and are grateful for reviewer 3dRY's suggestion. However, concerning the time budget of rebuttal, we would leave this as future work. \n\n>[1] Graph filtration learning. ICML 2020.  \n[2] Topological graph neural networks. ICLR 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jrBzsb4xMe", "reviewer": "Reviewer_HRv2", "summary": "This paper proposes a TDA-based mechanism for storing phase information in the pooling layer of a GNN. The proposed approach resamples the connections in the graph and scales the edge weights using persistence information from a one-dimensional persistence diagram. Experiments on artificial data for concept evaluation and on several benchmark datasets were also carried out.", "questions": "See Weakness", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The retention of phase information in the pooling layer is a new and interesting approach.\n- Experiments have shown that performance can be improved.", "weaknesses": "- The proposed method uses a 1-dim betti number, but its validity is not known. All 1-dim death times seem to be the same (maximum time for filtration) and seem to be only information about the last connection of the cycle. Only limited information on the cycle seems to be stored and is less convincing.\n- Learning to preserve topology information in persistent diagrams is proposed in [1]. (It would be inappropriate not to mention this.)  This paper vectorises PDs for training, but [1] and [2] show the possibility of learning in a more data-loss-free form, which lacks consideration. The novelty of the method also seems to be limited to the introduction of phase conservation in the pooling layer.\n- The paper only considers TU Datasets, ZINC and OGB, which have become mainstream in recent evaluations, should also be included in this evaluation.\n\n[1] Topological Autoencoders, ICML 2020\n\n[2] Optimizing persistent homology based functions, ICML 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: The proposed method uses a 1-dim betti number, but its validity is not known. All 1-dim death times seem to be the same (maximum time for filtration) and seem to be only information about the last connection of the cycle. Only limited information on the cycle seems to be stored and is less convincing.\n\n>It's common practice to use PH to characterize 0 and 1 dimentional betti numbers and intergrate with GNNs [1, 2, 3, 4], which has been proven effective. Following the practical implementations in previous works mentioned above, the 1-dim death times are equal and set as a large constant value, but their birth times vary according to their filtration values, resulting in different persistences (|death_time - birth_time|). We adhere to the conventions in [1] and utilize persistence rather than extended persistence for efficiency.\n\nW2: Learning to preserve topology information in persistent diagrams is proposed in [5]. (It would be inappropriate not to mention this.) This paper vectorises PDs for training, but [5] and [6] show the possibility of learning in a more data-loss-free form, which lacks consideration. The novelty of the method also seems to be limited to the introduction of phase conservation in the pooling layer.\n\n>We thank the reviewer for providing another perspective and evidence to support our claim that preserving topology information is meaningful in pooling. Our motivation arises from the observation that PH and graph pooling naturally aligns well, as evidenced in Figure 1. Preserving topology information in general can also be considered as graph pooling, as noisy topology is filtered out and essential parts are preserved. This is the major innovation of our method. We apologize for the unclear statement of our motivation and will reorganize and include new references in our revised manuscript.  \n>\n>We acknowledge that [5] and [6] provide effective ways to preserve topology information. However, directly calculating the distance between PDs is also a stable, expressive, and practical way to assess the similarity of two graphs, as proved by [4]. Additionally, vectorizing PDs is a common practice [1, 3, 7], which we adopt for its efficiency and flexibility. Autoencoders emphasize upstream tasks and therefore have higher demands for data loss, while pooling focuses on downstream tasks and has no such requirement.\n\nW3: The paper only considers TU Datasets, ZINC and OGB, which have become mainstream in recent evaluations, should also be included in this evaluation.\n\n>We have already considered one OGB dataset MOLHIV, as shown in the last column of Table 2. To address your concern, we provide additional experimental results on the ZINC dataset (see Table S1) in our response to Reviewer fBuZ.\n\n>[1] Topological graph neural networks. ICLR 2022.  \n[2] Graph filtration learning. ICML 2020.  \n[3] Deep learning with topological signatures. NIPS 2017.  \n[4] Curvature filtrations for graph generative model evaluation. NIPS 2023.  \n[5] Topological autoencoders. ICML 2020.  \n[6] Optimizing persistent homology based functions. ICML 2021.  \n[7] Persistence enhanced graph neural network. AISTATS 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n3Big5MmRs", "reviewer": "Reviewer_TU8V", "summary": "The paper introduces topological graph pooling, a novel method that leverages persistent homology to enhance general graph pooling techniques. The use of persistent homology serves two primary purposes, preserving important topological features in the coarsened graphs and generating edge weights for them. For the first purpose, a topological regularization term comparing the topology of the original and coarsened graphs is developed. For the second purpose, edge weights for the coarsened graph are generated based on an importance score derived from the persistence of cycles containing these edges in the filtration. The authors conducted two sets of experiments to assess the utility of PH in graph pooling. The first set demonstrates that coarsened graphs computed using the proposed PH graph pooling method effectively preserve topological information, even better than other dense and sparse pooling methods. The second set compares and benchmarks the topological pooling enhancement applied to some standard pooling techniques against other pooling techniques and standard graph neural networks. The results, obtained through a comprehensive experimental setup, clearly show the superiority of topological pooling over the other benchmarked methods.", "questions": "- Why do you use the Gumbel-softmax trick? I understand that you obtain a full graph using usual graph pooling, but, precisely, as you are learning filtrations and using persistent homology, you are also capturing in the persistence diagrams the topology of subgraphs that may not need to be fully connected. Did you try to avoid the Gumbel-softmax trick?\n- In lines 534, 535, 546, and 541 you write \"circles\", and not \"cycles\". Is this intentional? I believe there are more \"circles\" distributed across the test.\n- I have not seen any mention of more general pooling methods, such as cell complex pooling or simplicial complex pooling. Do you think your work can be extended to encompass general pooling on topological deep learning data?\n- Have you tried using some fixed filtrations insteaf of learnable filtrations for the graphs benchmark? If so, was there a significant difference compared to learnable filtrations?\n- In the complexity section, you mention that persistence diagrams can be computed very efficiently for dimension one. Do you have a reference for this claim? I was aware of this for dimension zero, but I have not encountered it for dimension one before.\n- In the Q1 experiments, the filtration is learned during training or is it also fixed as for benchmarking?", "limitations": "The limitations addressed are too simple. I think more effort is needed in this aspect.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper is one that evokes a sense of \"why didn't I think of that?\" due to its natural (but powerful) approach. In my opinion, after addressing a few questions, this paper deserves at least a spotlight at the conference.\n\n**Originality**: As far as I know, the connection between graph pooling and graph filtrations, while conceptually straightforward, has not been explored before.\n\n**Significance**: The persistent homology method addresses a significant problem in graph pooling, as highlighted by the authors. Previously, it was unclear which properties should be preserved in the coarsened graphs after pooling. It was even argued that random pooling could yield performances similar to previous state-of-the-art (SOTA) methods, making unclear why graph pooling was effective and how to design graph pooling techniques appropiately. This work clarifies that preserving the topology of the initial graph is crucial, consistently outperforming other SOTA graph pooling methods across various benchmarks. This makes intuitive sense, as topology concerns global structures, and destroying this information when getting a subgraph seems harmful for the network. This method is not only a clear win for persistent homology in the graph learning field, but also opens new avenues for effective pooling design in GNNs. \n\n**Clarity**: The paper is well-written, with pertinent and informative figures. In particular, Figure 3 effectively illustrates the importance of the contribution.\n\n**Quality**: The experiments are of high quality, encompassing various datasets and configurations. Additionally, the ablation study addressing the effectiveness of topological pooling in preserving input topology is enlightening and supports the use of persistent homology in graph pooling to preserve topology.", "weaknesses": "- Figure 1 (a), second row, is strange to me. Usually (and in the pipeline you describe), persistent homology goes from smaller to bigger graphs, and not the inverse path.\n- Line 80: Typographical error: \"filtraions\" should be corrected to \"filtrations\".\n- Equation 1: Missing comma after the formula.\n- In lines 114 and 115, you state that filtrations assign each vertex and edge a value. However, this is not always accurate. To have proper simplicial complexes through the filtration, the filtration function must assign lower values to the endpoints of edges than to the values of the edges themselves. Thus, the filtration needs to satisfy $f(\\{v_1, v_2\\})\\geq \\max(f(v_1), f(v_2))$.\n- In the paragraph starting at line 113, you mention that edges have a filtration value given by $f(\\{v_1, v_2\\}) = \\max(f(v_1), f(v_2))$, but, as stated in the previous comment, you do not restrict edge filtration values to these values. I suggest choosing one approach and modifying this paragraph slightly to ensure consistency.\n- In line 123 you state that the persistence diagram $ph(G, f)$ is a set of persistence diagrams $\\{D_1, D_2, ...\\}$.  However, in other parts, such as Equation 6, you imply that $ph(G, f)$ is only one of these persistence diagrams. I believe this is inconsistent.\n- Line 147 uses the word \"filtration\" twice, which seems redundant. I propose rephrasing it to \"The core of PH is the notion of filtration, the selection of which presents a challenging task.\"\n\n**Important points**: The score I give is subjected to solve/discuss at least the following points:\n\n- Lines 157 and 158 are unclear to me. How do you map the persistence diagrams to edge weights given by births and deaths of persistence diagrams points exactly? I think this should be described formally for several reasons. How do you choose the cycle representatives for the points of persistence diagrams? What does it happen if one edge belongs to more than one cycle? I think this is very relevant, even in the proofs.\n- In the proof of Theorem 4.1, I do not understand what are the nodes $u$ and $u'$. What are the nodes with different count? Are they unique? Also, the proof relies on understanding the specific function mapping persistence diagrams to edges. Should the proof end at line 537?\n- In the proof of proposition 1, what does it mean to be isomorphic for two graphs with features? I have not seen this definition before.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Figure 1 (a), second row, is strange\n\n>Figure 1(a) illustrates that PH and pooling naturally share a similar hierarchical structure, thereby aligning well. It does not imply that PH must progress from smaller to larger graphs.\n\nTypographical errors and incorrect expressions\n\n>We thank Reviewer TU8V for the valuable comments on our notations and expressions, which have significantly enhanced the readability of our paper. We have revised all instances according to the suggestions.\n\nIn lines 114 and 115, you state that filtrations assign each vertex and edge a value. However, this is not always accurate. \n\n>We thank Reviewer TU8V for the valuable comments on our statement of filtrations. We apologize for the unclear descriptions about filtrations. In our revised manuscript, we will explicitly state at the beginning of this paragraph that filtration on edges is set as $f(v_1, v_2) = max(f(v_1), f(v_2))$.\n\nInconsistent descriptions of persistence diagrams in line 123\n\n>We thank reviewer TU8V for the valuable comments. In our revised manuscript, we will add a slice to Eq. (6), e.g. $\\mathcal{D}_1 = ph(G, f)[1]$, to keep consistency.\n\nLine 147 uses the word \"filtration\" twice, which seems redundant\n\n>We thank reviewer TU8V for the valuable comments. In our revised manuscript, we will rephrase this sentence as suggested.\n\nLines 157 and 158 are unclear\n\n>Edge weights are encoded by persistence (lifespan of each edge: |death_time - birth_time|). Therefore, as stated in Lines 156-158, edges do not form cycles have the same birth time and death time, resulting in zero persistence. Each cycle is paired with the edge that created it, and the other edges in this cycle are assigned a dummy tuple value. If one edge belongs to more than one cycle, only the first time it gives birth to a cycle is considered. These settings are proposed and adopted in [1, 2], and we follow this common practice. Formal descriptions are provided in Appendix B.1, Lines 508-513. To enhance clarity, in the final manuscript, we will move this part to the main paper and modify the relevant sections in detail.\n\nIn the proof of Theorem 4.1, I do not understand what are the nodes 𝑢 and 𝑢′. What are the nodes with different count? Are they unique? Also, the proof relies on understanding the specific function mapping persistence diagrams to edges. Should the proof end at line 537?\n\n>Here we mean that we have graphs $\\mathcal{G}$ and $\\mathcal{G}'$, where nodes $u \\in \\mathcal{G}$ and $u' \\in \\mathcal{G}$ are nodes with unique label count in WL test. For example, $\\mathcal{G}$ contains 2 green nodes, 1 blue node and 1 red node, then node $u$ stands for the green node. The proof of Theorem 4.1 (PH is at least as expressive as WL) ends at line 537, and the subsequent paragraph demonstrates the existence of some cases where PH is more expressive than WL.  In our revised manuscript, we will add more details for better clarity.\n\nIn the proof of proposition 1, what does it mean to be isomorphic for two graphs with features? \n\n>We apologize for our ambiguous description. Here we consider a graph isomorphic test context, where node features denote the initial node labels.\n\nWhy do you use the Gumbel-softmax trick? \n\n>There are two reasons. First, the utilized learnable filtration [1] operates on nodes and edges, treating different weights equally. Second, edge weights may span a wide range in usual graph pooling (see Appendix D for empirical evidence). Therefore, we use the Gumbel-softmax trick to resample the subgraph into an unweighted graph. In our ablation study (Appendix E.5), TIP-NR represents our method without the Gumbel-softmax trick, and it demonstrates inferior performance.\n\nWrite \"circles\", and not \"cycles\". \n\n>We apologize for our inconsistent expressions. Both words refer to the same concept, and we will replace \"circles\" with \"cycles\" in our revised manuscript.\n\nI have not seen any mention of more general pooling methods, such as cell complex pooling or simplicial complex pooling. Do you think your work can be extended to encompass general pooling on topological deep learning data?\n\n>Thank you for the insightful comment. We believe that our work has the potential to be extended to encompass general pooling in topological deep learning data, as they also exhibit graph structures and one-dimensional topological features. We leave this extension for future work.\n\nHave you tried using some fixed filtrations insteaf of learnable filtrations\n\n>As suggested by Reviewer fBuZ, we consider using an MLP with randomly initialized and fixed parameters as the filtration function, named as **TIP-F**. The experimental results (see Table S2) on four benchmark datasets show that this kind of filtration is not as good as learnable filtrations in our method.\n\nReference for complexity analysis\n\n>The complexity analysis about persistent homology has been adequately discussed in [2, 3]. The bottleneck of PH computation is dominated by the complexity of sorting all edges, i.e. $\\mathcal{O}(m \\log m)$, where $m$ is the numer of edges.\n\nIn the Q1 experiments, the filtration is learned during training or is it also fixed as for benchmarking?\n\n>In the Q1 experiments, the filtration is learned during training.  We only keep a fixed filtration in the evaluation of topological similarity.\n\nThe limitations addressed are too simple.\n\n>We apologize for our inadequate discussions of the limitations. In addition to the limitations mentioned in our paper, we have found that our method lacks the ability to discriminate between graphs when the number of connected components is the only distinguishing factor. We provide empirical evidence (see Table S4) and analysis in our response to Reviewer 3dRY and will include this in our revised manuscript.\n\n>[1] Graph filtration learning. ICML 2020.  \n[2] Topological graph neural networks. ICLR 2022.  \n[3] Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology. ICML 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**General Response:**  

We would like to express our sincere gratitude for your thorough review of our manuscript and for providing valuable feedback and suggestions. Your expertise and insights have been instrumental in improving the quality and clarity of our work.  

During the rebuttal period, __we provide additional experimental results (Tables) and revised figure in a PDF file__. All experimental codes will be updated and released accordingly. Specifically:  

1. **Theory.** Reviewer fBuZ, 3dRY, and TU8V raised concerns about our theorem. We would like to emphasize that the innovation of our theory lies in further proving that the expressive power of one-dimensional topological features is stronger than that of the Weisfeiler-Lehman (WL) test. To clarify our proof of theorem, we will reorganize and explain it step by step.  
2. **Motivations.** Reviewer fBuZ is concerned about our motivations for preserving cycles in pooling. Meanwhile, Reviewer HRv2 provides literature evidence supporting the preservation of topological features. Our motivation arises from the observation that persistent homology (PH) and graph pooling naturally align well. This motivates us to preserve topological features in the pooling process. Preliminary experiments (shown in Table S3) indicated that using zero-dimensional topological features merely increases runtime; hence, our method focuses on one-dimensional persistence diagrams, which is explained as preserving cycles.  
3. **Experiments.** Both Reviewers fBuZ and HRv2 suggested adding experiments on the ZINC dataset. We have provided results in Table S1, where a consistent improvement is observed when integrating our method. To address the concerns of Reviewer fBuZ and TU8V about using fixed filtration functions, we use an MLP with randomly initialized and fixed parameters as the filtration function, as suggested by Reviewer fBuZ. Experimental results in Table S2 demonstrate that it is more effective to use learnable filtrations rather than fixed ones.  
4. **Limitations.** To address Reviewer 3dRY's question about our method's performance on graphs with more than one component, we generated a synthetic dataset named 2-Cycles. As most graphs contain only one connected component and we do not explicitly incorporate such information, our method does not show significant improvements for multi-component graphs, as evidenced in Table S4. This can be considered a limitation of our method, which we also discussed in response to Reviewer TU8V.   

We sincerely appreciate the time and effort you have devoted to reviewing our manuscript and providing constructive feedback. Your contributions have significantly strengthened our research.

## **PDF**

Meta-review: This paper presents a novel scheme for pooling graphs, making use of recently-developed topological paradigms, i.e., persistent homology. Using multi-scale representations of graphs (based on so-called filtration functions), the paper develops a new method for topology-aware graph coarsening, which is shown to lead to improved outcomes in an experimental suite. The paper is a timely and relevant contribution to a growing body of work on methods that leverage topological concepts in machine learning. Given the described benefits, the submission thus has the potential to be of high impact, not only for graph learning, but also as a general signal for the utility of topology-based methods.

This assessment was reflected in the reviews and the ensuing discussion. There was near-unanimous agreement on the relevance and soundness of the proposed work, but some reviewers raised concerns about theoretical and empirical aspects. As part of an extensive rebuttal, it is the impression of the AC—and of the reviewers—that these concerns could be alleviated. There is thus agreement that the paper is ready for presentation at the conference.

In their revised version, the authors should focus on the following aspects:

- Discuss delineation to existing methods better in the main paper (reviewer ` fBuZ`)
- Better discussion of limitations (reviewer ` k5BH`)
- Discussing additional data sets (reviewer `HRv2`), in particular those that have been mentioned as part of the extensive rebuttal)

The authors are moreover encouraged to heed the advice concerning the overall presentation of the work, with multiple reviewers pointing out suggestions for improvement. I trust the authors to provide these changes and turn this submission into an impactful contribution at the conference.
Decision: Accept (poster)