Boosting Graph Pooling with Persistent Homology

Figure 1 (a), second row, is strange

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.

Typographical errors and incorrect expressions

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.

In lines 114 and 115, you state that filtrations assign each vertex and edge a value. However, this is not always accurate.

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))$.

Inconsistent descriptions of persistence diagrams in line 123

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.

Line 147 uses the word "filtration" twice, which seems redundant

We thank reviewer TU8V for the valuable comments. In our revised manuscript, we will rephrase this sentence as suggested.

Lines 157 and 158 are unclear

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.

In 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?

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.

In the proof of proposition 1, what does it mean to be isomorphic for two graphs with features?

We apologize for our ambiguous description. Here we consider a graph isomorphic test context, where node features denote the initial node labels.

Why do you use the Gumbel-softmax trick?

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.

Write "circles", and not "cycles".

We apologize for our inconsistent expressions. Both words refer to the same concept, and we will replace "circles" with "cycles" in our revised manuscript.

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?

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.

Have you tried using some fixed filtrations insteaf of learnable filtrations

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.

Reference for complexity analysis

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.

In the Q1 experiments, the filtration is learned during training or is it also fixed as for benchmarking?

In the Q1 experiments, the filtration is learned during training. We only keep a fixed filtration in the evaluation of topological similarity.

The limitations addressed are too simple.

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.

[1] Graph filtration learning. ICML 2020.
[2] Topological graph neural networks. ICLR 2022.
[3] Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology. ICML 2019.

Thank you for your understanding and for raising the score. We appreciate your careful consideration of Theorem 4.1 and will revise the statement to ensure it accurately reflects the necessary conditions.

Regarding your final question, we apologize for any lack of clarity in our previous explanation. Initially, we consider a graph level task (e.g. graph classification). In this case, we consider if the sum of node features are invariant for any permutation of the graph, then it is isomorphism invariant (refer to Equation (9)). Now we provide more general proof of the invariant property.

Proof. Following the notations in our last response, we prove isomorphic invariance at feature level and connectivity level.
For feature-level invariance, let $X \in \mathbb{R}^{n \times d}$ be the node features, $P \in \\{0,1\\}^{n \times n}$ be the permutation matrix, $B\in \mathbb{R}^{n' \times n}$ be the assignment matrix, and $P^{\top}X$ be the permutated node features. The node feature map after pooling is denoted as $X' \in \mathbb{R}^{n' \times d}$, then we have $X' = BX$ If we permute $G$ using a permutation matrix $P$, the permutated node features after pooling are $X' = (BP)(P^{\top}X)$ which proves the isomorphism invariant property of pooling at feature level. For connectivity-level invariance, we copy our previous responses here. $A'=(B P) (P^\top A P) (P^\top B^\top)$ Note in our previous response with informal proof, we made a mistake in $A'=B^\top P^\top P A P^\top PB$ due to a rush, where $B^\top P^\top$ does not has a compatible dimension. Besides, for symmetric connectivity $A$, $PAP^\top=P^\top AP$. We correct it in this version.
This completes the proof.
We will revise our paper up to this new proof accordingly. Thank you once again for your valuable feedback and support.

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.

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.

W2: 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.

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.

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.

W3: The paper only considers TU Datasets, ZINC and OGB, which have become mainstream in recent evaluations, should also be included in this evaluation.

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.

[1] Topological graph neural networks. ICLR 2022.
[2] Graph filtration learning. ICML 2020.
[3] Deep learning with topological signatures. NIPS 2017.
[4] Curvature filtrations for graph generative model evaluation. NIPS 2023.
[5] Topological autoencoders. ICML 2020.
[6] Optimizing persistent homology based functions. ICML 2021.
[7] Persistence enhanced graph neural network. AISTATS 2020.

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.

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.

W2: 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.

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.

Q1: What happens when you consider graphs with more than one component? How does TIP perform in that scenario compared to other pooling mechanisms?

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.

Q2: Have you tried other ways to incorporate 𝐿𝑡𝑜𝑝𝑜? For e.g., by choosing a different vectorization of PDs such as persistence images or rational hats?

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.

[1] Graph filtration learning. ICML 2020.
[2] Topological graph neural networks. ICLR 2022.

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?

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.

Limitations: 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.

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.

W1:Concerns about theory and filtrations.

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.

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].

W2: Motivation for preserving cycles

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].

W3: No significant gains over some pooling-free models. Experiments on ZINC.

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.

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.

Q1: For the non-zero persistence tuples, are death times always equal

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.

Q2: Fig. 2 does not show self-loops

We have revised Fig. 2. The new version is provided in PDF.

Q3: Definition of simplicial complexes.

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.

Q4: The hierarchical view of PH in Figure 1

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.

Q5: Expressivity issues

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.

Q6: Isn't PH based on 𝐷1 strictly more expressive than 1-WL?

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.

Q7: What if using a fixed (non-trainable) random filtration function?

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.

[1] The expressive power of pooling in graph neural networks. NIPS 2023.
[2] Topological graph neural networks. ICLR 2022.
[3] Topological autoencoders. ICML 2020.
[4] Connectivity-optimized representation learning via persistent homology. ICML 2019.
[5] Graph filtration learning. ICML 2020.
[6] Deep learning with topological signatures. NIPS 2017.
[7] Rethinking pooling in graph neural networks. NIPS 2020.