Graph Persistence goes Spectral
Authors: Mattie Ji
Amauri H Souza
Vikas K Garg
Venue: NeurIPS 2025 poster ()
Keywords: topological data analysis
graph neural networks
graph machine learning
Primary area: deep_learning
TL;DR: We incorporate spectral information to the PH-based method RePHINE and analyze its expressivity, stability, and empirical performance.

Abstract: Including intricate topological information (e.g., cycles) provably enhances the expressivity of message-passing graph neural networks (GNNs) beyond the Weisfeiler-Leman (WL) hierarchy. Consequently, Persistent Homology (PH) methods are increasingly employed for graph representation learning. In this context, recent works have proposed decorating classical PH diagrams with vertex and edge features for improved expressivity. However, these methods still fail to capture basic graph structural information. In this paper, we propose SpectRe --- a new topological descriptor for graphs that integrates spectral information into PH diagrams. Notably, SpectRe is strictly more expressive than PH and spectral information on graphs alone. We also introduce notions of global and local stability to analyze existing descriptors and establish that SpectRe is locally stable. Finally, experiments on synthetic and real-world datasets demonstrate the effectiveness of SpectRe and its potential to enhance the capabilities of graph models in relevant learning tasks.  Code is available at https://github.com/Aalto-QuML/SpectRe/.

Graph Persistence goes Spectral
Mattie Ji University of Pennsylvania mji13@sas. upenn edu
Amauri H. Souza Federal Institute of Ceará
Vikas Garg Aalto University Yai Ltd
edu.br br
vgarg@csail.nm
Abstract
Including intricate topological information (e.g.. cycles) provably enhances the ex- pressivity of message-passing graph neural networks (GNNs) beyond the Weisfeiler- Leman (WL) hierarchy. Consequently, Persistent Homology (PH) methods are increasingly employed for graph representation learning. In this context, recent works have proposed decorating classical PH diagrams with vertex and edge fea- tures for improved expressivity. However, these methods still fail to capture basic graph structural information. In this paper, we propose SpectRe - new topo- logical descriptor for graphs that integrates spectral information into PH diagrams. Notably, SpectRe strictly more expressive than PH and spectral information on graphs alone. We also introduce notions of global and local stability analyze ex- isting descriptors and establish that SpectRe is locally stable. Finally, experiments synthetic and real-world datasets demonstrate the effectiveness of SpectRe and its potential to enhance the capabilities of graph models in relevant learning tasks. Code available at https: github. com Aawto-allolooo-a QWMM/SpectRR//////
Introduction
Relational data is ubiquitous in real-world applications, and can be elegantly abstracted with graphs. GNNs are state-of-the-ard models for graph representation learning [10, 11, 28, 36, 51, 55, 62]. Almost all commonly employed GNNs can be cast as schemes where nodes repeatedly exchange messages with their neighbors [25]. Despite empirical success, GNNs are known to have some key limitations.
Notably, due to their strong local inductive bias, these GNNs and their higher-order counterparts bounded in power by the WL hierarchy [40, 41, 43, 62]. Furthermore, they fail compute important graph properties such as cycles and connectivity [15, 24]. Topological descriptors such as those based PH can provide such information not just for GNNs but also the co-called topological neural networks (TNNs) that generalize pressage-passipgg to nigher-dimensiona, topological domains, enabling more nuanced representations than the standard GNNs [6-8, 22, 26. 27, 46, 47, 56].
Specifically, PH employs filtration (or filter functions) that can track the evolution of key topological information; e.g., when
component starts or the time interval during which a component survives (until two components merge, or indefinitely). This persistence information is typically encoded (birth, death) pairs, or more generally tuples with additional entries, in a persistence diagram. The topological features derived from these persistence diagrams can be integrated into GNNs and TNNs enhance their expressivity and boost their empirical performance [56]. PH is thus increasingly being utilized in (graph) machine learning [1, 9, 13, 14, 29-31, 49, 54, 63, 64, 66, 67].
Understandably, there is growing interest in designing more expressive PH descriptors for graphs [2]. Recently, Immonen et al. [33] analyzed the representational ability of color-based PH schemes, provid- ing complete characterization of the power of O-dimensional PH methods that employ vertex-level or edge-level filtrations using graph-theoretic notions. They also introduced RePHINE as a strictly more powerful descriptor than these methods. However, turns that RePHINE is still unable to 39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Overview of our theoretical results.
Expressive Power of Filtration Methods (Section 3)
Construction of SpectRe Diagrams
Definition 3.1
Spect is isomorphism invariant
Theorem 3.2
SpectRe > RePHINE and SpectRe > Laplacian Spectrum
Theorem 3.3
Stability of RePHINE and SpectRe Diagrams (Section 4):
Construction of suitable metric d on RePHINE
Definition 4.2
Construction of a suitable metric
di Spee it
on SpectRe
Definition 4.3
RePHINE is globally stable under d'B
Theorem 4.4
Re is locally stable under Sppee
Theorem 4.5
Estimate on the Extent of Instability for d R
Theorem 4.7
Verifying d and dege R are metrics
Proposition A.2
separate some simple non-isomorphic graphs: c.g., on monochromatic graphs, RePHINE recovers the same information as vanilla PH. We, therefore, seek to design a more expressive PH descriptor here.
Our key idea is to enhance the persistence tuples of RePHINE with the evolving spectral information inherent the subgraphs resulting from the filtration. Spectral information has been previously found useful in different learning tasks graphs [4, 5, 32, 37, 38, 57, 60], which motivates investigations into extracting spectral signatures from the graph Laplacian.
Laplacian appears in several flavors: unlike graph Laplacian (the O-th combinatorial Laplacian), rows in the 1-st combinatorial Laplacian correspond to the edges of the graph (as opposed to vertices), and ligeer-dimensional persistent versions [59] have also been proposed for both. Since
interested in graph-based filtrations, simply tracking the graph Laplacian of filtered subgraphs provides all the additional expressivity that the higher-order generalizations of the Laplacian offer. Guided by this key insight, we introduce a new topological scheme called Spect that amalgamates RePHINE and graph Laplacians to be strictly more expressive than both these methods.
Furthermore, we unravel the theoretical merits of SpectRe. Specifically, stability is a key desideratum of PH descriptors [16]. Stability of PH is typically assessed via a bottleneck distance, which provides a suitable metric on the space of persistence diagrams (obtained from different filtration functions). The bottleneck distance guarantees a minimum separation between the filtered spaces, which makes persistence diagrams an effective tool in several applications such as shape classification and retrieval [3]. Stability results are known for standard persistence diagrams in [16, 39, 58]. However, since PH metrics for the persistence diagrams in edge-level filtrations are agnostic the node color, even defining a suitable metric to quantify stability is challenging for methods such as RePHINE (that strictly generalizes PH with node colors). We first fill this gap with a novel generalization for the bottleneck distance that forms metric on the space of persistence diagram of RePHINE, and establish that RePHINE is globally stable under this metric. Interestingly, we proceed to show that SpectRe is globally stable but only locally stable (which suffices for practical applications) under similar metric, outside of measure zero subset of all possible filtrations. Moreover, we quantify an explicit upper bound on how unstable SpectRe can be when "crossing over a locus of instability" in terms of the complexity of the input graph.
To validate theoretical analysis and show the effectiivnness of SpectRe diagrams, conduct ex- periments using two sets of synthetic datasets for assessing the expressive power of graph models (13 datasets in total), and multiple real datasets. Overall, these results demonstrate the higher expressivity of SpectRe and illustrate its potential for boosting the capabilities of graph neural networks on graph classification. We summarize our theoretical results in Table 1, and relegate all the proofs Appendix.
2 Preliminaries
Unless mentioned otherwise, we will consider graphs G (V, F,ce, e, X) with a finite vertex set V, edges E C V V. and vertex-coloring function V + X, where X is finite set denoting the

---

space of available colors or features. All graphs are simple unless mentioned otherwise. Two graphs G EV, c, X) and G' (V', E", c',''') are isomorphic if there is bijection h V of the vertices such that (1) the two coloring functions are related by c = d' o h and (2) the edge (v, w) is in E if and only if (h(v)), ((w)) is in F'.
We remark the first condition ensures that isomorphic graphs should share the same coloring set. For example, the graph K3 with all vertices colored "red" will not be isomorphic to the graph K3 with all vertices colored "blue", as it fails the first condition. For the rest of this work, we will assume that all graphs that appear have the coloring set X (we can always, without loss of generality, take X to be the union of their coloring sets). In this work, we are interested in graph features that change over time (i.e. persistent descriptors) as opposed to static features. Our notion of time will be color filtration of graph defined as follows.
Definition 2.1 (Coloring Filtrations). On color set X, we choose a pair of functions (Ju X RR Se X x X + Rk50) where fa is symmetric (i.e. Se(a, b) = sb a) for all a, b X). On graph G with vertex color set X, the pair fe) induces the following pair of functions (Fe VUEEEEE + IR, Fe VUEE- + R20).
1. For all v E V(G), P.(e) == fe(c(v).. For all e E E(G) with vertices U1, 222. (e(e) = max(F,(21) F((2)) Intuitively, we are assigning the edge e with the color c(arg max, F. (v.))) (the vertex color with a higher value under fe).
2. For all v E VV)) (o( = O. For all e(G) with vertices v1 U2, Fo(e) = f.(c(v)). Intuitively, we are assigning the edge with the color (c(v1), c(v2)).
For each & E R, we write G. = Fara(((o00 ((-o0, (o,t)) f)) and Gf F. ((-oo,).
Note we chose the notation "G."" and Gf as opposed to "G.- and Gffe" to emphasize that the function G + (IG))) HER (G.: }R) is well-defined for any graph G with the common coloring set X. The lists (G/- HER and (G heR define vertex filtration of G by F, and edge filtration of G by Fe respectively. is clear that -.- can only change when t crosses critical value in (fu(c) : E X), and G can only change when f crosses a critical value in {fe(c1, 02) (21, E X X}. Hence, we can reduce both filtrations to finite filtrations at those critical values.
2.1 Persistent Homology on Graphs
The core idea of persistent homology is track how topological features evolve throughout filtration, accounting for their apparanceddisapperrnce. In particular, we say a vertex e (i.e. O-dimensional persistence information) is born when it first appears in given filtration. When merge two connected components represented by two vertices v and w, we use a decision rule to kill off one of the vertices and mark the remaining vertex represent the new connected component. Similarly, cycle (i.e. 1-dimensional persistence information) is born when it appears in a filtration, and it will never die. For vertex an edge e, we mark its persistence pair as the tuple (b, d). where b and d indicate its birth and death time respectively (here d = oo if the feature never dies).
For color-based vertex and edge filtrations, there is canonical way to calculate the persistence pairs a graph for given filtration. We refer the reader to Appendix A of Immonen et al. [33] for a precise introduction. Following the terminology in Immonen et al. [33], we say 0-th di- mensional persistence pair (b, d) is a real hole if d = co, is an almost hole if b & d oc, and is trivial hole if b = d. Note that edge-based filtrations do not have any trivial holes.
(L.
Ml DL 2 ( (Boo)
Figure 1: Vertex-level PH: filtration and di- agram induced by fu- Here, we have that S. = and (.((re)) =2
Definition 2.2. Let f= fe) be on the coloring set X,
as in Definition 2.1. The persistent homology (PH) diagram of a graph G is a collection PH(G, f) composed of two lists PH(G, f) PH(G.f) where PH(G,f) f) are persistence pairs in the vertex filtration (G. HER and (H(G.f) f) are all pairs in the edge filtration (G!- hERR
Figure depicts a vertex filtration along with its 0-th dim PH diagram PH We also provide in Figure 2 the persistence pairs of PH(G, f) for the same graph.
3

---

2.2 RePHINE
Despite the growing popularity of PH in graph representation learning, PH alone does not fully capture local color information. To overcome this limitation, Immonen et al. [33] introduced RePHINE as generalization PH.
Definition 2.3. Let / = (Se, fe) be on X. The RePHINE diagram of graph G is a multi-set RePHINE = RePHINEEG, f) RePHINE, f) 2 of cardinality IV(G)) + fg where:
0-th dimensional component: RePHINE f) consists of tuples of the form (b(v), d()), a(v), 7(0) for each vertex v V(G). Here, b(v) and d(v) are the birth and death times of v under the edge filtration { JIRR. a(v) fo(c(u)) and 7(v) = min ((e) fe (c(r),c(w)) where (N) denotes the neighboring vertices of v.
The decision rule for which vertex to kill off is as follows an almost hole (6, d) corresponds to the merging of two connected components with vertex representatives d1 and U2. We kill off the vertex with greater value under a. If there is a tie, we kill off the vertex with a lower value under y. If there is further tie, Theorem of Immonen et al. [33] shows that the resulting diagram RePHINE(G, f] is independent of which vertex we kill off here. 1-st dimensional component: for each e in the first persistence diagram. d(e) indicates the birth time of a cycle in the same filtration. the definition of Immonen et al. [33], the birth of a cycle corresponds to what is called the death of a "missing hole". This is why we use d to indicate the birth time instead.
(aPHINE(G.,) f)² consists of tuples of the form (1, d()), 0)
Theorem of Immonen et al. [33] asserts that RePHINE diagrams are strictly more expressive than PH diagrams.
3
Spectrum-informed Persistence Diagrams
We now introduce a novel descriptor, called SpeciRe, that incorporates spectral information. We also demonstrate its isomorphism invariance and analyze its expressive power.
3.1 Laplacian Spectrum and SpectRe
Homology captures harmonic information (in the sense that the kernel of the graph Laplacian cor- responds the 0-th homology), but there some non-harmonic information we also want account for. One option is to account for colors, as we have done with RePHINE. Another option is to augment RePHINE with spectral information. Building on this idea, we propose new descriptor below.
Definition 3.1. Let f (fe. be on the coloring set X. The spectral RePHINE diagram (SpectRe, in short) of graph G is multi-set SpectRo(G, SpectRo(G, f) Spe of cardinality |V(G)) + A where:
Sp) consists of tuples of the form V(G). Here, b, d, a, are the same as Definition 2.3, and p(u) is the list of non-zero eigenvalues of the graph Laplacian of the connected component is in when it dies at time d(v).
0-th dimensional component:
(()), (v)) p(v)) for each vertex
1-st dimensional component: SpectRe(G,, f)² consists of tuples of the form (1, d(e), O, O, p(e)) for each e in the first persistence diagram. Here, d(e) indicates the birth time of cycle given by the edge p(E) denotes the non-zero eigenvalues the graph Laplacian of the connected component is when it is born time d(e).
For completeness, we also define the Laplacian spectrum (LS) diagram of graph G as the projection of Spect to its I-component, d-component, and p-component. Figure 2 shows an example computing SpectRe, RePHINE, and LS on the same graph and filtration.
3.2 Expressive Power
Here, we compare the expressivity SpectRe to both RePHINE and Laplacian spectrum, showing that SpectRe is strictly more expressive than the other two. We also discuss alternative, more

---

The intuition behind why RePHINE cannot differentiate the examples in Figure 3 is that has the same amount of expressive power counting the number of connected t = 0
t=1
t= 2
t == 3
2
3
3
3
2
2
2
2
2
2
2
2
(D.sr)) (0...)
2,,12,1, (2) (0,, 1.)
1, 1. (2)
2.
1.. (2) (222222 00,2,1,2 2)
SpectRe
(0..)) (..)
10...)0...0
0,,2,1,2 (2) 10,112
(2,2
(..)
(L..0.0.)
(L3.00.0
(0...) (...)
(0, 1,1,2,00 (0.22) (0....(0..... (4,,0,0)
1.,1,2.1 20
(0,122 3
RePHINE
(O..)
(0.2, 1,2)
(0,2,1,2 (x. (1.3.0.0)
(1,0,0)
(1,,0,0)
Odh: (0.) (0.) (0,)
Odh (0, 1) (0.) (0.) (0.)
Od: (0. (0.)
Oth: (0. 1) (0. (0.2) (0, (0,
PH(())
[0, (0.)
Ist
Ist:
lst:
(0. (0..
(0, (2), (0..)
(0, 1. (2)) (0..)
10.1 (2)
(., (2,2,4)
LS
( (o..)
(0..) (0..)
(0.2, (2)) (0..) (1..)
(0.2 2..2. (
00 (2.2. (2,2,4)
(..))
(1..)
Figure 2: Example computing SpectRe, RePHINE, (edge-level) PH, and LS on graph G with fu 1, (red) 2 and f<(red) 1, febluee 2, fo (red-blue) The graph G has an edge filtration fc.
elaborate definition of SpectRe we initially considered using the ideas of a "persistent Laplacian" in Wang et al. [59]. The upshot is that we show this approach is as expressive as our current definition.
To be precise on what we mean by expressivity, let X, Y be two graph isomorphism invariants. We say X has least the same expressivity Y (denoted X > Y) for all non-isomorphic graphs G and Hl that Y can tell apart, X can also tell them apart. We say X is strictly more expressive than Y (denoted tell apart but X can. We say X and Y have the same expressive power (denoted X Y) if X ž Y and Y > X. We say X and Y incomparable if there are two non-isomorppic graphs G and H that X can tell apart but Y cannot, and vice versa.
> Y) if, addition, there exist two non-isomopphic graphs G and H that cannot
Before analyzing SpectRe's expressivity, we must first verify its invariance to graph isomorphism.
Theorem 3.2. Suppose G and H are isomorphic graphs with the same color set X. Let f (fer fe) be any filtration functions finnttion on X, then SpectRe(G, equal to SpectRe(H,
Now we state the expressivity comparisons of SpectRe, RePHINE, and the Laplacian spectrum (LS).
Theorem 3.3. SpectRe is strictly more expressive than both RePHINE and LS, which are incomparable to each other. Furthermore, the counterexamples are illustrated in Figure
(a)
(b)
components and independent cycles (i.e. the harmonic components of the Laplacian) (see Lemma C. Introducing spectral information (i.e. the non-harmonic components of the Laplacian) can give lens to a wider scope to distinguish these graphs.
monochromatic graph
G
H
H
It is well-known that the kernel of the graph Laplacian of G has the same dimension as the number of connected components (i.c. 0-th Betti number) of G. There is generalization of graph Laplacians to "combinatorial Laplacians" (whose kernels yield higher Betti numbers) and even kernels yield the persistent Betti numbers). One might ask whether incorporating their spectrum into RePHINE would result in greater expressivity than SpectRe.
Figure 3: (a) Graphs that SpectRe and LS can separate but not RePHINE. (b) Graphs that SpectRe and RePHINE can separate but not LSS
generally "a persistent version of Laplacians" [59] (whose
5

---

Proposition 3.4. Consider an alternative topological descriptor on G (V. given by ((f) = {[b(v), d(v)), a(()),(())))))))))))())))()))( (t)) where the first four components are the same as RePHINE (Definition 2.3), pf (t) returns the spectrum of the persistent Laplacians in [59] on the connected component v dies in, and pe())
{((e), d(e)) a(e), (e cycles).
returns the spectrum of the persistent Laplacians of the connected component e born in.
If we remember which vertex and edge is assigned to which tuple in the computation, + has the same expressive power as SpectRe.
In other words, augmenting RePHINE with the spectrum of persistent Laplacians is just as expressive as including the spectrum of the graph Laplacian. Note that the assumption for remembering the tuple assignment is always satisfied in practice, as computing SpectRe, RePHINE, or PH-based methods in general would go through such assignments (see Algorithm and 2 of [33]). It then suffices for us to focus on graph Laplacians hereafter.
We provide self-contained proof of Proposition 3.4 in Appendix B for completeness. Note that the comparison in Proposition 3.4 can be derived from a fact noted in Example 2.3 of [45] and Section of [19]. We remark that is unclear how Proposition 3.4 would follow without assuming the underlined condition that we remember the tuple assignment, which is a situation that [19, 45] did not encounter since their design of descriptors different from ours.
4 Stability of RePHINE and SpectRe
Let f (fu -, X xxx- - Rs0) and g = (ge X + ge X X two pairs of functions on X. For graph G with the coloring set X, we would ideally like way to measure how much the diagrams we constructed in Section 2 differ in SpectRe of f and g. One way to measure this is to impose suitable metric bound. For PH diagrams on G. this suitable metric is called the bottleneck distance and has been classically shown be bounded by [[ - golloo + IIʃe gelloo [16]. In this section, we will discuss a generalization of this result to RePHINE and Spect Re diagrams.
R>o) be
the space of diagrams and obtain a stable
Let us examine RePHINE first. One naive proposal for suitable "metric" on RePHINE diagrams would be to restrict only to the first two components (b and d) of the multi-set and use the classical bottleneck distance for persistence diagrams. However, this approach ignores any information from the a and y components and will fail the non-degeneracy axioms for a metric. Thus, we need to modify the metric on RePHINE diagrams to take into account of its and components.
For ease of notation, we introduce the following definition simplify our constructions.
Notation 4.1. Let A and B be two finite multi-subsets of the same cardinality in a metric space (X, dx), we write Bott(A, dx) == inf Ebbjecctoos A B maXpe A dx (p, (p)).. Informally, Bott(A, B, dx) is the infimum of distances for which there is a bijection between A and B in X.
Note that when X = R and dx is the form, we recover the definition of bottleneck distance for PH diagrams. Now we will define a metric for RePHINE diagrams.
Definition 4.2. Let RePHINE(G. f) and RePHINE(G, g) be the two associated RePHINE diagrams for G respectively. We define the bottleneck distance as dit (RePHINE(G. f). RePHINE(G,, g)) = aR.D (RePHINE(G, B
RePHINE(G, g) + d (RaPHINE(G, f) (oCPHNE(GG,g))
Here, di,0( and di (o, are both given by Bott(e, d). where d' is defined on I as d((bg do 0o: 70); (b, d1, 01 71) = max(lb] bul. Idg dol} + |01 ool + h vol-
Similarly, we define a metric for Se diagrams.
Definition 4.3. We define the bottleneck distance between SpectRe diagrams as &See R,0 (SpectRe(G, f),, ()p.tf))))SecR(CG.gg)) Spec R, (Spec SSeecdeeG..s)))
Spec R (SpectReeG,,f) SpectRo g)) S
Here, S Sper R.0 and Spoc n11 (o. 9) are both given by Bott( ,, d'), where d' is defined on T2.' as d' ((bb,, do, oo, Yo. Po), (b,, d,, a, m. Pi)) = d((bo, do, ao. 70). (b,, di, a1, 71)) + Speee (po,

---

Here, d is given in Definition 4.2 and d is given by embedding Po and P1 as sorted lists (followed by zeroes) into el (N) and taking their el -distance in l (N).
We verify in Appendix A.2 that Definition 4.2 and Definition 4.3 are indeed metrics. We also prove that the bottleneck distances of two RePHINE diagrams may be explicitly bounded in terms of the er norms of the input functions, and hence RePHINE diagrams stable in the following sense.
Theorem 4.4. For any choice of f = (fu and g = [gv. as before, we have the inequality
B (RePHINE(G, f), RePHINE(G,,) s 3|1ʃe - ge loo + 115u gulloc.
RePHINE diagrams are regarded globally stable in the sense that no matter what f and g we choose, their respective RePHINE diagrams are bounded by a suitable norm on and g. SpectRe diagrams, contrast, only satisfy local form of stability. We make precise what local means by introducing a suitable topology on the possible space of filtration functions.
After fixing canonical ordering on X and X X/ separately, we may view fo (resp. fe) as an element of ~n* (resp. (R>o)"r), Furthermore, if fu (resp. f.) is injective, it may viewed as an element in Conf,, (I)) (resp. Confn, (R>>)),, where Conf,, (IR) (resp. Conf (R>o)) is the subspace of "h" (resp. (R>o)"*) composing of points whose coordinates have no repeated entries. From here obtain the following theorem.
Theorem 4.5. If Ju and fa are injective, then f f= (fus (e. fe) is locally stable on Conf m. (R) x Co (R))) under depee It That is, over graph G with the coloring set X, we have:
dSee R. (SpectRe(G, SpectReG g)) S 3|1fe gelloo + +Iff. gulloo
for all g (ge. ge) sufficiently close to in Conf (ER Conf (R>o). Furthermore, the same bound holds without imposing the local stability condition in f..
Local stability suffices in practical applications. Note that the injectivity assumption is necessary for fe, and SpectRe is not globally stable in general. We illustrate this in the following example.
Example 4.6. Let G the path graph on vertices colored in the order red, blue, blue, red. Let fo = be any functions. Let 9e be constant with value 1, and fe be given by (red, blue) = 1, (blue, blue) = e for e > small, and [e red) any value. SpectRe(G.) J) has 1 tuple representing blue vertex that dies at time = - whose p-parameter is (2). In contrast, every tuple of SpectRe(G: 9)" has its p-parameter equal the list L = {2, 2 + v2). No matter how small e > 0 is, the distance on their SpectRe diagrams is bounded below by
d
Spee
Spec (Spec(()). L) 0.
Thus, SpectRe could fail to be locally stable without the injectivity assumption.
We also note that SpectRe is not globally stable, even with the injectivity assumption. A counter- example can be found by changing 9e in the same example to the function given by ge (red, red) = fe (red, red), Ie (red, blue) 1, and g. (blue, blue) 1 for 0. The intuitive reason is that to change ge (blue, blue) = 1 + to fa (blue, blue) = e, De has to become non-injective when its value at (blue, blue) crosses 1.
We can, however, obtain bound to how unstable the situation becomes when injectivity is violated.
7

---

Theorem 4.7. Let G be a graph and let fe be an injective edge fitraatin function with values [ei) for each edge color lype 6,. Let ge. be a perturbation of Ie
< < On with such that = {c)e for all 4 i, and ge(ez) = (e(e)41)= = 04+11 (ie. ge merges the i-th and i+ 1-th value together). Let fo. 9e be veriex filtration functions, then the distance between the O-dimensional components of SpectteeG, fe) and SpectRe(Ca Ios 9e) is bounded by
l1g. - fulloe + +((as+1 - -a,) [Q,)+ +
max (Hi,
-
where Y is the collection of pairs (H,, H2) where H1 is the connected graph that a vertex v died at time a, for fe is contained in, H2 is the connected graph the same vertex v died time 01+1 for Gr is in, and H1 C H2.
The distance between the 1-dimensional components of SpectRe(G, fo: and SpectRe(G,, Iv. Ie> ) bounded by
(ai+1 a.) + max HH)EZ
E(H2) (E(H))),
where Z is the collection of pairs (I,,, H2) where Hi is the connected graph that cycle- creating edge e born at ag for Se is contained in, H2 is the connected graph for the same edge e time 1 for go. and Hi C H2.
We conclude this section by remarking that analyzing the stability of RePHINE and Sp is more challenging than one might expect. For RePHINE, the values can be interpreted as the birth time of the vertices, but there was no clear interpretation of what the y values are terms of the birth/death time of a simplex, rendering direct application of the stability of PH fruitless. For SpectRe, the filtration method was not globally stable, which came as a surprise us. To circumvent this finding, we instead came up with new description of the topology of the filtration functions and showed it is locally stable under this topology. For both RePHINE and SpectRe, it was also unclear how the setting of Bottleneck stability would change since the original metric on persistence pairs [16] was given by the -noms,, but we adopted various other norms in this work.
Integration with GNNs
Like most topological descriptors for graphs, SpectRe can be seamlessly integrated into GNNs. Fol- lowing Immonen et al. [33], use GNN representations each layer as inputs to filtration functions and obtain a vectorized representation of the entire diagram by encoding its tuples with DeepSets [65]. However, unlike existing methods, we must also encode the spectrum (the p component) associated with each tuple. To this end, we use an additional DeepSet model dedicated to processing these spec- tral features. Consequently, at each GNN layer, we obtain new SpectRe diagram which we then vec- torize (as described above). These representations are then integrated into the GNN - for example, by concatenating them with the graph-level GNN's embedding just before the final classification head.
Formally, let SpectRe(G** fky0 be the 0-th dimensional SpectRe diagram obtained at the k-th GNN layer. Since each element of the diagram is associated with node v, we compute the topological embedding r of SeectRe(G*, (
0 as
0 di
Σ (P)
2 = 02
Σ v2 (M) DEV
(1)
pEp(o)
where 0% o2 W/ dh are feedforward neural networks. We follow analogous procedure obtain 1-dimension topological embeddings at each layer.
It is worth noting that there are alternative ways to integrate topological embeddings with GNNs. For instance, instead of computing a diagram-level representation, Horn et al. [31] incorporates vertex-level representations, 7 by adding them to the node embeddings of the GNN at each layer.
8

---

Table 2: Accuracy in distinguishing all pairs of minimal Cayley graphs with nodes (c-n) and graphs in the BREC datasets. We use degree vertex filter (fx) and Forman Ricci curvature as edge filter (f.). SpectRe separates all Cayley graphs and is the best performing method on BREC datasets. Note that some outputs are slightly different from earlier versions of the paper due to minor bug in the code (see Appendix E for further details).
Cayley Graphs
BREC Datasets
Methods
c-12
C-16
e-20
e-24
o-32
e-36
c-60
c-63
B (60)
R (50)
E (100)
(100)
D (20)
All (400)
PHF
0.67
0.83
0.61
0.65
0.76
0.69
0.69
0.49
0.03
0.00
0.07
0.03
0.00
0.03
PH
0.95
0.83
0.61
0.86
0.76
0.84
0.98
0.94
0.55
0.03
RePHINE
0.95
0.83
0.61
0.86
0.76
0.84
0.78
0.73
0.98
0.94
0.55
0.03
0.00
0.41
Speciit
1,00
1.00
1,00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.04
0.05
0.54
Experiments
To assess the effectiveness of SpectRe from an empirical perspective, we consider two sets of experiments. The first consists of isomorphism tests on synthetic benchmarks designed evaluate the expressive power of graph models. The second explores the combination of topological descriptors and GNNs in real-world tasks. Implementation details are provided in Appendix E, In addition, our code is publicly available at https: // thub. com/ SallttoQuML/Speeeeee
6.1 Synthetic data
Following Ballester and Rieck [2], we consider datasets containing minimal Cayley graphs with varying numbers of nodes [18] and the BREC benchmark [61] details are given in the Appendix. We compare four topological descriptors (PH", PH' RePHINE, and SpectRe) obtained using fixed filtration functions. Specifically, we use node degrees and augmented Forman Ricci curvatures [50] as vertex- and edge-level filtration functions, respectively
i.e., fu(u) (N( and fu, w) = 4 [N)x)] (w) (N Note that only RePHINE and SpectRe leverage both functions as PH applies (u, w) = max f. (u), (ww) and PH uses (u( = 0 for all u.
Table 2 presents the accuracy results for the Cayley and BREC datasets. Here, accuracy represents the fraction of pairs of distinct graphs for which the multisets of persistence tuples differ. In all datasets, the performance of PHO is bounded by that of PH² while PH" performs on par with RePHINE. Interestingly, for most datasets, these descriptors distinguish exactly the same graphs. Notably, SpectRe can separate all pairs of minimal Cayley graphs. Overall, РH struggles to distinguish graphs across all BREC datasets, indicating that degree information is not informative in these cases. Except for the (regular) Distance dataset, these results confirm the high expressivity of SpectRe on exploiting complex graph structures, even under simple degree-based filtrations. We note that the BREC datasets 'strongly connected' and '4-vertex condition' were omitted from the table since no descriptor can separate any their pairs of graphs. For completeness, Figure 4 illustrates pair of graphs that RePHINE does not separate but SpectRe does.
Figure 4: Example of pair of graphs from the dataset Ex- tension( 100) that RePHINE cannot distinguish but Spec- (Re can. Node and edge labels denote filtration values.
6.2 Real data
To illustrate the potential of SpectRe on boosting the power of GNNs, we consider nine datasets for graph-level predictive tasks: MUTAG, PTC-MM, PTC-MR, PTC-FR, NCII, NCI109, IMDB-B. ZINC, MOLHIV [42]. Again, we wish to compare SpectRe against PH (vertex filtrations) and RePHINE. Thus, we consider the same GNN architecture for all diagrams: graph convolutional network (GCN) [36]. We provide additional results using graph Transformers in the Appendix. Impor- tantly, diagrams are vectorized exactly the same way using DeepSets. We report the mean and stan- dard deviation of accuracy (MAE for ZINC, and AUROC for MOLHIV) over three independent runs.

---

Table 3: Predictive performance graph classificatio//eggresionn We denote the highest mean accuracy (lowest MAE for ZINC) in bold. For most datasets, SpectRe is the best performing model.
Method
MUTAG
PTC-MM
PTC-MR
PTC-FR
NCI1
NC1109
IMDB-B
ZINC
MOLHIV
GCN 63.2-4.7
$6.9
58.111.6
6..6116
74.33.1 2.58
73.49 10.86
69.00.1.41
0.87.1001
1..7
PH
82.5=6.0
59.8=744
55.2=3.3
65.7+9.7
77.37+2.06
76.15:2255
71.00:0.000
0.53= 0.01
71.31
RePHINE
87.2=3.0
1..8-1.6
58.1-119
68.5166.
80.66111.55
76.51=1.03
75.0012..3
0.47.0001
76.03.10.48
SpectRe
91.2-3.0
61.7=29
59.1=59
69,4:2.8
80.90:0.17
76.63=0.86
76.00:00.00
0.48:00.22
76.33+0.57
To enable SpectRe for large datasets (e.g., NCI1, ZINC and MOLHIV), we employed the power method for computing the largest eigenvalue > and used the full spectrum otherwise. In addi- tion, we applied scheduling: we only computed the eigendecomposition at 33% of the filtration steps.
Table 3 shows the results real-world data. SpectRe achieves the highest mean accuracies in 8 out of 9 cases, with a significant margin on the MUTAG and PTC-MM datasets. In most cases, the second best performing model is RePHINE. Overall, these results support the idea that GNNs can benefit from PH-based descriptors on real-world graph learning tasks.
Additional experiments. For completeness, Appendix F includes further experiments using Graph Transformers [48], along with ablation studies and an empirical assessment our stability bounds.
Limitations. Like most highly expressive graph models, SpectRe's ' power comes at the cost of increased computational complexity. The overhead of computing eigendecomposition across graph filtrations is non-negligible and can become a bottleneck for large-scale real-world datasets. Specifi- cally, on graphs, 0- and I-dimensional persistence diagrams can be computed in Om log m) time using disjoint sets, where m is the number of edges. Since SpectRe requires eigendecomposittin, in the worst case, the cost is (rr²) which comes from a fully connected graph with the eigendecomposi- tion being applied to ( filtration steps. In the best case (considering connected graphs), the whole graph is revealed at the same time and the cost is Onn)). Fortunately, there are faster algorithms for computing (or approximating) partial spectral information. For instance, to experiments on large datasets, one can employ LOBPCG or the power method, which reduces the time complexity to O(kn") in the worst case, where k is the number of iterations (often much smaller than n). If we further consider scheduling, i.e., only applying decomposition to a fixed number of filtration steps, can further reduce the worst-case complexity to Okk??).
In this work, we focused on color-based filtrations of graphs. However, exploring alternative constructions (e.g.. biparameter or Vietoris-Rip filtrations) would be interesting research direction. Also, while SpectRe incorporates spectral information with respect to edge-based filtrations, it would also be worthwhile investigate how they interact with vertex-basee filtrations. We discuss these directions in greater detail in Appendix D.
7 Conclusion
We augmented PH-based descriptors on GNNs with the Laplacian spectrum, focusing expressivity, stability, and experiments. For expressivity, we amalgamated spectral features with RePHINE to craft strictly more expressive scheme SpectRe than both RePHINE and the Laplacian spectrum. For stability, we constructed a notion of bottleneck distance on RePHINE and SpectRe. We showed that the former is globally stable, and the latter is locally stable. Building on our theoretical foundations, we proposed an integration of SpectRe with GNNs and "vectorized" the spectral component using DeepSets. We also benchmarked SpectRE against other TDs in this work on both synthetic and real data, showing empirical gains with our new approach.
Broader Impact
While we do not anticipate immediate negative societal impacts from our work, we believe it can serve as catalyst for the development of principled learning methods that effectively integrate topological information into graph representation learning. By enhancing the expressivity of graph- models, such approaches hold promise for advancing wide range of applications - including molecular modeling, drug discovery, social network analysis, recommender systems, and material design where capturing multiscale structural and topological dependencies is essential.
10

---

Acknowledgments and Disclosure of Funding
This research was conducted while the first author was participating during the 2024 Aalto Science Institute international summer research programme at Aalto University. We are grateful to the anonymous program chair, area chair and the reviewers for their constructive feedback and service. VG acknowledges Saab-WASP (grant 41 1025), Academy of Finland (grant 342077), and the Jane and Aatos Erkko Foundation (grant 7031703) for their support. AS acknowledges the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) (312068/2025 5). AS would also like to thank Jorge Franco for his assistance with C++ routines. We also Likkoodldgee the computational resources provided under the Aalto Science-IT Project by Computer Science ITT. MJ would like to thank Sabína Gulčfková for her amazing help at Finland Summer 2024. MJ would also like to thank Cheng Chen, Yifan Guo, Aidan Hennessey. Yaojie Hu, Yongxi Lin, Yuhan Liu, Semir Mujevic, Jiayuan Sheng. Chenglu Wang, Anna Wei, Jinghui Yang. Jingxin Zhang, an anonymous friend, and more for their incredible support in the second half of 2024.
References
[1] Nikita Balabin, Daria Voronkova, Ilya Trofimov, Evgeny Burnaev, and Serguci Barannikov. Disentangle- ment lcarning via topology. Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41 International Conference on Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 2474-2504. PMLR, 21-27 Jul 2024.
[2] Rubén Ballester and Bastian Rieck. On the expressivity of persistent homology in graph learning. In Proceedings of the Third Learning on Graphs Conference, 2024.
[3] Mattia Bergomi, Massimo Ferri, and Antonella Tavaglione. Steady and ranging sets in graph persistence. Journal of Applied and Computational Topology, 7, 09 2022. doi: 00.1007//4444-002--000
[4] Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Speeformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreriie
[5] Deyu Bo, Xiao Wang, Yang Liu, Yuan Fang, Yawen Li, and Chuan Shi. A survey on spectral graph neural networks, 2023. URL https://arzii..rr wwwp://ggg///a//eeeeeeeee 2202 05631.
[6] Cristian Bodnar, Fabrizio Frasea, Nina Otter, Yuguang Wang. Pietro Liò, Guido Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2625-26400 Curran Associates, Inc., 2021. URL https: http///ppceeeen..../////// neurips. Paper. pdf.
ho/paper_filess
[7] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter. Guido F Montufar, Pietro Lió. and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1026-1037. PMLR, 18-24 Jul 2021. URL https: //pp://///ccceinggs..m mlr, www.sseesssve... vvt.//11///////// htt//bodaa2222 21a. .ttl..
[8] Cristian Bodnar, Francesco Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M. Bronstein. Neural sheaf diffuusio:: A topological perspective on heterophily and oversmoothing in GNNs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https:// //tpp///e///peeeee..../ met/forun?id-veeee BhhO..
[9] Kirill Brilliantov, Amauri H Souza, and Vikas Garg. Compositional PAC-bayes: Generalization of GNNs with persistence and beyond. In The Tiirtt-eighth Annual Conference on Neural Information Processing Systems, 2024. URL httpp: http::///////eeeeeeeeeeeeeeeeeee wet. wttee//oorrmmidd2......i.e.
[10] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34, 2017.
[11] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovie. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. 2021.
[12] Andries E. Brouwer and Willem H. Haemers. Spectra of Graphs. Universitext. Springer New York, 1 edition. 2012. ISBN 978- 1--11-144-1938-99 doi: 10.1007/978. 1-4614- 1939-6. 6. URL https://doi. org/ 10. 9007/9787 1- 4614- 1939-6.

---

[13] Mathieu Carriere, Frederic Chazal, Yuichi Ike. Theo Lacombe, Martin Royer, and Yuhei Umeda, Perslay: A neural network layer for persistence diagrams and new graph topologcaa signatures. In Silvia Chiappa and Roberto Calandra, editors. Proceedings of the Twenty Third International Conference on Artifcial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2786-27 2796. PMLR, 26- 28 Aug 2020, URL https: https::/proceeddiiieiee
proceedingss..... mlr. press/vvvvvveee 100// cet8//arrieii carriere2aa..... html.
[14] Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning on graphs. In M. Ranzato. A. Beygelzimer, Y. Dauphin, P.S. Liang. and J. Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 27029-27042. Curran Asso- ciates, Inc., 2021. URL https://proceedingg wewrrocceeinngnnnurrprpe. neurips wwwripp.cc/pppeeee.ppeeeeeeeepep httpperriileepppper//////////e/e e334fd9dac68f 157111577911188111222 www.paapr.........e..e..a.p
[15] Zhengdao Chen. Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria- Perri-FFooria Balcan, and Hsuan-Tiee -ien Lin, editors, NeurlPS, 2020.
[16] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1); 100111000-0011101111111111 Dee 2006. doi: 10.10077500454-006 006--076-5555
[17] David Cohen-Steiner, Herhert Fdelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the Twenty-Secome Annual Sympusium Computational Geometry, SCG '06, page 119-126, New York, NY. USA, 2006. Association for Computing Machinery. ISBN 1595933409. doi: 10. 10.11145/13788566 1137877. 1137877.
URL attpss://oi.... org/ 10. 1445/113755..
[18] K. Coolsaet, D'hondt, and Goedgebeur. House of graphs 2.0: database interesting graphs and more. Discrete Applied Mathematics, 325:97-107, 2023.
[19] Thomas Davies, Zhengchao Wan, and Ruben Sanchez-Garcia. The persistent laplacian for data science: evaluating higher-order persistent spectral representations of data. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org. 2023.
[20] Tamal Krishna Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.
[21] V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43): 48, 2023.
[22] Yam Eitan, Yoav Gelberg, Fabrizio Frasca Guy Bar-Shalom, Michael M. Bronstein, and Haggai Maron. Topological blindspots: Understanding and extending topological deep learning through the lens of expressivity. The Thirteenth International Conference on Learning Representations, 2025.
[23] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In Workshop track of the International Conference on Representation Learning (ICLR), 2019.
[24] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), 2020.
[25] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George F. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 1263-1272. JoLR. 2017.
[26] Mustafa Hajij. Kyle Istvan, and Ghada Zamzmi. Cell complex neural networks. In TDA & Beyond, 2020. URL. https: //tpe//eeeeeeeeee/////
[27] Mustafa Hajij. Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzzán-Sáénzz Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K. Dey, Soham Mukherjee, Shreyas N. Samaga, Neal Livesay, Robin Walters, Paul Rosen, and Michacl T. Schaub. Topological deep learning: Going beyond graph data, 2023. URL https: //taxv/////iv///// http/aaxivv.graeeee/e///// aa//a/b///222// 00606.
[28] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems (NeurlPS). 2017.
[29] Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl. Deep learning with topologi- cal signatures. In I. Guyon, U. Von Luxburg. S. Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL https: http:///poceennneeeeee neurips cttpscccpppppeeeeee 863e881bb4d22a77
0856881144222211d888882822222222 act5aa222220000206550002211 Paper.
12

---

[30] Christoph D. Hofer. Roland Kwitt, and Marc Nietharmer. Learning representations of persistence barcodes. Journal of Machine Learning Research, 20(126):1-45, 2019. URL http:// httsp://jmmrr org/ wttp://rr//pppp/////p/// pttpppppppe/////////// 18-358. 358.html.
[31] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference Learning Representations, 2022. URL cetpps:/openreviise
[32] Yinan Huang, William Lu, Joshua Robinson, Yu Yang. Muhan Zhang. Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graph neural networks. 2024.
[33] Johanna Immonen, Amauri Souza, and Vikas Garg. Going beyond persistent homology using persistent homology. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages (3150-6317) 173. Curran Associates, Inc., 2023.
[34] John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zine: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(7):1757-1768, 2012.
[35] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
[36] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://opperrriieeeeee http://///ppppeeeesssseeeerrrrr? id=SJU4ayYgl.
net/forum?
[37] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Letourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[38] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanic Jegelka. Sign and basis invariant networks for spectral graph representation learning. In International Conference on Learming Reprexentations (ICLR), 2023.
[39] David Loiseaux, Luis Scoccola. Mathieu Carrière, Magnus B. Botnan, and Steve Oudot. Stable vector- ization of multiparameter persistent homology using signed barcodes as measures. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[40] H. Maron, H. Ben-Hamu, H. Serviansky, and Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[41] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence (AAAI), 2019.
[42] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: collection of benchmark datasets for learning with graphs. In ICMI. 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[43] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: the story so far. J. Mach. Learn. Res., 24(1), mar 2024. ISSN 1532-4435.
[44] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent- laplacia. URL htttts///gtthbbb com/
[45] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent laplacians: Properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4(2)8858-884, June 2022. ISSN 2577-0187. doi: 133/21m 1435471. URL http:// doi org/10 10. 1137/21M143547.
[46] Theodore Papamarkou, Tolga Birdal, Michael M. Bronstein, Gunnar E. Carlsson, Justin Curry, Yue Gao, Mustafa Hajjj. Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, Vasileios Maroulas, Nina Miolane, Farzana Nasrin, Karthikeyan Natesan Ramamurthy, Bastian Rieck, Simone Scardapane, Michael T Schaub, Petar Velickovic, Bei Wang. Yusu Wang, Guowei Wei, and Ghada Zamzmi. Position: Topological deep learning the new frontier for relational leamnig. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages
PMLR, 21-27 Jul 2024. URL https: / http::////cceednee/ee mlr, prrsss v235 2235/papamarko225 html.
13

---

[47] Mathilde Papillon, Sophia Sanborn, Mustafa Hajij, and Nina Miolane. Architectures of topological deep learning: A survey of message-pannt passing topologica neural networks, 2024. URL https://arzzi org/ Abs/2304.10031.
[48] Ladislav Rampákek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general. powerful, scalable graph transformer. In Conference on Neural Information Processing Systems, 2022.
[49] Bastian Rieck. Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lhnman procedure for graph classification. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th Internationaa Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 5448-543 5458, PMLR, 09-15 Jun 2019. URL https: / httptp::/pprcceednnnee ..r. sal..press/vvi http://////eeeee...// html.
[50] A. Samal, R. P. Sreejith, J. Gu. S. Liu, E. Saucan, and J. Jost. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific Reports, 8(1):8650, 2018.
[51] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20, 2009.
[52] Primoz Skraba and Katharine Tumner. Notes on an elementary proof for the stability of persistence diagrams, 2021.
[53] Primoz Skraba and Katharine Turner. Wasserstein stability for persistence diagrams, 2025, URL https: // //arxiv. .rgg ats////b.0......//// 20002.6066.........111/11/110406
[54] Ilya Trofimow, Daniil Cherniavskii, Eduard Tulchinskii, Nikita Balabin, Evgeny Burnaev, and Serguei Barannikov. Learning Topology-Preserving Data Representations. In ICLR 2023 International Conference on Learning Representations, volume 2023, Kigali, Rwanda, May 2023. URL hhtph::///haaa http://aaaa..aeeccceeeee science/
hal 040-04003214.
[55] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. International Conference Learning Representations (ICLR). 2018.
[56] Yogesh Verma, Amauri H. Souza, and Vikas Garg. Topological neural networks go persistent, equivariant, and continuous. In Proceedings of the 41st International Conference on Machine Learning, ICML'24.
JMLR.org, 2024.
[57] Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations (ICLR), 2023.
[58] Minghua Wang, Yan HU, Ziyun Huang, Di Wang, and Jinhui Xu. Persistent local homology in graph learning. Transactions on Machine Learning Research, 2024.
[59] Rui Wang, Due Duy Nguyen, and Guo-Wei Wei Wei. Persistent spectral graph. International Journal for Numerical Methods in Biomedical Engineering, 36(9), Aug 2020. doi: 10. 10.1002/cnm.3376
[60] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors. Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 23341-23362. PMLR, 17-23 Jul 2022. URL htR..tttt://// htttpa:/ppooceedingg mlr. press/vi62. vitass//12//aag22an html.
[61] Yanbo Wang and Muhan Zhang. An empirical study of realized GNN expressiveness. In International Conference on Machine Learning (ICML) 2024.
[62] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
[63] Zuoyu Yan. Tengfei Ma. Liangeai Gao, Zhi Tang, Yusu Wang, and Chao Chen. Neural approximation of graph topological features. In Alice H. Oh, Alckh Agarwal, Daniclle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httpp:///penreeeeee..t net/ forum? ferummid-guen wiriiddddjrrrerrrrrr
[64] Xue Ye, Fang Sun, and Shiming Xiang. Treph: A plug-in topological layer for graph neural networks. Entropy. 25, 2023. URL https::/ppp...mmmticcc..... www.nticscoooar.r.......... Crgg/CrrpssDD:... :Dte//uusuSID22562550000 256852600.
14

---

[65] M. Zaheer. S. Kottur, S. Ravanbakhsh, B. Poczos, R. Salakhuidinov, and A. Smola. Deep sets, In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[66] Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification. In Proceedings of the 33rd International Conference Neural Information Processing Systems, Red Hook, NY. USA, 2019. Curran Associates
[67] Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2896 2906. PMLR, 26 28 Aug 2020, URL https: / http//pooeeiige mlr, press/ vv10s////v////////// V108/2haa20dd /hw.o0d..dd.. html.
15

---

A Proofs
A.1
Proofs for Section
In this section, we will prove Theorem 3.2 and Theorem 3.3, and we discuss the proof of Theorem 3.4 separately Appendix B.
Proof of Theorem 3.2. Let us check that Re is graph isomorphism invariant. We will first show this for SpectRe( f) Here we follow the suggestions laid out in Theorem of Immonen et al. [33] and decompose it in two steps.
1. From Theorem 4 of Immonen et al. [33], we know that the original RePHINE with (b, d, a, is an isomorphism invariant.
2. We also want to show that the map G - {o(C(re d(()))) (EV) is an isomorphism invariant. Here, produces the spectrum the connected component v is in at its time d(v). Since P itself does not depend on choice, it suffices for us show the following map is an isomorphism invariant:
G+ {C(e, d(e)))
where Civ, d) the component is in at time d. The ambiguity comes in, depending on our choice, a vertex may very well die at different times.
Now from the proof of Theorem of Immonen et al. [33], we already know that the multi- set of death times is isomorphism invariant. Now vertex death can only occur during a merging of old connected components .i...., Tn (with representatives U1, ... Un) to a component C. Now under the RePHINE scheme, there which vertex. However, we see that any choice of the vertex does not affect the connected component that will be produced after merging. Thus, we will always be adding a constant n - 1 copies of C' to the function we are producing.
specific procedure to choose
For the real holes, know from the proof of Theorem 4 of Immonen et al. [33] that, it does not matter how each of the remaining vertices is matched to the real holes, since the rest of the vertices for the real holes will not be affected. Finally, the description above also shows that we can concatenate the pair (b, d, a, 7) with (p) in a consistent way.
associated in invariant way. Hence, the production of graph Laplacians
3. Hence, we that Spect e f) is isomorphism invariant.
Now for SpectRe( f) the argument follows similarly as above. suffices for us to check that the list {C(e, b(e)))()eeeeeee)) eCcycle is consistent. We observe that the birth of a cycle can only happen when an edge occurs that goes from a connected component C' back to itself. The only possible ambiguity is that, at the birth time, multiple edges are spawned at the same time, and an edge may or may not create a cycle based on the order added to the graph. However, regardless the order, the resulting connected component that the edge belongs in will be the same. Thus, the list (C(e, eecyyle will be consistent.
Proof of Theorem 3.3. Clearly SpectRe has least the same expressivity to either RePHINE LS. This is because RePHINE is the first four coordinates of SpectRe, and LS is the first, second, and fifth coordinates of SpectRe. Thus, suffices for to show that RePHINE and LS incomparable to each other.
Consider the graphs G' and H in Figure 3(a). From the remarks below Theorem of Immonen et al. [33], we know that RePHINE cannot differentiate G and H. However, the data about the real holes of the respective Se diagrams of G and H will be different. This is because the eigenvalues of the graph Laplacian Ao) are (0, 1, 1, 1,4) and the eigenvalues of the graph Laplacian An (H) are {0, 2. 22, 2 + 22).
the other hand, consider the graphs G and H in Figure 3(b). We note that all edges in and H would be labeled the color "red-blue". Thus, the p-component of the LS diagrams for G and
16

---

H would be the same, being the non-zero eigenvalues of the star graph on 4 vertices. The set of death-time times would also be the same, being IS would not be able to differentiate G and H. However, RePHINE, would if we choose fo such that fo (red) * (blue)) just based on comparing the a-values.
fo (red-blue), fo (red-blue), oo). Thus,
A.2 Proofs for Section
For ease of notation, we will omit the parameter G the RePHINE diagram in this section since we will only be discussing functions on the same graph. We will first verify that our definition of a metric d in Definition 4.2 is actually a metric. To do this, we first remind the reader that, under Notation 4.1, the definition of d can be elaborated as the following definition.
Definition A.1. Let RePHINE(G..] RePHINE diagrams for G respectively. We define the bottleneck distance as d (RePHINE((, f), Re,RReHHHEEG,, g)) = di (RePHINE(G; (HPPPIN + d (RePHINE(G, f)', (e)))
and RePHINE(G.g) be the two associated
For the 0-th dimensional component, d defined as, d (RoPHINE(G, RoPHINE(G, = inf EEbijections PERGPHLNE(G..
max d(p, π (p)),
where d is defined d( do, ag. 7o). (b). d1. m1) = max bu bd dol) + |01 aul + I/ - -o and ı ranges over all bijections RePHINE(G, f) + RePHINE g) For the 1-st dimensional component, dn is the usual bottleneck distance on 1-dimensional persistence pairs.
Proposition A.2. d' and Specf are metrics.
Proof. We will first check this for dg. Since the usual bottleneck distance is a metric, it suffices for us to check that d is metric.
Non-degeneracy: Clearly the function is non-negative, and choosing マ to be the identity bi- jection shows that d (RcPHINE(()) RePHINE(,))) O. For any pairs RePHINE(,)) * RePHINE(g)), the term maxpERPPHINELFY d(p, (p)) will be greater than 0 for any choice of bijection π. Since there are only finitely many possible bijections the infimum R..0 B (RePHINE(J)), RePHINE(g))) will be greater than 0.
Symmetry: Any bijection क RePHINE(f)) - RePHINE(()) corresponds exactly to a bijection x RePHINEE()) + RePHINE(S)) Hence, the definition of RR.0 is symmetric.
Let RePHINE(/)) RePHINE(g)), RePHINE(())) be the vertex compo- nents of RePHINE diagrams G. Suppose oi RePHINE(()) - RePHINE(())) is bijection that achieves the infimum labeled in the definition of d//00 In other words,
Triangle Inequality:
RR.0 (RePHINE(J)), RePHINE(4)") = max d(p, (1).o(())) (p)).
Suppose TI, T2 are bijections from RePHINE(()) PEROPHINELO) RePHINE(h) respectively. We then have that, max PERePHINE(())
RePHINE())) and RePHINE(g) +
d(p) <
max PERePHINE.
d(p, m (p)) d(ri (v), (2(T(P)))
Triangle Inequality for d
d(p,T((P)) max PEROPHINEL
max
d(g. (2))).
P
For the sake of paragraph space, we write A RR.0 (RePPHIE)))(()) RePHINE(h))), Taking infimum over all possible 71 and over 72 gives us that
A= d (RePHINE(F)) RRePHINE(A)))
< inf max
d(p, (1) + max d(g, T2(9)) ( (()TT(p)) + inf
71.12 PERePHINB(/1)
inf max
Ebjjecttion Te F d(g, T2(9))
max
Ebjjectioo PER
< d (RoPHINE(J)) RePHINE(g))) + (RoPHINE)))))) RePHINE(h))).
17

---

This shows that d satisfies the triangle inequality.
For SpeeR since we showed d from Definition 4.2 is a metric, it suffices for us to check in this proposition that dSpec is a metric. To reiterate the definition of dSpec, given a list L of non-zero eigenvalues with length n, we define an embedding ((L) E é (N) where @(L) where the first n-elements in the sequence are L sorted in ascending order and the rest are zeroes. This embedding
clearly injective on the lists of non-zero eigenvalues. For two lists po: PL. we define
d (po, P1) = 110(p)) - ((p1)lla-
The fact that dSeec is a metric now follows from the fact that (NN) is a metric space under its El distancce and & is injective.
To prove Theorem 4.4, we first define a technical construction as follows.
Definition A.3. Given a graph G and functions (fr. on X. This induces functions (F., Fe) as defined in Definition 2.1. From here, we construct a pairing between RePHINE(f) and (v, e) E V(G) x {0} U E(G) as follows.
1. For every almost hole (0,d) that occurs in the edge filtration by Fe, this corresponds to the merging of two connected components represented by vertices i and vj-
2. We assign to (0, d) the vertex that has greater value under a. If there is a tie, we assign the vertex that has the lower value under y. If there is further tie, we will be flexible in how we assign them in the proof of the stability of the RePHINE diagram.
3. The occurrence of an almost hole (0, d) is caused by an edge e whose value under fe is d that merges two connected components. We assign this edge to (0, d). If there are multiple such edges, we will be flexible in how we assign them in the proof of the stability of the RePHINE diagram.
4. For the real holes, we assign them with the vertices left. The edge takes uninformative value (i.c. 0).
Note that for any vertex that dies finite time d, its associated edge e (U1, satisfies f=(c(v1), = d(v).
We will now state and prove two propositions that will directly imply Theorem 4.4. Our proof is inspired by the methods presented in Skraba and Turner [52].
Remark A.4. To expand on the original statement above: our proof relies on the technical construction in Definition A.3, which inspired by vertex-edge pairing in Skraba and Turner [52] (which are called pivots) and proceeds with linear interpolation technique as in Skraba and Turner [52]. Vertex-edgs pairing has also appeared in Skraba and Turner [53] and Sohen-Steiner et al. [17] for stability results. While we focused on stability analysis here, the concept of vertex-edge pair is standard in TDA; e.g.. it has appeared in numerous algorithmic designs in Dey and Wang [20].
Our definition of pairing in Definition A.3 is different from the pivots in Skraba and Turner [52]. A pairing here is pivot in Skraba and Turner [52] with respect to fe. but not every pivot with respect to Se is a pairing. This is because there are some obstructions to conclude Theorem 4.4 directly from bottleneck stability, such as [16, 52]: (1) RePHINE has 4 parameters, while the stability results with traditional PH deals with only 2 parameters. (2) Our analysis here has to pay attention to pair of filtrations (fu. fe) compared to another pair (gu. ge). as opposed to just comparing between individual filtration functions. (3) For the pair (fos ). ). it is unclear how to interpret the y parameter in terms of a birth/death time of a simplex in fe). For an arbitrary vertex e E G. its (v) need not be its birth time or its death time in fe/fe. It is possible to view y as the birth-time arising in another filtration f. but we did not pursue this approach as our metrics are defined with respect to the pair fe).
Extending the stability analysis from PH to RePHINE non-trivial. In particular, we must resort to a RePHINE version of the vertex-edge pairing (Definition A.3) that respects both filtrations (eo, For our purpose, we require pairing that respects both vertex and edge filtrations. This can seen in Proposition A.5 below, whose proof uses an assignment with respect to fe to analyze changes to
18

---

fo. The subtlety also occurs in Proposition A.7 that analyzes changes in fe. since the proof entails careful analysis on how the 7yparameter (which is not present in traditional PH) behaves.
Proposition A.5. Suppose fe 9e h for some edge coloring function h, then
d (RoPHINE( h)" RePHINE(g,, h))) - [1 gulloo.
Proof. Let (x) = (1) Also H; G R be the induced function of hi on G, in the sense of Definition 2.1. We can divide [0, 1] into finite intervals [to, t1l, [+1. tg],..., [t tn+1l. where to 0, tz1 t, t < ... txt1, such that for all t E [t,, t441] and all simplicies 2,y G, either
(x) H S 0r 2 0 (t)-
To be clear the wording, this means that cannot find s [t,, 1441 such that Hz(x) > HC(v)
but Hy (xr) < Hg (v).
For all $1, $2 E [t,, t.+1]. we claim that we can use Definition A.3 to produce the same list of pairs (v. e) (with some flexible adjustments at endpoints if needed).
Since fe 9c. the list of death times and order of edges that appear do not change, what could change is which vertex to kill off at the time stamp. Let us now order the finite death times (i.e. those corresponding almost holes), accounting for multiplicity, dj I d2 S ... S dn < co. Now we observe that
1. At di, RePHINE(Hă h) and RePHINE(h,", h) will be merging the same two connected components with vertex representatives and w. For the RePHINE diagram at 81 (resp. 82), choose which vertex to kill off based on which vertex has higher value under H (resp. He?). By (t), we will be killing off the same vertex. there happens to be a tie of a values, will still kill off the same vertex in the comparison of y values since there is a tie of y values, we make the flexible choice to kill off the same vertex.
9e. Finally, if
Since fo = Dc. the edge associated to this vertex can be chosen to be the same. Hence, RePHINE((C) h) and RePHINE(( h) will produce the same pair (v, e) at time d1.
2. Suppose that up to the i-th death, both RePHINE diagrams are producing the same pairs and merging the same components. For the + 1-death, the RePHINE diagrams at both and $2 will be merging the same two components v' and w'. The same argument the case for dj shows that they will produce the same pair of vertex and edge.
3. After we go through all finite death times, both RePHINE diagrams will have the same list of vertices that are not killed off, which are then matched real holes.
This proves the claim above. From triangle inequality, we R.0 (RePHINE((s,, h)), RePHINE(g.. h))) is bounded by the term
know that
(RePHINE(H)) h) "A
For each summand on the right, we assign bijection from RePHINE(h;; h) to RePHINE(K .h) as follows - using our previous claim, we send (0,d,a,7) e RePHLNE(Mh,, 4/)" to the pair in RePHINE(M ,h)" that correspond to the same (v,e). For the sake of paragraph space, write A,
R.00 (RePHINE(K;; h)), RePHINE(S Aie h))) and
19

---

see that
A. d (RePHINE(K) h),, R ,1))
max (0,e)
de (v) (b) | (at,_(() an, (v) + he (1) - -c, [e]
max 0 latit1 (v) on, (v)) +0 (0,c)
Since Se ge.
max [14, (v) (xr((()) (v)
max !h 1n (c(w)) - -
max [1 (1-- -1-) (tg
max - (4
(t+1 (1 (()go(((w))
max(14-1 (4) -
$ (1++1 t.)l -elloo
Hence, we have that
R.. (RePHINNE(S,,)) (
h))) S
Σ A
t=
Σ (ts+1 - 1:)lffo 80l120
fl gulloc.
Remark A.6. the proof of the previous proposition, we claimed that we can assign the same vertex-edge pair to each death time for both filtration at f; and 44+1. This may seem contradictory at first, as this seems to suggest that, by connecting the endpoints of the interval, RePHINE would assign the same vertices on G as real holes regardless of the choice of functions. However, in our proof, the choice vertex-edge assignment on t; E [t., f++1) 1 need not be the same as the choice of vertex-edge assignment on t, b.). This is what meant by "flexibility" in Definition A.3, the key point is that both choices will give the same RePHINE diagram.
Proposition A.7. Suppose J = 9v h for some vertex coloring function h, then d RR00 (RePHINE(( fa) RePHINE(h, 9o))) < 211Se gelloo
Proof. Let (1 ()fe
+ (x) X X X Rso be as in the previous proof. Also let H G R20 denote induced function on in the sense of Definition 2.1. We can divide [0, 1] into finite intervals (lo, 41), [4, (2), Mn, An+ 1]. where 4o = 0, la+1 = 1,40 < l1 < ln+1.
such that for all t [te, t441 and all edges x, y E G. either
(x(x) (v) < or 2 (t).
For all $1, $2 E [t,, 1. we claim that we can use Definition A.3 to produce the same list of pairs (v, e) (with some flexible adjustments at endpoints if needed).
The death times for the RePHINE diagrams 81 and 82 may be different. Let write dit < < d (with multiplicity) to indicate all the finite death times for $1, and similarly we write di² < ... S d for s2 (with reordering allowed for deaths that occur the same time). We claim that the corresponding (v, e) produced at df² and d=a can be chosen to be the same.
1. For each death time that occurs, we are free choose any of the merging of two components that occurred at that time to be assigned to that death time.
2. At d the death occurs between the merging of two vertices and by an edge such that H (e) = d If (e) = dis, then we can choose the first death occur with the same edge between and
20

---

Otherwise, suppose (e) > di. There exists an edge e' such that (²² = d (e) > (e"( By (f). this means that (e) H²"(e); (e'), which implies that (e' = dir We instead choose the first death in di to occur with the edge e between its adjacent vertices.
In either case, we see that at the first death time, we can choose an assignment such that the RePHINE diagrams at si and 52 are merging the same two connected components a, b by the same edge. Now we will show that they will kill off the same vertex. Since fe Iv. the first comparison will always give the same result. If there is a tie, then we are comparing fe and ge. Suppose for contradiction, that without loss, has lower y value at $1 and b has lower y value s2. This means that there exists an edge ea adjacent to a such that
H (ea) < H (e), for all adjacent to b.
Now, since b has lower y value at 82, this means that there exists an edge es adjacent to such that
(es) < H (e), for all e adjacent to a. In particular, this means that (es) < H (ea) and (e) > (ea)), which violates
(t). Hence, we will have consistent vertex kill off. Finally, if there tie, then flexibly choose the same vertex to kill off. Since we are comparing the same edge, there is canonical edge associated too.
Thus, we have shown that d' and d² can be chosen to give the same vertex edge pair.
3. Inductively, suppose that up to the i-th death, both RePHINE diagrams producing the same pairs and merging the same components.
For the i + 1-th death, 1 occurs between the merging of two connected components C1 and C2 by an edge such that H (e) = d- Now if H = dii then by our inductive hypothesis we can choose both filtration that they would be merging the same connected components.
Now suppose 11 (e) + di By the inductive hypothesis, it cannot be lower, H d In this case, we look at d itself, which also occurs with an edge e' that merges connected components C₁ and Cz2. Hence, we have that
(*) > (e) dit
By (t), this means that
(e) (c)
By our inductive hypothesis, this edge e' cannot have occurred in prior deaths, hence have that (e" = d and the same arguments as the base case follow through.
In either case, we see that at the i + 1-th death time, we can choose assignment such that the RePHINE diagrams at 31 and $2 are merging the same two connected components a, by the same edge. Similar to discussion in the base case, the vertex-edge pair produced would be consistent.
4.
After we go through all finite death times, both RePHINE diagrams will have the same list of vertices that are not killed off, which are then matched real holes.
This proves the claim above. Now, from triangle inequality, again have that RRD0 (RePHINE(h, fe) RePHINE(h,, 9o) is bounded by the sum
R.0 B (RePHINE((, h()) RePHINE((,, (4, (211))).
For each summand on the right, we assign bijection with the exact same strategy as the proof of the previous proposition. For the sake of paragraph space, write A,
21

---

R.D (RePHINE(H, ) RePHINE((h, he*+))) and compute that
B
A, d (RePHINE(H,,)) RR
I max d (v) - d, (v)] + |a (1) - ac, + M1a4 (1)+(()) - (1, (w) (0,e)
max de-i (v) - (v]] + + M (v) - [v) (U)e)
Since fo = 9u
max H (c) H (e)l + (v) - (,) (0,e)
< (1++1 - 1:)l1se - - + max Ie (v) Te. (v]l-
We claim that M1e41 (v) - ne, (v) S || h bl Indeed, without loss let us say Ytu (v) 2 -e,
Let e be the edge adjacent to v that has minimum value under H then this means that
( (v) -/. (v)
Mhis (v) 7e, (v)
Mots (v) H:: (e,)
Hout (ei) H. (e:)
Since Mes (v) is minimum
|e 11. 1100
11bt 1221100
< (ti+1 tilllfe -9elloo
Thus, we have that
A, dR.0 (RePHINE((h, RePHINEEH.HNNNN S 2(4+1 1014111100 - 4))lJ. - -gello.
Hence, we have that
B (RePHINE(b,, fe) Re..HNNEE,h, ge) s A
<
2(11+1 - Lilllse gel
k=U
211fe 9ells0.
Now we finally give proof of Theorem 4.4.
Proof of Theorem 4.4. On the 1-dimensional components of the RePHINE diagram, we have the usual bottleneck distance. Cohen-Steiner et al. [16] gives standard bound this term by d (RePHINE(()) RePHINE(g))) < llfe - loo The theorem then follows from the trian- gle inequality, the inequality in the previous sentence, and the previous two propositions.
Now show that SpectRe is locally stable under the metric Spec R
Proof of Theorem 4.5. Let us first prove the case with constraints on both fu and fe. We will again split this into two cases where fe = 9e and fo = go respectively.
Suppose again that fo = 9u = h, let us try to follow the proof of Proposition A.7 to give an idea on why using this method falls apart. let (x(x) (1 f)fe(2)) tg)( and H G - R be the induced function of hi on G, in the sense of Definition 2.1. We can again divide [o, 1] into finite
intervals (L,, da), [1,, f.), [t,: In+1], where = 4,+1 1,40 < l < lnt1, such that for all t E [t,, 4+41 and all simplicies x. J E G, either
(x (v) < 0 or 2 (t).
For all 82 E [lo, 41. we can again use Definition A.3 to produce the same list of pairs (v, e) (vertex to edge identification). Previously, by choosing 81 = la = 0 and 82 = (1, we were able to obtain reasonable bound on the bottleneck distance for RePHINE in terms of the _ norms of h and hā.
22

---

We could do this for RePHINE because the b, d, a, parameters of RePHINE are all not sensitive to the loss of injectivity. However, the p-parameter in SpectRe is sensitive to the loss of injectivity, as seen in Example 4.6. Moreover, the way we constructed the division of [0, 1] indicates that we are forced to cross some time stamps in [0, where ht no-longer injective.
However, we observe that clearly we could get the desired bound
dSee R.0 (Spect fa)", Sh gx)²) S 211fe gelloc,
provided that the following more restrictive condition holds hg is injective for all E [0. 1j. The bounds on the b, d, ax parameters evidently follows from the same proof of Proposition A.5. For the bound of p. we observe that in the production of the vertex-edge pairs (v, e) in the proof of Proposition A.5, wc can choose the order of vertex deaths to be the same for both (h. fe) = (h, h?)) and (h, 9e) = (h, h:y). Furthermore, the condition that A is injective for all t E [0, 1] means that the ordering of colors in X given by fe and ge respectively are exactly the same. Furthermore, both orderings are strict they are injective. Thus, the component that the vertices die in at each time also the same. What this effectively means is that, P (v) = Py(u) for all v E V (after choosing the (v. e) identification). Thus, we would obtain the same bound.
Suppose Je = ge = ht then we note that an analogous argument (although not required, see the proof of Theorem 4.7 later), would work to show the bound
Jo) if we impose the condition that by, is injective for all & E [0, 1] in the context of the proof for Proposition A.5.
Spece R.0 (Spect Reee,, fo) SpectRe(h,, 9o S [1/ gulloo:
We still need to check what happens for dppc R.1 which is no longer the usual bottleneck distance. If fe Jr h and N1 is injective for all t E [0, 1]. then the 1st dimensional component of SpectRe(fe: h) and SpectRe(ge: h) would quite literally be identical. If Jv = Ie h, and hyg is injective for all E 1]. then a similar argument in Proposition A.7 would show that
Spee R, (SpectRe(h, fe)", SpectRe((,, ge)") llfe ge lelloo.
The idea is that the only obstruction to this bound was the presence of the p-parameter, which we could always choose the presence of cycles to have the same strict order with the same graph components showing up.
Thus, we have proven the following result- - let f f= (fe, fe) and g = (ge, ge), suppose hy (1 - ff) (z) and h²())) (1 f)) + (x) are injective for all t [0, 1], then
=
d SSpee (SpectRe(f), SpectRe(g)) 3|1fe lel + llfe golloc-
remains for us to show that the conditions on h², and hy are locally satisfied. However, we note that clearly Conf,., (RR and Conf, (R>o) are both locally convex, which is the same as imposing the hypothesis to obtain this bound. Thus, we have proven that SpectRe is locally stable in (for fe).
Let us now argue why the local stability condition is not required for fa- Indeed, this because the parameter in SpectRe is completely independent of the vertex-level filtration. No matter which vertex one decides to kill off, the connected component the vertex dies in is always the same if the edge filtration function does not change (and the same goes for which edge is born). Thus, if Se ge. then one can correctly assign the matching of tuples so that the p-components cancel out identically during similar linear interpolation proof as in Proposition A.5. This concludes the proof.
O
Now we will give proof of Theorem 4.7, which gives an upper bound on how unstable SpectRe can be relative to the complexity of the graph.
Proof of Theorem 4.7. Let D denote the distance Spec R.0 (SpectRe(G, fo, fe), SpectRe(G, ge, ge)). By the explanation in the proof of Theorem 3.4, we know the SpectRe globally stable in the vertex filtration. Thus, we have that
D < d Spee R,0
(SpectRe(G, f SpectRe fc)
+ Spec R.0 (SpectRe gr. fe)", Spect
B
< [15 go 0ol + /Spee R.0 (eeectReeGG (G,g., gm, (ae Spect gos ge))))
23

---

This means that we have reduced to the case that they have the same vertex vertex-filtratie filtration function. Now observe that the SpectRe diagram for both gv fa) and gn. are the same outside of the vertex deaths at time di 4i+1 for Je and time di+1 for ye, by how Je is constructed. Thus, we can choose suitable bijection и to cancel out the identical pairs outside this critical range. In the critical range, the vertex deaths at time 0,+1 for fe are a subset of vertex deaths at time 0,+1 for Je- such that they have the same a and parameters, so we extend the bijection π to match them too. Finally, we match the vertex deaths at time for fe to the remaining ones left in d++1 for ge. Write Spec R,0 (SpectRe(G, go: fa)", Spect (,, 9u: (o) this bijection will give us the bound Spec
D' d
D' S (ai+1 a.) + life lel +
max (H),
d-parameter
"-parameter
e parameler
S 2(a4+1 a;)
max Ha)YY
Spec
((
Here, is the set indicated in the description of Theorem 4.7, that is - Y is the collection of pairs (H1, H2) where H1 is the connected graph that a vertex v died at time as for fe is contained in, H2 is the connected graph the same vertex v died at time 0++1 for Je in, and H1 H2. The reason why Y occurs here comes from a direct examination of the graphs H1 and H2 that the p p-parameter considers in the bijection
By the interlacing theorem (Proposition 3.2.1 of Brouwer and Haemers [12]), &Spe (p(H)) (22)) can be written as tr( tr()o(H2) tr(Ao(Hi)) where tr is the matrix trace and -o(-) is the graph Laplacian. The trace of Laplacian is also the sum of degrees of the graph, which is also twice the number edges. Thus, we have that
D' 2(a+1 a.) +
max (Hi.
|E(H2) -E(HH)
This concludes the proof for the O-dimensional part.
For the I-dimensional part, we can perform a similar bijection in this case. In this case, the a and ? parameters are automatically zero, so the terms they contribute (l gelloo for a and (a++1 a;) for 7) also vanish. Following similar proof as before yields the bound
(at+1 - -a; +2)+2 max
-B(())))
(HI.
B Expressivity of Spectral Information
In this section, we will give a self-contained proof of Proposition 3.4. We will first introduce the relevant concepts. Suppose K is an n-dimensional finite simplicial complex. There is standard simplicial chain complex of the form
0 Ba+1, (x)
Ci(K) 0h Co(K)
0
Here each Cs(K) has formal basis being the finite set of i-simplicies in K, hence there is way well-defined notion of an adjoint (which is the transpose) a." for each 0, The i-th combinatorial Laplacian of K is defined
A( of o 0.+1 0
A; is a linear operator on C(()). Note that when K is graph and 0, Ao(K) is exactly the graph Laplacian of K. It is general fact that the dimension of ker (K(K) is the same as the i-th Betti number of K. Hence, the multiplicity the zero eigenvalues of (K(K)) corresponds to the i-th Betti number of K. However, the Betti numbers of K (harmonic information) do not give any information on the non-zen eigenvalues of (K) (which we can think as the non-harmonic information). This is the data that would like keep track of.
For filtration of a simplicial complex K by = Ko S K1 .... S Km = K, Wang et [59] proposed persistent version of combinatorial Laplacians as follows.
24

---

Definition B.I. Let C (g(K)) denote the 9-th simplicial chain group of K 0j (Ke))) + (o-1(Ki) be the boundary map on the simplicial subcomplex K,. For p 0, we C to denote the subset of C2pP whose boundary is in C--1 (in other words Cy+ = (a Cj+P 10tt((a) C2-1)).
We define the operator 0 C C--1 as the restriction of 0 to Cstp, From here, we define the y-persistent g-combinatorial Laplacian (K) (K,) (K,)
A (K) = 8 0 + 00
Note that the multiplicity of the zero eigenvalues in A # (K) coincides with the p-persistent q-th Betti number.
Now will focus the special case where K G is graph. In this case, we only need to look at the p-persistent 1-combinatorial Laplacians and the p-persistent 0-combinatorial Laplacians. Our goal is to augment the RePHINE diagram, cigenvalues of the p-persistent g-combinatorial Laplacians in our augmentation. In this section, we will show that augmentation of the ordinary graph Laplacian.
intuitively would like to include all the non-zero
more expressive than simply focusing the spectral information
Lemma B.2. On graph G. the multi-set of non-zero eigenvalues of (1(G) the same as the non-zero eigenvalues of (o(G).
Proof. For ease of notation, we omit the parameter G in the combinatorial Laplacian. Since G has dimension 1, On and 8g are both O. Hence, the two combinatorial Laplacians may be written as
Do = 0 of and A = 0 o 0j
Let be an eigenvector of Ao corresponding to non-zero eigenvalue X, then A. v) = o7 (0, o (x)) = or (Ao(o)) = of (Ae) = X(0
Hence, of e is an eigenvector of A with eigenvalue A.
We also need to check that if v, w linearly independent eigenvectors of An with the same eigenvalue X, then of u and of we are linearly independent. Suppose for contradiction this not the case, then there exist coefficients a, E IR (not all zero) such that
= 0= v + bot w = of (ac + bw).
This means that av + bw kcr( C (er(A)) is non-zero eigenvector corresponding to the eigenvalue O. However, we also know that av +
a non-zero eigenvector of An corresponding to the eigenvalue X. Thus, it has to be the case that av + bw 0, so we have contradiction.
Hence, the non-zero cigenvalues of Ao form a sub-multiset of that of A₁. The other direction may also be proven using linear algebra. Alternatively, however, we observe that by the equality of the Euler characteristic,
V(G)) |E( = GG) = dim (Ao) - dim ker (1).
Rearranging the terms gives us
V(G) dim ker(Ao) = |E(G] dim ker (x))
This means that A and Ao have the same number of non-zero eigenvalues, so their respective multi-sets of non-zero eigenvalues equal.
Let G be graph and
-= Go G C C.
be a sequence of subgraphs of G. Recall that A A++P(G) denotes the p-persistent g-combinatorial Laplacian operator. We will first examine what happens when q = 1.
Lemma B.3. The 1-combinatorial p-persistence Laplacian A(+ equal to A A Moreover, the non-zero eigenvalues of y-persistence A t+P (G) are the same as the non-zero eigenval- ues of A accounting for multiplicity.
25

---

Proof. Recall that (G) is defined as
(G) = 0 0 (o)))) + 00
When I, we know that (G) is the zero matrix since G is graph, and hence
A (G) = (8))
This is independent of p and just (G) Finally, from Lemma B.2, we have that (j(G) and (G) have the same multi-set of non-zero eigenvalues.
Remark B.4. This is reflective of the definition of the p-persistent k-th homology group of G³, which is given by
HR(G") = ker O& In this case, when k 1, I 02(G(+P) is the map, so Hf(G) ker (G') H (G'). Hence, the p-persistent 1st homology groups of G' stays constant as varies. This is also reflective of the fact that inclusion of subgraph G G' induces injective homomorphism i. : (G) + (G").
(G ker((;
The focus of persistent spectral theory should then be on the data given by the graph Laplacians, so makes sense for us to interpret what exactly A (G) is.
Lemma B.S. Suppose C++P {a E Ci+P pftP(a)) in Getp whose vertices are in Gt. the p-persistent O-combinatorial Laplacian operator of G
(a) C.i equal the span of all I-simplicies
(G) (8ttro
the graph Laplacian of the subgraph of Gi+q with all the vertices in Gt-
Proof. The map 07th C Cj is the restriction map + onto C++p, Let G' denote the subgraph of Gr+g generated by vertices in G. Note that by our assumption C++P C (G'). this case, there are two vertical isomorphisms, by quite literally the identity map, such that the following diagram commutes,
(i))
a Co(
Cttp
C.
Hence, the graph Laplacian of G' is the same as the Laplacian A ttp
Corollary B.6. Lemma B.3 asserts that the non-zero eigenvalues of (G) are the same as the non-zero eigenvalues of (G) (o(G.). In the special case where focus filtrations of G given by (Fu, Fe) outlined in Section we have that 1 is the same Do Lo(Gr+p) in the edge filtration given by Fe.
Proof. We first observe that edge filtrations satisfy the hypothesis of Lemma B.5 since all vertices are spawned at time 0 and hence C = C. To prove Corollary B.6, observe Lemma B.5 implies that A AG) is the graph Laplacian of the subgraph of Gt+p generated by the vertices in Gr. However, all vertices are spawned at the start, so they have the same vertex set and the subgraph is just the entire graph Geep.
Now we will define the alternative descriptor in Proposition 3.4 more formally and prove the theorem.
Definition B.7. Given graph G (V, C, and filtration functions f= (fu, fe). We define ((f) = (bb()), (()) p' hev U [(((e), d(e). a(C) pf (c) (ind. eycles)-
Here, the first four components are the same as RePHINE, (Definition 2.3). The component p/ refers to the following data.
26

---

Let d be the time the vertex e dies in and G(v) be the connected component of e at time d. The edge filtration gives a sub-filtration of G(v) such that at time we start with only the vertices of (vv) and we have all of (vv) at time d. This gives sequence of subgraphs:
vertices of G(u) = G(u)) & G(v)1 .... Ç G( G(u) (t)
p'(v) returns the cigenvalues of the Laplacians p and (G for all p m with respect to the filtration (t). Here i refers to the subscript G(v); in the filtration. The definition of p' (c) for represents a cycle (in the sense of (GV)) is defined similarly, with the graph being the connected component of the time is born in.
Now we will prove that no more expressive than SpectRe given a technical assumption. The assumption is that we need to remember which vertex is assigned to which tuple and which edge (representing cycle) assigned which tuple in our computation of SpectRe. This assumption is always satisfied for a computer algorithm, as computing SpectRe (or RePHINE) in practice already goes through such assignments (see Algorithm 2 of [33]).
Proof of Proposition 3.4. Let us look at why the SpectRe alternative does not give more informa- tion than our SpectRe (Def 3.1) for vertices. The argument for the Ist-dimensional components will follow similarly.
By Lemma B.5 and Corollary B.6 above, we have that A (G(v) is equal to the graph Laplacian of G(v)itn = G(v)m = G(v). On the other hand, Lemma B.3 implies that (G(t) A (G(u).) where A denotes the 1st combinatorial Laplacian. The multiplicity of the zero eigenvalues of (G(v) is equal to dim H1 (G(v);) which can be recovered by looking the number of (1,d(e)) with E G(v) that has appeared before or at G(v);
By Lemma B.3, the non-zero eigenvalues of A st (G(v)) are equal to the non-zero eigenvalues of the graph Laplacian of G(v),. Although G(v); may be connected, we can mark its connected components as CI,..., C, (as graphs). Let ((i) be the time where the filtration (t) got to G(v); For each 1 S j < r. we let aj S ((i) be the time for which the connected graph C, is created. The creation of the graph Cj is done either by merging two components (i.e. a vertex in Cj died at time aj) or by adding cycle (i.c. an was born at time ay). so there exists tuple in the SpectRe (Def 3.1) diagram that has the non-zero eigenvalues of the graph Laplacian of Cj. Doing this for all
recovers the non-zero eigenvalues of A +tp (G()).
The upshot that considering the eigenvalues of persistent Laplacians on edge filtrations reduces to computations that could be found from the graph Laplacian and persistent homology.
C RePHINE on Monochromatic Graphs
Lemma C.1. Let G and H be two graphs with the same number of nodes with single color, then RePHINE can differentiate and H if and only if either bo(G) + bo(H) (H) or bT(G)) + b, (H).
Here bo. by refer to the Oth 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, fcr fc are both constant functions of values ay, ag. so the and 7 parameters of RePHINE for G and H are the same and can be discarded. Here, the filtrations with respect to fc has two steps - 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, and Se are constant, a vertex either dies at time ay or at infinity, and all independent cycles are born at time ag. Thus RePHINE can differentiate G and H if and only they have different counts of pairs (0, av), ) (0, oo), and (1, ag). Since G and have the same number of vertices, these counts differ if and only if bo (G) o bo (H) and by (G) # bi (H). O
27

---

D Considerations and Comparisons with Alternative Designs
In this section, discuss on and how some topological descriptors we described in the main text may behave on alternative filtration and descriptor designs. Specifically, we will be discussing:
1. The behavior of PH for Biparameter Filtrations.
2. The behavior of PH for Vietoris-Rips Filtrations.
3. Spectral information on vertex-based filtrations.
D.1 Vertex and Edge Filtration vs. Biparameter Filtration
The purpose of this section is to compare the individual filtrations of fo and fe against the biparameter filtration inducded by fo and fe together.
Definition D.1. Let f.g. G + IR be two filtration functions of a graph G. We define a function [()x),((x)) A biparameter filtration of G is the collection of the x (-oo, (]).. Let (o, On be the time steps for the filtration of by J. and let bo:... bm be the time steps for the filtration of G by g. We also let a ao and b-1 < bo- The collection
fag: G 2R2 with / (g)())
subgraphs G..t == (ʃ + g) ((= ((-o0,
= DE (. (.................b. and have a poset structure induced by inclusions G.,t C G.','' for S s' and f S t'. For our purposes, the biparameter persistence of (G, f,g) is the PH of all possible poset pathes in the collection A.
The upshot of this section in the appendix is the following result.
Proposition D.2. Let for fe G + R be vertex-level and edge-level filtration functions (still with respect to coloring), then the biparameter persistence of (G, f.g) is strictly more expressive than the PH of (G. f) added with the PH of (G.g).
Proof. Let G and H be the following graphs:
R
R
B
B
R R
B
B
G
H
In this case, one can check PH in Definition 2.2 cannot tell them apart for any choices of f. and
fe (this was also done in [33]). Now let fe B) fe = (B) 1, (R) = Consider the sub-filtration of the 2-parameter filtration given by G..I. ie. (Go. - G1, G2,1 and H., respectively. One can check that this is the vertex-coloring filtration fo on the subgraphs:
B
B
PRRP
R
B
G3.1
H3.1
In this case, the left one gives persistence pairs (1, 2), (2, 2), (2, oo), (1, oc) (since red node (R) and a blue node (B) die here at t = 2), but the right one gives pairs (1,)0), (1, oc), (2, 2), (2, 2) (since the two R's die here at 2).
D.2 Vietoris-Rips Filtrations
In our main paper, we were concerned with conducting filtrations directly on the given graph G. The idea of a Vietoris-Rips (VR) filtration is to build simplicial complex K out of the graph
28

---

and examines a filtration on K instead. The hope is that the filtration on K would contain more information. For our purposes, a Vietoris-Rips (VR) filtration defined as in the discussions right under Theorem 1 of Ballester and Rieck [2]:
Definition D.3. Given a graph G = (V. E), we consider the filtration Jv of a simplicial complex K, where K is the set of all non-empty subsets S of V such that the diameter of 5 is not infinity (ie. they are all reachable from one another), and the filtration is fv( nazu,vda(tt v) (where dg is the shortest-path distance). We write VRPH(G) be the persistence diagrams associated this filtration (K, fv).
We note here that VRPH is, general, incomparable to PH (Definition 2.2) in terms of expressive power. Indeed, let G be a path-graph on 3 vertices and H be cycle graph on 3 vertices, then VRPH cannot differ them (see the discussions right before Section 5 [2]), but PH clearly can, due to the presence of a cycle in H that it can detect. On the other hand, the PH used in Definition 2.2 is color-based and processes graphs with the structure of colors on them. On monochromatic graphs, PH is no more expressive than the number of connected components and independent cycles, whereas VRPH can tell more examples apart as it does not need to respect the colors. More comparisons between VRPH and other persistence methods are present in Table 3 of Ballester and Rieck [2].
Thus, rather than viewing VR filtrations as a strictly richer simplicial filtration, the graph filtration we considered and the VR filtrations are really complementary to each other. There is no reason to expect the two to comparable we also add in spectral information either. would be interesting. though, to look at how combinatorial Laplacians and persistence Laplacians method behave VR filtrations (or simplicial filtrations in general).
We do note that, a simplicial filtration of K adds in the entire graph first, and then adds in the higher dimensional simplicies later time, then it does subsume the context of graph-based filtration. A full simplicial filtration may in general be quite difficult to enumerate when the scale of the base graph gets larger. For example: on a connected graph G with n vertices, the full VR filtration on G will go through 2 - many simplicies. This is exponential in scale whereas SpectRe can be done in polynomial time with respect to G.
D.3 Adding Vertex-level Spectral Information SpectRe
In the definition of SpectRe (Definition 3.1), we added an extra 7-parameter with respect to the edge-level filtration fe. One can observer, as in the proof of Theorem 4.5, that changing the function fo has no effect on the o-parameter of the respective vertices. One can consider what would happen we want to add spectral information with respect to fo well.
From here we make an interesting observation on whether Proposition 3.4 extends to the case of fo- For edge-based fe, we observe that the proof of Proposition 3.4 follows from Corollary B.6 in Appendix B- that the non-zero eigenvalues of persistent Laplacians in edge-based filtrations on graphs can be recovered by the eigenvalues of the graph Laplacians. We note this is however not true for wertex filtrations.
Indeed, consider a two step filtration K C I, where I. is the path-graph on 4-vertices labeled 1-2-3-4 and is the discrete subgraph {1, 43. This filtration is the vertex-based filtration of a function fu given by [1) (4) = 1 and f2) (3) = 2. If we only look at the graph Laplacian spectra of the filtration, would get that K has eigenvalues 0, 0 and L has eigenvalues 0, /2, 2, v2.
1/3 -1/3)
The persistent O-dim Laplacian of the pair (K, L) is the matrix
-1/3
1/3
with eigenvalues
0, 2/3/3. This can be verified using the Matlab code in Mémoli et [44] with inputs
B1 = [o 0];
B2 [-1 0; 1 -1 0; -1; 0 0 1];
Gind = [1 4];
The extra 2/3 cannot be recovered from the graph Laplacian spectra of K and alone. Indeed,
1/2 -1/2
for a different filtration of L with K' [1,3), we would get the matrix eigenvalues 0, 1.
(-1/2 1/2
with
29

---

E Datasets and implementation details
Table 4: Statistics of datasets for graph classification, for TUDatasets obtain random 80%//1%//10% (train/val/test) split. For ZINC and OGB- -OB-MM,, we use public splits.
Dataset
graphs
#caasses
Avg #nodes
Avg #edges
Train%
Val%
Test5
MUTAG
188
2
17.93
19.79
80
PTC-MM
336
2
13.97
14.32
80
10
PTC-MR
344
14,29
14.69
80
10
PTC-FR
351
14.56
15.00
80
10
NCII
4110
29.87
32.30
80
NCT109
4127
2
29.68
32.13
80
10
IMDR-B
1000
19.77
96.53
80
10
MOLHIV
41127
25.5
27.5
Public Split
ZINC
12000
23.16
49.83
Public Split
Datasets. Table 4 reports summary statistics of the real-world datasets used in the paper. MUTAG contains 188 aromatic and heteroaromatic nitro compounds tested for mutagenicity with avg. number of nodes and edges equal to 17.93 and 19.79, respectively. The PTC dataset contains compounds labeled according to carcinogenicity on rodents divided into male mice (MM), male rats (MR), female mice (FM) and female rats (FR). For instance, the PTC-MM dataset comprises 336 graphs with 13.97 nodes (average) and 14.32 edges (average). Except for ZINC and MOLHIV, all datasets are part of the TUDataset repository, vast collection of datasets commonly used for evaluating graph kernel methods and GNNs. The datasets are available at https: / /tte:://hrrraaa //ch//rrrrrrrr smrrs. gi thub. io/ /ataasssss////// docs/datasets/ In addition, MOLHIV is the largest dataset (over 41K graphs) and is part of the Open Graph Benchmark', We also consider a regression task using the ZINC dataset - subset of the popular ZINC-250K chemical compounds [34], which is particularly suitable for molecular property prediction [21].
Our first set of synthetic datasets comprises minimal Cayley graphs special class of Cayley graphs only partially understood. For instance, it is unkonwn whether their chromatic number is bounded by global constant. These datasets have been used to assess the expressivity of graph models [2] and can be found at https: htt///oouooooaaareeeeoo a benchmark for GNN expressiveness comparison. It includes 800 non-isomorphic graphs arranged pairwise manner to construct 400 pairs in four categories (Basic, Regular, Extension, CFT). Basic graphs consist of 60 pairs of W-WL-indistigguisabbl graphs. Regular graphs consist of 140 pairs of regular graphs split into simple regular graphs, strongly regular graphs, 4-vertex condition graphs and distance regular graphs. For further details on the remaining graph structures, we refer to Wang and Zhang [61].
wwteeeettteettrrrrraar http:/minmmmmmmmcemm -cyleyy BREC
Experimental setup. We implement all models using the PyTorrch Geometric Library [23]. Our implementation is an extension of the official code repository of [33]. For all experiments, we use cluster with Nvidia V100 GPUs.
For the experiments on real data, we employ MLPs to obtain vertex and edge filtrations followed by sigmoid activation functions, following [33]. We use two different DeepSets to process the O-dim and I I-dim diagrams.
Regarding model selection, we apply grid-search considering a combination of {1,2] GNN layers and (1, 4} filtration functions. We set the number of hidden units in the DeepSet and GNN layers to 32, and of the filtration functions to 16 i.e., the vertex/edge filtration functions consist of a 2-layer MLP with 16 hidden units. The GNN node embeddings are combined using a global mean pooling layer. We employ the Adam optimizer [35] with a maximum of 500 epochs, learning rate of 10 and batch size equal to 64.
We use a random learning rate of 10 3 that is halved if the validation loss does not improve over 10 epochs. We apply carly stopping with patience equal to 30.
(train/val/test) split for all datasets. All models are initialized with
30

---

Implementation note. For the sake of full transparency, while preparing the final version of the manuscript, we discovered that an earlier version of our implementation contained minor error in the computation of the augmented Forman- curvature. This issue affected a few results reported in Table 2 and Table and accounts for small numerical discrepancies with the previous version of the manuscript. After correcting the implementation, all results were recomputed. Importantly, the correction does not alter the qualitative findings of the paper: in particular, the conclusion that SpectRe is the rest-performing model across our experiments remains unchanged. Further details are available in the official code repository.
F
Additional experiments
For completeness, we consider two sets of additional experiments. First, we run an ablation study to measure the impact of using partial information SpectRe's performance BREC datasets. The second group of experiments aims to assess the performance of SpectRe when combined with other graph neural networks. To do so, consider the graph transformer model in [48] backbone GNN.
Table 5 shows results regarding 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 on Basic, Regular, and Extension. However, if we remove the spectral information, the expressivity drops significantly SpectRe without spectrum reduces to RePHINE. We note that using partial spectrum is one approach to speed up SpectRe.
Table 5: Additional ablation study: SpectRe with partial spectral information (1/3 of the total number of cigenvalues) and Laplacian Spectrum (LS) on the BREC datasets. The results show that using only a small subset of eigenvalues allows distinguishing almost as many graphs as the original (full spectrum) approach. Note that RePHINE corresponds to SpectRe with spectral information.
Dataset
PH
PH
RePHINE
LS
SpectRe
SpectRe (partial spectrum)
Basic (60)
0.03
0.98
0.98
1.00
1.00
1.00
Regular (50)
0.00
0.94
0.94
1.00
1.00
1.00
Extension (100)
0.07
0.55
0.55
1.00
1.00
1.00
CFI (100)
0.03
0.03
0.03
0.04
0.04
0.03
Distance (20)
0.00
0.00
0.00
0.05
0.05
0.00
Table also reports results using LS (Laplacian Spectrum) on BREC datasets. The results show that LS perform on par with SpectRe on all datasets. This somehow expected, given the identical performance of PH and RePHINE under our simple choice of filtrations. It is worth noting that LS a simplified version of SpectRe, and also contribution of this paper - as far as we know, no prior work has exploited persistent spectral information in graph learning.
Table 6 shows the results of integrating SpectRe into GPS. Leveraging topological descriptors boosts the performance of the graph Transformer in 3 out of 4 datasets. Again the gains achieved by SpectRe higher than those obtained with RePHINE. In these experiments, we applied the f'st variant of SpectRe: specifically, we used the power method to approximate the largest eigenvalue when 9, and computed the full spectrum otherwise. Additionally, we employed a scheduling strategy, computing the cigendecompasition at only one-thire of the filtration steps.
Table 6: Graph Transformer (GPS, [48]) and SpectRe. Here, we consider the combination of topological descriptors with SOTA graph model. As we can observe, SpectRe boosts the performance of the GPS model and beats RePHINE. For ZINC, we only considered a single filtration.
Method
NCI1
NC1109
IMDB-BINARY
ZINC
GPS GPS+REPHINE
81.51 + 1.72
77.00 + 0.68
76.00 + 2.83
0.38 0.01
82.36 0.86
77.97 + 2.74
71.50 = 2.12
0.34
GPS+FastSpectRe
83.33 + 2.23
79.66 + 0.34
75.50 0.71
0.34
31

---

Finally, we also provide experimental results regarding our stability bounds. In particular, we look at the first 4 graphs from the BREC dataset (basic.npy). For each graph, we define the base filtrations (o., fo) with fe being the degree of the vertex and fe being the average of the degree of the two vertices. Table shows the bottleneck distance and the inequality bound 3| gell + II5e go for different choices of (e).
Table Empirical validation of the stability bounds.
Graph ID
RePHINE Dist
RePHINE Bound
SpectRe Dist
SpectRe Bound
sin(10f.)
5fe
G1
65.25
78.30
66.23
78.30
G2
55.25
66.30
56.30
66.30
G3
68.25
86.99
69.25
86.99
G4
62.26
72.30
62.26
72.30
0.1f exp(-fe)
G1
21.18
24.19
71.95
24.19
G2
17.77
20.28
65.98
20.28
G3
22.59
26.60
72.37
26.60
18.78
21.79
60.60
21.79
The results in Table correspond to the expected behaviors. We first see that no matter what the (gv,9el is, the RePHINE distance is always bounded by the RePHINE bound, which corresponds to RePHINE being globally stable. For SpectRe, setting 9. = sin(10ff), ge = 5fe does not break stability. This is because of two reasons (I) changes in the vertex-filtration function do not affect stability, and (2) the change fe + 5ge does not cross the region of non-injectivity. We also remark without breaking stability. When 9. = 0.1f. + 0.1, ge = exp( (e(- we see the stability of SpectRe is broken. This expected behavior because exp(-fe) is order reversing function, and the path from fe to exp(-fa fe) would necessarily cross some region of non-injeontie non-injectivity.
that Reason (2) shows there is great flexibility to perturb
32

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We summarize all contributions in Table 1, explicitly indicating theorems and definitions and where to find them in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification:
We discuss limitations Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer: [Yes]
Justification:
We provide detailed proof' in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide implementation details in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
34

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: As mentioned the Abstract, we make our code available at https:// gi thub. com Aa Malto--QuML/SpectRee/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / httppsscccppbccccccceecce hepollcc/giieee Codeeubbm ssi aasonnooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details on datasets, splits, and hyperparameters are provided in Appendix C (Implementation Details).
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide error bars for all experiments real data (Section 6).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes)
Justification:
We describe the compute resources in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /nwurrrursp.../ cc httpppi//ttiissptiiieeep
Answer: [Yes]
Justification: Authors have reviewed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss broader impact in the main text (just before the acknowledgments).
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
36

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not poses high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the original papers related all datasets/toolboxes used.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
38

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLMs significant relevant part of the work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https : //tp:///eeuupppeeeeee hct.s//cccccooeeeeeeee/2222222 for what should or should not be described.
39


Reviews:
[{"review_id": "jHwMDutS4t", "reviewer": "Reviewer_aJUR", "summary": "This paper introduces SpectRe, a topological descriptor for graphs that enhances persistent homology (PH) diagrams with spectral information. Designed to be more expressive than prior methods like RePHINE, SpectRe augments persistence tuples with eigenvalues of the graph Laplacian at critical filtration steps. The authors provide a theoretical analysis of the descriptor's expressivity and local stability, and demonstrate its effectiveness on synthetic isomorphism tests and real-world graph learning tasks.", "questions": "1. **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\"?\n2. **On Comparison with Multi-Parameter Persistence:** The paper builds upon single-parameter persistence. How do you see SpectRe's expressivity in relation to representations derived from Multi-Parameter Persistence (MPH) [1, 2, 3]? Since MPH can capture more complex interactions by using multiple simultaneous filtrations, could replacing the single-parameter PH backbone of SpectRe with an MPH backbone lead to an even more powerful descriptor?\n3. **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?\n4. **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?\n\n\n**References**\n\n[1] Magnus Bakke Botnan and Michael Lesnick. An introduction to multiparameter persistence. In Representations of algebras and related structures, EMS Ser. Congr. Rep., pages 77–150. EMS Press, Berlin, [2023] ©2023.\n\n[2] Oliver Vipond. Multiparameter persistence landscapes. Journal of Machine Learning Research, 21(61):1–38, 2020.\n\n[3] Xin, C., Mukherjee, S., Samaga, S. N., and Dey, T. K. GRIL: a 2-parameter persistence based vectorization for machine learning. In Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), volume 221 of Proceedings of Machine Learning Research, pp. 313–333. PMLR, 7 2023.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n- The paper is theoretically sound and provides a comprehensive analysis of the proposed SpectRe descriptor. The expressivity proofs and the stability property of are well-executed.\n- The isomorphism tests on synthetic datasets are well-designed and clearly support the theoretical claims about the superior expressive power of SpectRe.\n- The paper is well-written and presents its complex ideas in a structured and understandable manner.\n\n**Weaknesses:**\n- 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. The method essentially decorates an existing descriptor with a well-known useful feature type. The main theoretical result—that adding more information (spectral features) increases the model's ability to distinguish non-isomorphic graphs—is not surprising. \n- 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.", "was_revised": true, "final_justification": "I thank the authors for a thoughtful and highly productive discussion. Their rebuttal was exemplary.\n\nMy initial concerns centered on the novelty of the paper's main theoretical claims. After a constructive exchange, the authors have agreed to significantly revise the paper to address these points. Specifically:\n\n- On Expressivity (Thm. 3.4): The authors have acknowledged that their claim about the persistent Laplacian's expressivity is limited to the specific case of edge-based graph filtrations, where the result is a direct consequence of known properties established in prior work. They have committed to citing these works and clarifying this important context. Their new counter-example for vertex-based filtrations is an excellent addition that adds valuable nuance and strengthens their discussion.\n\n- On Proof Techniques (Thm. 4.4): I am satisfied with their commitment to properly cite the standard TDA techniques used in their stability proof.\n\nThis discussion has clarified my final assessment. The paper introduces SpectRe, a useful descriptor. However, the authors' revisions will now accurately frame the work as a valuable exploration of a specific, practical case (edge-filtrations), with theoretical results that follow from known properties and standard techniques. This limits the overall novelty of the contribution.\n\nFor these reasons, I am maintaining my score of 4 (Borderline Accept). The paper is technically solid and the authors' response has been outstanding, but its contribution is ultimately more incremental than groundbreaking.", "rebuttal": "We are grateful to Reviewer aJUR for their time and detailed comments. We reply to your comments/questions below.\n\n```\nThe 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.\n```\nThank 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.\n\nFor 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.\n\nIn 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.\n\nWe 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.\n\n```\nThe main theoretical result ... is not surprising.\n```\nThank 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.\n\n```\nWhile 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.\n```\nWe 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.\n\nMost 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.\n\n```\nOn 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\"?\n```\nThank 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.\n\n```\nOn Comparison with Multi-Parameter Persistence\n```\nThank 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.\n\nIn 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.\n\nIn 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\n```\nR - R - B     B - R - R - B\n     \\---B\n``` \nIn 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:\n```\nR   R - B    B - R  R - B\n     \\---B\n```\nIn 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.\n\n```\nOn 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?\n```\nThank 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)$.\n\nIntuitively, 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**.\n\nIntuitively, 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.\n\nNumerically, 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.\n\nWe 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.\n\n```\nOn 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?\n```\nThank 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.\n\n---\n\nMany 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.\n\n[1] Persistent spectral graph. R. Wang, D. Nguyen, G. Wei. \n[2] Talk: Persistent harmonic forms. A. Lieutier."}, {"review_id": "8iuI3fIabi", "reviewer": "Reviewer_jmrk", "summary": "The paper extends the existing work in the line of using Persistent Homology (PH) methods for Graph Representation Learning. \n\nMore specifically, the authors extend the existing work of Immonen et. al. [28] by incorporating Laplacian spectral information into the PH invariants, which are then fed into the filtration analysis typical of PH-methods for GNNs.", "questions": "\"189 The intuition behind why RePHINE cannot differentiate the\n190 examples in Figure 3 is that it has the same amount of expres191 sive power as counting the number of connected components\n192 and independent cycles (i.e. the harmonic components of the\n193 Laplacian) on a monochromatic graph .. \"\n\nPlease cite this as a theorem from an earlier paper, or prove it somewhere.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The exposition is very clear. \n2. The stability analysis is quite thorough. \n\nWeakness\n\n1. The experimental set-up is mainly designed to compare the results of this paper vs the Immomen paper. There are no comparisons with other state-of-the-art GNNs. In particular, I would like to see a baseline of GNNs which use spectral information in a simple manner (there are tons of models, message-passing based or transformed based which do this). The theoretical results (Theorem 3.2, Theorem 3.3) do not seem very hard to prove. \n\nOverall, the paper seems to be focused on exceeding the results in the Immomen paper. Perhaps PH enthusiasts can better describe the significance of these results (stability section): The broader significance of these results is not so clear to me.\n\n2. I do not see how the stability section is connected with the rest of the paper. Why are there no experimental results to demonstrate the significance of these results? \n\n3. The computational costs of SpectRe are very prohibitive, compared to SOTA GNNs.", "was_revised": true, "final_justification": "The authors have addressed my main concerns via detailed feedback (SOTA GNNs, Spectral Information, Stability). Overall, I am not convinced if the paper will have a strong impact on the field: This is why I have updated my score to a borderline accept.", "rebuttal": "Thanks for your review. We reply to your comments below.\n\n```\nThere are no comparisons with other state-of-the-art GNNs. \n```\nThanks 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.\n```\nIn particular, I would like to see a baseline of GNNs which use spectral information in a simple manner.\n```\nA 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.\n\nTo assess the impact of a simpler spectrum-based descriptor on expressivity, we have run experiments using LS (Laplacian Spectrum) on BREC:\n\n| Dataset         | PH⁰  | PH¹  | RePHINE | SpectRe | **LS** |\n|-----------------|------|------|---------|---------|--------|\n| Basic (60)      | 0.03 | 0.97 | 0.97    | 1.00    | **1.00** |\n| Regular (50)    | 0.00 | 0.94 | 0.94    | 1.00    | **1.00** |\n| Extension (100) | 0.07 | 0.70 | 0.77    | 1.00    | **1.00** |\n| CFI (100)       | 0.03 | 0.16 | 0.28    | 0.77    | **0.72** |\n| Distance (20)   | 0.00 | 0.00 | 0.00    | 0.05    | **0.05** |\n\nThe 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.\n\n```\nThe theoretical results (Theorem 3.2, Theorem 3.3) do not seem very hard to prove.\n```\nThank 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.\n\n**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.\n\nPlease see the answer to the comment below for why proving stability (Section 4) was also quite involved.\n\n```\nThe broader significance of these results [stability] is not so clear to me.\n```\nThank 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.\n\nFrom 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.\n\n```\nWhy are there no experimental results to demonstrate the significance of these results [stability]?\n```\nTo 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)$.\n\n| $g_v$              | $g_e$              | **Graph ID** | **RePHINE Dist** | **RePHINE Bound** | **SpectRe Dist** | **SpectRe Bound** |\n|--------------------|--------------------|--------------|------------------|-------------------|------------------|-------------------|\n| $\\sin(10 f_v)$     | $5 f_e$            | G1           | 65.25            | 78.30             | 66.23            | 78.30             |\n|                    |                    | G2           | 55.25            | 66.30             | 56.30            | 66.30             |\n|                    |                    | G3           | 68.25            | 86.99             | 69.25            | 86.99             |\n|                    |                    | G4           | 62.26            | 72.30             | 62.26            | 72.30             |\n| $0.1f_v+0.1$       | $\\exp(-f_e)$       | G1           | 21.18            | 24.19             | 71.95            | 24.19             |\n|                    |                    | G2           | 17.77            | 20.28             | 65.98            | 20.28             |\n|                    |                    | G3           | 22.59            | 26.60             | 72.37            | 26.60             |\n|                    |                    | G4           | 18.78            | 21.79             | 60.60            | 21.79             |\n\nThe 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**.\n\nFor 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.\n\n```\nThe computational costs of SpectRe are very prohibitive, compared to SOTA GNNs.\n```\nIndeed, 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). \n\n```\n Please cite this as a theorem from an earlier paper, or prove it somewhere.\n```\nWe will prove it here as follows and include in the paper.\n\n**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)$.\n\nHere $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.\n\n**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).\n\n---\nWe 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."}, {"review_id": "FtAZ5f3g5c", "reviewer": "Reviewer_77B6", "summary": "This paper introduces a new topological descriptor for graphs, SpectRe, which enhances RePHINE diagrams by incorporating the nonzero eigenvalues of the graph Laplacian at each filtration step. The authors show that SpectRe is strictly more expressive than both RePHINE and the Laplacian spectrum alone, and establish that it is invariant under graph isomorphisms. They also define custom bottleneck-like metrics under which RePHINE is globally stable and SpectRe is locally stable (under an injectivity assumption). Experimental results on graph isomorphism tasks (Cayley graphs, BREC) and real-world GNN benchmarks (MUTAG, ZINC, etc.) show that SpectRe outperforms prior persistence-based descriptors in both discriminative and predictive settings.", "questions": "1. How sensitive is SpectRe to noise or perturbations in the filtration functions, particularly when injectivity is violated?\n\n2. Can the stability results be extended to include non-injective filtrations in some approximate sense?\n\n3. Would using approximate spectral methods (e.g., Nyström) change expressivity, or just reduce fidelity?", "limitations": "The authors note the computational complexity and the lack of global stability for SpectRe. I’d add that the injectivity assumption may be hard to guarantee in real applications, and there’s some ambiguity about how robust SpectRe is to near-ties or small perturbations in filtration values. The method also assumes access to full eigenvalue spectra (at least at small graph sizes), which may limit applicability at larger scale.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The idea is conceptually clean and fills a real gap in the PH literature. Augmenting persistence diagrams with spectral information has been discussed before, but this is the first implementation that (i) actually improves expressivity over RePHINE and Laplacian individually and (ii) is formalized with a proper stability framework.\n\n2. The theoretical results are solid. The expressivity separation is clearly demonstrated (Figure 3), and the stability results (global for RePHINE, local for SpectRe) are carefully stated and proven with new metrics defined for each case. The counterexample in Example 4.6 is also good for setting expectations.\n\n## Weaknesses\n\n1. The method is significantly more expensive than standard PH descriptors, especially on large or dense graphs. The authors mention scheduling and power methods, but they don’t provide any concrete timing comparisons or resource benchmarks.\n\n2. 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. The mean improves slightly, but the standard deviation is rather high in most cases.\n\n3. 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. It would be good to have some robustness analysis or at least an empirical sanity check here.\n\n4. The lack of ablation is noticeable. It’s not clear whether the gains come primarily from the spectral component or whether there is some synergy with RePHINE. A comparison with a \"spectrum-only\" variant would help clarify this.\n\n## Verdict\n\nThis paper introduces a well-motivated and clearly beneficial modification of persistence-based graph descriptors. The improvements over RePHINE and the Laplacian spectrum are theoretically well-justified. That being said, Table 3 does not leave me with a particularly convincing impression of the real-world empirical utility of the method and I do think the lack of ablations and runtime analysis weakens the empirical section. Additionally, the local-only stability is a limitation worth highlighting. All things considered, I am inclined to give the paper a weak reject rating in its current state.", "was_revised": true, "final_justification": "This paper introduces a well-motivated and clearly beneficial modification of persistence-based graph descriptors. The improvements over RePHINE and the Laplacian spectrum are theoretically well-justified. However, downstream improvements in Table 3 are modest and in many cases not clearly statistically significant. Additionally, after the rebuttal discussion, I note that the additional experiments in the appendix (e.g., Graph Transformers, LS on BREC) help clarify the relative contributions of each component and this goes part of the way toward addressing my request for ablations. The expanded discussion on stability and the injectivity assumption in the rebuttal was useful and I appreciate the formal attempt to quantify the impact of injectivity violations; including this in the main text would strengthen the paper. All things considered, I now lean towards a weak accept rating for the paper and have updated my review accordingly.", "rebuttal": "Thank you for your comments. We reply to your comments/questions below.\n\n```\nThe method is significantly more expensive than standard PH descriptors, ...\n```\nThank 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.\n\n```\nI 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...\n```\nWe 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).\n\nMost 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. \n\n```\nThe 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 \n```\nThank 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).\n\nHere, 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.\n\nWe 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).\n\nWe also did an empirical verification of the stability results. Please see our response to **Reviewer jmrk** for more details\n\n```\nThe lack of ablation is noticeable. ... A comparison with a \"spectrum-only\" variant would help clarify this.\n```\nWe 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.\n\nAdditionally, we have run experiments using LS (Laplacian Spectrum) on BREC datasets. The results are:\n\n| Dataset         | PH⁰  | PH¹  | RePHINE | SpectRe | **LS** |\n|-----------------|------|------|---------|---------|--------|\n| Basic (60)      | 0.03 | 0.97 | 0.97    | 1.00    | **1.00** |\n| Regular (50)    | 0.00 | 0.94 | 0.94    | 1.00    | **1.00** |\n| Extension (100) | 0.07 | 0.70 | 0.77    | 1.00    | **1.00** |\n| CFI (100)       | 0.03 | 0.16 | 0.28    | 0.77    | **0.72** |\n| Distance (20)   | 0.00 | 0.00 | 0.00    | 0.05    | **0.05** |\n\nThe 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\n\nOverall, 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\n\n```\nQ1:How sensitive is SpectRe to noise or perturbations in the filtration functions, particularly when injectivity is violated?\n```\nThank 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$\n\nFor 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\n\n$D := d^{Spec R, 0}_B(SpectRe(G, fv, fe), SpectRe(G, gv, fe))$\n\n(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\n\n$D \\leq (a_{i+1} - a_i) + (f_e - g_e)_{\\infty} + $ \n\n$ \\max_{(H1, H2) \\in Y} d^{Spec}(p(H1), p(H2)) $\n\n$ = 2(a_{i+1} - a_i) + \\max_{(H1, H2) \\in Y} d^{Spec}(p(H1), p(H2)) $\n\nwhere 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.\n\nBy 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\n\n$D \\leq 2(a_{i+1} - a_i) + 2 \\max_{(H1, H2) \\in Y} |E(H_2)| - |E(H_1)|.$\n\nHere 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.\n\nThis is a very interesting question, and we will include this discussion in the main text and the appendix.\n```\nQ2:Can the stability results be extended to include non-injective filtrations in some approximate sense?\n```\nThank 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.\n\nHere, 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$.\n\n```\nQ3:Would using approximate spectral methods (e.g., Nyström) change expressivity, or just reduce fidelity?\n```\nThanks 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.\n\nIn fact, we can use this to further speed up FastSpectre --- by estimating the lower spectrum based on the Nystrom's approximation. \n\nWe 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.\n\n---\nThank 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.\n\n[1] Spectra of graphs. Brouwer et al\n[2] Curvature Filtrations for Graph Generative Model Evaluation. Southern, J. Wayland, M. Bronstein, B. Rieck"}, {"review_id": "y7IvF0cSga", "reviewer": "Reviewer_MSD2", "summary": "In this paper, authors propose SpectRe, a novel topological descriptor for graphs that incorporates spectral information into persistent homology (PH) diagrams. SpectRe offers greater expressiveness compared to existing graph descriptors. The authors also present concepts of global and local stability to evaluate existing methods, demonstrating that SpectRe exhibits local stability. Experimental results  showcase the effectiveness of SpectRe and highlight its potential to enhance the performance of graph-based models in various learning tasks.", "questions": "1. In the paper, authors mentioned \"Homology captures harmonic information (in the sense that the kernel of the graph Laplacian corresponds to the 0-th homology), but there is some non-harmonic information we also want to account for...\" I am not so sure if harmonic information is necessary? Could you please explain a bit?\n2. The experiments provided are insufficient to fully support the authors' claims. For instance, it is unclear whether the authors considered comparisons with local persistent homology methods.\n3. Could you please clarify the steps involved in the procedure described in Section 5 (Integration with GNNs)?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The authors demonstrate that the expressiveness provided by the non-zero eigenvalues of these spectral descriptors can be equivalently achieved by incorporating the non-zero eigenvalues of the graph Laplacians at all time steps.\n2. The authors conduct further theoretical analysis of SpectRe.\n3. The authors perform experiments, and the results highlight SpectRe's enhanced expressiveness while demonstrating its potential to improve the performance of graph neural networks on related tasks.\n\nWeaknesses:\n1. Overall, this is a strong paper. However, the introduction could be slightly improved by being more concise and clearly articulating the motivation and contributions, particularly for researchers without a background in topological data analysis (TDA).\n2. The work heavily relies on results from previous studies, which limits the novelty of its theoretical contributions.\n3. The experiments provided are insufficient to fully support the authors' claims. For instance, it is unclear whether the authors considered comparisons with local persistent homology methods.", "was_revised": true, "final_justification": "The authors make it clear that the main motivation and contribution. Moreover, it shows it claim, particularly the theorecial part, how to contribute to the community.", "rebuttal": "Thank you for your suggestions. We reply to your comments below.\n\n```\nIntroduction: motivation and contributions\n```\nThank 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.\n\n```\nThe work heavily relies on results from previous studies, which limits the novelty of its theoretical contributions.\n```\nThank 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.\n\nFor 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.\n\nFor 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.\n\n```\nThe experiments provided are insufficient to fully support the authors' claims.\n```\nThanks 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.\n\nWe 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)$.\n\n| $g_v$              | $g_e$              | **Graph ID** | **RePHINE Dist** | **RePHINE Bound** | **SpectRe Dist** | **SpectRe Bound** |\n|--------------------|--------------------|--------------|------------------|-------------------|------------------|-------------------|\n| $\\sin(10 f_v)$     | $5 f_e$            | G1           | 65.25            | 78.30             | 66.23            | 78.30             |\n|                    |                    | G2           | 55.25            | 66.30             | 56.30            | 66.30             |\n|                    |                    | G3           | 68.25            | 86.99             | 69.25            | 86.99             |\n|                    |                    | G4           | 62.26            | 72.30             | 62.26            | 72.30             |\n| $0.1f_v+0.1$       | $\\exp(-f_e)$       | G1           | 21.18            | 24.19             | 71.95            | 24.19             |\n|                    |                    | G2           | 17.77            | 20.28             | 65.98            | 20.28             |\n|                    |                    | G3           | 22.59            | 26.60             | 72.37            | 26.60             |\n|                    |                    | G4           | 18.78            | 21.79             | 60.60            | 21.79             |\n\nWe 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**.\n\nFor 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.\n\n```\nComparison with local persistent homology methods.\n```\nThank 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.\n\n```\nI am not so sure if harmonic information is necessary?\n```\nThank 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.\n\n```\nOn the integration with GNNs\n```\nTo integrate SpectRe into GNNs, we first need to obtain a vector representation of the persistence diagrams. This is done in two stages:\n\n1) We use a DeepSet to encode the graph spectrum associated with each tuple in the diagram.\n2) A second DeepSet is then applied to aggregate the encoded tuples into a single vector, yielding a fixed-size representation of the diagram.\n\nAt 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.\n\n---\nWe 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.\n\n[1] Persistent Topological Laplacians – a Survey. X. Wei and G-W. Wei\n\n[2] Stability of Persistence Diagrams. D. Cohen-Steiner, H. Edelsbrunner, J. Harer\n\n[3] Persistent Local Homology in Graph Learning. M. Wang, Y. Hu, Z. Huang, D. Wang, J. Xu"}]

Author rebuttal:

Meta-review: The paper introduces SpectRe, a topological graph descriptor that augments persistent homology diagrams with Laplacian spectral information. This leads to greater expressivity than both RePHINE and spectrum-only approaches, while retaining stability guarantees. The main contribution of the paper lies in providing proofs of expressivity and local stability. The method is also empirically validated on isomorphism benchmarks and real-world GNN tasks.

After the authors clarified some doubts during the rebuttal period, the reviewers agreed that the idea is conceptually clean and appreciated the theoretical results and their exposition. At the same time, they raised concerns about the novelty of the work, since it reuses well-known results from TDA that were not properly acknowledged throughout the paper. 

Overall, the reviewers have a positive opinion of the paper.
Decision: Accept (poster)