Going beyond persistent homology using persistent homology

Summary

- The paper presents a comprehensive analysis of two types of color filtrations on graphs, focusing on their expressiveness. - The paper introduces a novel topological summary RePHINE that combines both node and edge persistence diagrams. The proposed summary is proven to be more expressive than either node or edge persistence diagrams alone. - The authors conduct experiments on synthetic and real-world datasets. They leverage a combination of RePHINE and a GNN structure to evaluate its performance.

Strengths

- The presented method RePHINE for mixing 0- and 1- dim information is interesting and, as far as I know, is novel. - A remarkable strength of the proposed method is its theoretical expressiveness, which surpasses the capabilities of utilizing 0- or 1-dimensional information in isolation. - The paper is well presented and effectively communicates its ideas, ensuring a high level of clarity and ease of understanding for readers.

Weaknesses

One weakness of the paper lies in the experimental evaluation section, which could benefit from a more comprehensive comparison with existing methods, such as the method proposed in [28]. Specifically, the paper could have included a comparative analysis between the proposed method and the local Persistent Homology (PH) method based on subgraph persistence diagrams included in [28].

Questions

- line 47-52: I think there is some syntax issue with the appearance of [Theory], [Methodology] and [Experiments] - line 142: "disconnect" should be "disconnects". - line 172: please mention that Q is a color separating set in this sentence. - line 502: what does "disjoint union" here mean? What does "these sets" refer to? could you please provide an explicit description of the set you are constructing here? - line 510: I don't think $\{\{X_i\}\}$ should have $l$ as a superscript. Are you also referring to connected components with $l$ colors instead of subgraphs? - line 513: "l+1 the" -> "l+1 th" - line 693: "it is not injective" should be "is not injective".

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations of the method are not adequately discussed. I think it would be beneficial for the authors to discuss applicability of the proposed method to handle large scale graphs. There are no potential negative societal impact of the work.

Summary

In this paper, the authors discuss the limitations of message-passing graph neural networks (MP-GNNs) in terms of the Weisfeiler-Leman test for isomorphism. They explore the use of persistent homology (PH) to augment graph models with topological features but highlight the challenge of identifying the class of attributed graphs that PH can recognize. To address this problem, they introduce the concept of color-separating sets. They establish necessary and sufficient conditions for distinguishing graphs based on the persistence of their connected components using filter functions on vertex and edge colors. Based on these insights, they propose RePHINE, a method for learning topological features on graphs. RePHINE integrates both vertex-level and edge-level PH, claimed to be more powerful than either category alone. When incorporated into MP-GNNs, RePHINE enhances their expressive power.

Strengths

The paper presents new theoretical results and introduces a concept of color-separating sets, providing a resolution to the problem of recognizing attributed graphs based on the persistence of their connected components. The authors establish necessary and sufficient conditions for distinguishing graphs using filter functions on vertex and edge colors. They also propose RePHINE, a method for learning topological features on graphs, which integrates both vertex-level and edge-level persistent homology.

Weaknesses

While the theoretical contributions of this paper are new, there is room for further exploration and validation in real-world experiments. The current evaluation primarily focuses on controlled simulated datasets, limiting our understanding of RePHINE's performance in practical scenarios. It is equally important to conduct more comprehensive experiments using real-world data to fully assess the efficacy and applicability of the proposed approach. Addressing these limitations would strengthen the practical relevance of the paper's findings. Are there any specific limitations or challenges when applying RePHINE to real-world applications? Additionally, it would be interesting to understand the factors that contribute to the marginal performance gain of RePHINE on most real-world datasets.

Questions

Please refer to the sections above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Please refer to the sections above.

Summary

The authors introduce RePHINE, which calculates 0-dimensional persistent homology (PH) with respect to the filtration on edge colors, augmented with so-called missing holes and vertex color information. They establish the necessary and sufficient conditions for distinguishing graphs. RePHINE is shown to be more expressive than both standard 0-dim and 1-dim PH, can be easily integrated into GNNs, and is demonstrated to boost their expressive power on several benchmarks for graph classification.

Strengths

(S1) The three questions in the Introduction nicely position and motivate the work, and the presentation of the main contributions is very clear. (S2) The theoretical results are relevant, as they discuss in detail the expressivity of PH on vertex-color and edge-color filtrations, and expressivity of RePHINE. I do not have a good overview of PH on graphs, so I cannot comment on the novelty of results, and I did not check the supplementary material for proofs. (S3) Experiments are carried out on 3 synthetic and 5 real-world datasets.

Weaknesses

(W1) The related work seems not be detailed enough and is hard to identify. (W2) The name RePHINE is clever and nice. However, the word interleaving suggests interleaving distance (esp. relevant in TDA), so it would probably be better to replace this with e.g. interplay or integration. Also, it is somewhat a misnomer since you are not really using a filtration on nodes (this information does not influence birth and death values), so it might be better to rephrase that part too (e.g. Refined PH by incorporating node-color on edge-based filtration)? (W3) From the beginning of the paper, I was confused what the particular interplay between vertex- and edge-based PH will be. This was most pronounced in Section 3.3, since your way of edge-coloring definition, if used together with vertex-coloring, does not satisfy the definition of simplicial complex. For example, f(orange)=1, f(blue-orange)=2, f(blue)=3, so that an edge can appear in the filtration before the two incident vertices appear. Stressing earlier on (already in Section 1) that you calculate PH on edge-based filtration, including so-called missing holes and augmenting it with vertex-color information would be helpful. See related comment (W2) on the acronym RePHINE above. (W4) You write: “We note that missing holes correspond to cycles obtained from 1-dim persistence diagrams.” How does you approach compare to concatenated standard 0- and 1-dim PH on edge-based filtration? (W5) Experimental results on synthetic data: More information about the data should be included (in Appendix C.1). What exactly is the problem/goal here? What type of graphs results in the same RePHINE representation (in particular for cub12-3)? You write that you compare with 0- and 1-dim PH on vertex-color filtration, but what exactly do you mean by this, is this information concatenated (union of sets is considered)? What about PH on edge-color filtration? Why are standard PH and GNNs performing so poorly? (W6) Experimental results on real-world data: You write that you compare against standard color-based PH, but what do you mean with this? See related comments in (W4). It would be interesting to look at the results in more detail, in particular to discuss some examples that would be wrongly classified with other approaches, but that are successfully tackled with your method, but also at the examples that cannot be classified properly with your approach (the discussion may be placed in an appendix).

Questions

Main questions are formulated in the weaknesses (W1)-(W6) above. (Q1) Abstract: “… provably more powerful than both”. The word both is confusing here, is your method more powerful than the two combined, or more powerful than each of them separately? (Q2) What is a suitable metric for the augmented persistence diagrams? A brief comment is sufficient, and can be placed in future research. (Q3) Which software do you use for calculation of PH? Some minor suggestions: - “Experiments support our theoretical analysis and show the effectiveness of RePHINE on five real-world datasets.” -> “Experiments support our theoretical analysis and show the effectiveness of RePHINE on three synthetic and five real-world datasets.” - Provide a reference for persistence diagram (e.g., in Section 2), so that readers can find more information, and to make it clear that this is not defined for the first time here in your work. - Explicitly mention that all lemmas and theorems are proved in Appendix B, since one might wonder if some or all of these are earlier results. - Lemma 1 Vertex-based filtrations … -> Lemma 1 Injective vertex-based filtrations … - For better readability, it would be good to also have explicit Definitions for separating and disconnecting set. Improve consistency in naming theoretical results, e.g., if Lemma 6 (Edge-based almost holes as disconnecting sets), then it is better that Lemma 4 (Vertex-based almost holes as color-separating sets). - A visual or table summary (can be placed in Appendix B) of your theoretical results could really help the readability of Section 3 and the impact of your work. For example, some of the table rows could be the following: 1) Real holes (d = infty) of 0-dim PH wrt vertex-color filtration --- Component-wise colors --- Lemma 2 2) Almost holes (b neq d, d < infty) of 0-dim PH wrt vertex-color filtration --- Color-separating sets --- Lemma 3 3) Birth time of 0-dim persistence interval wrt vertex-color filtration --- Vertex color --- Lemma 5 4) Almost holes (b neq d, d < infty) of 0-dim PH wrt edge-color filtration ---- Disconnecting sets --- Lemma 6 - What is {{ on line 135, line 160, line 182, line 199, …? - In Section 3, you denote birth and death values with b and d (I think this is more common and readable), but you use a and b in Section 4. - Introduce the augmented PH as an explicit Definition in Section 4, as this is your main contribution. - Cite specific Appendix (e.g. Appendix B), rather than pointing to the general Appendix. - Capitalization in References: PersLay, Kolmogorov, Rayleigh-Bénard, Leman

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations and future work are not discussed.

Summary

The discriminative power of the persistent homology (in certain homological degrees) of vertex- and edge-filtered graphs is characterized in terms of combinatorial structure of the graphs. It is shown that there exist pairs that can be distinguished by the persistent homology of vertex-filtrations but not by the persistent homology of edge-filtrations, and viceversa. This is used to motivate the introduction of a new topological descriptor of graphs which is strictly more discriminative than the persistent homology of both vertex- and edge-filtrations. The performance of this descriptor is evaluated on benchmark datasets. [Post rebuttal edit] Raised score to 6.

Strengths

1. The theoretical results on the expressiveness of persistent homology of vertex- and edge-filtered graphs are interesting, and they are put to good use in that they motivate the design of a provably stronger topological descriptor of graphs. 2. The fact that the invariant being introduced is strictly more discriminative than the persistent homology of vertex- and edge-filtrations seems to be relevant in practice.

Weaknesses

3. The exposition is, at times, not that easy to follow. See, in particular, my comment about line 174, below. 4. The experimental section is interesting, but the empirical claims about the performance of the RePHINE would be better substantiated with experimental evaluation on more datasets. 5. The conclusions are a bit too succinct. In particular, the limitations of the approach are not discussed in detail. Relatedly, no future work or open questions are mentioned.

Questions

## Main questions 6. Your approach seems similar to extended persistence (in the sense of your reference [2]). How does your main strategy (RePHINE) compare to extended persistence and in particular to Perslay (both in theory and in practice)? Can you substantiate this with theory or experiments? 7. Is it clear that RePHINE is isomorphism invariant? Since this is an important property for the theorical section of this paper, I believe that this should be addressed explicitly. 8. Is RePHINE stable in the sense of persistent homology? Is this relevant in your setup? 9. In line 58 you mention that you aim to fully characterize graphs that can be distinguished with persistent homology. Was this achieved or are there still open questions? ## Minor questions and comments 10. Line 61: Should the subset inclusion be $\in$? 11. Line 135: the double brace notation has not been introduced and is quite important for this paper. 12. Line 174: I understand that, when you say "graph" here, you mean a graph together with a vertex coloring function, as well as a filtration defined on those colors. However, in line 198 (Theorem 1), the graphs $G$ and $G'$ don't come with a filtration. The convention on what exactly is a graph and what extra structure is used in each result should be made more explicit. If graphs are always assumed to be colored, I would also suggest using the term "colored graph", or a term to the same effect. 13. Line 198: In Theorem 1, when you write $D_G$, do you mean diagrams in homological degree 0, in homological degree 1, or both? 14. Line 219: Could you please comment on the relevance of Lemma 7? How can it be used (in theory or in practice)? 15. Line 312: Is there a geometric or topological motivation for "case a=0" in line 312?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The paper would benefit from a discussion about limitations of the approach, even if brief. This will help readers asses how useful is their approach for specific tasks, as well as what remains to be done and what are the current promising avenues in the theoretical front.

Summary

The paper provides a theoretical analysis of the expressive power of Persistent Homology (PH) features in distinguishing different colored graphs. The paper characterizes the family of graphs that is separable by a 0-dimensional PH using either node filtering or edge filtering and identifies the failure cases. Based on the theoretical analysis, a new PH filtration is proposed that overcomes the previous limitation and is provably strictly more expressive than either node or edge filtering. The new filtering is compared with standard PH filtering on a synthetic dataset and a few graph-classification benchmarks.

Strengths

The main contribution of the paper lies in the theoretical analysis of the expressive power of PH filtering, which allows one to understand the limits of standard filtering schemes fully and to build a new enriched scheme to overcome them. The paper is generally well-written and drives you through the reasoning that led to the development of the method while introducing all the essential theorems. Fully understanding them and grasping all the implications requires some effort from the reader, and possible to jump forth and backward from the main paper and the supplementary where proofs are given, but this has to be expected in this kind of paper.

Weaknesses

If the paper is well structured for what concerns the theoretical analysis, the experimental one is a bit lacking. In particular, in its current state, the paper does not position itself with respect to recent methods for graph classification, and it is not clear if it is a practical competitive alternative or if the contribution mostly lies on the theoretical analysis and just paves the road to future possible developments. A felt also that an analysis of the expressive power bounds of the proposed method could have been interesting. For instance, is there any particular graph structure in which the proposed method cannot distinguish two non-isometric graphs?

Questions

Going through the Lemmas introduced in the preliminaries and the following section, it is not clear which lemmas/theorems are introduced by the authors and which ones are just reported (if any). I would add to the comparison soma SOTA method for graph classification. For MOLHIV the ROC-AUC is usually reported.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

I do not foresee any particular negative societal impact. A discussion on the theoretical and practical (if any) limitations of the proposed method, also w.r.t. SOTA on graph classification, would better help to understand the current and future potential of the method.

Thanks for the clarification

Dear Authors, thanks for taking the time to answer my doubts. The newly added material and experiments seem convincing. Should you have some preliminary results on the use of your method with SOTA GNNs before the reviewers/authors discussion period, I would be curious to see them.

Answer to rebuttal

I thank the authors for their response. Overall, I am satisfied with their answers, and I have raised my score accordingly. My score is not higher mainly due to some unanswered theoretical questions (stability and characterization of the expressivity of RePHINE, and comparison to expressivity of extended persistence).