Aligning Persistent Homology with Graph Pooling

Questions

1. (Weaknesses) Essentially, all these discrete Ricci curvature models only characterize the “local” geometric information of the graph or simplicial complex. It is not sure why the authors choose to use it as the filtration parameter.

While it is true that curvature characterizes local geometric information, we use it solely as the filtration function. Filtration is the fundamental concept in persistent homology (PH), providing a means to capture the graph's global structures [1]. In this study, the objective is to select a fixed filtration function to compute the Wasserstein distance between persistence diagrams, serving as an evaluation metric for their topological similarities. Thus, we opt for utilizing the Forman-Ricci curvature as the filtration function, given its suitability for our scenario involving graphs with edge weights and cluster structures. Consequently, it is better equipped to capture the topological features of the coarsened graphs. Another advantage of using Forman-Ricci curvature is its computational efficiency. While alternative options like the Ollivier-Ricci curvature are also viable, they generally result in a heavier computational workload.

2. What is the meaning of “computation of filtration”?

We apologize for the lack of clarity in our presentation. In this section, we aim to convey the challenge of selecting the appropriate filtration for achieving optimal performance. We have revised this part as "The core of PH is notion of filtration, which presents a challenging task to choose the right filtration."

3. Some notations in the paper are very confusing.

We have revised them accordingly.

4. Page 4, for the “sequence of nested subgraphs”, the subindex is from 0 to n, this implies that nodes are added into the filtration process one by one, which is clearly not the case. To avoid the confusion, it is better to use a different way of notations.

Here the subindex does not have to be continuous from 0 to n. We have revised the notations to eliminate any potential ambiguity.

5. Page 5, in equation (5), the operation of min and max is in terms of what? If it is for the elements of the matrix, the min($A^l$) will result in a number.

It is for the elements of the matrix to get the maximum and minimum values of A, so it will result in a scalar. Equation (5) represents a regular min-max normalization process.

6. Page 5, in equation (6), the two matrices have very different dimensions.

Please note that the persistence diagram $\mathcal{D}$ is extended to match cardinality of the number of edges. Therefore, Eq. (6) represents the element-wise product of the edges in $\mathbf{A}'^{(l)}$. We apologize for the lack of clarity in our presentation. The notations of Eq. (6) have been updated to eliminate any potential ambiguity.

[1] Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Learning, pp. 4314–4323. PMLR, 2020.

Weaknesses

1. Why we need to preserve the mentioned topological information, e.g., the 1-th Betti Number (number of cycles) during graph coarsening?

In this paper, we leverage persistent homology (PH) to inject global topological invariance into pooling layers. For a molecule with some ring-like topology (e.g. a necklace), we assume that the coarsened graph still preserve this this characteristic, which has the potential to enhance performance in downstream tasks. The visualization and experimental results demonstrate our assumption. Our assumption is supported by the visualization and experimental results. It is worth noting that the original pooling layers already possess some local structure-preserving capability, mainly owing to their reliance on clustering methods.

2. What is the chosen filtration of PH in Figure 1(a) and Figure 1(b)? In Figure 1(c), which graph does the diagram correspond to?

Figure 1(a) provides an illustration of the hierarchical view of PH, with the colors of nodes representing the filtration. Nodes with the same color exhibit simultaneous appearances, disappearances, or merging into new nodes. In Figure 1(b), the filtration is selected based on the criteria described in [1]. Figure 1(c) offers a simple illustration of persistence diagrams, which are not associated with a specific graph. Our purpose here is to show that topological features, such as cycles and connected components, can be found in different regions of the persistence diagrams, where points located in the off-diagonal portion contribute to non-zero persistence.

Figure 1(b) denotes that we can use a graph pooing function to capture the change of the PH information since the correspondence is stable regardless of different datasets. In other words, we do not need additional efforts to preserve the mentioned topological information.

The persistence ratio represents only the proportion of non-zero persistence and implies that graph pooling may coarsen or sparsify graphs in a manner similar to PH. However, while PH utilizes persistence to indicate the significance of corresponding topological features, this aspect cannot be captured by graph pooling alone. Our fundamental insight is to preserve essential topological features during the coarsening process through the integration of PH and graph pooling, which relies on the integration of PH and graph pooling.

3. I recommend adding more popular benchmarks. In addition, the running time should be reported on different benchmarks.

We provide additional experiments on OGBG-MOLHIV from the OGB datasets. The comparison results are shown in Table 2 and the response to Reviewer XtaZ, where our method can significantly improve the baseline pooling methods. Additionally, to compare the running time, we perform experiments on a platform with an AMD EPYC 7542 CPU and a single NVIDIA 3090 GPU. We utilize the default settings from the graph classification experiments and record the running time of 50 epoches training on different datasets. The running time (in seconds) is reported in Appendix E.3 and shown below, which reveals that the incorporation of TIP does not impose a substantial computational burden.

[1] Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Learning, pp. 4314–4323. PMLR, 2020

Weaknesses

1 and 4. The integration of persistent homology should be fundamentally different. Since you are using single filtration, edge weights have no importance here. Therefore, the concepts of resampling and persistence injection, which involve varying the edge weights, may not align well with the method's underlying principles.

PH is utilized to incorporate topological information into the edge weights, which are then utilized as inputs to the GNN for obtaining node features. As a result, the utilization of PH influences the final node representations, which, in turn, impact the filtration values in the subsequent pooling layer, ultimately resulting in varied performance on downstream tasks.

2. The theorem is a bit irrelevant here as the existence of a filtration function in this context does not mean much for practical purposes.

The existence of such filtration function implies that theoretically TIP has stronger expressive power than conventional dense pooling methods (such as DiffPool, MinCutPool, and DMoNPool) when it comes to distinguishing non-isomorphic graphs. It does not generally translate into better predictive performance, though. Expressive power serves as an indicator of the method's ability in graph classification tasks [1]. By employing a learnable filtration function to enhance flexibility, the theorem validates the potential capability of our method [2][3]. Additionally, we apply our mechanism to a collection of graph pooling methods and observe consistent and substantial performance gain over several popular datasets in graph classification tasks, which is consistent with our theorem.

3. For classification results, it would provide more valuable insights into the performance of the proposed model if the authors compared it with State-of-the-Art (SOTA) GNN results rather than basic models.

We provide additional comparisons with Graph Substructure Networks (GSN) [4], which is a GNN model with a topologically-aware message passing scheme based on substructure encoding. The results are presented in Table 2 and shown below. GSN is highly related to our method TIP, as they both take the graph topology into consideration.

5. The sublevel filtration applied to the original graph is irrelevant to this goal and holds no significance in this specific context.

The sublevel filtration applied to the original graph is utilized to evaluate the topological similarity between the original graph and the coarsened graph within the feature space induced by PH. This leads to the inclusion of a topological loss term in Equation (8) in our design. Consequently, our method guides the pooling process to retain the essential topology of the original graph.

6. Including dataset statistics would enhance the exposition.

The dataset statistics have been added in Appendix B.2.

[1] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018.

[2] Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Learning, pp. 4314–4323. PMLR, 2020.

[3] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. arXiv preprint arXiv:2102.07835, 2021.

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

Weaknesses

[Theory] One dimensional persistence diagram is less expressive than 1-WL.

In the resampling process in Section 4.2, we forgot to include some implementation details. In Eq. (5), we add self-loops to the graph for the diagonal part of $\mathbf{A}^{\prime (l)}$ . For the off-diagonal part of $\mathbf{A}^{\prime (l)}$, we only resample the upper triangular matrix to ensure symmetry. As mentioned at the end of Section 3, the self-loop edges are assigned a dummy tuple value $(f(e), f(e))$. Therefore, for graphs $G_1$ and $G_2$ comprising one and two isolated nodes respectively, their corresponding 1-dim persistence diagrams contain one and two data points respectively, making them still distinguishable. While there are cases where 1-dim persistence diagram and 1-WL have the same expressive power, there are also cases where 1-dim persistence diagram can distinguish while 1-WL cannot, e.g. $G_1$ is a graph containing two non-overlapping triangles (2 cycles) and $G_2$ is a hexagon (1 cycle). We would like to thank Reviewer XtaZ for pointing out the deficiencies in our proof. To address this, we have made revisions to Section 4.2 to include additional implementation details and Theorem 1 in Section 4.3.

[Methodology] Does proposed method mainly relies on cycle-preserving pooling? The motivation for adopting only 1-dimensional PD is weak.

Our primary motivation is to preserve cycle structures during the pooling process. This motivation stems from the significant empirical evidence that substructures, such as cycles, are often intimately related to downstream tasks in fields like chemistry, biology, and social network analysis. Additionally, there has been an increasing focus on cycles in graphs, as evidenced by several notable works [1, 2, 3]. These works emphasize the significance of cycles in graphs and highlight the potential for structure-aware GNNs to enhance expressivity and improve performance in downstream tasks.

The effectiveness of graph pooling heavily relies on the quality of the coarsened graphs. Therefore, we assume that preserving cycles in the coarsened graphs can be beneficial for network science and bioinformatics tasks. In this paper, we leverage persistent homology (PH) to incorporate these essential topological features into graph pooling. Experimental results confirm the efficacy of our model, validating our assumption. Regarding the use of 1-dim persistence diagrams exclusively, our rationale is that the majority of graphs are connected with only one connected component. Additionally, we performed experiments comparing the use of 1-dim persistence diagrams and found no improvements in our model. In response to this, we have enhanced the description of the motivation for retaining cycle structures in Section 4.2.

[Experiments] More empirical evidence to support the proposed method and detailed ablation study.

We conduct additional experiments on OGBG-MOLHIV from the OGB datasets. The comparison results, presented in Table 2 and shown below, demonstrate that our method significantly enhances the performance of the baseline pooling methods. It's worth noting that our objective is to enhance graph pooling methods through the alignment of PH with graph pooling. Furthermore, we include additional results on the ablation study in Appendix E.2, where we add ablation study of DiffPool-TIP, MinCutPool-TIP and DMoNPool-TIP on a wider range of datasets.

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

[2] 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, pp. 10737–10745, 2021.

[3] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with iˆ2-gnns. In The Eleventh International Conference on Learning Representations, 2022.