Topological Data Analysis on Graphs: Euler characteristics, Persistent Homology, or Spectrum?

Authors: Mattie Ji, Vikas Garg
Primary area: learning on graphs and other geometries & topologies
Keywords: graph representation learning, topological data analysis, Euler characteristics, persistent homology, Laplacian spectrum, graph neural networks

Abstract:
Graph neural networks (GNNs) are limited by the Weisfeiler-Leman (WL) hierarchy and cannot compute graph properties such as cycles. Topological descriptors (TDs) such as the Euler characteristics (EC), persistent homology (PH), and Laplacian spectrums have thus been employed to enhance the GNNs. However, despite empirical successes,  the theoretical underpinnings of these TDs remain largely underexplored. We bridge this gap with a rigorous characterization of TDs focusing on three key aspects: expressivity (representational power), stability (robustness to data perturbations), and computation (implementation cost). We evaluate the expressivity of different TDs, and design a novel scheme $\operatorname{RePHINE}^{Spec}$ that is strictly more expressive. We also propose new metrics to assess the stability of the state-of-the-art RePHINE method and the newly proposed $\operatorname{RePHINE}^{Spec}$ method. To address computational costs, we introduce and analyze weaker variants for several descriptors. TDs find significant applications in molecular contexts, so we also explore new filtration functions on the molecular graphs. Finally, we formalize the properties of filtration functions derived from graph products. Overall, this work lays the foundation for the principled design and analysis of new TDs that can be tailored to specific applications.

Decision: reject
Reviewer scores: 6, 6, 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1729894439169

thread_type:
official_review

<thread_object>
creator: reviewer_icub

<content>
summary:
The paper establishes several results on topological descriptors on graph representation learning.

strengths:
The paper studies three topological descriptors—Euler Characteristics, Persistent Homology, and Laplacian Spectra—from various perspectives and compares their features and effectiveness.

weaknesses:
I found the paper difficult to follow due to a lack of cohesion among the presented results. The paper includes multiple, somewhat incremental findings that are loosely grouped under a single theme but lack a clear, unifying narrative. Each topic examined by the authors requires a much deeper, individual analysis; however, the paper only provides limited advancements in each area. Moreover, these results appear largely unrelated to one another, creating an impression of a collection of disjointed findings rather than a focused contribution to the field of topological descriptors in graph representation learning. I will address some points in more detail below.

1. **Expressivity of PH or TD**: The expressivity of persistent homology (PH) or topological descriptors (TD) is difficult to define without specifying the space of filtration functions. Without this specification, one could theoretically achieve any level of distinguishing power between graphs by selecting suitable filtration functions (or colorings). Therefore, the current results lack meaning from a machine learning perspective, as they do not offer a robust comparison to graph neural network (GNN) expressivity.

2. **Stability**: The stability result presented here is incremental, as it mainly builds upon foundational work by Cohen-Steiner (2006). There is limited novel contribution to the understanding of stability in this context.

3. **Product of Graphs**: The purpose of this section is unclear, as it does not seem connected to the main theme of the paper. The motivation for ML and relevance to the other sections should be clarified.

4. **Death-time Filtration**: The relevance of this section to the other sections is also unclear. Its connection to the overall analysis needs to be better justified. The authors derive several new notions and make comparisons between them. However, the motivation is again unclear.

5. **Molecular Graphs**: Since this is an ML venue, I would expect experimental validation. Some experiments demonstrating the utility of the discussed approaches on molecular graphs would be valuable to illustrate practical implications.

**In summary**, the paper discusses several interesting topics; however, it lacks focus and depth. I recommend narrowing the scope to one or two of these topics, accompanied by a much deeper analysis, with clearly defined goals and statements. This approach would lead to a more substantial and coherent contribution.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730590079004

thread_type:
official_review

<thread_object>
creator: reviewer_pi7v

<content>
summary:
This paper seeks to systematically study and provide advice (in the form of new contributions) on three topological descriptors for graph neural networks in terms of expressivity, stability, and computational cost.

strengths:
The paper seeks to rigorously study and provide a convincing basis for the role of topology in graph neural networks, which I agree with the authors is not yet convincing.  I think the paper does a good job at outlining the challenges of topological methods in computational settings, especially in deep learning and graph neural networks.

weaknesses:
Some of the main conclusions and findings of the paper are not that surprising, such as the Euler characteristic being strictly less expressive than persistent homology.  This is in quite fact obvious, given that the (persistent) Euler characteristic is an alternating sum of Betti numbers, while persistent homology by construction contains more information.  Overall, while I agree with the need for an unbiased and rigorous study of the effectiveness of topological methods in graph neural networks and I believe that this part of the study was carried out well, I am still not convinced by the place that topology has in graph neural networks and I am not convinced by the new contributions proposed in the paper, which in some cases, I see as straightforward extensions of existing methods.  Perhaps it is an artifact of needing to "sell" the new contribution.  I almost feel like the paper would have been stronger as a rigorous computational survey paper, systematically studying the strengths and limitations of topological methods, with a presentation of straightforward/obvious ways to fix the limitations.

The paper is also not very well written.  I am missing the traditional summarized bullet point list clearly listing all contributions of the work.

questions:
- Do you mean Euler characteristic or persistent Euler characteristic?  Definition 5 is the static version, but a persistent version is cited with Turner et al. being the reference.
- Overall, I find the presentation of the topological descriptors studied confusing; it is not very clear to me whether the persistent version is being studied for the three types or the static ones, although the title of the paper and the introduction seems to emphasize persistent versions of all descriptors.  Why are persistent versions studied in particular and not static ones?
- Should the authors choose to study static topological descriptors as well, I would be interested in what can be said about the Hodge Laplacian?  The kernel is known to encode geometric information about the homology of simplicial complexes (and therefore graphs as a lower dimensional special case); other eigenspaces do the same for graphs.  However, for the persistent version (which appears to be the one studied in this paper – again, not always clear...), only the kernel has been studied.
- What can be said in addition to expressivity?  What about interpretability of topological methods?  For this point, I admit that my rating of "soundness" might be somewhat unfair, as I think this paper would be stronger as a review/experimental study paper (as mentioned in the "weaknesses" section) and I would be open to raising my score for this criterion.  Although it may be (substantially) more work, I still feel like it is a plausible question since in some instances, interpretability and expressivity can be seen as related, especially in considering topological notions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730642859689

thread_type:
official_review

<thread_object>
creator: reviewer_nvly

<content>
summary:
The authors analyse three topological descriptors Persistent Homology, Euler Characteristic and Laplacian Spectrum from expressivity, computation and stability standpoint. The authors also introduce weaker but computationally more feasible topological descriptors. They show that $RePHINE^{spec}$ is among the most expressive topological descriptors. Further, they show that $RePHINE$ diagrams are stable and discuss how the analysis would generalize for product of graphs.

strengths:
I like the problem that the authors are attempting to solve, which is to have a comprehensive guide about which topological descriptor to use on what kind of data/tasks. I feel that solving this problem would really help TDA in ML community.

weaknesses:
Last line of the first paragraph “the theoretical foundations of TDs remain rather elusive.” This statement, as it reads, is incorrect. All the topological descriptors have a rich theory backing them. What the authors, perhaps, want to say is the expressivity analysis of TDs is rather elusive.

Definition 1: $f_e(c,c’) = f_e(c,c’)$ -> $f_e(c,c’) = f_e(c’,c)$

Most of the comparisons in Theorem 1 seem fairly obvious from the definitions. 

I don’t understand the point of stating Theorem 2 separately. Isn’t it already stated in Theorem 1 that $EC$ and $EC^m$ have the same expressive power?

The flow seems to be lacking from Section 4 onwards. I don’t quite get the motivation behind the product of graphs and death-time filtrations. 

Section 5 seems something new, although I am not sure about its applicability as such. 

I didn’t quite understand the overall point being made by Section 7. 

In Definition 8, what does $h_1 ~ h_2$ mean?

Line 491: Bond Coloring Representation -> Bond Counting Representation?

Overall, I think that the paper needs significant revisions before it is ready for acceptance.

questions:
The stability section just talks about the stability of $RePHINE$ diagrams, which is a straightforward extension of the stability of persistence diagrams. What about the stability of $RePHINE^{spec}$? Can that be characterized as well? What about the stability of EC?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730710435569

thread_type:
official_review

<thread_object>
creator: reviewer_qz4p

<content>
summary:
This paper provides a rigorous theoretical analysis of different topological descriptors (TDs) used to enhance graph neural networks (GNNs), focusing on Euler characteristics (EC), persistent homology (PH), and Laplacian spectrums. The authors examine these TDs through three key lenses: expressivity (representational power), stability (robustness to perturbations), and computational efficiency. They introduce a novel descriptor called RePHINE_Spec that combines spectral features with RePHINE and prove it is strictly more expressive than existing methods. They also propose a new metric to assess the stability of RePHINE and analyze weaker variants of several descriptors to address computational costs. The work includes theoretical results about filtrations on graph products and applications to molecular graphs.

strengths:
The paper's primary strength lies in its comprehensive theoretical treatment of topological descriptors, providing rigorous proofs and clear characterizations of their properties. The authors make several significant theoretical contributions, including proving the equivalence of EC and max EC diagrams, establishing stability bounds for RePHINE, and characterizing filtrations on graph products. The work is well-structured, building from fundamental concepts to more complex settings. The paper also introduces useful variants of existing methods that maintain expressivity while reducing computational costs.

weaknesses:
The paper is heavily theoretical and could benefit from more empirical validation of the proposed methods, particularly RePHINE_Spec. While the theoretical advantages are well-established, there is limited discussion of practical implementation challenges or computational benchmarks comparing the different methods.

questions:
- How does the computational complexity of RePHINE_Spec compare to existing methods in practice, and what are the memory requirements for storing the additional spectral information?
- Can the authors provide empirical evidence that the improved expressivity of RePHINE_Spec translates to better performance on real-world tasks?
- Could the theoretical framework developed in this paper be extended to handle dynamic or temporal graphs where the topology evolves over time?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730716215861

thread_type:
official_review

<thread_object>
creator: reviewer_zqbm

<content>
summary:
This paper presents new topological descriptors, especially RePHINE and RePHINESpec, designed to enhance the capabilities of GNNs by enhancing how well they capture complex graph features like cycles. By analyzing expressivity, stability, and computational efficiency, the authors compare various descriptors and explore practical applications, including insights for molecular graphs.

strengths:
1. The paper covers a range of topological descriptors and presents a detailed comparison of their expressivity, stability, and computational expenses.
2. The paper considers applications in molecular graphs, offering insights that could benefit chemistry and drug discovery.

weaknesses:
1. The definitions and theoretical explanations are dense and without sufficient explanations. This can be very difficult to follow for people with limited background.
2. The focus is primarily on color-based filtrations. Expanding the discussion to include other kinds of filtrations, would give a more comprehensive perspective.
3. . While the paper presents more expressive descriptors like RePHINESpec, it doesn’t address the computational cost, particularly in large graphs or real-time applications.

questions:
1. The paper’s applications are primarily molecular. Can this be expanded to other fields that use GNNs, such as social network analysis?
2. How does the use of topological descriptors like RePHINESpec compare with traditional GNN methods, particularly in tasks that do not require high expressivity?
3. The paper proposes several filtrations for molecular graphs. What criteria were used to select these?
4. What is the STABILITY OF REPHINE DIAGRAMS? explanation is missing. Can the authors provide practical examples where stability significantly impacts application outcomes?
5. How sensitive are the proposed descriptors (especially RePHINESpec) to variations in parameters such as filtration type or depth?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732735750492

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Comment

comment:
We are grateful to all the reviewers for their time and insightful comments, as well as to the (senior) area, program, and general chairs for their service to the community. We appreciate the reviewers' acknowledgement that the problem we are trying to address - the theoretical pinnings of how topological methods relate to graph neural networks - are important.

We have submitted a new version of our manuscript to address the common questions/concerns raised by the reviewer. Most of the notable changes are colored in orange. Here we summarize the changes we made to address the questions/concerns:

##  Extending Stability
Some reviewers were curious in whether the discussion of stability of RePHINE and persistent homology (PH) can be extended to the other two filtration methods we considered in this manuscript - $\operatorname{RePHINE}^{Spec}$ and $EC$. We first found out that the stability of $EC$ was already shown by Dłotko an Gurnari in [1] (Proposition 3.2).

We then investigated the stability of $\operatorname{RePHINE}^{Spec}$. Specifically, we prove in the new manuscript that $\operatorname{RePHINE}^{Spec}$ is locally stable under the assumption that the functions $f_v: X \to \mathbb{R}$ (which assigns each vertex color type with a real value) and $f_e: X \times X/\sim \to \mathbb{R}_{>0}$ (which assigns each edge volor type with a positivie real value) are both injective.

By **locally stable**, we mean that tiny variations in the filtration functions used will not drastically change the output of $\operatorname{RePHINE}^{Spec}$. In our original submission, what we proved for $\operatorname{RePHINE}$ is actually somewhat stronger - we showed that the bottleneck distance of any two RePHINE diagrams on the same graph are bounded in terms of some variant of the $\ell^{\infty}$ metric on the filtration functions that created them. This is a global statement of stability, whereas it suffices for local stability to hold in applications.

While $\operatorname{RePHINE}$ was shown to be globally stable by us, we also showed that $\operatorname{RePHINE}^{Spec}$ is not globally stable. Furthermore, when injectivity does not hold, it may not be locally stable either (but on a measure zero subset of the space of filtration functions). We have provided counter-examples for this at the end of Appendix A.3 (Example 1).

To discuss the word **local**, we needed a notion of topology on $(f_v, f_e)$. The convenient choice for us turned out to be thinking of $(f_v, f_e)$ as an element of $\mathbb{R}^{n} \times \mathbb{R}^m$ (where $n$ is the size of the vertex coloring set $X$ and $m$ is the size of the correspondent edge coloring set). In this case, $f_v$ being injective is the same as saying its coordinates have no repeated entries. The main idea behind proving the local stability of $\operatorname{RePHINE}^{Spec}$ was that the proof for the stability $\operatorname{RePHINE}$ may be adapted in a convex open neighborhood of $f_v$ in $\mathbb{R}^n$ and $f_e$ in $\mathbb{R}^m$.

The discussions on the new results are now in Section 4 of the manuscript, and the correspondent proofs are in Appendix A.3.

## Graph Product Motivation
Some reviewers raised some concerns that the motivations behind the discussion of graph products were not explained clearly. We have added a new explanation at the beginning of the correspondent section. Specifically, a key motivation for us to study graph products is that, when dealing with large or complex graphs that have the structural property of being some product, it is often easier to work with the components of the graph product rather than the graph as a whole. This decomposition can be particularly useful in how they relate to persistent homology methods and spectral methods. In particular, we were interested in how much topological information about the whole graph we can recover by just analyzing the components. 

## Static vs Persistent
There was a question raised about whether the topological methods we are considering in our work are **static** or **persistent**. To clarify, for us, a **persistent** topological method is a method that involves examining at how the topological invariants change over time with respect to the color-based filtrations of the graph. A **static** topological method is a method that does not take into account of this change over time. Therefore, all methods we defined in Section 2 of the manuscript are **persistent** topological methods. The reason why we wanted to **persistent** methods over **static** methods is because static methods only give a snapshot of the whole timeline of changes persistent methods can give, so persistent methods are generally more expressive than static methods of the same kind.

## Death Time Filtration
We have moved the discussion of the death time filtration to the appendix.

[1] Paweł Dłotko and Davide Gurnari, **Euler characteristic curves and profiles: a stable shape invariant for big data problems**
</content>
</thread_object>

</thread>


Metareview:
metareview:
This submission provides a characterisation of different topological descriptors along the axes of expressivity (that is, their power to _represent_ objects, stability (that is, how robust they are with respect to perturbations), and computation (that is, how fast they are and how easy they are to implement). Moreover, a new descriptor, RePHINE$^\text{Spec}$, is developed, which incorporates information RePHINE—an existing descriptor—and the graph Laplacian, in order to outperform existing descriptors in terms of expressivity. The submission then discusses the aforementioned aspects for the different descriptors, providing more insights into their underpinnings. This, along with the comprehensive scope of the submission, is also one of the main strengths of the submission. I also find the collection of theoretical results to be useful for practitioners with a background in computational topology.

These strengths are, however, marred by certain weaknesses, not all of which could be easily addressed during the rebuttal. Specifically, the following concerns remain largely unaddressed:

1. The overall "narrative" of the paper is lacking—while I and the reviewers understand the relevance of assessing topological descriptors from multiple perspectives, some of the sections are not sufficiently motivated (at least not on first glance). This makes the paper appear to lack some cohesion.
2. In addition, due to the focus on three different "axes" as pointed out above, some of the results are not described in-depth, while other results could be considered as "well-known" already, at least in the computational topology community.
3. Clearly, making such results available to a wider audience is a valid enterprise, and would indeed be the basis for a strong submission, but the paper, in its current form, lack accessibility by non-expert readers, thus impeding the stated goal of the manuscript, namely the dissemination of expressivity results of topological descriptors to a wider machine-learning community.
4. In addition, for such an audience, _some_ empirical components would be highly appreciated, in particular in light of the fact that topological methods may yet have a pivotal role to play in areas like graph machine learning, for instance.

It is for these reasons that I have to suggest rejecting the paper for now. I understand that this is not the desired outcome for the authors, and, as I shall briefly explain below, some of the reviewers could have been more active during the rebuttal. I took all these aspects into consideration, but nevertheless, I believe that this work—which has lots of potential—requires a major round of additional changes before being ready for publication. I see multiple paths going forward, and I hope the authors find one of them appropriate:

1. By improving the accessibility for a general machine-learning audience, together with the addition of empirical results, the authors could easily target another machine-learning conference with their revision.
2. By focusing more on the theoretical aspects of the works, the authors could target a journal like [JACT](https://link.springer.com/journal/41468), which has an audience with a strong background in (computational) topology.
3. Finally, the authors could also target JMLR or a related venue and rewrite their paper as a general _survey_ on such results; notice that a survey would not preclude theoretical results on their own, of course. In this case, a more comprehensive analysis of other descriptors would be warranted.

Regardless of the path taken by the authors, I believe in the potential of the work, and I would encourage them to incorporate some of the salient points raised by reviewers.