Graphcode: Learning from multiparameter persistent homology using graph neural networks

Summary

This paper introduces graphcodes, biparametric persistence summaries that are empirically efficient to compute yet not topologically invariant. It also provides a dedicated C++ library for calculating graphcodes. Graphcodes are structured as layered graphs; each layer contains vertices representing points in persistence diagrams derived from "horizontal slices" of a bifiltration. Edges connecting these points are induced by the inclusion maps between homology groups across the vertical slices. The authors propose the use of graphcodes as effective representations of data topology for graph neural networks, which facilitates the learning from topological features in datasets through deep learning approaches. The performance of graphcodes is empirically tested and benchmarked against other (multi)persistent summaries across three distinct tasks: graph classification, shape classification, and binary classification of samples derived from various random point processes. While graphcodes demonstrate superior performance in shape and binary classification tasks, they do not outperform state-of-the-art methods in graph classification.

Strengths

**Significance**: The paper tackles an important problem in applied topological data analysis: the development of topological summaries or representations that "characterize" (or provide critical information about) multiparameter persistence modules in such a way that they are easy to use/study, as persistence diagrams and their vectorizations do in one-dimensional persistent homology. More than that, the proposed summaries, called graphcodes, are not only good representations in the sense that they are easy to understand (stacked and connected persistence diagrams) as one-dimensional persistence diagrams, but are also easy to represent and manipulate in machine learning tasks, as are diagram vectorizations in the one-dimensional case. The graph nature of the representation makes graphcodes ideal for machine learning tasks, where topological information can be combined with graph learning architectures to automatically extract topological information about the input. This last point may be really relevant in topological deep learning as an automatic topological feature extractor from topological domains. **Originality**: Although I am not an expert on the specific topic of multiparameter persistent homology, I know that its integration with machine learning is still in its beginning, and there are not a lot of papers exploring how to create efficient and ML-suitable representations of the topological information of data. This one does, and it does so in a very original and understandable way. Seeing biparametric filtrations as graphs is something clever that I have not seen before and opens the door to automatically extracting topological information from the input data using graph learning methods. **Quality and Clarity**: Regarding quality, I find the main text (and the parts of the appendix I read) to be of very good quality. For an expert in topological data analysis, the paper can be followed smoothly, and the main concepts are illustrated with figures. For a non-expert, the theoretical part will be probably hard, but I cannot think of any way of making it clearer with the limited number of pages. Regarding the experiments, the number of tasks is enough for a theoretical paper.

Weaknesses

The main weakness of the paper is that the topological summary is not a topological invariant and depends on a choice of basis. This likely means that, in a real scenario, neural networks fed with graphcodes would require numerous examples to learn how to overcome this limitation. In a context where equivariance and invariance are becoming increasingly important in neural networks to avoid issues like this one, this may prevent graphcodes from being a suitable choice in deep learning pipelines. However, something similar occurs with graph eigenvector positional encodings, yet they are still used in state-of-the-art graph neural networks. The suitability of graphcodes may depend on how sensitive the performance of neural networks trained with graphcodes is to the choice of basis. Given that this conference is oriented towards machine learning, I believe that experiments assessing this sensitivity are crucial for the paper's acceptance. Regarding the entire set of experiments, I feel the discussion on the graph classification problem is not fair. For instance, it is mentioned that the performance of their methods is affected by small training sets for GNN architectures, but for the proteins dataset, a GNN achieves an accuracy of 84.91%, which is significantly higher than the methods reported, according to PapersWithCode: https://paperswithcode.com/sota/graph-classification-on-proteins. Although it is a drawback that the results with graphcodes are inferior to their counterparts, I do not think this is a critical weakness, and I believe it is preferable to have a more critical discussion of the method. Similarly, I think that the comparison with other methods in graph classification is unfair because they do not report the accuracies of neural networks trained with the other summaries. Although you mention partial experimentation, it is not specified adequately how these experiments were conducted, how many parameters they used, etc., to dismiss the experiments and present results from other tables. Regarding the text, it is unusual for me to work with half-open intervals [a, a). As stated in Figure 2, some cycles can be born at the same time they die. While it is useful for computations to have these bars, it is not standard to consider persistence diagrams with only some diagonal points. Even the notation is counterintuitive (what does an interval like this signify?). Perhaps it would be worth adding a comment about this fact. There is a typo in line 134 (bais -> basis). I believe there is a typo in line 143: I think you meant to say that it "contains consistent bases for all chain vector spaces $Z_p(K_1)$, ..., $Z_p(K_n)$"; subcomplexes are not vector spaces. Finally, regarding literature review, I feel like the Mapper paper [1], and [2] and [3] could be good additions to the section, The first one is used usually to generate graph representations of datasets that "preserves" topology and can also be used as inputs to graph neural networks. The second one analyzes expressivity of topology for graph learning (coincides very well with the topic). The third one is a topological layer based on persistent homology for graphs. [1] Singh, Gurjeet, Facundo Mémoli, and Gunnar E. Carlsson. "Topological methods for the analysis of high dimensional data sets and 3d object recognition." PBG@ Eurographics 2 (2007): 091-100. [2] Rieck, Bastian. "On the expressivity of persistent homology in graph learning." arXiv preprint arXiv:2302.09826 (2023). [3] Horn, Max, et al. "Topological graph neural networks." arXiv preprint arXiv:2102.07835 (2021). PS: Some basic experiments (really basic) on sensitivity and a slight modification of the discussion for graph classification being more critique would increase my score to weak accept. More critical experiments on sensitivity, or/and a good discussion about this section may likely make me to increase the score even higher.

Questions

- Vertices of the graph are given by persistence diagrams computed from "horizontal" slices, and edges from vertical morphisms. Does the construction depend on which parameter you select to be "horizontal" and which parameter you select to be "vertical"? - Can computations be parallelized? If so, what is the impact on the computation time? I saw that you compute the whole graph reducing one big matrix. However, it seems to me that parallelization, like reducing several matrices at a time, could be worth in this context. - Could this be extended to $n$-parametric persistent homology? - Are there differentiability results for these computations? You compare your method with PersLay. One of the good points of PersLay is precisely that backpropagation can be computed using PersLay as in intermediate layer due to differentiability results of one-dimensional persistence barcodes. Can something be said about this?

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Authors have addressed adequately the limitations of their paper through the text.

Summary

This paper introduces "Graphcode", a new representation for summarizing the topological properties of datasets filtered along two parameters. Graphcodes are based on persistent homology but aim to provide a more interpretable and efficient summary than existing multi-parameter topological descriptors. The key idea is to collect one-parameter sliced barcodes with basis-choice dependent mappings between consecutive persistence diagrams, which results in a bipartite graph structure, as the so-called Graphcode summary. The authors present an efficient algorithm to compute Graphcodes and demonstrate how they can be directly used as input to graph neural networks for machine learning tasks. Experiments on several datasets show that Graphcodes have competitive or superior performance compared to other existing topological descriptors of multi-parameter persistence, especially on tasks with clear topological signals.

Strengths

- A new topological representation that captures two-parameter topological information. - Efficient computation algorithm that scales well to large datasets.

Weaknesses

- Graphcode are not topologically invariant, depending on choice of basis. Impact of this is not fully explored. - Theoretical analysis of expressiveness/information captured by Graphcode is limited.

Questions

- How sensitive are the results to the choice of basis used in constructing the Graphcode? Is there a way to make this choice optimal or at least consistent/stable locally? - Since the Graphcode is not topological invariant, one concern might be that if the GNN based on such method is still permutational invariant / equivalent? If yes, more discussion or justification should be included in the main text. If not, the potential issue or constraints in application should be discussed. - The theoretical foundations and analysis of what information Graphcode capture compared to other descriptors is somewhat limited. Can this be expanded?

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

As the author already mentioned in the paper, one main concern is raised from the issue that the Graphcode, as a topological descriptor, is not invariant. It might also break the stability property of persistence modules. A GNN based on Graphcode might no longer be permutation invariant or equivalent. More discussion about such limitations in both theory and application will buy the paper more benefits.

Summary

The paper introduces "graphcodes," a novel multi-scale summary of the topological properties of datasets using graph neural networks. Unlike traditional persistent homology, which uses a single parameter, graphcodes handle datasets filtered along two real-valued scale parameters, resulting in a more informative and interpretable summary. The paper outlines how graphcodes can be efficiently computed and integrated into machine learning pipelines, demonstrating improved classification accuracy over state-of-the-art approaches.

Strengths

The paper introduces graphcodes, extending persistent homology to two-parameter scales, offering a novel and efficient method that integrates seamlessly into machine learning pipelines via graph neural networks. It demonstrates superior classification accuracy on various datasets compared to existing methods and provides an interpretable summary of topological features. The approach claims efficient computation comparable to one-parameter summaries, adding value through its innovation and practical performance.

Weaknesses

From the experimental results, it’s hard to find too much practical meanings of using graphcode.

Questions

1. How is the graph constructed in graphcode? Is it a directed graph? 2. From Table 1, MP-HSM-C performs much better than GC. Moreover, as stated in Line 251, all approaches terminate within a few seconds even on the devices mentioned in Line 240. So do we really need a method that runs a few seconds faster at the cost of losing considerable accuracies? 3. As stated in Line 227, GC-NE can be viewed as Perslay. It seems that Perslay is already accurate and efficient enough. From my perspective, it’s more practical to use Perslay rather than graphcode considering the experimental results provided in this paper. Besides, how does GC-NE perform on graph classification tasks? 4. As mentioned in line 172, the graphcode depends on the chosen barcode bases. I wonder if there is a risk that different choices of barcode bases could impact the robustness and consistency of GC?

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

1

Limitations

See Questions

Summary

This paper proposes a computationally fast method to extract information from a 2-parameter persistence module. The authors consider a 2-parameter persistence module as slices of 1-parameter persistence modules. Each 1-parameter persistence module can be represented as barcodes. The authors consider these barcodes as basis and represent the maps between the barcodes, induced by the bifiltration, as an attributed graph. This attributed graph is used as an input to a GNN architecture. The information extracted by this method is not a topological invariant, however, empirical results show that the method gives comparable results on TU datasets and better results on some synthetic datasets as compared to existing multiparameter methods.

Strengths

1. Overall, the paper is well-written and organized. 2. The problem that the authors are trying to tackle is a hard one of capturing relevant information in 2-parameter persistence in the absence of a complete invariant. 3. The method proposed in the paper has substantial theoretical backing and an algorithmic component. 4. The proposed method is computationally fast, as indicated by results in Table 2.

Weaknesses

1. The authors have shown experiments on TU Datasets and some synthetic datasets. GC seems to perform well on the synthetic datasets, however, the performance on TU datasets is not particularly impressive. The authors claim that it might be because there are not enough topological signals to capture in those datasets, which is not fully convincing. 2. The exact experimental setup (hyperparameter choices, number of GAT layers etc.) is not described in the paper, not even in the appendix.

Questions

1. Was there a specific reason to choose GAT as the GNN architecture? How does GC perform with other GNN architectures? 2. Was there a specific reason to choose max-pooling? How does the model perform with sum/average pooling? 3. It is interesting to see from Table 3 and Table 4 that adding edges in GC amounts to a marginal increase in performance. Does this mean that the information carried by the maps between barcodes is not as important? 4. How does the proposed method stand with respect to the expressivity as compared to other multiparameter persistent homology methods?

Rating

7

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, the authors have discussed limitations.