Graph Persistence goes Spectral

Thank you for your suggestions. We reply to your comments below.

Introduction: motivation and contributions

Thank you for your suggestion. We will edit the introduction accordingly in the paper. To clarify our motivation and contribution: persistent homology (PH) based methods have been used in GNNs to boost the expressivity beyond the WL hierarchy. The spectra of (combinatorial) Laplacians can be seen as a generalization of homology, as homology corresponds to their kernels (see our response to the harmonic information question below for details), and thus we are motivated to include Laplacians as a next step. We chose RePHINE as our base to build SpectRe on, but, in principle, our augmentation would apply to any PH-based methods. Pleease see our response right below for a detailed account of our theoretical contributions.

The work heavily relies on results from previous studies, which limits the novelty of its theoretical contributions.

Thank you for giving us the opportunity to clarify our work. Although we chose RePHINE as the base descriptor to incorporate spectral information, we could have created a similar construction with any persistent based descriptors in the given filtration. We chose RePHINE as our base because it is a simple topological descriptor that is provably more expressive than traditional PH. Otherwise, the Laplacian spectrum (LS) (defined after Def 3.1) could have been a more generic option, but its expressivity is bounded by SpectRe.

For Section 3, Theorem 3.4 shows that augmenting RePHINE with the non-zero eigenvalues of graph Laplacians is just as expressive as augmenting with the entire family of persistent Laplacian spectra outlined in [1]. Using essentially the proof of Theorem 3.4 in the appendix, the same proof holds for augmenting any descriptor that is at least as expressive as PH. In other words, for any descriptor X such that $X \succeq PH$, augmenting X with the non-zero eigenvalues of graph Laplacians has the same expressive power as adding the entire family of persistent Laplacian spectra.

For Section 4, we first want to emphasize that the (global) stability of RePHINE (Theorem 4.4) was an open question in the RePHINE paper that we resolved here, which also led to our proof of a stability result for SpectRe (Theorem 4.5). There were three difficulties in proving stability properties for RePHINE and SpectRe that prevented us from directly using previous studies (ie. [2]). For RePHINE alone, the original definition of Bottleneck distance did not generalize to RePHINE diagrams as it did not take into account the $\alpha$ and $\gamma$ parameters. To address this, we needed to come up with a suitable version of Bottleneck distance for RePHINE (and SpectRe). The second is that the original proof for Bottleneck stability is not applicable to our setting because it does not account for the $\alpha$ and $\gamma$ parameters. In the appendix, to prove Theorem 4.4, we had to come up with the concept of a `vertex-edge pairing' in Definition A.3. Finally, for SpectRe, we even lose the global stability of PH and RePHINE as seen in Example 4.6. In order to quantify a weaker notion of stability, we used configuration spaces (ie. Conf_n(R)) to describe a local version of stability to correctly describe the stability of SpectRe. These are theoretical challenges we needed to overcome that suggest the stability section is not a direct application of previous studies. We also want to note that the ``vertex-edge pairing" in Def A.3 and the proofs can give approaches to proving the stability of persistent descriptors whose tuple size is greater than 2.

The experiments provided are insufficient to fully support the authors' claims.

Thanks for the opportunity to elaborate on our experiments. We conducted three sets of experiments: (1) Expressivity results on multiple datasets (Table 2), (2) experiments on graph classification (Tables 3 and 6), and (3) ablation studies (Table 5). We believe these experiments demonstrate the effectiveness of SpectRe (and its fast variant) and are aligned with the claims in the paper.

We have additionally run experiments to showcase the global and local stability of RePHINE and SpectRe. We look at 4 graphs from BREC (basic.npy). For each one, we define ($f_v$, $f_e$) with $f_v$ being the degree and $f_e$ being the average of the degree of the vertices. The following table shows the bottleneck distance and our bound for different choices of $(g_v, g_e)$.

We first see that no matter what the $(g_v, g_e)$ is, the RePHINE distance is bounded by the RePHINE bound, which corresponds to RePHINE being globally stable.

For SpectRe, when $g_v = \sin(10 f_v), g_e = 5 f_e$, we observe that we did not break stability. This is because of two reasons (1) changes in the vertex-filtration function do not affect stability, and (2) the change $f_e->5g_e$ did not cross the region of non-injectivity. When $g_v = 0.1f_v+0.1, g_e=\exp(-f_e)$, we see the stability of SpectRe is broken. This is expected behavior because $\exp(-f_e)$ is an order reversing function, and the path from $f_e$ to $\exp(-f_e)$ would necessarily cross some region of non-injectivity.

Comparison with local persistent homology methods.

Thank you for raising this question. Given a fixed filtration method, the local PH method in [3] takes in a graph G with no labels on its vertices and produces a map plh_p: V(G) -> R^d where for each vertex v, we takes an appropriate annular local subgraph around v and calculate the PH of the filtration method applied to the subgraph, and then `vectorize' the PH diagram. In the paper, the authors considered the Vietoris-Rips filtration, which produces a simplicial complex with a filtration from the subgraph, so its PH has higher dimensions at the expense of needing to do more calculations. On the other hand, the PH in our work only concerns 0th and 1st dim information. We do note, however, that our method would subsume local PH if we replace the filtration method by a vertex-based or edge-based filtration on the annular local subgraph itself. This is because we can always choose a convenient coloring function such that it repeats the filtration for the annular local subgraph first before loading in the other parts of the graph.

I am not so sure if harmonic information is necessary?

Thank you for raising this question. To clarify, the graph Laplacian and more generally combinatorial Laplacians are usually thought of as the discrete analog of Laplacians in the calculus case. In calculus, solutions to $\Delta u = 0$ are called harmonic functions, and hence the kernel of the combinatorial Laplacians are sometimes referred to as harmonic information. When we extend this to persistent Laplacians, the kernel of the persistent Laplacians (ie. the harmonic information) capture precisely the persistent homology (see the introduction and Section 3 of [1]). This is a generalization of the fact that the dimension of the graph Laplacian's kernel is the same as the number of connected components (ie. the 0th homology). Therefore, harmonic information is quite necessary for our studies because they are exactly persistent homologies. In the design of SpectRe, we only needed to include the non-zero eigenvalues precisely because persistent homology already accounted for the zero ones.

On the integration with GNNs

To integrate SpectRe into GNNs, we first need to obtain a vector representation of the persistence diagrams. This is done in two stages:

1. We use a DeepSet to encode the graph spectrum associated with each tuple in the diagram.
2. A second DeepSet is then applied to aggregate the encoded tuples into a single vector, yielding a fixed-size representation of the diagram.

At each GNN layer, we compute a new SpectRe diagram and derive its corresponding vector representation. These representations are then integrated into the model—for example, by concatenating them with the graph-level representation—just before the final classification head. We will clarify this process in the revised manuscript.

---

We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional concerns.

[1] Persistent Topological Laplacians – a Survey. X. Wei and G-W. Wei

[2] Stability of Persistence Diagrams. D. Cohen-Steiner, H. Edelsbrunner, J. Harer

[3] Persistent Local Homology in Graph Learning. M. Wang, Y. Hu, Z. Huang, D. Wang, J. Xu

Thank you for your comments. We reply to your comments/questions below.

The method is significantly more expensive than standard PH descriptors, ...

Thank you for your comment. The average times per epoch (measured over 10 epochs) on CPU for FastSpectre (with scheduling) on the largest datasets are as follows: NCI1 / NCI109 (11s), IMDB-BINARY (10s), ZINC (17s), and MOLHIV (130s). This is substantially faster than the full method, which requires NCI1 / NCI109 (26s), IMDB-BINARY (24s), ZINC (40s), and MOLHIV (211s). As discussed in the paper, the faster variants of SpectRe can be applied to larger datasets while still offering greater expressivity compared to other topological graph descriptors.

I do not find the downstream empirical performance on real data to be particularly convincing. For most of the datasets in Table 3, the separation between SpectRe and RePHINE does not seem to be statistically significant...

We note that the gains over RePHINE are consistent across datasets and GNNs (see Table 6 for experiments using Graph Transformers). Overall, these results indicate that when combining topological descriptors with GNNs on attributed datasets (with informative node features), the latter’s inductive biases play a significant role. Similar findings have also been observed, for instance, in Topological GNNs (ICLR, 2022).

Most important, our expressivity results are significant and clearly demonstrates benefits of our proposal over existing topological descriptors, which is the primary motivation for our proposal.

The stability of SpectRe only holds locally under injectivity, which is a strong assumption. Many real-world filters (e.g., curvature-based or learned ones) may not satisfy this. ... have some robustness analysis or ... empirical sanity 

Thank you for raising this! From the issue pointed out on injectivity, we came up with an approximate bound on how worse the error could get when injectivity is violated and some extensions of the stability results (see our response to Q1 & Q2 below).

Here, we note that our stability result holds on filtration functions that are ``injective on the level of colors". In other words, the filtration function produces the same value on v and w if and only if v and w have the same color. The curvature-based scheme in [2] assigns filtrations to graphs without labels (ie. colors), which is somewhat different. In our context, if we are given a graph without labels, we typically would assign it some form of colors first in order to be able to apply the theorem. The curvature-based method in [2] does not really adapt to give a filtration for an arbitrary graph with some colors.

We also note that the injectivity assumption is reasonable in many cases. For example, if fv: X -> R is not injective. Then the filtration on the graph is the same as the filtration induced by an injective function fv': X' -> R where X' is X/~ where we say two colors a, b are equivalent if fv(a) = fv(b).

We also did an empirical verification of the stability results. Please see our response to Reviewer jmrk for more details

The lack of ablation is noticeable. ... A comparison with a "spectrum-only" variant would help clarify this.

We report in Table 5 of the Appendix additional experiments considering SpectRe using partial spectrum information (one third of the total eigenvalues). As we can see, SpectRe with partial spectrum can distinguish the same graphs as the full spectral approach. However, if we remove the spectral information, the expressivity drops significantly — note that SpectRe without spectrum corresponds to RePHINE. Thus, the comparison to RePHINE already represents an ablation study.

Additionally, we have run experiments using LS (Laplacian Spectrum) on BREC datasets. The results are:

The results show that LS perform on par with SpectRe on 4 out of 5 BREC datasets. However, the performance on CFI confirms the higher expressivity of SpectRe compared to LS --- 0.77 (SpectRe) vs. 0.72 (LS). Indeed, LS is a simplified version of SpectRe, and is also a contribution of this paper --- as far as we know, no prior work has exploited spectral information persistently in graph learning

Overall, these results demonstrate the importance of spectral information to the expressive power of the proposed descriptors. We will add these experiments to the revised paper

Q1:How sensitive is SpectRe to noise or perturbations in the filtration functions, particularly when injectivity is violated?

Thank you for raising this question. We will quantify an explicit bound on how much SpectRe changes when injectivity is violated, which also may serve as a partial answer to the next question. First of all, we note that perturbing fv does not break stability. This is because the actual filtration SpectRe is being done on is with respect to the edge-level filtration (ex. see Figure 2), and fv is only used to populate with $\alpha$-parameter, which is stable. Thus, SpectRe is globally stable in f_v and locally stable in $f_e$

For simplicity, let G be a graph and let $f_e$ be an injective edge filtration function with values $a1 < ... < an$ and $ai = f(ei)$ for ei an edge color type. Let $g_e$ be a perturbation of $f_e$ such that $g_e(ej) = f_e(ej)$ for all j != i, and $g_e(e_{i}) = g_e(e_{i+1}) = a_{i+1}$ - in other words, $g_e$ merges the i-th and i+1-th value together. Since SpectRe is globally stable in vertex filtration function, we might as well set $f_v = g_v$. We seek to quantify a bound on the distance

$D := d^{Spec R, 0}_B(SpectRe(G, fv, fe), SpectRe(G, gv, fe))$

(The case for 1-dim components is similar). Now observe that the SpectRe diagram for both are the same outside of the vertex deaths at time $a_i, a_{i+1}$ for $f_e$ and time $a_{i+1}$ for $g_e$, so they can be cancelled out under a suitable bijection. Furthermore, the vertex deaths at time $a_{i+1}$ for $f_e$ are a subset of vertex deaths at time $a_{i+1}$ for $g_e$, such that they have the same \alpha and \rho parameters, so we extend the bijections to match them too. Finally, we match the vertex deaths at time $a_{i}$ for $f_e$ to the remaining ones left in $a_{i+1}$ for $g_e$. This bijection gives the bound

$D \leq (a_{i+1} - a_i) + (f_e - g_e)_{\infty} +$

$\max_{(H1, H2) \in Y} d^{Spec}(p(H1), p(H2))$

$= 2(a_{i+1} - a_i) + \max_{(H1, H2) \in Y} d^{Spec}(p(H1), p(H2))$

where Y is the collection of pairs (H1, H2) where H1 is a connected graph a vertex v died at time a_i for f_e is in, H2 is a connected graph the same vertex v died at time a_{i+1} for g_e is in, and H1 is in H2. p(H1) is the list of non-zero Laplacian eigenvalues of H1.

By the interlacing theorem (see Prop. 3.2.1 of [1]), $d^{Spec}(p(H1), p(H2))$ can be written as $tr(L(H2)) - tr(L(H1))$, where tr is the trace and L(-) is the graph Laplacian. The trace of Laplacian is also the sum of degrees of the graph, which is also twice the number of edges. Thus, we have that

$D \leq 2(a_{i+1} - a_i) + 2 \max_{(H1, H2) \in Y} |E(H_2)| - |E(H_1)|.$

Here we proved a bound of a perturbation where we "pushed a_i up to a_{i+1}", a similar bound can be obtained where we ``push a_{i+1} down to a_i". Also note that Y can be checked component-wise rather than vertex-wise as a simplification.

This is a very interesting question, and we will include this discussion in the main text and the appendix.

Q2:Can the stability results be extended to include non-injective filtrations in some approximate sense?

Thank you for this question. As in the last answer, it is totally okay for f_v to not be injective. Please also see the discussion above for a quantitative bound on the extent SpectRe fails to be stable for non-injective filtrations.

Here, we also note that the proof of Theorem 4.5 essentially shows that the following local stability result is possible on a non-injective filtration f_e. Let c1, ..., ck be the possible values of f_e on edges, and let x_i^1, ..., x_i^{ai} be f_e^{-1}(ci). Let Z be the subspace of edge filtration functions g_e: X x X/~ \to R_{>0} such that $g_e(f_e^{-1}(ci)) = di$ and $g_e^{-1}(di) = f_e^{-1}(ci)$ (for some di). Z is a metric space, and essentially the same arguments for Theorem 4.5 would show that SpectRe is locally stable around $f_e \in Z$.

Q3:Would using approximate spectral methods (e.g., Nyström) change expressivity, or just reduce fidelity?

Thanks for your great question. Assuming (some of) the filtered subgraphs have low rank structure, we can approximate their corresponding Laplacians with the Nystrom Method. Under low rank structure, this Nystrom approximation would not impact expressivity. Then, one can compute the spectrum on the matrix obtained via Nystrom’s approximation.

In fact, we can use this to further speed up FastSpectre --- by estimating the lower spectrum based on the Nystrom's approximation.

We believe that it might also be interesting to explore the use of approximate “leverage scores” to find nodes that are most relevant at any timestep. This could make the method more interpretable.

---

Thank you for the insightful review and constructive feedback. We hope your concerns are satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engage further if you have any more questions or suggestions.

[1] Spectra of graphs. Brouwer et al [2] Curvature Filtrations for Graph Generative Model Evaluation. Southern, J. Wayland, M. Bronstein, B. Rieck

Thanks for your review. We reply to your comments below.

There are no comparisons with other state-of-the-art GNNs. 

Thanks for your comment. We provide additional results in Table 6 in the Appendix, where we show that our topological descriptor can boost the performance of Graph Transformers (SOTA GNN). Importantly, since we propose a new persistent topological descriptor that can be readily integrated into graph models, we focused on comparing it to existing topological descriptors. In this regard, REPHINE and the standard PH procedure are the main baselines.

In particular, I would like to see a baseline of GNNs which use spectral information in a simple manner.

A common approach to incorporating spectral information in graph models is through Laplacian Positional Encoding (LapPE), as used by the Graph Transformer in Table 6. Notably, our results demonstrate that SpectRe can further enhance the performance of models that already leverage spectral features, highlighting its complementary benefits.

To assess the impact of a simpler spectrum-based descriptor on expressivity, we have run experiments using LS (Laplacian Spectrum) on BREC:

The results show that LS performs on par with SpectRe on 4/5 datasets. The performance on CFI confirms the higher expressivity of SpectRe compared to LS --- 0.77 vs. 0.72. Indeed, LS is a simplified version of SpectRe, and is also a contribution of this paper --- as far as we know, no prior work has tried to incorporate spectral information persistently in graph learning.

The theoretical results (Theorem 3.2, Theorem 3.3) do not seem very hard to prove.

Thank you for the opportunity to clarify our work. We want to emphasize that our main theoretical results are not just Theorem 3.2,3.3 but also Theorem 3.4, Theorem 4.4, and Theorem 4.5. We agree that the results of Theorem 3.2,3.3 are not surprising - it is included for book-keeping purposes.

Theorem 3.4 shows that augmenting RePHINE with the non-zero eigenvalues of Laplacians is just as expressive as augmenting with the entire family of persistent Laplacian spectra in [1]. This was quite surprising and non-trivial for us, since the definitions of persistent Laplacian are a lot more involved and produce a much larger list. Theorem 3.4, however, shows that there are no additional gains that persistent Laplacians would give in this case in terms of expressivity than the more traditional graph Laplacians. Using essentially the proof of Theorem 3.4 in the appendix, the same proof holds for augmenting any descriptor that is at least as expressive as PH. In other words, for any descriptor X such that $X \succeq PH$, augmenting X with the non-zero eigenvalues of graph Laplacians has the same expressive power as adding the entire family of persistent Laplacian spectra.

Please see the answer to the comment below for why proving stability (Section 4) was also quite involved.

The broader significance of these results [stability] is not so clear to me.

Thank you for raising this comment. We want stability results for both RePHINE and SpectRe because they ensure that small perturbations in the input filtrations will not change the output drastically. This is quite important in graph representation learning because often times the attributes/colors we put on the vertices of the graph may be subject to slight measurement errors or imprecision, and the corresponding output of the topological descriptors (TDs) may be affected by that as well. If the TDs are not stable, then their outputs would vary heavily, rendering the method not robust / reliable. This is why the (global) stability of RePHINE and the (local) stability of SpectRe in the paper are quite important, as they ensure the methods are sufficiently robust to perturbations.

From a theoretical viewpoint, there were some difficulties we overcame in proving stability for RePHINE and SpectRe that may be quite helpful for proving stability of persistent descriptors whose tuple size is greater than 2 in the future. For RePHINE, the original proof for Bottleneck stability is not applicable to our setting because it does not account for the $\alpha$ and $\gamma$ parameters. In the appendix, to prove Theorem 4.4, we had to come up with the concept of a ``vertex-edge pairing" in Definition A.3. Going from RePHINE to SpectRe, we even lose the global stability of PH and RePHINE as seen in Example 4.6. In order to quantify a weaker notion of stability, we used configuration spaces (ie. Conf_n(R)) to describe a local version of stability to correctly describe the stability of SpectRe. We also want to note that the stability of RePHINE was an open question in the original RePHINE paper.

Why are there no experimental results to demonstrate the significance of these results [stability]?

To address your issue, we look at the first 4 graphs from BREC (basic.npy). For each graph, we define ($f_v$, $f_e$) with $f_v$ being the degree of the vertex and $f_e$ being the average of the degree of the two vertices. The following table shows the bottleneck distance and the inequality bound $3||f_e - g_e|| + ||f_v - g_v||$ for different choices of $(g_v, g_e)$.

The outputs of the table are expected behaviors. We first see that no matter what the $(g_v, g_e)$ is, the RePHINE distance is always bounded by the RePHINE bound, which corresponds to RePHINE being globally stable.

For SpectRe, when $g_v = \sin(10 f_v), g_e = 5 f_e$, we observe that we did not break stability. This is because of two reasons (1) changes in the vertex-filtration function do not affect stability, and (2) the change $f_e\to 5g_e$ did not cross the region of non-injectivity. When $g_v = 0.1f_v+0.1, g_e=\exp(-f_e)$, we see the stability of SpectRe is broken. This is expected behavior because $\exp(-f_e)$ is an order reversing function, and the path from $f_e$ to $\exp(-f_e)$ would necessarily cross some region of non-injectivity.

The computational costs of SpectRe are very prohibitive, compared to SOTA GNNs.

Indeed, the vanilla version of SpectRe is computationally expensive. To make it scalable to larger datasets, we developed FastSpectRe by combining efficient algorithms for computing partial spectra with a scheduling strategy. The average times per epoch (measured over 10 epochs) on CPU for FastSpectre (with scheduling) on the largest datasets are as follows: NCI1 / NCI109 (11s), IMDB-BINARY (10s), ZINC (17s), and MOLHIV (130s).

 Please cite this as a theorem from an earlier paper, or prove it somewhere.

We will prove it here as follows and include in the paper.

Lemma: Let G and H be two graphs with the same number of nodes with one single color, then RePHINE can differentiate G and H if and only if either $b_0(G) \neq b_0(H)$ or $b_1(G) \neq b_1(H)$.

Here $b_0, b_1$ refer to the 0th and 1st Betti numbers of G and H, which are the number of connected components and independent cycles.

Proof: Since G and H only have one color, $f_v, f_e$ are both constant functions of values $a_V, a_E$, so the $\alpha$ and $\gamma$ parameters of RePHINE for $G$ and $H$ are the same and can be discarded. Here, the filtrations with respect to $f_e$ has two steps - it first spawns all the vertices and then adds in all the edges. Thus, RePHINE can differentiate G and H if and only if looking at its first two parameters alone can differentiate $G$ and $H$. Since $f_v$ and $f_e$ are constant, a vertex either dies at time $a_V$ or at infinity, and all independent cycles are born at time $a_E$. Thus RePHINE can differentiate G and H if and only if they have different counts of pairs (0, a_V), (0, \infty), and (1, a_E). Since G and H have the same number of vertices, these counts differ if and only if b_0(G) != b_0(H) and b_1(G) != b_1(H).

---

We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional questions, concerns, or suggestions.

We are grateful to Reviewer aJUR for their time and detailed comments. We reply to your comments/questions below.

The core idea is to add spectral features to an existing descriptor (RePHINE). This is a natural follow-up step rather than a fundamentally new approach.

Thank you for giving us the opportunity to clarify our work. Although we chose RePHINE as the base descriptor to incorporate spectral information, we could have created a similar construction with any persistent based descriptors in the given filtration. We chose RePHINE as our base because it is a simple topological descriptor that is provably more expressive than traditional PH. Otherwise, the Laplacian spectrum (LS) (defined after Def 3.1) could have been a more generic option, but its expressivity is bounded by SpectRe.

For Section 3, Theorem 3.4 shows that augmenting RePHINE with the non-zero eigenvalues of graph Laplacians is just as expressive as augmenting with the entire family of persistent Laplacian spectra in [1]. This was quite surprising for us, since the definitions of persistent Laplacian are a lot more involved and produces a much larger list. Theorem 3.4, however, shows that there are no additional gains persistent Laplacians would give in this case in terms of expressivity than the more traditional graph Laplacians. Using essentially the proof of Theorem 3.4 in the appendix, the same proof holds for augmenting any descriptor that is at least as expressive as PH. In other words, for any descriptor X such that $X \succeq PH$, augmenting X with the non-zero eigenvalues of graph Laplacians has the same expressive power as adding the entire family of persistent Laplacian spectra.

In Section 4, there were some difficulties we overcame in proving stability for RePHINE and SpectRe that may be quite helpful for proving stability of persistent descriptors whose tuple size is greater than 2 in the future. For RePHINE, the original proof for Bottleneck stability is not applicable to our setting because it does not account for the $\alpha$ and $\gamma$ parameters. In the appendix, to prove Theorem 4.4, we had to come up with the concept of a ``vertex-edge pairing" in Definition A.3. Going from RePHINE to SpectRe, we even lose the global stability of PH and RePHINE as seen in Example 4.6. This was quite surprising to us during discovery. In order to quantify a weaker notion of stability, we used configuration spaces (ie. Conf_n(R)) to describe a local version of stability to correctly describe the stability of SpectRe.

We also want to note that the ``vertex-edge pairing" in Def A.3 and the proofs can give approaches to proving the stability of persistent descriptors whose tuple size is greater than 2.

The main theoretical result ... is not surprising.

Thank you for the opportunity to clarify our work. We want to emphasize that our main theoretical results are not just Theorem 3.3 (on SpectRe being more expressive) but also Theorem 3.4, Theorem 4.4, and Theorem 4.5. We agree that the results of Theorem 3.3 are not surprising - it is included for book-keeping purposes. Please see our comment to the previous question for we find these results to be surprising.

While theoretically more expressive, the empirical improvements on several real-world datasets (Table 3) are marginal. This raises questions about the practical utility of the proposed method, especially when considering its significant computational overhead.

We note that the empirical gains over RePHINE are consistent across datasets. In addition, our topological descriptors can be readily integrated into SOTA graph models, and we have reported additional evidence of their benefits in Table 6 (Appendix) through the combination of SpectRe and Graph Transformers. Using topological descriptors boosts the performance of the graph Transformer in 3 out of 4 datasets. Also, the gains achieved by SpectRe are higher than those of RePHINE.

Most important, our expressivity results are significant and clearly demonstrates benefits of our proposal over existing topological descriptors, which is the primary motivation for our proposal.

On the Choice of Persistent Laplacian Construction: The paper argues that persistent Laplacians offer no more expressive power than the standard graph Laplacian. However, the cited work [49] is one of several constructions. How does this result hold up when considering other definitions, such as the one proposed by Mémoli, Wan, and Wang in "Persistent Laplacians: properties, algorithms and implications"?

Thank you for the question. Actually, the definition proposed by Mémoli, Wan, and Wang in "Persistent Laplacians: properties, algorithms and implications" is equivalent to the cited work's definition in [1]. At the beginning of Section 2.2 in the arXiv v3 of the paper, when the authors Mémoli, Wan, and Wang defined the persistent Laplacian citing precisely the paper in [1]. The authors also directly attributed the definition to come from [1] (and indepdently in [2]) on page 3 of the introduction. We are also not aware of an alternative construction for the persistent combinatorial Laplacians.

On Comparison with Multi-Parameter Persistence

Thank you for the question. We looked more into multi-parameter persistence in the context of our setup, and we have found an example where 2-parameter PH can give more expressive power descriptors than PH alone. SpectRe can be readily adapted to this 2-parameter scheme as well, and we are confident it can make a more powerful descriptor, although we have not investigated an example yet.

In multi-parameter persistence, we define a function f: G -> R^n. There is no time anymore, but rather a partial order on R^n. In our case, we can define a 2-parameter filtration as (fv, fe): G -> R^2, with G_{s,t} = (f_v, f_e)^{-1}( (-infty, s] x (-infty, t]) for (s,t) in R^2.

In this case, we found a pair of graphs that PH for fv and fe (ie. Def 2.2) cannot tell apart, but the 2-parameter scheme above can. Let G (left) and H (right) be the graphs

R - R - B     B - R - R - B
     \---B

In this case, one can check PH in Def 2.2 cannot tell them apart for any choices of fv and fe. Now let fe(R-B) = 1, fe(R-R) = 2, fv(B) = 1, fv(R) = 2. Consider the sub-filtration of the 2-parameter filtration given by G_{*, 1}, ie. (G_{0, 1} -> G_{1, 1} -> G_{2, 1}.) One can check that this is the vertex-coloring filtration fv on the subgraphs:

R   R - B    B - R  R - B
     \---B

In this case, the left one gives persistence pairs (1, 2), (2, 2), (2, infty), (1, infty) (since a R and a B die here at t=2), but the right one gives pairs (1, infty), (1, infty), (2, 2), (2,2) (since two R's die here at t=2). We will include this as an interesting future direction in the paper.

On Local vs. Global Stability: Could you provide more intuition on the practical implications of local stability? Are there realistic scenarios or types of graph data where you would expect the lack of global stability to be a significant issue?

Thank you for your question. The idea for global vs. local stability is as follows. Recall $f_v$ is a function $f_v: X \to \mathbb{R}$ and $f_e$ is a function $f_e: X x X/~ \to \mathbb{R}_{>0}$. Since the domains of $f_v, f_e$ are both finite with say size a and b, we can identify $f_v$ as a point in $\mathbb{R}^a$ and $f_e$ as a point in $\mathbb{R}^b$ (after we fix an ordering on the domains). Every point of $\mathbb{R}^{a+b}$ can thus be viewed as a pair $(f_v, f_e)$.

Intuitively, RePHINE is globally stable in the sense that it is a continuous on $\mathbb{R}^{a+b}$ with respect to the bottleneck distance in the codomain and a suitable metric on $\mathbb{R}^{a+b}$ given by the bound in Theorem 4.4.

Intuitively, SpectRe is locally stable in the sense that it is only continuous on $\mathbb{R}^{a+b}$ with a subset (the region of non-injectivity in the paper) removed, which typically has multiple connected components. When SpectRe crosses from one component to other, the output jumps drastically and is not continuous. It is only locally continuous.

Numerically, what this means is - for global stability, any two pairs of filtration functions are bounded by the inequality in the paper. For local stability, only a pair X of injective filtraiton functions and another pair sufficiently close to X satisfies the same inequality.

We do not expect the lack of global stability to be a significant issue, since we want stability to ensure that tiny perturbations in the input filtrations do not change the output drastically. For sufficiently small perturbations, the local stability would always suffice.

On the Choice of Filtration: The performance of SpectRe can be dependent on the choice of the initial vertex and edge filtration functions. Do you have any general guidelines or heuristics for choosing effective filtration functions for a given graph learning task?

Thank you for your question. Both fixed and learnable filtration functions have been explored in the literature. Fixed functions offer advantages in terms of computational efficiency and interpretability. In contrast, recent works (e.g., Topological GNNs, ICLR 2022) have applied learnable filtration functions, which adapt to the task and data, potentially leading to improved performance. In our real-world experiments, we opted for learnable filtration functions to allow greater flexibility and task-specific adaptation.

---

Many thanks for your insightful review and constructive feedback. We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional questions, concerns, or suggestions.

[1] Persistent spectral graph. R. Wang, D. Nguyen, G. Wei. [2] Talk: Persistent harmonic forms. A. Lieutier.

The proof of .. Theorem 3.4 appears to rest on an analysis ... 1-dim complexes (graphs). ... It would strengthen the paper to include a discussion of this limitation, clarifying that the claim holds for graph-only filtrations but may not generalize to richer simplicial filtrations (e.g. rips complex) where the full power of the persistent Laplacian would be unleashed.

Novelty of Theorem 3.4

B1 = [0 0];
B2 = [-1 0 0; 1 -1 0; 0 1 -1; 0 0 1];
Gind = [1 4];

Theorem 4.4